Université Paris Diderot - Master 1 Ingénierie Informatique

Algorithmique (2009)

Equipe pédagogique

Chargé de cours : Eugene Asarin

Chargés de TD :  Roberto Mantaci,  Fabien de Montgolfier, Daniele Varacca

Objectifs

Connaitre et savoir appliquer les grands principes de la conception et de l'analyse des algorithmes. Connaitre, savoir appliquer, et savoir adapter des algorithmes classiques. 

Page web de TDs

Elle est ici.

Contrôle de connaissances

• Un devoir surveillé. Le partiel d'algorithmique M1 a  eu lieu mardi le 17 novembre 09 à la place du cours : sujet, corrigé.
• Un projet. Étudier et présenter un algorithme. Explications ici. Choix de sujet  ici. Les soutenances auront lieu jeudi le 21 janvier 2010 (salles 471E et 473F). Inscriptions pour les soutenances ici.
• Un examen a eu lieu  en janvier 2010. Document autorisé : 1 feuille A3 (ou 2 feuilles A4) recto-verso avec toute information que l’étudiant trouve utile. Programme: tous les grands principes y compris la Programmation Dynamique. Les algos vus en cours et en TD (voir la liste en bas de la page). Flux dans les graphes. 
• Sujet et corrigé de l’examen du 11 janvier 2010 
• Un examen de rattrapage aura lieu le 17 juin 2010 à 15h30-18h30 en amphi 5C. Document autorisé : 1 feuille A3 (ou 2 feuilles A4) recto-verso avec toute information que l’étudiant trouve utile.

Annales

Les sujets de 2008 vous seront très utiles.  Le programme a beaucoup changé par rapport à l'année 2007, mais pour votre information on met sur cette page quelques sujets de 2007

• Sujet  et  Corrigé  du partiel du 30 novembre 2007
• Projet de l'année 2007.
• Sujet et corrigé du partiel du 28 novembre 2008
• Sujet  et  corrigé de l'examen du 18 janvier 2008
• Sujet , corrigé, page 2 de corrigé de l'examen du 9 janvier 2009
• Sujet de l'examen du 18 juin 2009 (rattrapage)

Pré-requis

Tri. Structures de données. Algorithmique des arbres et des graphes (recherche, plus courts chemins)

Programme

Méthodes

• Diviser pour régner (faites attention à l'analyse de complexité)
• Algorithmes gloutons (faites attention à la preuve de correction)
• Algorithmes exponentiels et retour-arrière (on peut les voir comme recherche dans les graphes)
• Programmation dynamique (2 formes : récursive avec marquage et itérative)

 Exemples d'algorithmes

• Multiplication des grands entiers: Karatsuba-Ofman
• Multiplication des matrices : Strassen
• Exponentiation
• Tri par fusion et quicksort (révision)
• Sélection et médiane: Quickselect et l'algo en O(n)
• Les 2 points les plus proches
• Sac-à-dos fractionnaire
• Ordonnancement des tâches (s,f)  sur un processeur maximisant le nombre de taches accomplies.
• Chemin Eulerien
• Les 8 reines
• ....

Compléments de l'algorithmique de graphes

• Composantes fortement connexes: Tarjan
• Flux maximum dans un graphe: Ford-Fulkerson

Bibliographie

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001.
2. G. Brassard and P. Bratley, Algorithmique : conception et analyse. Paris Montréal: Masson ; Presses de l'Université de Montréal, 1987.
3. D. Beauquier, J. Berstel, Ph. Chretienne : Eléments d'algorithmique, Masson.