====== Complexité et Calculabilité ======

===== Synoptique =====

^ Prof ^ Site ^ Cours ^ TP ^ TD ^ ECTS ^^
| M. Pascal Schreck |  | 24h |  |  | 3 |
^ Contenu  ^^^^^^
| Extensions des machines de Turing, machines de Turing non déterministes. ||||||
| Récursivité (au sens de Turing) et mu-récursivité (au sens de Church). ||||||
| Thèse de Church-Turing. Machine de Turing universelle et non-calculabilité. ||||||
| Exemples de problèmes indécidables, classes de complexité : P, NP et EXP, NP-complétude.||||||
^ Pre-requis ^^^^^^
| Théorie des langages  ||||||
^ Références ^^^^^^
| Lewis & Papadimitriou, "Elements of the theory of computation." ||||||


===== Notes de Cours =====

N.B. Ces notes sont relativement incomplètes pour le moment, en attendant de faire des diagrammes.

| 15/09 | [[c_et_c_1| Machines de Turing]] | Introduction\\     Définition et exemples de Machines de Turing \\     Définitions de configuration, calcul, pas de calcul, etc. Exemple et exercices. |
| 22/09 | [[c_et_c_2| Composition de Machines de Turing]] | Calculer avec des MT |
| 29/09 | [[c_et_c_3| Fonctions rècursives]] (Turing calculables) | reconnaissance de langages (avec MT)  \\ semi-décisions  \\ Extensions : MT multi-ruban |
| 6/10 | [[c_et_c_4| MT Multi-rubans]] | Exercices, et théorème d'équivalence  \\  Autres extensions |
| 13/10 | [[c_et_c_5|]] \\ [[c_et_c_6| 1.6 Grammaires générales]]  \\  [[c_et_c_ex_5| exercice]] | et théorème d'équivalence |
| 20/10 | [[c_et_c_7|]] |  |
| 27/10 | [[c_et_c_8|]] | mu-récursivité (calculable sens de Church)<=> récursivité (sens de Turing) |
| 10/11 | [[c_et_c_9|]] | II. Indécidabilité\\ 1. Thèse de Church-Turing\\ 2. Machines de Turing Universelles\\ 3. "The Halting Problem" |
| 17/11 | [[c_et_c_a|]] | II.4 Problèmes indécidables |
| 24/11 | [[c_et_c_b|]] | II.5 Problèmes indécidables pour les grammaires |
| 1/12 | [[c_et_c_c|]] | Interrogation écrite |
| 15/12 | [[c_et_c_d|]] |  | 
| 15/12 | [[c_et_c_defs| Définitions]] |  |
===== Travail à Rendre =====

  * [[c_et_c_devoir_1| Exercices à rendre pour le 29/9/2009]]
  * [[c_et_c_devoir_2| Exercices à rendre pour le 13/10/2009]]
  * [[c_et_c_devoir_3| Exercices à rendre pour le 10/11/2009]]
  * 
  * [[c_et_c_ex_5| Exercice à rendre pour le 20/10/2009]] : une grammaire qui engendre L={a^(n^2) | n ∈ N }