Table of Contents

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

Fonctions

Exercice 4

Exercice 5

Attention à la différence entre fun qui définit une fonction anonyme, et function qui ne marche que dans la définition d'une fonction :

Exercice 6

Récursivité

Exercice 7

Exercice 8

Utilisons le générateur de nombres aléatoires pour faire quelques tests :

Exercice 9

Avec ce morceau de code on peut facilement mesurer le temps d'exécution :

Voilà la différence.

Exercice 10

Aucune hypothèse n'est faite sur les arguments de la fonction, on supposera seulement qu'elle est itérable sur sa sortie.

Exercice 11

Avec un compteur de coups joués (ce sera toujours $2^n - 1$) :


Listes

Exercice 12

Les listes en Python sont des list. Elles ne fonctionnent pas comme des listes simplement chaînées comme en Caml.

Exercice 13

Exercice 14

Avantage à la notation concise applique f l autorise à avoir (applique f)(l) au lieu de faire fun l -> applique l f si les deux arguments étaient dans l'autre sens.

Exercice 15

Avec de grandes listes, on voit la différence.

Exercice 16

Exercice 17

Pour un ordre, de type ordre : 'a -> 'a -> 'a :


Exponentiation rapide

Exercice 18

Complexité : linéaire ($\mathcal{O}(x)$)...

Exercice 19

Complexité : logarithmique ($\mathcal{O}(\log_2 x)$).

Exercice 20

Avec des champs d'enregistrement, c'est concis :

Par contre, impossible d'avoir un neutre de taille quelconque donc on doit écrire un monoied pour les matrices qui soit dépendent d'une taille $n$.

Manuellement ce n'est pas trop dur :

Exercice 21

Exercice 22

Et pour les matrices, un petit piège à cause des tailles :

Exercice 23


Formule du calcul propositionnel

Exercice 24

Exercice 25

Exercice 26

Et voilà. Pas si difficile non ?

Exercice 27

Les valeurs des variables seront données comme une fonction associant nom de variable à valeurs booléennes. On a l'avantage de pouvoir mettre les valeurs par défaut à true ou false via la filtration.

Exercice 28

On peut vérifier, par exemple sur Wolfram|Alpha que l'on obtient bien le bon résultat...


Conclusion

Voilà pour aujourd'hui !

Cette solution est aussi disponible en Python : TP1__Python.ipynb.

Là où Caml excelle pour les types définis, le filtrage et la récursion, Python gagne en simplicité sur l'affichage, sa librairie standard et les dictionnaires et ensembles...