Langages formels, calculabilité et complexité
(ENS Ulm, 2011-2012)
Chargé de cours : Eugene Asarin (Univ. Paris Diderot, LIAFA)
Chargée de TP : Anne Bouillard (DI ENS, INRIA-TREC)
Cours : jeudi 9h-12h15, salle R, à partir du 29/9 jusqu’au 5/1
TD : vendredi 10h45-12h45, salle R, à partir du 30/9 jusqu’au 6/1
Soutenances : vendredi le 13, 20, 27 janvier 2012 à 10h45-12h45 et jeudi le 26 janvier à 9h-12h15, salle R
Le contrôle continu de cet enseignement consiste à lire, comprendre, rédiger un rapport et présenter oralement un résultat (ou quelques concepts) scientifique en se basant sur un ouvrage ou un article de recherche. La liste des sujets presque finale avec attribution des thèmes est ici. La date limite pour envoyer le rapport était le 25/12/11. Le planning de soutenances est ici.
Examen du 2 février 2012 : sujet (un peu long); corrigé (un peu court).
Feuilles de TD : TD1 (mots et langages) ; TD2 (automates) ; TD3 (langages rationnels) ; TD3bis (apprentissage – algo d’Angluin) ; TD4 (logique et automates séquentiels) ; TD5 (mots infinis) ; TD6 (grammaires) ; TD7 (lemme d’Ogden, automates à pile) ; TD8 (calculabilité) ; TD9 et TD10 (décidabilité) ; TD11 (complexité), TD12 (complexité)
Certaines corrections d’exercices seront mises sur cette page d’Anne Bouillard
·
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.
Un petit poly sur la calculabilité (Eugene Asarin, cours de maitrise à UJF-Grenoble)
Ancienne page du cours (Olivier Carton)
réalisé
LANGAGES RÉGULIERS
· Cours n° 1 (29 septembre) : induction, automates et langages.
o Mots
§ alphabet, lettre, mot, longueur d'un mot, notation |u|, mot vide, notation A*
o 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
o 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é.
Cours 2 (6 octobre) automates et langages réguliers
· Théorème de Kleene
o produit, étoile
o expressions régulières et leur sémantique
o 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
o Notion de quotient
o Enoncé du théorème
o Congruence sur les mots.
o |etats|> =|quotients|, condition nécessaire de régularité
o automate des quotients (minimal), condition suffisante de régularité
o exemples de langages non-réguliers (preuve par Myhill-Nerode)
o 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
o TD : Apprentissage d’Angluin
Cours 3 (13 octobre) pompage et monoides
· lemmes de l'étoile et ses variantes (y compris Ehrenfeuht-Parikh-Rozenberg)
· autres preuves de non-régularité
· Approche algébrique
o Reconnaissance par morphisme
o monoïde, sous-monoïde, morphisme, quotient, division
o reconnaissance par morphisme
o équivalence entre automates et monoïdes finis
o monoïde syntaxique
· calcul du monoïde syntaxique sur l'automate minimal
Cours 4 (20 octobre) star-free et logique
·
o « minimalité » du monoïde syntaxique
· Langages sans étoile
o Expressions SF
o exemples (ab)*, (ab+ba)*
o monïdes apériodiques, automates non-comptant
o théorème de Schützenberger (sans preuve pour l’implication difficile)
· Approche logique
o Logiques FO(Sigma,<) et MSO(Sigma,<)
o Cas général : Caractérisation des langages réguliers en logique monadique de second ordre
o Langages sans étoile
· Caractérisation en logique de premier ordre (énoncé)
Cours 5 (27 octobre) mots infinis
· o Langages sans étoile
· Caractérisation en logique de premier ordre
· Caractérisation en LTL
· Automates sur les mots infinis
· 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
Cours 6 (3 novembre) grammaires
GRAMMAIRES
· grammaires, dérivations, langages
· hiérarchie de Chomsky
· grammaires régulières et leurs langages
· Grammaires hors contexte
o définition et exemples
o dérivation, dérivations gauche et droites, arbre syntaxique, ambiguïté
o simplifications et formes normales
· petites simplifications (epsilon, A->B, symboles inutiles)
· forme normale quadratique de Chomsky.
Cours 7 (10 novembre)
· Propriétés de langages hors contexte
o Lemme de pompage (simple)
· application à L = { anbncn | n ≥ 0 }
· TD : lemme d’Ogden
o Propriétés de clôture et procédures de décision
· substitution algébrique
· opérations rationnelles et morphisme
· Non-cloture par int5ersection eyt complément
· morphisme alphabétique inverse (+tard)
· intersection avec un rationnel (+tard)
· procédures de décision, algorithme de Cocke–Younger–Kasami (CYK) -TD
· Automates à pile
o définitions et exemple
o différents modes d'acceptation
o équivalence avec les grammaires
Cours 8 (17 novembre)
· Propriétés de clôture prouvées par automate (morphisme inverse, 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
· Notion de fonction récursive générale
Cours 9 (24 novembre)
· 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.
§ Exemple : machine qui copie un mot.
§ 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 no m 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.
Cours 10 (1 décembre)
Cours 11 (8 décembre)
· exemples de problèmes indécidables
o PCP (en TD)
o Arrêt et atteignabilité pour les machines de Turing (machine fixe, rubant vide et autre variantes)
o arrêt des machines de Minsky (simulation faite en TD)
o méthode de preuve par simulation (cas particulier de réduction)
§ pour les grammaires algébriques
· codage des historiques de machines à compteurs
§ indécidabilité de LG(S) ∩ LG'(S') = ∅
§ indécidabilité de LG(S) = A*
§ indécidabilité de LG(S) = LG'(S')
§ Autre preuve : par réduction du PCP (TD)
§
COMPLEXITÉ
o 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
o Une vraie borne inférieure
§ Complexité de reconnaitre un palindrome par une MT à 1 ruban
Cours 12 (15 décembre)
O Encore sur la complexité en temps
· théorème d'accélération
· changements de modèles
· théorème d’hiérarchie –énoncé
· Temps polynomial
o Classes P, Exp,
o P comme « tractabilité »
§ exemples de problèmes de classe P
§ accessibilité dans un graphe
§ le plus court chemin (comment coder un problème d’optimisation comme problème de décision)
§ primalité (résultat de 2005, sans preuve)
§ 2-matching
· machines nondeterministes, classe NTime (f(n))
· temps déterministe vs temps nondéterrministe
· Classe NP
§ 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
§ Clique
§ 3-matching
§ Non-primalité
· Réductions polynomiales
· NP-complétude
· définition de NP-facile, NP-difficile et NP-complet
· NP-complétude et problème P=NP
· Théorème de Levine –Cook : NP-complétude de SAT
Cours 13 (5 janvier)
· Exemples de problèmes NP-complets
§ 3-sat (TD)
§ CLIQUE, STABLE, TRANSVERSAL
§ 3-Matching
§ SOMME-SOUSENSEMBLE
§
· Complexité en espace
o Complexité en espace
§ définition
§ liens entre la complexité en temps et en espace
§ classes de complexité en espace
§ théorème de Savitch
o Espace polynomial
§ exemples de problèmes en espace polynomial
§ L(M) = A* pour un automate non déterministe M
§ relations entre les classes P, NP, PSPACE et EXPTIME.
o PSPACE-complétude
§ définition
§ PSPACE-complétude de la vérité des formules booléennes quantifiées (TD)