Université Paris Diderot - Master 1 Ingénierie Informatique

Algorithmique (2010)

Equipe pédagogique

Chargé de cours : Eugene Asarin

Chargés de TD :  Roberto Mantaci,  Pierre Boutiller

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. 

Contrôle de connaissances

• Un devoir surveillé. Le partiel d'algorithmique M1 a  eu lieu mardi le 16 novembre 10 à la place du cours : sujet, corrigé.
• Un projet. Étudier et présenter un algorithme. Explications ici. Choix de sujet  ici (ou sujet libre à faire valider par E. Asarin avant le 10/12/10). Les soutenances auront lieu jeudi le 20 janvier 2011. Inscrivez-vous ici : http://doodle.com/7tedpe27ddz2bx34 http://doodle.com/svaayxxv3nxsffaf . Je viens d’ajouter jury 2.
• Un examen a eu lieu  le 11 janvier 2011. 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 cet examen.

Annales

Les sujets de 2008-2010 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)
• sujet, corrigé du partiel du 17 novembre 2009
• Sujet et corrigé de l’examen du 11 janvier 2010 
• Sujet de l’examen du 17 juin 2010 (rattrapage)

Pré-requis

Tri. Structures de données. Algorithmique des arbres et des graphes (recherche, plus courts chemins). Une certaine expérience en algorithmique et programmation.

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
• Algorithmes pour des problèmes classique NP-complets : 3-matching, clique
• Jeu de doublets
• Sac-à-dos : Programmation dynamique
• …

Compléments de l'algorithmique de graphes

• 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.