L3 - ALGO

Equipe enseignante

Cours: François Laroussinie (mercredi 10h30-12h30, amphi 12E)
TD Groupe 1: Alberto Carraro (jeudi 14h30--16h30; 478F)
TD Groupe 2: Sylvain Jacob (mardi 14h30--16h30; 473F)
TD Groupe 3: Thu-Hien To (mardi 8h30--10h30; 470E)
TD Groupe 4 (math-info): Pierre Aboulker (mardi 16h30--18h30; 376F)
TD Groupe 5 (EIDD): Sylvain Perifel (vendredi 10h45--12h45; 056A Bât. Condorcet)

Actualités

Résultats de la sesion 2 : Les notes de la session 2 sont disponibles ICI.

Programme

Une version du polycopié est disponible ici.

Introduction, complexité
Transparents du premier cours
Arbres binaires de recherche (algorithmes de base + analyse de complexité dans le pire cas et en moyenne)
Un programme Java pour les ABR
Arbres binaires de recherche équilibrés
Un programme Java pour les AVL (ajout et recherche)
Introduction aux graphes; parcours en largeur; parcours en profondeur; recherche d'extension linéaire.
Transparents des cours 5 et 6.
Composantes fortement connexes (algorithme de Tarjan)
Transparents des cours 7 et 8.
Rappel sur les tas et les files de priorité
Arbres couvrants minimaux
Transparents
Plus courts chemins
Transparents
Hachage
Notions générales: familles d'algorithmes, aperçu sur la complexité des problèmes et la décidabilité.

Programmes Python pour les algorithmes dans les graphes

Vous trouverez ici quelques programmes écrits en Python reprenant les algorithmes vus en cours.
Attention ! L'objectif est de fournir une implémentation simple des algorithmes en utilisant les facilités de Python afin de permettre aux étudiants de "jouer" avec les algorithmes, de les faire tourner, de les modifier, etc. En particulier, les complexités des algorithmes ne sont pas toujours respectées.
Dans la plupart des cas, un graphe est représenté par un paire G=(S,A) où S est un ensemble de sommets (chaque sommet étant une chaîne de caractère, un nombre, ...) et A est un dictionnaire Python associant à chaque sommet sa liste de sommets adjacents.
Rappel: en Python, G[0] désignera donc l'ensemble S et G[1] correspondra à A. Et donc G[1][x] désigne la liste d'adjacence du sommet x... etc.

Le fichier boiteaoutils.py contient quelques fonctions utiles.
Le fichier graphe_PL.py contient le parcours en largeur. Et exemples1.py décrit un exemple d'utilisation (NB: depuis l'interface Python, il suffit de faire "import exemples1").
Le fichier graphe_PP.py contient le parcours en profondeur et l'algorithme de recherche d'extension linéaire. Et exemples2.py contient un exemple d'utilisation.
Le fichier graphe_CFC.py contient l'algorithme de Tarjan. Et exemples_cfc.py contient un exemple d'utilisation.
Le fichier graphe_ACM.py contient l'algorithme de Prim pour les arbres couvrants minimaux qu'il faut utiliser avec les files de priorités étendues.
Le fichier graphe_PCC.py contient l'algorithme de Dijkstra pour les plus courts chemins (avec poids non négatifs) qu'il faut utiliser avec les files de priorités étendues.

Examen et contrôle des connaissances

La note d'algorithmique sera calculée à partir du contrôle continu (coef 0,35) composé d'un TD noté et d'un devoir maison, et de l'examen (coef 0,65).
Les sujets de l'année 2009-2010:

Devoir "maison" 2010--2011

Le sujet du devoir maison est disponible ICI. Il est à rendre la semaine du 1er novembre.

Sujets des TD

Références bibliographiques

"Eléments d'algorithmique", D. Beauquier, J. Berstel, Ph. Chrétienne, Edition Masson. Ce livre est épuisé... mais disponible sur Internet ICI
"Introduction à l'analyse des algorithmes", R. Sedgewick, Ph. Flajolet, International Thomson Publishing.
"Introduction à l'Algorithmique", T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Dunod.

Email: francois.laroussinie[at]liafa.jussieu.fr

Cours d'algorithmique -- L3 (2010--2011)