| mardi 8 septembre 2015 | IntroductionMagnets à imprimerTri insertion : spécifications d'un algorithme, terminaison, correction, invariant, complexité en temps, complexité en espace. Notations O(.), Ω(.), Θ(.) Tri fusion : algorithme récursif, paradigme diviser pour régner, récurrence Optimalité : modèle de calcul, type abstrait, arbres de décision |
| mardi 15 septembre 2015 |
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é Tri insertion et tri shell Démonstration tri shell Tri par tasTri par tas et file de prioritéTri sélection Tri par tas comme une variante du tri sélection Type abstrait : file de priorité. Implémentation avec un tas. Bonus : tri fusion en place (non montré en cours) Arbres binaires de recherche (ABR)Motivation : intersection de segments verticaux et horizontaux |
| mardi 22 septembre 2015 | Transparents ABR Définition des ABR. Recherche, ajout, suppression. Equilibrage (Adelson-Velsky-Landis) Fiche rotations Transparents sur les nombres d'équilibrages Animation sur le web pour les ABR et les ABR AVL |
| mardi 29 septembre |
Table de hachage Démonstration
Diviser pour régnerThéorème fondamental Multiplication de nombres FFT |
| mardi 6 octobre 2015 | Parcours en profondeurTransparents Pourquoi les graphes ? Implémentation avec matrice d'adjacence ou listes d'adjacence Exploration de labyrinthe : lemme des sommets non vus Parcours en profondeur : complexité linéaire, pre/post, classification des arcs Tri topologique : Magnets pour habiller le savant Cosinus Composantes fortement connexes : algorithme de Kosaraju(correction non démontrée)
|
| mardi 13 octobre 2015 |
Correction de l'algorithme de Kosaraju
Parcours en largeurAlgorithme de parcours en largeur : distance des plus courts chemins Correction du parcours en largeur Adaptation pour un graphe pondéré positivement : algorithme de Dijkstra Correction de l'algorithme de DijkstraQuelques mots sur les tas de Fibonacci (pas fait)
|
| mardi 20 octobre 2015 | Algorithmes gloutonsTransparents Arbre couvrant minimal Algorithme de Kruskal : exemple et correction Union find : version simple et compression de chemins Magnets qui illustrent la compression de chemins |
| 26 octobre au 2 novembre 2015 | VACANCES |
| mardi 3 novembre 2015 | Algorithmes gloutons (suite)Algorithme de Prim : Prim en 1957, Dijkstra en 1959, même squelette de l'algorithme ! Codage de Huffman Formules de Horn Converture d'ensembles |
| mardi 10 novembre 2015 | Programmation dynamiqueTransparents (ne suit pas exactement le cours)Explication du paradigme : définition des sous-problèmes, relation de récurrence (sous-structures optimales), conception de l'algorithme Exemple du problème de la plus longue sous-suite croissante Algorithme de Floyd-Warshall Algorithme de Bellmann-Ford Exercice : calcul de la seconde structure ARN optimale |
| mardi 17 novembre 2015 |
Correction de l'exercice : calcul de la seconde structure ARN optimale
FlotsPrésentation Problème du flot maximalAlgorithme de Ford-Fulkerson |
| mardi 24 novembre 2015 |
Correction de Ford-Fulkerson : flot maximal = coupe minimale
Réduction : exemple du couplage maximal.
Programmation linéairePrésentation Problème de programmation linéaire Encore des réductions : plus court chemins et flots (expliqué "avec les mains") Exemple du chocolatier Résolution de l'exemple avec l'algorithme du simplexe présenté intuitivement Formalisation de l'algorithme du simplexe Outil pour résoudre des programmes linéaires |
| mardi 1er décembre 2015 |
Problèmes de "recherche"Présentation Problème de décision. Non-déterminisme pour modéliser la "recherche d'une solution" Exemple : Algorithme non-déterministe pour SAC A DOS Définition de la classe NP Voyage optimiste dans NP : rappel de la programmation dynamique; réduction du placement de tours aux échecs vers COUPLAGE MAXIMAL Technique quand pas d'algorithme polynomial connu : Réduction à SAT (démonstration de la réduction PICROSS vers SAT), branch and bound pour SAC A DOS Local search pour dessiner des diagrammes d'Euler (démonstration) PS : dans ce cours, la NP-dureté (et donc la NP-complétude) n'est pas abordée mais laissée pour ALGO2. |
| mardi 15 décembre 2015, 10h15-12h15 | TERMINAL : sujet |