Fondements de l'Informatique: Logique, modèles, calculs

INF 412







Recent Changes- Printable Version - Search:



 

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).
Edit - History - Print - Recent Changes - Search - Edit menu - Private
Page last modified on October 23, 2020, at 06:42 PM