Fondements de l'Informatique: Logique, modèles, calculs
CSC_41012_EP
INF 412
VIDEOS sur le cours 8
- Globalement: NP-compétude.
- ” ’Transparents en un seul fichier”’ (version imprimable 2x2)
- Partie a: Introduction. La classe P
- transparents: fichier plus haut du transparent 1 à 11..
- (partie(s) relieé(s) du polycopié: chapitre 12, section 1).
- Partie b: La classe P. Notion de réduction.
-
- transparents: fichier plus haut du transparent 12 à 19.
- (partie(s) relieé(s) du polycopié: chapitre 12, section 2).
- Partie c: La classe NP. La question P = NP?
-
- transparents: fichier plus haut du transparent 20 à 25..
- (partie(s) relieé(s) du polycopié: chapitre 12, début de la section 3).
- Partie d: NP-complétude. Stratégie pour prouver la NP-complétude.
-
- transparents: fichier plus haut du transparent 26 à 30..
- (partie(s) relieé(s) du polycopié: chapitres 12, jusqu’à la section 3.6).
- Partie e: Exemples de preuves de NP-complétude.
-
- transparents: fichier plus haut transparent 31 à 38..
- (partie(s) relieé(s) du polycopié: chapitres 13).
- Partie f: Quelques autres problèmes NP-complets .
-
- transparents: fichier plus haut du transparent 39 à fin..
- (partie(s) relieé(s) du polycopié: chapitre 13).