Automates et calculabilité I (J. ZAHND)
Section: Semestre: Crédits:	Informatique 3, obligatoire	Cours: Exercices: Pratiques:	2 h par semaine 1 h par semaine
Forme: Examen: Bibliographie:	Cours ex cathedra avec exercices Branche théorique (oral) Notes polycopiées
Préalable requis: Préparation pour:	Logique élémentaire, Programmation I,II Automates et calculabilité II, Algorithmique

OBJECTIFS Etudier les notions informatiques fondamentales de machine et de langage, et leurs relations mutuelles, d'un point de vuethéorique. L'information qui est traitée dans les machines peut être modélisée par certaines suites de symboles, et un ensemble detelles suites constitue ce qu'on appelle un langage formel. Une machine, du point de vue théorique, n'est pas une machinephysique, mais un modèle abstrait d'une telle machine, dont on ne retient que les aspects logiques et algorithmiques essentiels.Un tel modèle est appelé un automate. Différentes espèces d'automates sont utilisées pour caractériser la complexité desproblèmes de traitement de l'information. CONTENU Introduction sur les automates et les langages formels. La notion de simulation permet une classification des différentes espèces d'automates. Lorsqu'un automate A peut simuler un automate B, la capacité de traitement de l'information du premier est supérieure ou égale à celle du second. Les automates les plus limités sont ceux qui possèdent une capacité de mémoire finie. On les appelle automates finis. Leur étude présente un intérêt car d'importants algorithmes pratiques de traitement de l'information (analyse lexicale) reposent sur de tels automates. On connaît des espèces d'automates très simples capables de simuler toutes les autres. L'une d'elle fut inventée par Turing (1936) bien avant l'apparition des ordinateurs. Ce genre de machine permet de caractériser les limites du traitement algorithmique de l'information en général, et notamment de distinguer des fonctions (mathématiques) calculables et des fonctions non calculables. Pour prouver qu'un problème est algorithmiquement insoluble, c'est-à-dire qu'il n'existe pas d'algorithme pour le résoudre, il suffit de montrer qu'il n'existe pas de machine de Turing capable de le faire. Un problème historique prouvé insoluble de cette manière est celui de la décision en logique: reconnaître si une expression arbitraire de logique des prédicats est une tautologie. Last updated: November 1998, by Alex Bänninger. In case of problems with this site, please contact www_adm@lslsun.epfl.ch Logic Systems Laboratory, http://lslwww.epfl.ch