Logique, théorie des modèles, complexité
Cours de master de mathématiques (2011-12)
Programme
- Théorie des modèles, théorème de compacité, théorèmes de complétude
et d'incomplétude
- Complexité: automates finis, machines de Turing, classes P et NP
Pour cette partie, le cours suivra essentiellement quelques chapitres
du livre de Michael Sipser,
Introduction to the Theory of Computation
(Si vous ne le trouvez pas à la bibliothèque, essayez Google....) :
- Automates finis, déterministes et non-déterministes. Langages
réguliers, lemme de pompage.
- Machines de Turing et leurs variantes, thèse de Church.
Langages décidables, le problème d'arrêt.
- Complexité classes P, NP NP-complétude; primalité en temps
polynomial.
D'autres références utiles, en tout cas instructives, sont
la bande dessinée d'Apostolos Doxiadis et Christos Papadimitriou, Logicomix (à préférer en anglais, elle n'est pas chère !), le livre d'Oded Goldreich, P, NP, and NP-Completeness: The Basics of Computational Complexity,
et celui de Sanjeev Arora et Boaz Barak, Computational Complexity: A Modern Approach.
(Ces deux derniers livres insistent moins sur la théorie des automates et le fonctionnement interne des machines de Turing. Ils vont beaucoup plus loin.)
Enseignants
Horaires
- Complexité (A. Chambert-Loir).
Le mercredi, de 10h15 à 12h15, bât. 2A, salle 307.
- Théorie des modèles (P. Joray).
Le jeudi, de 10h15 à 12h15, bât. 2A, salle 305.
Les deux parties du cours concernent des notions cousines
et seront traitées indépendamment chacune des séances intégrant
cours et travaux dirigés.
Modalités de contrôle des connaissances
- Contrôle continu (note C) : 2 ou 3 contrôles
dans chacune des parties du cours.
- Examen terminal (note T) : examen écrit de 2 h
La note finale sera la moyenne (C+T)/2 ;
en cas de seconde session, seule la note obtenue lors de l'examen de rattrapage
comptera.
A priori, les documents devraient être autorisés aux
« contrôles continus » et à l'examen final.
Il y au eu un contrôle en classe le 29 février 2012, de 10h15 à 12h15 ;
il comptera pour la note de contrôle continu.
Devoir libre en temps limité, le mercredi 21 mars, de 10h15 à 12h15,
salle 004 ou 006 au bâtiment 22/23 (Irmar) : récupérer le sujet
à 10h15 auprès de Marie-Annick Paulmier et lui rendre les copies
à 12h15.
Documents disponibles
Résumé des cours
- 4 janvier : Automates finis.
Automates finis (déterministes) ;
Langages, opérations sur les langages, langages réguliers
et stabilité par complémentaire, union et intersection ;
Automates finis non déterministes.
Équivalence des automates déterministes et non déterministes ;
application à la concaténation et à la répétition des langages réguliers.
Exercices pour le 11 janvier : exercices 1 à 5
de la première feuille d'exercices.
- 11 janvier :
Lemme de pompage et exemples de langages irréguliers.
Expressions régulières.
Correction des exercices 1 et 3.
Exercices pour le 2 février : chercher
tous les exercices de la feuille (les derniers sont plus difficiles).
- 18 janvier :
Machines de Turing.
Le 10e problème de Hilbert. Description intuitive
et définition formelle d'une machine de Turing. Variantes.
- 25 janvier :
Machines non déterministes. Langages reconnaissables ;
existence de langages non reconnaissables. Langages décidables.
-
1er février :
Indécidabilité du problème de l'arrêt d'une machine de Turing.
Correction des exercices 1, 2, 4 de la feuille 2.
- 8 février :
Définition de la complexité (en temps
ou en espace) d'une machine de
Turing, d'un langage ; classes de complexité P, NP.
Langage PATH, son appartenance à la classe de complexité P.
Langages COPRIMES.
- 15 février :
Le langage PRIMES appartient à NP.
Langage SAT, théorème de Cook.
Antoine Chambert-Loir