INFO724 : Algorithmique avancée, graphes et NP-Complétude

De Wiki du LAMA (UMR 5127)
Aller à la navigation Aller à la recherche

Quelques ressources bibliographiques

Ouvrage de référence :

  1. Cormen, Leiserson, Rivest et Stein, Algorithmique, 3e edition (2009). ( Aussi appelé "Introductino à l'algorithmique" pour les deux premières éditions )

Autres références bibliographiques :

  1. Wilf, Algorithms and Complexity, (1994). Disponible en ligne
  2. Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
  3. Paschos, Complexité et approximation polynomiale, (2004).
  4. Hopcroft et Ullman, Introduction to automata theory, languages, and computation. (1979).




CSAT --> 3SAT.

-->


TP

À venir.


Déroulement (2014-2015)

Cours 1 : Introduction 

- Exemple "Tri lent" triLent.sage
- Notions d'instance et de problème
- Rappels sur les graphes (nombres de Ramsey)
    - Programme qui calcule les nombres de Ramsey (du moins les premiers...)



Déroulement (2014-2015)

  • (Cours 1): 29 septembre. Introduction à la théorie de la complexité, notion de problèmes et instances.
  • (Cours 2): 1er octobre. Complexité temporelle et ordres de grandeurs. Notations grand-O, Omega, Theta.
  • (Cours 3): 3 octobre. TD, feuille d'exercices "Notation grand-O". Approche "Diviser pour régner".
  • (Cours 4): 8 octobre. Approche "Diviser pour régner" (suite + exemple du calcul de la distance minimale).
  • (Cours 5): 13 octobre. Approche "Programmation dynamique" (exemple de la découpe de barres).
  • (Cours 6): 6 novembre. Approche "Programmation dynamique" suite et fin (exemple dela distance de Levenshtein).
  • (Cours 7): 12 novembre. Algorithmes de type "retour sur bande" (backtrack), (exemple du cycle eulérien + solution polynomiale).
  • (Cours 8): 17 novembre. Problème du sudoku, réduction vers couverture exacte et algorithme Dancing Links.
  • (Cours 9): 18 novembre. Début de la théorie de la NP-Complétude. Types de problèmes et réductions polynomiales.
  • (Cours 10): 18 novembre. Réductions polynomiales suite et fin (équivalence polynomiale, Cycle hamiltonien <= Commis voyageur, Clique = EI = CA).
  • (Cours 11): 19 novembre. Classe NP et algorithmes de vérification (ex : clique appartient à NP).
  • (Cours 12): 2 décembre. NP-Complétude, logique booléenne, théorème de Cook (SAT est NP-Complet), CSAT est NP-Complet, 3SAT est NP-Complet.
  • (Cours 13): 8 décembre. Preuvens de NP-Complétude (Couverture des arêtes et SubsetSum).


Déroulement (2013-2014)

  • (Cours 1): 9 septembre. Introduction à la théorie de la complexité, notion de problèmes et instances.
  • (Cours 2): 10 septembre. Complexité temporelle et ordres de grandeurs. Notations grand-O, Omega, Theta.
  • (Cours 3): 11 septembre. TD, feuille d'exercices "Notation grand-O".
  • (Cours 4): 13 septembre. Approche "Diviser pour régner" (ex : calcul de la distance minimale).
  • (Cours 5): 18 septembre. Approche "Diviser pour régner" (suite et fin). Programmation dynamique (ex : découpe de barre et attribution des skis).
  • (Cours 6): 18 septembre. Programmation dynamique (suite et fin).
  • (Cours 7): 23 septembre. Algorithmes gloutons (ex : algorithme de Kruskal pour le calcul de l'ACM et implémentation de Union-Find).
  • (Cours 8): 25 septembre. Types de problèmes : existence, optimisation et décision (ex : commis-voyageur (décision ==> optimisation), chemin hamiltonnien (décision ==> existence) ).
  • (Cours 9): 25 septembre. Réduction polynomiale comme relation d'ordre sur les problèmes (ex : chemin hamiltonien <= commis-voyageur, clique == ensemble indépendant == couverture par les arêtes )
  • (Cours 10): 2 octobre. Appartenance à la classe NP et algorithmes de vérification. NP-Complétude.
  • (Cours 11): 2 octobre. Logique booléenne, théorème de Cook (SAT est NP-Complet), CSAT est NP-Complet, 3SAT est NP-Complet.
  • (Cours 12): 7 octobre. Coloriage avec k couleurs est NP-Complet. EI, Clique et CA sont NP-Complet. Attribution des sujets de TP.
  • (Cours 13): 9 octobre. Quoi faire avec un problème NP-Complet. Algorithmes "back-track" et algorithmes d'approximation.



Déroulement (2012-2013)

  • (Cours 1): 10 septembre. Introduction à la théorie de la complexité, notion de problèmes et instances.
  • (Cours 2): 12 septembre. Mesures de complexité, notations O, Omega, Theta.
  • (Cours 3): 12 septembre. Temps polynomial VS temps exponentiel.
  • (Cours 4): 14 septembre. Problèmes de décision VS problèmes d'optimisation, classes P, EXP, NP.
  • (Cours 5): 17 septembre. Classe coNP, démonstrantion d'appartenance à NP/coNP.
  • (Cours 6): 18 septembre. Réduction polynomiale, NP-Complétude.
  • (Cours 7): 19 septembre. Introduction au Théorème de Cook. Modèles de machines de Turing et modèle RAM.
  • (Cours 8): 24 septembre. RAM vs MTD (suite), MTN et classe NP, logique booléenne.
  • (Cours 9): 25 septembre. Preuve du théorème de Cook, CSAT est NP-Complet.
  • (Cours 10): 1 octobre. 3-SAT est NP-Complet, Coloriage de graphe est NP-Complet (I).
  • (Cours 11): 2 octobre. Coloriage de graphe est NP-Complet. Résolution par énumération des certificats, résultion par backtrack.
  • (Cours 12): 9 octobre. Complexité d'un algorithme de backtrack, Clique, CS et EI sont équivalents.
  • (Cours 13): 12 octobre. Attribution des sujets de TP, résolution du Sudoku par les liens dansants (dancing links).
  • (TP 1): 15 octobre. Démonstration de NP-Complétude (I).
  • (TP 2): 23 octobre. Démonstration de NP-Complétude (II).
Récupérée de « http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO724_:_Algorithmique_avancée,_graphes_et_NP-Complétude&oldid=8385 »