Analyse d’algorithmes et programmation

Info pratiques

Cours & TD le jeudi de 8h00 à 11h10, salle RC22 (Bât Descartes - RDC)

Chargé de cours et TD : Luca De Feo

Serveur pour les TPs: https://jupyter.ens.uvsq.fr/

En cas de panne: https://sage.prism.uvsq.fr/ (attention : données non sauvegardées).

Calendrier

24 janvier 2019
Introduction à l’analyse des algorithmes
  • Tri par insertion
  • Analyse de complexité
TD : (Ré)-introduction à Python
Le Jupyter notebook de la séance.
31 janvier 2019
Algorithmes de tri
  • Complexité asymptotique, notation et
  • Principe “diviser pour régner”
  • Exemples : tri fusion, tri rapide
TD : Algorithmes de tri
Le Jupyter notebook de la séance.
15 février 2019 (9h40, salle G103)
Structures de données
  • Piles et files
  • Listes chaînées
  • Arbres
  • Tables de hachage
TD : Structures de données
Le Jupyter notebook de la séance.
21 février 2019
Arbres
  • Arbres binaires de recherche
TD : Arbres
28 fevrier 2019
Contrôle continu
14 mars 2019
Arbres (suite) ?
22 mars 2019 (9h40, salle G103)
Programmation dynamique
28 mars 2019
Graphes
4 avril 2019
Graphes (suite)
11 avril 2019
Algèbre linéaire ?
18 avril 2019
Programmation linéaire ?
25 avril 2019
Problèmes NP-complets ?

Modalités d’évaluation :

Deux contrôles continus

Note finale : 60% Examen + 40% CC, où CC = (CC1 + CC2)/2

Annales

2016
CC1 et CC2
Examen et Rattrapage
2017
CC1 et CC2
Examen
2018

CC1 et CC2

Examen

Bibliographie

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.

A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy, É. Schost. Algorithmes Efficaces en Calcul Formel. 686 pages. Imprimé par CreateSpace. Aussi disponible en version électronique. Palaiseau: Frédéric Chyzak (auto-édit.), sept. 2017. ISBN : 979-10-699-0947-2. https://hal.archives-ouvertes.fr/AECF/

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.