Note : j’étais chargé des TD et TP du groupe Maths 2.
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 .
- 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.