Python L1, TD/TP 25.02


Exercices

Quelques exercices sur les listes

Exercice 0.

Étant données deux listes de longueur quelconque mais identique : [x0,x1,x2, ... xn], et [y0,y1,y2, ... yn], par ex. aa=[1,2,3]; bb=[4,5,6], –
calculer la somme : x0*y0 + x1*y1 + ... + xn*yn .

Avertissement : cet exercice est MORALEMENT obligatoire (pas besoin de me rendre quoi que ce ce soit, mais BIEN le comprendre pour vous-mêmes). Si après un mois et demi de Python, où on travaille sur les boucles semaine après semaine, en cours, en TD et en TP, certains ne sont toujours pas capables d'écrire des simples boucles (et j'en ai vu dans vos devoirs...), on peut soupçonner qu'ils se moquent de leurs études.


Exercice 1.

Étant donnée une liste quelconque, par ex. ['a',1,(),8,'b',1,7,8,['x']], écrire une fonction qui parcourt la liste et élimine tous les doublons, éléments qui ont d'autres occurrences. Ici : ['a',1,(),8,'b',7,['x']]. On a la liberté de laisser en place l'arbitraire occurrence, pas forcément la première.
Extra. Réfléchir comment éliminer des éléments atomiques (nombres, etc.) cachées à l'intérieur des listes internes, par ex. [1,2,3,[4,2]] [1,2,3,[4]]. Ceci n'est pas facile, demande l'usage de la récursivité, et vous pourrez travailler dessus si vous avez vraiment trop de temps et vous avez envie de quitter les TP avant l'heure. J'espère que c'est compris !

Exercice 2.

"Rabbit sequence"


Exercice 3.

Étant donnée une liste de caractères – l'alphabet, par ex. alph=["a","b","c","d"], ainsi qu'un nombre entier n (par ex. 3), construire tous les mots (chaînes) basés sur cet alphabet, de longueur n. Ici : ['aaa', 'baa', 'caa', 'daa', 'aba', 'bba', 'cba', 'dba', 'aca', 'bca', 'cca', 'dca', 'ada', 'bda', 'cda', 'dda', 'aab', 'bab', 'cab', 'dab', 'abb', 'bbb', 'cbb', 'dbb', 'acb', 'bcb', 'ccb', 'dcb', 'adb', 'bdb', 'cdb', 'ddb', 'aac', 'bac', 'cac', 'dac', 'abc', 'bbc', 'cbc', 'dbc', 'acc', 'bcc', 'ccc', 'dcc', 'adc', 'bdc', 'cdc', 'ddc', 'aad', 'bad', 'cad', 'dad', 'abd', 'bbd', 'cbd', 'dbd', 'acd', 'bcd', 'ccd', 'dcd', 'add', 'bdd', 'cdd', 'ddd'].

Attention avec les tests, prendre des données petites !. Prouver que la longueur de cette liste est \(L^N\), où \(L\) est la longueur de l'alphabet. Donc pour \(L=26\) et \(N=5\), vous aurez une liste de 11881376 mots... Cependant, l'algorithme doit être universel, et fonctionner pour les données de taille quelconque.

Plusieurs algorithmes sont possibles. Le plus simple n'est pas plus compliqué qu'une triple boucle.

Ceci est un exemple de génération combinatoire, souvent nécessaire dans des algorithmes statistiques. Dans cette "niche" on trouve la génération des permutations, combinaisons (sous-ensembles de longueur concrète d'un ensemble), le powerset (l'ensemble de tous les sous-ensembles d'une collection), partitions (tout un "monde"...), etc. Ces algorithmes sont vraiment utiles, mais parfois "explosifs" : engendrent des données de taille considérable.


Exercice 4.

Étant donnée une liste numérique, par ex. [2,3,7,10,-5,4,5,12,6,6,3,1,8,9] écrire une fonction qui trouve les deux valeurs plus grandes dans la liste. La procédure retourne le tuple qui contient la valeur maximale, et la seconde valeur la plus grande, ici : (12,10). La liste est parcourue une seule fois, et ne subit aucune modification. Par contre, il faut opérer avec deux variables de travail qui stockent les valeurs mis à jour lors du parcours de la liste.


Exercice 5.

Listes multi-dimensionnelles.

Si les listes peuvent représenter des vecteurs dans la géométrie des espaces de dimension quelqconque M, les listes de listes peuvent représenter des matrices, par ex.

[[1,9,0,6],
 [0,2,2,0],
 [3,3,0,1]] ,

et elles peuvent aussi représenter des images, chaque élément est un pixel d'une couleur (ce sont des images monochromes, par ex. niveaux du gris, ou des images basées sur une palette (color map): une couleur prédéfinie pour chaque nombre ; pour les images en couleurs arbitraires la structure sera plus compliquée, et on y reviendra).


Exercice 6.

Implémenter l'algorithme de multiplication d'un vecteur (liste l) par une matrice A, la méthode classique, "ligne par colonne", où la liste - vecteur doit être "vu" comme verticale :

l=[a,
   b,
   c,
   d] .
La formulation mathématique est \(\displaystyle{l'_k = \sum_{j=0}^{N-1} {A_{kj}\cdot l_j}}\,,\) où la notation \(A_{kj}\) spécifie l'élément avec numéro de ligne k et colonne j.

"Couche interprète" pour Turtle ; introduction aux L-systèmes (1).

Exercice 7.

Un (simple) programme qui trace des courbes en mode "tortue", est une séquence de commandes : fd(...); left(...); fd(...); etc., normalement plongée dans des boucles et procédures récursives (donc, on ne voit pas explicitement une longue séquence de commandes, qu'il faudrait coder péniblement à la main...).
Supposons, que – dans le cadre d'UN problème traité par cet exercice, le pas de la tortue, et l'angle de rotation vers la droite ou vers la gauche, sont toujours les mêmes, disons a et α. On n'a donc pas besoin de paramètrer ces commandes, et une séquence symbolique, disons : "F+F-FF+F-F++F ..." peut représenter la séquence fd(a); left(alpha); fd(a); right(alpha); fd(a); fd(a); ...


Exercice 8.

Compréhensions et nombres premiers : le crible d'Ératosthène.

Pour plusieurs raisons, théoriques et pratiques, on a besoin de la liste de nombres premiers, assez longue (même si, en apparence, cela n'influence pas notre vie quotidienne). La construction de telle liste peut procéder comme suit : on parcourt les entiers, et pour chaque entier N on vérifie sa primalité, s'il est divisible par 2, 3, 5, etc., jusqu'à – à peu-près – la racine de N (car si un diviseur est plus grand que cette racine, l'autre doit être forcément plus petit).

Cependant, une telle stratégie est pénible ! On implementera la technique très vénérable d'Ératosthène (276 - 194 a.JC.)

Profitez de la construction nommée "compréhension", avec une boucle for implicite, et des conditionnelles de filtrage :

[expr(x) for x in _séquence_  if _condition_]
par ex. z = [p for p in range(279) if z % 17 == 2]. Si la condition est satisfaite, l'objet est retenu, sinon il est abandonné.


Semaine précédente
Semaine suivante
Retour à l'index