Table of Contents

TP 2 - Programmation pour la préparation à l'agrégation maths option info


Listes

Exercice 1 : taille

Pas sûr qu'elle soit récursive terminale, alors que celle là oui :

Solution plus ésotérique :

Exercice 2 : concat

Autre approche, moins simple mais de même complexité en $\mathcal{O}(n)$.

Exercice 3 : appartient

Exercice 4 : miroir

Exercice 5 : alterne

La sémantique n'était pas très claire, mais on peut imaginer quelque chose comme ça :

La complexité est linéaire en $\mathcal{O}(\max(|\text{liste 1}|, |\text{liste 2}|)$.

Mais on manque souvent la version la plus simple :

Exercice 6 : nb_occurrences

Autre approche, avec un List.fold_left bien placé :

Exercice 7 : pairs

C'est un filtrage :

Exercice 8 : range

Exercice 9 : premiers

Plusieurs possibilités. Un filtre d'Erathosthène marche bien, ou une filtration. Je ne vais pas utiliser de tableaux donc on est un peu réduit d'utiliser une filtration (filtrage ? pattern matching)

Une version purement fonctionnelle est moins facile qu'une version impérative avec une référence booléenne (rappel : pas de break dans les boucles for en OCaml...).


Quelques tris par comparaison

On fera les tris en ordre croissant.

Exercice 10 : Tri insertion

Complexité en temps $\mathcal{O}(n^2)$.

Exercice 11 : Tri insertion générique

Exercice 12 : Tri selection

Complexité en temps : $\mathcal{O}(n^2)$.

Exercices 13, 14, 15 : Tri fusion

Complexité en temps $\mathcal{O}(n \log n)$.


Listes : l'ordre supérieur

Je ne corrige pas les questions qui étaient traitées dans le TP1.

Exercice 16 : applique

Exercice 17

Exercice 18 : itere

Exercice 19

Exercice 20 : qqsoit et ilexiste

Exercice 21 : appartient version 2

Exercice 22 : filtre

Exercice 23

Je vous laisse trouver pour premiers.

Exercice 24 : reduit

Très pratique pour calculer des sommes, notamment.

Exercice 25 : somme, produit

Exercice 26 : miroir version 2


Arbres

Exercice 27

Autre variante, plus simple :

Exercice 28

Compte le nombre de feuilles et de sommets.

Exercice 29

Exercice 30

Bonus.


Parcours d'arbres binaires

Exercice 31

Exercice 32 : Parcours naifs (complexité quadratique)

Pourquoi ont-ils une complexité quadratique ? La concaténation (@) ne se fait pas en temps constant mais linéaire dans la taille de la première liste.

Exercice 33 : Parcours linéaires

On ajoute une fonction auxiliaire et un argument vus qui est une liste qui stocke les élements observés dans l'ordre du parcours

Exercice 34 : parcours en largeur et en profondeur

En remplaçant la file par une pile (Stack), on obtient le parcours en profondeur, avec la même complexité.

Exercice 35 et fin


Conclusion

Fin. À la séance prochaine.