Actualité

[[{"title":"Python - Programmation fonctionnelle","posi":0},{"text":"

On ne compte pas moins de 2500 langages de programmation créés depuis les années 50 jusqu’à aujourd’hui.

Bien qu’il ne soit pas utile d'en donner une liste exhaustive, voici ci-dessous un petit sous-ensemble qui montre la variété des langages disponibles.

ABC Ada Algol AWK APL

B Basic

C C++ C# CAML CLU

Cobol CPL CSS

Dart Delphi

Eiffel

Flow-Matic Forth Fortran

Go Hack Haskell

HTML ICon J Java JavaScript Julia

Kotlin Lisp

Mainsail M ML Modula

Oberon Objective-C OCaml

Pascal Perl PHP

PL/I Postscript Prolog Python

R Ruby

Rust

Scade Scala Scheme Sh Simula

Smalltalk SQL Swift Tcl/TK

TypeScript VBA

Si certains de ces langages ne sont que peu ou plus utilisés aujourd’hui, il en reste tout de même encore un très grand nombre qui sont le «langage préféré» de tout une communauté de développeurs.

Devant une telle profusion, on peut se demander pourquoi il existe autant de langages en informatique.

Quelles sont les différences entre ces langages?

Quels sont ceux qu’il est important de connaître?

Pourquoi utiliser un langage plutôt qu'un autre?

Etc.

Il est aussi important de remarquer que certains langages dans la liste ci-dessus n’existaient pas il y à dix ans et de même, il est fort probable que de nouveaux langages apparaîtront dans les dix prochaines années.

"},{"text":""}],[{"text":"

Pourquoi ne pas avoir un unique langage de programmation?

La raison est qu’un langage est souvent conçu pour répondre à des besoins ou des problématiques spécifiques.

Par exemple, pour écrire un driver de carte graphique, il est parfois nécessaire de programmer en assembleur

afin d’être au plus proche du fonctionnement de la machine.

En revanche, un langage comme SQL est plus adapté pour réaliser des opérations avec une base de données.

Il existe aussi des langages dits généralistes, c'est-à-dire conçus pour permettre de programmer le plus d’applications possibles. Python est un de ces langages.

Néanmoins, même les langages appartenant à cette catégorie évoluent sans cesse. Année après année, version après version, ils proposent de nouvelles instructions ou de nouveaux concepts pour simplifier le développement de logiciels.

Au final, cette abondance de langages est liée au fait que les critères pour les concevoir sont nombreux et quelquefois contradictoires.

Voici une liste non exhaustive de tels critères :

- expressivité, pour simplifier l'écriture des programmes grâce à des constructions de haut niveau ;

- lisibilité, pour faciliter la lecture et le raisonnement sur les programmes ;

- efficacité, pour écrire des programmes rapides en permettant une génération de code optimisé ;

- portabilité, pour que les programmes soient facilement exécutables sur plusieurs systèmes d'exploitation ou architectures ;

- sûreté, pour aider à l'écriture de programmes corrects, sans bugs ;

- maintenabilité, pour faciliter la maintenance des programmes et des logiciels.

","title":" "},{"edit":"

"}],[{"text":"

","title":" "},{"edit":"

Bien qu’il en existe un très grand nombre, les langages peuvent néanmoins être rassemblés par familles, on dit aussi paradigmes de programmation, selon les concepts qu’ils mettent en œuvre.

Là encore, la liste de ces familles de langages est longue et nous donnons ci-dessous les principaux paradigmes.

Impératif	Orienté objets	Fonctionnel
Concurrent	Événementiel	Orienté requêtes
Orienté contraintes	Synchrone	Logique

Par exemple, le paradigme impératif est celui des langages qui permettent de manipuler des structures de données modifiables (comme les variables, les tableaux, etc.) en utilisant notamment des boucles (while, for, etc.).

Les idées sous-jacentes à ces langages sont donc bien connues des utilisateurs de Python.

Les concepts du paradigme orienté objets, qui sont liés aux notions de classes, de méthodes et d’héritage, ont été présentés à travers le langage Python.

Il est important de noter qu’un langage de programmation peut appartenir à plusieurs familles. C’est le cas de Python qui, en plus des deux paradigmes précédents, propose par exemple des constructions pour la programmation concurrente, mais également des concepts du paradigme fonctionnel que nous allons présenter dans la suite de cette séquence.

Mais ce mélange des genres n’est pas propre à Python. On

trouve en effet de plus en plus de langages généralistes (comme C++ ou Java) qui s’appuient sur plusieurs paradigmes de programmation.

Comme les langages de programmation utilisés aujourd’hui ne sont pas ceux d’hier ni peut-être ceux de demain, il nous semble plus important de maftriser les concepts des paradigmes de programmation, plutôt que de chercher à apprendre un très grand nombre de langages. Cependant, il est parfois nécessaire de découvrir de nouveaux langages pour apprendre à programmer

dans un certain paradigme.

Par exemple, nous avons présenté les concepts de la programmation événementielle à travers le langage JavaScript.

De même, le paradigme de la programmation orientée requêtes est présenté avec le langage SQL que nous verrons plus tard dans l'année.

Dans la suite de cette séquence, nous allons présenter le paradigme fonctionnel. Si, comme son nom l'indique, ce style de programmation met en avant la notion de fonction, il est aussi intimement lié à la manipulation de structures de données non modifiables.

"}],[{"text":"

Supposons que l’on écrive en Python une fonction pour trier les éléments d’un tableau. On peut par exemple écrire un tri par insertion sous la forme d’une fonction tri_par_insertion(t) qui reçoit un tableau t en argument et trie, en place, ses éléments par ordre croissant.

Dans le code de cette fonction, donné dans le programme 15, on compare les éléments du tableau t à l’aide de l’opération > de Python. Cette opération possède un certain degré de généricité, dans le sens où elle permet de trier aussi bien un tableau d’entiers, de flottants, ou encore de chaînes de caractères.

En effet, la comparaison fournie par une opération de Python comme > s'applique à plusieurs types de données. Mieux encore, elle s'applique en profondeur

à. des tvnes structurés nomme des n-uplets.

Programme 15 — Tri par insertion

def insere(t, i, v):

\"\"\"insère v dans t[0...i[ supposé trié\"\"\"

j=i

while j > 0 and t[j - 1] > v:

t[j] = t[j - 1]

j=j-1

t[j] = v

def tri_par_insertion(t):

\"\"\"trie Le tableau t dans l’ordre croissant\"\"\"

for i in range(1, len(t)):

insere(t, i, t[i])

#test de la fonction

t1 = [(9,3),(4,7),(2,10),(6,5),(2,7),(3,0),(4,2)]

print(t1)

tri_par_insertion(t1)

print(t1)

Ainsi si on trie un tableau de couples d’entiers, ils seront triés selon la première composante et, en cas

d'égalité, selon la seconde composante.

Mais supposons maintenant qu’on ne souhaite pas trier selon la relation d'ordre définie par l'opération >.

On pourrait par exemple vouloir trier en ordre décroissant, ou selon une relation encore différente. Ainsi, on peut imaginer qu’on dispose d’un tableau contenant des élèves avec leur date de naissance, sous la forme de quadruplés,

eleves = [(\"Brian\", 1, 1, 1942),

(\"Grace\", 9, 12, 1906),

(\"Linus\", 28, 12, 1969),

....

et qu’on veuille trier ces élèves par année de naissance croissante. Avec notre fonction tri_par_insertion du programme 15, cela ne fonctionnera pas.

En effet, les prénoms vont être comparés en premier puis, à prénom égal, les jours vont être comparés, et ainsi de suite. Ce n’est pas ce que l’on souhaite.

Il nous faut donc écrire une autre fonction de tri.

Bien évidemment, il est facile de faire une copie de notre fonction tri_par_insertion puis de remplacer dans son code tout occurrence de la comparaison de deux éléments par la comparaison qui nous intéresse ici.

C'est même relativement simple, car dans le code du tri par insertion, la comparaison n'est faite qu’à un seul endroit. Mais c’est tout de même déplaisant. On comprend qu’on est parti pour faire une copie de la fonction de tri chaque fois que la relation d’ordre change, ce qui n’est clairement pas satisfaisant. Quand on programme, le copier-coller est en effet à proscrire, car toute erreur dans le code initial sera alors dupliquée et, si elle est corrigée un jour, elle ne le sera probablement que dans une copie.

","title":"Fonctions passées en arguments"},{"edit":""}],[{"text":"

Une bien meilleure solution consiste à passer la fonction de comparaison des éléments en argument de la fonction de tri.

Ceci est fait dans le programme 16.

Programme 16 — Tri par insertion générique

def insere(inf,t, i, v):

\"\"\"insère v dans t[0...i[ supposé trié\"\"\"

j=i

while j > 0 and not inf(t[j - 1] , v):

t[j] = t[j - 1]

j=j-1

t[j] = v

def tri_par_insertion(inf,t):

\"\"\"trie Le tableau t dans l’ordre croissant

pour la relation inf\"\"\"

for i in range(1, len(t)):

insere(inf,t, i, t[i])

On à toujours le tableau t en argument mais on à maintenant un premier argument, appelé inf pour «inférieur ou égal», qui est une fonction. Lorsque le code du programme de tri veut comparer deux éléments x et y, il appelle inf(x, y).

Le booléen renvoyé indique si x est inférieur ou égal à y.

Dans le code, on a donc remplacé l'expression

t[j - 1] > v

par l'expression

not inf(t[j - 1], v).

Le reste est inchangé.

Une fois que ce petit changement est fait, on à une fonction de tri qui nous permet de trier n'importe quel tableau pour n'importe quelle façon de comparer les éléments.

Si par exemple on veut trier un tableau d’entier

par ordre croissant (comme auparavant), il suffit de passer à la fonction tri_par_insertion une fonction qui fait la même chose que <=.

On le fait comme ceci :

def inf1(x, y):

return x <= y

#Test avev inf

t1 = [(9,3),(4,7),(2,10),(6,5),(2,7),(3,0),(4,2)]

print(t1)

tri_par_insertion(inf1,t1)

print(t1)

Mais surtout on peut maintenant trier notre tableau d’élèves par année de naissance, en passant en argument une fonction qui compare uniquement la

quatrième composante de chaque quadruplé.

def inf2(x, y):

return x[3] <= y[3]

Tester le code et vérifier que cela fonctionne bien avec le tableau élève ci-dess :

#Test avec inf pour les élèves

t1 = [('Blaise', 19, 6, 1623), ('Joseph Marie', 7, 7, 1752),

('Louis', 16, 5, 2003) ,('Grace', 9, 12, 1906)]

print(t1)

tri_par_insertion(inf2,t1)

print(t1)

Ainsi, on dispose maintenant d’un tri par insertion universel, que l’on peut utiliser à loisir pour trier n'importe quel tableau.

","title":" "},{"edit":""}],[{"text":"

On convient qu’il est un peu pénible d’écrire une fonction comme la fonction inf du premier cas, dont le code se réduit à l’utilisation de l'opération <=, à seule fin de pouvoir la passer en argument à la fonction tri_par_insertion. Pour y remédier, Python propose une notion de fonction anonyme, sous la forme d'une construction lambda.

lambda x, y: x[3] <= y[3]

Ainsi, l'expression désigne une fonction, anonyme, qui prend deux arguments, appelés ici x et y, et qui renvoie le booléen x[3] <= y[3]. Outre l’absence de nom pour cette fonction, on note l'absence des parenthèses autour des paramètres x et y ainsi que l’absence du mot-clé return.

Ainsi, on peut trier notre tableau d'élèves par année de naissance de la manière suivante :

#Test avec lambda

t1 = [('Blaise', 19, 6, 1623), ('Joseph Marie', 7, 7, 1752),

('Louis', 16, 5, 2003) ,('Grace', 9, 12, 1906)]

print(t1)

tri_par_insertion((lambda x, y: x[3] <= y[3]), t1)

print(t1)

Tester le code ci-dessous et conclure sur l'utilisation lambda.

","title":"Fonction anonyme"},{"edit":""}],[{"text":"

Supposons qu’un tableau Python contient n valeurs, x1,x2, .... , xn et que l’on souhaite calculer le résultat de

x1@x2@....@xn

pour une certaine opération @.

Ainsi, on peut imaginer que les valeurs sont des entiers et @ l'addition, ou que les valeurs sont des flottants et @ le maximum, ou encore que les valeurs sont des chaînes de caractères et @ la concaténation, etc.

Pour écrire un tel programme une seule fois, on peut

le faire sous la forme d’une fonction calcul qui reçoit en argument une fonction op qui représente l'opération @.

Le programme 17 contient une telle fonction. Pour simplifier un peu les choses, on suppose ici que le tableau t contient au moins une valeur.

Dès lors, on peut calculer facilement la somme, le produit ou encore le maximum des éléments d’un tableau d’entiers.

Programme 17 — Calcul sur un tableau

def calcul(op, t):

\"\"\"calcule t[0] op t[1] op ... op t[n-1]

le tableau t est supposé non vide\"\"\"

v = t[0]

for i in range(1, len(t)):

v = op(v, t[i])

return v

t = [1, 2, 3, 4, 5]

print(calcul((lambda x, y: x + y), t))

print (calcul((lambda x, y: x * y), t))

Avec des objets. passer une fonction en argument à

tri_par_insertion n’est pas la seule solution pour avoir un tri universel. Dans un contexte de programmation orientée objet, on peut en imaginer au moins deux autres.

- Les éléments du tableau à trier sont des objets qui fournissent tous une méthode inf.

Dans le code de la fonction de tri, au lieu d'écrire inf(x,y) pour comparer deux éléments x et y, on écrit

x.inf(y) .

C’est en fait déjà ce qui se passe dans le programme 15, car l'opération > de Python invoque la méthode appelée __gt__.

Dans le cas du tri de nos élèves, cependant, la méthode __gt__ ne réalise pas la comparaison que vous voulons et cette solution ne convient donc pas.

- Plutôt que de passer une fonction en argument de

tri_par_insertion, on passe un objet, appelons-le c, qui

fournit une méthode inf qui prend en arguments les deux éléments à comparer. Dans ce cas, au lieu d'écrire

inf(x, y) dans le programme de tri, on écrit

c.inf(x, y).

Un tel objet c est appelé un comparateur. Contrairement à la solution précédente, on peut

ainsi trier de mêmes éléments de plusieurs façons différentes.

Et notre fonction calcul n’est même pas limitée à des entiers, dès lors que la fonction op est cohérente avec le contenu de t.

","title":"Un autre exemple"},{"edit":"

"}],[{"title":"Fonctions renvoyées comme résultats"},{"text":"

En programmation fonctionnelle, les fonctions ne se contentent pas de pouvoir recevoir d’autres fonctions en argument. Elle peuvent également renvoyer une fonction comme résultat.

Prenons l'exemple de la dérivée d’une fonction. Dans certaines méthodes numériques, comme par exemple la méthode de Newton pour approcher le zéro d’une fonction, il est nécessaire de savoir calculer la dérivée d’une fonction f en un point x.

Lorsque la dérivée f' de f ne peut être calculée symboliquement, on peut approcher la valeur de f'(x) avec un taux d’accroissement

f(x+h) - f(x)

pour une valeur de h très petite.

Du coup, on peut écrire une fonction Python derive qui reçoit une fonction f en argument et renvoie une fonction qui approche la dérivée de f.

def derive(f):

h = 1e-7

return lambda x: (f(x + h) - f(x)) / h

#Tester la fonction derive

from math import sin, pi

d = derive(sin)

print(d(0.))

print(d(pi / 2))

Tester le programme et conclure.

On peut constater que cela fonctionne plutôt bien sur une fonction (ici, la fonction sinus) dont on connaît la dérivée (en l'occurrence la fonction cosinus).

Comme on le voit, la fonction renvoyée par derive, ici stockée dans une variable d, est ensuite utilisée comme n'importe quelle autre fonction Python.

Avec des objets, il est possible de réaliser quelque chose de comparable en utilisant des objets. En effet, on peut représenter une fonction par un objet (d’une certaine classe, peu importe son nom) qui fournit une méthode, appelons-la app, pour appliquer cette fonction. Ainsi, on pourrait avoir un tel objet représentant la fonction sinus dans une variable appelée sinus et obtenir la valeur de sin(x) en faisant sinus.app(pi) .

Dès lors, on peut imaginer que chaque objet qui représente une fonction fournit en outre une seconde méthode, derive, qui renvoie un autre objet représentant sa dérivée. Ainsi, sin.derive() est un objet qui représente la dérivée de la fonction sinus (et donc la fonction cosinus).

"},{"edit":"

"}],[{"title":" Structures de données immuables"},{"text":"

Dans cette section, nous illustrons un autre aspect de la programmation fonctionnelle, à savoir l’utilisation de structures de données immuables. Une structure immuable est une structure de données, a priori quelconque (tableau, ensemble, dictionnaire, etc.), que l’on ne peut plus modifier une fois qu’elle est construite.

Bien entendu, on peut néanmoins l'utiliser, pour en consulter le contenu ou pour construire d’autres structures de données. Avec Python, on est plutôt habitué pour l’instant à une programmation impérative où les structures de données sont au contraire mutables, c’est-à-dire que leur contenu est modifié par des opérations. Ainsi, on affecte de nouvelles valeurs aux cases d’un tableau, on ajoute des éléments dans un ensemble, de nouvelles entrées dans un dictionnaire, etc.

Dans cette section, nous allons montrer l'intérêt des structures immuables sur un exemple concret.

Supposons que l’on programme une structure de données pour réaliser des ensembles. En particulier, on fournit une opération pour construire un ensemble vide, des opérations pour ajouter ou supprimer un élément, une opération pour tester si un élément appartient à un ensemble, etc.

La façon dont ces ensembles sont réalisés ne nous intéresse pas ici. En revanche, la façon dont ils se présentent à l'utilisateur, selon le paradigme de programmation choisi, n’est pas sans conséquence et c’est ce que nous allons montrer.

Si par exemple on a opté pour le paradigme impératif, avec des opérations qui modifient l’ensemble passé en argument, alors on va se retrouver à écrire quelque chose comme ceci.

s = creer_ensemble()

ajouter(s, 34)

ajouter(s, 55)

Ici, l'opération ajouter modifie l’ensemble s qu’elle a reçu en argument, pour lui ajouter un nouvel élément. Dans un paradigme objet, on aura quelque chose de très semblable, à quelques détails syntaxiques près.

s = Ensemble()

s.ajouter(34)

s.ajouter(55)

Là encore, l’ensemble s est modifié par l'opération ajouter. Dans le paradigme fonctionnel, en revanche, l’opération ajouter ne modifie pas l’ensemble s mais renvoie plutôt un nouvel ensemble.

Du coup, on écrit quelque chose d’un rien différent comme ceci :

creer_ensemble()

ajouter(s, 34)

ajouter(s, 55)

À chaque appel à ajouter, un nouvel ensemble est renvoyé, ici stocké à chaque fois dans la même variable s. On pourrait aussi utiliser des variables différentes à chaque fois.

"},{"edit":"

"}],[{"text":"

De même, si on considère des opérations plus complexes, pour calculer par exemple l'union, l’intersection ou la différence de deux ensembles, il faut

décider si ces opérations modifient un de leur arguments ou au contraire renvoient un troisième ensemble. Si on opte pour le premier choix, il faut même décider lequel des deux ensembles est modifié.

Ainsi, on pourrait choisir que l’opération

union(a, b)

modifie l’ensemble a pour lui ajouter tous les éléments de l’ensemble b.

Cette dissymétrie est un peu déplaisante mais on n’a pas trop le choix dès lors qu’on a opté pour une version impérative de l'opération union. Sans grande différence, on écrirait a.union(b) avec le paradigme objet. Enfin,

dans le paradigme fonctionnel, on écrit plutôt quelque chose comme ceci

c = union(a, b)

où la variable c reçoit le résultat de l'union, sans modifier les ensembles a et b. Tout cela fait finalement peu de différence.

En première approximation, seule la syntaxe varie légèrement.

Mais supposons maintenant que nous voulons tester notre bibliothèque d'ensembles. Par exemple, on peut vouloir tester que l’identité mathématique

AUB=(A\\B)U(B\\A)U(A∩B) (1)

est toujours valable, où U désigne l'union, ∩, désigne l'intersection et \\ désigne la différence ensembliste.

Par exemple, on peut générer aléatoirement de nombreuses paires d’ensembles A et B, et choisissant soigneusement leur taille et le domaine de leurs éléments, et vérifier l’identité ci-dessus à chaque fois.

Construire un ensemble aléatoirement n’est pas difficile. On peut par exemple ajouter successivement dans un ensemble des entiers tirés aléatoirement avec la fonction randint. En revanche, tester l'identité ci-dessus n’est pas chose aisée si les opérations d'union, d’intersection et de différence modifient leurs arguments. En effet, si on commence par calculer AUB, avec quelque chose comme union(a, b) qui modifie l’ensemble a pour lui ajouter les éléments de b, alors on ne peut plus calculer a\\b, b\\a et a∩b car l’ensemble à été modifié. Il faut réaliser une opération copie pour copier un ensemble puis on doit écrire quelque chose qui ressemble à ce qui suit.

u1 = copie(a)

union(u1, b)

u2 = copie(a)

difference(u2, b)

b_a = copie(b)

difference(b_a, a)

union(u2, b_a)

i = copie(a)

intersection(i, b)

union(u2, i)

assert egal(u1, u2)

La situation ne serait pas vraiment différente si les ensembles étaient des objets avec des méthodes qui en modifient le contenu. Mais dans un paradigme fonctionnel, en revanche, où les opérations ne modifient pas leurs arguments, alors on peut écrire quelque chose de beaucoup plus simple :

assert egal(union(a, b),

union(union(difference(a, b), difference(b, a)),

intersection(a, b)))

C’est là une traduction littérale de l’identité (1), beaucoup plus agréable.

D'une manière générale, la programmation fonctionnelle se caractérise par l’idée que, comme en mathématiques, quand on applique deux fois la

même fonction aux mêmes arguments, alors on obtient le même résultat.

On appelle cela la transparence référentielle. Cette propriété exclut de fait tout effet de bord que la fonction pourrait avoir, comme la mutation d’une donnée.

","title":" "},{"edit":"

"}],[{"text":"

Écrire une fonction trouve(p, t) qui reçoit en arguments une fonction p (pour « propriété ») et un tableau t et renvoie le premier élément x de t tel que p(x) vaut True. Si aucun élément de t ne satisfait p, alors la fonction renvoie None.

Tester votre fonction trouve avec le code suivant :

t = [1,3,5,7]

print(trouve(lambda x : x==5 ,t))

t = [1,3,6,7]

print(trouve(lambda x : x==5 ,t))

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def trouve(p, t):

\"\"\"le premier élément æ de t tel que p(x) est vrai\"\"\"

for x in t:

if p(x):

return x

return None

"}],[{"text":"

Écrire une fonction applique(f, t) qui reçoit en arguments une fonction f et un tableau t et renvoie un nouveau tableau, de même taille, où la fonction f a été appliquée à chaque élément de t.

Le faire avec et sans la notation par compréhension.

Tester la fonction applique avec le code suivant :

t = [1,3,5,7]

print(applique(lambda x : x**3 + 2 ,t))

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

#Sans la notation par compréhension, on peut le faire

#par exemple comme ceci :

def applique(f, t):

r= []

for x in t :

r.append(f(x))

return r

#Avec la notation par compréhension, c’est beaucoup plus simple :

#def applique(f, t):

# return [f(x) for x in t]

"}],[{"text":"

Écrire une variante du programme 17 qui calcule le résultat de

f(x1)@f(x2)@....@f(xn)

sur les éléments x1,x2,...,xn d’un tableau, pour une fonction f et une opération quelconques @.

Tester la fonction calcul2 avec le code suivant :

t = [1,3,5,7]

print(calcul2(lambda x : x**2 + 4 , lambda x ,y: x+y , t))

Le résultat obtenu est 100.

Appliquer cette nouvelle fonction calcul pour obtenir la représentation du contenu d’un tableau sous la forme d’une chaîne de caractères de la forme \"1, 2, 3, 4\", c’est-à-dire où les éléments sont séparés par des virgules.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def calcul2(f, op, t):

v = f(t[0])

for i in range(1, len(t)):

v = op(v, f(t[i]))

return v

"},{"solution":"

Pour construire la chaîne demandée, il suffit de faire

print(calcu12((lambda x: str(x)), (lambda x, y: x+\", \"+y), t))

"}],[{"text":"

Écrire une fonction double(f) qui reçoit une fonction f en argument et renvoie une fonction qui applique deux fois de suite la fonction f à son argument.

Que vaut double(double(lambda x: x*x)) (2) ?

Trouver le résultat de tête, puis lancer le calcul pour le vérifier..

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def double(f):

return lambda x: f(f(x))

La réponse est 2^16 = 65536. En effet, le résultat de

double(lambda x: x*x) est la fonction x ++ (x^2)^2 = x^4 et donc le résultat de double (double(...)) est la fonction x ++ (x^4)^4 = x^16.

"}],[{"text":"

Écrire un code Python correspondant au test de l'identité (1) en utilisant les opérations non destructives des ensembles de Python, à savoir

les opérations | pour l’union, - pour la différence et & pour l'intersection.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Le test s'écrit aussi simplement que ceci :

assert à | b == (a - b) | (b - a) | (a & b)

"}],[{"text":"

Écrire une fonction repeter_delai(f, n, t) qui effectue n appels et affiche f(0),..., ,f(n - 1) où chaque appel à f est suivi d’une pause de t secondes.

On pourra utiliser la fonction time.sleep(t) pour mettre le

programme en pause pendant t secondes.

Tester la fonction avec le code suivant :

repeter_delai(lambda x : x**2 + 5,11,1)

Résultats affichés toutes les 1 secondes :

105

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

from time import sleep

def repeter_delai(f, n, t):

for i in range(n):

print(f(i))

sleep(t)

"}],[{"text":"

Écrire une fonction temps_d_execution(f, x) qui prend en arguments une fonction f et une valeur x et qui renvoie une paire formée du résultat de f(x) et du temps mis par ce calcul. Pour mesurer ce temps, on pourra utiliser la fonction time.perf_counter() ou la fonction time.time() . Mesurer le temps pris par la fonction boucle_inutile sur l’argument 10000000.

def boucle_inutile(n):

k=0

for i in range(n):

k=k+1

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

from time import perf_counter

def temps_d_execution(f, n):

t1 = perf_counter()

r = f(n)

t2 = perf_counter()

return (r, t2 - t1)

def boucle_inutile(n):

k = 0

for i in range(n):

k=k+i

print (temps_d_execution(boucle_inutile, 10000000))

"}],[{"text":"

La fonction temps_d_execution de l'exercice 43 n'accepte en argument que des fonctions à un argument, ainsi que l'argument sur lequel appeler la fonction.

Soit la fonction

def boucle_inutile2(n, m):

k=0

for i in range(n):

for j in range(m):

k=k+1

Indiquer comment utiliser la fonction temps_d_execution pour mesurer le temps de l’appel boucle_inutile2(1000, 10000), sans modifier aucune

des deux fonctions.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On peut utiliser une fonction anonyme :

temps_d_execution(lambda m: boucle_inutile2(1000, m), 10000)

Ici le lambda contient une « application partielle » de la fonction boucle_inutile2 où le paramètre 1000 est déjà passé.

"}],[{"text":"

La paradigme de la programmation événementielle consiste à associer du code pour qu'il soit exécuté lorsque survient un évènement.

Le programme de première présente ce paradigme dans le cadre de la programmation d’interfaces graphiques. C'est une application naturelle de la programmation fonctionnelle.

Le code associé aux événements est tout simplement une fonction stockée dans une structure

de données du système et appelée au moment opportun.

Compléter le code Python ci-dessous pour qu’à chaque clic de bouton, le nombre affiché sur celui-ci soit incrémenté.

import tkinter as tk

fenetre = tk.Tk()

b = tk.Button(fenetre, text=\"0\")

b.pack()

# ... insérer ici le code demandé ...

fenetre.title(\"Cliquer sur le bouton\")

fenetre.geometry(\"800x400\")

fenetre.mainloop()

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On définit une fonction gerer_clic passé en argu-

ment à la méthode bind du bouton b.

compteur = 0

def gerer_clic(ev):

global compteur

compteur = compteur + 1

ev.widget.configure(text=str (compteur))

b.bind(\"<Button-1>\", gerer_clic)

"}],[{"text":"

Soit le code suivant, qui définit une étiquette et 10 boutons.

Compléter la fonction changer_chiffre pour que le chiffre passé en argument soit utilisé comme texte pour l'étiquette.

Attention : on prendra garde à la façon dont cette fonction est appelée dans la boucle for.

import tkinter as tk

fenetre = tk.Tk()

chiffre = tk.Label(fenetre)

chiffre.grid(row=1, column=1, columnspan=10)

def changer_chiffre(c):

\"\"\"... compléter ici ...\"\"\"

x=0

for i in range(10):

c = str(i)

b = tk.Button(fenetre, text=c)

b.grid(row=2, column=i+1)

b.bind(\"<Button-1>\", changer_chiffre(c))

fenetre.mainloop()

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

La méthode bind attend en second argument une

fonction. Il faut donc que change_chiffre(c) renvoie la fonction que le système va stocker et appeler plus tard.

def changer _chiffre(c):

return lambda e: chiffre.configure(text=c)

Attention, appeler directement chiffre.configure(text=c) dans le corps

"}],[{"text":"

Considérons une petite bibliothèque permettant de manipuler des points dans le plan.

Partie 1. Une première implémentation utilise des n-uplets, qui en Python sont des séquences immuables.

# fichier point_imm.py

def point(x, y):

\"\"\"construire un point\"\"\"

return(x, y)

def deplacer(p, dx, dy):

\"\"\"translation d’un point\"\"\"

return point(p[0]+dx, p[1]+dy)

def triangle(p1, p2, p3):

\"\"\"construction d’un triangle\"\"\"

return (p1, p2, p3)

# une constante utile origine = point(O, 0)

1. Écrire du code Python utilisant cette implémentation pour créer 4 points a, b, c et d de coordonnées respectives (0, 0) , (1, 2) , (-5, 18) , (42, 37).

2. Écrire une fonction deplacer _triangle(t, dx, dy) qui renvoie un nouveau triangle dont les trois points sont déplacés chacun de dx et dy.

Tester votre travail avec le code suivant :

t1 = (a,b,c)

print(t1)

print(deplacer_triangle(t1,2,3))

Résultat :

((0, 0), (1, 2), (-5, 18))

((2, 3), (3, 5), (-3, 21))

3. Écrire du code Python qui crée deux triangles t1 et t2 constitués respectivement des points a, b, c et b , c, d.

4. Créer un triangle t3 obtenu en déplaçant t1 de (-1,-1) et t4 obtenu en déplaçant t2 de (2,3).

Tester avec le cpde suivant :

print(t1)

print(t2)

print(t3)

print(t4)

Résultat attendu :

((0, 0), (1, 2), (-5, 18))

((1, 2), (-5, 18), (42, 37))

((-1, -1), (0, 1), (-6, 17))

((3, 5), (-3, 21), (44, 40))

Partie 2. On considère maintenant une implémentation utilisant des objets et des modifications en place des attributs.

class point:

def __init__(self, x, y):

self.x = x

self.y = y

def deplacer(self, dx, dy):

self.x += dx

self.v += dv

class triangle:

def __init__(self, p1, p2, p3) :

self.p1 = p1

self.p2 = p2

self.p3 = p3

def deplacer(self, dx, dy):

self.p1.deplacer(dx, dy)

self.p2.deplacer(dx, dy)

self.p3.deplacer(dx, dy)

1. Est-il pertinent de rajouter à cette implémentation une variable globale origine contenant le point (0,0)?

2. Comme précédemment, créer 4 points a, b, c et d.

3. Créer deux triangles t1 et t2 constitué de a, b, c et b, c, d.

4. Déplacer t1 de (-1,-1) et t2 de (2,3). Obtient-on des triangles équivalents aux triangles t3 et t4 de la Partie 1 ?

5. Proposer une modification de l'implémentation mutable qui corrige le problème.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

#Partie 1.

# Question 1.1

a = point(0, 0)

b = point(1, 2)

c = point(-5, 18)

d = point(42, 37)

"},{"solution":"

# Question 1.2

def deplacer_triangle(t, dx, dy):

p0 = deplacer(t[0], dx, dy)

p1 = deplacer(t[1], dx, dy)

p2 = deplacer(t[2], dx, dy)

return triangle(p0, p1, p2)

"},{"solution":"

# Question 1.3

t1 = triangle(a,b,c)

t2 = triangle(b,c,d)

"},{"solution":"

# Question 1.4

t3 = deplacer_triangle(t1, -1, -1)

t4 = deplacer_triangle(t2, 2, 3)

"},{"solution":"

Partie 2. A priori, si l’on crée un objet origine = point(0,0) mutable, alors on pourra modifier l’origine en faisant origine.deplacer(1,1), ce qui n’est pas souhaitable. À chaque fois que l’on voudra utiliser l'origine, il faudra recréer le point avec point (0,0).

"},{"solution":"Question 2.2

a = point(0, 0)

b = point(1, 2)

c = point(-5, 18)

d = point(42, 37)

"},{"solution":"

# Question 2.3

t1 = triangle(a, b, c)

t2 = triangle(b, c, d)

"},{"solution":"

# Question 2.4

ti.deplacer(-1, -1)

t2.deplacer(2, 3)

"},{"solution":"

#Question 2.5

class point:

# constructeur et deplacer inchangés

def clone(self):

return point(self.x, self.y)

class triangle:

def __init__(self, pi, p2, p3):

self.pi = p1.clone()

self.p2 = p2.clone()

self.p3 = p3.clone()

# deplacer inchangé

Avec les modifications ci-dessus, la classe triangle stocke une copie des points qui lui sont passés en argument. Elle peut donc les modifier sans impacter les points initiaux. Il faudra cependant être vigilant, à chaque fois que l'on «donne» un tel point mutable à une fonction dont on ne connaît pas le code, car il existe un risque que ce point soit modifié. Il conviendra

donc de faire des copies au moment opportun. Le style fonctionnel utilisé en Partie 1 permet d'écrire une code plus lisible (il n’est pas encombré d'opérations de copies) et dans lequel les erreurs causées par le partage sont inexistantes.

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 20 Septembre 2020; Mis à jour : 28 Septembre 2020; Clics : 1446

[[{"title":"Python - Mise au point des programmes","posi":0},{"text":"

Nous allons aborder trois thèmes liés à la

spécification des programmes et à la gestion des erreurs :

- le typage, qui permet la détection précoce d’incohérences dans un programme ;

- le test systématique et rigoureux des différentes fonctions composant un programme ;

- les invariants de structure, qui spécifient les propriétés internes des structures de données complexes.

"},{"text":""}],[{"text":"

En programmation, la notion de type désigne une classification des objets manipulés en fonction de leur nature. D’un langage à l’autre, ces informations sont plus ou moins présentes, mais on gagne toujours à ne pas les ignorer.

","title":"Types"},{"edit":"

"}],[{"text":"

","title":"Les types en Python"},{"edit":"

Chaque valeur manipulée par un programme Python est associée à un type, qui caractérise la nature de cette valeur. On a ainsi un type int pour les nombres entiers, et d’autres types de base illustrés dans le tableau suivant.

valeur	type	description
1	int	nombres entiers
3.14	float	nombres décimaux
True	bool	booléens
“abc'\"	str	chaînes de caractères
None	NoneType	valeur indéfinie
(1 , 2)	tuple	n-uplets
[1, 2, 3]	list	tableaux
{1, 2, 3}	set	ensembles
{’a’: 1, ’b’: 2}	dict	dictionnaires

En outre, chaque nom de classe Python définit un type, de même nom, pour les instances de cette classe.

En Python, on dispose d’une fonction type permettant d’obtenir le type de la valeur passée en paramètre.

En jouant avec cette fonction dans la boucle interactive, on pourra par exemple vérifier que {} en Python désigne le dictionnaire vide et non l’ensemble vide, observer que les fonctions peuvent être vues comme des valeurs dont le type est tout simplement appelé fonction, ou encore remarquer que les classes elles-mêmes ont le type, type!

Les types permettent de caractériser les opérandes ou paramètres qui sont ou non acceptables pour certaines opérations. En particulier, l’utilisation de valeurs qui seraient par nature incompatibles avec une opération donnée lève une exception TypeError qui est généralement accompagnée

d’information sur les types qui ne conviennent pas.

Dans le cas d'opérateurs comme + qui peuvent avoir de multiples significations (on parle ici de surcharge de cet opérateur), les types des opérandes permettent également de préciser ce aui doit être fait.

exemple	opérande	effet	résultat
1+2	int	addition	3
1.2 + 3.4	float	addition	4.6
True + True	bool	addition	2
\"abc\" + \"de\"	str	concaténation	\"abcde\"
(1, 2) + (3, 4)	turple	concaténation	[1, 2, 3, 4)
[1, 2] + [3, 4] \|	list	concaténation	[1, 2, 3, 4]

En Python, la gestion des types est qualifiée de dynamique : c'est au moment de l'exécution du programme, lors de l'interprétation de chaque opération de base, que l’interprète Python vérifie la concordance entre les opérations et les types des valeurs utilisées.

Bien que le langage Python ne nous y pousse pas explicitement, il est utile d’avoir en tête les types des différentes variables et expressions contenues dans les programmes que nous écrivons ou lisons : cette information, qu’on peut rapprocher de la notion de dimension des grandeurs physiques, aide à la compréhension de l’ensemble et évite les incohérences.

"}],[{"text":"

Erreurs. L’addition d’un nombre entier et d’un tableau n’a pas de sens en Python.

>>> 1 + [2, 3]

Traceback (most recent call last):

File \"<stdin>\", line 1, in <module>

TypeError: unsupported operand type(s) for +:

int” and ’list’

","title":"Création d'un objet"},{"edit":""}],[{"text":"

Bien qu’en Python les types ne jouent réellement un rôle qu’au niveau des opérations de base, il est indispensable lors de la définition d’une fonction d’avoir en tête les types attendus pour les paramètres et l’éventuel type du résultat.

Cette information est même une information cruciale à fournir dans l'interface d’un module, pour préciser la description faite de chaque fonction et éviter autant que possible leur mauvaise utilisation.

En effet, l'utilisateur d’un module n’étant pas censé avoir besoin de lire le code de ce module, lui présenter à l'exécution une erreur de type survenant à l’intérieur de ce code qu’il aurait dû pouvoir ignorer est pour le moins discourtois.

De manière plus générale, même sans parler d'interface il est utile de concevoir clairement le type des données associées à chaque variable d’un programme.

Pour inclure ces informations sur les types dans le programme lui-même il est possible d’annoter le code d’un programme, et en particulier les définitions de variables et de fonctions.

Ainsi, lors de la première définition d’une variable x destinée à représenter un nombre entier.

Nous pouvons utiliser la notation suivante :

x: int = 42

Dans cette instruction d’affectation ordinaire, le nom de la variable est suivi d’un symbole : (deux-points) et du type associé à cette variable.

Pour fournir les informations de types sur les paramètres et le résultat d’une fonction, des annotations similaires sont incluses dans la première ligne de la définition, c’est-à-dire la ligne donnant les noms de la fonction et de ses paramètres. Pour illustrer nos propos, nous allons reprendre le code des programmes 6 et 7. Par exemple, notre fonction contient_doublon du programme 7, qui attend un tableau t (type list en Python) et renvoie un booléen (type bool), peut ainsi voir la première ligne de sa définition annotée comme ceci :

def contient _doublon(t: list) -> bool:

Comme le montre cet exemple on annote un paramètre de la même manière qu’une variable, en faisant suivre son nom par le symbole : (deux-points) et le type attendu pour ce paramètre. On indique le type du résultat d’une fonction à la fin de la ligne, juste avant le : marquant le début du corps de la fonction, après une flèche ->.

L’annotation des fonctions du programme 6 suit le même principe. La fonction crée n'attend aucun paramètre et renvoie un tableau.

def cree() -> list:

La fonction contient attend pour paramètres un tableau et un entier, et renvoie un booléen. Les deux paramètres annotés sont séparés par une virgule, comme ils l’étaient avant d’être annotés.

def contient(s: list, x: int) -> bool:

La fonction ajoute attend pour paramètres un tableau et un entier, et ne renvoie pas de résultat. On note l’absence de résultat en indiquant None comme type de retour 1.

def ajoute(s: list, x: int) -> None:

En Python, ces annotations ont uniquement un rôle de documentation.

L’interprète lui-même ne fait aucune vérification de cohérence, lors de lappel d’une fonction ou de l’utilisation d’une variable, entre les types déclarés et

les types des valeurs effectivement utilisées. Les annotations fournissent en revanche des informations importantes pour toute personne amenée à lire le

programme ou à utiliser ses fonctions.

En outre, des outils externes peuvent être utilisés pour faire des vérifications globales de cohérence des types dans des programmes Python. Ces outils, eux, utilisent les annotations apportées par le programmeur.

","title":"Annoter les variables et les fonctions"},{"edit":""}],[{"text":"

En Python, les types connus pour les valeurs structurées comme les n-uplets et les tableaux restent très superficiels : le couple d’entiers (1, 2) et le triplet mixte (1, \"abc\", False) ont tous les deux le type tuple.

De même un tableau d’entiers et un tableau de chaînes de caractères auront tous deux le type list, et la même confusion s'applique aux ensembles ou encore aux dictionnaires.

","title":"Types nommés, types paramétrés et généricité"},{"edit":""}],[{"text":"

À l'inverse de Python, de nombreux langages de programmation ont une gestion dite statique des types, en procédant à des vérifications au moment de la compilation des programmes. Dans de tels langages, un programme comportant des incohérences entre des opérations et les valeurs auxquelles elles s'appliquent ne sera jamais exécuté.

L'intérêt de ces vérifications en amont est de faire que les incohérences soient détectées aussi tôt que possible, et de manière systématique. Avec

de tels langages, il se passe donc parfois plus de temps avant qu’un programme ne puisse être exécuté pour la première fois, puisqu'il faut corriger au préalable les éventuelles incohérences détectées par le compilateur. En revanche, on gagne énormément de temps sur le débogage, puisqu'on évite les erreurs que ces incohérences auraient immanquablement causées lors des tests, ou pire, lors de l’utilisation réelle.

Les vérificateurs de types, inclus dans ces langages à typage statique ou disponibles comme outils externes pour Python, utilisent les annotations de types données par le programmeur. Certains langages sont mêmes capables d’une inférence de types, c'est-à-dire qu'ils déterminent par eux-mêmes le type de chaque élément du programme, sans l’aide du programmeur.

","title":"Vérification statique des types et détection précoce des erreurs."},{"edit":"

"}],[{"title":"Vérificateurs de types pour Python"},{"text":"

Un outil libre historique pour la vérification statique des types en Python est mypy (http://www.

mypy-lang.org).

L'outil peut être ajouté à toute installation standard

de Python, et fournit un programme que l’on peut exécuter sur un ensemble de fichiers .py pour réaliser la vérification et, le cas échéant, obtenir la liste des erreurs.

Depuis, plusieurs grandes compagnies ont également produit leur vérificateur, qu’il s'agisse comme mypy d'outils à exécuter à part (pytype de Google ou pyre de Facebook), ou d'outils intégrés à un environnement de développement (l'éditeur pycharm de JetBrains ou le

Visual Studio Code de Microsoft).

"},{"edit":"

"}],[{"title":"Types paramétrés."},{"text":"

On peut cependant être plus précis dans la description

des types de ces éléments composites, en associant le type de l’élément lui-même et le ou les types de ses composants. On dit que le type de l’élément principal est paramètré par le ou les types de ses composants.

Le tableau suivant donne quelques exemples compatibles avec la syntaxe des annotations de types de Python.

type	description
Tuple[int, bool]	couple d’un entier et d’un booléen
List[int]	tableau d’entiers
Set[str]	ensemble de chaînes de caractères
Dict[str, int]	dictionnaire dont les clés sont des chaînes de caractères et les valeurs des entiers

Notez que les types paramétrés de ce tableau sont écrits avec une première

lettre majuscule : il ne s’agit pas directement des types de base tuple, list, set et dict de Python, mais de nouvelles versions définies dans le module typing (et qui doivent donc être importées avant utilisation).

"},{"edit":"

"}],[{"text":"

Lorsque l’on manipule des structures de données particulières, il est courant de fournir un nouveau nom (appelé alias) à leur type.

Ainsi, la structure de données représentant un ensemble de l’un ou l’autre des programmes 6, 9 ou 10 pourrait être simplement nommée Ensemble dans

l'interface du module correspondant, et les trois fonctions auraient alors les types suivants.

cree() -> Ensemble

contient(s: Ensemble, x: int) -> bool

ajoute(s: Ensemble, x: int) -> None

Cette pratique a de nombreux avantages. En premier lieu elle présente à l'utilisateur du module un nom

représente et non la manière dont il est réalisé en interne.

Par conséquent, cette pratique accompagne également l’encapsulation : le type présenté par l'interface ne dépend pas des détails d’implémentation, et n’a donc pas à être modifié en cas d’évolution de la représentation interne.

Remarque : les types donnés pour cree, contient et ajoute valent pour toutes les réalisations que nous avons données de ces fonctions, bien que ces dernières adoptent des représentations très différentes. En effet, dans le programme 6 le type Ensemble serait défini par

Ensemble = List[int]

alors que dans le programme 9 nous aurions

Ensemble = List[List{int]]

Notez que dans le cas où un tel module est réalisé à l’aide d’une classe,par exemple dans le programme 12, le nom de la classe définit le nom du type correspondant. Le détail de la signification de Ensemble est alors déduit de la définition de la classe.

","title":"Alias de types. "},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

Les annotations de types d’une méthode d’une classe sont exactement les mêmes que celles des fonctions ordinaires. Il faut simplement noter que le premier paramètre, self, désignant un objet de la classe contenant la méthode, son type sera nécessairement cette classe elle-même.

class Chrono:

def texte(self: Chrono) -> str:

def avance(self: Chrono, s: int) -> None:

","title":"Annotations de types pour les méthodes"},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

L'interface fournie aux modules représentant des ensembles d’entiers pourra être adaptée pour

des ensembles d’autres types d'éléments.

En donnant un type EnsembleC pour des ensembles de chaînes de caractères, il suffira d’écrire les types

adaptés suivants.

cree() -> EnsembleC

contient(s: EnsembleC , x: str) -> bool

ajoute(s: EnsembleC, x: str) -> None

On peut même imaginer un module d’ensembles généralistes, capable de

gérer des ensembles homogènes d'éléments d’un type arbitraire. On peut

ainsi avoir une variante paramétrée Ensemble [T] du type Ensemble, où T

est un paramètre de type non précisé (on l'appelle parfois variable de type,

où le mot « variable » doit cette fois être compris au sens mathématique et

plus au sens informatique). L'interface devient alors

cree() -> Ensemble[T]

contient(s: Ensemble[T], x: T) -> bool

ajoute(s: Ensemble[T], x: T) -> None

et n’impose plus un type particulier d'éléments dans l’ensemble, mais seulement une cohérence entre le type des éléments contenus dans l’ensemble et le

types des éléments que l'on veut ajouter ou dont l’on veut tester la présence.

Le même module fournissant ces ensembles de type Ensemble[T] pourra alors être utilisé par un client pour des ensembles d’entiers (Ensemble[int] ),par un autre pour des ensembles de couples d’entiers et de chaînes de caractères (Ensemble[Tuple[int, str]], etc.

Pour se conformer à une telle interface générique, un module doit réaliser les différentes opérations sans utiliser d'opérations spécifiques à un type particulier.

La stratégie rudimentaire utilisée dans le programme 1 donne un tel exemple : l’opération s.append(x) n’agit que sur le tableau s et n’a pas besoin de consulter la valeur de x, et l'opération x in s ne consulte x et les éléments de l’ensemble que pour tester leur égalité deux à deux, ce qui est possible quels que soient les types des éléments.

Les autres programmes que nous avons donnés en revanche utilisent d’une manière ou l’autre le fait

que les éléments de l’ensemble étaient des entiers. Ainsi, en réalisant un module générique on s’interdit certaines optimisations qui tireraient parti d’une nature particulière des éléments manipulés. En revanche on gagne en réutilisabilité du code, ce qui est l’un des objectifs de la modularité!

","title":"Types génériques"},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

Le programme 10 réalisant une table de hachage simple pourrait facilement être transformé en un module d’ensembles capable de gérer une grande variété de types d'éléments : il suffit, à chaque fois que l’on détermine le numéro du paquet d’un élément

x avec une opération

p = x % n

de faire à la place

p = hash(x) % n.

La fonction hash de Python, appelée fonction de hachage, prend en paramètre un élément de n'importe quel type « hachable » et renvoie un entier (le code de hachage de cet élément). Cette fonction est utilisée

en interne par les ensembles et dictionnaires de Python.

Grâce à cette combinaison il est possible d’avoir des structures pour les ensembles et les dictionnaires qui soient à la fois génériques et très efficaces.

","title":"Tables de hachage génériques"},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

Le module typing permet d'introduire des variables de type avec l'opération TypeVar. On peut alors utiliser

ces variables dans les annotations.

from typing import TypeVar, List

T = TypeVar(’T’)

Ensemble = List[T]

def contient(s: Ensemble, x: T) -> bool:

Notez que pour pouvoir écrire Ensemble[T] en Python tel que nous l'avons fait dans le texte il faut utiliser les mécanismes d’héritage (hors programme) pour indiquer que le type Ensemble est un cas particulier d'un type spécial Generic[T] défini dans le module typing.

Nous prendrons cependant la liberté d’utiliser cette notation paramétrée partout où elle sera utile pour clarifier les interfaces.

","title":"Variables de types en Python"},{"edit":"

Tester et mettre le résultat ici (code et figure).

"}],[{"text":"

Même si on a correctement spécifié et documenté une programme, il reste possible de faire une erreur en écrivant son code.

Pour détecter ces éventuelles erreurs, on peut utiliser le programme sur quelques cas concrets et vérifier qu’il produit effectivement les résultats attendus.

On appelle cela le test

","title":"Tester un programme"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"title":"Code de sortie d'un programme","text":"

Lorsqu'un programme se termine, il signale au système d'exploitation s'il a terminé son exécution normalement, ou bien au contraire s'il s'est arrête sur une erreur, à l’aide d'un code de sortie, qui est un entier.

Lorsqu'un programme Python parvient sans erreur au terme de la séquence de ses instructions, il termine avec le code 0, qui désigne une exécution qui s'est correctement déroulée. De même, un appel à exit() termine le programme avec le code 0.

Tout code de sortie non nul signale un problème et la valeur de l’'entier peut être utilisée pour distinguer plusieurs raisons différentes pour l'échec du programme. Un appel à exit(\"message\") ou une instruction assert qui évalue sa condition à False termine le programme avec le code de sortie 1.

On peut utiliser exit avec un entier en argument. comme par exemple exit(42), pour terminer le programme avec un code de sortie de son choix.

Pour cela, on peut appliquer la fonction indice maximum _tableau au tableau suivant [2, 3, 1] et observer le résultat.

>>> indice maximum _tableau([2, 3, 1])

Si le résultat renvoyé par la fonction n’est pas celui qui était attendu, alors le programme est manifestement erroné et il convient de trouver et corriger l'erreur.

Si le résultat est bien celui attendu, comme ici, cela ne signifie pas nécessairement qu’il n’y pas d'erreur.

Le programme peut contenir une erreur qui ne se révélerait que sur d’autres tableaux. Il faut donc effectuer d’autres tests.

Par exemple, comme la spécification de indice_maximum_tableau mentionne le cas particulier du tableau vide, il est intéressant de tester la fonction sur ce cas.

>>> indice _maximum_tableau([])

None

De nombreuses autres situations méritent encore d’être testées, par exemple des cas particuliers où la valeur maximale est située au début ou à la fin du tableau, où encore le cas d’un tableau ne contenant que des entiers négatifs.

"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Plutôt que d’effectuer les tests dans la boucle interactive de Python, une meilleure solution consiste à les inclure dans le même fichier que le programme. En particulier, plutôt que de vérifier visuellement que chaque résultat obtenu est bien celui qui était attendu, on peut faire vérifier ceci par l'interprète Python, par exemple avec la construction assert et un test.

def indice_maximum_tableau(t) :

#Ecrire le code ici

return 1

assert indice_maximum_tableau([2, 3, 1]) == 1

assert indice_maximum_tableau([]) == None

assert indice_maximum_tableau([3, 1, 3, 7]) == 3

assert indice_maximum_tableau([8, 3, 1, 3, 7]) == 0

assert indice_maximum_tableau([-3, -1, -3, -7]) == 1

Ecrire la fonction indic_ maximum_tableau.et tester le code.

Si l’un de ces tests échoue, il faut rectifier le programme. Une fois l'erreur corrigée, il convient de relancer tous les tests, y compris ceux qui avaient

déjà été effectués avec succès.

En effet, en corrigeant une erreur, on peut en introduire une autre. (C’est même assez courant.) Il est donc intéressant d’avoir écrit tous les tests dans le fichier où est définie la fonction indic_ maximum_tableau.

","title":"Inclusion des tests"},{"htm":"","css":"","js":""}],[{"text":"

Pour un test donné, c'est la spécifion qui indique le résultat attendu. On à une situation un peu plus délicate lorsque plusieurs réponses sont correctes. En particulier, que devrait renvoyer la fonction indice__maximum_tableau sur le tableau

[3, 1, 3] où l'élément maximum apparaît deux fois?

La spécification n'indique pas que l’une des deux occurrences doit être préférée à l’autre.

Ainsi, à moins d’être certain que le programme donnera toujours la préférence à la première occurrence, on ne peut écrire le test sous la forme

assert indice_maximum_tableau(([3, 1, 3]) == 0

puisque la réponse 2 serait également acceptable. Dans ce cas nous ne pouvons que vérifier que le résultat obtenu est bien un des resultats admissibles.

On pent le faire de la manière suivante.

m = indice_maximum_tableau([3,1,3])

assert m == 0 or m == 2

Tester votre fonction avec les 2 exemples de test.

","title":"Spécification non déterministe"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

On peut définir de nombreux tests pour un programme donné sur la seule base de sa spécification. Il suffit donc d'avoir décidé ce que devait exactement faire une fonction pour commencer à écrire les tests associés.

En particulier. il est tout à fait imaginable, et c'est même une pratique courante, d'écrire un certain nombre de tests pour une fonction avant même d’avoir écrit le code de cette fonction.

Dans le cas d’un travail en équipe et une fois la spécification décidée en commun, on peut même confier la définition des tests et l'écriture du programme à deux personnes différentes. Cette pratique vise à éviter que le même oubli se glisse à la fois dans le programme et dans les tests et passe ainsi inaperçu.

","title":"Quand définir ses tests?"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

En général on ne peut pas écrire un ensemble de tests exhaustif, qui suffirait à exclure toute erreur. Les entiers de Python, par exemple, sont en nombre infini, de même que les tableaux d’entiers, les chaînes, etc.

Il est donc exclu de tous les tester individuellement. Le mieux qu’on puisse faire a priori est de trouver un « bon » ensemble de tests, qui soit suffisant pour donner une bonne confiance dans le programme testé.

Il est délicat de déterminer à quel moment un ensemble de tests est suffisant. L'objectif est que les tests réunis couvrent tous les «comportements» possibles du programme, ce qui est un concept assez vague.

Voici une liste de points d'usage général à garder en tête et à compléter au cas par cas.

- Si la spécification du programme mentionne plusieurs cas, chacun de ces cas doit faire l’objet d’un test

- Si une fonction renvoie une valeur booléenne, essayer d’avoir des tests impliquant chacun des deux résultats possibles.

- Si le programme s'applique à un tableau, il faut inclure un test couvrant le cas du tableau vide.

- Si le programme s’applique à un nombre, il peut être utile de tester pour ce nombre des valeurs positives, des valeurs négatives, ainsi que Zéro.

- Si le programme fait intervenir un nombre appartenant à un certain intervalle, il peut être utile d'inclure des tests dans lesquels le nombre est aux limites de cet intervalle. En particulier, si le programme fait intervenir un indice d’un tableau, on peut inclure des tests dans lesquels

cet indice sera 0 ou l'indice maximal.

","title":"Bons ensembles de test"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

On n'eflectue que des tests en accord avec cette précondition. Eu effet, lorsque les conditions d'utilisation d'une fonction ne sont pas remplies, la spécification ne dit rien de ce que doit être le résultat

On ne saurait alors déterminer un € résultat attendu » auquel comparer le résultat obtenu.

","title":"Tests et précondition"},{"edit":"

"}],[{"text":"

En plus des critères informels évoqués ici, on

utilise également dans l'industrie quelques critères quantitatifs appelés critères de couverture, mesurant par exemple le pourcentage des instructions du programme qui sont effectivement exécutées lors d'au moins un des tests.

","title":"Critères de couverture"},{"edit":"

"}],[{"text":"

Nous venons d'insister sur la nécessité de tester ses programmes.

Maintenant, nous mettons en œuvre sur un exemple de test sur un programme de tri.

Plus précisément, on suppose que l’on cherche à tester ici une fonction Python tri qui trie un tableau d’entiers, en place, par ordre croissant.

On suppose par ailleurs qu’on n’a pas accès au code Python de cette fonction tri. Elle pourrait avoir été écrite par quelqu'un d'autre, voire même proposée dans un module Python dont nous n’avons pas le code source.

Dans de telles circonstances, on appelle cela un «test en boîte noire», une image qui évoque que la fonction que nous sommes en train de tester est cachée dans une boîte opaque, sans que nous puissions l’observer autrement qu’en l'appelant sur des arguments donnés et en examinant le résultat.

Pour tester notre fonction de tri, on écrit une fonction test qui prend en argument un tableau t, appelle la fonction tri sur ce tableau, puis vérifie que le tableau t est bien trié.

def test(t):

tri(t)

for i in range(0, len(t) - 1):

assert t[i] <= t[i+i]

On utilise ici l'instruction assert pour faire cette vérification. Ainsi, si le tableau n’a pas été trié correctement, l'exécution de la fonction test sera

interrompue avec une exception AssertionError. Avec cette fonction test, on peut commencer à écrire quelques tests élémentaires, sur un tableau vide,

un tableau ne contenant qu’un seul élément, un tableau manifestement non trié, etc.

test([])

test ([1])

test([2, 1])

C’est un bon début. Cependant, notre fonction test est un peu trop naïve. En effet, elle vérifie que le tableau t a bien été trié mais elle omet de vérifier qu’il contient bien les mêmes éléments qu'avant l’appel.

Une fonction tri qui écrirait la valeur 0 dans toutes les cases du tableau passerait les tests !

","title":"Mise en oeuvre des tests"},{"edit":"

"}],[{"text":"

Plus subtilement, une fonction qui ajouterait ou supprimerait un élément pourrait encore passer les tests.

Le cas extrême serait celui d’une fonction qui supprime tous les éléments du tableau :

def tri(t):

t.clear()

Modifions donc la fonction test pour qu’elle vérifie également que les éléments sont toujours les mêmes qu'initialement.

Ce n’est pas complètement évident à réaliser. On peut imaginer faire une copie du tableau t avant d’appeler tri(t) puis vérifier que tout élément de cette copie est dans t et que tout élément de t est dans cette copie.

Malheureusement, c’est là encore un peu naïf. En effet, une fonction tri qui changerait le tableau [2, 1, 1] en le tableau [1, 2, 2] passerait ce test, sans pour autant être correct. Il faut donc vérifier que les éléments sont les mêmes, avec pour chacun le même nombre d’occurrences avant et après.

Il y a de multiples façons de réaliser une telle vérification.

Le programme 14 en propose une, à l’aide d’une fonction occurrences qui construit un dictionnaire à partir des éléments d’un tableau et d’une fonction identiques qui vérifie que deux dictionnaires sont

identiques.

Maintenant que nous disposons d’une fonction test correcte, on peut relancer les trois tests qu’on a faits plus haut mais surtout passer à des tests un peu plus ambitieux. On commence par se donner une fonction qui construit un tableau aléatoire, d’une taille donnée et dont les éléments sont pris dans un intervalle également donné.

On se sert pour cela de la fonction randint de la bibliothèque random.

def tableau_aleatoire(n, a, b):

return [a + randint(0, b - a) for _ in range(n)]

t = tableau_aleatoire(20,-15,15)

print(t)

Enfin, on lance des tests sur des tableaux de différentes tailles et dont les valeurs sont prises dans des intervalles variables.

def test(t) :

print(t)

for n in range(100):

test(tableau_aleatoire(n, 0, 0))

test(tableau_aleatoire(n, - n // 4, n // 4))

test(tableau_aleatoire(n, - 10 * n, 10 * n))

Ici, on fait varier la taille n du tableau entre 0 et 99. En particulier, on teste donc la fonction sur un tableau vide, ce que nous avions fait plus haut explicitement avec test([]).

Par ailleurs, le choix des intervalles n’est pas anodin. Le premier, à savoir 0..0, aura pour effet de tester la fonction de tri sur des tableaux contenant uniquement la valeur 0, c’est-à-dire des valeurs toutes égales.

Cela peut paraître stupide, mais c’est en réalité un très

bon test. Il n’est pas rare qu’un programmeur suppose, inconsciemment ou non, que les valeurs manipulées sont distinctes.

Le deuxième intervalle, à savoir -n//4..n//4 a l'objectif similaire de créer des doublons. En effet, un

tableau de taille 10 dont les valeurs sont comprises entre —3 et 2 contiendra nécessairement des doublons.

Le troisième intervalle est au contraire d’une

amplitude 20 fois supérieure à la taille du tableau, ce qui réduira les collisions.

Enfin, remarquons qu’on a délibérément inclus des valeurs négatives dans ces intervalles. Là encore, c’est pour mieux éprouver la fonction tri. dans le cas où elle ne fonctionnerait correctement que sur des entiers positifs ou nuls.

Programme 14 — Tester une fonction de tri

def occurrences(t):

\"\"\"renvoie le dictionnaire des occurrences de t\"\"\"

d = {}

for x in t:

if x in d:

d[x] += 1

else:

d[x] = 1

return d

def identiques(d1, d2):

\"\"\"test si deux dictionnaires sont identiques\"\"\"

for x in d1:

assert x in d2

assert d1[x] == d2[x]

for x in d2:

assert x in d1

assert d2[x] == d1[x]

def test(t):

\"\"\"teste la fonction tri sur le tableau t\"\"\"

occ = occurrences(t)

tri(t)

for i in range(0, len(t) - 1):

assert t[i] <= t[i+1]

identiques(occ, occurrences(t))

Pour être complet, mentionnons que la fonction tri doit bien entendu terminer, sans quoi elle ne peut être considérée comme correcte. Notre fonction test n’est évidemment pas en mesure de déterminer cela.

On pourrait imaginer interrompre la fonction tri passé

un certain délai, mais cela n’est pas facile à mettre en œuvre, d’une part, et le choix d’un tel délai est délicat, d'autre part. En pratique, on observe que la fonction test ne termine pas et on interrompt le programme (avec un Ctri-C). On en déduit qu’on a trouvé un problème avec la fonction tri.

","title":"Accès aux méthodes de la classe mère."},{"edit":"

"}],[{"text":"

Au delà de la correction, on souhaite le plus souvent vérifier également les performances de nos programmes.

Parfois, la théorie nous permet de prédire les performances (tel algorithme sera linéaire en la taille des données, tel autre quadratique, etc.) mais il n’en reste pas moins une certaine distance entre la théorie et la pratique qu’il peut être intéressant d'évaluer.

Ainsi, on peut connaître précisément la complexité d’un algorithme de tri et pour autant ne pas savoir s’il va permettre de trier un tableau d’un million d’entiers en un temps raisonnable.

Par ailleurs, un programme pourrait avoir passé avec succès tous les tests de correction dont nous avons parlé plus haut et être pour autant victime d’un bug qui

affecte uniquement ses performances.

Pour évaluer les performances d’une fonction ou d’un programme, une méthode simple mais efficace consiste à mesurer son temps d'exécution sur différentes entrées. Pour réaliser une telle mesure, on peut utiliser la fonction perf_counter ou la fonction time de la bibliothèque time.

La première est plus précise que la seconde mais n’est disponible que depuis la version 3.3 de Python.

Ces deux fonctions renvoient le nombre de secondes écoulées depuis un instant de référence (le démarrage de l'ordinateur, le premier janvier 1970 à minuit : heure Unix).

import time

t1 = time.time()

print(t1)

t2 = time.time()

print(t2)

dt = t2 - t1

print(dt)

Tester le code ci-dessus et conclure.

Comme on le constate, cette valeur a une précision en dessous de la seconde.

La valeur proprement dite ne nous intéresse pas vraiment mais la différence entre les deux valeurs renvoyées par time.time() à deux moments différents

nous donne le temps écoulé.

Ainsi, on peut mesurer le temps passé dans l’appel à une certaine fonction tri comme ceci :

t = time.time()

tri(tab)

print(time.time() - t)

Bien entendu, c’est là une mesure relativement grossière du temps, car notre système d’exploitation est multitâche, c’est-à-dire qu'il exécute plusieurs

programmes en même temps.

Néanmoins, si le processeur n’est pas occupé à d’autres programmes demandant beaucoup de calcul,

c'est là une mesure suffisante pour des tests de performance, surtout dès lors que les temps relevés dépassent la seconde.

","title":"Tester les performances"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Plutôt que de mesurer les performances d’un seul appel, il est préférable d'essayer de faire varier les entrées, dans le but de relier la taille de ces entrées avec la mesure du temps d'exécution.

Avec la petite boucle suivante, on mesure la performance d’une fonction tri sur des tableaux dont la taille double à chaque étape.

for k in range(10, 16):

n = 2 ** k

tab = tableau_aleatoire(n, -100, 100)

t = time.time()

tri(tab)

print(n, time.time() - t)

Ici, la fonction tableau_aleatoire est supposée construire un tableau aléatoire de taille n, comme on l’a fait plus haut dans cette section. On note qu’on a pris soin de ne pas mesurer le temps passé dans cette fonction, mais seulement celui passé dans la fonction tri.

On obtient par exemple les chiffres ici donnés à gauche :

n	temps(s)
1024	0.023916959762573242
2048	0.07994365692138672
4096	0.3072216510772705
8192	1.2350132465362549
16384	4.926177501678467
32768	20.367548942565918

$\"\"$

Un tel affichage sur deux colonnes, de la valeur de n d’une part et du temps d'exécution d’autre part, nous facilite la compréhension des performances de notre fonction tri. Ici, on constate immédiatement que, lorsque la valeur de n double, le temps d’exécution fait plus que doubler.

Mieux encore, on observe qu’il quadruple. Il s’agit donc là très probablement d’un algorithme de tri quadratique (comme le tri par insertion). Si la lecture est difficile, on

peut également copier-coller ces valeurs dans un tableur ou plus générale-ment dans un quelconque outil qui saura les analyser ou les afficher.

Ici, on a affiché un graphique construit par l'outil gnuplot à partir de ces valeurs.

","title":" "},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Dans la séquence précédent, nous avons expliqué qu'un objet encapsule un certain nombre d’attributs, avec lesquels on interagit notamment par l'intermédiaire de méthodes. Il n’est pas rare

que ces attributs satisfassent des invariants. En voici quelques exemples :

- un attribut représente un mois de l’année et sa valeur doit être comprise entre 1 et 12;

- un attribut contient un tableau d’entiers représentant un numéro de sécurité sociale et sa taille doit être égale à 13 (et un numéro de sécurité sociale vérifie par ailleurs un certain nombre d’autres invariants) :

- un attribut contient un tableau qui doit être trié en permanence ;

- deux attributs x et y représentent une position sur une grille N x N et se doivent de respecter les inégalités 0 <x<N et 0<y<N;

- etc.

On trouvera dans cet ouvrage d’innombrable exemples de tels invariants, souvent implicites. On a pris ici l'exemple d’attributs, car le principe d’encapsulation nous permet d'espérer pouvoir maintenir ces invariants. Il suffit en effet que le constructeur de la classe les garantisse. par construction ou par vérification, puis que les méthodes qui modifient des attributs maintiennent les invariants. Ainsi, si on est en train de définir une classe C avec deux attributs x et y passés en arguments au constructeur, et que ces deux attributs doivent vérifier un invariant, on commencera par s'assurer que c’est bien le cas.

class C:

def __init__(self, x, y):

if not (...invariant...):

raise ValueError(?’...une explication...’)

self.x = x

self.y = y

On pourrait être tenté de faire confiance à l'utilisateur, mais une programmation défensive est toujours une bonne idée.

De même, si on écrit une méthode qui modifie un ou plusieurs attributs, on peut ajouter une vérification explicite :

def deplace(self):

if ... :

self.x += 1

self.y += 1

assert ...invariant...

Cette fois, il ne s’agit pas de faire confiance à l’utilisateur mais plutôt d’avoir confiance dans notre capacité à programmer correctement. Là encore, une

programmation défensive n’a que des avantages.

Lorsque la vérification d’un invariant commence à être complexe à écrire et/ou coûteuse à exécuter, il peut être une bonne idée de la déporter dans une méthode spécifique.

def valide(self):

vérifie l’invariant

... et lève une exception si besoin ...

Les bénéfices sont nombreux. D'une part, on peut l’invoquer à de multiples endroits, sans avoir à dupliquer le code qui fait la vérification. En particulier,

on limite ainsi le risque d’erreur dans le code qui vérifie l’invariant.

D'autre part, on peut facilement débrancher le test de l’invariant s’il s'avère coûteux, par exemple en ajoutant un simple return tout au début de la méthode valide une fois la classe mise au point. Enfin, on peut avantageusement utiliser une telle méthode pendant le test de notre classe.

Comme on l’a expliqué, le principe d'encapsulation

est également valable pour les modules, dont une partie des données peut être volontairement cachée. Là encore, ces données peuvent être sujettes à des invariants. On peut alors procéder exactement comme avec les objets, en testant l’invariant dynamiquement et/ou en fournissant une fonction valide qui effectue la vérification.

","title":"Invariant de structure :"},{"edit":"

"}],[{"text":"

Pour chacune des fonctions suivantes, proposer un type pour chacun de ses arguments et un type pour son résultat :

def f1(t):

return t[0] + 1

def f2(x):

return str(3.14 x x)

def f3(p):

x, y = p

return 2*x+7y

def f4(s):

s.add(42)

def f5(d, s):

if s != \"toto\":

d[s] += 1

return d[s]

Dans certains cas, il peut y avoir plusieurs solutions.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def f1(t: list) -> int:

def f2(x: float) -> str:

def f3(p: tuple) -> int:

def f4(s: set) -> NoneType:

def f(d: dict, s: str) -> int:

"}],[{"text":"

On suppose avoir écrit une fonction mult(x, y) qui calcule et renvoie le produit de deux entiers x et y reçus en arguments.

L'idée est que cette fonction ne se contente pas d’appeler l'opération * mais réalise un autre algorithme, comme la multiplication russe, la méthode de Karatsuba.

def taille(x):

n=1

while x > 0:

x //= 2

n += 1

return n

def karatsuba(x, y, n):

\"\"\"multiplie x et y par La méthode de Karatsuba\"\"\"

if n <= 1:

return x * y

n //=2

m = 1 << n

a , b = x>>n , x%m

c , d = y>>n , y%m

ac= karatsuba(a, c, n)

bd = karatsuba(b, d, n)

abcd = karatsuba(a - b, c - d, n)

return (ac << (2*n)) + ((ac+bd -abcd) << n) +bd

def mult(x, y):

n = max(taille(abs(x)), taille(abs(y)))

return karatsuba(x, y, n)

print(mult(1000,1000))

Proposer des tests de correction pour cette

fonction mult.

Proposer ensuite des tests de performances.

Tracer la caractéristique et conclure

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Pour ce qui est des tests de correction, une bonne

idée consiste à tester que les multiplications par 0 et par 1 donnent bien les résultats attendus. C’est également une bonne idée d'inclure des valeurs négatives, car il est tout à fait plausible que la fonction mult soit correcte uniquement sur des entiers positifs. Voici de premiers tests tout à fait raisonnables :

from random import randint

#Test de correction

for _ in range(1000):

x = randint(-100, 100)

assert mult(0, x) == 0

assert mult(x, 0) == 0

assert mult(1, x) == x

assert mult(x, 1) == x

y = randint(-100, 100)

assert mult(x, y) == x * y

assert mult(y, x) == x * y

En particulier, la dernière ligne vérifie que la multiplication est bien com-

mutative.

Pour ce qui est des tests de performances, on peut mesure le temps d’exécution de la fonction mult sur deux entiers de n chiffres chacun, pour différente valeur de n. On peut prendre par exemple des valeurs de n qui doublent à chaque étape, c’est-à-dire des puissances de 2.

Pour construire un nombre de n chiffres, on le tire au hasard entre 10^(n-1) et 10^n - 1.

#Test de performance

import time

from random import randint

for k in range(1, 17):

n=2**k

min, max = 10**(n-1),10**n - 1

x = randint(min, max)

y = randint(min, max)

t = time.time()

z = mult(x, y)

print(n, time.time() - t)

En traçant la caractéristique, on voit que le temps d'exécution est à peu près multiplié par 4 lorsque

le nombre de chiffres est multiplié par 2.

Il s’agit donc là d’un algorithme de complexité quadratique (en le nombre de chiffres n), ce qui est la complexité de la méthode naïve ou encore de la multiplication russe.

"}],[{"text":"

Proposer des tests pour tester la fonction miroir(ch) qui prend en argument une chaîne de caractères ch et renvoie la chaîne contenant les caractères de ch en ordre inverse.

def miroir(ch) :

ch2 = \"\"

for lettre in ch :

ch2 = lettre + ch2

return ch2

print(miroir(\"Bonjour\"))

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Il y a plusieurs façons d'écrire une fonction test qui

vérifie le comportement de la fonction miroir sur une chaîne ch donnée. On peut vérifier que la longueur est la même et que les caractères sont bien inversés :

def test(ch):

n = len(ch)

m = miroir(ch)

assert len(m) == n

for i in range(n):

assert m[i] == ch[n - 1 - i]

print(\"test ok\")

test(\"bonjour\")

Il y a une solution plus simple, cependant, car Python nous fournit déjà cette opération de miroir, avec ch[::-1], et il suffit donc de comparer les deux chaînes :

def test(ch):

assert miroir(ch) == ch[::-1]

print(\"test ok\")

test(\"bonjour\")

Pour ce qui est du jeu de tests, maintenant, on se donne une fonction pour

from random import randint

def chaine_aleatoire(n):

return ''.join([chr(randint(65, 90)) for _ in range(n)])

print(chaine_aleatoire(50))

Ici, on a choisi de prendre des caractères entre 'A' et 'Z’ mais il faudrait en toute rigueur tester la fonction miroir sur l’ensemble des caractères UTF-8 (ce que ce peut faire en tirant au hasard un entier entre 0 et Ox10FFFF puis en lui appliquant chr). Enfin, on peut tester avec des chaînes de différentes longueurs :

for n in range(100):

test(chaine_aleatoire(n))

Il est important d'inclure la chaîne vide (longueur 0), ainsi que des chaînes de longueur impaire (la fonction miroir pourrait ne fonctionner correctement que sur des chaînes de longueur paire).

"}],[{"text":"

On suppose qu’une classe portion contient un tableau dans un attribut tab et délimite une portion de ce tableau à l’aide de deux autres attributs deb et fin. La portion s'étend de l'indice deb inclus à l’indice fin exclu.

Écrire une méthode valide

def valide(self):

assert ...

qui vérifie que les attributs deb et fin définissent bien une portion valide du tableau tab.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

assert 0 <= self.deb <= self.fin <= len(self.tab)

#On utilise ici le fait que Python permet de chaîner les

#inégalités :

def valide(self):

assert 0 <= self.deb <= self.fin <= len(self.tab)

"}],[{"text":"

On suppose avoir écrit une fonction retire_com(nomf). Cette fonction ouvre en lecture un fichier dont le nom est donné en argument et qui doit obligatoirement se terminer par l'extension «.py».

Pour un tel fichier « {.py », la fonction crée un nouveau fichier «{_sanscomm.py » qui est une copie du fichier original dont on a retiré tous les commentaires. Si le

fichier de destination existe déjà, il est écrasé.

La fonction renvoie True en cas de succès et False en cas d’erreur.

Lister les conditions sous lesquelles cette fonction peut renvoyer False.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

- L’argument nomf ne se termine pas par « .py ».

- Le fichier nomf n'existe pas.

- Le fichier nomf existe, mais l’utilisateur n’a pas les droits en lecture.

- Le fichier nomf existe, mais c’est un répertoire.

- Le fichier de sortie existe, mais l'utilisateur ne possède pas les droits en écriture sur ce fichier (il ne pourra donc pas écraser son contenu).

- Le fichier de sortie n'existe pas et l'utilisateur n’a pas les droits en écriture sur le répertoire de destination (il ne peut donc pas créer de fichier).

- Le fichier de destination existe et est un répertoire (l’utilisateur ne pourra pas l’écraser).

- (Rare) Le fichier source est un lien symbolique dont la cible n'existe pas.

- (Très Rare) Il ne reste plus assez d'espace disque pour stocker le fichier de sortie.

De façon générale, à part pour la première condition que l’on peut tester facilement avec nomf .endswith(\".py\"}), on ne va pas tester individuellement

toutes les conditions d’erreurs sur les fichiers. Il est plus judicieux d’encadrer les fonctions systèmes par un bloc try except et de rattraper les grandes classes d’exceptions : toutes les erreurs sauf la première et la dernière lèveront l'exception OSError avec un message approprié.

La dernière sera une exception IOError.

"}],[{"text":"

On souhaite que les instances de la classe Chrono ébauchée ci-dessous respectent les invariants de structure suivants : la valeur de l’attribut heures est comprise entre 0 et 23, et les valeurs des attributs minutes et secondes sont comprises entre 0 et 59.

class Chrono:

\"\"\"lune classe pour représenter un temps mesuré en

heures, minutes et secondes\"\"\"

def __init__(self, h, m, s):

self.heures = h

self.minutes = m

self.secondes = s

def avance(self, s):

self.secondes += s

self.minutes += self.secondes // 60

self.secondes = self.secondes % 60

self.heures += self.minutes // 60

self.minutes = self.minutes % 60

Que manque-t-il à ce code pour que ces invariants soient bien toujours valides quoiqu'il arrive?

Le corriger, en précisant au besoin la spécification de

chacune des méthodes.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Le code de la méthode avance prend garde à ne pas

induire de dépassement sur les minutes et les secondes, mais ne gère pas les heures.

On pourrait ajouter une ultime ligne

self.heures = self.heures % 24

à son code, après la dernière ligne actuelle.

Dans ce cas, avancer d’une seconde à partir de 23h 59m 59s amène à 0h 0m 0s.

Notez que cette méthode fonctionne également pour les valeurs négatives de s.

La fonction __init__, elle, ne fait aucune vérification.

On pourrait restreindre son utilisation et imposer qu’elle ne prenne en paramètres que des nombres entiers, pris dans les bons intervalles.

def __init__(self, h: int, m: int, s: int):

if h<0 or h > 23 or m < 0 or m > 59 \\

or s < 0 or s > 59 :

raise ValueError(’heure invalide’)

self.heures = h

....

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 16 Septembre 2020; Mis à jour : 16 Septembre 2020; Clics : 1499

[[{"title":"Python - Programmation objet","posi":0},{"text":"

Nous avons évoqué dans la séquence précédente l'intérêt de définir et identifier certaines structures de données composées de plusieurs éléments, par exemple avec la table de hachage pour laquelle nous avions besoin de mémoriser à la fois un tableau de paquets et un entier représentant le nombre

total d'éléments.

Revenons sur les différents moyens de représenter une telle structure composite en Python.

-Le couple, cas particulier de n-uplet pour n valant 2, permet effectvement de regrouper deux éléments de types distincts mais n’autorise pas la modification des éléments. En l'occurrence on pourrait modifier

le contenu du tableau de paquets (cela ne change pas l'identité de ce tableau) mais pas modifier l’entier représentant la taille.

Le tableau permet de regrouper une séquence d’éléments et autorise la modification, mais nous avons invariablement recommandé de n’en faire qu’une utilisation homogène (un même type pour tous les éléments contenus). Le regroupement d’un tableau et d’un entier est incompatible avec cette discipline.

Les n-uplets nommés sont une approche tout à fait adaptée. Cependant, réaliser un n-uplet nommé à l’aide d’un dictionnaire n’est pas l'approche la plus idiomatique, ni en Python ni dans d’autres langages majeurs, chacun offrant pour cela des mécanismes

plus intégrés.

Le paradigme de la programmation objet, qui est intégré à Python et que nous allons présenter dans cette séquence, fournit une notion de classe, qui

permet à la fois de définir (et nommer) des structures de données composites, et de structurer le code d’un programme.

"},{"text":""}],[{"text":"

Une classe définit et nomme une structure de données qui vient s’ajouter aux structures de base du langage. La structure définie par une classe peut regrouper plusieurs composantes de natures variées. Chacune de ces composantes est appelée un attribut (on dit aussi un champ ou une propriété) et est dotée d’un nom.

","title":"Classes et attributs : structurer les données"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

******

Supposons que l’on souhaite manipuler des triplets d’entiers représentant des temps mesurés en heures, minutes et secondes.

On appellera la structure correspondante Chrono. Les trois nombres pourront être appelés, dans l’ordre, heures, minutes et secondes, et nous pourrions nous figurer le temps «21 heures, 34 minutes et 55 secondes» comme un triplet nommé correspondant à la représentation graphique suivante.

*********

	Chrono
heures	21
minutes	34
secondes	55

Un triplet donné associe ainsi chacun des noms heures, minutes et secondes à un nombre entier. La structure Chrono elle-même peut alors être pensée comme le cas particulier des n-uplets nommés possédant exactement trois composantes nommées respectivement heures, minutes et secondes.

Python permet la définition de cette structure Chrono sous la forme d’une classe avec le code suivant.

class Chrono:

\"\"\"Une classe pour représenter un temps mesuré en

heures, minutes et secondes\"\"\"

def __init__(self, h, m, s):

self.heures = h

self.minutes = m

self.secondes = s

La définition d'une nouvelle classe est introduite par le mot-clé class, suivi du nom choisi pour la classe et du symbole : (deux-points).

Le nom de la classe commence par une lettre majuscule. Tout le reste de la définition est alors placé en retrait.

Nous avons dans cette exemple une chaîne de documentation décrivant la classe et la définition d’une fonction __init__ dont nous détaillerons la construction à la section suivante.

Notons pour l'instant simplement sa forme, à savoir qu’elle possède un premier paramètre appelé self, trois paramètres correspondant aux trois composantes

de notre triplet, ainsi que trois instructions de la forme self.a = ... correspondant de même aux trois composantes (et en l’occurrence, affectant à

chaque attribut sa valeur).

","title":"Description d'une classe"},{"edit":""}],[{"text":"

Une fois une telle classe définie, un élément correspondant à la structure Chrono peut être construit avec une expression de la forme Chrono(h,m,s). On appelle un tel élément un objet où une instance de la classe Chrono.

On peut ainsi définir et affecter à la variable t un objet représentant notre temps « 21 heures, 34 minutes et 55 secondes» avec la ligne suivante.

>>> t = Chrono(21, 34, 55)

Tout s'écrit comme si le nom de la classe était également une fonction attendant trois paramètres et construisant l’élément correspondant.

Notez que, comme c'était le cas pour les tableaux, la variable t ne contient pas à strictement parler l’objet qui vient d’être construit, mais un pointeur vers le bloc de mémoire qui à été alloué à cet objet. La situation correspond donc au schéma suivant.

t[.] +———> Chrono

heures! 21

minutes | 34

secondes] 55

En outre, comme le suggère ce schéma, l’objet mémorise d’une manière ou l’autre son appartenance à la classe Chrono.

","title":"Création d'un objet"},{"edit":""}],[{"text":"

On peut accéder aux attributs d’un objet +de la classe Chrono avec la notation t.a où a désigne le nom de l’attribut visé.

Les attributs, comme les cases d’un tableau, sont mutables en Python : on peut non seulement

consulter leur valeur mais aussi la modifier.

>>> t.secondes

>>> t.secondes = t.secondes + 1

>>> t.secondes

Notez que l’on a parlé dans le paragraphe précédent «d’attribut d’un objet». En effet, bien que les noms des attributs soient attachés à une classe, chaque objet possède pour ses attributs des valeurs qui lui sont propres. C’est pourquoi on parle parfois aussi d’attributs d'instance. Ainsi, chaque objet de la

classe Chrono possède bien trois attributs heures, minutes et secondes, dont les valeurs sont indépendantes des valeurs des attributs de même

nom des autres instances. Les deux définitions

t = Chrono(21, 34, 55)

et u = Chrono(5, 8, 13)

conduisent donc à la situation suivante.

t[e}——{Chrono u[e}——{Chrono

heures | 21 heures 5

minutes 34 minutes 8

secondes 55 secondes 13

Les valeurs des attributs d’un objet pouvant varier, on les comprend parfois comme décrivant l’état de cet objet. Avec ce point de vue, un changement des valeurs des attributs d’un objet correspond alors à l’évolution de cet objet. Une avancée de cinq secondes du chronomètre t mènerait ainsi à la situation suivante.

t{e———\\Chrono Uu|e$+———) Chrono

heures 21 heures 5

minutes 35 minutes 8

secondes 0 secondes 13

Erreurs. Il n’est évidemment pas possible d'obtenir la valeur d’un attribut inexistant.

>>> t.x

Traceback (most recent call last):

File \"<stdin>\", line 1, in <module>

AttributeError: Chrono’ object has no attribute ?x’

De façon plus surprenante, rien n'empêche en Python d’affecter par mégarde une valeur à un attribut n’appartenant pas à la classe de l’objet.

>>> t.x = 89

>>> (t.heures, t.minutes, t.secondes, t.x)

(21, 34, 55, 89)

Voir à ce propos l’encadré « spécificités des attributs en Python » ci-dessous.

","title":"Manipulation des attributs"},{"edit":""}],[{"text":"

La structure des objets en Python ne correspond pas tout à fait à la pratique usuelle de la programmation objet. Dans le paradigme objet habituel, une classe introduit un ensemble d’attributs, définissant la totalité des attributs que possédera chaque instance de cette classe. C’est cette situation que nous décrivons dans cette séquence et que nous utiliserons dans le reste de l’ouvrage.

En Python, cependant, les attributs ne sont pas réellement introduits au niveau de la classe. Plutôt, chaque affectation d'un attribut à un objet crée cet attribut pour cet objet particulier. Dans la terminologie

de Python, ces «attributs» s'appellent ainsi des variables d'instance.

Python permet donc techniquement que deux objets d’une même classe possèdent des attributs n’ayant aucun rapport les uns avec les autres.

Utilisée sans discernement, cette possibilité est évidemment une source inépuisable d'erreurs. Pour rester dans le cadre habituel de la programmation objet, on s'imposera donc la discipline suivante en Python : que chaque objet au moment de sa création se voie doté des attributs prévus pour sa classe, et qu'aucun autre attribut ne lui soit ajouté par la suite.

","title":"Spécificités des attributs en Python"},{"edit":""}],[{"text":"

Une classe peut également définir des attributs de

classe, dont la valeur est attachée à la classe elle-même.

class Chrono:

heure_max = 24

On peut consulter de tels attributs depuis n'importe quelle instance, ou depuis la classe elle-même.

>>> t = Chrono(21, 34, 55)

>>> (t.heure_max, Chrono.heure_max)

(24, 24)

On peut également modifier cet attribut en y accédant via la classe elle-même pour que la modification soit perceptible par toutes les instances présentes ou futures.

>>> Chrono.heure max = 12

>>> t.heure max

En revanche, un tel attribut n’est pas destiné à être modifié depuis une instance (techniquement cela ne ferait que créer une variable d’instance du même nom, pour cette seule instance, qui serait donc décorrélée de

lattribut de classe).

","title":"Attributs de classe"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"title":"Retour sur les tables de hachage"},{"text":"

Le programme 10 utilisait un n-uplet nommé pour regrouper la table des paquets et la taille d’une table de hachage. On utilisera plus couramment à la place une classe munie de deux attributs, dont les valeurs initiales sont fixes et n’ont donc pas besoin d’être passées à la fonction __init__.

class Ensemble:

def __init__(self):

self.taille = 0

self.paquets = [[] for _ in range(32)]

La fonction de création d’une table de hachage vide se contente alors de créer une nouvelle instance de la classe Ensemble.

def cree():

return Ensemble()

On pourrait également adapter chacune des fonctions écrites pour les n-uplets nommés à cette nouvelle organisation de la structure de données. La fonction contient par exemple s’écrirait ainsi.

def contient(s, x):

p = x % len(s.paquets)

return x in s.paquets[p]

Cette manière d'écrire des fonctions manipulant des objets fonctionne parfaitement dans le cadre du programme de terminale. Elle n’est cependant

pas l’usage idiomatique de la programmation orientée objet, que nous allons présenter dans la section suivante.

"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"title":"Méthodes : manipuler les données"},{"text":"

Dans le paradigme de la programmation objet, la notion de classe est souvent associée à la notion d’encapsulation : un programme manipulant

un objet n’est pas censé accéder librement à la totalité de son contenu, une partie de ce contenu pouvant relever du «détail d’implémentation». La manipulation de l’objet passe donc de préférence par une interface constituée de fonctions dédiées, qui font partie de la définition de la classe et sont appelées les méthodes de cette classe.

"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Les méthodes d’une classe servent à manipuler les objets de cette classe.

Chaque appel de méthode peut recevoir des paramètres mais s'applique donc avant tout à un objet de la classe concernée. L'appel à une méthode

texte s'appliquant au chronomètre t et renvoyant une chaîne de caractères.

***********

>>> t.texte()

?21h 34m 555?

Cette notation pour l’appel de méthode utilise la même notation pointée que l'accès aux attributs de t, mais fait apparaître en plus une paire de parenthèses, comme pour l’appel d’une fonction sans paramètres.

Lorsqu'une méthode dépend d’autres paramètres que cet objet principal t, ces autres paramètres paraissent de la manière habituelle, entre les parenthèses et séparés par des virgules. L'appel à une méthode avance faisant avancer le chronomètre t d’un certain nombre de secondes passé en paramètre s'écrit donc comme suit.

>>> t.avance(5)

>>> t.texte()

?21h 35m 0s’

On a déjà rencontré cette notation, par exemple avec tab.append(e) pour ajouter l'élément e à la fin d’un tableau tab. Remarquez également dans cet

exemple qu’une méthode appliquée à l’objet t a la possibilité de modifier les attributs de cet objet.

Lors d’un appel i.m(e1, ..., en) à une méthode m, l'objet à est appelé le paramètre implicite et les paramètres e1 à en, les paramètres explicites.

Toutes les méthodes d’une classe attendent comme paramètre implicite un objet de cette classe. Les paramètres explicites, en revanche, de même que

l’éventuel résultat de la méthode, peuvent être des valeurs Python arbitraires : on y trouvera aussi bien des valeurs de base (nombres, chaînes de caractères, etc.) que des objets.

On peut ainsi imaginer dans notre classe Chrono une méthode egale s'appliquant à deux chronomètres (le paramètre implicite et un paramètre explicite) et testant l'égalité des temps représentés, et une méthode clone

s'appliquant à un chronomètre t et renvoyant un nouveau chronomètre initialisé au même temps que t.

>>> u = t.clone()

>>> t.egale(u)

True

>>> t.avance(3)

>>> t.egale(u)

False

","title":"Utilisation d'une méthode"},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

Comme nous venons de le voir, une méthode d’une classe peut être vue comme une fonction ordinaire, pouvant dépendre d’un nombre arbitraire de paramètres à ceci près qu'elle dait nécessairement avoir pour premier paramètre un objet de cette classe (le paramètre implicite). Une méthode ne peut donc pas avoir zéro paramètre.

La définition d’une méthode d’une classe se fait exactement avec la même notation que la définition d’une fonction. En Python, le paramètre implicite apparaît comme un paramètre ordinaire et prend la première position, les paramètres explicites 1 à n prenant alors les positions 2 à n + 1. Par convention, ce premier paramètre est systématiquement appelé self !.

Ce paramètre étant un objet, notez que l’on va pouvoir accéder à ses attributs avec la notation self.a . Ainsi, les méthodes texte et avance de la classe Chrono peuvent être définies de la manière suivante :

def texte(self):

return (str(self.heures) + 'h '

+ str(self.minutes) + 'm '

+ str(self.secondes) + 's')

def avance(self, s):

self.secondes += s

# dépassement secondes

self.minutes += self.secondes // 60

self.secondes = self.secondes % 60

# dépassement minutes

self.heures += self.minutes // 60

self.minutes = self.minutes % 60

Remarque : Dans d’autres langages de programmation orientée objet, il s'appelle parfois this.

","title":"Définition d’une méthode"},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

Erreurs. Ne pas faire apparaître les parenthèses après un appel de méthode ne déclenche pas l'appel, même si la méthode n’attendait aucun paramètre explicite.

Cet oubli ne provoque pas pour autant une erreur

en Python, l'interprète construisant à la place un élément particulier représentant «la méthode associée à son paramètre implicite». On pourra ainsi observer la réponse suivante si l’on tente un appel incomplet dans

la boucle interactive.

>>> t.texte

<bound method Chrono.texte of <__main__.Chrono object at

0x10d8ac198>>

L’appel n'ayant pas lieu, cet oubli se manifestera en revanche certaine-

ment plus tard, soit du fait que cette valeur spéciale produite n’est pas

le résultat de la méthode sur lequel on comptait, soit plus sournoisement

car l’objet n’a pas été mis à jour comme il aurait dû l’être.

En revanche, utiliser un attribut numérique comme une méthode déclenche cette fois bien une erreur immédiate.

>>> t.heures()

Traceback (most recent call last):

File \"<stdin>\", line 1, in <module>

TypeËrror: ’int’ object is not callable

","title":" "},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

La construction d’un nouvel objet avec une expression comme :

Chrono(21, 34, 55)

déclenche deux choses :

1. la création de l’objet lui-même, gérée directement par l'interprète ou le compilateur du langage,

2. l'appel à une méthode spéciale chargée d’initialiser les valeurs des attributs. Cette méthode, appelée constructeur, est définie par le programmeur.

En Python, il s’agit de la méthode __init__ que nous

avons pu observer dans les exemples.

La définition de la méthode spéciale __init__ ne se distingue en rien de la définition d'une méthode ordinaire : son premier attribut est self et représente l’objet auquel elle s’applique, et ses autres paramètres sont les paramètres donnés explicitement lors de la construction. La particularité de cette méthode est la manière dont elle est appelée, directement par l’interprète Python en réponse à une opération particulière.

","title":"Constructeur"},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

Il existe en Python un certain nombre d’autres méthodes particulières, chacune avec un nom fixé et entouré comme pour __init__ de deux paires

de symboles _. Ces méthodes sont appelées par certaines opérations prédéfinies de Python, permettant parfois d’alléger ou d’uniformiser la syntaxe. Il existe de telles méthodes d'usage général, comme les exemples donnés dans le tableau suivant.

Méthode	Appel	Effet
__str__(self)	str(t)	renvoie une chaîne de caractères
__lt__(self,u)	t<u	renvoie True si t est strictement plus petit que u
__hash__(self)	hash(t)	donne un code de hachage pour t, par exemple pour l'utiliser comme clé d'un dictionnaire d
__len__(self)	len(t)	\| renvoie un nombre entier définissant la taille de t
__contains__(self, x)	x in t	renvoie True si et seulement si x est dans la collection
__getitem__(self, i)	t[i]	renvoie le i-ième élément de t

Remarque : La méthode texte de notre classe Chrono correspond exactement au rôle de la méthode __str__, mais ne bénéficie pas de la syntaxe allégée.

puisque nous n’avons pas utilisé le nom dédié à cela. On pourrait éventuel

lement ajouter la définition suivante.

def __str__(self):

return self.texte()

","title":"Autres méthodes particulières en Python"},{"edit":"

Tester et mettre le résultat ici (code et figure).

"}],[{"text":"

Par défaut, la comparaison entre deux objets avec

== ne considère pas comme égaux deux objets avec les mêmes valeurs pour chaque attribut : elle ne renvoie True que lorsqu'elle est appliquée deux fois au même objet, identifié par son adresse en mémoire.

Pour que cette comparaison caractérise les objets qui, sans être physiquement les mêmes, représentent la même valeur, il faut définir la méthode spéciale

__eq__(self, other)

On peut à cette occasion soit simplement comparer les valeurs de chaque attribut, soit appliquer un critère

plus fin adapté à la classe représentée.

","title":"Égalité entre objets."},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"title":"Classes et espaces de noms","text":"

Deux classes, même définies dans un même fichier, peuvent tout à fait avoir des attributs ou des méthodes

de même nom sans que cela prête à confusion. En effet, on accède toujours aux méthodes et attributs d’une classe via un objet de cette classe (voire dans certains cas via le nom de la classe elle-même) et l’identité de cet objet permet de résoudre toutes les ambiguïtés potentielles.

Ainsi, des noms d’attributs courants comme x ou y pour des coordonnées dans le plan ou des noms de méthodes généraux comme ajoute ou __init__ peuvent être utilisés dans plusieurs classes différentes sans

risque de confusion. On dit qu’une classe définit un espace de noms, c’est-à-dire une zone séparée des autres en ce qui concerne le nommage des variables et des autres éléments.

Attention en revanche, une classe donnée ne peut contenir un attribut et une méthode de même nom.

"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Dans un style de programmation objet ordinaire, l’appel de méthode se fait exclusivement avec la notation pointée t.m(e1, ... , en),

En Python, il reste toutefois possible d'accéder directement à une méthode m d’une classe C et de l’appeler comme une fonction ordinaire. Il faut dans ce cas bien passer le paramètre implicite comme les autres : C.m(t, e1, ..., en).

","title":"Accès direct aux méthodes"},{"htm":"","css":"","js":""}],[{"text":"

On à vu que pouvaient exister des attributs de

classe, dont la valeur ne dépend pas des instances mais est partagée au niveau de la classe entière. De même, la programmation objet connaît une notion de méthode de classe, aussi appelée méthode statique, qui ne s'applique pas à un objet en particulier. Ces méthodes sont parfois pertinentes pour réaliser des fonctions auxiliaires ne travaillant pas directement sur les objets de la classe ou des opérations s'appliquant à plusieurs instances aux rôles symétriques et dont aucune n’est modifiée.

def est_seconde_valide(s):

return 0 <= s and s < 60

def max(t1, t2):

if t1.heures > t2.heures:

return t1

elif t2.heures > t1.heures:

return t2

elif t1.minutes > t2.minutes:

.....

Pour appeler de telles méthodes, on peut utiliser la notation d'accès direct avec le nom de la classe.

>>> Chrono.est_seconde_valide(64) :

False

>>> Chrono.max(t, u)

<__main__.Chrono object at Ox10d8ac198>

Notez que de telles méthodes sont équivalentes à des fonctions qui seraient définies à l’extérieur de la classe. Cette notion n'est donc pas cruciale en Python. Sachez simplement que définir comme ici une méthode sans paramètre self suffit à créer l’effet simple que nous venons de décrire, sans correspondre exactement à la notion de méthode statique de Python.

","title":"Méthodes de classe"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Programme 12 — Une classe pour les ensembles

class Ensemble:

def __init__(self):

self.taille = 0

self.paquets = [[] for _ in range(23)]

def contient(self, x):

return x in self.paquets[x % 23]

def ajoute(self, x):

if not self.contient(x):

self.taille += 1

self.paquets[x % 23].append(x)

def contient_doublon(t):

s = Ensemble()

for x in t:

if s.contient (x):

return True

s.ajoute(x)

return False

Le programme 12 donne une adaptation sous la forme d’une classe du programme 9. Nous profitons de la facilité avec laquelle une classe peut regrouper plusieurs données pour mémoriser la taille de l'ensemble à côté de la table des paquets. Cela permettrait par exemple une définition simple

d’une méthode __len__.

def __len__(self):

return self.taille

Notez que la réalisation de notre structure d'ensemble sous la forme d’une classe demande quelques modifications superficielles de notre fonction

contient_doublon, également incluses dans ce programme :

- l'appel à la fonction cree() est remplacé par un appel au constructeur

Ensemble() ;

- les appels de fonctions contient(s, x) et ajoute(s, x) sont transformés en les appels de méthodes s.contient(x) et s.ajoute(x).

S'il n’est pas envisageable de faire passer ainsi le code client en style objet on peut cependant toujours ajouter, en dehors de la définition de la classe, des fonctions encapsulant ce détail.

def cree():

return Ensemble()

def contient(s, x):

return s.contient(x)

","title":"Une classe pour les ensembles"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

***

Dans la philosophie objet, l'interaction avec les objets d’une classe se fait essentiellement avec les méthodes, et les attributs sont considérés par défaut comme relevant du détail d’implémentation.

Ainsi, concernant la classe Chrono, il est fondamental de savoir que l’on peut afficher et faire évoluer

les temps, mais l'existence des trois attributs heures, minutes et secondes est anecdotique.

En l'occurrence, il serait certainement bienvenu de modifier la structure de cette classe pour simplifier toutes les opérations arithmétiques sur les temps. On pourrait ainsi se contenter d’un unique attribut _temps mesurant le temps en secondes.

class Chrono:

def __init__(self, h, m, s):

self. _temps = 3600*h + 60%xm + s

Les opérations arithmétiques modifieraient alors cet attribut sans besoin de se soucier des dépassements comme c'était le cas dans notre première version de la méthode avance.

def avance(self, s):

self. _temps += s

En contrepartie, nous devons adapter le code de certaines méthodes pour qu’elles assurent la conversion entre les secondes et les triplets «heures,minutes,secondes».

def texte(self):

return (str(self._ temps // 3600) + ’h ?

+ str((self._temps // 60) % 60) + ’m ?

+ str(self. temps % 60) + ?’s’)

Dans certains cas, on pourra introduire également des méthodes qui ne sont pas destinées à faire partie de l’interface. Par exemple ici, on peut ajouter une méthode _conversion qui extrait d’un temps le triplet (h,m,s) correspondant, destinée à être utilisé par les méthodes principale.

Programme 13 — Chronomètre compté en secondes

class Chrono:

def __init__(self, h, m, s):

self._temps = 3600*h + 60*m + s

def texte(self):

h, m, s = self._conversion()

return str(h) + 'h ' + str(m) + 'm ' + str(s) + 's'

def avance(self, s):

self. _temps += s

def egale(self, u):

return self._temps == u._temps

def clone(self):

h, m, s = self._conversion()

return Chrono(h, m, s)

def _conversion(self):

s = self._temps

return (s // 3600, (s // 60) % 60, s % 60)

comme texte et clone.

Le programme 13 donne une version complète de la

classe Chrono qui inclut cette méthode auxiliaire.

Rappelons que la présence de ce symbole _ n’est qu’une déclaration d’intention en Python : il rappelle à un utilisateur extérieur que celui-ci n’est pas censé utiliser la méthode _conversion, sans que rien dans le langage ne l'empêche réellement de le faire.

Notez que, cette remarque étant faite sur la philosophie de la programmation objet, il aurait mieux valu appeler nos trois attributs _heures, _minutes et _secondes dans la première version de la classe Chrono, c’est-à-dire préfixer leur nom d’un symbole _ soulignant leur caractère interne.

En revanche, les méthodes conservent bien, sauf exception, leur nom tel quel : elles forment

******

","title":"Retour sur l'encapsulation"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

``````

La notion d’héritage présentée dans cette section est intégralement hors programme. Cependant, cette notion étant l’un des principaux éléments distinctifs de la programmation orientée objet, il nous faut l’aborder brièvement pour donner une présentation équilibrée de ce paradigme de programmation.

Il est possible de définir une nouvelle classe comme une extension d’une classe existante. Dans ce contexte, la classe d’origine est appelée classe de

base ou classe mère et la nouvelle classe fille. Dans une telle situation d’extension, la classe fille possède automatiquement tous les attributs et méthodes de la classe de base (on dit qu’elle en hérite), et peut en outre ajouter à sa définition de nouveaux attributs et de nouvelles méthodes qui lui sont spécifiques. Il faut comprendre la classe fille comme définissant un cas

particulier de la structure générale décrite par la classe mère. On dit donc aussi que la classe fille est une spécialisation de la classe mère et que la classe

mère est une généralisation de la classe fille.

Ainsi, une structure CompteARebours peut être définie comme un Chrono qui posséderait, en plus de ce qui caractérise un Chrono ordinaire, la capacité de faire évoluer son temps à reculons. La définition à écrire pour cela est la suivante.

class CompteARebours(Chrono) :

def tac(self):

self._temps -= 1

À la première ligne de la définition, le nom de la nouvelle classe suit directement le mot-clé class et le nom de la classe de base est fourni entre parenthèses.

La définition du contenu de la classe ne mentionne ensuite que ce qui est spécifique à la classe fille, ici la nouvelle méthode tac. Toutes les méthodes déjà présentes dans Chrono, comme __init__ et texte, sont

héritées : elles sont présentes sans qu’on les ait mentionnées à nouveau.

>>> c = CompteARebours(0,1,1)

>>> c.tac()

>>> c.texte()

?0h 0m 59s?

Dans une situation d’héritage, une instance de la classe fille possède tous les attributs et méthodes de la classe mère. Il s'ensuit que tout programme destiné à manipuler une instance de la classe mère arrivera tout aussi bien à manipuler une instance de la classe fille : un objet de la classe fille peut être vu comme un objet de la classe mère.

Il se trouve que la spécialisation que représente une classe fille va plus loin que le seul ajout de nouveaux attributs ou de nouvelles méthodes

£££££

être mieux adaptées au cas particulier défini par la classe fille. Pour cela, il suffit de définir à nouveau une méthode du même nom qu’une méthode déjà existante.

On peut par exemple définir dans la classe CompteARebours étendant Chrono une nouvelle version de la méthode texte.

class CompteARebours (Chrono) :

def texte(self):

h, m, s = self._conversion()

return ’plus que ' + str(h) + 'h ' \\

+ str(m) + 'm' + str(s) + 's'

Notez que ce code réalise au passage un appel self._conversion(), qui fait référence à la méthode _conversion héritée de la classe Chrono.

","title":"Héritage"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

. De telles extensions permettent plus de modularité et de réutilisation de code, grâce aux deux effets cumulatifs

suivants :

- D'une part, grâce à l'héritage, toute classe fille bénéficie de l’intégralité du code qui a été écrit pour sa classe mère sans qu'il soit besoin de le réécrire. Cet effet peut être démultiplié lorsque l’on a besoin de créer plusieurs classes qui sont des variantes les unes des

autres : une classe mère peut regrouper tout ce qui est commun aux classes que l’on souhaite définir, puis chacune peut hériter de cette même classe mère et n’ajouter que ce qui lui est spécifique.

- D'autre part, grâce au principe de substitution selon lequel tout objet d’une classe fille peut être utilisé à la place d’un objet de la classe mère, il est possible d'écrire des fonctions polymorphes, c’est-à-dire des fonctions qui s’appliquent à plusieurs types d’objets. En l'occurrence, une fonction attendant en paramètre un objet d’une classe mère pourra également s'appliquer à tout objet de toute classe fille.

","title":"Héritage et réutilisation de code"},{"edit":"

"}],[{"text":"

Il est possible en Python de définir une nouvelle

classe étendant plusieurs autres classes à la fois. La classe fille hérite ainsi des méthodes de tous ses parents, ce qui donne un pouvoir supplémentaire au mécanisme d’héritage.

Notez cependant que tous les langage de programmation objet n'autorisent pas cet héritage multiple, qui pose par ailleurs d’autres questions, notamment pour éviter les ambiguïtés lorsque plusieurs parents définissent des méthodes de même nom.

","title":"Héritage multiple"},{"edit":"

"}],[{"text":"

Lorsqu'une classe fille redéfinit une des méthodes de sa classe mère, il reste toujours possible de faire référence à la version d’origine. On utilise pour cela la fonction spéciale super(), qui donne accès aux méthodes telles que définies dans la classe mère. On peut ainsi faciliter la redéfinition de texte en réutilisant la

version définie dans la classe mère Chrono.

def texte(self):

return ’plus que ' + super().texte()

Techniquement, en Python, cette fonction super renvoie un objet particulier, chargé d’aller chercher dans la classe mère le code des méthodes appelées (en cas d’héritage multiple c’est évidemment un peu plus fin).

Du point de vue des valeurs des attributs, tout se passe en revanche bien comme si le paramètre implicite était self.

En Python, il est également possible d'utiliser un accès direct et de remplacer l’expression super().texte() par Chrono.texte(self).

","title":"Accès aux méthodes de la classe mère."},{"edit":"

"}],[{"text":"

Une exception est une structure de données contenant plusieurs informations, dont généralement un message et un résumé de l’état de la pile d'appels au moment où l’exception a été levée.

Ce sont notamment ces données qui sont affichées lorsqu'un programme est interrompu par une exception.

En Python, cette structure est un objet. Les noms des exceptions sont en réalité des noms de classes, et la ligne

raise ValueError(’indice négatif’)

contient en réalité deux actions : d’abord l'appel du constructeur ValueËrror, créant une instance de la classe éponyme; puis l’interruption du programme avec raise, qui transmet l'instance qui vient d'être créée et qui pourra être manipulée comme l’objet ordinaire qu’elle est dans les blocs alternatifs des constructions

try /except

englobantes.

Pour récupérer et nommer cette instance, on utilise la forme

except ValueError as err:

où le nom fourni après le mot-clé as est un identifiant, de notre choix, définissant une variable locale utilisable uniquement dans ce bloc alternatif.

Ainsi, il est également possible de définir soi-même de nouvelles exceptions avec des noms et attributs sur mesure : il suffit de définir de nouvelles classes étendant la classe Exception de Python.

","title":"La vraie nature des exceptions."},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Définir une classe Fraction pour représenter un nombre rationnel. Cette classe possède deux attributs, num et denom, qui sont des entiers et désignent respectivement le numérateur et le dénominateur.

On demande que le dénominateur soit plus particulièrement un entier strictement positif.

- Écrire le constructeur de cette classe. Le constructeur doit lever une ValueError si le dénominateur fourni n’est pas strictement positif.

- Ajouter une méthode __str__ qui renvoie une chaîne de caractères de la forme \"12 / 35\", ou simplement de la forme \"12\" lorsque le dénominateur vaut un.

- Ajouter des méthodes __eq__ et __it__ qui reçoivent une deuxième fraction en argument et renvoient True si la première fraction représente respectivement un nombre égal ou un nombre strictement inférieur à la deuxième fraction.

- Ajouter des méthodes __add__ et __mul__ qui reçoivent une deuxième fraction en argument et renvoient une nouvelle fraction représentant respectivement la somme et le produit des deux fractions.

- Tester ces opérations.

Bonus : s'assurer que les fractions sont toujours sous forme réduite.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

#On teste la valeur du dénominateur dans le construc-

#teur. Pour le reste, on applique les règles de calcul et on construit une

#nouvelle fraction dans chaque opération arithmétique.

class Fraction:

def __init__(self, n, d):

if d <= 0:

raise ValueError(str(d) + \"n’est pas strictement positif\")

self.num = n

self.denom = d

def __str__(self):

if self.denom == 1 :

return str(self.num)

else :

return str(self.num) + ' / ' + str(self.denom)

def __eq__(self, f):

return self.num * f.denom == f.num * self.denom

def __it__(self, f):

return self.num * f.denom < f.num * self.denom

def __add__(self, f):

return Fraction(self.num*f.denom + f.num*self.denom, self.denom * f.denom)

def __mul__(self, f):

return Fraction(self.num*f.num, self.denom*f.denom)

"},{"solution":"Bonus :

class Fraction:

def __init__(self, n, d):

if d <= 0:

raise ValueError(str(d) + \"n’est pas strictement positif\")

p = pgcd(n, d)

self.num = n //p

self.denom = d // p

#et la fonction auxiliaire pour calculer le PGCD (voir exercice 5 page 16).

def pgcd(a, b):

if b == 0:

return a

return pgcd(b, a % b)

def __str__(self):

if self.denom == 1 :

return str(self.num)

else :

return str(self.num) + ' / ' + str(self.denom)

def __eq__(self, f):

return self.num * f.denom == f.num * self.denom

def __it__(self, f):

return self.num * f.denom < f.num * self.denom

def __add__(self, f):

return Fraction(self.num*f.denom + f.num*self.denom, self.denom * f.denom)

def __mul__(self, f):

return Fraction(self.num*f.num, self.denom*f.denom)

"}],[{"text":"

Définir une classe Intervalle représentant des intervalles de nombres. Cette classe possède deux attributs a et b représentant respectivement l’extrémité inférieure et l'extrémité supérieure de l’intervalle.

Les deux extrémités sont considérées comme incluses dans l'intervalle.

Tout intervalle avec b < a représente l'intervalle vide.

- Écrire le constructeur de la classe Intervalle et une méthode est_vide renvoyant True si l’objet représente l’intervalle vide et False sinon.

- Ajouter des méthodes __len__ renvoyant la longueur de l'intervalle (l'intervalle vide à une longueur 0) et __contains__ testant l’appartenance à l'intervalle.

- Ajouter une méthode __eq__ permettant de tester l'égalité de deux intervalles avec == et une méthode __le__ permettant de tester l'inclusion d’un intervalle dans un autre avec <=.

Attention : toutes les représentations de l'intervalle vide doivent être considérées égales, et incluses dans tout intervalle.

- Ajouter des méthodes intersection et union calculant respectivement l'intersection de deux intervalles et le plus petit intervalle contenant l’union de deux intervalles (l'intersection est bien toujours un intervalle, alors que l’union ne l’est pas forcément). Ces deux fonctions doivent renvoyer un nouvel intervalle sans modifier leurs paramètres.

Tester ces méthodes.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

class Intervalle:

\"\"\"classe pour représenter un intervalle fermé

d’extrémités a et b, considéré vide si b < a\"\"\"

def __init__(self, a, b):

self.a = a

self.b = b

def est_vide(self):

return self.b < self.a

#La longueur d’un intervalle est donnée par la différence entre les bornes,

#avec cas particulier pour l'intervalle vide.

def __len__(self):

return max(0, self.b-self.a)

def __contains__(self, x):

return self.a <= x <= self.b

#Deux intervalles sont égaux s’ils ont les mêmes bornes, ou s’ils sont tous deux

#vides. L’inclusion est déterminée par une comparaison des indices lorsque les

#intervalles sont non vides, mais le cas self vide doit être traité à part.

def __eq__(self, i):

return self.est_vide() and i.est_vide() \\

or self.a == i.a and self.b == i.b

def __le__(self, i):

return self.est_vide() \\

or i.a <= self.a and self.b <= i.b

def intersection(i, j):

return Intervalle(max(i.a, j.a), min(i.b, j.b))

def union(i, j):

return Intervalle(min(i.a, j.a), max(i.b, j.b))

"}],[{"text":"

Définir une classe Angle pour représenter un angle en degrés.

Cette classe contient un unique attribut, angle, qui est un entier. On demande que, quoiqu'il arrive, l'égalité

0<angle<360 reste vérifiée.

Écrire le constructeur de cette classe.

- Ajouter une méthode __str__ qui renvoie une chaîne de caractères de la forme \"60 degrés\".

Observer son effet en construisant un objet de la classe Angle puis en l’affichant avec print.

- Ajouter une méthode ajoute qui reçoit un autre angle en argument (un objet de la classe Angle) et l’ajoute au champ angle de l’objet.

Attention à ce que la valeur d'angle reste bien dans le bon intervalle.

- Ajouter deux méthodes cos et sin pour calculer respectivement le cosinus et le sinus de l’angle.

On utilisera pour cela les fonctions cos et sin de la bibliothèque math.

Attention : il faut convertir l’angle en radians (en le multipliant par π/180) avant d’appeler les fonctions cos

et sin.

Tester les méthodes ajoute, cos et sin.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

#On fait bien attention de maintenir l’angle entre 0 et

#360, dans le constructeur __init__ ainsi que dans la méthode ajoute.

from math import cos, sin, pi

class Angle:

\"\"\"une classe pour représenter un angle en degrés\"\"\"

def __init__(self, a):

self.ansle = a % 360

def __str__(self):

return str(self.angle) + \" degrés\"

def ajoute(self, a):

self.angle = (self.angle + a.angle) % 360

def radians(self):

return self.angle * pi / 180

def cos(self):

return cos(self.radians())

def sin(self):

return sin(self.radians())

#Pour ce qui est de la conversion en radians, on a choisi ici d'ajouter une

#méthode radians, qui a un intérêt en soi. Mais une simple fonction conver-

#tissant des degrés vers des radians conviendrait tout aussi bien.

#Pour tester, on peut utiliser des angles remarquables (0, 30, 45, 60, 90,

#etc.) pour lesquels on connaît la valeur du cosinus et du sinus.

"}],[{"text":"

Définir une classe Date pour représenter une date, avec trois attributs jour, mois et annee.

Ecrire son constructeur.

- Ajouter une méthode __str__ qui renvoie une chaîne de caractères de la forme \"8 mai 1945\". On pourra se servir d’un attribut de classe qui est un tableau donnant les noms des douze mois de l’année.

Tester en construisant des objets de la classe Date puis en les affichant avec print .

- Ajouter une méthode __it__ qui permet de déterminer si une date d1 est antérieure à une date d2 en écrivant d1 < d2. La tester.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

class Date:

\"\"\"lune classe pour représenter une date\"\"\"

def __init__(self, j, m, a):

self.jour = j

self.mois = m

self.annee = a

nom_mois = [\"janvier\", \"février\", \"mars\", \"avril\", \\

\"mai\", \"juin\", \"juillet\", \"août\", \"septembre\", \\

\"octobre\", \"novembre\", \"décembre\"]

def __str__(self):

return str(self.jour) + \" \" + \\

Date.nom_mois[self.mois - 1] +\" \" + \\

str(self.annee)

def __it__(self, d):

return self.annee < d.annee or \\

self.annee == d.annee and (self.mois < d.mois or \\

self.mois == d.mois and self.jour < d.jour)

#Pour cette dernière méthode, il est important de savoir que l’opération and

#a une priorité plus forte que l'opération or.

"}],[{"text":"

Dans certains langages de programmation, comme Pascal ou Ada, les tableaux ne sont pas nécessairement indexés à partir de 0. C’est le

programmeur qui choisit sa plage d’indices.

Par exemple, on peut déclarer un tableau dont les indices vont de -10 à 9 si on le souhaite.

Dans cet exercice, on se propose de construire une classe Tableau pour réaliser de tels tableaux.

Un objet de cette classe aura deux attributs, un attribut premier qui est la valeur de premier indice et un attribut contenu qui est un tableau Python contenant les éléments. Ce dernier est un vrai tableau Python, indexé à partir de 0.

- Écrire un constructeur __init__(self, tmin, tmax, v) où tmin est le premier indice, tmax le dernier indice et v la valeur utilisée pour initialiser toutes les cases du tableau.

Ainsi, on peut écrire

t = Tableau(-10, 9, 42)

pour construire un tableau de vingt cases, indexées de -10 à 9 et toutes initialisées avec la valeur 42.

- Écrire une méthode __len__(self) qui renvoie la taille du tableau.

- Écrire une méthode __getitem__(self, i) qui renvoie l'élément du tableau self d'indice i. De même, écrire une méthode __setitem__(self, i, v) qui modifie l’élément du tableau self d'indice i pour lui donner la valeur v.

Ces deux méthodes doivent vérifier que l’indice i est bien valide et, dans le cas contraire, lever l'exception IndexError avec la valeur de i en argument (c’est-à-dire

raise IndexError(i)).

- Enfin, écrire une méthode __str__(self) qui renvoie une chaîne de caractères décrivant le contenu du tableau.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

class Tableau:

\"\"\"tableau avec une plage d’indices quelconqgue\"\"\"

def __init__(self, imin, imax, v):

self.premier = imin

self.contenu = [v] * (imax - imin + 1)

def __len__(self):

return len(self.contenu)

def __indice_valide(self, i):

if i < self.premier or \\

i >= self.premier + len(self.contenu):

raise IndexError(i)

def __getitem__(self, i):

self._indice_valide(i)

return self.contenu[i - self.premier]

def __setitem__(self, i, v):

self._indice_valide(i)

self.contenu[i - self.premier] = v

def __str__(self):

return str(self.contenu)

"}],[{"text":"

On veut définir une classe TaBiDir pour des tableaux

bidirectionnels, dont une partie des éléments ont des indices positifs et une partie des éléments ont des indices négatifs, et qui sont extensibles aussi bien par

la gauche que par la droite.

Plus précisément, les indices d’un tel tableau bidirectionnel vont aller d’un indice imin à un indice Îmax, tous deux inclus, et tels que imin ≤ 0 et -1≤imax.

Le tableau bidirectionnel vide correspond

AU CAS OÙ imin vaut 0 et imax vaut -1.

La classe TaBiDir a pour attributs deux tableaux Python:

un tableau droite contenant l'élément d'indice 0 et les autres éléments d'indices positifs,

et un tableau gauche tel que gauche[0] contient l'élément d'indice -1 du tableau bidirectionnel, et gauche[1], gauche [2], etc. contiennent les éléments d'indices négatifs suivants, en progressant vers la gauche.

- Écrire un constructeur __init__(self, g, d) construisant un tableau bidirectionnel contenant, dans l’ordre, les éléments des tableaux g et d. Le dernier élément de g (si g n’est pas vide), devra être calé sur l'indice -1 du tableau bidirectionnel, et le premier élément de d (si d n'est pas vide) sur l'indice 0.

Ecrire également des méthodes imin(self) et imax(self) renvoyant respectivement l’indice minimum et l'indice maximum.

- Ajouter une méthode append(self, v), qui comme son homonyme des tableaux Python ajoute l'élément v à droite du tableau bidirectionnel self, et une méthode prepend(self, v) ajoutant cette fois l'élément v à gauche du tableau bidirectionnel self.

Utiliser append sur un tableau bidirectionnel vide place l'élément à l’indice 0. Utiliser prepend sur un tableau bidirectionnel vide place l'élément à l'indice -1.

- Ajouter une méthode __getitem__(self, i) qui renvoie l’élément du tableau bidirectionnel self à l'indice i, et une méthode __setitem__(self, i, v) qui modifie l'élément du tableau self d'indice i pour lui donner la valeur v.

- Ajouter une méthode __str__(self) qui renvoie une chaîne de caractères décrivant le contenu du tableau.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

#Pour obtenir les éléments dans le bon ordre, il faut

#à l’initialisation former l’attribut gauche avec les éléments du paramètre

#g pris dans l’ordre inverse. Dans un cas comme dans l’autre, on travaille

#avec un nouveau tableau et non avec l'original pour éviter les problèmes de

#partage.

class TaBiDir:

def __init__(self, g, d):

self.gauche = g[::-1]

self.droite = d[:]

def imin(self):

return - len(self.gauche)

def imax(se1f) :

return len(self.droite) - 1

#Ceci étant fixé, étendre à gauche ou à droite correspond directement à

#étendre le tableau de gauche ou le tableau de droite.

def append(self, v):

self.droite.append(v)

def prepend(self, v):

self.gauche.append(v)

#Les accès aux éléments sont répartis à gauche ou à droite selon que i est

#positif ou négatif. Attention au décalage des indices dans la partie gauche

#(l'indice -1 du tableau bidirectionnel correspond à l'indice O0 du tableau

#gauche).

def __getitem__(self, i):

if i >= 0:

return self.droite[i]

else:

return self.gauche[-i-1]

def __setitem__(self, i, v):

if i >= 0:

self.droite[i] = v

else:

self.gauche[-i-1] = v

#Pour __str__, on réutilise ici la méthode __str__ des tableaux de Py-

#thon pour avoir directement la présentation avec éléments séparés par des

#virgules, mais il faut ajouter un peu de découpage/collage pour retirer un

#crochet de chaque côté et séparer les deux parties par une virgule.

def __str__(self):

return str(self.gauche[::-1])[0:-1] + ', ' \\

+ str(self.droite)[1:]

"}],[{"text":"

Nous allons illustrer la programmation orientée objet sur un mini-projet inspiré du jeu des lemmings. Dans ce jeu, les lemmings marchent dans une grotte représentée par une grille à deux dimensions dont

chaque case est soit un mur soit un espace vide, un espace vide pouvant contenir au maximum un lemming à un instant donné.

Les lemmings apparaissent l’un après l’autre à une position de départ, et disparaissent lorsqu'ils atteignent une case de sortie. Chaque lemming a une coordonnée verticale et une coordonnée horizontale désignant la case dans laquelle il se trouve, ainsi qu’une direction (gauche ou droite). Les lemmings se déplacent à tour

de rôle, toujours dans l’ordre correspondant à leur introduction dans le jeu, de la manière suivante :

- si l’espace immédiatement en-dessous est libre, le lemming tombe d’une case ;

- sinon, si l’espace immédiatement devant est libre (dans la direction du lemming concerné), le lemming avance d’une case;

- enfin, si aucune de ces deux conditions n’est vérifiée, le lemming se retourne.

On propose pour réaliser un petit programme permettant de voir évoluer une colonie de lemmings une structure avec une classe Lemming pour les

lemmings, une classe Case pour les cases de la grotte, et une classe principale Jeu pour les données globales.

La classe principale Jeu contient un attribut grotte contenant un tableau à deux dimensions de cases, et un attribut lemmings contenant un tableau des lemmings actuellement en jeu.

Son constructeur initialise la grotte, par exemple à partir d’une carte donnée par un fichier texte d’un format inspiré du suivant, où # représente un mur, où les lemmings apparaissent au niveau de la case vide de la première ligne, et D représente la sortie.

# ################

# # #

##### ###########

# # # #

# ###########. #

#. D

######## ########

#. #.

####

Cette classe fournit notamment les méthodes suivantes:

- affiche(self) affiche la carte avec les positions et directions de tous les lemmings en jeu;

- tour(self) fait agir chaque lemming une fois et affiche le nouvel état du jeu;

- demarre(self) lance une boucle infinie attendant des commandes de l'utilisateur.

Exemples de commandes : 1 pour ajouter

un lemming, q pour quitter, et Entrée pour jouer un tour.

- Une classe Lemming avec des attributs entiers positifs 1 et c indiquant la ligne et la colonne auxquelles se trouve le lemming, et un attribut valant 1 si le lemming se dirige vers la droite et -1 si le lemming se

dirige vers la gauche. Il sera aussi utile d’avoir un attribut j pointant sur l'instance de la classe Jeu pour laquelle le lemming a été créé, pour accéder au terrain et à la liste des lemmings.

Cette classe fournit en outre les méthodes suivantes :

- __str__(self) renvoie '>' ou '<' selon la direction du lemming ;

- action(self) déplace ou retourne le lemming ;

- sort(self) retire le lemming du jeu.

- La classe Case contient un attribut terrain contenant le caractère représentant la caractéristique de la case (mur, vide, sortie), et un attribut lemming contenant l’éventuel lemming présent dans cette case

et None si la case est libre. Cette classe fournit notamment les méthodes

- __str__(self) renvoie le caractère à afficher pour représenter cette case ou son éventuel occupant ;

- libre(self) renvoie True si la case est peut recevoir un lemming (elle n’est ni un mur, ni occupée) ;

- depart(self) retire le lemming présent ;

- arrivee(self, lem) place le lemming lem sur la case, ou le fait sortir du jeu si la case était une sortie.

Cette base peut ensuite évidemment être étendue avec des terrains plus variés, de nouvelles possibilités d’interaction pour le joueur, des objectifs en termes de nombre de lemmings sauvés, etc.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

#Dans les cases, on utilise comme dans le plan le

#caractère ? ? pour représenter une case vide, *#’ un mur et ?0? une sortie.

#Dans la méthode __str__ on renvoie, le cas échéant, la représentation du

#lemming présent plutôt que la représentation du terrain lui-même.

class Case:

def __init__(self, char):

self.terrain = char

self.lem = None

def __str__(self):

if self.lem is not None:

return str(self.lem)

else:

return self.terrain

def libre(self):

return (self.terrain == ' ' or self.terrain == '0') \\

and self.lem == None

def depart(self):

self.lem = None

def arrivee(self, lem):

if self.terrain == '0':

lem.sort()

else:

self.lem = lem

#Dans la classe Lemming on introduit une méthode additionnelle

#deplacement (self, 1, c) qui tente de déplacer le lemming vers la case

#de coordonnées (1, c) : si la case est libre le lemming est effectivement dé-

#placé et l’appel renvoie True ; si la case n’est pas libre le lemming ne bouge

#pas et la méthode renvoie False. La méthode action tente alors à l’aide

#de cette méthode de faire tomber le lemming, puis de le faire avancer, et

#enfin le retourne seulement si aucun des deux mouvements n’a eu liou.

#La méthode deplace peut modifier le contenu des cases du jeu, et la méthode

#sort va modifier le tableau lemmings du jeu.

class Lemming:

def __init__(self, j, l, c):

self.j = j

self.l = l

self.c = c

self.d = 1

def __str__(self):

if self.d > 0:

return '>'

else:

return '<'

def deplacement (self, l, c):

if not self.j[l][c].libre():

return False

self.j[self.l][self.c].depart()

self.j[l][c].arrivee(self)

return True

def action(self):

if self.deplacement(self.l+1, self.c):

self.l += 1

elif self.deplacement(self.l, self.c + self.d):

self.c += self.d

else:

self.d = -self.d

def sort(self):

self.j.lemmings.remove(self)

#Pour simplifier l'accès aux cases de la grotte dans les autres classes, on inclut

#une méthode __getitem__ permettant d'accéder à la ligne d'indice i de la

#grotte directement à partir d’une instance j avec la notation j[i]. On a

#également isolé le code responsable de l’introduction d’un nouveau lemming

#dans une méthode à part. Notez dans la méthode tour que la boucle n’est

#pas faite directement sur le tableau lemmings mais sur une copie de ce

#tableau. En effet, des lemmings sont susceptibles d’être retirés du tableau

#lemmings au cours de l’itération sur ce même tableau, ce qui causerait des

#problèmes.

class Jeu:

def __init__(self, nom_de_carte):

carte = open(nom_de_carte)

self.grotte = [[Case(char) for char in ligne

if char != '\\n']

for ligne in carte.readlines()]

carte.close()

self.lemmings = []

def __getitem__(self, i):

return self.grotte[i]

def affiche(self):

for ligne in self.grotte:

for case in ligne:

print(case, end='')

print()

print ('\\n')

def ajoute_lemming(self) :

if self.grotte[0][1].libre():

lem = Lemming(self, 0, 1)

self.lemmings.append(lem)

self.grotte[0][1].arrivee(lem)

def tour(self):

for lem in self.lemmings[:]:

lem.action()

def demarre(self):

while True:

cmd = input()

if cmd == 'q':

break

elif cmd == 'l':

self.ajoute_lemming()

else:

self.tour()

self.affiche()

#Enfin, il suffit pour jouer de créer une instance du jeu en lui fournissant le

#nom d’un fichier texte contenant la carte d’une grotte et appeler sa méthode

#de démarrage.

Jeu('carte.txt').demarre()

"}],[{"text":"

Nous allons illustrer la programmation orientée objet sur un mini-projet de jeu de course. Des tortues font la course en se déplaçant à tour de rôle sur un circuit en deux dimensions matérialisé par une grille dont certaines cases sont passables et d’autres non.

Les tortues ne sont pas très maniables et leurs capacités d'accélération, de décélération et de changement de direction sont limitées : pour déterminer les mouvements possibles à un tour on reproduit depuis la position courante de la tortue le mouvement du tour précédent, et on a ensuite le droit de décaler le point d’arrivée d’au plus une case.

Pour l'affichage, on propose d’utiliser le module turtle de Python. Sachez que ce module définit une classe Turtle, dont chaque instance donne une tortue indépendante. Ces tortues sont ensuite manipulées

avec les opérations habituelles, qui sont en réalité des méthodes.

from turtle import Turtle

t1 = Turtle()

t2 = Turtle()

t1.left(84)

t1.forward(60)

t2.left(18)

t2.forward(90)

Ainsi les instructions créent donc deux tortues t1 et t2 animées indépendamment. En l’occurrence, chacune opère une rotation puis avance, pour représenter ensemble les deux aiguilles d’une horloge qui afficherait midi douze.

On propose de réaliser un tel jeu en utilisant trois classes :

- une classe principale Jeu contenant les tortues et le terrain et animant les tortues à tour de rôle, une classe Tortubolide représentant une tortue de course, et

une classe Vecteur permettant de manipuler des couples de coordonnées.

On peut réaliser le jeu en deux étapes :

1. Dans une première étape, permettre aux tortues de se déplacer librement sur un terrain vierge.

- La classe Vecteur est réalisée intégralement à cette étape, avec deux attributs x et y représentant des coordonnées entières dans le plan cartésien à deux dimensions et des méthodes __eq__,

_-add__ et __sub__ permettant des comparaisons et manipuations arithmétiques de base.

- La classe Tortubolide comporte à cette étape trois attributs : un vecteur donnant les coordonnées de la tortue, un vecteur donnant sa vitesse (le vecteur allant de la position précédente à la position actuelle), et une instance de la classe Turtle destinée à afficher le parcours de cette tortue de course.

Les tortues ont une vitesse initiale nulle, c’est-à-dire égale à Vecteur(0, 0).

Cette classe fournit une méthode action(self, acc) qui modifie la vitesse actuelle de la tortue en lui ajoutant le vecteur acc puis déplace la tortue en ajoutant son vecteur vitesse à son vecteur position.

Lors du déplacement, la méthode trace à l'écran le trajet suivi et à position d'arrivée.

- La classe Jeu possède en attribut une ou plusieurs tortues de course, et définit une méthode demarre lançant la boucle de jeu attendant les commandes du ou des joueurs. Par exemple :

’s' pour conserver le mouvement tel quel,

’z', 'x', 'q', ’d’ pour ajuster le déplacement d’une case, respectivement vers le haut, le bas, la gauche, la droite, et ’fin’ pour quitter le jeu.

2. Dans une deuxième étape on ajoute les murs entourant le circuit, que les tortues de course ne peuvent pas franchir. On apporte alors les modifications suivantes.

- La classe Jeu contient comme nouvel attribut un tableau à deux dimensions indiquant quelles cases sont ou non franchissables.

Cet attribut peut être initialisé à partir d’un dessin du circuit donné dans un fichier texte. Au démarrage du jeu, on dessine l'intégralité du circuit dans la fenêtre turtle avant d'y inclure les tortues de course (dont les coordonnées de départ peuvent de même être données dans le fichier décrivant le circuit, par exemple sur les premières lignes).

- La classe Tortubolide a besoin d’une méthode action enrichie, dans laquelle le déplacement d'une tortue est arrêté par un mur qu’elle tenterait de franchir.

On cherchera à obtenir le comportement suivant :

- si la trajectoire de la tortue doit traverser un mur, alors la tortue est arrêtée sur la case précédant immédiatement ce mur et sa vitesse est réduite à zéro. Pour pouvoir réaliser cette méthode, il faudra ajouter aux attributs de Tortubolide l'instance du jeu en cours.

Cette base peut ensuite être étendue, par exemple en faisant en sorte que les tortues concurrentes soient également des obstacles ou que les collisions imposent des pénalités plus sévères au redémarrage, en enrichissant le circuit, ou en améliorant l'interface graphique. Dans certaines de ces extensions,

il pourra être pertinent d'ajouter des classes, par exemple une classe Case comme dans l'exercice précédent.

Ci-dessous, un exemple de fichier décrivant un circuit et les coordonnées de départ de deux tortues de course.

########################

### ###

# ##

# ############ ##

# ## ## #

# ############# #

# #

## ##

##############################

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

#On utilise le module turtle pour l'affichage, le module

#sys pour sa fonction exit et le module math pour décomposer le mouvement

#des tortues. On définit deux constantes globales : ECHELLE pour la longueur

#du côté d’une case en pixels et TANPI8 (tangente de ?) qui servira pour

#calculer les déplacements des tortues.

import turtle

import sys

import math

ECHELLE = 12

TANPI8 = math.tan(math.pi / 8)

#La classe vecteur applique les opérations de base coordonnée par coordonnée.

class Vecteur:

def __init__(self, x, y):

self.x = x

self.y = y

def __add__(self, v):

return Vecteur(self.x + v.x, self.y + v.y)

def __sub__(self, v):

return Vecteur(self.x - v.x, self.y - v.y)

def __eq__(self, other):

return self.x == other.x and self.y == other.y

#Classe Tortubolide : on utilise une méthode auxiliaire pour le déplacement,

#qui décompose le mouvement total en une suite de mouvements d’une case

#horizontaux, verticaux ou diagonaux. Cette décomposition permet d’arrêter

#la tortue sur la case précédent un mur, le cas échéant.

class Tortubolide:

def __init__(self, pos, couleur, jeu):

self.pos = pos

self.vit = Vecteur(0, 0)

self.jeu = jeu

self.t = turtle.Turtle()

self.t.up()

self.t.goto(pos.x*ECHELLE, pos.y*ECHELLE)

self.t.down()

self.t.hideturtle()

self.t.color(couleur)

def dessine(self) :

self.t.goto(self.pos.x*ECHELLE,

(self.pos.y - 0.5)*ECHELLE)

self.t.begin_fill()

self.t.circle(ECHELLE/2)

self.t.end_fill()

self.t.goto(self.pos.x*ECHELLE, self.pos.y*ECHELLE)

def action(self, acc):

self.vit += acc

self.avance_aux(self.vit)

self.t.goto(self.pos.x*ECHELLE, self.pos.y*ECHELLE)

self.dessine()

def avance_aux(self, v):

if v == Vecteur(0, 0):

return

dx = 0 if abs(v.x) < TANPI8*abs(v.y) \\

else 1 if v.x > 0 else -1

dy = 0 if abs(v.y) < TANPI8*abs(v.x) \\

else 1 if v.y > 0 else -1

dv = Vecteur(dx, dy)

if self.jeu[self.pos + dv]:

self.vit = Vecteur(0, 0)

else:

self.pos += dv

self.avance_aux(v - dv)

#Outre les méthodes de dessin et la boucle principale du jeu, on à inclut dans

#la classe Jeu une méthode __getitem__ recevant en paramètre un vecteur

#v et indiquant si la case dont les coordonnées correspondent à ce vecteur est

#un mur.

class Jeu:

def __init__(self, nom_de_carte):

carte = open(nom_de_carte)

self.x1 = int(carte.readline())

self.y1 = int(carte.readline())

self.x2 = int(carte.readline())

self.y2 = int(carte.readline())

self.murs = [[char == '#' for char in ligne]

for ligne in carte.readlines()]

carte.close()

self.tortubolides = []

def __getitem__(self, v):

return self.murs[-v.y-1][v.x]

def dessine_circuit(self):

hauteur = len(self.murs)

largeur = len(self.murs[0])

turtle.setup(largeur*ECHELLE, hauteur*ECHELLE)

turtle.setworldcoordinates(-ECHELLE, -ECHELLE,

(largeur+1)*ECHELLE,

(hauteur+1)*ECHELLE)

turtle.hideturtle()

turtle.speed(0)

for x in range(largeur) :

for y in range(hauteur):

if self.murs[-y-1][x]:

Jeu.carre(x*ECHELLE, y*ECHELLE)

def ajoute_tortubolide(self, x, y, couleur):

b = Tortubolide(Vecteur(x, y), couleur, self)

self.tortubolides.append(b)

b.dessine()

def demarre(self):

self.dessine_circuit()

self.ajoute_tortubolide(self.x1, self.y1, 'orange')

self.ajoute_tortubolide(self.x2, self.y2, 'purple')

while True:

for tortubolide in self.tortubolides:

cmd = input()

if cmd == 'fin':

sys.exit(0)

elif cmd == 's':

tortubolide.action(Vecteur(0, 0))

elif cmd == 'q':

tortubolide.action(Vecteur(-1, 0))

elif cmd == 'z':

tortubolide.action(Vecteur(0, 1))

elif cmd == 'd':

tortubolide.action(Vecteur(1, 0))

elif cmd == 'x':

tortubolide.action(Vecteur(0, -1))

else:

tortubolide.action(Vecteur(0, 0))

def carre(x, y):

d = ECHELLE/2

turtle.up()

turtle.goto(x-d, y-d)

turtle.down()

turtle.begin_fill()

turtle.goto(x+d, y-d)

turtle.goto(x+d, y+d)

turtle.goto(x-d, y+d)

turtle.goto(x-d, y-d)

turtle.end_fill()

#Il n’y a plus qu’à démarrer un jeu créé avec un circuit au choix.

Jeu('carte2.txt').demarre()

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 15 Septembre 2020; Mis à jour : 15 Septembre 2020; Clics : 3087

[[{"title":"Python - Modularité","posi":0},{"text":"

Le développement d’un grand programme demande une certaine organisation, et en particulier un découpage des différents aspects du programme

et des différentes tâches qui doivent être accomplies. Ceci est d'autant plus vrai lorsque plusieurs personnes participent au développement.

Parmi ces questions relevant du génie logiciel (« génie », au sens d’ingénierie), nous nous intéressons dans cette séquence à la manière dont les différentes parties

d’un programme peuvent s’articuler.

L’un des objectifs consiste à spécifier le rôle de chaque partie suffisamment précisément pour que chacune puisse ensuite être réalisée indépendamment des autres.

"},{"text":""}],[{"text":"

Lorsque l'on réunit 23 personnes, ii y a une chance sur deux pour que deux d'entre elles soient nées le même jour. Ce résultat est appelé le paradoxe des anniversaires.

Ci-dessous, nous avons le programme qui le vérifie expérimentalement. Celui-ci permet de tirer 1000 fois aléatoire 23 dates d'anniversaire, c'est-à-dire 23 entiers entre 1 et 365.

De cette manière, vous allez observer combien de fois au moins deux personnes sont nées le même jour.

Le programme est le suivant :

from random import randint

def contient_doublon(t) :

s = set()

for x in t:

if x in s:

return True

s.add(x)

return False

nb_personnes = 23

nb_tirages = 1000

ok = 0

for __ in range(nb_tirages) :

if contient_doublon([randint(1,365) for __ in range(nb_personnes)]) :

ok += 1

print(\"nb doublons : \",ok)

Tester le code ci-dessus et en déduire si le paradoxe des anniversaires est vérifié expérimentalement.

Ce programme, consiste à remplir un tableau de taille 23 avec les dates d'anniversaire tirées au hasard puis à vérifier si ce tableau contient au moins un doublon à l'aide de la fonction contient_doublon().

Celle-ci passe tous les éléments en revue et les stocke à la volée dans un ensemble s, jusqu’à trouver un élément déjà présent dans cet ensemble, c'est-à-dire qui apparaissait déjà plus tôt dans le tableau t.

Nous allons voir différente manière pour écrire la fonction contient_doublon()

","title":" Variations sur les ensembles"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Si nous utilisions un simple tableau pour s comme dans

le programme 1. L'opération append est efficace. Le problème vient seulement du test x in s dont le temps d'exécution est le plus souvent proportionnel au nombre d'éléments stockés dans s.

Nous pouvons améliorer cela avec une recherche dichotomique si le tableau est trié, Mais pour trié le tableau s, il faudra insérer les éléments au bon endroit et décaler tous les suivants. Le coût de cette méthode est proportionnel au nombre d'éléments dans le tableau.

Nous allons utiliser une autre approche pour laquelle le coût du test est minimal.

Regarde le programme 2, Alice, nous créons un grand tableau de booléens, un pour chaque date possible.

Nous décidons que s{x] vaut True si nous avons enregistré x et False sinon.

Programme 1 — rechercher un doublon dans un tableau

def contient_doublon(t):

\"\"\"Le tableau t contient-il un doublon ?\"\"\"

s = []

for x in t:

if x in s:

return True

s.append(x)

return False

Programme 2 — rechercher un doublon dans un tableau

def contient_doublon(t):

\"\"\"Le tableau t contient-il un doublon ?\"\"\"

s = [False] * 367

for x in t:

if s[x]:

return True

s[x] = True

return False

L'inconvénient de cette méthode, c'est de prendre un tableau de 366 cases pour utiliser que 23 éléments.

","title":"Deux approches rudimentaires"},{"edit":""}],[{"text":"

Il est dommage que les booléens occupent autant d'espace en mémoire que des nombres entiers (au moins 8 octets, 64 bits!), alors qu’un seul bit est réellement utile pour choisir entre les deux valeurs True ou False. le tableau s du programme 2 est 64 fois trop grand!

Nous allons compacter cela en utilisant des entiers pour représenter plusieurs booléens. En effet, la représentation des entiers en machine est une suite de bits (0 ou 1!) basée sur leur écriture en base 2. De plus, il existe des opérations arithmétiques classiques qui

agissent directement sur cette représentation binaire.

Par exemple, l’opéra-tion | de « ou » bit à bit renvoie l’entier pour lequel chaque bit vaut 1 dès lors

qu’il valait 1 dans au moins l’un des paramètres : si je prends 40 qui s'écrit en binaire 101000 et 10 qui s’écrit en binaire 1010 (ou 001010 si j'ajoute

des zéros pour avoir le même nombre de chiffres), l'opération 40 | 10 me renvoie l’entier dont l'écriture binaire est 101010, c’est-à-dire 42.

Nous considérons un entier s de 64 bits représente par un tableau b de 64 booléens, dont la clé de lecture.b[x] vaut True si et seulement si le bit de rang x de s vaut 1.

Ainsi l’entier 26, qui s’écrit en binaire 0...011010, représente le tableau de booléens (False, True, False, True, True, False, ..., False], autrement dit l’ensemble {1,3,4}. Alors je peux utiliser l’entier 2, qui a tous

ses bits à 0 sauf le bit de rang x qui vaut 1, comme révélateur.

On calcule 2x avec l'opération de décalage 1 << x. Si je fais un « ou » bit à bit s | ( 1 << x) je fais passer le bit de rang x de s à 1 (et il y reste s'il y était déjà). Si en revanche je fais un «et » bit à bit s & (1 << x) j'obtiens soit 2x si b{x] vaut True, soit 0 sinon. Avec ces ingrédients, on pourrait obtenir le programme 3. En plus, c’est particulièrement facile à écrire en Python,

les entiers n'étant même pas limités à 64 bits.

De plus, sans ces entiers illimités on pourrait aussi utiliser un tableau d’entiers ordinaires. On décompose x sous la forme x = i + 64j avec les opérations

de quotient et de reste de la division entière et on fait correspondre à x le bit de rang i de l’entier d'indice j.

Le code s'exécute aussi vite, et on gagne un facteur 64 en occupation de la mémoire par rapport au tableau de booléens.

Pour notre cas d'application effectivement il suffirait alors d’un tableau de six entiers pour représenter n'importe quel ensemble de dates d'anniversaires, comme dans le programme 4. Dans ce cas précis, cela m'a l'air d’être imbattable.

Cependant, si on ne parle plus de jours de l’année et que l’amplitude des éléments auxquels on s’intéresse est bien plus grande que l'intervalle [1,366], ce facteur 64 gagné finira par devenir dérisoire. »

Programme 3 — rechercher un doublon dans un tableau

def contient_doublon(t):

\"\"\"Le tableau t contient-il un doublon ?\"\"\"

s = 0

for x in t:

if s & (1 << x) != 0:

return True

s = s | (1 << x)

return False

Programme 4 — rechercher un doublon dans un tableau

def contient_doublon(t):

\"\"\"le tableau t contient-il un doublon ?\"\"\"

s = [0] * 6

for x in t:

if s[x // 64] & (1 << (x % 64)) != 0:

return True

s[x // 64] = s[x // 64] | (1 << (x % 64))

return False

","title":"Représentation plus compacte : le tableau de bits"},{"edit":""}],[{"text":"

La représentation des ensembles développée dans les programmes 3 et 4 donne les idées essentielles de la

structure de tableau de bits (en anglais bit array ou bit set).

Cette structure donne une représentation compacte d’un ensemble de booléens. Elle permet donc une meilleure utilisation des ressources de mémoire limitées comme la mémoire cache, cette mémoire accessible

beaucoup plus rapidement que la mémoire vive de l’ordinateur et conservant temporairement les derniers éléments consultés.

","title":"Structure de tableau de bits"},{"edit":""}],[{"text":"

L'avantage du programme 1 qui stockait directement les éléments dans le tableau s était d’avoir un tableau dont la taille correspondait au nombre d'éléments présents. L’inconvénient en était que chaque élément pouvait se trouver n’importe où dans le tableau.

À l'inverse, dans le programme 2 et ses dérivés, il était immédiat de trouver la case du tableau liée à un élément donné, mais il fallait pour cela utiliser un tableau bien trop grand.

Peut-on combiner les avantages de ces deux méthodes ?

Prendre par exemple un tableau de 23 cases, puisque pour l'application au paradoxe des anniversaires c’est le nombre d'éléments que l’on est susceptible de stocker dans notre ensemble, dans lequel chacune des 366 dates est liée a priori à une et une seule de ses cases ?

Programme 5 — rechercher un doublon dans un tableau

def contient_doublon(t):

\"\"\"Le tableau t contient-il un doublon ?\"\"\"

s = [[] for __ in range(23)]

for x in t:

if x in s[x % 23]:

return True

s[x % 23].append(x)

return False

C’est cela. Nous pourrions par exemple, s’il faut enregistrer l’entier x, le placer dans la case d'indice x % 28.

Mais que faire si l’on doit stocker deux éléments associés à la même case ? Par exemple 24 et 47?

On pourrait stocker dans la case s[i] un tableau contenant tous les éléments x enregistrés tels que x % 23 vaut i. Voir le programme 5.

Je comprends, nous avons un maximum de 23 éléments à répartir entre 23 petits tableaux (appelons ces derniers des paquets). Chacun des 23 paquets sera quasiment vide. Même sans la moindre organisation des éléments à l’intérieur de chaque paquet le coût des tests x in s[x % 23] sera en général négligeable. Nous perdrions en efficacité seulement si de nombreux

éléments se retrouvaient aiguillés par malchance dans le même paquet, mais la situation est extrêmement peu probable. Ici en l'occurrence, tous les jours de naissance étant à peu près également probables, la répartition dans les différents paquets a les meilleures chances d’être équitable.

— Et on peut toujours imaginer sinon une fonction de répartition qui mélange convenablement les éléments, en évitant que deux dates similaires se trouvent systématiquement envoyées dans le même paquet. Avec un peu d’arithmétique on devrait certainement pouvoir arranger cela. En revanche, peut-on adapter l’idée si l’on ne connaît pas à l’avance le nombre d’éléments ?

— On pourrait partir d'un nombre de paquets arbitraire, et agrandir le tableau s lorsque l’on commence à avoir trop d’éléments par rapport au nombre de paquets. On peut tenter une nouvelle version de notre programme. »

Factorisation du code

« Stop. Nous avons déjà écrit un certain nombre de programmes quasiment identiques, en changeant simplement une petite structure de données.

J'aimerais bien qu’on puisse mettre fin à ces redondances et se concentrer sur l'essentiel.

— Comment comptes-tu t’y prendre ?

— Commençons par regarder les parties qui n’ont jamais changé une version du programme à l’autre.

def contient_doublon(t):

\"\"\"le tableau t contient-il un doublon ?\"\"\"

s = ...

for x in t:

if ... :

return True

...

return False

Dans tous les cas, la structure s représente d’une manière ou d’une autre un ensemble de dates. Le premier trou correspond à la création de la structure s, le deuxième au test de la présence de x dans s et le dernier à l’ajout de x dans s.

Seules ces trois choses varient d’un programme à l’autre.

— On pourrait donc isoler ces trois aspects dans trois fonctions cree(),

contient et ajoute pour avoir la fonction contient_doublon unique suivante.

def contient_doublon(t):

\"\"\"Ile tableau t contient-il un doublon ?\"\"\"

s = cree()

for x in t:

if contient(s, x):

return True

ajoute(s, x)

return False

Ainsi, on pourrait changer la représentation de l’ensemble de dates s en changeant uniquement les définitions de ces trois fonctions, sans qu'il y ait

besoin de toucher à la fonction contient_doublon.

— Et on gagnerait même plus : une fois ainsi isolée, notre définition des ensembles de dates pourrait plus facilement être réutilisée dans un autre programme qui en aurait également besoin.

— D'une certaine manière, ces trois fonctions définissent une frontière entre un programme qui utilise une structure de données et un programme qui la

définit. Celui qui l'utilise n’a pas besoin de connaître le détail de la réalisation de la structure utilisée, et cette réalisation peut elle-même être faite sans savoir comment ni combien de fois elle sera utilisée.

— Frontière n’est pas vraiment le mot. Certes la séparation permet d'ignorer ce qui se passe de l’autre côté, mais ces fonctions sont plutôt l'outil qui permet aux deux programmes d’interagir, de coopérer. Je parlerais plutôt d’une interface. »

","title":"Représentation plus souple : la table de hachage"},{"edit":""}],[{"text":"

Une des clés du développement à grande échelle consiste à circonscrire et séparer proprement les différentes parties du programme.

On peut par exemple séparer le code qui définit une

structure de données du code qui l’utilise, ou dans un plus grand projet séparer l'interface graphique du cœur de l'application.

Chacun des morceaux obtenus peut être placé dans un fichier de code différent, appelé un module.

Un petit module de manipulation d’ensembles de dates correspondant à la stratégie du programme 4 pourrait ainsi être défini par le fichier dates .py reproduit dans le programme 6.

","title":"Modules, interfaces et encapsulation"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"title":"Découpage et réutilisation de code"},{"text":"

Tout projet a donc un code séparé en plusieurs modules, les fonctionnalités définies dans l’un pouvant être utilisées par d’autres. Nous avons pu observer cette utilisation par un programme principal de fonctionnalités issues d’un autre module avec les directives import et les appels à des bibliothèques livrées avec Python, comme random, math, turtle et ....

Nous allons voir ici que cela s'applique également à des modules définis par nous-mêmes ou par des tiers. En particulier, une définition de notre fonction contient _doublon utilisant le module dates défini par le programme 6 s’écrirait comme dans le

programme 7.

Notez qu'en Python le nom d’un module défini par un fichier de code s’obtient simplement en retirant le suffixe .py au nom du fichier.

Un module peut donc faire référence à un certain nombre d'autres modules, qui peuvent aussi bien être issus du projet lui-même que de sources extérieures. On dit alors qu’il dépend de ces autres modules. En dehors de ces dépendances, un module reste a priori autonome et indépendant du reste du projet.

En conséquence, un module constitue également une « brique » logicielle pouvant être réutilisée dans d’autres projets (ou plusieurs fois dans un même projet). On a donc tout intérêt à ce que chaque module soit dédié à la résolution d’une tâche, ou d’un ensemble de tâches apparentées, clairement identifiable.

Cela permet notamment, à chaque fois que le même problème se pose à nouveau, de faire appel au module déjà défini plutôt que d'écrire une nouvelle fois un code similaire et dépenser son temps à résoudre un problème déjà résolu.

Ainsi, si l’on veut savoir combien d'élèves il faut en moyenne dans une école pour qu’un anniversaire soit fêté chaque jour, on peut utiliser un programme tirant des dates au hasard et les stockant dans un ensemble jusqu’à ce que toutes aient été obtenues au moins une fois. Le programme 8 réalise cela. en tirant narti de notre module dates

Programme 6 — dates.py

def cree():

return [0] * 6

def contient(s, x):

paquet = x // 64

bit = x % 64

return s[paquet] & (1 << bit) != 0

def ajoute(s,x):

paquet = x // 64

bit = x % 64

s[paquet] = s[paquet] | (1 << bit)

Programme 7 — rechercher un doublon dans un tableau

from dates import cree, contient, ajoute

def contient_doublon(t):

\"\"\"le tableau t contient-il un doublon ?\"\"\"

s = cree()

for x in t:

if contient(s, x):

return True

ajoute(s, x)

return False

Programme 8 — fête continue

from dates import cree, contient, ajoute

from random import randint

def fete_continue():

compteur = 0

nombre_dates = 0

s = cree()

while nombre_dates < 366:

compteur += 1

x = randint(1, 366)

if not contient(s, x):

nombre_dates += 1

ajoute(s, x)

return compteur

n = 0

for __ in range(1000):

n += fete_continue()

print (\"En moyenne\", n / 1000, \"élèves\")

"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"title":"Interface"},{"text":"

cree() crée et renvoie un ensemble de dates vide

contient(s, x) | renvoie True si et seulement si l’ensemble 5

contient la date x

ajoute(s, x) ajoute la date x à l’ensemble sInterfaces

Pour chaque module, on distingue :

- sa réalisation ou implémentation, c’est-à-dire le

code lui-même;

- son interface, consistant en une énumération des fonctions définies dans le module qui sont destinées à être utilisées dans la réalisation d’autres modules, appelés clients.

L'interface d’un module est liée à sa documentation, et doit notamment expliciter ce qu’un utilisateur a besoin de connaître des fonctions proposées :

comment et pour quoi les utiliser.

Pour chaque fonction de l’interface, on a besoin de :

- son nom,

- de la liste de ses paramètres

- de sa spécification, c'est-à-dire les conditions auxquelles la fonction peut être appliquée et les

résultats à attendre.

Des informations supplémentaires concernant des caractéristiques comme le temps d’exécution ou l’espace mémoire requis peuvent également être utiles.

L'objectif est que ces fonctions incluses dans l'interface soient suffisantes pour permettre à un utilisateur de faire appel aux fonctionnalités du module,

et qu’elles puissent être utilisées sans avoir besoin d’aller consulter le code du module.

L'interface peut être décrite comme une abstraction du module :

une description de ce qui caractérise le module, mais faite à un niveau assez haut, ignorant les détails concrets de la réalisation.

La documentation de l'interface peut être vue comme un contrat entre l’auteur d’un module et ses utilisateurs, qui simplifie l(utilisation du module en limitant le nombre

de choses qu’il faille lire, comprendre et mémoriser pour utiliser le module.

Ainsi, pour être utilisable par notre fonction contient_doublon, l’interface d’un module permettant de manipuler des ensembles de dates devra fournir au minimum les trois fonctions décrites dans l'interface 1.

"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

On dit qu’un module réalise une interface dès lors qu’il définit (au moins) toutes les fonctions promises par l'interface.

Ainsi, le programme 6 et le programme 9 réalisent tous deux l’interface 1, avec les stratégies de représentation des ensembles utilisées dans le programme 4 et le programme 5.

Dans le programme 9, on a ajouté une fonction enumere() construisant un tableau avec les éléments de l’ensemble s donné en paramètre, qui peut notamment

servir à écrire une boucle for sous la forme

for x in enumere(s):

pour énumérer les éléments de l’ensemble s.

Comme nous venons de le voir, une même interface peut admettre une variété de réalisations radicalement différentes. Nous en étudierons plusieurs exemples dans les séquences consacrés à l’algorithmique et aux structures de données.

Programme 9 -ensemble.py

def cree():

return [[] for _ in range(23)]

def contient(s, x):

return x in s[x % 23]

def ajoute(s, x):

s[x % 23].append(x)

def enumere(s) :

tab = []

for paquet in s:

tab.extend(paquet)

return tab

De la difficulté de définir une bonne interface et un code vraiment réutilisable. Dans notre exemple, nous avons introduit une interface pour une structure représentant un ensemble de dates. Nous connaissions un certain nombre de choses sur les données du problème, et notamment que les données à stocker dans l’ensemble étaient des entiers compris entre 1 et 366. Le programme 6 tire d’ailleurs pleinement parti de cette

information. De même, le programme 9 tire parti du fait que l’on n’attend pas plus de 23 dates.

Que se passerait-il si l’on souhaitait généraliser ces programmes et les utiliser pour représenter d’autres ensembles que ceux prévus initialement?

Pour adapter le programme 6 à un intervalle d’entiers de 0 à n on peut imaginer donner n en paramètre à la fonction cree(). Pour que le programme 9 reste efficace lorsqu'il représente des ensembles de 10000 éléments on peut de même imaginer donner le nombre d'éléments attendu en paramètre à la fonction cree().

Ces deux améliorations impliquent en revanche deux manières différentes de modifier l'interface de notre structure d'ensemble. Le programme 10 montrera à l'inverse une manière de généraliser le programme sans changer l'interface, mais ceci n’est pas toujours possible.

","title":"Réalisation d’une interface"},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

Le contrat qu’une interface établit entre le client et l’auteur d’un module ne porte pas sur les moyens, mais sur les résultats : l’auteur s'engage à ce que les résultats produits par l’utilisation de ses fonctions soient ceux décrits, mais il est libre de s’y prendre comme il le souhaite pour y parvenir.

Ainsi, l'auteur d’un module est libre d'utiliser les structures de données qui lui conviennent, mais aussi de définir toute une panoplie de fonctions ou objets annexes uniquement destinés à un usage interne et qui ne sont pas inclus dans l'interface.

Ces éléments internes, qui sont souvent qualifiés de «détails d’implémentation» mais peuvent constituer une large part du code lui-même, ne doivent pas être utilisés par les modules clients. Tous ces éléments hors de l’interface sont parfois qualifiés de privés, et on parle à leur propos d’encapsulation pour signifier qu’ils sont comme enfermés dans une boîte hermétique, dont l'utilisateur n’a pas à connaître le contenu et qu’il

doit encore moins ouvrir.

Ce principe d’encapsulation réduit le couplage entre les différents modules, en évitant que les modifications du code d’un module ne nécessitent d'adapter le code de ses modules clients (pourvu que l’interface soit toujours respectée). Ainsi, l’auteur d’un module peut mettre à jour son code pour le corriger ou l'améliorer, éventuellement en modifiant ou supprimant

certains de ses éléments internes, sans que les projets dépendant de son module n’en souffrent :

si ces derniers fonctionnaient avant la mise à jour, ils fonctionneront toujours après.

On peut donc par exemple modifier notre module ensemble pour l’adapter à la représentation d’ensembles d’entiers quelconques.

Au lieu de constamment utiliser un tableau de 23 paquets qui deviendront tous très grands en moyenne si l’on doit stocker de nombreux éléments dans l’ensemble, on va permettre au nombre de paquets d'augmenter à mesure que le nombre d'éléments dans l’ensemble augmente lui aussi.

Le programme 10 donne un tel programme dans lequel on commence avec 32 paquets, ce nombre étant doublé à chaque fois que le nombre d’éléments dépasse le nombre de paquets. Pour ne pas avoir besoin de recalculer en permanence la taille de l’ensemble représenté, on conserve en outre cette

information avec la table. Un ensemble est ainsi représenté par une paire nommée, réalisée par un dictionnaire contenant deux clés : ’paquets’ pour

la table des paquets et ’taille’ pour le nombre d'éléments. Dans cette nouvelle version, la fonction ajoute, après avoir augmenté la taille de l’ensemble, étend au besoin le tableau des paquets avec une fonction auxiliaire _etend. Cette fonction crée un nouveau tableau avec deux fois plus de paquets dans lequel elle réinsère tous les éléments, avant de lui faire prendre la place du tableau de paquets d’origine. Dans cette opération, les éléments réinsérés sont à nouveau ventilés dans l’ensemble des nouveaux paquets. Les

fonctions ajoute et _etend font de plus toutes deux appel à une fonctionauxiliaire _ajoute_aux qui ajoute un élément à une table de paquets. Notez également un point que nous avions laissé de côté jusqu'ici : la fonction ajoute prend garde à ne pas ajouter un élément déjà présent, de sorte que la taille enregistrée corresponde bien au cardinal de l’ensemble.

Programme 10 — ensemble.py

def cree():

return { 'taille':0,

'paquets': [[] for __ in range(32)] }

def contient(s, x):

p = x % len(s['paquets'])

return x in s['paquets'][p]

def ajoute(s, x):

if contient(s, x):

return

s['taille'] += 1

if s['taille'] > len(s['paquets']):

etend(s)

_ajoute_aux(s['paquets'], x)

def _ajoute_aux(t, x):

p = x % len(t)

t[p].append(x)

def _etend(s):

tmp = [[] for __ in range(2 * len(s['paquets']))]

for x in enumere(s):

_ajoute_aux(tmp, x)

s['paquets'] = tmp

def enumere(s):

tab = []

for paquet in s['paquets']:

tab.extend(paquet)

return tab

","title":"Encapsulation"},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

En Python, l’auteur d’un module peut indiquer que certains éléments (variables globales ou fonctions) sont privés en faisant commencer leur nom par le symbole _. Par convention, tous les autres éléments sont «publics» et doivent être compris comme appartenant à l'interface.

Il faut cependant savoir que dans ce langage, l’encapsulation est une pure convention (certains disent, un vœu pieux), et son respect est sous la seule responsabilité des programmeurs des modules clients. Rien dans les mécanismes du langage n’empêche l'accès aux éléments privés, ni leur utilisation, ni leur modification.

De nombreux autres langages de programmation, mieux adaptés aux projets à grande échelle, introduisent en revanche un contrôle strict de l’encapsulation en rendant l’accès aux éléments privés très compliqué voire impossible.

","title":"Encapsulation en Python. "},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

Le programme 10 ébauche la structure de données fondamentale de table de hachage, sous-jacente aux ensembles et aux dictionnaires de Python. Cette structure très polyvalente permet de représenter des ensembles de taille arbitraire, avec des opérations d’accès aux éléments extrêmement rapides.

Elle est considérée comme la plus efficace dans la plus grande variété des cas courants.

Le principal élément manquant pour obtenir une vraie table de hachage est une fonction appelée fonction de hachage, qui prend en paramètre l'élément à stocker et renvoie un nombre entier définissant (modulo le

nombre de paquets) le numéro du paquet dans lequel insérer l'élément.

Via cette fonction de codage de l'élément à stocker, on peut donc utiliser une table de hachage pour représenter des ensembles d'éléments de toutes sortes, et pas seulement des ensembles d’entiers. En outre, une fonction de hachage est souvent utilisée même pour les tables stockant des entiers, afin de mélanger les éléments et éviter que des nombres liés

les uns aux autres (par exemple, des multiples) ne se retrouvent systématiquement dans le même paquet.

Dans le cas des nombres entiers, on pourra par exemple utiliser des multiplications par des grands nombres premiers combinées à des rotations de la représentation binaire. L'équité de la répartition des éléments dans les différents paquets, et donc l’efficacité de cette structure de données, dépend de la qualité du mélange opéré par cette fonction de hachage. Mais avec une fonction de hachage

convenable, on peut en pratique considérer que la recherche ou l'ajout d’un élément dans une table de hachage sont des opérations instantanées.

","title":"Tables de hachage"},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

Manipuler les fonctionnalités d’un module en n’utilisant que les fonctions fournies par son interface permet de ne pas se soucier des détails d’implémentation de ce module. Du moins tant que tout se passe bien.

Erreurs. Considérons le module dates du programme 6, et essayons d'ajouter à un ensemble une date invalide.

>>> import dates

>>> s = dates.cree()

>>> dates.ajoute(s, 421)

Traceback (most recent call last):

File \"<stdin>\", line 1, in <module>

File \"-/lib/dates.py\", line 12, in ajoute

s[paquet] = s{paquet] | (1 << bit)

IndexError: list index out of range

Le message d'erreur est fâcheux pour plusieurs raisons:

- il mentionne une IndexError, alors que nous ne voulions pas savoir que cette structure utilisait en interne un tableau ;

- pire, la ligne de code fournie ne permet en rien de comprendre le dépassement de tableau : elle mentionne un tableau s dont on ne connaît pas la longueur, et un indice paquet dont on ne connaît

pas le lien avec les paramètres s et 421 fournis à ajoute.

Comprendre en détail cette erreur demande d’explorer le code du module dates, ce qui fait perdre une partie des bénéfices de l’encapsulation.

Remarquez que, plus sournoisement, d’autres dates invalides n’auraient pas déclenché d'erreur.

>>> dates.ajoute(s, 377)

>>> dates.ajoute(s, -383)

Mais quelles dates auraient été ainsi ajoutées ?

Les six entiers de notre tableau fournissent au total 384 bits, dont nous n’utilisons que les numéros 1 à 366 (le numéro 0 est ignoré pour simplifier les calculs). L'ajout de 377 se fait sur un des bits inutilisés du dernier entier du tableau, qui ne correspond à aucune date particulière. L’ajout de -383 en revanche touche le bit du premier janvier.

En l’état actuel des modules définis dans cette séquence, une mauvaise utilisation

dae fnnrtinne de l’interfara riens d'ancendrer As srranre an des affatecollatéraux

qui ne peuvent être compris et anticipés sans une connaissance approfondie du code de ces modules. Ceci contredit le principe d’encapsulation.

Une meilleure pratique consiste, lors du développement de nos modules à renvoyer à l'utilisateur des erreurs explicites, qui peuvent être interprétées à l’aide de la seule connaissance de l'interface. Cette pratique approfondit la notion de programmation défensive.

","title":"Exceptions"},{"edit":"

Tester et mettre le résultat ici (code et figure).

"}],[{"text":"

Nous avons déjà pu observer à de nombreuses reprises des programmes s’interrompre avec des messages d’erreurs variés.

Erreurs.

>>> t = [1, 1, 2, 5, 14, 42, 132]

>>> t[12]

Traceback (most recent call last):

File \"<stdin>\", line 1, in <module>

IndexError: list index out of range

De telles «erreurs» sont appelées en programmation des exceptions et correspondent à la détection,

ici faite par l'interprète Python lui-même, d’un problème empêchant la bonne exécution du programme. Lorsqu'une exception survient, l’exécution du programme est interrompue sur le champ, à moins d’une prise en charge spécifique que nous verrons plus loin dans cette section.

Le tableau suivant redonne quelques exceptions courantes, observables en utilisant les structures de base de Python.

NameError Description

IndexError accès à un indice invalide d’un tableau

KeyError accès à une clé inexistante d’un dictionnaire

ZeroDivisionError | division par zéro

TypeError opération appliquée à des valeurs incompatibles

Il est possible de déclencher directement toutes ces exceptions (on dit « lever une exception ») avec l'opération raise de Python.

>>> raise IndexError(’indice trop grand’)

Traceback (most recent call last):

File \"<stdin>\", line 1, in <module>

IndexError: indice trop grand

Cette opération s'écrit en faisant suivre le mot-clé raise du nom de l’exception à lever, lui-même suivi entre parenthèses d’une chaîne de caractères donnant des informations sur l’erreur signalée.

On peut ainsi définir par exemple une fonction

ecrit(t, i, v)

destinée à remplacer l'opération primitive t[i] = v de modification de la valeur d’une case d’un tableau pour empêcher tout accès involontaire à un indice négatif?.

def ecrit(t, i, v):

if i < 0:

raise IndexError(\"indice négatif”)

tli] = v

La levée d’une exception avec raise interrompant l'exécution du programme, remarquez que dans le code de cette fonction nous n'avons pas eu besoin de else : l'instruction t[i] = v ne sera exécutée que si le programme n’a pas été interrompu.

","title":"Signaler un problème avec une exception"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"title":"Observer la pile d'appels","text":"

Le message affiché lorsqu'une exception interrompt un programme donne un aperçu de l’état de la pile d'appels au moment où l'exception à été levée. On y voit donc quelle première fonction a appelé quelle deuxième fonction qui a, à son tour, appelé quelle

autre fonction, etc., jusqu’à arriver au point où l'exception a été levée.

Il s’agit d’une information inestimable pour comprendre le contexte du problème et le corriger.

"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Les exceptions peuvent être utilisées en particulier dans les fonctions formant l'interface d’un module, pour signaler à un utilisateur du module toute utilisation incorrecte de ces fonctions.

L'interface mentionnera dans ce cas quelles exceptions spécifiques sont levées et dans quelles conditions. On

peut ainsi mettre à jour l'interface 1 comme suit.

contient(s, x) : renvoie True si et seulement si l’ensemble s contient l'élément x

ajoute(s, x) ; ajoute l'élément x à l'ensemble s si 1<x<366 et lève une exception ValueError sinon.

Programme 11 — dates.py

def cree():

return [0] * 6

def contient(s, x):

if x < 1 or x > 366:

return False

paquet = x // 64

bit = x % 64

return s[paquet] & (1 << bit) != 0

def ajoute(s, x):

if x < 1 or x > 366 :

raise ValueError(\"date \" + str(x) + \" invalide\")

paquet = x // 64

bit = x % 64

s[paquet] = s[paquet] | (1 << bit)

L’exception ValueError de Python est à utiliser dans les cas où un paramètre inadapté est donné à une fonction. C’est ici le cas lorsque le paramètre x de la fonction ajoute est un nombre qui n’est pas dans la plage représentant une date valide.

Pour se conformer à cette interface, le programme 6 peut être complété sous la forme du programme 11.

La fonction ajoute commence par vérifier la valeur de x, et lève une exception en cas de problème. Le message associé

précise la valeur de x qui a posé problème. Notez que la fonction contient ne lève pas d'exception en cas de date invalide. Elle se contente alors de renvoyer False.

","title":"Interfaces et exceptions"},{"htm":"","css":"","js":""}],[{"text":"

Les exceptions levées par un programme peuvent avoir plusieurs causes.

Certaines traduisent des erreurs du programme : elles sont imprévues et leurs conséquences ne sont par définition pas maîtrisées. Dans ces conditions,

interrompre l'exécution du programme est légitime. D’autre exceptions, en revanche, s'inscrivent dans le fonctionnement normal du programme : elles correspondent à des situations connues, exceptionnelles mais possibles. Dans cette ligne de code, par exemple, il est tout à fait envisageable que la chaîne de caractères entrée par l’utilisateur ne représente pas un entier valide.

x = int(input(\"Entrer un jour\"))

Dans ce cas, la fonction int lève une exception ValueError, de même que notre fonction ajoute du programme 11 lorsque l’entier fourni n'est pas dans la plage de valeurs attendue.

Une telle exception, qui correspond à un événement prévisible, n’est pas forcément fatale. Certes le programme ne peut pas poursuivre son exécution

comme si de rien n’était, puisque certaines choses n’ont pas eu lieu normalement :

- sur cet exemple, la variable x n'aurait pas été définie.

Cependant, en tant que programmeur, on peut anticiper cette éventualité et prévoir un comportement alternatif du programme pour cette situation exceptionnelle.

Dans le cas présent, on pourrait par exemple demander à nouveau un jour à l'utilisateur, après avoir affiché un message précisant le format attendu.

Pour mettre en place ce comportement alternatif, il faut rattraper cette exception, c’est-à-dire l’intercepter avant que l'exécution du programme ne soit définitivement abandonnée, avec la construction suivante :

try :

x = int(input(\"Entrer un jour : \"))

except ValueError:

print(\"Prière d’entrer un entier valide\")

Le mot-clé try suivi du symbole : (deux-points) introduit un premier bloc de code, puis le mot-clé except suivi du nom de l'exception et du symbole :

précède un deuxième bloc de code.

On qualifiera le premier bloc de normal et le second d’alternatif.

L’exécution d’une telle instruction procède comme suit. On exécute d’abord le bloc de code normal. Si l’exécution de ce bloc s'achève normalement, sans lever d'exception, alors le bloc alternatif est ignoré et on passe directement aux instructions suivantes. Si à l’inverse une exception est levée dans l’exécution du bloc normal, alors l’exécution de ce bloc est immédiatement interrompue et le nom de l'exception levée est comparé avec le nom

précisé à la ligne except. Si les noms correspondent, l'exception est rattrapée et on exécute le bloc de code alternatif avant de passer à la suite. Sinon,

l'exception est propagée et le programme s’interrompt, à moins que le fragment de code considéré soit lui-même inclus dans une autre construction try /except qui pourra à son tour tenter de rattraper l’exception.

Un fragment de code ajoutant une date saisie par un utilisateur à un ensemble s pourra ainsi avoir la forme suivante :

while True:

try:

x = int(input(\"Entrer un jour : \"))

dates.ajoute(s, x)

break

except ValueError:

print (\"Il faut un nombre entier entre 1 et 366\")

Notez que int et ajoute sont toutes deux susceptibles de lever une exception ValueError : la première si la saisie n’est pas un nombre entier et la seconde

si l’entier saisi n’est pas dans la bonne plage. Toutes deux sont rattrapées par notre bloc alternatif.

Si en revanche la valeur saisie convient, alors l'exécution du bloc try s'achève avec l'instruction break qui met fin à la boucle infinie while True.

","title":"Rattraper une exception"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Si. l’on prévoit que plusieurs exceptions peuvent être rattrapées, il est possible d'écrire plusieurs blocs alternatifs, chacun associé à sa ligne except.

try:

<bloc normal>

except Exception1:

<bloc alternatif 1>

except Exception2:

<bloc alternatif 2>

Notez que seules les exceptions levées lors de l’exécution du bloc normal peuvent être rattrapées : les exceptions du premier bloc alternatif ne sont jamais rattrapées par les blocs alternatifs suivants. Autrement dit, les exceptions levées par un bloc alternatif ne peuvent être rattrapées que par une autre construction try /except englobante.

","title":"Alternatives multiples"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

.Si l’on ne précise pas de nom d’exception après except, alors foutes les exceptions seront rattrapées par ce bloc alternatif.

while True:

try:

x = int(input(\"Entrer un jour : \"))

dates.ajoute(s, x)

break

except :

print (\"Il faut un nombre entier entre 1 et 366\")

C'est généralement une mauvaise idée, car on rattrape alors à la fois les exceptions qu’il est légitime de rattraper et celles qui traduisent des erreurs que l’on ne soupçonnait pas. Ce faisant, on efface donc les traces

de ces éventuelles erreurs et on complique leur diagnostic.

Un cas d'usage légitime du rattrapage indiscriminé consisterait à fournir quelques informations sur le contexte de l'exception, par un affichage ou une écriture dans un fichier journal, avant de relancer la propagation de l'exception. On peut réaliser ce redémarrage de la propagation en utilisant le mot-clé raise sans paramètre dans le bloc alternatif.

","title":"Rattrapage indiscriminé"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

( n = 1 si n = 0,

fact(n) = (

( n x fact(n-1) si n>0.

def fact(n):

if n == 0 :

return 1

else:

return n * fact(n - 1)

print(fact(5))

"}],[{"text":"

Écrire un module réalisant l'interface 1 suivant la stratégie du programme 1.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def cree():

return []

def contient(s, x):

return x in s

def ajoute(s, x):

s.append(x)

"}],[{"text":"

Écrire un module réalisant l'interface 1 suivant la stratégie du programme 3.

Attention : pour que la fonction ajoute fonctionne, il faut

pouvoir modifier l’ensemble.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def cree():

return { 'n': 0 }

def contient(s, x):

return s['n'] & (1 << x) != 0

def ajoute(s, x):

s['n'] = s['n'] | (1 << x)

"}],[{"text":"

Supposons que l’on veuille ajouter à l'interface des ensembles la fonction enumere déjà présente par exemple dans le programme 9.

Adapter le module du programme 6 pour qu’il réalise cette interface étendue.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Comme dans le programme 9, on construit un tableau

que l’on agrandit à chaque élément trouvé. On teste alors chaque bit de chacun des six entiers du tableau, et on calcule le nombre correspondant lorsque nécessaire.

def enumere(s):

tab = []

for paquet in range(6):

for bit in range(64):

if s[paquet] & (1 << bit) != 0:

tab.append(paquet*64 + bit)

return tab

"}],[{"text":"

Supposons que l’on veuille ajouter à l'interface des ensembles les deux fonctions d’union et d’intersection suivantes.

union(s1, s2) renvoie un nouvel ensemble composé de

l’union des éléments de s1 et s2.

intersection(s1, s2) renvoie un nouvel ensemble composé de l'intersection des éléments de s1 et s2.

Précisons que ces fonctions ne doivent pas modifier les ensembles s1 et s2 qui leur sont donnés en paramètres.

Réaliser ces fonctions dans le module de l'exercice 11.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def union(s1, s2):

t = [x for x in s1]

for x in s2:

if x not in si:

t.append(x)

return t

def intersection(s1, s2):

t= [0]

for x in s1:

if x in s2:

t.append(x)

return t

"}],[{"text":"

Certaines réalisations des ensembles d’entiers vues dans cette séquence représentent plus précisément des ensembles d’entiers compris entre 0 et un certain entier maximum nmax? Lesquelles ? Comment était décidé Nmax ? Que changer à l'interface de ces programmes pour permettre à l’utilisateur de choisir nmax ?

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}],[{"text":"

Les modules décrits par chacun des programmes 6, 9 et 10 réalisent tous l’interface 1 et peuvent donc tous être utilisés par le programme 8.

Pour autant, l'un est-il préférable aux autres pour cette application particulière ?

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Les trois modules sont corrects et permettront d’obtenir le résultat. On a cependant les différences d'efficacité suivantes.

- Le programme 10 est préférable au programme 9 concernant le temps d’exécution. En effet, l’ensemble manipulé contiendra à terme plus de 360 éléments, soit en moyenne une quinzaine d’éléments par paquet :

l'augmentation du nombre de paquets est utile.

- Le programme 6 est comparable au programme 10 pour le temps d’exécution, mais préférable aux deux autres pour la mémoire utilisée. En effet, l’ensemble manipulé n’est pas quelconque : on sait qu’il contiendra à terme tous les éléments de 1 à 366. La représentation utilisée par ce programme sera donc de loin la plus compacte.

"}],[{"text":"

Considérons une structure de table de hachage telle que réalisée par le programme 10 mais avec seulement 8 paquets. On place dedans les entiers 0, 1, 4, 9, 13, 24 et 30.

Donner le contenu de chacun des paquets.

‹

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On place l’entier x dans la table d’indice x % 8. On

obtient le tableau de paquets suivant.

[[0, 24], [1, 9], [ ], [ ],, [4], [13], [30], [ ]]

"}],[{"text":"

L'interface des tableaux de Python fournit de nombreuses opérations à l’allure anodine mais cachant une complexité non négligeable. Rien de tel que d’essayer de réaliser soi-même ces fonctions pour s’en rendre compte.

Écrire un module réalisant l'interface suivante

tranche(t, i, j) renvoie un nouveau tableau contenant les

éléments de t de l’indice i inclus à l'indice j exclu (et le tableau vide si j < i)

concatenation(t1, t2) | renvoie un nouveau tableau contenant, dans l’ordre, les éléments de t1 puis les

éléments de t2

Notez qu'aucune de ces fonctions ne doit modifier les tableaux passés en paramètres.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

La tranche est créée dans un nouveau tableau de

longueur adaptée, où on place les éléments prélevés à partir de l’indice i.

La concaténation de même crée dès l’origine un tableau de taille adaptée.

def tranche(t, i, j):

n = j - i

if n <= 0:

return []

else:

tab = [None] * n

for k in range(n):

tab[k] = t[i+k]

return tab

def concatenation(ti, t2):

l1, l2 = len(t1), len(t2)

tab = [Nonel * (l1 + l2)]

for i in range(l1):

tab[i] = t1[i]

for i in range(l2):

tab[l1 + i] = t2[i]

return tab

"}],[{"text":"

Voici une interface minimale pour une structure de dictionnaire.

cree() crée et renvoie un dictionnaire vide

cle(d, k) renvoie True si et seulement si le dictionnaire d

contient la clé k

lit(d, k) renvoie la valeur associée à la clé k dans le dictionnaire d, et None si la clé k n’apparaît pas

ecrit(d, k, v) | ajoute au dictionnaire d l'association entre la clé k et la valeur v, en remplaçant une éventuelle valeur si la clé k existe.

On propose de réaliser cette interface de dictionnaire avec un tableau de couples clé-valeur, en faisant en sorte qu'aucune clé n’apparaisse deux fois.

Écrire un module réalisant cela.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

#Le dictionnaire vide n’est rien d’autre qu’un tableau

def cree():

return []

#Pour chercher une clé, on passe en revue tous les couples clé-valeur jusqu’à

#trouver la clé cherchée ou épuiser le tableau.

def cle(d, k):

for (kv, v) in d:

if hv == k :

return True

else :

return False

def lit(d, k):

for (kv, v) in d:

if kv == k :

return v

return None

#Pour ajouter une nouvelle association, il faut distinguer le cas où la clé est

#déjà présente du cas où elle ne l’est pas. Ici, dans le premier cas on remplace

#le couple correspondant par un nouveau couple, et dans le deuxième cas on

#ajoute le nouveau couple à la fin.

def ecrit(d, k, v):

for i in range(len(d)):

if d[i][0] == k:

d[i] = (k, v)

return

d.append((k, v))

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 10 Septembre 2020; Mis à jour : 10 Septembre 2020; Clics : 1443

[[{"title":"Python - Les fonctions récursives","posi":0},{"text":"

$\"What$

Nous venons de voir des généralités sur les fonctions. Maintenant, nous allons aborder un cas particulier sur celle-ci, les fonctions récursives.

Il s’agit à la fois d’un style de programmation mais également d’une technique pour définir des concepts et résoudre certains problèmes qu’il n’est parfois pas facile de traiter en programmant uniquement avec des boucles.

"},{"text":"Si vous avez réalisé l'activité demandée, le bouton suivant apparaîtra en bas à droite pour réaliser l'étape d'après."}],[{"text":"

Pour définir la somme des n premiers entiers, on a l'habitude d’écrire la formule suivante :

0+1+2+...+n-1 + n (1)

Une solution pour calculer cette somme consiste à utiliser une boucle for pour parcourir tous les entiers i entre 0 et n, en s’aidant d’une variable locale s pour accumuler la somme des entiers de 0 à i. On obtient par exemple le code Python suivant :

def somme1(n) :

s = 0

for i in range(n + 1):

s=s+i

return s

print(somme1(5))

La fonction somme(n) ci-dessus calcule bien la somme des n premiers entiers. Cependant, ce code Python n'est pas directement lié à la formule

0+1+2+...+n-1 + n.

En effet, il n’y a rien dans cette formule qui puisse laisser deviner qu’une variable intermédiaire s est nécessaire pour calculer cette somme.

","title":"Problème : la somme des n premiers entiers"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Il existe une autre manière d'aborder ce problème. Il s’agit de définir une fonction somme(n) qui, pour tout entier naturel n,donne la somme des n premiers entiers de la manière suivante :

{ 0 si n=0 ,

somme(n) = {

{ n+somme(n-1) si n>0.

Cette définition nous indique ce que vaut somme(n) pour un entier n quelconque, selon que n soit égal à 0 ou strictement positif (n>0).

Ainsi, pour n = 0, la valeur de somme(0) est simplement 0.

Dans le cas où n est strictement positif (n>0), la valeur de somme(n) est n + somme(n - 1).

Par exemple, voici ci-dessous les valeurs de somme(n), pour n valant 0, 1,2,3,4 et 5.

somme(0) = 0

somme(1) = 1+somme(0) = 1+0 = 1

somme(2) = 2+somme(1) = 2+1 = 3

somme(3) = 3+somme(2) = 3+3 = 6

somme(4) = 4+somme(3) = 4+6 = 10

somme(5) = 5+somme(4) = 5+10 = 15

Comme on peut le voir, la définition de somme(n) dépend de la valeur de somme(n - 1). Il s’agit là d’une définition fonction récursive, c’est-à-dire d’une définition de fonction qui fait appel à elle-même.

Ainsi, pour connaître la valeur de somme(n), il faut connaître la valeur de somme(n - 1), donc connaître la valeur de somme(n - 2), etc. Ceci jusqu’à la valeur de somme(0) qui vaut 0. La valeur de somme(n) s'obtient en ajoutant toutes ces valeurs.

Cette définition récursive de la fonction somme(n) est facilement programmable en Python :

def somme(n) :

if n == 0 :

return 0

else :

return n + somme(n - 1)

print(somme(5))

L'analyse par cas de la définition récursive est ici réalisée par une instruction conditionnelle ( if ) pour tester si l’argument n est égal à 0. Si c’est le cas, la

fonction renvoie la valeur 0, sinon elle renvoie la somme de n + somme(n - 1).

Cet appel à somme(n - 1) dans le corps de la fonction est un appel récursif, c'est-à-dire un appel qui fait référence à la fonction que l’on est en train de

définir.

On dit de toute fonction qui contient un appel récursif que c’est une fonction récursive.

Par exemple, l'évaluation de l’appel à somme(5) peut se représenter de la manière suivante :

somme(5) = return 5+somme(4)

return 4+somme(3)

return 3+somme(2)

return 2+somme(1)

return 1+somme(0)

return 0

","title":"Boucles bornées simples"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"title":"Formulations récursives"},{"text":"

Une formulation récursive d’une fonction est toujours constituée de plusieurs cas, parmi lesquels on distingue des cas de base et des cas récursifs

du calcul.

Les cas récursifs sont ceux qui renvoient à la fonction en train d’être définie :

somme(n) = n + somme(n - 1 si n > 0.

Les cas de base de la définition sont à l'inverse ceux pour lesquels on peut obtenir le résultat sans

avoir recours à la fonction définie elle-même :

somme(n) = 0 si n = 0.

Ces cas de base sont habituellement les cas de valeurs particulières pour lesquelles il est facile de déterminer le résultat.

Prenons comme exemple l'opération de puissance

-ième d’un nombre a.

On a donc la multiplication répétée n fois de a avec lui-même.

Cela s'écrit de la manière suivante :

aⁿ = a x a x a x ... x a

(_____________)

n fois

avec, par convention a” que la puissance de a pour n = 0 vaut 1.

Pour écrire une version récursive de an, on va créer une fonction puissance(a,n) en réalisant les 2 étapes suivante :

Etape 1 : Rechercher les cas de base

0n a

1 si n = 0

Etape 2 : Déterminer les cas récursifs

On a

a x puissance(a,n-1)

Au final, on obtient définition de la fonction produit(a,n) :

{ 1 si n=0 ,

produit( a , n ) = {

{ a x produit( a , n-1 ) si n>0.

On en déduit le programme suivant de la fonction produit(a,n) :

def produit(a,n) :

if n == 0 :

return 1

else :

return a * produit(a,n-1)

print(produit(2,4))

"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"title":"Définitions récursives plus riches"},{"text":"

Toute formulation récursive d’une fonction possède au moins un cas de base et un cas récursif. Ceci étant posé, une grande variété de formes est possible.

Cas de base multiples

La définition de la fonction puissance(a,n) n’est

pas unique. On peut par exemple identifier deux cas de base « faciles », celui pour n = 0 mais également celui pour n = 1 avec puissance(a, 1) = a.

Ce deuxième cas de base a l’avantage d'éviter de faire la multiplication (inutile) a x 1 de la définition précédente. Ainsi, on obtient la définition suivante avec

deux cas de base :

{ 1 si n=0 ,

produit( a , n ) = { a si n=1

{ a x produit( a , n-1 ) si n>0.

Cas récursifs multiples

Il est également possible de définir une fonction

avec plusieurs cas récursifs. Par exemple, on peut donner une autre définition pour puissance(a,n) en distinguant deux cas récursifs selon la parité de n.

{ 1 si n=0 ,

produit( a , n ) = { carre(puissance(a,n/2)) si n > 0 et n est pair,

{ a x carre(puissance(x,(n —1)/2)) si n > 0 et n est impair

"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Les expressions qui définissent une fonction peuvent

aussi dépendre de plusieurs appels à la fonction en cours de définition.

Par exemple, la fonction fibonacci(n), qui doit son nom au mathématicien Leonardo Fibonacci, est définie récursivement, pour tout entier naturel n, de la manière suivante :

{ 0 si n = 0

fibonacci(n) = { 1 si n = 1

{ fibonacci(n-2)+fibonacci(n-1) si n > 1.

","title":"Double récursion"},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

Les occurrences de la fonction en cours de définition peuvent également être imbriquées. Par exemple, la fonction f_n(n) ci-dessous, que l’on doit à John McCarthy (informaticien et lauréat du prix

Turing en 1971), est définie avec deux occurrences imbriquées, de la manière suivante :

{ n - 10 si n > 100

fn(n) = {

{ f91( f91(n + 11)) si n ≤ 100.

","title":"Récursion imbriquée"},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

Il est également possible de définir plusieurs fonctions récursives en même temps, quand ces fonctions

font référence les unes aux autres. On parle alors de définitions récursives mutuelles.

Par exemple, les fonctions a(n) et b(n) ci-dessous, inventées par Douglas Hofstadter (il y fait référence dans son ouvrage Güdel, Escher, Bach : Les

Brins d’une Guirlande Éternelle, pour lequel il a obtenu le prix Pulitzer en 1980), sont définies par récursion mutuelle de la manière suivante :

{ 1 si n = 0

a(n) = {

{ n - b(a(n-1)) si n > 0.

{ 0 si n = 0

b(n) = {

{ n - a(b(n-1)) si n > 0.

","title":"Récursion mutuelle"},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

Pour écrire une définition récursive correcte, il faut respecter les règles suivantes :

Règle 1 : il faut s’assurer que la récursion va

bien se terminer, c’est-à-dire que l’on va finir par « retomber » sur un cas de base de la définition.

Règle 2 : il faut que les valeurs utilisées pour appeler

la fonction soient toujours dans le domaine de la fonction.

Règle 3 : il convient de vérifier qu’il y a bien une définition pour toutes les valeurs du domaine.

","title":"Définitions récursives bien formées"},{"edit":"

Tester et écrire ici le résultat.

"}],[{"text":"

Les techniques de définition récursive peuvent s’appliquer à toute une variété d'objet, et pas

seulement à la définition de fonctions. Nous verrons en particulier aux des structures de données définies récursivement.

","title":"Définition récursive de structures de données"},{"edit":"

Tester et mettre le résultat ici (code et figure).

"}],[{"text":"

Une fois que l’on dispose d’une définition récursive pour une fonction, il faut codé la fonction en Python.

Mais il faut faire attention à 2 points :

1. Le domaine mathématique d’une fonction (les valeurs prise par la définition) , n’est pas toujours le même que l’ensemble des valeurs du type Python avec lesquelles elle sera appelée

2. Le choix d’une définition récursive plutôt qu’une autre peut dépendre du modèle d’exécution des fonctions récursives.

","title":"Programmer avec des fonctions récursives"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"title":"Domaine mathématique vs. type de données","text":"

Prenons l'exemple de somme(n) :

Sa définition est ;

{ 0 si n=0 ,

somme(n) = {

{ n+somme(n-1) si n>0.

est définit pour n≥0 ou n∈[0 ; +∞ [

Sa fonction en python :

def somme(n) :

if n == 0 :

return 0

else :

return n + somme(n - 1)

est définit pour n∈] -∞ ; +∞ [. En effet, n peut être négatif ou positif.

Tester la fonction pour somme( -1 ) et conclure.

"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

La fonction somm(-1) provoque une erreur d'exécution.

En effet si n<0 (négatif) la fonction boucle à l'infini.

Pour éviter ce comportement, il y a plusieurs solution :

1. Changer le test n==0 par n<=0, mais là on change le domaine de définition.

2. Une autre solution est de restreindre les appels à la fonction somme(n) en ajoutant une instruction assert avec n>=0.

def somme(n) :

assert n>=0 ,\"Erreur : n doit être positif ou nul\"

if n == 0 :

return 0

else :

return n + somme(n - 1)

print(somme(-2))

Tester le code ci-dessous avec n = 5 et n = -2. Conclure.

Cette solution est correcte, mais elle n’est pas encore satisfaisante. En effet, pour tout appel somme(n) avec n >= 0, chaque appel récursif commencera par faire le test associé à l'instruction assert, alors que chaque valeur de n sera toujours positive.

Une solution pour éviter ces tests inutiles est de définir deux fonctions :

def somme_bis(n) :

if n == 0 :

return 0

else :

return n + somme(n - 1)

def somme(n) :

assert n>=0 ,\"Erreur : n doit être positif ou nul\"

return somme_bis(n)

print(somme(-2))

La fonction somme(n) vérifiera une seule fois que

son argument n est positif. Puis, si c’est le cas, elle appellera la fonction somme_bis(n).

Tester avec les 2 fonctions et conclure.

"},{"htm":"","css":"","js":""}],[{"text":"

Une partie de l’espace mémoire d’un programme

est organisée sous forme d’une pile où sont stockés les contextes d'exécution de chaque appel de fonction.

SI nous prenons l'exemple de la fonction puissance(x,n) :

def puissance(x, n):

if n == 0 :

return 1

else:

return x * puissance(x, n - 1)

l’organisation de la mémoire au début de l'appel à puissance(7,4) est un emplacement pour la variable x initialisé à 7 et un autre pour n à 4.

	...
x	7	puissance(7,4)
n	4

L'environnement contient également d’autres valeurs (comme l'emplacement pour la valeur renvoyée par la fonction, la sauvegarde des registres, etc.)

qui sont simplement représentées par des --- dans le schéma ci-dessus.

Le calcul récursif de puissance(7,4) va engendrer une suite d’appels « en cascade » à la fonction puissance, que l’on peut représenter par l’arbre d’appels suivant :

puissance(7,4)=

return 7 * puissance(7,3)

return 7 * puissance(7,2)

return 7 * puissance(7,1)

return 7 * puissance(7,0)

return 1

L’organisation de la pile mémoire est de cette forme pour puissance(7,4) :


x	7	puissance(7,4)
n	4
x	7	puissance(7,3)
n	3
x	7	puissance(7,2)
n	2
x	7	puissance(7,1)
n	1
x	7	puissance(7,0)
n	0

Juste après le dernier appel à puissance (7,0), la pile contient donc les environnements d'exécution pour les cinq appels à la fonction puissance. Donc pour un appel à puissance(x,n), il y aura n+1 environnements dans la pile.

","title":"Modèle d'exécution"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Par défaut, Python limite le nombre d’appels récursifs dans une fonction à 1000.

Si vous dépassez les 1000, l'exception suivante s'affichera RecursionError: maximum recursion depth exceeded.

Cette limite, fixée à 1000 appels récursifs , peut être modifiable avec la fonction setrecursionlimit disponible dans le module sys.

Par exemple, pour passer cette limite à

2000 appels maximum, on exécutera le code Python suivant :

import sys

sys.setrecursionlimit(2000)

Remarque : La récursion dans d’autres langages. Certains langages de programmation, plus spécialisés que Python dans l’écriture de fonctions récursives, savent dans certains cas éviter de placer de trop nombreux environnements d'appel dans la pile. Cela leur permet dans les cas en question de s'affranchir de toute limite relative au nombre d'appels emboîtés. C’est

le cas notamment des langages fonctionnels (Lisp, Scala, ...).

","title":"Erreurs"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Donner une définition récursive qui correspond au calcul de la fonction factorielle n! définie par nl=1x2x...xn si n > 0 et 0! = 1, puis le code d’une fonction fact(n) qui implémente cette définition (fact(5)=120).

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

( n = 1 si n = 0,

fact(n) = (

( n x fact(n-1) si n>0.

def fact(n):

if n == 0 :

return 1

else:

return n * fact(n - 1)

print(fact(5))

"}],[{"text":"

Soit u, la suite d’entiers définie par

U_n+i = U_n/2 si Un est pair,

- 3xU_n+1 sinon.

avec U₀ un entier quelconque plus grand que 1.

Écrire une fonction récursive syracuse(u_n) qui affiche les valeurs successives de la suite w, tant que w, est splus grand que 1

Exemple pour syracuse(20)

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def syracuse(u_n):

print (u_n)

if u_n > 1:

if u_n % 2 == 0:

syracuse(u_n // 2)

else:

syracuse (3 * u_n + 1)

syracuse(20)

"}],[{"text":"

On considère la suite u, définie par la relation de récurrence suivante, où a et b sont des réels quelconques :

( a€ℝ si n =0

Un = ( b€ℝ si n=1

( 3U_n-1 + 2U_n-2 + 5 si n≥2

Écrire une fonction récursive serie(n, a, b) qui renvoie le n-ème terme de cette suite pour des valeurs a et b données en paramètres.

Exemple : serie(20,1,5,5.3) = 211709824932.3

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def serie(n, a, b):

if n == 0 :

return a

elif n == 1 :

return b

else:

r = 3 * serie(n - 1, a, b) + 2 * serie(n - 2, a, b) +5

return r

print(serie(20,1.5,5.3))

"}],[{"text":"

Écrire une fonction récursive boucle(i ,k) qui affiche les entiers entre i et k.

Par exemple, boucle(0,3) doit afficher : 0 1 2 3.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def boucle(i,k):

if i <= k:

print(i)

boucle(i+1, k)

boucle(0,3)

"}],[{"text":"

Écrire une fonction récursive pgcd(a, b) qui renvoie le PGCD de deux entiers a et b.

Exemple pgcd(96,36)=12

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def pgcd(a, b):

if a == 0:

return b

else :

return pgcd(b % a, a)

"}],[{"text":"

Écrire une fonction récursive nombre_de_chiffres(n) qui prend un entier positif ou nul n en argument et renvoie son nombre de chiffres.

Par exemple, nombre_de_chiffres(34126) doit renvoyer 5.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def nombre_de_chiffres(n):

if n <= 9:

return 1

else:

return 1 + nombre_de_chiffres(n // 10)

print(nombre_de_chiffres(34126))

"}],[{"text":"

En s'inspirant de l'exercice précédent, écrire une fonction récursive nombre _de_bits_1(n) qui prend un entier positif ou nul et renvoie le nombre de bits valant 1 dans la représentation binaire de n.

Par exemple : nombre _de_bits_1(1100100)=3

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}],[{"text":"

Écrire une fonction récursive appartient(v, t, i) prenant en paramètres une valeur v, un tableau t et un entier i et renvoyant True si v apparaît dans t entre l’indice i (inclus) et len (t) (exclu), et False sinon.

On supposera que i est toujours compris entre 0 et len(t).

Exemple :

t = [1,3,5,6,7,9,10]

appartient(7,t,5) = False

appartient(7,t,3) = True

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def appartient(v, t, i):

if i == len(t):

return False

else:

return t[i] == v or appartient(v, t, i + 1)

t = [1,3,5,6,7,9,10]

print(appartient(7,t,5))

print(appartient(7,t,3))

"}],[{"text":"

Le triangle de Pascal (nommé ainsi en l’honneur au mathématicien Blaise Pascal) est une présentation des coefficients binomiaux sous la forme d’un triangle défini ainsi de manière récursive :

( 1 si p=0 ou n = p,

C{n,p) = (

( C(n - 1 , p - 1) + C(n - 1,p) sinon.

Écrire une fonction récursive C(n,p) qui renvoie la valeur de C{n,p).

Exemple : C510,5) = 252

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def C(n,p):

if p == 0 or n == p :

return 1

else:

return C(n - 1, p - 1) + C(n - 1, p)

print(C(10,5))

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 7 Septembre 2020; Mis à jour : 13 Septembre 2020; Clics : 2035

Page 50 sur 79

1ère Générale NSI

Term. Générale NSI

Terminale STI2D SIN

Bts Ccst

Technico-commercial 3.0

Vidéos YouTube

tnsi json sequence 10 programmation fonctionnelle

tnsi json séquence 8 mise au point programme

tnsi json programmation objet sequence 8

tnsi json modularité séquence 2

tnsi json séquence 6 fonction récursive