| Vendredi 13 septembre 2013 | Séance
introductoire avec des exercices Message : distinguer interface/implémentation, diviser pour régner, analyse amortie 1)Implémentation d'une file à l'aide de deux piles (avec analyse amortie) 2) Etant donné un tableau T, chercher le kème élément dans la permutation triée de T 3) Algorithme de Strassen. Si on a un algorithme en O(n^c) pour calculer le carré d'une matrice, a-t-on un algorithme en O(n^c) pour calculer le produit de deux matrices ? Feuille d'exercices Devoir maison Lire "divide and conquer" dans Algorithms, Papadimitriou et al. Lire "tri" dans le Cormen |
| Vendredi 20 septembre 2013 | Séance arbre rouge/noir I) Définition II) Insertion III) Suppression IV) Quelques mots sur la persistance Fiche des transformations |
| Mardi 24 septembre 2013 | Table de hachage 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 Devoir maison Union-find Tas de Fibonacci (dans le poly ou Cormen) |
| 6 décembre 2013 | Graphes Panorama des problèmes sur les graphes Fiche d'exercices 1) Algorithme de Kosaraju 2) Utilisation du graphe quotient des composantes fortement connexes pour optimiser le calcul de la fermeture réflexive et transitive d'un graphe 3) 2SAT via les composantes fortement connexes 4) Trouver le puits, s'il existe 5) Composantes bi-connexes 6) Adaptation de Djikstra à un problème original 7) Plus court chemin et programmation linéaire |
| vendredi 7 février 2014 | Nous abordons un problème d'ordonnancement d'intervalles : trouver le maximum d'intervalles dans un ensemble quelconques d'intervalles. Si on le considère comme un problème sur les graphes, on tombe sur le problème de calculer un ensemble indépendant maximal dans un graphe. C'est un problème NP-complet. Il y a mieux : utiliser la structure des intervalles pour trouver une stratégie gloutonne. Malheureusement, si on ajoute des poids aux intervalles, la stratégie gloutonne ne fonctionne plus. On a recourt alors à la programmation dynamique. Démonstration |