Table of Contents

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

Remarques sur le style

Ici, pour vous montrer, j'ai utilisé :

Notez que ce n'est absolument pas nécessaire, c'était juste pour montrer que ce genre d'annotations peut aider à passer de Caml à Python.

Fonctions

Exercice 4

Exercice 5

Exercice 6

Récursivité

C'est simple. Pas besoin d'un mot clé rec quand on définit une fonction récursive en Python.

Exercice 7

Exercice 8

Pour ce genre de fonction, j'aime bien afficher les appels récursifs. On peut rendre ça optionnel, avec comme ici un argument nommé log, à valeur par défaut log=False.

On peut faire des essais pour afficher notre calcul de PGCD, sur des entiers aléatoires entre $1$ et $100$.

Pour se rassurer, on peut chercher dans la bibliothèque standard, à partir de Python 3.6 il y a la fonction math.gcd pour calculer le PGCD, sinon fractions.gcd ou encore dans le module (non standard) SymPy sympy.gcd.

Exercice 9

Rien de particulier à faire, la récursivité fonctionne sans réfléchir :

Dans IPython (ou Jupyter) on peut facilement mesurer le temps (moyen) d'exécution d'une fonction sur une entrée donnée, avec la macro %timeit.

Dans Python, on peut faire pareil avec timeit() du module timeit.

Fibonacci linéaire impérative

Pour la version qui est en complexité (temporelle) linéaire dans l'entrée $n$, il suffit de déplier la récursion en calculant $F_{n+1}$ progressivement en partant de $F_0, F_1$.

On peut vérifier que cette deuxième implémentation fonctionne comme la première, et ensuite vérifier qu'elle est (bien) plus rapide.

Fibonacci linéaire récursive

Pour la version qui est en complexité (temporelle) linéaire dans l'entrée $n$, il suffit de déplier la récursion en calculant $F_{n+1}$ progressivement en partant de $F_0, F_1$.

On peut vérifier que cette troisième implémentation fonctionne comme la première, et ensuite vérifier qu'elle est (bien) plus rapide.

Voilà les différences :

Un petit graphique : juste pour montrer ce que l'on peut faire rapidement

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.

On peut aussi écrire une version récursive :

Exercice 11

C'est assez naturel, on affiche la suite de mouvement à faire, comme une suite de "T1 -> T2" par exemple. La fonction suivante affiche les déplacements qu'il faut faire pour déplacer une tour de hauteur n initialement posée en x, à destination de z et avec y comme position intermédiaire.


Listes

Exercice 12

Les listes en Python sont des list.

Elles ne fonctionnent pas comme des listes simplement chaînées comme en Caml : ce sont des tableaux, donc l'accès à T[i] pour n'importe quel i est en $\mathcal{O}(1)$ pour n'importe quel i et n.

MUST READ Allez lire la page https://wiki.python.org/moin/TimeComplexity#list en détail !

Exercice 13

Exercice 14

Exercice 15

Exercice 16

Exercice 17


Exponentiation rapide

Exercice 18

Une approche naïve, de complexité temporelle linéaire en $n$ ($\mathcal{O}(n)$).

Exercice 19

Une approche maline (optimale, en fait).

Si n = 0 $x^0 = 1$

Si n est pair : $$ x^n = (x^{(n/2)})^2$$ $$ x^n = (x*x)^{(n/2)}$$

Si n est impair : $$ x^n = x * (x^{((n-1)/2)})^2$$ $$ x^n = x * (x*x)^{((n-1)/2)}$$

Exercice 20

On ne dispose pas de typage pour faire ça aussi joliment qu'en Caml...

Manuellement ce n'est pas trop dur :

Exercice 21

Exercice 22

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

Exercice 23

A comparer avec l'implémentation naïve qui était en $\mathcal{O}(n)$ :


Formule du calcul propositionnel

Spoiler alert : en Python, c'est chaud.

ATTENTION Il faut un peu d'habitude et d'idées pour réussir à faire tout ça aussi efficacement (enfin presque) qu'en OCaml.

On va faire des choses non typées, avec des dictionnaires, pour bidouiller.

Exercice 24

(not p ^ ((q ^ not p) v (r v q))) s'écrit en Caml (Conj(Not(V("p")),Disj(Conj(V("q"),Not(V("p"))),Disj(V("r"),V("q"))))).

On va imbriquer des dictionnaires, les types, V, Not, Conj et Disj seront des clés, et les valeurs seront des formules ou couples de formules. Mais on va cacher ça et l'utilisateur verra exactement la même chose qu'en Caml !

Si on veut afficher plus joliment ce genre de structures récursives, la fonction pprint.pprint(...) est là pour ça (elle affiche avec de l'indentation) :

Exercice 25

Ensuite on fait une filtration "à la main" sur les clés du dictionnaire (de niveau 1, on ne récurse pas quand on teste 'V' in formule).

Exercice 26

Et voilà. Pas tellement plus dur hein !

Exercice 27

Les valeurs des variables seront données comme un dictionnaire associant nom de variable à valeurs booléennes. Et comme on veut frimer, on prend un defaultdict, qui est comme un dict mais qui stocke aussi une fonction qui donne la valeur des clés absentes du dictionnaire :

Exercice 28

On trouve facilement les $n$ variables d'une formule.

Ensuite, un itertools.product permet de générer les $2^n$ valuations.

Note : ce code est encore plus concis que celui donné dans la solution en Caml.

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


Conclusion

Comme vous le voyez, on arrive à répondre aux mêmes questions dans les deux langages, et il n'y a pas de grosses différences en pratique dans la mise en oeuvre.

Là où OCaml 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...