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).


Matériel remis en classe

  1. Feuille d'exercices sur la notation Grand-O.
  2. Exemples d'algorithmes basés sur le principe "Diviser pour régner"
  3. Problème de la distance minimale parmi un ensemble de points via l'approche "Diviser pour régner"
  4. Problème de la découpe de barres via l'approche "Programmation dynamique"



Exemples vus en classe

  1. Programme sage qui trie des listes de nombres de manière spécialement inefficace
  2. Programme sage qui calcule les nombres de Ramsey ... mais il faut de la patience !
  3. Programme C++ qui résoud le problème de la distance minimale parmi un ensemble de points approche naïve vs approche diviser pour régner.
  4. Programme java qui résoud le problème de la découpe de barres approche récursive naïve.
  5. Programme java qui résoud le problème de la découpe de barres approche "Programmation dynamique".


TP

  1. TP0 : Affichage équilibré. Code à compléter : impression_eq.py


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" (exemples de la découpe de barres).


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=6611 »