| 11 septembre 2012 | Premières
notions Transparents introduction à l'algorithmique Magnets à imprimer Transparents cours 1) Spécifications et terminaison (tri insertion) 2) Complexité en temps 3) Algorithme récursif (tri fusion) 4) Algorithme optimal 5) Conclusion |
| 18 septembre 2012 | 1.
Diviser
pour régner Démonstration comparaison tri insertion et tri fusion sur un tableau quelconque Démonstration comparaison tri insertion et tri fusion sur un tableau presque trié Transparents qui accompagnent le cours 1) Théorème fondamental 2) Application en calcul : multiplication de nombres 3) Application en traitement du signal : FFT 4) Application en géométrie : 2 points les plus proches |
| 25 septembre 2012 | 2. Types
abstraits et structures
de données Transparents 1) Types abstraits a) Piles (ex :
fonction annuler/refaire, pile d'appel, etc.)
2) Implémentationsb) Files (ex : gestionnaire d'impression) c) Ensembles a) Tableaux,
tableaux triés, tableaux de booléens
3) Tables de hachagesb) Listes 4) Etendre une structure de données (coupler deux structures de données, ajout de champs supplémentaires) 3. La puissance des arbres A) Prélude : une démonstration de la puissance 1) Du tri rapide aux
arbres binaires
2) Définition des arbres binaires |
| 2 octobre 2012 | B) Au service du type abstrait "Ensemble" Transparents arbres binaires de recherche 1) Définition
2) Opération de recherche 3) Ajout d'un élément 4) Suppression d'un élément 1) Définition et
propriété
2) Ajout d'un élément et rééquilibrage avec rotations Transparents sur les
nombres d'équilibrages Un seul rééquilibrage 3) Suppression Plusieurs rééquilibrages |
| 9 octobre 2012 |
C) Au service du type abstrait "File de priorité" Transparents tri par tas I) Besoins : le type abstrait la file de priorité II) Implémentations a) Implémentations naïves
b) Tas c) Implémentation en place du tas d) Implémentation des opérations III) Tri par tas Exercice de cours D) Au service du type abstrait "Relation d'équivalence" (union-find) Transparents union-find I) Besoins : générer un labyrinthe
II) Implémentation naïve III) Implémentation en forêt d'arbres |
| 16 octobre 2012 | 4. Parcours de graphes I) Graphe 1) Définitions
Transparents
sur les applications des graphes2) Structure de données Labyrinthe en parcours en largeur Labyrinthe en parcours en profondeur II) Parcours en profondeur Transparents pour le parcours en profondeur 1) Algorithme
générique
a) Définition
2) Application : cycleb) Classification des arcs c) Lemme utile : le lemme des chemins non vus 3) Application : tri topologique |
| 23 octobre 2012 |
4) Application : composantes fortement connexes
a) Définitions III) Parcours en largeurb) Algorithme de Kosaraju Transparents pour le parcours en largeur |
| 29 octobre au 4 novembre 2012 | VACANCES |
| 6 novembre 2012 | 5. Algorithmes
gloutons Transparents 1) Principe général 2) Arbre couvrant de poids minimal a) Algorithme de
Kruskal
3) Formules de HornDémonstration de la correction par "couper-coller" c) Algorithme de Prim Prim en 1957, Dijkstra en 1959, même squelette de l'algorithme ! |
| 9 novembre 2012 | 6. Programmation
dynamique
Transparents 1) Sous-structures optimales a) On les trouve fréquemment dans l'algorithmique du texte. Exemple de la sous-structure ARN 2) Ecrire un algorithme
b) Analyse du problème c) Exhiber une relation de récurrence a) De la récursivité ? Non, merci ! 3) Plus court cheminsb) Mémoïsation c) Algorithme ascendant a) Algorithme de Bellmann-Ford
|
| 13 novembre 2012 |
b) Algorithme de Floyd-Warshall 7. Programmation
linéaire et réductionsI) Flots
1) Problème du flot maximal
2) Un échec 3) Algorithme de Ford-Fulkerson 4) Théorème du flot maximal |
| 27 novembre 2012 |
II) Réductions 1) Le problème de la
programmation linéaire
III) Introduction à l'algorithme du simplexe2) Réductions a) Définitions
b) Exemples : plus court chemins et flots (on se restreint à la forme canonique) 1) Principe général
- exemple du chocolatier
8. NP-complétude2) Résolution de l'exemple a) Explication de
l'algorithme sur la forme standard b) Déroulement de l'algorithme Transparents Quelques problèmes de "recherche". 3-COLORIAGE comme problème phare. |
| 4 décembre 2012 |
I) Non-déterminisme. Définition de NP. II) Les problèmes les plus durs de NP. III) Le pouvoir de la logique propositionnelle. 1) Problème SAT
III) Des réductions pour montrer la NP-dureté2) Machines de Turing Exemple d'une machine de Turing - Fiche à compléter 3) Théorème de Cook (SAT est NP-complet) 1) 3SAT 2) 3-COLORIAGE |