Langages formels, calculabilité et complexité
(ENS Ulm, 2014-2015)
Équipe pédagogique :
Chargé de cours : Eugene Asarin (Univ.
Paris Diderot, LIAFA)
Chargé de TP : Thomas Nowak
(ENS)
Horaires, salles, annonces :
Cours : jeudi 8h30-12h, salle UV, à partir du 25/9 jusqu'au 8/1
TD : vendredi 10h45-12h45, salle R, à partir du 26/9 jusqu'au 9/1
Soutenances : 22/1 matin et après-midi en salle UV; 23/1 matin en salle
INFO 2; voici le planning
Examen : 29/1 9h-12h, salle UV
Lecture de document
Le contrôle continu de cet enseignement consiste à lire, comprendre,
préparer une présentation sur ordinateur et présenter oralement un
résultat (ou quelques concepts) scientifique en se basant sur un ouvrage
ou un article de recherche. Le transparents et l'exposé doivent être faits
en français ou en anglais (toutes les combinaisons sont autorisées. La
liste des sujets est ici.
Bibliographie, documents et liens :
Examens:
Feuilles de TD : td1.pdf td2.pdf
td3.pdf td4.pdf td5.pdf
td6.pdf td7.pdf td8.pdf
td9.pdf td10.pdf td11.pdf
td12.pdf td13.pdf
Quelques livres :
- Olivier Carton, Langages formels, calculabilité et complexité,
Vuibert, 2008.
C'est « le livre du cours », l'auteur
était chargé de ce même cours à l'ENS en 2004-2010. Complet et
accessible, ce livre est très conseillé.
- Pierre Wolper, Introduction à la calculabilité, Dunod, 2006.
A lire rapidement au début de
semestre pour avoir une vision globale du sujet.
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to
Automata Theory, Languages, and Computation, Pearson Education, 2007.
Un manuel américain classique sur le sujet. Vous pouvez regarder aussi
sa version plus ancienne, voir référence suivante.
- John E. Hopcroft, Jeffrey D. Ullman, An Introduction to Automata
Theory, Languages, and Computation, Addison Wesley, 1979 Edition
recommandée.
- André Arnold, Irène Guessarian, Mathématiques pour l'informatique,
Dunod 2005.
Couvre certains thèmes (induction,
par exemple) non couverts ailleurs.
- Dominique Perrin, Jean-Éric Pin, Infinite Words, Academic Press, 2004
A regarder certains chapitres de cet
ouvrage.
- M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to
the Theory of NP-Completeness, W. H. Freeman, 1979 A
regarder briévement ce livre classique.
- Christos H. Papadimitriou, Computational Complexity, Addison Wesley,
1993. Un manuel classique très
complet sur la complexité. À lire certains chapitres.
Documents et liens sur le web :
Un petit poly sur la
calculabilité (Eugene Asarin, cours de maitrise à UJF-Grenoble)
Ancienne
page
du cours (Olivier Carton)
Plan de cours
LANGAGES RÉGULIERS
- Mots
- alphabet, lettre, mot, longueur d'un mot, notation |u|, mot vide,
notation A*
- Parenthèse sur l'induction structurelle
- Définition inductive d'un sous-ensemble
- Dérivation, arbre de dérivation
- Principe de preuve par induction structurelle
- Définition d'une fonction par récurrence structurelle (cas
non-ambigu).
- Exemples classiques : N, Sigma^*, expressions
- Automates finis
- Automates déterministes complets :
- définition A = (Q, Sigma, delta, q0, F) et exemples
- Calcul, calcul acceptant, mot accepté, langage accepté
- Opération de successeur et critère d'acceptation
- Automates non-déterministes
- définition A = (Q, Sigma, Delta, I, F)
- Calcul, calcul acceptant, mot accepté, langage accepté
- Opération de successeur et critère d'acceptation
- Théorème de déterminisation et construction de sous-ensembles.
- Autres variantes des automates finis :
- déterministes incomplets
- non-déterministes avec epsilon-transitions
- élimination des epsilon-transitions (EXERCICE)
- Classe de langages reconnaissables et ses propriétés.
- Définition de la classe de langages reconnaissables.
- Propriétés de clôture (op. booléennes, morphisme, morphisme
inverse, shuffle).
- EXERCICES : calculer le produit de deux automates ; prouver
la clôture par morphisme inverse, par shuffle.
- Algorithmes de décision : appartenance, vide, inclusion, égalité.
- Théorème de Kleene
- produit, étoile
- expressions régulières et leur sémantique
- théorème de Kleene
- passage d'une expression à un automate
- algorithme de McNaugthon-Yamada
- lemme d'Arden et résolution d'un système
- applications au patern-matching
- Théorème de Myhill-Nerode
- Notion de quotient
- Enoncé du théorème
- Congruence sur les mots.
- |etats|> =|quotients|, condition nécessaire de régularité
- automate des quotients (minimal), condition suffisante de
régularité
- exemples de langages non-réguliers (preuve par Myhill-Nerode)
- Minimisation
- congruence de Nerode sur les états d'automate
- construction de l'automate quotient
- sa minimalité
- Algos pratiques de minimisation
- calcul par raffinement successifs
- TD : algo de Brzozowski
- A lire si intéressé : algo de Hopcroft
- lemme de l'étoile
- Approche algébrique
- Reconnaissance par morphisme
- monoïde, sous-monoïde, morphisme, quotient, division
- reconnaissance par morphisme
- équivalence entre automates et monoïdes finis
- monoïde syntaxique
- calcul du monoïde syntaxique sur l'automate minimal
- « minimalité » du monoïde syntaxique
- Langages sans étoile
- Expressions SF
- exemples (ab)*, (ab+ba)*
- monoïdes apériodiques, automates non-comptant
- théorème de Schützenberger (sans preuve pour l'implication
difficile)
- Approche logique
- Logiques FO(Sigma,<) et MSO(Sigma,<)
- Cas général : Caractérisation des langages réguliers en logique
monadique de second ordre
- Langages sans étoile
- Caractérisation en logique de premier ordre ( voir TD)
- Automates sur les mots infinis et langages omega-réguliers
- Mots infinis
- Automates de Büchi
- Problème de déterminisation (voir aussi TD)
- Complémentation (sans preuve)
- Propriétés des langages omega-réguliers
- Expressions omega-régulières
- Caractérisation en logique monadique de second ordre
(presque tout laissé en exercice)
- Applications : théories décidables, notion de model-checking
GRAMMAIRES
- grammaires, dérivations, langages
- hiérarchie de Chomsky
- grammaires régulières et leurs langages
- Grammaires hors contexte
- définition et exemples
- dérivation, dérivations gauche et droites, arbre syntaxique,
ambiguïté
- forme normale quadratique de Chomsky.
- Lemme de pompage (simple)
- application à L = { anbncn |
n ≥ 0 }
- TD : lemme d'Ogden
- Propriétés de clôture et procédures de décision
- procédures de décision, algorithme de Cocke-Younger-Kasami
(CYK)
- substitution algébrique
- opérations rationnelles et morphisme
- Non-cloture par intersection et complément
- morphisme alphabétique inverse (omis)
- intersection avec un rationnel (+tard)
- Automates à pile
- définitions et exemple
- différents modes d'acceptation
- équivalence avec les grammaires
- Propriétés de clôture prouvées par automate (intersection
avec un régulier)
- 2 mots sur les automates déterministes
CALCULABILITÉ (voir mon poly
)
- Généralités
- notion de problème
- notions naïves de problèmes décidables et semi-décidables
- Fonctions récursives primitives
- Définition (inductive) de la classe RP
- Fonctions RP programmées en C
- Prédicats RP
- Propriétés de clôture
- Exemples
- Fonction d'Ackerman (sans preuve de non-RP)
- Énumération de fonctions RP est calculable mais pas RP
(diagonalisation)
- Fonctions récursives partielles
- Notion de fonction partielle
- Définition (inductive) de la classe des fonctions récursives
partielles.
- Fonctions réc partielles programmées en C
- Thèse de Church
- Machines de Turing
- Définitions : machine de Turing déterministe à une bande
bi-infinie (avec zone utilisée finie), calcul, fonction Nk->N
calculée.
- Théorème : fonction récursives partielles ó fonctions
Turing-calculables
- => Construction inductive de MT pur une fonction récursive
partielle
- <= Arithmétisation et expression des calculs par fonctions
récursives partielle
- Conséquences importantes
- Forme normale des fonctions récursives partielles : f(x)=h(x,
mx.P(x)) avec h et P récursives primitives.
- Fonction universelle U(m,x) - résultat de calcul de la machine de
nm sur l'entrée x.
- Pour f récursive partielle il existe un m, tel que pour tout x on
a f(x)=U(m,x)
- Machine de Turing universelle (un interpréteur des Machines de
Turing) qui calcule U(m,x)
- Enumération de toutes les fonctions récursives partielles fm(x)=U(m,x)
- modification pour les fonctions à k arguments.
- Théorème de paramétrisation (s-m-n) : il existe s récursive
primitive telle que fm(k,y)=fs(m,k)(y).
Explication en termes de transformation de programmes. Idée de
preuve (trop sommaire)
- application : trouver h telle que fh(m)(x)=3fm(x)2+4x2.
- Indécidabilité du problème d'arrêt
- Prédicats Arrêt(x,y)= (jx(y) converge) et K(x)= (jx(x)
converge)
- Indécidabilité du prédicat K - preuve par diagonalisation.
- Indécidabilité du prédicat Arrêt - preuve par réduction
- Preuves d'indécidabilité par réduction
- m-réduction - la définition
- m-réduction et décidabilité : si B est décidable et A £ mB,
alors
A est décidable
- Méthode de preuve d'indécidabilité par m-réduction: montrer que K
£ mP
- Technique de réduction et exemples de propriétés indécidables des
fonctions récursives partielles
- Théorème de Rice
- Semi-décidabilité
- Idée intuitive
- Définitions de prédicats semi-décidables et récursivement
énumérables (r.e.)
- Equivalence de deux dernières propriétés
- Forme normale
- Théorème de Post: P décidable si et seulement si P et son
complément sont r.e.
- Propriétés de cloture:
- Prédicats décidables: par opérations booléennes
- Predicats semi-décidables: par conjonction, disjonction,
quantification existentielle ; par m-réduction
- Prédicat T(x)=( jx est totale) n'est ni r.e. ni co-r.e.
- APPLICATIONS de la calculabilté
- Remarque sur le codage de l'entrée
- Notion de langages décidable et récursivement énumérable.
- exemples de problèmes indécidables
- PCP (en TD)
- Arrêt et atteignabilité pour les machines de Turing (machine
fixe, rubant vide et autre variantes)
- arrêt des machines de Minsky (simulation faite en TD)
- méthode de preuve par simulation (cas particulier de
réduction)
- indécidabilité de l' arithmétique de Peano
- preuve
- corollaire: représentation de prédicats r.e. en
arithmétique
- corollaire: variante du théorème d' incomplétude de Gödel
- sans preuve: théorème de Matiasevich
- pour les grammaires algébriques(TD)
- Problème de correspondance de Post (PCP)
- indécidabilité de LG(S) ∩ LG'(S') =
∅
- indécidabilité de LG(S) = A*
- indécidabilité de LG(S) = LG'(S')
COMPLEXITÉ
- Machines de Turing - variantes
- codage de l'entrée
- machines à plusieurs bandes
- Complexité en temps
- complexité en temps
- classes de complexité en temps TIME(f(n))
- Problèmatique en complexité
- Bornes supérieures
- Bornes inférieures
- Une vraie borne inférieure
- Complexité de reconnaître un palindrome par une MT à 1
ruban
- Encore sur la complexité en temps
- théorème d'accélération
- changements de modèles
- théorème d'hiérarchie (TD)
- Temps polynomial
- Classes P, ExpTime,
- P comme « tractabilité »
- exemples de problèmes de classe P
- machines nondeterministes, classe NTime (f(n))
- temps déterministe vs temps nondéterrministe
- Classe NP (rappels)
- Définition
- Caractérisation en deux étapes :
- Deviner un temoin (de taille polynomiale)
- Tester en temps polynomial
- Problème P=NP ?
- exemples de problèmes de classe NP
- Réductions polynomiales
- NP-complétude
- NP-complétude et problème P=NP
- Théorème de Levine -Cook : NP-complétude de SAT
- Exemples de problèmes NP-complets (voir aussi TD et Algo)
- 3SAT
- STABLE ( c-à-d INDEPENDENT_SET)
- NP et co-NP
- Complexité en espace
- Définitions de base
- Liens entre complexité en time et en espace
- Classes SPACE(f(n)) et NSPACE(f(n))
- Problème REACHABILITY est dans NSPACE(log n) et dans SPACE(log2(n))
-
Savitch
- Théorème de Savitch NSPACE(f(n)) est dans SPACE(f2(n)).
Graphe
de configurations
- L<NL<P<N<PSPACE=NPSPACE<EXPTIME…
- Problèmes PSPACE-complets.
- QSAT est PSPACE complet.
- UNIVERSAL_REGEXP est PSPACE-complet (voir examen du 24/1/14 et
corrigé - exercice 5.2-5.3)