Calculabilité et Complexité (11X008)

Enseignant : Arnaud Casteigts
Assistants : Alexandre-Quentin Berger et Matteo De Francesco
Monitrice : Léa Heiniger

Pages du cours

• sur moodle (supports, informations, modalités d’examens, etc.)
• sur unige (informations administratives)

Notes de cours

• Préambule : [slides]
• Cours 1 : Survol du module : [slides] (pb d’enregistrements, pas de vidéo :-/)
• Cours 2 : Rappels de langages formels : [notes de cours]
• Cours 3 : Décidable, reconnaissable, simulation : [notes de cours]
• Cours 4 : Diagonalisation et indécidabilité : [notes de cours]
• Cours 5 : Théorème de Rice (et degrés de Turing) : [notes de cours]
• Cours 6 : Introduction à la complexité algorithmique (A. Berger) : [notes de cours]
• Cours 7 : Classes de complexité basiques : [notes de cours]
• Cours 8 : Relations connues; non-déterminisme; théorème de Savitch : [notes de cours]
• Cours 9 : Classe NP : [notes de cours]
• Cours 10 : NP-complétude : [notes de cours]
• Cours 11 : Exemples de réductions : [notes de cours]
• Cours 12 : Théorème de Cook-Levin : [notes de cours]