1.  Home
  2.  Teaching

Algorithmes et Programmation 3 (2019–2020)

Université de Paris. L2 Maths (S1). exercise sessions  & practical work . 42 h.

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 O.
  • 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.