Plan du cours :
le but de ce cours est de présenter différents paradigmes algorithmique et de les illustrer sur différents problèmes. Les principaux algorithmes sur des graphes pondérés seront notamment abordés. Nous nous intéresserons à étudier la validité et la complexité des algorithmes rencontrés.
- Méthodes "diviser pour régner" (où l'on divise un problème en
sous-problèmes indépendants et on combine les solutions des
sous-problèmes). Parmi les applications classiques, mentionnons
le tri fusion ou encore la détermination de la plus proche paire
de points dans un plan.
- Algorithmes basés sur des parcours de graphes. On abordera notamment les
algorithmes de Dijkstra et
de Prim.
- Algorithmes gloutons (où l'on construit une solution de
manière incrémentale, en optimisant un critère de manière
locale). On abordera par exemple les algorithmes de Kruskal et
de Huffman.
- Algorithmes de programmation dynamique (où l'on divise un
problème en sous-problèmes emboîtés, et on résout les
sous-problèmes par tailles croissantes). On abordera, entre
autres, les algorithmes de Bellman et Bellman-Ford.