Option informatique 1ère année (2016-2017)

Table des matières

Premier cours et premier TP. Vous pouvez récupérer le fichier Caml que nous avons créé en cours.

Second cours. Exercice pour le mardi 7 mars:

Écrire une fonction append : ’a list -> ’a list -> ’a list telle que append l1 l2 retourne la liste constituée des éléments de l1 suivis de ceux de l2. Ainsi append [1; 2; 3] [4; 5; 6] doit retourner la liste [1;2;3;4;5;6]. On rappelle que [a; b; c] n’est qu’une notation (pratique) pour la liste a::(b::(c::[])).
Calculer la complexité temporelle de l’exécution de append l1 l2 en fonction des longueurs respectives n₁ et n₂ de l1 et l2.
Écrire une fonction reverse : ’a list -> ’a list prenant en argument une liste [x₀;…;x_n−1] et retournant la liste [x_n−1;…;x₀].
Calculer la complexité temporelle de l’exécution de reverse l en fonction de la longueur n de l.

Vacances.

Ordres bien fondés (compléments au poly). Exercice: montrer la terminaison de la fonction de Ackermann.

Tri par insertion.

Diviser pour régner (suite).

Programmation impérative.