Algorithmes et Programmation 3 (2019−2020)

Institution
Université Paris Cité
Cursus
L2 Maths (S1)
Responsibilities
Exercise sessions: 18h. Practical work: 24h.

Note : j’étais chargé des TD et TP du groupe Maths 3.

Objectifs

  • savoir lire et concevoir un algorithme ;
  • savoir analyser un algorithme simple pour déterminer sa complexité dans le pire des cas et prouver sa correction ;
  • savoir implémenter des algorithmes en Python.

Chapitres

  • Codage et complexité. Codage des données, taille d’une donnée, notion de complexité dans le pire des cas d’un algorithme donné, utilisation de la notation OO.
  • Tris naïfs. Exemples d’algorithmes de tris non efficaces (tri à bulle, tri par insertion).
  • Récursivité. Introduction des stratégies usuelles de résolution de problèmes par programmation récursive, paradigme “diviser pour régner”. Exemple du tri fusion.
  • Programmation dynamique.
  • Structures de données. Introduction des notions de piles et files, exemple d’implémentation en Python. Thèmes supplémentaires. Au choix parmi, par exemple :
    • structures de données plus avancées telles que les tas ;
    • algorithmes simples sur les graphes ;
    • algorithmes gloutons.