Skip to content

Latest commit

 

History

History
174 lines (97 loc) · 3.81 KB

index.md

File metadata and controls

174 lines (97 loc) · 3.81 KB
Raw
title
Home

Info pratiques

Cours & TD le mercredi de 13h50 à 17h00, salle G107 Bâtiment Sphie Germain (en Amphi J exceptionnellement le 19 avril)

Chargés de cours et TD : Kahina Bouchama et Yann Rotella

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

Lien cours Kahina Lien

Calendrier

1 février Kahina Bouchama

Introduction à l'analyse des algorithmes

  • Tri par insertion
  • Analyse de complexité

TD : (Ré)-introduction à Python

8 février Kahina Bouchama

Algorithmes de tri

  • Complexité asymptotique, notation $$\mathcal{\Theta}$$ et $$\mathcal{O}$$
  • Principe diviser pour régner
  • Exemple : tri fusion

TD : Algorithmes de tri

15 février Kahina Bouchama

Structures de données

  • Listes chaînées
  • Arbres
  • Tables de hachage

TD : Structures de données

22 février Yann Rotella

Arbres

  • Arbres binaires de recherche

TD : Arbres

8 mars Yann Rotella

Programmation dynamique

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

TD : Programmation dynamique

15 mars Yann Rotella

1er contrôle continu

22 mars Kahina Bouchama

Programmation linéaire - Algorithme du simplexe

TD : Programmation linéaire

29 mars Kahina Bouchama

Heuristiques - Algorithmes probabilistes

TD : TBA

5 avril

Graphes (1)

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

TD : Graphes

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

12 avril Yann Rotella

Graphes (2)

TD : Graphes

19 avril Yann Rotella

Problèmes NP complets, machines de Turing

26 avril Kahina Bouchama

Second et dernier CC

Pour aller plus loin (cours de l'année passée)

String matching

  • Rabin-Karp,
  • Automates finis

TD : String matching

Modalités d'évaluation :

15 mars - 13 h 50 : 1er contrôle continu (sur feuille + machine) :

26 avril - 13 h 50 : 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.