ENS, année scolaire 2012-2013
Algorithmique et Programmation
Annonces
Evaluation
Résumé du cours
Planning du cours
Partiels des années précédentes
Autres Notes de Cours
Annonces
Pas de TD le mercredi 31 octobre.C'est la page d'un cours de niveau L3 de l'ENS en informatique. Page web officielle ici. Emploi du temps ici. Plan des salles ici.
Enseignants :
- Claire Mathieu (claire AT cs.brown.edu)
- Jacques Stern (stern AT di.ens.fr)
- Sorina Ionica (sorina.ionica AT m4x.org)
- Damien Vergnaud (vergnaud AT di.ens.fr)
Cours Lundi 15:30-18:30, Salle U ou V (ancien immeuble rateau, passage rouge)
TDs Mercredi 16:30-18:30, Info 4 (NIR)
Evaluation
Examens:- 3 Déc. 2012 : Examen Algorithmique des Structures de données
- 21 Jan. 2013 : Examen Algorithmique numérique
- 21 Nov. 2012 : Choix des Projet de Programmation
- 15 Déc. 2012 : Envoi des Projets de Programmation
- 17-21 Déc. 2012 : Soutenances des Projet de Programmation
Résumé du cours
Le cours présente les bases sur les structures de données et les principes de conception des algorithmes ainsi qu'un certain nombre de développements plus avancés. On attend des étudiants un minimum de connaissances algorithmiques. Ces pré-requis correspondent approximativement aux chapitres 1, 2, 3, 4, 5 (sauf sections étoilées), et 10 du livre "Introduction to Algorithms" de Cormen, Leiserson, Rivest et Stein, et un étudiant qui n'aurait pas ces connaissances devrait se pré parer en lisant ces chapitres. Nous couvrirons avec rapidite des sujets que beaucoup d'etudiants connaissent : les tas (chapitre 6), le tri rapide (chapitre 7) , les arbres binaires de recherche (chapitre 12), les parcours de graphes (chapitre 22). Chaque séance est organisée en deux parties, la première consacrée aux connaissances de base et la seconde présente un résultat plus avancé (ou exceptionnellement plusieurs). Détails.
Agenda du cours
Matériel du cours
- Planches du cours : 1(tif), 1(jnt), 3(tif), 3(jnt), 4(tif), 4(jnt), 5(tif), 5(jnt), 6(tiff),
- Feuilles de TD : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
Autres Notes de Cours
- Jean Berstel
- Jeff Erickson (chaudement recommandé)
Projets de programmation
Vous aurez le choix entre plusieurs sujets de programmation à effectuer en binôme. Vous devez indiquer aux chargés de TD (ou bien à algoL3@di.ens.fr) quel sujet vous choisissez le 21 novembre au plus tard.
Vous devrez implémenter l'algorithme que vous avez choisi en C. Le but est de s'essayer au moins une fois dans votre vie &agave; ce langage, étant donné qu'il s'agit d'un des plus (sinon le plus) utilisé. Vous devrez également préparer une brève soutenance durant laquelle vous nous expliquerez le fonctionnement de l'algorithme, votre implémentation, ses performances, les problèmes que vous avez rencontrés, les idées d'améliorations que vous avez eues, etc.
Avis aux connaisseurs (et/ou aux petits malins) : l'usage du C++ est interdit. Plus précisément, l'usage d'objets (new, class...) et de la STL est interdit. Vous pouvez éventuellement utiliser les template si ça vous chante, mais il n'est pas certain que ce soit utile. Si vous voulez vraiment pouvoir déclarer des variables dans les expressions for(int i=0; ....), vous pouvez utiliser l'option -c99 de gcc.
Voici la liste des sujets. Plusieurs personnes peuvent prendre le même sujet bien sûr.
- Arbre couvrant minimal
- algorithme de Kruskal (avec la structure de donnée Union-Find) et application au voyageur de commerce
- algorithme de Prim (avec des tas de Fibonacci)
- Plus courts chemins à origine unique
- algorithme de Dijsktra (avec des tas de Fibonacci)
- algorithme de Gabow
- Plus courts chemins pour tout couple de sommets
- algorithme de Johnson (avec des tas binaires)
- Flot maximal
- Couplage maximal
- algorithme de Ford-Fulkerson pour les graphes bipartis (application à la mise en forme triangulaire par bloc de matrices creuses)
- algorithme d'Edmonds pour les graphes généraux
- clique maximum (Il y a des graphes challenges)
- algèbre linéaire
- Multiplication de matrices (denses) par l'algorithme de Strassen (avec parenthésage optimal)
- Résolution de systèmes linéaires creux par la décomposition LU (creuse)
- inclassables
- Plus proche ancêtre commun dans un arbre en temps constant
- Heuristique de Weisfeiler-Lehman pour l'isomophisme de graphes
Examen Algorithmique des Structures de données - Années Précédentes
- Partiel 2006
- Partiel 2007
- Partiel 2008
- Partiel 2009 (lost ?)
- Partiel 2010
- Partiel 2011