Info pratiques
Cours & TD le mercredi de 13h à 15h50, sur Zoom (lien dans l’espace Moodle)
Chargés de cours et TD : Christina Boura et Yann Rotella
Serveur pour les TPs: https://jupyter.ens.uvsq.fr/
Calendrier
3 février
Introduction à l’analyse des algorithmes
- Tri par insertion
- Analyse de complexité
TD : (Ré)-introduction à Python
10 février
Algorithmes de tri
- Complexité asymptotique, notation \(\mathcal{\Theta}\) et \(\mathcal{O}\)
- Principe diviser pour régner
- Exemple : tri fusion
Structures de données
- Listes chaînées
- Arbres
- Tables de hachage
17 février (16h - 18h50)
TD : Algorithmes de tri
3 mars
Arbres
- Arbres binaires de recherche
TD : Arbres
10 mars
Programmation dynamique
- Exponentiation rapide
- Puissance d’une matrice, square and multiply
17 mars
1er contrôle continu
24 mars
Systèmes linéaires
- Résolution de systèmes linéaires de type AX = B,
- Pivot de Gauss
TD : Algèbre linéaire
31 mars
Programmation linéaire - Algorithme du simplexe
7 avril
Graphes
- Notions de base, représentation, matrice d’adjacence
- Parcours en largeur et en profondeur
- Tri topologique
TD : Graphes
14 avril
Graphes (suite)
- Arbres couvrants minimaux, algorithme de Prim
- Chemins les plus courts, algorithme de Dijkstra
TD : Graphes (bis)
21 avril
2nd contrôle continu
5 mai
Problèmes NP complets, machines de Turing
Modalités d’évaluation :
17 mars - 13h : 1er contrôle continu (sur feuille + machine) :
21 avril - 13h : 2nd contrôle continu (sur feuille + machine) :
Note finale : 100% CC, où CC = (CC1 + CC2)/2
Annales
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.
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.