Complexité de calcul et NP-complétude IFT-66975 Les informations pertinentes sur le cours seront placés sur cette page au fur et à mesure. Pour des informations d’ordre général, veuillez consulter le plan de cours. Acétates présentées en cours (2006): Intoduction et aperçu du cours Chapitre 0: Rappels Chapitre 1: les classes P, NP, BPP, RP, ZPP Chapitre 2: Réductions: définitions et exemples Chapitre 3: Le téorème de Cook-Levin et la NP-complétude Chapitre 4: Algorithmes d’approximation Chapitre 5: Au delà de NP Chapitre 6: Complexité d’espace Chapitre 7: Preuves interactives Chapitre 8: Théorème PCP Exercices: · Intra 2005 (questions seulement) · Intra 2005 (avec les réponses) Acétates présentées en 2005 (attention, certaines erreurs n’ont pas été corrigées! Utiliser avec précaution...) · Introduction et aperçu du cours · Chapitre 0 : Quelques rappels... · Chapitre 1 : les classes P, NP, BPP, RP, ZPP · Chapitre 2: Les réductions · Chapitre 3: Le théorème de Cook et la théorie de la NP-complétude · Chapitre 4: Contourner la NP-complétude · Chapitre 5: Hiérarchie polynomiale, EXP, NEXP · Chapitre 6: Complexité d’espace: L, NL, PSPACE, P-complétude et NC · Chapitre 7: Preuves interactives et isomorphisme de graphe · Chapitre 8: Un aperçu du théorème PCP Autres liens utiles · Les notes de cours de IFT-15751, informatique théorique · The complexity zoo: là où vivent toutes les classes de complexité! · Le weblog de Lance Fortnow: l’«actualité» du domaine… · Wikipédia: computational complexity theory · (en français) Matériel de cours de Pierre McKenzie (UdM) · Liste de problèmes d’optimisation NP · Liste de problèmes P-complets · Liste de problèmes paramétrés · A Short History of Computational Complexity (article de Lance Fortnow) |