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
-
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.
- Flots
et couplages. Reference bibliographique: Cormen Leiserson
Rivest, chapitre 27.
-
Programmation lineaire, algorithme du simplexe, dualite, methode
d l'ellipsoide. Reference bibliographique: debut du livre de Chvatal
(sur le simplexe et la dualite).
- NP-completude.
- Algorithmes d'approximation.
- Algorithmes probabilistes.
- Algorithmes pour la bio-info.
- Algorithmes et physique statistique
- 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,