Table of Contents

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


Listes

Ces exercices sont un peu foireux : les "listes" en Python ne sont pas des listes simplement chaînées !

Exercice 1 : taille

Exercice 2 : concat

Mais attention le typage est toujours optionnel en Python :

Exercice 3 : appartient

Notre implémentation est évidemment plus lente que le test x in liste de la librarie standard... Mais pas tant :

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}|)$.

Exercice 6 : nb_occurrences

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.


Listes simplement chaînée (manuellement définies)

Comme ces exercices étaient un peu foireux à écrire avec les "listes" de Python, qui ne sont pas des listes simplement chaînées, je propose une autre solution où l'on va définir une petite classe qui représentera une liste simplement chaînée, et on va écrire les fonctions demandées avec cette classe.

La classe ListeChainee

On va supposer que les listes que l'on représentera ne contiendront pas la valeur None, qui est utilisée pour représenter l'absence de tête et/ou de queue de la liste.

Exercice 1 : taille

Par exemple la longueur sera bien en O(n) si n=taille(liste) avec cette approche récursive :

Exercice 2 : concat

Je vais déjà commencer par écrire une fonction copy qui permet de copier récursivement une liste simplement chaînée, pour être sûr que l'on ne modifie pas en place une des listes données en argument.

On peut vérifier que cela marche en regardant, par exemple, l'id de deux objets si le deuxième est une copie du premier : les id seront bien différents.

Et donc pour concaténer deux chaînes, c'est facile :

Exercice 3 : appartient

C'est en complexité linéaire dans le pire des cas.

Exercice 4 : miroir

Ce sera en temps quadratique, à cause de toutes les recopies :

Exercice 5 : alterne

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

La complexité est quadratique en $\mathcal{O}((\max(|\text{liste 1}|, |\text{liste 2}|)^2)$ à cause des recopies.

Exercice 6 : nb_occurrences

Ce sera en temps linéaire, dans tous les cas.

On peut facilement écrire une variante qui sera récursive terminale ("tail recursive") :

Exercice 7 : pairs

C'est un filtrage par le prédicat x % 2 == 0. Autant écrire la fonction de filtrage générique :

Et donc c'est rapide :

Exercice 8 : range

Ce sera de complexité temporelle linéaire :

Si on veut les avoir dans l'ordre croissant, il faudrait utiliser miroir qui est quadratique. Autant écrire directement une fonction intervale(a, b) qui renvoie la liste simplement chaînée contenant a :: (a+1) :: ... :: b :

Une autre approche est d'écrire la fonction mymap et de dire que

intervale_bis(a, b) = miroir(mymap(lambda x: x + (a - 1), myrange(b - a + 1)))

Exercice 9 : premiers

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

On a besoin des fonctions suivantes :

Une version purement fonctionnelle est moins facile qu'une version impérative avec une référence booléenne.

On est prêt à écrire estPremier :

En effet il suffit de construire d'abord la liste des entiers impairs de 2 à $\lfloor \sqrt{n} \rfloor$, de les filtrer par ceux qui divisent $n$, et de vérifier si on a aucun diviseur (taille(..) == 0) auquel cas $n$ est premier, ou si $n$ a au moins un diviseur auquel cas $n$ n'est pas premier.

On voit dans l'exemple ci dessus les nombres premiers comme ceux n'ayant aucun diviseurs, et les nombres non premiers comme ceux ayant au moins un diviseur.


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

(On voit que la liste autre a été inversée)

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

Exercices 13, 14, 15 : Tri fusion

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

Comparaisons


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

Est-ce que notre implémentation peut être plus rapide que le test x in liste ? Non, mais elle est aussi rapide. C'est déjà pas mal !

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

Pour de petites listes, la version récursive est aussi efficace que la version impérative. Chouette !

Bonus :

Exercice 26 : miroir version 2

Attention en Python, les listes ne sont PAS simplement chainées, donc lambda l, x : [x] + l est en temps linéaire en $|l| = n$, pas en $\mathcal{O}(1)$ comme en Caml/OCaml pour fun l x -> x :: l.


Arbres

/!\ Les deux dernières parties sont bien plus difficiles en Python qu'en Caml.

Exercice 27

Avec une syntaxe améliorée, on se rapproche de très près de la syntaxe de Caml/OCaml :

Exercice 28

Compte le nombre de feuilles et de sommets.

Exercice 29

Exercice 30

Bonus. (Écrivez une fonction testant si un arbre étiqueté par des entiers est tournoi.)


Parcours d'arbres binaires

Après quelques exercices manipulant cette structure de dictionnaire, écrire la suite n'est pas trop difficile.

Exercice 31

Exercice 32 : Parcours naifs (complexité quadratique)

Pourquoi ont-ils une complexité quadratique ? La concaténation (@ en OCaml, + en Python) ne se fait pas en temps constant mais linéaire dans la taille de la plus longue 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

Pour utiliser une file de priorité (priority queue), on utilise le module collections.deque.

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

Exercice 35 et fin

Reconstruction depuis le parcours prefixe

L'idée de cette solution est la suivante : j'aimerais une fonction récursive qui fasse le travail; le problème c'est que si on prend un parcours prefixe, soit il commence par F et l'arbre doit être une feuille; soit il est de la forme N::q où q n'est plus un parcours prefixe mais la concaténation de DEUX parcours prefixe, on ne peut donc plus appeler la fonction sur q. On va donc écrire une fonction qui prend une liste qui contient plusieurs parcours concaténé et qui renvoie l'arbre correspondant au premier parcours et ce qui n'a pas été utilisé :

Et cet exemple va échouer :

Reconstruction depuis le parcours en largeur

Ce n'est pas évident quand on ne connait pas. L'idée est de se servir d'une file pour stocker les arbres qu'on reconstruit peu à peu depuis les feuilles. La file permet de récupérer les bons sous-arbres quand on rencontre un noeud

Le même algorithme (enfin presque, modulo interversion de g et d) avec une pile donne une autre version de la reconstruction du parcours prefixe.


Conclusion

Fin. À la séance prochaine.