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

TD : Structures de données

3 mars

Arbres

• Arbres binaires de recherche

TD : Arbres

10 mars

Programmation dynamique

• Exponentiation rapide
• Puissance d’une matrice, square and multiply

TD : Programmation dynamique

17 mars

1er contrôle continu

24 mars

Programmation linéaire - Algorithme du simplexe

TD : Programmation linéaire

31 mars

String matching

• Rabin-Karp,
• Automates finis

TD : String matching

7 avril

Graphes

• Notions de base, représentation, matrice d’adjacence
• Parcours en largeur et en profondeur
• Tri topologique
• Plus court chemins, Dijkstra et Bellman-Ford

14 avril

TD Graphes

• Programmation des algorithmes vus en cours
• Arbre couvrant minimum
• Preuves en exercice

TD : Graphes

21 avril

Problèmes NP complets, machines de Turing

5 mai

Second et dernier CC

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

• CC 1, 2020
• Devoir à la maison (CC2), 2020
• Examen 2020
• Rattrapage 2020

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.