| Vendredi 28 novembre 2014 | Programmation dynamique La programmation dynamique c'est quand glouton ne fonctionne pas. La programmation dynamique permet d'approximer des problèmes NP-complets. Feuille de TD Exécution des algorithmes pour l'ordonnancement d'intervalles |
| Vendredi 5 décembre 2014 | Algorithme sur les graphes
Les étudiants ont préparés des "fiches exemples" sur :
Feuille de TD
|
| Vendredi 12 décembre 2014 | Table de hachage
Démonstration
I) Vecteurs de bits et adressage direct (avec l'exercice où il n'y a pas besoin d'initialiser le tableau) II) Chaînage III) Hachage universel IV) Hachage parfait V) Adressage ouvert (juste ce que c'est) |
| Mardi 6 janvier 2015 | Arbres de recherche I) ABR et AVL Rotations pour les AVL II) B-arbres Affiche B-arbres Magnets pour les B-arbres III) Arbres 2-3-4 et arbres rouge et noir Fiche des transformations des arbres rouge-noirs IV) Application : intersection de segments horizontaux et verticaux V) Discussion sur la persistence, pred/succ, arbres d'intervalles |
| Vendredi 23 janvier 2015 | Tris Rappel des principaux algorithmes Tri fusion en place Réseaux de tris : tri insertion/bulle, coNP-complétude de la vérification, principe 0-1, tri fusion (avec tri bitonique) TD |
| Mardi 27 janvier 2015 | Tas Fibonacci Magnet tas Fibonacci Motivation pratique : pour algo de Djikstra Motivation pédagogique : exemple d'analyse amortie, exemple où l'arité est O(log n) (au lieu de la profondeur), etc. Ajout, extraire minimum, mise à jour |