INFO704 : Analyse d'algorithmes

Responsable 2017: Sébastien Tavenas

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.

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 et exercices : logarithme et ordres de grandeur. 

Cours 3 (19 septembre) : Complexité des algorithmes gloutons et Diviser-pour-régner

- Algorithmes gloutons
- Présentation des algorithmes Diviser-pour-régner.

Cours 4 et 5 (26 septembre) : Complexité des algorithmes Diviser-pour-régner (suite et fin) + Programmation dynamique.

- Comparaison d'approches naïves VS diviser-pour régner (théorie et implémentation).
- Problème de la distance minimum dans un nuage de points.
- Problème de la multiplication de grands entiers.

Cours 6 et 7 (3 et 9 octobre) : Probabilités.

- Complexité en cas moyen.
- Complexité d'un algorithme probabiliste.

<-- - Solutions aux exercices du cours précédent : dmin.cpp multGrandsEntiers.cpp sommeMax.cpp

- Distance de Levenshtein Levenshtein.py Petite banque de mots.
- Devoir "Impression équilibrée"
  - Code à compléter (Python 2).
  - Code à compléter (Python 3).

-->

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.
- Preuve de NP-Complétude. 

Cours 12 ( 6 novembre) : Analyse amortie?

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.