Planning des cours

Cours	Date	Sujet	Matériel supplémentaire
1	07/09/2010	Introduction : tri par insertion tri fusion preuve par invariants de boucle	Une démonstration animée (sous Acrobat Reader) pour comparer le tri par insertion et le tri fusion sur une entrée tirée aléatoirement.
	14/09/2010	Annulé et remplacé par un TD
2	21/09/2010	Fin des tris : tri par tas en place tri Shell (le tri rapide sera vue en ALGO2)	Une démonstration animée (sous Acrobat Reader) pour comparer le tri par insertion et le tri fusion sur une entrée tirée aléatoirement mais presque déjà triée. Le tri par insertion ne s'en sort pas si mal. Cela donne des idées pour le tri Shell. Une démonstration animée (sous Acrobat Reader) du tri Shell. En surbrillance la zone du tableau en cours de tri par insertion
3	28/09/2010	Recherche : techniques simples arbres de recherche arbres équilibrés (AVL)	Une applet Java pour jouer avec les AVL.
4	05/10/2010	Recherche (fin): arbres équilibrés (AVL) tables de hachage	Expériences sur les fonctions de hachage: on hache une fois tous les mots distincts du livre Les misérable (Tome 1) et on observe le nombre de collision.
5	12/10/2010	Graphes : Premières définitions Représentations Parcours	Une jolie image du graphe orienté du web. [Plus...] Un graphe non orienté représentant un labyrinthe. L'entrée est en bas à gauche. Il n'y pas de sortie mais on aimerait pouvoir parcourir tout le labyrinthe. Un parcours récursif en profondeur animé (sous Acrobat Reader) du labyrinthe. Les sommets déjà vus sont noirs ou bleus. Les sommets bleus représentent des sommets i dont l'appel récursif VISITE(i) n'est pas encore terminé. Pour les sommets noirs, la date de fin a été déjà choisie. Un parcours itératif en profondeur animé (sous Acrobat Reader) du labyrinthe. Les sommets déjà vus sont noirs ou bleus. Les sommets bleus représentent les sommets actuellement sur la pile. Un parcours en largeur animé (sous Acrobat Reader) du labyrinthe. Les sommets déjà vus sont noirs ou bleus. Les sommets bleus représentent les sommets actuellement sur la file d'attente.
6	19/10/2010	Graphes : Etude formelle du parcours en largeur par invariant de boucle Calcul des plus courts chemins Jeu de taquin	Recherche d'une solution d'un jeu de taquin par parcours de graphe. Recherche d'une solution d'un jeu de Mini-Rubik's Cube sur le site d'Interstices.
	26/10/2010	Vacances
7	02/11/2010	Graphes : Etude formelle du parcours en profondeur Tri topologique Calcul de composantes fortement connexes avec l'algorithme de Kosaraju Calcul de composantes fortement connexes avec l'algorithme de Tarjan	Présentation de l'algorithme de Tarjan
8	09/11/2010	Union-Find Début des algorithmes gloutons	Arborescence obtenu avec Quick-Union Arborescence obtenu avec Weighted-Quick-Union Arborescence obtenu avec Union-Find
9	16/11/2010	Algorithmes gloutons Problème du choix d'activités Arbre couvrant minimal (algorithme de Kruskal) Plus courts chemins à origine unique (algorithme de Dikjstra)	Algorithme de Kruskal Algorithme de Dikjstra
10	23/11/2010	Programmation dynamique Algorithme de Bellman-Ford Algorithme de Floyd-Wharshall
11	30/11/2010	Programmation linéaire - algorithme du simplexe
12	7/12/2010	Résoudre les problèmes difficiles Introduction informelle à P/NP Backtracking (N reines, coloriage de graphe, sudoku) Branch and bound (voyageur de commerce)	Programme OCaml pour les N reines Le graphe du sodoku à colorier avec 9 couleurs Programme OCaml pour le sudoku Comparaison des arbres de recherches pour le problème du voyageur de commerce