Fondements de l'Informatique: Logique, modèles, calculs
INF 412
VIDEOS sur le cours 9
- Globalement: NP-compétude (suite).
- ” ’Transparents en un seul fichier”’ (version imprimable 2x2)
- Partie a: Retour sur quelques problèmes NP-complets
- transparents: fichier plus haut du transparent 1 à 4.
- (partie(s) relieé(s) du polycopié: chapitre 13).
- Partie b: NP et temps polynomial non-déterministe
-
- transparents: fichier plus haut du transparent 5 à 16.
- (partie(s) relieé(s) du polycopié: chapitre 12, section 12.3.3).
- Partie c: Preuve du théorème de Cook-Levin
-
- transparents: fichier plus haut du transparent 17 à 26.
- (partie(s) relieé(s) du polycopié: chapitre 12, section 12.3.6).
- Partie d: Décision vs Construction
-
- transparents: fichier plus haut du transparent 27 à 31.
- (partie(s) relieé(s) du polycopié: chapitre 12, sections 12.4.1 et 12.5).
- Partie e: Gérer la NP-complétude
-
- transparents: fichier plus haut du transparent 32 à fin.