ALGO1 : Introduction à l'algorithmique

Magistère de Mathématiques de Rennes - ENS Rennes - Année 2018/2019

Intervenants

Cours : François Schwarzentruber
Travaux dirigés : Alexandre Debant

mardi 4 septembre 2018	Introduction Algorithme de Gale et Shapley. Terminaison. Variant. Correction. Invariant. Algorithme sous-spécifié (plusieurs exécutions). Démonstration que ce qui proposent sont favorisés. Exposé de Judicaël Courant sur les mariages stages et les affectations des lycées dans le supérieur.
mardi 11 septembre 2018	File de priorité Type abstrait (interface) VS structure de données (implémentation). File. Liste doublement chaînée. File de priorité. Implémentation naïve. Implémentation avec un tas. Construction d'un tas en temps linéaire. Problème du tri. Tri par tas : variante du tri sélection mais utilisant un tas. Type abstrait : file de priorité. Optimalité du tri par tas. Mise en place du projet wikipedia.
mardi 18 septembre 2018	Structures de données pour un ensemble Discussion autour des tableaux, vecteurs de bits. Table de hachage. Exemples de fonctions de hachage. Démonstration Arbres binaires de recherche : définitions, recherche d'un élément, ajout et suppression. Notion de structure persistante. Equilibrage : B-arbres.
mardi 25 septembre 2018	PAS DE COURS
mardi 2 octobre 2018	Diviser pour régner Théorème fondamental Multiplication de nombres : algorithme de Karatsuba Multiplication de matrices : algorithme de Strassen Transformation de Fourier rapide Multiplication de polynômes. Passage de la représentation par coefficients et par valeurs via FFT et FFT inverse.
mardi 9 octobre 2018	Parcours en profondeur Implémentation des graphes : matrice d'adjacence ou listes d'adjacence. Parcours en profondeur : algorithme, lemme des sommets non vus, complexité linéaire, pre/post, classification des arcs Tri topologique : magnets pour habiller le savant Cosinus Composantes fortement connexes : algorithme de Kosaraju (correction débutée)
mardi 16 octobre 2018	Correction de l'algorithme de Kosaraju Parcours en largeur Algorithme de parcours en largeur : distance des plus courts chemins Correction admise Adaptation pour un graphe pondéré positivement : algorithme de Dijkstra Correction de l'algorithme de Dijkstra Algorithme A* Implémentation de Dijkstra en C++ Demo sur le site d'un tutorial à IJCAI-ECAI 2018
mardi 23 octobre 2018	PAS DE COURS
jeudi 25 octobre 2018	Algorithmes gloutons Arbre couvrant minimal Algorithme de Kruskal : exemple et correction Union find : version simple et compression de chemins Magnets qui illustrent la compression de chemins
28 octobre au 3 novembre 2018	VACANCES
mercredi 7 novembre 2018 à 16h	Programmation dynamique Exemple du problème de la plus longue sous-suite croissante pour expliquer : qu'il faut se concentrer sur la quantité à optimiser définir des sous-problèmes trouver une relation par récurrence écrire un algorithme itératif décorer l'algorithme pour construire une solution au problème Algorithme de Bellmann-Ford Algorithme de Floyd-Warshall Sac à dos avec et sans répétition Mémoïzation expliquée avec le sac avec répétition Explication de l'art de trouver des sous-problèmes avec sac à dos sans répétition
mardi 13 novembre 2018	Flots Problème du flot maximal Algorithme de Ford-Fulkerson Correction de Ford-Fulkerson : flot maximal = coupe minimale Réduction : exemple du couplage maximal.
mardi 20 novembre 2018	Programmation linéaire Introduction avec l'exemple du chocolatier. Résolution avec l'outil lp_solve sous linux Discussion sur programmation linéaire réelle, entière, mixte Réduction à la programmation linéaire : plus court chemin, flots, flot de coût minimum, sac à dos Conversion de programme linéaire : problèmes standards et canoniques Algorithme du simplexe : exécution sur l'exemple du chocolatier Discussions : espace des solutions non borné. Prétraitement pour se ramener à un problème canonique avec solution basique s'il y a une solution, ou détecter que l'espace des solutions est vide. Correction et terminaison de l'algo du simplexe admise.
mardi 4 décembre 2018	Algorithme de recherche de solutions Exemple : sac à dos, voyageur de commerce, SAT. Backtracking. Idée générale du backjumping. Réduction à SAT : exemple du jeu Picross (démonstration) Branch and bound illustré sur sac à dos Local search pour voyageur de commerce, pour dessiner des diagrammes d'Euler (démonstration)
lundi 17/12/2018 – 8h	TERMINAL : sujet

Références

• Introduction à l’algorithmique, T. H. Cormen, C. E. Leiserson, R. L. Rivest, Dunod. (une référence, couvre beaucoup de choses, un peu lourd et quelques erreurs)
• Algorithms de S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. (couvre l'essentiel, une approche intéressante et concise)
• Algorithms, R. Sedgewick, Addison-Wesley.
• Éléments d’algorithmique, D. Beauquier, J. Berstel, Ph. Chrétienne, Masson. (merci aux auteurs de donner le livre sur Internet)
• Types de données et algorithmes, C. Froidevaux, M.-C. Gaudel, M. Soria, McGraw-Hill-InterEditions. (intéressant pour les structures de données)
• Algorithmics, The Spirit of Computing. David Harel. (une façon originale de présenter le paysage des algorithmes : "les limites", "relâcher les règles (parallélisme, proba)", "algorithme dans la création de logiciels")
• Algorithm design, Jon KIeinberg et Eva Tardos. (ouvrage riche en bons exemples) http://www.aw-bc.com/info/kleinberg/index.html
  

Autre cours sur internet

• http://www.algorist.com/
• Programmation efficace à l'école polytechnique pour le concours ICPC
• http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/