Majeure Informatique


Cours d'Analyse et conception d'algorithmes
2003-2004


  • Projets:
    En ce qui me concerne je souhaiterais particulierement encadrer un projet proche de mes interets de recherche actuels: par exemple, relaxation lagrangienne en optimisation combinatoire (voir ici), algorithmique de plus courts chemins dans des graphes planaires (Multiple-source shortest paths in planar graphs allowing negative lengths, Philip Klein, conference ACM STOC, sera presente en juin 2004), couplage biparti et reconnaissance de caracteres (ici --> premier article de la liste), etc.
    Typiquement: lire un article, implanter l'algorithme de l'article, ecrire un petit rapport resumant l'article et votre programme, et le presenter en soutenance de projet. Des "plus" apprecies: vous pouvez en plus vous interesser a des questions telles que: etendre l'algorithme a des questions connexes, ou chercher des exemples ou il fonctionne particulierement bien ou mal, ou faire une recherche bibliographique et le mettre dans le contexte des autres algorithmes existant pour ce meme probleme, etc.
  • Theme: Ce cours porte sur des techniques avancées dans la conception et l'analyse des algorithmes. En particulier, il couvre les mesures de complexité, l'analyse de coût amorti ; stratégies adverses ; NP-complétude : théorème de Cook, réductions polynomiales, exemples typiques (SAT, clique, couvertures, sac à dos, voyageur de commerce, chemins hamiltoniens, programmation entière, etc.), difficult\'e d'approximation; algorithmes d'approximation pour les probl\`emes d'optimisation; algorithmes randomisés. Extensions possibles : problèmes de flot, couplage ; arithmétique des nombres, des polynômes et des matrices (multiplication, FFT, formules de Strassen) ; recherche et tris avancés ; algorithmes de graphes, programmation linéaire, ordonnancement, bin-packing, exploration, etc.
  • Bibliographie: Thomas Cormen, Charles Leiserson and Ronald Rivest. Introduction to Algorithms McGraw-Hill, 1990.
  • Enseignants :
  • Page web 2002-03
  • Emploi du temps: l'amphi a habituellement lieu le mercredi de 13h45 a 15h15 dans l'amphi Gay-Lussac et les petites classes le mercredi de 15h30 a 17h30.
  • Evaluation: Examen, plus un bonus qui sera donne, dans certains cas, aux eleves qui ont fait preuve d'assiduite dans les PC et de serieux dans le travail sur les devoirs hebdomadaires.
  • Plan du cours
    1. Algorithmes sur les graphes et r\'eseaux: Arbre couvrant de poids maximal, plus courts chemins \`a partir d'une source, plus courts chemins entre tous les couples de sommets. Reference bibliographique: Cormen Leiserson Rivest, chapitres 24, 25, et 26.
    2. Flots et couplages. Reference bibliographique: Cormen Leiserson Rivest, chapitre 27.
    3. Programmation lineaire, algorithme du simplexe, dualite, methode d l'ellipsoide. Reference bibliographique: debut du livre de Chvatal (sur le simplexe et la dualite).
    4. NP-completude.
    5. Algorithmes d'approximation.
    6. Algorithmes probabilistes.
    7. Algorithmes pour la bio-info.
    8. Algorithmes et physique statistique
    9. Algorithmes et \'economie
  • Transparents : Cours 1, Cours 2, Cours 3, Cours 4, Cours 5, Cours 6, Cours 7, Cours 8, Cours 9.
  • Petites classes : PC 1, PC 2, PC 3, PC 4, PC 5, PC 6, PC 7, PC 8, PC 9.
  • Corriges petites classes : PC 1, PC 2, PC 3, PC 4, PC 5, PC 6, PC 7, PC 8, PC 9,
  • Devoirs : Devoir 1, Devoir 2, Devoir 3, Devoir 4, Devoir 5, Devoir 6, Devoir 7.
  • Corriges devoirs : corrige D1, corrige D2, corrige D3, corrige D4, corrige D5, corrige D6,