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
Le Jupyter notebook de la séance.
28 fevrier 2019
Contrôle continu (solution)
14 mars 2019
Programmation dynamique
  • Puissance d’une matrice, square and multiply,
  • Nombres de Catalan,
  • Programmation dynamique.

TD : Programmation dynamique

Le Jupyter notebook de la séance.
22 mars 2019 (9h40, salle G103)
Graphes
  • Définitions de base,
  • Parcours, tri topologique.

TD : Graphes

Le Jupyter notebook de la séance.
28 mars 2019
Graphes (suite)
  • Arbres couvrants, algorithmes de Prim et Kruskal
  • Plus courts chemins, Algorithme de Dijkstra

TD : Graphes

Le Jupyter notebook de la séance.
4 avril 2019
String matching
  • Rabin-Karp
  • Automates finis

TD : String matching

Le Jupyter notebook de la séance.
11 avril 2019
Programmation linéaire
  • Algorithme du simplexe

TD : Programmation linéaire

Le Jupyter notebook de la séance.
18 avril 2019
Problèmes NP-complets
  • Classes de complexité P, NP
  • Arguments réductionnistes
  • Problèmes NP-complets

TD : Sac à dos

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/

B. Cordeau, L. Pointal. Python 3 – Apprendre à programmer en Python avec PyZo et Jupyter Notebook. Dunod 2017. ISBN : 978-2-10-076636-9. Côte BU : 005.13pyt. Site web.

B. Cordeau, L. Pointal. Une introduction à Python 3. Polycopié, licence libre CC3.0. 2015. https://perso.limsi.fr/pointal/python:courspython3.

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.