INFO704 : Analyse d'algorithmes

Responsable 2018: Sébastien Tavenas

Adresse couriel : sebastien.tavenas@univ-smb.fr

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

TP1 le 17 octobre

Seuls les deux premiers problèmes suffisent pour avoir la note maximale!!!
- Énoncé du TP
- Fichiers relatifs au TP1

TP2 le 19 octobre

- Fichiers relatifs au TP2

TP3 le 9 novembre

- Énoncé du TP, deuxième partie.
- 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)
  * Avro Chapitre 10
  * Avro Chapitre 10
  * Avro Chapitre 10

  * 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 (2018-2019)

Cours 1 (10 septembre) : Introduction

- Exemple de différents tris 
- Notions d'instance et de problème
- Notion de complexité asymptotique

TD 1 (14 septembre) : Rappels de mathématiques

- Grand-O de la notation de Landau
- Fonctions mathématiques de base : polynômes, exponentielles et logarithmes
- Correction des questions 2 et 3 du TD

TD2 (18 septembre) : Analyse des algorithmes

- Complexité d'éléments basiques : instructions, tests, boucles Pour et TantQue
- Cas des algorithmes récursifs.
- Analyse des algorithmes

Cours 2 (21 septembre) : Algorithmes récursifs (Diviser pour régner)

- Présentation des algorithmes Diviser-pour-régner.
- Théorème général.

TD 3 (24 septembre) : Algorithmes récursifs (Diviser-pour-régner)

- Correction des derniers exos de la feuille de TD.
- Problème de la multiplication de grands entiers.

Cours 3 (1 octobre) : Fin correction "Diviser pour régner" + Début programmation dynamique.

TD 4 (5 octobre) : Programmation dynamique

Cours 4 (8 octobre) : Complexité des problèmes

Cours 5 (9 octobre) : NP-complétude

TD 5 (19 octobre) : NP-complétude

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.