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 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 Composition de Machines de Turing Calculer avec des MT
29/09 Fonctions rècursives (Turing calculables) reconnaissance de langages (avec MT)
semi-décisions
Extensions : MT multi-ruban
6/10 MT Multi-rubans Exercices, et théorème d'équivalence
Autres extensions
13/10 1.5 Machines de Turing non-déterministes
1.6 Grammaires générales
exercice
et théorème d'équivalence
20/10 Fonctions numériques
27/10 c_et_c_8 mu-récursivité (calculable sens de Church)⇔ récursivité (sens de Turing)
10/11 II. Indécidabilité II. Indécidabilité
1. Thèse de Church-Turing
2. Machines de Turing Universelles
3. “The Halting Problem”
17/11 II.4 Problèmes Indécidables II.4 Problèmes indécidables
24/11 II.5 Problèmes indécidables pour les grammaires II.5 Problèmes indécidables pour les grammaires
1/12 c_et_c_c Interrogation écrite
15/12 III. Complexité
15/12 Définitions

Travail à Rendre

 
m1ilc/complexite_et_calculabilite.txt · Dernière modification: 2010/10/03 07:07 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki