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


TP

  1. TP : Énoncé du TP (première partie)
  2. TP : Énoncé du TP (deuxième partie)
  3. TP : Script test_TP.sh qui test le bon fonctionnement de vos programmes
  4. TP : Programme gen3SAT.py (générateur d'instances de 3SAT)
  5. TP : Programme 3SATtoCA.py (réducteur de 3SAT vers CA)


Déroulement (2015-2016)

Cours 1 (6 novembre) : 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 (les premiers du moins...)
- Encodage d'une instance


Cours 2&3 (16 novembre ) : Complexité temporelle 

- Mesure de complexité temporelle
- Notations grand-O, Theta, Omega
- Exercices notation grand-O.
    - Feuille d'exercices
- Exercices logarithmes et exponentielle
    - Feuille d'exercices

Cours 4 (20 novembre) : Fonctions de complexité récursives

Cours 5&6 : Comparaison et implémentation de solution "naïves" VS "Diviser-pour-régner" 

    - faireCourbe.gnuplot 
    - timeUtil.h

Cours 7 : 

- Approche "Diviser-pour-régner" (suite et fin)
- Programmation dynamique
    - Exemples de problèmes pour la programmation dynamique

Cours 8 : 

- Programmation dynamique
  - Rendu de monnaie
    - Algo naïf en Python
    - Algo naïf en C++
    - Algo "Programmation dynamique" en Python
  - Distance de Levenshtein

Cours 9 : 

- Programmation dynamique (suite et fin)
  - Distance de Levenshtein (suite et fin)
    - Levenshtein.py
  - Impression équilibrée
    - impression_eq.py (TP0 à rendre *AVANT* le prochain cours)
    - impression_eq--sol.py (solution du TP0)

TP1

Cours 10 : 

- Algorithmes de type "Retour sur bande"
- Cycle Eulérien VS cycle Hamiltonien.
- Complexité d'un problème.
- Types de problèmes (Décision, Optimisation, Existence).
- Réduction polynomiale.
- Réduction Cycle Hamiltonien -> Commis-voyageur.


Cours 11 : 

- Classez de complexité (classes P et NP).
- Algorithme de vérification.
- Exemple VérifClique.
- Clique = Couvertures des arêtes = Ensemble indépendant.

Cours 12 : 

- Présentation sur le théorème de Cook.
- NP-complétude.
- Théorème de Cook (SAT est NP-complet)
- CSAT est NP-complet.
- 3SAT est NP-complet.

Cours 13 : 

- k-couleurs est NP-complet.
- Couverture des arêtes est NP-Complet.




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