Algorithmes et Programmation 3 (2019−2020)

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.