Calculabilité et Complexité - Master 1

2021-2022


[Annonces] [Informations Générales] [Planning] [Énoncés de TD] [Supports Supplémentaires]

Planning

Vous trouvez ci-dessous un planning avec le contenu des séances et le materiel à lire.
Date Sujet Matériel
17/9 Problèmes et langages, codage de l'entrée, machines de Turing Livre : Préliminaires et notations ; Chapitre 1 (jusqu'à 1.2.2 inclus)
Diapos : Introduction ; Machines de Turing ; Machines de Turing - exemple
22/9 Introduction à la complexité Livre : Paragraphe 1.2.4
Diapos : Complexité Définitions
24/9 Questions sur la complexité des machines de Turing Livre : Lemme 1-O (Réduction de l'alphabet) du paragraphe 1.2.3
Diapos : Complexité Définitions
Notes : Borne Inférieure pour les Palindromes
29/9 Machine de Turing Universelle, les classes DTIME(t(n)), P,EXP Livre : Paragraphes 1.2.3, 2.1.1, 2.1.3
Diapos: La machine de Turing Universelle, Temps déterministe
1/10 Diagonalisation, le théorème de hiérarchie Livre : Paragraphe 2.1.2
Diapos : Temps déterministe
6/10 Machines de Turing non-déterministes, les classes NTIME(t(n)), NP, NEXP Livre : Paragraphes 2.2.1, 2.2.2, 2.2.4, 2.2.6
Diapos : Machines de Turing non-déterministes, Temps non-déterministe
8/10 La question P=NP, la classe coNP Livre : Paragraphes 2.2.7, 2.2.8
Diapos : Temps non-déterministe
13/10 Réductions Livre : Paragraphe 3.1
Notes : Réductions - Introduction
20/10 Réductions 2 Livre : Paragraphes 3.2.2 (pas le theorème de Cook), 3.2.3 jusqu'à la page 80)
Notes : Réductions - SAT
22/10 Réductions 3 Livre : Paragraphe 3.2.3
Notes : Autres réductions
27/10 NP-completude Livre : Paragraphes 3.2.1, 3.2.2, 3.2.4 et 3.2.5 (juste l'énoncé du Théorème de Ladner)
Diapos : Completude
Notes : Notes du cours
10/11 Partiel Corrigé