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:

· Exercices 1

· Exercices 2

· Exercices 3

 

· Intra 2005 (questions seulement)

· Intra 2005 (avec les réponses)

· Corrigé (devoir 1)

 

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)