Automates et calculabilité (G. CORAY du LITH)
Section: Semestre: Crédits:	Informatique 4, obligatoire	Cours: Exercices: Pratiques:	2 h par semaine 1 h par semaine
Forme: Examen: Bibliographie:	Ex cathedra avec exercices Branche théorique (oral) Feuilles polycopiées, logiciels pour les exercices
Préalable requis: - Préparation pour:	Logique élémentaire, Programmation I,II, Automates et calculabilité I Algorithmique

OBJECTIFS Étudier les notions informatiques fondamentales de machine et de langage, et leurs relations mutuelles, d'un point de vue théorique. L'information qui est traitée dans les machines peut être modélisée par certaines suites de symboles, et un ensemble de telles suites constitue ce qu'on appelle un langage formel. Une machine, du point de vue théorique, n'est pas une machine physique, 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é des problèmes de traitement de l'information. CONTENU Les automates finis et les machines de Turing sont les deux extrêmes d'une hiérarchie de types d'automates, à laquelle correspond une hiérarchie de types de langages formels. La classe intermédiaire la plus importante est celle des automates à pile, utilisés dans d'importants algorithmes de traitement de l'informations textuelle (analyse syntaxique en particulier). La définition générale de la complexité d'un problème de traitement de l'information repose sur les notions de langage, de machine et de simulation: tout problème peut se ramener, théoriquement, à celui de reconnaître les expressions d'un langage particulier. La complexité d'un problème peut être mesurée par le temps ou l'espace de mémoire nécessaire à une machine pour le résoudre. Les classes de complexité de problèmes sont ainsi définis en fonction de la taille des données. Une correspondance précise peut être établie entre la hiérarchie de modèles de machines et celle des types de grammaires définissant les langages. 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