INFO704 : Analyse d'algorithmes

Responsable 2020: 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

Dates provisoires :

- 22/25 septembre
- 9 octobre
- 16 octobre

TP1 les 22/25 septembre : Analyser la complexité d'algorithmes

- Sujet du TP 1
- Fichiers pour le TP
- Nécessité d'importer la librairie Matplotlib

TP2 le 9 octobre : Problème NP-complet

- Sujet du TP 2
- Exemples d'entrée
- Générateur aléatoire d'entrées

TP3 le 16 octobre : Réductions

- Sujet du TP 2
- Esquisse de résolveur pour Clique
- Nécessité d'importer la librairie pycosat

Déroulement (2020)

Cours 1 (7 septembre) : Introduction

- Introduction
- Exemple de différents tris 
- Notions d'instance et de problème
- Notion de complexité asymptotique
- Grand-O de la notation de Landau

TD 1 (10 septembre) : Analyses d'algorithmes

- Sujet du TD
- Fonctions mathématiques de base : polynômes, exponentielles et logarithmes

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

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

TD 2 (29 septembre) : Exercices d'analyse pour des algos récursifs ("Master Theorem")

- Exercices, complexité des fonctions récursives.
- Solutions des questions 6 et 7.
- Solution de la question 5.

Cours 3 (2 octobre) : Programmation dynamique

- Algorithme récursif pour les nombres de Fibonacci
- Programme python pour le problème de découpe de barres
- Algorithme de Levenshtein
- Présentation 'tablette' vue en cours

TD 3 (5 octobre) : Exercices sur la programmation dynamique

- Sujet du TD
- Si besoin, problème du sous-tableau de somme maximale.
- Notes lors de la correction
 

Cours 4 (13 octobre) : Premières réductions algorithmiques

- Un liste de réductions algorithmiques entre différents problèmes
- Note sur les mathématiques derrière la réduction de 3SUM vers 3COLLINEAR

TD 4 (14 octobre) : Clique et consorts

- Réductions autour de Clique et NP-complétude de Clique
- Notes sur le problème SAT

Cours 5 (23 octobre, matin) : Classes de complexité et NP-complétude

- Petite introduction en survol de la NP-complétude
- Notes de cours sur les classes de complexité
- Petit Vrai/Faux sur la NP-complétude
- Hors programme : slides sur les classes de complexité que j'avais utilisé lors d'une année antérieure quand je faisais la preuve du théorème de Levin-Cook

TD 5 (23 octobre, après-midi) : Classes de complexité et NP-complétude

- Énoncé du TD
- Problème du sac à dos
- Corrigé de l'exercice 3 du TD

Annales Examen

Examen 2017

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.