Analyse d’algorithmes et programmation

Info pratiques

Cours+TDs les vendredis de 13h30 à 17h30, salle 2105.

Chargés des cours et des TDs : Christina Boura, Gaëtan Leurent.

Liste des cours

20 janvier
Introduction à l’analyse des algorithmes :
  • Tri par insertion
  • Analyse de complexité
  • Complexité asymtotique, notation et .

Références : CLRS §1, §2 et §3.

TD : (Re)-introduction à Python

27 janvier
Classes de complexité, P vs NP, principe diviser pour régner.
Tris : bubble sort, merge sort, quick sort.
TD : Algorithmes de tri
3 février
Tableaux, listes, piles, files, Tables de hachage.
TD : Structures de données en Python
10 février
Arbres binaires de recherche, arbres rouge-noir
TD : Classes python, les arbres avec Python, Code de Huffman
24 février
Programmation dynamique
TD : Programmation dynamique
10 mars
Graphes :
  • Notions de base, représentation, matrice d’adjacence ;
  • Parcours en largeur et en profondeur ;

Références : CLRS §22, §B.4.

TD : Graphes

17 mars
Graphes (suite) :
  • Tri topologique
  • Arbres couvrants minimaux, algorithme de Prim ;
  • Chemins les plus courts, algorithme de Dijkstra.

Références : CLRS §23, §24, et §B.5.

TD : Graphes, suite

24 mars
Algèbre linéaire :
  • Méthode de Strassen pour la mutliplication de matrices ;
  • Exposant ω de l’algèbre linéaire, et equivalence multiplication ↔ inversion ;
  • Méthode des moindres carrés.

Références : CLRS §4.2 et §28. Bostan et al. §8.

TD : Algèbre linéaire

31 mars
Problèmes NP-complets
  • Problèmes d’optimisation, problèmes décionnels,
  • Problèmes NP-complets, NP-durs, SAT,
  • Programmation linéaire entière,
  • Sac à dos,
  • Autres problèmes.

Références : CLRS §16.2, §34, §35.5.

TD : Sacs à dos

7 avril
2e contrôle continu

Modalité de contrôle

3 mars
1er contrôle continu (Sujet)
7 avril
2e contrôle continu

Note finale : (Examen + CC)/2

Sujets d’examen

1er contrôle 2016

2e contrôle 2016

Examen 1e session 2016

Examen 2e session 2016

Bibliographie

A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy. Algorithmes Efficaces en Calcul Formel.
Notes de cours du MPRI. http://perso.ens-lyon.fr/bruno.salvy/mpri/poly.pdf.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction à l’Algorithmique.
Trad. X. Cazin, G.-L. Kocher. Dunod 2010. ISBN: 978-2-10-054526-1. Côte BU: 005.1 COR.
G. Swinnen. Apprendre à programmer avec Python 3.
Eyrolles 2009-2010. ISBN: 978-2-212-12708-9. Côte BU: 005.13pyt SWI.
C. H. Papadimitriou. Computational complexity.
Addison-Wesley, 1994. 523 pages.