Algorithmique et programmation 2

ECTS : 5

Enseignant responsable : Stephane AIRIAU (https://www.lamsade.dauphine.fr/~airiau/)

Langue du cours : Français

Volume horaire : 60

Description du contenu de l'enseignement :

• Analyse des algorithmes de tri
  • tri par insertion
  • diviser pour régner: tri Fusion, quicksort
  • trier en temps linéaire (tri par paquets, tri comptage, tri radix)
• Structures de données et leur analyse: tas, files, piles, listes chaînées, tables de hachage. Etude des structures natives en Python
• Tri par tas

Compétences à acquérir :

Comprendre et formaliser un algorithme, analyser la complexité (temps, espace, dans le pire des cas), comprendre le rôle des structures de données et développer des connaissances sur le langage Python.

Pré-requis obligatoires

Avoir suivi le cours Algorithmique et Programmation 1 qui donne les bases du langage Python.

Mode de contrôle des connaissances :

Partiel et examen.

Bibliographie, lectures recommandées :

Introduction to Algorithms, third or fourth edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.MIT Press.