INFO704 : Analyse d'algorithmes

De Wiki du LAMA (UMR5127)
Responsable 2017: Sébastien Tavenas


Sommaire

Quelques ressources bibliographiques

Ouvrage de référence :

  1. Cormen, Leiserson, Rivest et Stein, Algorithmique, 3e edition (2009). ( Aussi appelé "Introduction à 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. Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979).

TP

TP les 10 octobre et 6 novembre.

- Énoncé du TP, première partie : tp-part-1.pdf. Plus de détails pour chacuns des trois sujets :
  * tp-part-1-CHO.pdf
  * tp-part-1-CHNO.pdf
  * tp-part-1-3C.pdf

Voici aussi un exemple d'entrée pour chaque sujet :

  * Graphe-vrai-CHO.pdf
  * Graphe-vrai-CHNO.pdf
  * Graphe-vrai-3C.pdf


- Énoncé du TP, deuxième partie : tp-part-2.pdf.

Documents pour les réductions :

  * Avro Chapitre 10
  * Cormen-Leiserson-Rivest-Stein Coloration
  * Cormen-Leiserson-Rivest-Stein HNO (Attention la figure 34.16 est incorrecte. La remplacer par la figure 34.16 de la Version anglaise)
  * Hon HO Version francaise
  * Garey-Johnson HNO
  * wiki proof

Voici des exemples d'entrée pour 3SAT et Couverture par Sommets :

  * 3SAT-vrai
  * CS-vrai
  * 3SAT-faux
  * CS-faux

Déroulement (2017-2018)

Cours 1 et 2 (12 septembre) : Introduction

- Exemple "Tri lent" 
- Notions d'instance et de problème
- Encodage d'une instance
- Feuille de rappels : logarithme Logarithme.pdf, ordres de grandeur Grand-O.pdf et correction partielle Correction.pdf.

Cours 3 (19 septembre) : Analyse des algorithmes (suite et fin).

- Analyse des algorithmes

Cours 4 et 5 (26 septembre) : Complexité des algorithmes Diviser-pour-régner

- Présentation des algorithmes Diviser-pour-régner.
- Théorème général. Théorème général
- Comparaison d'approches naïves VS diviser-pour régner (théorie et implémentation).
- Problème de la multiplication de grands entiers.

Cours 6 et 7 (3 et 9 octobre) : Complexité des algorithmes Diviser-pour-régner (suite et fin) + Programmation dynamique.

- Problème de la distance minimum dans un nuage de points. Distance
- Problème du rendu de monnaie. Rendu monnaie

Cours 8 et 9 (17 octobre) : Complexité des problèmes

- Complexité d'un problème.
- Classe P.
- Réduction polynomiale.
- Algorithme de vérification.
- Classe NP.

Cours 10 et 11 (24 octobre) : NP-complétude

- Problèmes NP-difficiles et NP-complets.
- Théorème de Cook-Levin. Cook-Levin
- Preuve de NP-Complétude. 

Cours 12 ( 6 novembre) : Algorithmes probabilistes

Historique

Ce cours était donné précédemment par Xavier Provençal. Ce cours est une refonte de INFO724 Algorithmique avancée, graphes et NP-complétude.

Outils personnels