| Cours | Date | Sujet | Matériel supplémentaire |
| 1 |
06/09/2016 |
Introduction
- Union-Find
- preuve par invariants de boucle
|
Quelques expériences avec des variantes de l'algorithme Union-Find
|
| 2 |
13/09/2016 |
Analyse de l'efficacité des algorithmes |
Quelques visualisations de tris (à utiliser en plein écran avec Acrobat Reader pour déclencher l'animation)
|
| 3 |
20/09/2013 |
Recherche :
- techniques simples
- arbres de recherche
- arbres équilibrés (AVL)
|
|
| 4 |
27/09/2016 |
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érables (Tome 1) et on observe le nombre de collision. |
| 5 |
04/10/2016 |
Graphes :
- Premières définitions
- Représentations
- Parcours
|
- Quelques illustrations.
- 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 |
11/10/2016 |
Graphes :
- Etude formelle du parcours en profondeur
- Détection de cycles
- Tri topologique
- Calcul de composantes fortement connexes avec l'algorithme de Kosaraju
|
|
| 7 |
18/10/2016 |
Graphes :
- Fin de la preuve de l'algorithme de Kosaraju
- Algorithme de Tarjan pour le calcul de composantes fortement connexes
- Propriétés du parcours en largeur
|
|
| Bonus 1 |
23/10/2016 |
Cours de programmation Python avancé |
Notes de cours. |
| 8 |
08/11/2016 |
Réseaux de flot |
Notes de cours. |
| 9 |
15/11/2016 |
|
|
| 10 |
22/11/2016 |
|
|
| Bonus 2 |
29/11/2016 |
|
|