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 \(\mathcal{\Theta}\) et \(\mathcal{O}\)
- 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.
- 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
- 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 :
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
- 2019
- CC1 et CC2
- Examen et Rattrapage
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.