Programmation Fonctionnelle

L'étudiant doit maîtriser les principes de l'algorithmique et de la programmation sans effet de bord en utilisant la programmation fonctionnelle. Il doit notamment maîtriser les concepts de récursivité, complexité et terminaison des algorithmes. Il doit pouvoir manipuler les listes et les itérateurs, ainsi que les modules et foncteurs. Le langage de programmation associé est le langage OCaml.

La matière est composée de 4 cours magistraux, 4 TD et 6TP. La matière est évaluée par un TP noté sur machine de 3h. Les concepts abordés sont :
- programmation fonctionnelle, sans effet de bord
- récursivité, récursivité terminale
- complexité, terminaison
- structures de données et itérateurs: listes, arbres
- conception modulaire, signatures, foncteurs

Contenu détaillé des séances :
C1 : introduction, syntaxe, notions de base, typage, filtrage
C2 : fonctions récursives, analyse récursive, terminaison et complexité, récursivité terminale
TP1 : premiers pas, fonctions récursives simples
C3 : listes, filtrage, tris et calcul de complexité
TD1 : listes, TAA file
TP2 : tris améliorés
TD2 : itérateurs
TP3 : algorithmes combinatoires et listes
C4 : types récursifs généraux (uniformes), arbres, parcours d’arbres
TD3 : arbres n-aires avec données dans les nœuds et dans les branches
TP4 et TP5 : arbres
TD4 : modules, foncteurs
TP6 : modules, foncteurs

Base de l'algorithmique et de la programmation.