Programmation Python
Programmation Python
Programmation Python
0 (2015)
Thierry Massart
CONTENTS
Prsentation du cours
1.1 Avant-propos . . . . . . . . . . . . . . .
1.2 But du cours . . . . . . . . . . . . . . .
1.3 Comptences principales vises . . . . .
1.4 Ressources . . . . . . . . . . . . . . . .
1.5 Pourquoi Python ? (et pas C++, Java, ...)
1.6 Un peu de vocabulaire . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
1
2
3
3
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
5
5
7
7
8
9
10
11
11
12
12
13
14
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
17
21
21
24
24
.
.
.
.
.
25
25
26
27
28
30
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.6
4.7
5
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
33
33
36
38
46
47
48
49
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
55
55
59
62
63
64
69
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Ensembles et Dictionnaire
71
7.1 Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
7.2 Dictionnaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.3 Changement de type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Recherches et tris
83
8.1 Les classiques : recherches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.2 Les classiques : tris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
95
95
101
108
113
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
117
117
118
121
126
129
11 Rcursivit
11.1 Motivation et introduction du concept . . . . . . . .
11.2 Mcanismes . . . . . . . . . . . . . . . . . . . . .
11.3 Structures de donnes rcursives . . . . . . . . . . .
11.4 Traduction de fonction rcursive en fonction itrative
11.5 Gestion de la mmoire lexcution . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
133
133
136
140
142
143
ii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
179
179
185
189
190
205
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
211
211
211
212
212
213
213
214
214
215
iii
iv
CHAPTER
ONE
PRSENTATION DU COURS
1.1 Avant-propos
Author Thierry Massart <tmassart@ulb.ac.be>
Version 2.1.3
Date August 21, 2015
Copyright This document has been placed in the public domain.
1.4 Ressources
Ces pages
le livre de Grard Swinnen sur Python 3 (pour la premire partie du cours)
lUniversit Virtuelle (exercices, anciens examens, codes sources, ventuels complments de matire)
python.org (tutoriel, manuels, download, ...)
un environnement python 3.2, ainsi quun diteur simple comme gedit
le site de test upylab
le syllabus dexercices
Pour ceux qui veulent faire des calculs numriques : python2.7 avec pylab, numpy, scipy,
mathplotlib, ....
1.4. Ressources
Un problme algorithmique peut tre vu comme une fonction f dont limage de toute donne
d de lensemble D des donnes possibles est un rsultat r (= f(d)) de lensemble R des
rsultats possibles.
Lalgorithme qui rsout le problme est la mthode calculant f(d) en un temps fini, pour toute
donne d valide.
Notons quil nexiste pas dalgorithme pour tout problme (Il est donc intressant de dterminer
thoriquement lexistence dun algorithme pour un problme donn avant dessayer de lcrire
effectivement). A ct de cela, il existe souvent de nombreux algorithmes pour rsoudre un
problme donn; leurs qualits propres permettront de les diffrencier.
Un algorithme doit tre implment sur un ordinateur. Celui-ci ne possde jamais quun nombre limit de mmoire de stockage dinformation dont la prcision est limite. De ce fait pour
rsoudre certains problmes qui en thorie pourraient requrir un calcul trop long, ou une prcision ou un stockage dinformation trop importants, des algorithmes ne donnant quune valeur
approche du rsultat doivent tre conus.
Ecrire un petit programme ou a fortiori dvelopper un gros logiciel demande une dmarche en
plusieurs tapes, appele processus de dveloppement dun programme, qui peut tre divis en
plusieurs phases (partiellement) successives.
1. Analyse de ce qui est requis et spcification,
2. Conception,
3. Implmentation,
4. Tests et installation,
5. Exploitation et maintenance.
Chaque phase produit des rsultats crits soit sous forme de rapport : spcification de ce qui
est requis (cahier de charges), manuel utilisateur, description du fonctionnement, description
succincte ou dtaille de lalgorithme, programme dment comment, historique des modifications, ....
Ce cours nabordera par tous ces points en dtails.
CHAPTER
TWO
mande (dans un shell) la commande python3 ou python si la version par dfaut sur votre
ordinateur est la bonne.
Le prompt >>> invite lutilisateur taper une instruction Python. Toute commande ou instruction est envoye lordinateur en tapant la touche return.
La session suivante donne un exemple dutilisation du mode interactif pour faire des calculs
simples.
litpc30:~ tmassart$ python3
Python 3.2.3 (v3.2.3:3d0686d90f55, Apr 10 2012, 11:25:50)
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 5 + 7
12
>>> 2 - 11
-9
>>> 7 + 3 * 2
13
>>> (7+3) * 2
20
>>> 20 /3
6.666666666666667
>>> 20 // 3
6
>>> -20 // 3
-7
>>> -20//-3
6
>>> 20//-3
-7
>>> 11/3
3.6666666666666665
>>> 9/3
3.0
>>> 3.14 * 5**2
78.5
>>> 3.14159 * 5**2
78.53975
>>> 3.14159 ** 100
5.187410133839704e+49
>>> 9 % 2
1
>>> exit()
litpc30:~ tmassart$
Note: les valeurs comme 5, 7, 3.14 sont appeles constantes ou littraux (literal).
Note: la fonction quit() ou exit() permet de clturer la session et revenir au prompt (symbole
dinvite) du shell.
6
Note: Les oprateurs arithmtiques les plus frquemment utiliss sont + (addition), - (soustraction), * (multiplication), / (division relle), // (division entire plancher), ** (exponentiation), % (modulo) ainsi que += (incrmentation) -= (dcrmentation) *= (multiplication par
w), /= (division par w).
Note: Attention, les oprateurs habituels sont tous associatifs gauche sauf lexponentiation
qui est associatif droite (essayez 2**2**3)
Les oprateurs + et * peuvent tre utiliss sur du texte et ont comme smantique la concatnation (mise bout bout des textes) et la rptition.
>>> cha+peau
chapeau
>>> "ha"*5
hahahahaha
x = 3
y = 12
z = x
x = 2 * x
y = 2 * y
z = x * y
x, y, z
24, 144)
Un type daction essentiel en Python (et dans la plupart des langages de programmation) est
lassignation galement appele affectation.
Lopration dassignation a la forme:
v=w
o w est une expression donnant une valeur et v est le nom dune variable.
Dans une premire approximation cette opration consiste mettre la valeur w dans la variable
v
Ainsi la squence dinstructions donnera les valeurs suivantes pour les variables, o ? signifie
que la variable nexiste pas (et donc que sa valeur est indfinie):
1
Plus prcisment lobjet qui contient la valeur mais aussi dautres attributs, comme nous le verrons plus loin.
x
3
3
3
6
6
6
6
y
?
12
12
12
24
24
24
z
?
?
3
3
3
144
144
Notons que la dernire instruction x, y, z a comme seul effet, dans lenvironnement interactif, dafficher les valeurs correspondantes (ici du tuple (x, y, z)).
2.6 print()
Linterprteur Python a un certain nombre de fonctions prdfinies sa disposition (voir la
liste dans la documentation de la Python Standard Library du site python.org ). Nous verrons
certaines de ces fonctions. Commenons par les fonctions print(), float() et input().
Quand le programmeur dsire, non pas faire des tests ou petits calculs rapides, mais crire
un programme complet, il dite un fichier qui par convention porte un suffixe py, contenant
son code Python. Je peux par exemple sauver le fichier mon-premier-programme.py du
code de mon premier programme sur disque (ou tout autre moyen de stockage) pour ensuite
lexcuter sur mon ordinateur en tapant la ligne de commande
python3 mon-premier-programme.py
Lexcution se fait en mode script par opposition au mode interactif.
Warning: Vos fichiers Python doivent tre sauvs dans lencodage UTF-8 (voir livre de
Swinnen pour plus dexplications). Nous vous conseillons dutiliser lditeur gedit pour
crire vos programmes Python.
Aprs un court instant, le prompt de la ligne de commande saffiche ce qui montre que
lexcution est termine: rien na t affich.
litpc30:Exemples-cours tmassart$ python3 mon-premier-programme.py
litpc30:Exemples-cours tmassart$
Si lon veut, en mode script, visualiser un rsultat dans la fentre de commande, le programme
doit utiliser linstruction
print()
par exemple, si lon remplace la dernire ligne par:
>>> print(x, y, z)
on obtient
2.6. print()
Note: Le tutoriel sur python 3.2 (section Fancier Output Formatting) illustre les possibilits
dcriture quoffre le langage
2.7 Types
En Python, les objets ont un type. Lors de la cration, dun nouvel objet, son type est dfini en
fonction de lobjet cr. Plus prcisment, Python est un langage orient-objet: on dit que les
entits cres sont des objets dune certaine classe.
Les types les plus habituellement manipuls sont entier (integer), rel ou plus prcisment
nombre virgule flottante (float), boolen ou logique (boolean), chane de caractres (string).
Linstruction Python
type(x)
o x est un objet, permet de connatre la classe de x.
>>> x = 3
>>> y = x / 2
>>> type(x)
<class int>
>>> type(y)
<class float>
Les exemples prcdents nutilisent que des objets (de type) entiers et rels. Lexemple suivant
manipule dautres types.
>>> t="Ceci est un exemple de texte"
>>> t2="Cest important de faire attention aux apostrophes"
>>> flag = t == t2
>>> print(t, t2, flag)
Ceci est un exemple de texte Cest important de faire attention aux apostrophes
>>> type(t)
<class str>
>>> type(t2)
<class str>
>>> type(flag)
<class bool>
Si la traduction a un sens, il est possible et peut tre utile de prendre une valeur dun certain
type et den construire une valeur correspondante dans un autre type. Par exemple
>>> r= 3.14
>>> r2 = int(r)
>>> print(r,r2)
10
3.14 3
>>> c = 52
>>> i = int(c)
>>> type(c)
<class str>
>>> type(i)
<class int>
Une premire application est la lecture de valeurs, comme expliqu dans la section suivante.
2.8 input()
Comme dj expliqu, un algorithme ou un programme peut tre vu comme une mthode pour
rsoudre un problme spcifi. Gnralement, le programme reoit des donnes et renvoie
des rsultats. Linstruction input() permet de lire des donnes lors de lexcution du programme.
x = input("un texte qui invite lutilisateur entrer une
donne")
Aprs cette instruction x contient le texte envoy par lutilisateur du programme et lu par le
programme.
Prenons lexemple dun programme dont le but est de trouver les ventuelles racines dune
quation du second degr. Pour recevoir les trois valeurs relles on pourra crire
>>> a= float(input(valeur de a : ))
>>> b= float(input(valeur de b : ))
>>> c= float(input(valeur de c : ))
float() traduit le texte lu en valeur relle sil correspond bien un rel dans une syntaxe
correcte
2.9 Commentaires
Un programme Python doit tre syntaxiquement correct pour tre comprhensible par
lordinateur (linterprteur qui le lit et lexcute); il doit galement tre lisible pour le programmeur ou toute personne qui aurait envie de comprendre son fonctionnement.
Pour cela, il est important que le programmeur crive dans son code des commentaires pertinents. Une faon de faire est de mettre le caractre #: tout ce qui suit sur la ligne ne sera ignor
par linterprteur.
# calcule le pourcentage de lheure coule
percent = (minute * 100) / 60
v = 5
# vitesse en mtres / secondes
Pour avoir des commentaires plus long quune ligne ou un fin de ligne, les commentaires multilignes peuvent tre utiliss
2.8. input()
11
"""
Exemple de commentaire multiligne
que lon peut mettre dans un programme Python
...
"""
Nous verrons que les commentaires multilignes permettent de documenter les fonctions crites
par le programmeur qui pourra redemander ces informations plus tard.
Attention, ici la virgule est un dlimiteurs des lments dune liste et srement pas le dlimiteur entre la partie entire et la partie fractionnaire dun nombre (Python utilise la convention
scientifique et anglaise pour cela).
12
#
#
#
#
rentrer
calcule
calcule
imprime
la donne
la circonfrence
la surface
les rsultats
ou par exemple
>>> import math as m
>>> m.cos(m.pi/4)
13
0.70710678118654757
>>> m.log(1024, 2)
10.0
ou encore
>>> from math import pi, cos, log
>>> cos(pi/4)
0.70710678118654757
>>> log(1024, 2)
10.0
Warning: Python permet de faire limportation de tous les lments dun module (exemple:
from math import *): ceci est fortement dconseill car
ne permet pas de savoir do vient les lments que lon utilise ensuite,
peut cacher des lments existants qui ont le mme nom
rend le code difficile debugger quand un symbole est indfini
peut provoquer des clashs entre plusieurs noms
Warning: Apprendre python : Plus important que davoir une connaissance encyclopdique de Python, il est important de pouvoir trouver linformation que lon cherche
et donc avoir une bonne mthode de recherche dinformation. Une recherche du contenu du
module math via dir(math), help(math), une recherche rapide (quich search) ou approfondie dans la documentation python (Tutorial, Library Reference, Language Reference)
ou un bon livre sur python est un bon exemple pour vous entraner. La mthode exprimentale (tester ce que fait une fonction, ...) constitue un complment important toutes ces
dmarches.
14
variable
objet contenant
la valeur w
Attention: dans une instruction dassignation, la variable assigne est toujours gauche sur
signe = et la valeur toujours droite !
Dans lexemple:
>>>
>>>
>>>
>>>
>>>
>>>
x
y
z
x
y
z
=
=
=
=
=
=
3
12
x
2 * x
2 * y
x * y
z
x
12
A la fin du programme entier, 5 objets (de type) entiers ont t crs, dont ceux valant 6, 24 et
144 sont rfrencs respectivement par les variables x, y et z. Les objets valant 3 et 12 ne sont
plus accessibles et donc potentiellement rcuprs par le systme (garbage collector).
15
12
24
144
inaccessible et donc
rcupr par le systme
2.13.1 Incrmentation
Lincrmentation (respectivement la dcrmentation) dune variable x est le fait daugmenter
(resp. diminuer) sa valeur (gnralement dune unit).
le diagramme dtat de
>>> x = 3
>>> x = x + 1
donne donc:
16
CHAPTER
THREE
a, b = 3, 7
a = b
b = a
print(a,b)
a, b = 3, 7
b = a
a = b
print(a,b)
Lordre dexcution, appel flux dexcution, peut tre modifi par des instructions dites composes. Nous allons voir ici les instructions conditionnelles (if) et les instructions rptitives
(while, for). Ce chapitre prsente les instructions if, while et for.
a > 100 est appele la condition du test if. Cest une expression boolenne qui peut donc
tre value vrai ou faux. Si la condition est vraie, ce qui dpend du if est excut.
17
>>> a = 20
>>> if (a > 100):
...
print("a dpasse la centaine")
... else:
...
print("a ne dpasse pas cent")
...
Reprenons le calcul des ventuelles racines dune quation du second degr. Aprs avoir lu les
donnes du problme, cest--dire les valeurs a, b et c, il faut calculer le delta et tester sil
est ngatif, nul ou positif. Le code du programme donne :
"""
Calcul des racines ventuelles dune quation du second degr
"""
__author__="Thierry Massart"
__date__="22 aot 2012"
from math import sqrt
a= float(input(valeur de a : ))
b= float(input(valeur de b : ))
c= float(input(valeur de c : ))
delta = b**2 - 4*a*c
if delta < 0:
print(" pas de racines relles")
elif delta == 0:
print("une racine : x = ", -b/(2*a))
else:
racine = sqrt(delta)
print("deux racines : x1 = ",
(-b + racine)/(2*a), " x2 = ", (-b - racine) / (2*a))
On a donc les trois mots-cls if, else et elif; ce dernier est donc la contraction dun else
et dun if. Noubliez pas de terminer la ligne den-tte du if, else, elif par le caractre
:.
Note: En Python il est prfrable de mettre une instruction par ligne sauf si linstruction prend
trop de place et prend plusieurs ligne (auquel cas, parfois il est ncessaire de terminer la ligne
par le caractre \ qui indique que linstruction continue sur la ligne suivante. Le ; permet
galement de sparer les instructions dune mme ligne.
Lindentation (dcalage de certaines instructions de quelques - on conseille 4 - caractres) est
essentielle en Python car il dtermine quelle(s) instruction(s) dpendent de la condition.
Note: Les oprateurs relationnels Python sont :
==, !=, <, >, <=, >=, is, is not, in.
18
b
False
True
False
True
not a
True
True
False
False
a and b
False
False
False
True
a or b
False
True
True
True
Les lois de De Morgan sont frquemment utilises pour simplifier les tests; ayant des expressions logiques A et B
1) not (A or B) == (not A) and (not B)
2) not (A and B) == (not A) or (not B)
Ainsi la place de not ((x >= 0) and (x <10)) on crira x < 0 or x >= 10
3.1.1 If imbriqus
Lindentation est trs importante et peut tre une source derreur en cas dinstructions if (ou
while, for) imbriques.
Le code suivant :
if a > 0 :
if b > 0 :
print("cas 1")
else :
print("cas 2")
imprime cas 1 quand a et b sont positifs, cas 2 quand a est positif et b ngatif ou nul et
nimprime rien si a est ngatif ou nul. Le else dpend du second if.
Le code suivant :
if a > 0 :
if b > 0 :
print("cas 1")
else :
print("cas 2")
imprime cas 1 quand a et b sont positifs, cas 2 quand a est ngatif ou nul et donc rien quand
a est positif et b ngatif ou nul. Le else dpend du premier if.
19
o
expression est une expression boolenne,
suite un bloc dinstructions (indentes)
( ... )\* est une mta-notation signifiant que la ligne peut ne pas tre mise, mise
une ou plusieurs fois
[...] est une mta-notation signifiant que la ligne est optionnelle, cest--dire peut tre
ou ne pas tre mise.
3.1.4 is
loprateur is peut tre utilis: il teste si deux variables rfrencent le mme objet
>>> x=3
>>> y=3
>>> x is y
True
>>> z = x
>>> x is z
True
>>> x = x + 1
>>> x is y
False
Ce code montre que lobjet entier contenant la valeur 3 nest pas cr 2 fois, ce qui serait une
perte de temps et despace mmoire. Par contre aprs incrmentation x = x + 1, x et y
rfrencent bien sr 2 objets diffrents (y vaut 3 et x vaut 4).
20
imprime :
5
7
9
11
exemple termin
21
nous aurons
pgcd(102, 30) = 6
Le programme Python calculant le pgcd de 2 nombres entiers positifs est donn la figure
ci-dessous
"""
calcule le pgcd de 2 nombres entiers positifs
"""
x = int(input("Introduisez le premier nombre entier positif : "))
y = int(input("Introduisez le second nombre entier positif : "))
while (y > 0):
x, y = y, x % y
print("Le pgcd vaut: ", x)
La table dtat suivante donne les valeurs des variables durant les diffrentes phases de
lexcution du programme
instruction
x = int(input(...
y = int(input(...
x,y = y, x%y (1re it
x,y = y, x%y (2me it)
x,y = y, x%y (3me it)
print(...
x
102
102
30
12
6
6
y
?
30
12
6
0
0
n = int(input(entier positif : ))
while n != 1:
print(n, end= )
if n % 2 == 0:
n = n//2
else:
n = n*3+1
avec n = 27795317865557576576432145678
22
", res)
Note: Notons que si la condition est fausse au dbut de lexcution dun while, linstruction
ne sera jamais excute. Inversment si la condition du while ne devient jamais fausse,
linstruction while continuera sexcuter indfiniment et ceci jusqu ce que le processus
qui excute le programme soit tu cest--dire arrt de faon brutale par le programmeur ou
le superviseur de lordinateur.
Tout programmeur novice va tt ou tard avoir affaire un tel programme qui cycle. Enfin
notons quil se peut que la condition devienne fausse au milieu de lexcution de linstruction
while. Ce nest qu la fin de lexcution de linstruction que la condition est rvalue. Ainsi
dans le programme Python de la figure suivante, le corps de la boucle while est excut 4 fois.
i = 0;
print("Dbut du programme")
while i < 4 :
i += 20
print(i)
i -= 19
print("termin")
o
expression est une expression boolenne,
suite un bloc dinstructions (indentes)
[...] est une mta-notation signifiant que la ligne est optionnelle, cest--dire peut tre
ou ne pas tre mise.
Si la partie else est prsente, elle est excute une seule fois quand la condition devient fausse.
23
Un container est une donne compose de plusieurs donnes plus simples (exemple: chane de caractre,
liste, tuple, dictionnaire)
24
CHAPTER
FOUR
DFINITION DE NOUVELLES
FONCTIONS
See Also:
Lire le chapitre 7 du livre de Grard Swinnen sur Python 3
Python permet de dcouper les programmes en fonctions. Chaque fonction cre peut tre
vue comme un outil rsolvant un certain problme. Les autres fonctions peuvent utiliser cet
outil sans se soucier de sa structure. Il leur suffit, pour pouvoir lutiliser, de savoir comment
employer cet outil, cest--dire, comme nous le verrons ci-dessous, de connatre le nom de la
fonction, les objets (valeurs, variables) quelle ncessite et la faon dont elle renvoie un ou
plusieurs rsultats.
Cette technique a en particulier deux avantages:
chaque fonction peut (gnralement) tre teste indpendamment du reste du programme;
si une partie contient une squence dinstructions qui doit tre ralise diffrents endroits du programme, il est possible de ncrire cette squence quune seule fois.
En gros, une fonction peut tre vue comme une opration dont la valeur est dfinie par le
programmeur. Notons que, dans les chapitres prcdents, nous avons dj vu quen Python, il
existe des fonctions prdfinies que le programmeur peut utiliser. Ainsi par exemple print(),
float(), cos() sont des fonctions; comme on la vu, cette dernire est prdfinie dans le module
math et doit tre importe avant de pouvoir tre utilise.
25
x,y = y, x%y
return x
o
"""Un commentaire quelconque
qui peut prendre plusieurs lignes
"""
On aura
sum(3,5) renvoie 8 qui est de type int
sum("bon","jour") renvoie bonjour qui est de type str (string)
26
sum("bon",5) gnre une erreur de type (lve une exception lors de lexcution de la
somme)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 2, in sum
TypeError: Cant convert int object to str implicitly
Note: On dit communment dune fonction qui renvoie un rsultat dun type x, que cest une
fonction de type x ou une fonction x (par exemple une fonction entire).
Note: Dans le vocabulaire des langages de programmation, une fonction qui peut faire des
choses diffrentes en fonction du type des arguments, est dite surcharge. La fonction sum est
un exemple simple de fonction surcharge qui tantt effectue une somme, tantt une concatnation de texte.
27
Note: Par dfaut une fonction renvoie la valeur None qui symbolise labsence de valeur.
Cela signifie que return sans expression donnant une valeur la fin quivaut return
None.
Par ailleurs, un return implicite existe la fin de toute fonction.
Donc aprs avoir dfini print_line, le code :
>>> print(print_line(5,7))
35
None
28
"""
La raison est que x et y sont des variables locales qui rfrencent les objets contenant les
valeurs, mais que la fonction ne modifie ni les objets, ni les rfrences donnes lors de lappel.
La solution est que les valeurs soient renvoyes en rsultat.
4.4. Excution de la fonction appele (passage de paramtres par valeur)
29
def min_et_max(x,y):
"""Renvoie min(x,y) suivit de max(x,y) """
if x > y:
x,y = y,x
return x,y
a=int(input("premire valeur : "))
b=int(input("seconde valeur : "))
print(a,b)
a,b = min_et_max(a,b)
print(a,b)
On parle de la porte (scope) des variables : zone du programme dans laquelle elle est
disponible. La porte dune variable locale ou dun paramtre est limite sa fonction.
4.5.1 Traceback
Lorsquune erreur se produit lors de lexcution dun programme Python lutilisateur reoit un
message derreur qui commence par Traceback (most recent call last):
Pour identifier o a eu lieu lerreur, le message retrace dans quelle fonction f0 et o a eu lieu
lerreur ainsi que, si cest le cas, la fonction f1 et le lieu o f0 a t appele, et ainsi de suite.
Par exemple:
def ma_fun():
une_autre_fun()
def une_autre_fun():
encore_une_fun()
def encore_une_fun():
# une_erreur utilis sans avoir t dfinie auparavant
une_erreur= une_erreur + 1
ma_fun()
donnera:
31
Cela peut tre intressant ou essentiel dans certain code. Ceci sera illustr dans un chapitre
ultrieur dans un code qui dessine une fonction, celle-ci tant donne en paramtre, dans un
certain intervalle.
Par ailleurs, laspect dynamique de Python permet galement de dfinir des nouvelles fonctions
lors de lexcution et davoir des variables qui rfrencient ces fonctions. En particulier on peut
utiliser des dfinition lambda, par exemple
>>> f = lambda x : x**2 - 3.0*x
>>>
# Dfinit une fonction (x^2-3x) rfrence par la variable f
...
>>> print(f(2.0)) # appel f(2.0) et imprime le rsultat
-2.0
32
Matire avance
CHAPTER
FIVE
CHANES DE CARACTRES
(STRINGS), TUPLES, LISTES ET
INSTRUCTION FOR
See Also:
Lire les chapitres 5 et 10 du livre de Grard Swinnen sur Python 3
Python manipule des types de donnes non simples cest--dire o une donne est forme de
parties. Nous allons tudier ici les types de donnes qui forment des squences : les chanes de
caractres (strings) que nous avons dj prsentes, ainsi que les listes, et les tuples.
Nous avons dj vu que les strings pouvaient tre concatns a+b ou rpts a*5.
On peut galement comparer 2 strings: lordre de la codification unicode UTF-8 est utilise
Les composantes (caractres) dun string s sont indices de 0 len(s) o len() est une
fonction prdfinie qui donne le nombre de caractres dans le string.
Warning:
Donc quand len(s) vaut 5 on peut manipuler s[0] s[4] (=
s[len(s)-1]).
33
Python permet aussi dutiliser des indices ngatifs sachant que s[-1] est le dernier caractre du string s, s[-2] lavant dernier ....
On peut aussi avoir une tranche (slice) de s (exemple: s[2:5] correspond la partie de s
depuis le caractre dindice 2 compris jusquau caractre 5 non compris.
s[:j] est synonyme de s[0:j] et s[i:] est synonyme de s[i:len(s)].
Enfin, on peut prendre certains lments, par exemple :
s[::2] est le string form des caractres pairs de s ou
s[::-1] est le string form de tous les caractres de s mais dans lordre inverse.
>>> s = "bonjour"
>>> print(len(s))
7
>>> print(s[1])
o
>>> print(s[-1])
r
>>> print(s[2:5])
njo
>>> s2 = s[::-1]
>>> print(s2)
ruojnob
>>> print(s[::2])
bnor
>>> print(len(s))
7
>>> print(s[-len(s)])
b
>>> s3 = B+s[1:]
>>> print(s3)
Bonjour
>>> print(s[:3]*2)
bonbon
>>> vide=""
>>> len(vide)
0
Ayant "bonjour" dans la variable greetings, le code correct pour mettre la premire
lettre en majuscule est :
>>> greetings = "B" + s[1:]
34
greetings
imprime G.i.l.l.e.s..
Le for ... in peut galement tre utilis avec les autres types de squences (tuples, listes) et
galement les dictionnaires (voir plus loin dans la matire).
5.1.2 Le test in
permet de tester si un lment appartient une squence. Par exemple :
car = "a"
voyelles = "aeiouyAEIOUY"
if car in voyelles:
print(car, " est une voyelle.")
35
imprimera :
Josephine passe aprs !
48 57 65 66 97
suivi des 20000 premiers caractres (certains ne sont pas imprimables) dans la codification
UTF-8.
Notez que certains caractres ne sont pas imprimables proprement parler: par exemple print(chr(7)) a comme effet denvoyer le code de signal (beep) au haut-parleur de
lcran. Dautres caractres reprsentent des pictogrammes: par exemple les codes 9812
9823 reprsentent les pices du jeu dchec.
5.2 Tuples
Un tuple est une squence immuable dlments; chaque lment pouvant tre du mme type
ou dun type diffrent.
mes_nombres_lotto = 7, 21, 27, 32, 35, 41
x=int(input("nombre gagnant : ")
if x in mes_nombres_lotto:
print("le ", x," est gagnant et est dans mes nombres ", mes_nombres_lotto)
Les tuples peuvent , par exemple, servir pour assigner plusieurs valeurs en une seule assignation
multiple
a,b = b, a # permute les valeurs de a et de b
36
if x > y:
x,y = y,x
return x,y
a=int(input("premire valeur : "))
b=int(input("seconde valeur : "))
print(a,b)
a,b = min_et_max(a,b)
print(a,b)
Notez que habituellement, on entoure les lments du tuple par des parenthses pour mieux
identifier les lments
...
(x,y) = (y,x)
return (x,y)
Les oprateurs + (concatnation) et * (rptition) et in ainsi que le slicing t[i:j] fonctionnent comme avec les strings. La comparaison de 2 tuples est similaire ce qui se passe avec
les strings (par exemple (1,2,3) < (1,2,3,4) est vraie).
Lassignation peut dfinir un tuple dont les lments sont les valeurs donnes droite du symbole = dassignation,
>>> s = 1,2,3
Cest ce que lon appelle le packing. Linverse (unpacking) est galement possible, quand ayant
une squence (tuple ou string ou liste,...) de n lments, on demande dassigner n variables
les valeurs de ces n lments:
>>> s=(1,2,3)
>>> print("s =", s)
s = (1, 2, 3)
>>> a,b,c = s
# unpack les 3 valeurs dans respectivement a, b et c
>>> print("a = ", a)
a = 1
>>> print("b = ", b)
b = 2
>>> print("c = ", c)
c = 3
>>> d, g = s
# s a 3 composantes !!!
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: too many values to unpack (expected 2)
37
ments non simples comme des strings, listes, tuples, dictionnaires (voir plus loin), ....
>>> mon_tup = bon, voici, 1, exemple, (2,3)
>>> print(mon_tup)
(bon, voici, 1, exemple, (2, 3))
>>> len(mon_tup)
5
>>> print(mon_tup[4])
(2, 3)
>>> len(mon_tup[4])
2
>>> a,b,c,d,e=mon_tup
>>> print(a)
bon
Note: Le tuple contenant un seul lment (par exemple 3 se note (3,). Le tuple vide de note
() (exemple t = ())
5.3 Listes
Un liste Python est une squence que lon peut modifier (muable) dlments, chaque lment
pouvant avoir le mme type ou un type diffrent des autres :
>>> ma_liste = [1,3,7]
>>> ma_liste[0] = 2
2
ma_liste
>>> ma_liste=[3,7,21,42]
>>> print(ma_liste)
[3, 7, 21, 42]
>>> print(len(ma_liste))
4
>>> empty=[]
# liste vide
>>> type(empty)
<type list>
>>> len(empty)
38
0
>>> data=[bon,"jour",0,1,[2,3,4]]
>>>len(data)
5
>>> type(data[0])
<type str>
>>> type(data[4])
<type list>
>>> data[4]=666
>>> print(data)
[bon, jour, 0, 1, 666]
>>> print(data[-1])
666
data
0
1
2
'b'
'o'
'n'
0
1
2
3
'j'
'o'
'u
'r'
666
Ici aussi, les oprateurs + (concatnation) et * (rption) et in fonctionnent comme avec les
strings. La comparaison de 2 tuples est similaire ce qui se passe avec les strings (par exemple
[1,2,3] < [1,2,3,4] est vraie).
Contrairement aux strings et aux tuples, cette squence est modifiable: chaque lment (composante) de la squence peut tre modifi. On peut aussi rajouter des lments ou en supprimer
:
>>> data=["bon","jour",0,1,[2,3,4], (7,8)]
>>> len(data)
6
5.3. Listes
39
imprime
[36, 3, 7]
[36, 3, 7]
[1, 3, 7]
Le type de copie que nous venons de prsenter sappelle shallow copy (copie superficielle).
Nous verrons plus bas que pour des listes complexes, un shallow copy peut ne pas tre suffisant
et quun deepcopy devra tre effectu.
40
en dbut du chapitre pour obtenir la dernire version pdf imprimable sur une feuille A4 recto
verso.
est quivalent :
>>> s[len(s):len(s)] = [37]
ou encore :
>>>
ou :
>>>
De mme:
>>> s[0:1] = []
est quivalent :
5.3. Listes
41
Egalement :
>>> del s[len(s)-1]
est quivalent :
>>> s[len(s)-1:] = []
Le programmeur a donc intrt dcider une fois pour toute quil utilise toujours la mme
faon de faire pour raliser un certain traitement, et sy tenir.
Warning: Il est interdit de manipuler en lecture (essayer de prendre la valeur de
llment) ou en criture (essayer de changer la valeur) une composante inexistante dune
liste s cest--dire en dehors de lintervalle 0 .. len(s)
>>> s= [a,b,c]
>>> s[3] = d
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: list assignment index out of range
>>> print(s[3])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: list index out of range
En particulier pour tendre une liste, il faut donc utiliser par exemple une des mthodes vues
plus haut (append, extend, slicing).
42
est de crer une liste de 3 objets entiers (valant 1, 2 et 3), de mettre dans s la rfrence
cette liste et ensuite de donner la mme rfrence t; et donc s is t rpond True.
Donc s et t rfrencent la mme liste comme le montre le diagramme dtat suivant:
Donc s[1] = 36 modifie la liste et donc print(s) et print(t) impriment tous les 2 [1,36,3].
Quand on utilise s[i:j] = l2 pour certains indices i et j et une liste l2 donns, ou del
s[i] ou encore s.append(v), on modifie la liste s (et donc t).
Rappelons que le test s is t (qui rpond donc True ou False) permet de savoir si s et
t rfrencent le mme objet.
Si lon fait par exemple:
>>> s = s + [37]
on cre une nouvelle liste avec les lments de lancienne liste s et la liste [37]. s reoit
la rfrence la nouvelle liste. Donc s rfrence cette nouvelle liste, t rfrence toujours
lancienne (s is t vaut False).
5.3. Listes
43
Warning: Cette faon de faire a beaucoup davantages, mais est une source derreur importante !!
Le code suivant:
>>> s= [1,2,3]
>>> t = s
>>> s[1] = 36
>>> s
[1,36,3]
>>> t
[1,36,3]
>>> t is s
True
>>> s = s + [47]
>>> s
[1,36,3,47]
>>> t
[1,36,3]
>>> s is t
False
36
36
47
Note: Plus prcisment, chaque constante (1, 3, 36,...) nest cre quune seule fois (un
objet) et si une composante dune squence a cette valeur, Python implmente cela comme une
rfrence vers cet objet ayant cette valeur (voir diagrammes dtat suivants).
44
5.3.5 range()
La fonction range() gnre une squence de valeurs entires.
On a dj vu que
for i in range(10):
print(i, end=" " )
imprime : 0 1 2 3 4 5 6 7 8 9
La fonction range() est un itrateur, cest--dire une fonction qui gnre une squence
dlments; range() gnre une squence dentiers.
range() peut avoir 2 ou mme trois arguments donnant le nombre de dpart, la borne et le
pas qui peut tre positif ou ngatif. Par dfaut le nombre de dpart vaut 0 et le pas vaut 1. Les
arguments doivent tre des nombres entiers.
Notons quil est possible dutiliser la fonction list() avec la fonction range(), pour
obtenir la liste des lments correspondants.
>>> t = list(range(10))
>>> print(t)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
5.3. Listes
45
Le code suivant illustre comment manipuler lindice de la squence, en mme temps que
llment.
>>>
>>>
...
...
0
1
2
3
4
5
6
7
8
9
10
46
Note: Il est possible dcrire les rsultats dans un format plus propre (par exemple, en rservant
systmatiquement 3 espaces pour une donne ou en demandant dimprimer le rsultat rel avec
une certaine prcision). Voir livre de Grard Swinnen, section formatage des chanes de
caractres.
Notez que si on a, par exemple, une liste de strings, on peut avec deux for imbriqus, passer
en revue tous les caractres de chaque string.
>>> ma_liste = ["bon", "jour", " tu vas ", " bien"]
>>> for s in ma_liste:
...
for c in s:
...
print(c, end =" ")
...
b o n j o u r
t u
v a s
b i e n
Le premier for assigne s chaque string de ma_liste, le for imbriqu, assigne c chaque
caractre du string mis dans s.
47
5.5.1 zip
Cette fonction peut tre bien pratique quand on veut parcourir deux ou plusieurs squences en
parallle. Par exemple le code suivant est quivalent au code vu un peu plus haut :
>>>
>>>
...
...
0
1
2
3
4
5
6
7
8
9
10
Notez que zip peut recevoir plus de deux squences, et quil sarrte ds que la plus courte est
puise.
>>>
>>>
...
...
(1,
(2,
(3,
la place de :
>>> squares = []
>>> for x in range(10):
...
squares.append(x**2)
...
48
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
De mme :
>>> combs = [(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]
>>> combs
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]
est quivalent :
>>>
>>> combs = []
>>> for x in [1,2,3]:
...
for y in [3,1,4]:
...
if x != y:
...
combs.append((x, y))
...
>>> combs
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]
49
avec s[2] et t[2] modifis de la mme faon puisquils rfrencent la mme sous liste.
Le diagramme dtat prcis correspondant donne :
36
1
2
5
777
t
0
0
1
2
La sous liste rfrence par t[2] (et par s[2]) est donc modifie.
Cest pour cette raison que ce type de copie est dit superficiel (shallow copy).
Si lon dsire une structure totalement spare, mme au niveau des sous-listes, la fonction
deepcopy du module copy peut tre utilise :
50
36
1
2
5
777
t
0
0
1
1
2
7
9
0
1
Notez que les objets immuables (comme les constantes 1, 5, ...) ne sont pas recopis puisquici
aucun risque nest possible, tant donn justement quils ne sont pas modifiables.
51
>>> s = list(range(3))
>>> s[0] = s
>>> print(s)
[[...], 1, 2]
Dans le print, le [...] signifie une rfrence cyclique une liste sans plus de prcision.
Le diagramme dtat correspondant s en fin de code donne :
Le code suivant :
>>> s = list(range(3))
>>> t = list(range(2))
>>> s[0]= t
>>> t[0] = s
>>> t[1] = t
>>> s[1] = s
>>> print(s)
[[[...], [...]], [...], 2]
Ici, [...] signifie tantt une rfrence valant s tantt une rfrence valant t.
Ce code donne la structure reprsente par le diagramme dtat suivant:
52
0
1
Tout ceci peut vous paratre dans un premier temps assez compliqu: le chapitre suivant revient
sur des choses plus abordables en passant en revue des algorithmes utilisant des squences plus
simples.
Note: Le mot conteneur (container) est utilis pour signifier un objet qui rfrence dautres
objets. Les listes, tuples (mais aussi dictionnaires) sont des exemples de conteneurs.
53
54
CHAPTER
SIX
CONCEPTION DALGORITHMES
SIMPLES
See Also:
Lire les chapitres 5 et 10 du livre de Grard Swinnen sur Python 3
55
Si lon estime quune prcision eps donne (exemple: eps = 1.0 e-8) est suffisante, il
faut donc crire un programme qui calcule e avec une erreur infrieure la constante eps
cest--dire de sommer les termes 1/i! jusqu ce que 2/(i+1)! < eps.
Lalgorithme devra donc calculer :
1 + 1/1! + 1/2! + ... + 1/n!
avec 2/n! <= eps et 2/(n+1)! < eps
ce qui ne peut pas tre fait en une seule instruction puisque le nombre n nest pas connu a priori.
Il semble naturel de dcomposer lalgorithme en une rptitive qui calcule chaque tour de
boucle un nouveau terme et qui teste si ce nouveau terme doit tre inclus dans lapproximation.
Le canevas gnral sera alors donn par le code suivant :
"""
Approximation de la valeur de e
"""
eps = 1.0e-8
n = 1
e = 1.0
terme = 1.0
while 2*terme >= eps:
e += terme
n += 1
... # calculer le terme 1/n! suivant
print("lapproximation de e = ", e)
la valeur n! grandit trs rapidement avec n, ce qui peut ne pas tre trs efficace pour les calculs.
Remarquons que :
fact_n = 0
for i in range(1,n+1):
fact_n *= i
Approximation de la valeur de e
"""
eps = 1.0e-8
n = 1
e = 1.0
56
terme = 1.0
while 2*terme >= eps :
# n = prochain indice, e = val jusque n-1, terme = terme dindice n
fact_n = 1
e += terme
n += 1
for i in range(2,n+1):
fact_n *= i
terme = 1/fact_n # calcul du terme 1/n! suivant
print("lapproximation de e = ", e)
Etant donn quau nime tour de boucle on calcule n!, on voit aisment que lon peut diminuer
le nombre de calculs: il suffit de reprendre la valeur du terme obtenu au tour prcdent et de
la diviser par n.
On obtient la version amliore suivante :
"""
Approximation de la valeur de e
"""
eps = 1.0e-8
n = 1
e = 1.0
terme = 1.0
while 2*terme >= eps : # n = prochain indice, e = val jusque n-1, terme = terme
e += terme
n += 1
terme /= n # calcul du terme 1/n! suivant
print("lapproximation de e = ", e)
Remarquons, dans le code, que le nom des objets (e, terme, n, eps, ... ) donne une ide de leur
usage. De plus, ce programme est comment et proprement indent. Ces pratiques facilitent la
tche de toute personne qui doit comprendre le fonctionnement du programme.
Warning: Une chose essentielle galement pour comprendre le fonctionnement du while
est de dcrire la situation chaque fois que lon va faire le test (ici: 2*terme >= eps):
ici on explique que lorsque lon fait ce test, que le rsultat soit True ou False,
n contient le prochain indice que lon va considrer pour la srie,
e contient lvaluation de la srie jusque lindice n-1,
terme contient le terme suivant, cest--dire dindice n
chaque itration, cette description est vraie; ce qui change dune itration lautre, est
lindice n (n += 1) et donc le fait que lon avance dans lvaluation.
57
import math
__author__ = "Thierry Massart"
__date__ = "16 september 2011"
EPSILON =10**-20
def almost_equal(x, y, EPS = 10 ** -7):
return abs(y - x) < EPS
def square_root(a):
"""Calcul de la valeur approche de la racine carre de a
Par la mthode de Hron
"""
x = 0.0
y = 1.0
while not almost_equal(x, y,EPSILON):
# rq : pas almost_equal(a,y*y,epsilon) qui peut cycler
x = y
y = (y + a / y) / 2
return y
help(square_root)
print("valeur calcule par la mthode de Hron : \t" \
"{0:20.18}".format(square_root(2)))
print("valeur calcule par le module math :
\t" \
"{0:20.18}".format(math.sqrt(2)))
58
imprime: [o, e, s]
59
x = input()
return res
print(lecture("liste dentiers termine par une ligne vide : "))
La mthode readline invoque sur un objet fichier permet de lire une ligne. Lors de la
premire invocation, la premire ligne est retourne. Lors de linvocation suivante de cette
mme mthode, la prochaine ligne sera lue.
>>> fichier.readline()
aa\r\n
>>> fichier.readline()
aah\r\n
Une boucle for peut tre utilise pour lire les lignes dun fichier de texte une une.
>>> for line in fichier:
...
print(line.strip())
aahs
aal
aalii
aaliis
...
zymoses
zymosis
zymotic
zymurgies
zymurgy
Problme: crivez un script qui lit le fichier words.txt et qui naffiche que les mots qui ont plus
de 20 caractres (sans compter les caractres blancs).
Solution :
fichier = open(words.txt)
for line in fichier:
word = line.strip()
if len(word) > 20:
print(word)
Problme: en 1939, Ernest Wright a publi une nouvelle de 50000 mots appele Gadsby qui ne
contient pas la lettre e. Comme e est la lettre la plus commune en anglais (et dans dautres
langues), ce ntait pas une tche facile. Ecrivez un script qui naffiche que les mots qui ne
contiennent pas de e et calculez le pourcentage de ceux-ci par rapport lensemble des mots
du fichier words.txt.
Notez que Georges Perec a fait le mme exercice en franais, dans son livre La disparition
(1969) o il dfinit ce qui a disparu comme un rond pas tout fait clos, fini par un trait
horizontal.
Solution :
fichier = open(words.txt)
total = 0
cnt = 0
for line in fichier:
total = total + 1
word = line.strip()
if e not in word :
print(word)
cnt = cnt + 1
print(Pourcentage de mots sans e:, cnt / total * 100.0)
Problme:
Donnez un mot anglais avec 3 doubles lettres conscutives. Je vous donne un couple de mots
qui sont presque candidats, mais pas tout fait. Par exemple, le mot committee serait parfait
sil ny avait pas ce i au milieu. Ou Mississippi : si on retirait les i, cela marcherait. Il y
6.2. Manipulation de squences
61
a cependant au moins un mot qui possde trois paires conscutives de lettres. Cest peut-tre le
seul mot, ou il peut y en avoir 500.
Problme:
Ecrire un script qui demande lutilisateur le nom dun fichier de texte (.txt), puis affiche les
mots contenus dans le fichier par ordre alphabtique (grce une liste). Un mme mot ne peut
pas tre affich deux fois. Tous les caractres qui ne sont pas des lettres ou des chiffres seront
supprims dans la cration de la liste de mots.
Hints :
la mthode isalnum invoque sur une chane retourne vrai ssi tous les caractres de la
chane sont des lettres ou des chiffres.
la mthode split invoque sur une chane retourne une liste des mots de la chane (c--d
les sous-chanes spares par des caractres blancs (Espaces, retours la ligne, tabulations, etc.)). On peut spcifier dautres sparateurs que des blancs avec le paramtre
optionnel sep.
Solution :
filename = input(Nom du fichier: )
file = open(filename)
wordsList = []
for line in file:
for word in line.split():
cleanWord = keepAlnum(word)
if not cleanWord in wordsList:
wordsList.append(cleanWord)
wordsList.sort()
print(wordsList)
62
Pour passer un argument qui contient des espaces, on peut le mettre entre apostrophes.
La commande
python3 args.py un deux trois "x + y"
initialise la liste sys.argv :
[args.py, un, deux, trois, x + y]
6.3.2 eval
Python tant un langage interprt, fournit une fonction eval(exp) qui value le string
exp donn en paramtre comme sil sagissait de code supplmentaire.
Cela permet par exemple dcrire un script Python qui reoit en paramtre un polynme
p et une valeur x et calcule la valeur p(x).
"""
utilisation : python3 eval-poly.py p x
o p reprsente un polynme en format python (ex: 3*x**2+2*x-2)
sans espace entre les valeurs et les oprateurs
x donne la valeur pour laquelle on veut la valeur p(x)
"""
import sys
p = sys.argv[1]
x = float(sys.argv[2])
print(eval(p))
63
Effet
On efface tout et on recommence
Aller lendroit de coordonnes x, y
Avancer dune distance donne
Reculer
Relever le crayon (pour pouvoir avancer sans dessiner)
Abaisser le crayon (pour recommencer dessiner)
couleur peut tre red , blue, etc.
Tourner gauche dun angle donn (exprim en degrs)
Tourner droite
Choisir lpaisseur du trac
Dbut de la zone ferme colorier
Fin de la zone ferme colorier
texte doit tre une chane de caractres
Aprs avoir install turtle et fait import turtle, nhsitez pas utiliser
help(turtle.write) par exemple pour avoir les dtails des fonctions (tailles des
caractres crits, alignement, ...).
Ecrire une fonction poly(n,long,t) qui reoit deux entiers n et long et le module turtle et qui
dessine un polygone rgulier n cts, chacun de longueur long.
import turtle
def poly(n,long,t):
for i in range(n):
t.forward(long)
t.left(360/n)
turtle.reset()
for i in range(3,12):
poly(i,50,turtle)
x=input(tapez return pour terminer : )
Modifiez votre code pour produire des toiles un nombre impair (et ensuite pair) de branches.
constante"""
def multiply(p1,p2):
""" Renvoie le produit de 2 polynmes"""
if len(p1) > len(p2):
p1,p2 = p2,p1
new = []
for i in range(len(p1)):
new = add(new,mult_one(p2,p1[i],i))
return new
def mult_one(p,c,i):
"""Renvoie le produit du polynme p avec le terme c*x^i
"""
new = [0]*i #termes 0 jusque i-1 valent 0
for pi in p:
new.append(pi*c)
return new
def power(p,e):
"""Renvoie la e-ime puissance du polynme p"""
65
D(y)
arctan(D(y)/D(x))
D(x)
arctan(D(y)/D(x))
D(y)
D(x)
import sys
from math import *
import turtle
def dessin_fun(t,f):
"""
exemple simple de trac dune fonction entre 2 bornes (ici -100,100)
"""
t.radians()
borne_inf = -100 # valeur impose pour simplifier le code
borne_sup = 100 # valeur impose pour simplifier le code
67
Un code plus labor est disponible ici. Il est utilis avec la commande
python3 dessin_f.py f bi bs zoom
o
f est la fonction tracer
bi la borne infrieure de lintervalle o f est trace
bs la borne suprieure de lintervalle
zoom : le zoom pour le dessin
dessin_f.py trace les axes pour les valeurs -200..200 et utilise un incrment de 0.1 pour x.
Pour cela, la fonction range est remplace par un gnrateur drange dfini dans le code. Un
gnrateur est une sorte de fonction qui gnre une squence: pour cela il remplace le return
habituel par la commande yield pour fournir les valeurs successives.
Note: les librairies pylab, numpy, scipy et mathplotlib permettent (!! en python 2.7 !!) de
faire des calculs numriques et des dessins en particulier en utilisant de nombreuses fonctions
disponibles.
68
x=[[1,2,3],[4,5,6]]
y=[[1,2],[4,5],[7,0]]
print("le produit vaut : ", produit(x,y))
Une version plus simple, cre la matrice rsultat avec des valeurs 0 au dpart et ensuite calcule
les bonnes valeurs:
def produit(a, b):
"""
Produit de la matrice a par la matrice b
Hypothse a: m x l - b : l x n (produit possible)
"""
c = [[0 for i in range(len(b[0]))] for j in range(len(a))]
for i in range(len(a)):
for j in range(len(b[0])):
for k in range(len(a[0])):
c[i][j] += a[i][k] * b[k][j]
return c
x=[[1,2,3],[4,5,6]]
y=[[1,2],[4,5],[7,0]]
69
70
CHAPTER
SEVEN
ENSEMBLES ET DICTIONNAIRE
See Also:
Lire le chapitre 10 du livre de Grard Swinnen sur Python 3
7.1 Set
Le type ensemble (set) existe en Python y compris de nombreux oprateurs ensemblistes (exemple venant du tutoriel de python.org):
>>> basket = {apple, orange, apple, pear, orange, banana}
>>> print(basket)
# show that duplicates have been removed
{orange, banana, pear, apple}
>>> orange in basket
# teste dappartenance
True
>>> crabgrass in basket
False
>>> # Demonstrate set operations on unique letters from two words
...
>>> a = set(abracadabra)
>>> b = set(alacazam)
>>> a
# lettres dans a
{a, r, b, c, d}
>>> a - b
# lettres dans a mais pas dans b
{r, d, b}
>>> a | b
# lettres soit dans a soit dans b
{a, c, r, d, b, m, z, l}
>>> a & b
# lettres la fois dans a et dans b
{a, c}
>>> a ^ b # lettres dans un des 2 mais pas dans les deux ensembles a et b
{r, d, b, m, z, l}
>>> s2 = set({})
# ensemble vide : {} donne un dictionnaire vide
Lexemple prcdent qui dtermine les lettres communes de deux mots peut simplement
scrire :
71
>>> s = set("pommeee")
>>> t = set("banane")
>>> s & t # ensemble des lettres communes
{e}
>>> list(s & t) # si on veut une liste pas un ensemble
[e]
En une ligne :
>>> list(set("pommeee") & set("banane")) # liste des lettres communes
[e]
7.2 Dictionnaire
7.2.1 Dfinition et manipulation
Un dictionnaire est une squence modifiable, o les indices peuvent tre de (presque) nimporte
quel type non modifiable.
Un dictionnaire peut tre vu comme une correspondance entre un ensemble dindices (les cls)
et un ensemble de valeurs. chaque cl correspond une valeur; lassociation entre une cl et
une valeur est vue comme une paire cl-valeur ou comme un lment de la squence.
Exemple: construisons un dictionnaire anglais-franais : les cls et les valeurs seront des
chanes de caractres.
>>> eng2fr = {one: un, two : deux, three : trois} # initialisation
>>> type(eng2fr)
<type dict>
>>> eng2fr[four] = quatre # ajoute un lment d"indice" four
>>> print(eng2fr)
{four: quatre, three: trois, two: deux, one: un}
>>> print(eng2fr[two])
deux
>>> print(eng2fr[five]) # lment inexistant
KeyError: five
>>> dico2 = {} # dictionnaire vide
En gnral, lordre des lments dun dictionnaire est imprvisible. Ce nest pas un problme
: on naccde pas aux lments avec des indices entiers, on utilise les cls.
Type des valeurs et des cls: les valeurs peuvent tre de nimporte quel type (comme pour
les listes); les cls doivent tre des lments non modifiables (exemple: valeur simple, string,
tuple) et donc pas une liste ou un autre dictionnaire qui sont des types modifiables.
72
Plus prcisment, le type dune cl doit tre hachable, c--d que lon peut le convertir en un
nombre entier dune manire dterministe.
>>> hash(6)
6
>>> hash(hello)
-1267296259
>>> hash( (1, 2) )
1299869600
Un dictionnaire est une squence : on peut lui appliquer certaines oprations dj vues avec les
autres squences (strings, tuples, listes).
>>> d = {entier : 1, liste : [1, 2, 3], 3 : trois, dico : eng2fr}
>>> len(eng2fr)
4
>>> one in eng2fr # eng2fr a une cl one
True
>>> deux in eng2fr # eng2fr na pas de cl deux
False
>>>for elem in d: # pour toutes les cls du dictionnaire
7.2. Dictionnaire
73
...
print("llment : ", elem, " vaut ", d[elem])
...
llment : liste vaut [1, 2, 3]
llment : dico vaut {three: trois, two: deux, one: un}
llment : 3 vaut trois
llment : entier vaut 1
Par contre on ne pourra pas utiliser le slice puisquon ne travaille pas avec des indices entiers.
Il est frquent dutiliser des tuples comme cls dun dictionnaire (principalement car on ne peut
pas utiliser des listes). Par exemple, on peut utiliser un dictionnaire pour stocker un rpertoire
tlphonique dont les cls sont un tuple (nom, prnom).
>>> tel = {}
>>> tel[Baroud,Bill] = 065-37-07-56
>>> tel[II,Albert] = 02-256-89-14
>>> tel[Poelvoorde,Benoit] = 081-23-89-65
>>> for last, first in tel:
...
printfirst, last, tel[last, first])
Benoit Poelvoorde 081-23-89-65
Bill Baroud 065-37-07-56
Albert II 02-256-89-14
Pour dterminer si une valeur est prsente dans le dictionnaire, on peut utiliser la mthode
values qui retourne toutes les valeurs sous la forme dune liste.
>>> vals = eng2fr.values()
>>> deux in vals
True
>>> print(vals)
[quatre, trois, deux, un]
La mthode get() prend une cl et une valeur par dfaut en paramtre. Si la cl est prsente
dans le dictionnaire, get retourne la valeur correspondante. Sinon, elle retourne la valeur par
dfaut.
>>> help(dict.get)
Help on method_descriptor:
7.2. Dictionnaire
75
get(...)
D.get(k[,d]) -> D[k] if k in D, else d.
(END)
d defaults to None.
Comme lexemple prcdent lillustre, lopration in permet de savoir si une cl est prsente
dans le dictionnaire.
Les mthodes keys, values et items permettent dobtenir respectivement les cls, les valeurs et
des 2-uples cl-valeur.
La mthode pop supprime une paire cl-valeur partir dune cl et retourne la valeur supprime.
>>> eng2fr = {one: un, two : deux, three : trois, four:quatre}
>>> help(dict.pop)
Help on method_descriptor:
76
pop(...)
D.pop(k[,d]) -> v, remove specified key and return the corresponding value.
If key is not found, d is returned if given, otherwise KeyError is raised
>>> print(eng2fr.pop(five, None))
None
>>> print(eng2fr.pop(one, None))
un
>>> eng2fr
{four: quatre, three: trois, two: deux}
La mthode popitem supprime une paire cl-valeur (indtermine) et retourne la paire supprime sous la forme dun 2-uple.
La fonction histogram est pratique mais on pourrait avoir besoin dobtenir ces informations de
manire inverse.
Exemple : Au lieu de {m: 1, n: 2, e: 4, t: 1, v: 1},
on aimerait avoir {1 : [m, t, v], 2 : [n], 4: [e]}.
7.2. Dictionnaire
77
d = histogram(evenement)
inv_d = invert_dict(d)
inv_d
[m, t, v], 2: [n], 4: [e]}
78
La mthode update() sur un dictionnaire prend une liste de tuples en argument et les ajoute
au dictionnaire existant. En combinant items, lassignation de tuples et une boucle for, on peut
facilement traverser les cls et les valeurs dun dictionnaire.
>>> d[a] = 0
>>> d.update(zip(bcd,range(1,4)))
>>> for key, val in d.items():
...
print(key, val)
a 0
c 2
b 1
d 3
Remarque : il ne peut y avoir quun seul paramtre de ce type, et il doit se trouver la fin de la
liste des paramtres.
On peut combiner loprateur gather * avec des paramtres requis et optionnels (avec valeurs
par dfaut). On commence par les paramtres requis, puis les optionnels et enfin le paramtre
de taille variable.
>>> def g(required, optional=0, *args):
...
print(required:, required)
...
print(optional:, optional)
...
print(others:, args)
>>> g()
TypeError: g() takes at least 1 argument (0 given)
79
>>> g(1)
required: 1
optional: 0
others: ()
>>> g(1,2)
required: 1
optional: 2
others: ()
>>> g(1,2,3)
required: 1
optional: 2
others: (3,)
>>> g(1,2,3,4)
required: 1
optional: 2
others: (3, 4)
Loprateur * appliqu sur un tuple lors de lappel une fonction permet galement de faire
linverse : il spare le tuple en une squence darguments.
>>> help(divmod)
Help on built-in function divmod in module __builtin__:
divmod(...)
divmod(x, y) -> (div, mod)
80
Warning: Nous avons vu que les squences peuvent tre manipules soit avec des oprateurs (+, *, ...) soit avec des mthodes. En fait les oprateurs sont des notations alternatives
de mthodes.
Par exemple si lon demande la liste des attributs dun entier (2 par exemple),
>>> dir(2)
[__abs__, __add__, __and__, __bool__,
__ceil__, __class__, __delattr__, __divmod__, __doc__,
__eq__, __float__, __floor__, __floordiv__, __format__,
__ge__, __getattribute__, __getnewargs__, __gt__,
__hash__, __index__, __init__, __int__, __invert__,
__le__, __lshift__, __lt__, __mod__, __mul__, __ne__,
__neg__, __new__, __or__, __pos__, __pow__, __radd__,
__rand__, __rdivmod__, __reduce__, __reduce_ex__,
__repr__, __rfloordiv__, __rlshift__, __rmod__,
__rmul__, __ror__, __round__, __rpow__, __rrshift__,
__rshift__, __rsub__, __rtruediv__, __rxor__,
__setattr__, __sizeof__, __str__, __sub__,
__subclasshook__, __truediv__, __trunc__, __xor__,
bit_length, conjugate, denominator, from_bytes, imag,
numerator, real, to_bytes]
la mthode __add__ apparat : lopration + renvoie cette mthode qui sexcute donc
lors de lappel lopration.
Pour ne pas crire de code erron, il est, en particulier, essentiel de bien connatre leffet
dune mthode: si lobjet est non modifiable (valeur simple, styring, tuple, ...), gnralement,
la mthode renvoie un rsultat (diffrent de None); dans le cas des objets modifiables (list,
dict, set, ...), il faut bien voir, si leffet de la mthode est
de modifier lobjet mais renvoie None
de renvoyer un rsultat sans modifier lobjet
la fois de modifier lobjet et de renvoyer un rsultat.
81
82
CHAPTER
EIGHT
RECHERCHES ET TRIS
Un certain nombre dalgorithmes font partie de la culture informatique. Parmi ceux-ci, les
algorithmes de
recherche de llment minimum (ou maximum) dans une squence;
recherche dun lment dans un ensemble reprsent sous une forme ou une autre
(squence, squence trie, structure plus labore);
tri des lments dune squence
sont probablement les classiques des classiques. Je me dois donc den donner une version
Python.
Heureusement pour le programmeur, mais malheureusement pour lalgorithmicien dsirant
utiliser ses connaissances, ces fonctions sont dj implmentes en Python:
>>> texte = "voici mon texte qui contient le mot que je cherche"
>>> min(texte) # lespace est llment qui a le plus petit code dans ce texte
>>> if "mot" in texte:
...
print("mot est dans mon texte")
...
mot est dans mon texte
>>> copains = ["Michelle", "Marie", "Alain", "Sophie", "Didier", "Ariane", "Gill
... "Bernadette", "Philippe", "Anne-Franoise", "Pierre"]
>>> x = input("Dis-moi ton nom")
>>> if x in copains:
...
print("bonjour", x)
...
bonjour Gilles
>>> copains.sort()
>>> for c in copains:
...
print(c)
...
Alain
Anne-Franoise
Ariane
Bernadette
Didier
Gilles
83
Marie
Michelle
Philippe
Pierre
Sophie
Notons quici cest lindice du minimum qui est renvoy: cela permet davoir la fois sa valeur
s[indice_min(s)] mais aussi sa position.
84
def recherche(s,x):
""" donne lindice o se trouve la valeur de x dans s (-1 si nexiste pas) ""
i = 0
while i < len(s) and s[i][0] != x:
i = i+1
if i == len(s):
i = -1 # pas trouv
return i
Version amliore
Si s est modifiable on peut ajouter llment recherch (et ensuite le retirer la fin).
def recherche(s,x):
"""
donne lindice o se trouve la valeur de x dans s (-1 si nexiste pas)
version amliore quand s est modifiable
"""
i = 0
s.append((x,0))
while s[i][0] != x: # ne teste pas si on est en fin de squence
i = i+1
del s[-1]
if i == len(s):
i = -1 # pas trouv
return i
85
2. Soit s[m][0] > x et il faut recommencer la recherche avec une nouvelle borne suprieure
(bs = m - 1).
3. Soit s[m][0] = x et m est lindice recherch.
Cette recherche se termine soit lorsque s[m][0] = x soit lorsque la tranche [bi:bs] est vide. Dans
le premier cas m est lindice recherch sinon, par convention, le rsultat de la recherche vaudra
-1.
def recherche_dichotomique(s,x):
"""
recherche dichotomique ou binaire de x dans s
rsultat:
donne lindice o se trouve la valeur de x dans s
(-1 si nexiste pas)
"""
bi, bs = 0, len(s)
m = (bi+bs)//2
while bi < bs and x != s[m][0]:
m = (bi+bs)//2
if s[m][0] < x:
bi = m+1
else:
bs = m # x est avant ou est trouv
len(s) <= m or s[m][0] != x:
m = -1
return m
if
# pas trouv
les noms et prnoms peuvent constituer la cl sur laquelle on effectue les comparaisons
pour trier les valeurs,
les autres informations constituent linformation satellite associe.
Ainsi, aprs le tri, le tableau contiendra les informations sur les personnes, classes dans lordre
alphabtique de leur nom. La figure suivante illustre un tel tableau avant et aprs le tri.
Avant le tri
Nom
Vanbegin Marc
Dupont Jean
Pascal Paul
Van Aa Michel
Dupont Jean
Milcamps Ren
Alexandre Eric
Adresse
Av. Louise
rue du Moulin
...
...
rue du Chteau
rue de Lige
...
Aprs le tri
Nom
Alexandre Eric
Dupont Jean
Dupont Jean
Milcamps Ren
Pascal Paul
Van Aa Michel
Vanbegin Marc
Adresse
...
rue du Moulin
rue du Chteau
rue de Lige
...
...
Av. Louise
87
Comme pour les algorithmes de recherche, nous allons prsenter nos algorithmes de tri sur des
listes s dlments (les valeurs de s[i][0] reprsentant les cls).
Notons galement que les tris prsents ci-dessous rangent les lments par ordre non dcroissant.
Ainsi aprs ltape n-2, la liste s est entirement trie puisque s[n-1] est suprieur ou gal aux
lments s[0] jusque s[n-2] tris.
La figure suivante montre les tapes du tri par slection pour une liste dont on ne reprsente
que les cls valant 1 7.
88
3 7 2 6 5 1 4
1 7 2 6 5 3 4
1 2 7 6 5 3 4
1 2 3 6 5 7 4
1 2 3 4 5 7 6
1 2 3 4 5 7 6
1 2 3 4 5 6 7
Code du tri par slection dune liste s.
def tri_selection(s):
"""
Trie la liste s par slection
"""
n = len(s)
for i in range(n-1):
# recherche du min dans s[i..n]
min = i # min = indice du min provisoire
for j in range(i+1,n):
if s[j][0] < s[min][0]:
min = j
# placement du ime lment: change s[i]<->s[min]
s[min],s[i] = s[i],s[min]
89
3 7 2 6 5 1 4
3 7 2 6 5 1 4
2 3 7 6 5 1 4
2 3 6 7 5 1 4
2 3 5 6 7 1 4
1 2 3 5 6 7 4
1 2 3 4 5 6 7
La procdure prsente la figure suivante effectue le tri par insertion en fusionnant la partie 2
et 3. En effet, la recherche de la nouvelle position de llment insrer (plac temporairement
dans Save se fait dans ce cas ci linairement en partant de lindice i-1 et en descendant. Tant
que s[j] est strictement suprieur llment insrer, on le dplace en s[j+1] et on dcrmente
j.
def tri_insertion(s):
"""
Trie liste s par insertion
"""
n = len(s)
for i in range(1,n):
Save = s[i]
#utilis pour lchange
# insertion de s[i]
j = i-1
while j>=0 and s[j][0] > Save[0]:
s[j+1] = s[j]
j=j-1
s[j+1] = Save
Lalgorithme fonctionne mme si n=0 ou 1 (dans ces cas il ne fait rien) et est stable.
90
91
92
Notons que:
ltape 3. procde par un for dont la variable de contrle a sa valeur qui va en dcroissant,
ceci pour que le tri soit stable.
Si m < n ce tri est trs efficace (voir plus loin).
93
94
CHAPTER
NINE
9.1 Motivation
Montrer quune version dun programme est plus efficace quune autre nest, a priori, pas ais.
La succession ou limbrication des tests et des boucles et la multitude des possibilits fait
quil nest gnralement pas possible ou raisonnable dvaluer lefficacit de lalgorithme pour
chaque cas possible.
Dans ce chapitre, nous donnerons un aperu des techniques et mthodes destimation de
lefficacit dun algorithme. En particulier nous dfinirons la notation grand O qui permettra de classer les algorithmes selon leur type defficacit sans devoir dtailler le nombre exact
dinstructions excutes par lalgorithme.
96
Dnotons len(s) = n. n est la taille de la liste et donc par extension, galement la taille du
problme.
Redonnons ici la partie traitement de cet algorithme en ayant eu soin de transformer le for en
while pour mieux dtailler chaque tape dexcution de lalgorithme et nous supposons n =
len(s) connu dans le programme :
res = 0
i = 1
while i< n :
if s[i][0] < s[res][0]:
res = i
i = i+1
return res
#
#
#
#
#
#
#
1
2
3
4
5
6
7
Pour obtenir des rsultats qui restent valables quel que soit lordinateur utilis, il faut raliser
des calculs simples donnant une approximation dans une unit qui soit indpendante du processeur utilis. On peut, par exemple, faire lapproximation que chaque assignation de donne
simple ou test lmentaire reprsente une unit de temps dexcution.
Dautres hypothses auraient pu tre faites. Par exemple, on aurait pu ne considrer que les
assignations et rechercher la complexit en nombre dassignations, ou ne considrer que les
tests et rechercher la complexit en nombres de tests effectus par lalgorithme.
La complexit dpend donc fortement de lunit prise qui doit tre clairement prcise.
Avec nos hypothses, les instructions des lignes 1, 2 et 7 prennent chacune une unit de temps
dexcution.
La boucle while de la ligne 3 6 sexcute n-1 fois, mais le test seffectue n fois. La ligne 3
prend n units et la ligne 6, n-1 units.
Le test de la ligne 4 prend une unit; il est effectu n-1 fois et donc la ligne 4 utilisera au total
n-1 units.
Lassignation de la ligne 5 prend une unit. Elle nest effectue que lorsque le test du if est
vrifi. Si lon ne dsire pas uniquement faire une seule mesure sur un jeu de donnes bien
prcis, il faut donc expliciter si lon dsire connatre le temps dexcution dans le meilleur des
cas T_min(n), le pire des cas T_MAX(n)), ou en moyenne T_moyen(n). Ici:
T_min(n) est donn dans le cas o le test du if nest jamais vrifi, ce qui signifie
que le minimum se trouve la premire composante. On a alors: T_min(n) =
1+1+n+(n-1)+(n-1)+1=3n+1
T_MAX(n) est donn dans le cas o le test du if est chaque fois vrifi, ce qui correspond au cas o toutes les valeurs de s sont distinctes et tries en ordre dcroissant. On a alors: T_MAX(n) = 1+1+n+(n-1)+(n-1)+(n-1)+1= 4n
Le calcul de T_moyen(n) est gnralement beaucoup plus difficile effectuer. Pour cela, on
peut faire des hypothses sur les jeux de donnes possibles et leur distribution statistique; ces
hypothses doivent tre le plus raliste possible. Pour que le calcul de T_moyen(n) ne soit pas
trop compliqu, on tolre gnralement certaines hypothses simplificatrices. Nous pouvons,
par exemple, supposer que toutes les valeurs dans s sont distinctes et faire lhypothse que la
distribution des valeurs est uniforme, la liste tant non trie a priori.
9.1. Motivation
97
Pour faire ce calcul, sparons les actions dues au while, au if et lassignation finale, des
actions dassignation de la variable res et posons:
C(n) = le nombre moyen dassignations res pour une liste de taille n
Si nous posons R(n) = le nombre dactions dues au while, au if et lassignation finale, ce
nombre est connu et vaut: R(n) = 3n.
Nous avons: T_moyen(n) = C(n) + R(n)
Pour exprimer la valeur de C(n), regardons dabord sa valeur pour n valant 1,2, ...
Pour n valant 1, C(1)=1 puisquil y a une assignation en dbut, et que le corps de la boucle
while ne sexcute jamais.
Pour n valant 2, la liste contient une valeur maximale Max et une valeur minimale min. Deux
possibilits quiprobables peuvent se prsenter:
1. s = min suivi de Max
2. s = Max suivi de min
Le cas 1. donne une assignation et le cas 2. deux assignations, soit en moyenne: C(2) = 3/2
Essayons davoir une expression gnrale pour C(n): s[0] a une chance sur n dtre le minimum, une chance sur n dtre le deuxime minimum, .... Donc s[0] a 1/n chance dtre le ime
minimum et cela pour tout i entre 1 et n.
Si nous posons C(0) = 0 et si dans la sous-liste quil reste traiter il y a j lments plus petits
que le minimum provisoire, le nombre dassignations quil faudra encore effectuer vaudra,
daprs la dfinition donne, C(j), car les nombres plus grands que le minimum provisoire
nimpliqueront aucune assignation supplmentaire. Ce raisonnement est valable pour tout i >=
1.
En consquence:
i1
1
C(i) = 1 +
C(j)
i j=0
(i 1)
i.C(i) = i +
i1
C(j)
j=1
98
(i + 1).C(i + 1) = (i + 1) +
C(j)
j=1
C(i + 1) =
1
+ C(i)
i+1
(i 1)
1
1
1
C(n) = +
+ ... + 1 =
n n1
i
i=1
Notons que nous aurions pu dduire ce rsultat plus rapidement en exprimant que C(i+1) vaut
le nombre moyen dassignations d la recherche du minimum pour les i premiers nombres,
cest--dire C(i), plus la probabilit que le nombre s[i] soit le minimum, cest--dire 1/i+1, ce
qui nous redonne lquation prcdente.
Pour effectuer une approximation de C(n), valuons les aires S1 et S2 donnes en gris dans la
figure suivante o la fonction f(x) = 1/x.
f(x) = 1/x
= S1
2
= S2
x
1
Ayant
n+1
n+1
1
dx = n(n + 1)
x
on voit que
99
Comme
1
1
1
S1 = 1 + + . . . + =
= C(n)
2
n
i
i=1
n+1
1
1 1
1
S2 = + + . . . +
=
= C(n + 1) 1
2 3
n+1
i
i=2
(n 1)
De ce fait:
(n > 1)
#1
#2
#3
#4
#5
#6
100
Nombre dunits
3+2
6+2
3n+2
Si x est dans s:
moyen
=
=
=
3
n (1 + 2 + . . .
3(n+1)
+2
2
3
7
2n + 2
+ n) + 2
n
(puisque i=1 i =
(1+n)n
)
2
3
7
3
3
Tmoyen (n) = (1 p)(3n + 5) + p( n + ) = (3 p)n + ( p + 5)
2
2
2
2
9.2 Le grand O
Les exemples prcdents montrent quil est souvent trs difficile de calculer le temps moyen
(ou maximal) dexcution dun algorithme. Ces calculs prcis sont, de plus, inutiles puisquils
se basent sur des approximations grossires du temps dexcution des actions lmentaires;
valuations qui ne tiennent pas non plus compte, par exemple, de lordinateur et du compilateur
ou de linterprteur utiliss.
Une valuation du temps dexcution dun algorithme ne devient gnralement intressante que
lorsque la taille du jeu de donnes, cest--dire de n dans nos exemples prcdents, est grande.
En effet pour n petit, les algorithmes sexcutent gnralement trs rapidement.
Supposons que la complexit maximale dun algorithme A = 100.n, que la complexit maximale dun algorithme B = 15.n^2 , celle de C = n^4 et celle de D = 2^n.
La table suivante donne les valeurs de complexit pour n = 1,10,100,1000, 10^6 et 10^9; les
figures qui suivent donnent les valeurs des fonctions respectivement pour n variant entre 0 et
12, et 0 et 18.
9.2. Le grand O
101
n=
1
10
100
1000
10000
106
109
A
100
1000
10000
100000
106
108
1011
B
15
1500
150000
15.106
15.108
15.1012
15.1018
C
1
10000
108
1012
1016
1024
1036
D
2
103
1030
10300
103000
10300000
8
103.10
10
12
102
x10 4
12
10
10
12
14
16
18
9.2. Le grand O
103
9.2.1 Dfinition
La notation grand O est dfinie comme suit:
Dfinition (O) : Une complexit T(n) est dite en grand O de f(n) (en O(f(n)) sil existe un
entier N et une constante c > 0 tels que pour tout entier n > N nous avons T(n) <= c.f(n)
Cette dfinition permet deffectuer de nombreuses simplifications dans les calculs. En effet de
cette dfinition il rsulte que:
Les facteurs constants ne sont pas importants. En effet, si par exemple T(n)=n ou si
T(n)=100n, T(n) est toujours en O(n)
Les termes dordres infrieurs sont ngligeables. Ainsi si T(n) = n^3 + 4n^2 + 20n +
100, on peut voir que pour n > N = 5
n^3 > 4n^2
n^3 > 20n
n^3 > 100
et donc pour n>5, T(n) = n^3 + 4n^2 + 20.n + 100 < 4n^3.
De ce fait T(n) est en O(n^3).
104
Classe dalgorithmes
constant
logarithmique
linaire
n log n
quadratique
cubique
exponentiel en base 2
exponentiel en base 3
exponentiel en base n
Classes de complexit
Dans la suite, nous essayerons toujours de donner une approximation de la complexit des
algorithmes vus.
Remarquons quen vertu du fait que pour tout a,b positif : log_a n = (log_a b).(log_b n)
et comme log_a b est une constante pour a et b fixs, si T(n) est en O(log_a n) il est galement
en O(log_b n). (la base du logarithme na donc pas dimportance pour exprimer un grand O).
Notons encore que ceci nest pas vrai pour la base des complexits exponentielles.
Donnons ici un petit nombre de rgles permettant dvaluer la complexit dun algorithme. Ces
rgles ne donnent en gnral quune surapproximation parfois grossire; une estimation plus
prcise devant tenir compte du fonctionnement de lalgorithme.
Rgles de calcul du grand O
Rgle sur lunit :
Rgle 1 (unit)
Il faut clairement dfinir lunit utilise et les lments pris en compte. Ainsi si lon tient
compte des tests lmentaires, des assignations, des lectures de donnes et des critures de
rsultats, une assignation une variable simple, une instruction input ou print dune donne
simple, ou lvaluation dune expression (ou dune condition) simple ne donnant pas lieu
lexcution de fonctions, prend un temps constant fix et est donc en O(1). Lassignation des
objets plus complexes ou des input ou print de donnes plus complexes peut ne plus tre en
O(1) en fonction de leur taille qui peut dpendre de la taille du problme (n).
Rgle de la squence :
Rgle 2 (squence)
9.2. Le grand O
105
Si un traitement 1 prend un temps T_1(n) qui est en O(f_1(n)) et un traitement 2 prend un temps
T_2(n) qui est en O(f_2(n)) alors le traitement 1 suivi du traitement 2 prend T_1(n) + T_2(n) et
est en
O(f_1(n) + f_2(n)) = O (max(f_1(n) , f_2(n)))
o max prend la fonction qui crot le plus vite cest--dire de plus grand ordre.
Par exemple si T_1(n) est en O(n^2 ) et T_2(n) est en O(n), T_1(n) + T_2(n) est en O(n^2 + n)
= O(n^2)
En particulier une squence dinstructions simples (dont on tient compte) ne faisant aucun appel
une procdure ou une fonction ne dpend pas de n et sont donc en O(1).
Rgle du if :
Rgle 3 (if)
Pour un if condition:
instruction_1 else:
instruction_2
o
instruction_1 est en O(f_1(n))
instruction_2 est en O(f_2(n))
lvaluation de la condition est en O(g(n))
suivant le test, le if sera en O(max(f_1(n),g(n))) ou en O(max(f_2(n),g(n))) et peut tre born
par:
O(max(f_1(n), f_2(n), g(n)))
Rgle 4 (while)
Pour un while, sachant que le corps de la boucle est en O(f_1(n)) et que lvaluation de la
condition est en O(f_2(n)), si on a une fonction en O(g(n)) qui donne une borne suprieure
du nombre de fois que le corps sera excut, alors le while est en O(f(n).g(n)) avec f(n) =
max(f_1(n),f_2(n)).
Rgle du for :
106
Rgle 5 (for)
Pour une boucle for, il suffit de traduire le for en while.
Par exemple :
for i in range(n):
print(i)
se traduit en:
i=0
while i < n:
print(i)
i=i+1
La fonction iter() applique sur une squence ou un range, permet de pouvoir ensuite utiliser la
fonction next() sur lobjet produit.
Par exemple :
st = "bonjour"
for i in st:
print(i)
se traduit en:
st = "bonjour"
i = iter(st)
s=next(i)
while s != None:
print(s)
s=next(i)
Donnons de simples exemples de complexit avec des for o ici aussi n est la taille du problme
:
for i in range(10):
traitement
Rgle 6 (fonction)
9.2. Le grand O
107
On peut raffiner ces calculs, selon que lon essaye de trouver une complexit minimale,
moyenne ou maximale. Ce raffinement se situera dans le nombre de fois quune instruction
sera rpte, ayant par exemple certaines hypothses sur la probabilit que certaines conditions
de if ou de boucles sont vrifies.
#1
#2
#3
#4
#5
#6
#7
Nous supposons que chaque instruction simple est prise en compte pour le calcul de la complexit.
Le traitement, comme tout algorithme, peut tre dcompos sous forme darbre (informatique)
comme donn par la figure suivante o chaque noeud reprsente une instruction Python simple
ou compose.
108
1-7
3-6
4-5
109
110
intervalle de recherche
10
20
30
40
50
10
20
30
40
48
25 30
40
48
37
60
nombre d'lments
70
80
90
99
48
3 7 41
40 41
41
100
49
24
12
La recherche dichotomique a donc une complexit maximale en O(ln n). On peut calculer que
la complexit moyenne (en supposant ou non que x est dans s) est galement en O(ln n).
111
1-13
6-13
9-11
13
10-11
11
112
113
Complexit moyenne
O(n)
O(1)
O(n)
O(1)
O(1)
O(n)
O(n)
O(k)
O(n)
O(k+n)
O(k)
O(n log n)
O(nk)
O(n)
O(n)
O(1)
Complexit maximale
O(n)
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(k)
O(n)
O(n+k)
O(n+k)
O(n log n)
O(nk)
O(n)
O(n)
O(1)
Complexit moyenne
O(1)
O(len(s)+len(t))
O(max(len(s),len(t))
O(max(len(s),len(t))
O(max(len(s),len(t))
Complexit maximale
O(n)
O(len(s) * len(t))
O(len(s) * len(t))
O(len(s) * len(t))
O(len(s) * len(t))
114
Complexit moyenne
O(n)
O(1)
O(1)
O(1)
O(n)
Complexit maximale
O(n)
O(n)
O(n)
O(n)
O(n)
115
116
CHAPTER
TEN
LOGIQUE, INVARIANT ET
VRIFICATION DALGORITHME
10.1 Introduction
Jusqu prsent nous avons expliqu nos algorithmes en dcrivant, de faon informelle, les diffrents traitements effectus par ceux-ci. Nous nous sommes assurs de leur bon fonctionnement en les testant sur certains exemples et, en particulier, sur des cas limites. Pour vrifier
compltement, en utilisant des tests, quun algorithme fonctionne correctement dans tous les
cas, il faudrait, en thorie, le tester avec toutes les donnes possibles, ce qui, en pratique, est
gnralement impossible vu le nombre norme de donnes possibles.
Notons que ceci est vrai si nous nous limitons aux algorithmes squentiels (une seule action
la fois), dterministes (2 excutions de lalgorithme avec les mmes donnes, donnent lieu
exactement au mme traitement). Si ce nest pas le cas, le problme de test ou de vrification
dun algorithme est beaucoup plus complexe.
Ce chapitre prsente, sur des exemples simples, le problme de la vrification dun algorithme. Le problme gnral de vrification complte dalgorithme est complexe et ne possde pas de mthode systmatique automatisable. Il est pourtant essentiel que le concepteur
dalgorithmes soit conscient des problmes et quil ait des notions de base en matire de vrification dalgorithmes. En effet, il est vident que la conception et la vrification dalgorithmes
vont de pair. En particulier, la notion dinvariant de boucle, prsente ci-dessous, est essentielle
pour comprendre comment fonctionne un programme.
Dans la suite de ce chapitre, aprs avoir fait un bref rappel de logique et avoir expliqu comment
formaliser en logique, ltat dun programme un endroit donn de son excution, nous allons
noncer le problme rsoudre en parlant de la notion de preuve partielle et totale, et ensuite,
prsenter la notion dinvariant de boucle qui, associe la notion de terminaison de boucle,
permet de vrifier un algorithme.
117
::= p (p P)
::= f
::= f op f
::= (f )
avec
op ::= | | | |
(le ou inclusif, le et, et les implications droite gauche ou dans les deux sens).
Note: La dfinition prcdente utilise la notation Backus Naur Form (BNF). BNF est un
formalisme qui permet de dfinir un langage; par exemple lensemble des syntaxes possibles
pour une formule logique ou pour un programme Python. Les dfinitions donnent un systme
de rcriture o la notation f ::= p signifie f peut tre rcrit en p. Quand f peut tre rcrit en
p ou q on crit f ::= p , f :: q ou de faon plus compacte f ::= p | q.
Par exemple;
pq
est une formule correcte puisque la dfinition BNF permet la squence de rcriture suivante:
f
f op f
f f
pf
pq
Smantique
Une formule peut avoir la valeur vraie ou fausse suivant la valeur des diffrentes propositions.
Nous dirons que le domaine smantique dune formule est lensemble {True, False} (Vrai
ou Faux) (dnot aussi {T, F}). Nous parlons dinterprtation dune formule, cest--dire son
valuation, en ayant donn une valeur T ou F chaque proposition.
La smantique de chaque oprateur logique est dfinie grce sa table de vrit.
Par exemple: pour linterprtation v o v(p) = F et v(q) = T
118
Enfin, si f_1 -> f_2 est valide (toujours vraie) nous disons que f_1 implique logiquement f_2 ou
que f_1 est une condition suffisante pour f_2 et que f_2 est une condition ncessaire pour f_1
(notation f_1 => f_2 o => est un mta-oprateur).
=> a la mme priorit que <=>.
119
o f(x) est une formule qui utilise la variable x, variable qui est lie par le quantificateur existentiel (il existe) ou universel (pour tout).
Par opposition, les variables simples ou indices qui ne sont pas lies par un quantificateur sont
nommes variables libres.
x<y+1
x=7y=3
x (x y = 0 x = 0)
x (x y = 0 x = 0 y = 0)
:x
:x
:x
:x
et y sont libres
et y sont libres
est lie par x et y est libre
est lie par x et y est libre
Le pour tout et il existe sont moins prioritaires que la ngation mais sont plus prioritaires que
le et, ou, les implications, et les mta-oprateurs => et <=>. Notons que lavant dernire
formule est consistante (peut tre vraie) tandis que la dernire est valide (est vraie pour toute
interprtation).
De mme, la formule :
x (0 x < 0 x = 7)
est valide (toujours vraie) puisque 0 <= x < 0 est toujours fausse.
Cette logique est la logique des prdicats ou logique du premier ordre.
Les notions dquivalence et dimplication logiques sont tendues. La liste suivante donne
quelques quivalences logiques reprsentatives o f(x), f_1(x) et f_2(x) sont des formules utilisant la variable libre x:
1. x f (x) x f (x)
2. x f (x) x f (x)
3. Si le domaine des valeurs possibles pour x nest pas vide:
x f (x) x f (x) (sinon ce nest pas vrai)
4. x (f1 (x) f2 (x)) (x f1 (x) x f2 (x))
5. x (f1 (x) f2 (x)) (x f1 (x) x f2 (x))
120
reprsente un proposition vraie si x vaut 3 et fausse sinon (ici on utilise le symbole = pour
dsigner lgalit).
Par extension, la smantique de cette formule, sera lensemble des tats o cette formule est
vraie, et donc lensemble des tats du programme o x vaut 3, quelque soit la valeur des autres
variables.
Exemple:
En pratique nous allons dcrire ltat dun programme un moment de son excution. Cet
tat est constitu par la valeur de chacune de ses variables (ou plus prcisment des objets
rfrencs par ses variables) et du point de contrle, cest--dire lendroit (instruction) o se
trouve lexcution du programme.
Par exemple dans le code :
x = 3
y = 4
z = x * y
#1
#2
#3
Aprs #2, on a :
x=3y =4
Aprs #3, on a :
x = 3 y = 4 z = 12
121
qui formalise la postcondition la plus forte (cest--dire qui a le plus de contraintes) que lon
peut imaginer avec ce code.
Notons que ltat du programme avant la premire instruction est, si aucune variable nest
initialise, quaucune contrainte sur la valeur des variables nexiste: dans ce cas, formalise
par la formule True dont la smantique est lensemble de tous les tats possibles.
De faon gnrale, la smantique dune formule f pour un programme donn, est lensemble
des tats o f est vraie. Donc quand on exprime quavec une prcondition donne Pre, le code
donne la postcondition Post, cela signifie que si lon prend nimporte quel tat de Pr en terme
de valeur de variables du programme satisfaisant Pr, la fin du code on sera dans un tat
satisfaisant Post cest--dire parmi lensemble des tats satisfaisant le rsultat Post.
Malheureusement les programmes, mme squentiels sans appels de fonctions, ne sont
gnralement pas si simples. En effet, le flux de lexcution du programme dpend videmment
des donnes lues qui vont influencer les tests des instructions conditionnelles (if) et rptitives
(while, et for).
Sil suffit de suivre la squence dexcution et leffet sur les variables pour un jeu de donnes
prcis, cela na aucun sens en gnral car ce que lon veut pouvoir faire sest exprimer ltat du
programme en particulier la fin de son excution quelles que soit les donnes traites pour
dterminer si la Postcondition (rsultat escompt) est toujours satisfaite.
Autre exemple:
Supposons le code suivant qui suppose que x et y sont des variables entires initialises:
if x > y:
x,y = y,x
est une postcondition valide ce code, cest--dire que quelque soit la valeur initiale de x et y,
on a la fin de lexcution le fait que la valeur de x est plus petit ou gal la valeur de y.
En supposant x et y rels la figure suivante reprsente les valeurs possibles de x et de y:
122
(0,0)
valeur de x
valeur de y
Par ailleurs, pour comprendre comment sexcute un programme, il est crucial de pouvoir
dcrire prcisment son tat au milieu de son excution. Dans le cas dune rptitive (while ou
for), il est essentiel de pouvoir fournir une description unique de ltat du programme qui est
valable au dbut de chaque itration ou plus prcisment au moment o lon teste la condition
(du while ou du fait quil reste un lment traiter par le for).
Ainsi dans la recherche squentielle,
i = 0
while i < n and s[i] != x:
i = i + 1
chaque fois que le test du while est ralis (que le rsultat de ce test soit vrai ou faux), ltat
du programme est dcrit par la formule suivante:
(0 i n) (j 0 j < i s[j] = x)
qui exprime que i est entre 0 et n compris et que tous les lments de s[0:i] (i non compris) sont
diffrents de x.
123
La valeur de x est infrieure ou gale celle de tous les lments dune liste s
(dentiers):
Formule correspondante :
(i 0 i < len(s) x s[i])
Notons ici, que x, s et len(s) sont des variables (et fonctions) du programme Python. Par
contre i est une variable lie au quantificateur logique pour tout. Ce nest donc pas une variable
du programme Python.
Au niveau de la formule logique, x, s (et len(s)) sont vues comme des variables libres tandis
que i est une variable lie au quantificateur pour tout et ne correspond donc pas une variable
du programme.
Notez le canevas utilis: on a un pour tout avec une variable dont on donne un nom de variable
(si possible pas celui dune variable du programme pour ne pas mettre de la confusion) et
ensuite une implication logique :
i hypothese(i) conclusion(i)
o hypothse(i) et conclusion(i) signifient que ce sont des formules qui utilisent la variable i.
Lhypothse sert identifier les endroits o il y a une contrainte. Par exemple ici, ce sont pour
les valeurs de i entre 0 compris et len(s) non compris.
La conclusion exprime la contrainte: ici x est infrieur ou gale s[i].
En conclusion la formule dit: pour tous les indices corrects i de s on doit avoir x plus petit ou
gale s[i].
liste s trie par ordre non dcroissant:
Formellement il suffit dexprimer que les lments voisins sont dans le bon ordre:
i ((0 i < len(s) 1) (s[i] s[i + 1]))
Notez que jai rajout des parenthses pour bien identifier les deux parties de limplication,
mme si cela nest pas ncessaire car limplication est moins prioritaire que les comparaisons.
liste range de faon bizarre:
Donnons une postcondition correcte dun algorithme qui trie une liste avec les lments
dindices pairs tris en ordre croissant et les lments dindices impairs, tris en ordre
dcroissant:
124
i < len(s
1)//2)
(s[2i]
i < len(s)//2
1)
(s[2i + 1]
s[2i + 2]))
s[2i + 3]))
Donnons une postcondition correcte dun algorithme qui trie une liste avec les lments
pairs tris en ordre croissant et les lments impairs, tris en ordre dcroissant (attention,
ce nest pas comme le prcdent !!) :
i, j ((0 i < j < len(s) s[i]%2 = 0 s[j]%2 = 0) (s[i] s[j]))
125
Encore un exemple
Exprimez en logique du premier ordre le rsultat (valeur de res) de lalgorithme suivant qui
travaille avec une liste s dentiers:
n = len(s)
i = 1
res = 0
while i < n:
if s[i] != s[res]:
i = i+1
else:
res = res+1
i = res+1
Postcondition:
n = len(s)
0 res < n
o hypothse(i) indique par exemple les conditions sur lindice i et conclusion(i), la formule
que lon veut exprimer sur les donnes du programme.
126
Essayons de prouver que le calcul du pgcd par la mthode dEuclide, donn la figure suivante
donne le bon rsultat en supposant quau dpart x >= 0 et y >0.
def pgcd(x, y):
""" calcule le pgcd(x,y)"""
while (y > 0):
x,y = y,x % y
return x
127
ralis est vide, on aura alors Rsultat = Ce qui reste raliser. A la terminaison de la boucle,
la condition darrt de la boucle permet de vrifier que ce qui reste raliser est vide. On aura
alors Rsultat = Ce qui est ralis et la preuve partielle pour la boucle sera ralise.
Formellement pour un code while C: instruction , les trois conditions suivantes
doivent tre vraies :
code avant le while I
I C + corps du while execute une iteration I
I C R
Pour exprimer linvariant de la boucle while de la fonction pgcd, il faut utiliser des notations
permettant de distinguer les valeurs initiales de x et de y de leur valeur courante.
Nous dnoterons x_i , y_i les valeurs respectivement de x et y aprs la ime itration, (initialement x = x_0 , y = y_0) et x, y leur valeur courante.
Linvariant vaut alors:
Invariant: (pgcd(x0 , y0 ) = pgcd(x, y)) (x 0) (y 0)
Cette formule exprime le fait que pour calculer pgcd(x_0 , y_0 ) il reste calculer pgcd(x,y) (ici
on peut oublier ce qui a dj t ralis). Le progrs provient du fait quil est plus simple de
calculer pgcd(x,y) que pgcd(x_0 , y_0 ).
Vrifier un invariant se fait par rcurrence. Pour le pgcd,
Base: : Initialement, linvariant est trivialement vrai puisque x=x_0 et y=y_0 avec x_0
et y_0 >= 0.
Induction:: Si la formule est vraie au dbut de la ime itration et que la boucle effectue une itration supplmentaire alors linvariant est vrai au dbut de la i+1me
itration.
En effet, on peut montrer que
x > 0 y > 0 pgcd(x, y) = pgcd(y, x % y)
De plus
x > 0 y > 0 x %y 0
Et donc, tant donn quaprs chaque itration, les nouvelles valeurs de x et y valent
respectivement lancienne valeur de y et lancienne valeur de x modulo lancienne
valeur de y (ce que lon peut noter x_i = y_(i-1) , y_i = x_(i-1) % y_(i-1)) on voit
que linvariant est vrai au dbut de la i+1me itration.
Pour complter la preuve partielle il faut montrer que linvariant et la terminaison implique le
rsultat.
En effet:
(pgcd(x0 , y0 ) = pgcd(x, y)) (x 0) (y 0) (y 0) pgcd(x0 , y0 ) = x
Enfin, pour complter la preuve totale il faut encore montrer que la boucle se termine effectivement.
128
Ayant x_0 > 0 et y_0 >= 0 on peut voir qu chaque itration, la valeur (entire) y diminue dau
moins une unit. De ce fait le test (y > 0) sera assurment faux un moment donn.
Fonction de terminaison
En gnral, on vrifie quune boucle se termine toujours en mettant en vidence une fonction de
terminaison, cest--dire une fonction f valeur entire qui dpend de la valeur des variables
et telle que:
la valeur de la fonction dcrot strictement dau moins une unit chaque itration;
si linvariant de la boucle est vrai, f est positif ou nul.
Linvariant tant par dfinition vrai au dbut de chaque itration de la boucle, on est alors assur
de la terminaison de celle-ci. Comme pour la recherche dun invariant correct, la recherche
dune telle fonction de terminaison ne possde pas de mthode systmatique.
10.5.1 minimum
Dans la fonction de recherche de lindice du minimum, pour trouver linvariant de la boucle
for, il faut traduire ce for en un while. On obtient le code suivant:
res = 0
i = 1
while i < n:
if V[i] < V[res]:
res = i
i += 1
et linvariant du while permettant deffectuer la preuve totale de lalgorithme est donne ci-dessous:
I 0 < i n j (1 j i 1 V [i min provisoire] V [j])
Notons bien que I reste vrai mme quand la condition du while i<n devient fausse. Une
fonction de terminaison qui, associe linvariant, permet de faire la preuve totale, vaut: n-i
Note: Trouver linvariant dune boucle peut tre difficile puisquaucun algorithme systmatique nexiste pour le trouver. Dans le cadre de ce cours, nous vous demandons seulement
de pouvoir prouver quun invariant que lon vous donne est correct (cest--dire remplit les 3
conditions donnes plus haut).
129
130
V[min],V[i] =
i = i+1
V[i],V[min]
avec
invariant I2 :
0i<n
k (0 k < i 1 V [k] V [k + 1])
m k (0 m i 1 i k < n V [m] V [k])
invariant I1 :
(i < j n) k (i k < j V [min] V [k])
avec
invariant I2 :
0<in
k (0 k < i 1 V [k] V [k + 1])
invariant I1 :
1 j i 1
k (j + 2 k i V [k] > Save)
131
132
CHAPTER
ELEVEN
RCURSIVIT
See Also:
Rfrence: livre de Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein - Algorithmique
Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein - Algorithmique - 3me dition - Cours avec 957 exercices et 158 problmes, Dunod, 2010,
ISBN: 978-2-10-054526-1 http://www.books-by-isbn.com/2-10/2100545264Algorithmique-Cours-avec-957-exercices-et-158-problemes-2-10-054526-4.html
La dfinition rcursive se base sur la dfinition n! = n.(n-1)! pour tout n>0 avec 0! = 1
On obtient le code:
def fact(n):
if n == 0:
res = 1
else:
res = n*fact(n-1)
return res
ou plus court:
def fact(n):
return 1 if n == 0 else n * fact(n-1)
Notons que nous avons dj vu plusieurs algorithmes crits de faon itrative mais dont lide
de base tait rcursive.
Le programme de test de la conjecture de syracuse:
def test_syracuse(n):
while n != 1:
if n % 2 == 0:
n = n//2
else:
n = n*3+1
return True
snonce chaque tape si n est pair on le divise par 2 sinon on le multiplie par 3 et ajoute 1.
Littralement on pourrait lcrire:
def test_syracuse(n):
if n == 1:
res = True
else:
if n%2 == 0:
n = n//2
else:
n = 3*n+1
res = test_syracuse(n)
return res
134
def test_syracuse(n):
if n == 1:
res = True
else:
res = test_syracuse(n//2 if n%2 == 0 else 3*n+1)
return res
Note: En pratique, le nombre dappels imbriqus de fonction est limit, par dfaut, 1000
appels. Par exemple, lexcution de la version rcursive de fact(1000) provoque lerreur
RuntimeError: maximum recursion depth exceeded in comparison.
Le code pour la recherche dichotomique sur une liste de couples tris sur la cl (premier lment
des couples):
def recherche_dichotomique(s,x):
bi, bs = 0, len(s)
m = (bi+bs)//2
while bi < bs and x != s[m][0]:
m = (bi+bs)//2
if s[m][0] < x:
bi = m+1
else:
bs = m # x est avant ou est trouv
len(s) <= m or s[m][0] != x:
m = -1
return m
if
# pas trouv
135
11.2 Mcanismes
Prenons un simple code rcursif (fonction foo) dont le cas de base est celui o le paramtre n
vaut 0 et qui sinon fait un appel rcursif une instance foo(n-1).
def foo(n):
if n == 0:
# traitement cas de base
else
...
foo(n-1)
...
La fonction foo ralise gnralement un certain traitement pour le cas de base, et peut effectuer
un traitement avant (pr-traitement), ou aprs (post-traitement) lappel rcursif.
Les trois codes suivants illustrent ces possibilits o les traitements correspondent simplement
des print :
Avec pr-traitement:
def foo(n):
if n==0:
print("cas de base :", n)
else:
print("pre-traitement pour :" , n)
foo(n-1)
foo(5)
donne:
pre-traitement pour
pre-traitement pour
pre-traitement pour
pre-traitement pour
pre-traitement pour
cas de base : 0
:
:
:
:
:
5
4
3
2
1
Avec post-traitement:
def foo(n):
if n==0:
print("cas de base")
else:
foo(n-1)
print("post-traitement pour :" , n)
foo(5)
donne:
136
cas de base : 0
post-traitement pour
post-traitement pour
post-traitement pour
post-traitement pour
post-traitement pour
:
:
:
:
:
1
2
3
4
5
Avec pr et post-traitement :
def foo(n):
if n==0:
print("cas de base : ", n)
else:
print("pre-traitement pour :" , n)
foo(n-1)
print("post-traitement pour :" , n)
foo(5)
donne:
pre-traitement pour : 5
pre-traitement pour : 4
pre-traitement pour : 3
pre-traitement pour : 2
pre-traitement pour : 1
cas de base : 0
post-traitement pour : 1
post-traitement pour : 2
post-traitement pour : 3
post-traitement pour : 4
post-traitement pour : 5
Notons quici on suppose que linstance n appelle une fois linstance n-1. Il se peut quelle
appelle plusieurs instances n-1 comme nous le verrons dans certains exemples plus bas.
Note: Quand une instance donne (par exemple de paramtre n) de la fonction foo appelle
rcursivement une instance plus petite (par exemple de paramtre n-1, on dit gnralement que
linstance pre foo(n) appelle une instance fils foo(n-1).
Illustrons ces trois canevas.
137
Les deux exemples suivant illustrent aussi bien un traitement rcursif avec pr-traitement:
Calcul de toutes les permutations des lments dune squence
Lide est simple: lensemble des permutations des lments dune squence s est donn en
prenant lensemble des squences commenant par un symbole quelconque de s suivi de toutes
les permutations des symboles restants.
On obtient facilement le code suivant:
def Permutations(prefixe, s):
if len(s) == 0: # prefixe est une nouvelle permutation
print(prefixe)
else: # prend un lment de la squence comme suivant
# et construit la suite avec ce quil reste a permuter
for i in range(len(s)):
Permutations(prefixe + s[i], s[:i]+s[i+1:])
Permutations("", "abcd")
print()
Permutations("", ("belle Marquise ", "vos beaux yeux ", "me font ",\
"mourir ", "damour ", "pour vous "))
138
Lide est que pour trier un vecteur (liste python), on choisit au hasard un (par exemple le
premier) lment du vecteur : il sera appel llment pivot. Ensuite on classe les lments
du vecteur de manire placer avant le pivot les lments qui lui sont infrieurs, et aprs ceux
qui lui sont suprieurs. On appelle (rcursivement) le tri rapide sur les deux moitis de part et
dautre du pivot. Lorsque la squence trier est de taille 0 ou 1, il ny a plus rien faire, car le
tableau est dj tri.
Le tri rapide sera donn ultrieurement dans un cours dalgorithmique.
Une implmentation nave du quicksort donne:
def quick_sort(s):
""" Tri rapide (quicksort) de s (liste de couples (cl, valeur)) """
if len(s) <= 1:
res = s
else:
pivot = s[0]
prefixe = quick_sort([x for x in s[1:] if x[0] < pivot[0]])
suffixe = quick_sort([x for x in s[1:] if x[0] >= pivot[0]])
res = prefixe + [pivot] + suffixe
return res
Notez quici s nest pas modifi, mais que la fonction renvoie une nouvelle liste trie. Une
version en place et plus efficace du Tri rapide est possible.
11.2. Mcanismes
evalue(v[2])
evalue(v[2])
evalue(v[2])
evalue(v[2])
139
elif v[1] == ^:
res = evalue(v[0]) ** evalue(v[2])
else:
res = None # error
return res
Notez aussi que ici l nest pas modifi, mais que la fonction renvoie une nouvelle liste trie.
140
11.3.1 Graphe
Un graphe G = (V,E) est une structure de donnes, forme dun ensemble V dlments et dun
ensemble de pairs (ou de couples) tablissant les liens entre ces lments.
Si E est un ensemble de pairs, on dit que le graphe est non orient, sil sagit de couples, le
graphe est orient.
Le graphique suivant dcrit un graphe orient donnant un ensemble V de personnes (V= {Jean,
Germaine, Catherine, Luc, Bernadette, Jules, Michel} avec la relation E (connat).
E = { Jean -> Germaine ; Germaine -> Catherine ; Catherine -> Jean ; Bernadette -> Luc ;
Bernadette -> Michel ; Michel -> Luc ; Bernadette -> Jules ; Jules -> Bernadette }
Jean
Bernadette
Germaine
Michel
Catherine
Jules
Luc
Une faon simple dimplmenter un tel graphe en python est avec un dictionnaire dont les
lments sont les cls, et la liste de leurs connaissances, leur valeur. Dans lexemple plus haut
on aurait:
graphe = { "Jean"
"Germaine"
"Catherine"
"Luc"
"Michel"
"Bernadette"
"Jules"
:
:
:
:
:
:
:
["Germaine"] ,
["Catherine"],
["Jean"] ,
[],
["Luc"],
["Luc", "Michel", "Jules"],
["Bernadette"] }
141
Ainsi lexpression 3+4*5 est vu comme larbre binaire illustr par la figure suivante :
142
cre un objet de classe entire (int) dont la valeur est 3, et place dans la variable a son adresse
(sa rfrence). Ensuite laddition cre un autre objet de type (classe) int et de valeur 4 et a
reoit la rfrence ce nouvel objet.
>>> dir(a)
[__abs__, __add__, __and__, __bool__, __ceil__, __class__,
__delattr__, __divmod__, __doc__, __eq__, __float__,
__floor__, __floordiv__, __format__, __ge__,
__getattribute__, __getnewargs__, __gt__, __hash__,
__index__, __init__, __int__, __invert__, __le__,
__lshift__, __lt__, __mod__, __mul__, __ne__, __neg__,
__new__, __or__, __pos__, __pow__, __radd__, __rand__,
__rdivmod__, __reduce__, __reduce_ex__, __repr__,
__rfloordiv__, __rlshift__, __rmod__, __rmul__, __ror__,
__round__, __rpow__, __rrshift__, __rshift__, __rsub__,
__rtruediv__, __rxor__, __setattr__, __sizeof__, __str__,
__sub__, __subclasshook__, __truediv__, __trunc__,
__xor__, bit_length, conjugate, denominator, from_bytes,
imag, numerator, real, to_bytes]
dir(a) renvoie la liste des attributs et mthodes de lobjet rfrenc par la variable a.
En fait en Python tout est objet (ou rfrence un objet).
Dans le vocabulaire Python, une variable est appel nom et est lie un objet. Un objet peut
avoir plusieurs noms, par exemple dans le code ci-dessous o lobjet de type liste est connu
sous les noms s et t dans un code appelant et x dans la fonction foo appele.
def foo(x):
x[0] = 3
s = [0, 0, 7]
t = s
foo(s)
Tout objet Python x a un identificateur (donn par id(x)), un type (donn par type(x)), et
un contenu.
Lors de son excution, un programme Python gre des espaces de noms (namespace). Un
espace de nom est un mappage (mapping) de noms vers des objets. Des exemples de tels
143
espaces de noms sont donns par lensemble des noms globaux (donn par globals()) ou
des noms locaux une instance de fonction (donn par locals()).
Note:
Les espaces de nom peuvent tre implments sous forme de dictionnaires Python.
Ainsi, lassignation ainsi que le passage de paramtres une fonction modifient les espaces de noms et pas les objets eux mmes !
Par contre :
x = []
x.append(3)
cre un liste et un nom dans lespace de nom courant et ensuite appelle la mthode append() qui va modifier lobjet rfrenc par x.
144
def merge_sort(t):
if len(t) > 1:
(t1, t2) = (t[:len(t)//2], t[len(t)//2:])
t1 = merge_sort(t1)
t2 = merge_sort(t2)
# merge
res = []
while len(t1) > 0 and len(t2) > 0:
if t1[0] < t2[0]:
res.append(t1[0])
del t1[0]
else:
res.append(t2[0])
del t2[0]
res += t1 + t2
else:
res = t
return res
l= list("DCBA")
print(merge_sort(l))
Illustrons en particulier les valeurs des variables t1 et t2 avant et aprs les appels rcursifs et
au moment des return (pour simplifier les diagrammes dtats, on reprsente par le caractre
X la rfrence ce caractre X).
Etat dans linstance de fonction de niveau 1 (DCBA) avant les appels au niveau 2.
Objets
Trames
Variables globales
merge_sort
l
fonction merge_sort(t)
"D"
"C"
"D"
"C"
"B"
"A"
"B"
"A"
merge_sort
t
t1
t2
Etat dans linstance de fonction de niveau 2 (DC) avant les appels au niveau 3.
11.5. Gestion de la mmoire lexcution
145
Objets
Trames
Variables globales
merge_sort
fonction merge_sort(t)
"D"
"C"
"D"
"C"
"B"
"A"
"B"
"A"
merge_sort
t
t1
t2
merge_sort
t
t1
t2
"D"
"C"
146
Objets
Trames
Variables globales
merge_sort
fonction merge_sort(t)
"D"
"C"
"D"
"C"
"B"
"A"
"B"
"A"
merge_sort
t
t1
t2
merge_sort
t
t1
t2
"D"
"C"
merge_sort
t
147
Objets
Trames
Variables globales
merge_sort
l
fonction merge_sort(t)
"D"
"C"
"D"
"C"
"B"
"A"
"B"
"A"
merge_sort
t
t1
t2
merge_sort
t
t1
t2
"D"
"C"
merge_sort
t
148
Objets
Trames
Variables globales
merge_sort
l
fonction merge_sort(t)
"D"
"C"
"D"
"C"
"B"
"A"
"B"
"A"
merge_sort
t
t1
t2
merge_sort
t
t1
t2
res
"D"
empty list
"C"
"D"
149
Objets
Trames
Variables globales
merge_sort
l
fonction merge_sort(t)
"D"
"C"
"C"
"D"
"B"
"A"
"B"
"A"
merge_sort
t
t1
t2
Etat dans linstance de fonction de niveau 2 (BA) avant les appels au niveau 3.
150
Objets
Trames
Variables globales
merge_sort
fonction merge_sort(t)
"D"
"C"
"C"
"D"
"B"
"A"
"B"
"A"
merge_sort
t
t1
t2
merge_sort
t
t1
t2
"B"
"A"
151
Objets
Trames
Variables globales
merge_sort
fonction merge_sort(t)
"D"
"C"
"C"
"D"
"B"
"A"
"B"
"A"
merge_sort
t
t1
t2
merge_sort
t
t1
t2
"B"
"A"
merge_sort
t
152
Objets
Trames
Variables globales
merge_sort
l
fonction merge_sort(t)
"D"
"C"
"D"
"C"
"B"
"A"
"B"
"A"
merge_sort
t
t1
t2
merge_sort
t
t1
t2
"B"
"A"
merge_sort
t
153
Objets
Trames
Variables globales
merge_sort
l
fonction merge_sort(t)
"D"
"C"
"C"
"D"
"B"
"A"
"B"
"A"
merge_sort
t
t1
t2
merge_sort
t
t1
t2
res
"B"
empty list
"A"
"B"
154
Objets
Trames
Variables globales
merge_sort
l
fonction merge_sort(t)
"D"
"C"
"C"
"D"
"A"
"B"
"B"
"A"
merge_sort
t
t1
t2
Objets
Trames
Variables globales
merge_sort
l
merge_sort
t
fonction merge_sort(t)
"D"
"C"
"C"
"D"
"B"
"A"
"C"
"D"
t1
t2
empty list
res
"A"
"B"
155
156
CHAPTER
TWELVE
FICHIERS, PERSISTANCE ET
EXCEPTIONS
See Also:
Lire le chapitres 9 du livre de Grard Swinnen sur Python 3 ainsi que
http://docs.python.org/3/library/string.html et http://docs.python.org/3/library/exceptions.html
Effet
ouvre fichier en lecture
ouvre fichier en criture
ouvre fichier en criture en rajoutant aprs les donnes dj prsentes
retourne le contenu du fichier f
lit une ligne
renvoie la liste des lignes de f
crit la chane de caractres s dans le fichier f
ferme f
Lexemple suivant
utilise un fichier data.txt de donnes, contenant des expressions valuer,
157
utilise un fichier result.txt rsultat qui va recevoir pour chaque expression lue, le
texte de lexpression suivie de = et de la valeur obtenue grce la fonction eval()..
d=open("data.txt")
r=open("result.txt",w)
for i in d:
i = i.strip()
r.write("{0} = {1}\n".format(i, eval(i)))
d.close()
r.close()
Note: la mthode write reoit en paramtre un string qui sera imprim. Comme nous lavions
dj vu avec les print, la mthode s.format() peut tre fort utile. Son principe gnral est
dexaminer le string s et de remplacer les lments entre accolades avec des numros et des
informations de formatage, par les paramtres donns, formats tel que spcifi.
158
>>> t2 = pickle.loads(save_t)
>>> t2
[1, 2, 3]
>>> t == t2
True
>>> t is t2
False
Les fonctions dump et load (sans s) prennent un fichier comme argument supplmentaire
pour sauvegarder / rcuprer un objet depuis le fichier.
>>>
>>>
>>>
>>>
>>>
>>>
import pickle
f = open(data.txt, w)
d = {a:3, b:8,c:9}
pickle.dump(d, f)
f.close()
exit()
12.1.2 Shelve
Le pickling est un moyen simple de sauvegarder un objet (ou plusieurs objets squentiellement
dans le mme fichier). Un autre moyen, plus souple, est dutiliser le module shelve qui fournit une solution de persistance de type base de donnes. Concrtement, la base de donne
est crite (automatiquement) dans un fichier; la mthode shelve.open cre un fichier de
sauvegarde sil nexiste pas, et retourne un objet de type shelve; un shelve fonctionne (presque)
comme un dictionnaire. La plupart des oprations et mthodes des dictionnaires lui sont applicables; toute modification applique au shelve est (automatiquement) sauvegarde; la mthode
shelve.close permet de fermer le shelve, comme pour un fichier.
>>> import shelve
>>> t = [0,1,2,3]
>>> p = (1, 2, 3)
>>> i = 12
>>> s = hello
>>> db = shelve.open(data.db)
>>> db[liste] = t
>>> db[point] = p
>>> db[entier] = i
>>> db[chaine] = s
>>> print(db)
{liste: [0, 1, 2, 3], chaine: hello, entier: 12, point: (1, 2, 3)}
159
>>> db.close()
>>> exit() # ferme la session
12.2 Exceptions
Les exceptions sont frquentes, en particulier quand on manipule des fichiers.
>>> 3 / 0
ZeroDivisionError: integer division or modulo by zero
>>> t = list(range(4))
>>> t[4]
IndexError: list index out of range
>>> s = 2 + 2
TypeError: cannot concatenate str and int objects
>>> open(xyz.txt)
IOError: [Errno 2] No such file or directory: xyz.txt
>>> open(/etc/passwd, w)
IOError: [Errno 13] Permission denied: /etc/passwd
>>> open(music)
IOError: [Errno 21] Is a directory: music
160
>>> square_root(4)
2.0
>>> square_root(-2)
ValueError: a must be >= 0
>>> square_root(hello)
TypeError: a must be an integer or a float
La syntaxe pour lancer une exception est donc :
raise ExceptionType(message)
Les types dexceptions les plus frquentes que vous pouvez lancer sont :
Nom
ValueError:
TypeError:
IndexError:
IOError:
Cause
Erreur de valeur (par ex., ne respecte pas les pr-conditions)
Erreur de type pour un paramtre
Indice hors bornes
Erreur dentre / sortie (par ex. fichiers)
12.2. Exceptions
161
Comportement [le code principal est excut. Ds que celui-ci] produit une exception, il est
interrompu et le code spcifique est excut. Si aucune exception ne sest produite, le
code spcifique nest pas excut.
On dit quon rattrape (catch) une exception (dans une clause except).
Exemple :
try:
print(Avant)
raise ValueError(Test)
print(Apres)
except:
print(Gestion exception)
print(Fin)
Rsultat :
Avant
Gestion exception
Fin
Exemple :
try:
i = int(input(Entier : ))
print("Nous pouvons travailler avec", i)
except:
print("Je ne peux travailler quavec un entier")
print("Fin du programme")
Si on entre un entier :
Entier : 2
Nous pouvons travailler avec 2
Fin du programme
Sinon :
Entier : hello
Je ne peux travailler quavec un entier
Fin du programme
Il est possible de spcifier dans la clause except le type dexception que lon veut rattraper.
Exemple :
162
ok = False
while not ok:
try:
x = int(input("Please enter a number: "))
ok = True
except ValueError:
print("Oops! That was no valid integer. Try again...")
print("Now Im sure that", x, "is a valid integer.")
Remarque : dans cet exemple, si une autre exception quune ValueError se produit, elle
nest pas rattrape et le comportement sera celui habituel : le programme sarrte brutalement.
On peut spcifier plusieurs clauses except, pour grer diffrents types dexceptions.
Exemple :
try:
f = open(myfile.txt)
s = f.readline()
i = int(s.strip())
except IOError:
print Cannot open myfile.txt
except ValueError:
print(Could not convert, s.strip(), to an integer.)
except:
print(Unexpected error.)
raise
Remarque : le dernier cas permet de relancer les exceptions qui nont pas t spcifiquement
gres (par ex. si ce code est encapsul dans une fonction, lappelant pourra alors grer ces
exceptions).
On peut spcifier un tuple dexceptions grer dans une mme clause except.
Exemple :
try:
f = open(myfile.txt)
s = f.readline()
i = int(s.strip())
except (IOError, ValueError):
print(Cannot open file or cannot convert integer)
On peut placer un else, aprs les clauses except. Il sera excut si aucune exception nest
produite. Cest utile dans le cas o il faut excuter du code seulement si linstruction try na
pas provoqu dexceptions.
Exemple :
import sys
for arg in sys.argv[1:]:
try:
f = open(arg, r)
except IOError:
12.2. Exceptions
163
Remarque : lutilisation dune clause else est ici meilleure que dajouter du code dans le
try car cela vite dattraper accidentellement une exception qui serait provoque par une autre
instruction que open.
Pour obtenir des informations sur une exception, on peut la faire suivre par le mot-cl as et
le nom dune variable. Cette variable possde comme valeur un objet de type exception. En
affichant celle-ci, on obtient le message associ lexception.
Exemple :
try:
f = open(myfile.txt)
except IOError as e:
print(Cannot open myfile.txt:, e)
else:
s = f.readline().strip()
print(s)
Enfin, on peut ajouter une clause finally qui sera excute dans tous les cas (quil y ait une
exception ou pas). Cela permet de raliser des tches de clean-up comme fermer un fichier
quon savait ouvert avant le try, ou sauvegarder les donnes avant que le programme sarrte
suite une exception, etc. La clause finally est excute juste avant de sortir du try except, quune exception soit provoque ou non.
Exemple :
try:
raise KeyboardInterrupt
finally:
print(Goodbye, world!)
donne:
Goodbye, world!
KeyboardInterrupt
164
else:
print(tac)
time.sleep(1)
except KeyboardInterrupt:
print(Well done! You have found the exit!)
else:
print(BOOOM! You lose!)
finally:
print(Goodbye!)
Exercice : Quels sont les messages que la fonction suivante va afficher (et dans quel ordre) si
x = 2 et y = 1;
x = 2 et y = 0;
x = 2 et y = 1 ?
def divide(x, y):
try:
result = x / y
except ZeroDivisionError:
print("division by zero!")
else:
print("result is", result)
finally:
print("executing finally clause")
12.2. Exceptions
165
166
CHAPTER
THIRTEEN
CLASSES ET OBJETS
13.1 Objet et classe
Nous avons dj vu que lors de lexcution dun programme, lenvironnement dexcution
Python gre un espace mmoire, appel tas dexcution (runtime heap) et un autre espace
mmoire, appel pile dexcution (runtime stack) qui, en particulier, un instant donn, contient
un espace de noms par instance locale dune fonction en cours dexcution.
Nous avons galement vu quune variable est en fait un nom dun objet; manipuler cet objet se
fait grce cette variable qui lidentifie.
Tout objet Python x a :
un identificateur unique et dont la valeur est constante tout au long de sa vie (donn par
id(x)),
un type (donn par type(x)),
un contenu
Note:
a is b est quivalent id(a) == id(b).
Deux objets dont les dures de vie nont pas dintersection peuvent avoir le mme identificateur.
On ne peut pas changer lidentit dun objet ni son type (sauf exception). On peut changer le
contenu des objets modifiables (mutables) sans changer leur identit ou leur type.
Un objet a donc un identificateur et un type et peut avoir un ou plusieurs noms. Il a galement,
en fonction du type de lobjet, une ou plusieurs mthodes qui permettent soit de consulter le
contenu de lobjet soit, si lobjet est modifiable, de modifier son contenu.
Un objet a aussi des attributs (de donnes) qui sont manipuls par les mthodes __setattr__
/ __getattr__ pour les attributs ou __setitem__ / __getitem__ pour les composants
dune squence.
La section suivante explique comment Python permet au programmeur de dfinir des nouvelles
classes dobjets et ainsi de crer et manipuler des objets de cette classe.
167
la valeur de retour est une rfrence vers un objet de type Point, que lon assigne la
variable p;
crer un objet est une instanciation, et lobjet est une instance de la classe Point;
168
quand on affiche une instance, Python nous dit quelle classe elle appartient et o elle est
stocke en mmoire (sous la forme dune adresse reprsente par un nombre hexadcimal).
0xe73bd0
Point
13.2.3 Attributs
Une des proprits des objets est quil possde des attributs. Un attribut est une valeur.
Par exemple, pour reprsenter un point dans le plan, on a besoin de deux attributs (coordonnes
x et y).
Pour assigner un attribut un objet, on peut utiliser la notation point.
>>> p.x = 2.0
>>> p.y = 4.0
100.0
box
200.0
width
Point
height
corner
x
y
0.0
169
class Rectangle(object):
""" represente un rectangle dans le plan
attributs: width, height, corner
(coin inferieur gauche, Point)
"""
box = Rectangle()
box.width = 100.0
box.height = 200.0
box.corner = Point()
box.corner.x = 0.0
box.corner.y = 0.0
100.0
box
200.0
width
Point
height
corner
x
y
0.0
Notons que :
>>>
>>>
>>>
>>>
p1 =
p1.x
p1.y
p2 =
Point()
= 3.0
= 4.0
copy.copy(p1)
p1 == p2 retourne False !
En effet, pour les objets, le comportement par dfaut de == est le mme que loprateur is.
Mais ce comportement pourra tre modifi (dans la dfinition de classe).
Soit :
>>> box2 = copy.copy(box)
>>> box2 is box
False
Les objets rfrencs par box et box3 sont maintenant compltement spars (et indpendants).
13.2. Dfinition de nouvelles classes
171
13.2.6 Mthodes
Les attributs dun objet modlisent son tat, ses particularits dans la famille des objets du
mme type.
Exemples:
un point a comme coordonnes (2,3); un autre (4,5), mais ce sont deux points dans le
plan.
un rectangle a une largeur de 10, une hauteur de 20, et un coin infrieur droit en (3,7).
Un autre sera plus grand, ou plus droite, mais il reste un rectangle.
un temps dans la journe correspond la manire dont nous dcrivons un temps donn,
c--d, une heure, une minute et une seconde.
Mais un objet possde dautres proprits que ses attributs : les mthodes associes son type
(sa classe).
Une mthode est une fonction qui est dfinie pour un type donn et qui sapplique sur les objets
de ce type.
Intuitivement, une mthode est une action applique sur un objet (et peut avoir besoin dautres
entres que lobjet sur lequel elle est applique, et peut produire galement des sorties).
Exemple: Pour manipuler des heures nous pouvons dfinir une classe Time :
class Time(object):
""" represente un temps (heure).
attributs: hour, minute, second
"""
Note: il existe dautres types de mthodes (de classes et statiques) qui ne seront pas vues dans
ce cours.
Notons que lon a ici une bauche de programmation oriente-objets :
>>> start.display()
09:45:00
173
01:36:00
>>> start.add(duration)
>>> start.display()
11:21:00
class Time(object):
# ...
def __str__(self):
return "{0:02d}:{1:02d}:{2:02d}".format(self.hour, self.minute, self.secon
# ...
174
>>> t = Time(8,30)
>>> print(t)
08:30:00
>>> str(t)
08:30:00
Le premier donnant le string qui sera imprim, lautre le string de la reprsentation non ambige
(donc entour de quotes pour indiquer quun lobjet est lui mme un string).
Lors dune session interactive, lorsque vous tapez juste le nom de lobjet x suivi de la touche
clavier de retour la ligne, linterprteur Python ralise un print(repr(x)).
>>> x = 36
>>> x
36
>>> s = Hello
>>> s
Hello
>>> print(s)
Hello
>>>
Dans le code prcdent, attribut __class__ renvoie un string avec le nom de la classe dfnie
(dans ce cas ci <class __main__.Time>)
13.2. Dfinition de nouvelles classes
175
176
>>> t3 = t1 + t2
>>> print(t3)
18:10:00
Problme : malheureusement, cette addition nest pas commutative. Si lentier est le premier
oprateur, on obtient une erreur.
>>> 1200 + t3
TypeError: unsupported operand type(s) for +: int and Time
Le problme vient du fait quau lieu de demander un objet Time dajouter un entier, on fait le
contraire, et on ne peut pas modifier les objets de type entiers pour quils connaissent les objets
Time.
Solution : crire la mthode spciale __radd__ (right-side add). Cette mthode est automatiquement invoque quand un objet Time est le membre droit dun oprateur + (et que la
mthode __add__ nexiste pas ou retourne NotImplemented sur le membre gauche).
class Time(object):
# ...
def __radd__(self, other):
return self.__add__(other)
# ...
Note: les mthodes spciales peuvent tre galement invoques la main, comme nimporte
quelle autre mthode.
13.2.10 Polymorphisme
On a dj vu quune fonction peut sappliquer sur diffrents types dobjets, pour peu que le
corps de la fonction applique des oprateurs disponibles pour ce type dobjet. On appelle cette
caractristique le polymorphisme. Cela signifie par exemple que lon peut utiliser la fonction
sum sur nos objets Time !
>>> sum(range(10))
45
>>> t = [Time(1,30), Time(2), Time(3,45,30)]
>>> total_time = sum(t)
>>> print(total_time)
07:15:30
177
178
CHAPTER
FOURTEEN
(consultation
http://fr.wikipedia.org/wiki/Histoire_des_langages_de_programmation (consultation 4
dcembre 2012)
http://en.wikipedia.org/wiki/Programming_language (consultation 4 dcembre 2012)
http://fr.wikipedia.org/wiki/Langage_de_programmation
2012)
(consultation
dcembre
14.1 Introduction
Un langage de programmation est une notation artificielle, destine exprimer des algorithmes
et produire des programmes. Dune manire similaire une langue naturelle, un langage de
programmation est fait dun alphabet, un vocabulaire, des rgles de grammaire (syntaxe), et
des significations (smantique). Les langages de programmation servent dcrire les structures
des donnes qui seront manipules par lordinateur, et indiquer comment sont effectues les
manipulations, selon quels algorithmes. Ils servent de moyens de communication par lesquels
le programmeur communique avec lordinateur, mais aussi avec dautres programmeurs; les
programmes tant dordinaire cris, lus, compris et modifis par une communaut.
Un langage de programmation est mis en oeuvre par un traducteur automatique: compilateur
ou interprteur.
179
14.1.1 Compilateur
Un compilateur est un programme informatique qui transforme un code source crit dans un
langage de programmation (le langage source) en un autre langage informatique (le langage
cible).
programme source
Compilateur
code objet
Pour quil puisse tre exploit par la machine, le compilateur traduit le code source, crit dans
un langage de haut niveau dabstraction, facilement comprhensible par lhumain, vers un langage de plus bas niveau, un langage dassemblage ou langage machine. Dans le cas de langage
semi-compil (ou semi-interprt), le code source est traduit en un langage intermdiaire, sous
forme binaire (code objet ou bytecode), avant dtre lui-mme interprt ou compil.
Un compilateur effectue les oprations suivantes : analyse lexicale, pr-traitement (prprocesseur), analyse syntaxique (parsing), analyse smantique, gnration de code intermdiaire,
optimisation de code et gnration de code final.
Quand le programme compil (code objet) peut tre excut sur un ordinateur dont le processeur ou le systme dexploitation est diffrent de celui du compilateur, on parle de compilateur crois (cross-compiler).
Structure et fonctionnement
La tche principale dun compilateur est de produire un code objet correct qui sexcutera
sur un ordinateur. La plupart des compilateurs permettent doptimiser le code, cest--dire
quils vont chercher amliorer la vitesse dexcution, ou rduire loccupation mmoire du
programme.
180
Java
Haskell
Prolog
Image
P7
RISC
Certains compilateurs effectuent des traitements substantiels sur la partie intermdiaire, devenant une partie centrale part entire, indpendante la fois du langage source et de la
machine cible. On peut ainsi crire des compilateurs pour toute une gamme de langages et
darchitectures en partageant la partie centrale, laquelle on attache une partie avant par langage et une partie arrire par architecture.
Les tapes de la compilation incluent :
le prtraitement, ncessaire pour certaines langues comme C, qui prend en charge la
substitution de macro et de la compilation conditionnelle. Gnralement, la phase de
prtraitement se produit avant lanalyse syntaxique ou smantique.
lanalyse lexicale (scanning), qui dcoupe le code source en petits morceaux appels
jetons (tokens). Chaque jeton est une unit atomique unique de la langue (units lexicales
ou lexmes), par exemple un mot-cl, un identifiant ou un symbole. Le logiciel qui
effectue une analyse lexicale est appel un analyseur lexical ou un scanner. Deux outils
classiques permettent de construire plus aisment des scanners : lex et flex.
lanalyse syntaxique implique lanalyse de la squence de jetons pour identifier la structure syntaxique du programme. Cette phase sappuie gnralement sur la construction
dun arbre danalyse ; on remplace la squence linaire des jetons par une structure en
arbre construite selon la grammaire formelle qui dfinit la syntaxe du langage. Par exemple, une condition est toujours suivie dun test logique (galit, comparaison...). Larbre
danalyse est souvent modifi et amlior au fur et mesure de la compilation. Yacc et
GNU Bison sont les outils les plus utiliss pour construire des analyseurs syntaxiques.
lanalyse smantique est la phase durant laquelle le compilateur ajoute des informations
14.1. Introduction
181
smantiques larbre danalyse et construit la table des symboles. Cette phase fait un
certain nombre de contrles: vrifie le type des lments (variables, fonctions, ...) utiliss dans le programme, leur visibilit, vrifie que toutes les variables locales utilises
sont initialises, .... Lanalyse smantique ncessite habituellement un arbre danalyse
complet, ce qui signifie que cette phase fait suite la phase danalyse syntaxique, et
prcde logiquement la phase de gnration de code ; mais il est possible de replier ces
phases en une seule passe.
la transformation du code source en code intermdiaire ;
lapplication de techniques doptimisation sur le code intermdiaire : cest--dire rendre
le programme meilleur selon son usage;
la gnration de code avec lallocation de registres et la traduction du code intermdiaire
en code objet, avec ventuellement linsertion de donnes de dbogage et danalyse de
lexcution.
Scanning
Parsing
Errors
management
Semantic
Analysis
Intermediate
code generation
Optimisation
Final code
generation
}
}
Analysis
Symbol
table
182
Synthesis
14.1.2 Interprteur
Un interprteur est un outil informatique ayant pour tche danalyser, de traduire et dexcuter
un programme crit dans un langage informatique. De tels langages sont dits langages interprts.
Linterprteur est capable de lire le code source dun langage sous forme de script, habituellement un fichier texte, et den excuter les instructions (une la fois) aprs une analyse syntaxique du contenu. Cette interprtation conduit une excution daction ou un stockage de
contenu.
Principe
Linterprtation consiste en lexcution dynamique du programme par un autre programme
appel interprteur, plutt que sur sa conversion (compilation) en un autre langage (par exemple
le langage machine) ; ainsi la traduction et lexcution sont simultanes.
Le cycle dun interprteur est le suivant :
lire et analyser une instruction (ou expression) ;
si linstruction est syntaxiquement correcte, lexcuter (ou valuer lexpression) ;
passer linstruction suivante.
Ainsi, contrairement au compilateur, linterprteur excute les instructions du programme (ou
en value les expressions), au fur et mesure de leur lecture pour interprtation. Du fait de
cette phase sans traduction pralable, lexcution dun programme interprt est gnralement
plus lente que le mme programme compil.
La plupart des interprteurs nexcutent plus la chane de caractres reprsentant le programme,
mais une forme interne, telle quun arbre syntaxique.
En pratique, il existe souvent des mlanges entre interprteurs et compilateurs.
Lintrt des langages interprts rside principalement dans la facilit de programmation et
dans la portabilit. Les langages interprts facilitent normment la mise au point des programmes car ils vitent la phase de compilation, souvent longue, et limitent les possibilits de
bogues. Il est en gnral possible dexcuter des programmes incomplets, ce qui facilite le
dveloppement rapide dapplications ou de prototypes dapplications.
Ainsi, le langage BASIC fut le premier langage interprt permettre au grand public daccder
la programmation, tandis que le premier langage de programmation moderne interprt est
Lisp.
La portabilit permet dcrire un programme unique, pouvant tre excut sur diverses platesformes sans changements, pourvu quil existe un interprteur spcifique chacune de ces
plates-formes matrielles.
Les inconvnients dune interprtation plutt quune compilation sont la lenteur lors de
lexcution, comme dj voqu, mais aussi labsence de contrle pralable sur la structure
du programme et les types des lments manipuls avant le dbut de son excution.
14.1. Introduction
183
Un certain nombre de langages informatiques sont aujourdhui mis en oeuvre au moyen dune
machine virtuelle applicative. Cette technique est mi-chemin entre les interprteurs tels que
dcrits ici et les compilateurs. Elle offre la portabilit des interprteurs avec une bonne efficacit. Par exemple, des portages de Java, Lisp, Scheme, Ocaml, Perl (Parrot), Python, Ruby, Lua,
C, etc. sont faits via une machine virtuelle.
Note: Lors de la conception dun programme dans un langage interprt, tant donn labsence
dun compilateur qui contrle les types, la visibilit, ..., les techniques de conception insistent
fortement sur la notion de test unitaire qui teste si possible lentiret du code dune fonction
ou dune classe, la fois au niveau fonctionnalit quen testant lensemble des lignes de code
crites, avant lintgration de ce code dans le reste du programme.
Notons cependant que tester ou vrifier la logique dun code est gnralement plus complexe
et doit se faire tant avec les langages interprts que compils.
Historique
Avec lapparition du langage compil Pascal et de compilateurs commerciaux rapides comme
Turbo Pascal, les langages interprts connurent partir du milieu des annes 1980 un fort
dclin. Trois lments changrent la donne dans les annes 1990 :
avec la ncessit dautomatiser rapidement certaines tches complexes, des langages de
programmation interprts (en fait, semi-interprts) de haut niveau comme, entre autres,
Tcl, Ruby, Perl ou Python se rvlrent rentables ;
la puissance des machines, qui doublait tous les dix-huit mois en moyenne (selon la loi de
Moore), rendait les programmes interprts des annes 1990 dune rapidit comparable
celle des programmes compils des annes 1980 ;
il est bien plus rapide de faire voluer un programme interprt. Or la vague Internet demandait une rponse trs rapide aux nouveaux besoins du march. amazon.com fut, dans
sa premire version, dvelopp largement en Perl. Smalltalk permettait un prototypage
trs rapide dapplications.
14.1.3 Runtime
Un runtime est lenvironnement dexcution du programme qui utilise un ensemble de bibliothques logicielles pour mettre en oeuvre le langage de programmation, permettant deffectuer
des oprations simples telles que copier des donnes, ou des oprations beaucoup plus complexes telles que le travail de garbage collection (ramasse-miettes).
Lors de la traduction dun programme vers le langage machine les oprations simples sont
traduites en les instructions correspondantes en langage machine tandis que les oprations complexes sont traduites en des utilisations de fonctions du runtime.
Chaque langage de programmation a une manire conventionnelle de traduire lexcution de
procdures ou de fonctions, de placer les variables en mmoire et de transmettre des paramtres.
Ces conventions sont appliques par le runtime. Le runtime sert galement mettre en oeuvre
184
certaines fonctionnalits avances des langages de programmation telles que le garbage collector qui rcupre de lespace mmoire 2 quand cest ncessaire pour continuer lexcution du
programme.
"a"..."z"
lc_letter (lc_letter | "_")*
dfinit un lment lc_letter comme tant nimporte quelle lettre alphabtique minuscule
et name comme tant nimporte quelle squence dau moins une lettre alphabtique qui peut
tre suivie de zro ou plus de caractres "_" ou alphabtique.
Dans ce mtalangage,
ce qui est rellement reprsent est mis entre " ";
le symbole ::= signifie que le nom gauche reprsente nimporte quel lment compatible avec la dfinition droite (par exemple dans lc_letter ::= "a"..."z");
"a"..."z" signifie tous les caractres entre "a" et "z";
(r1|r2) (par exemple dans (lc_letter | "_")) reprsente le choix entre la possibilit r1 et r2;
r* (par exemple dans lc_letter*) reprsente la rptition zro, une ou plusieurs fois
un lment de r;
r+ (par exemple dans lc_letter+) reprsente la rptition une ou plusieurs fois un
lment de r;
[ r ] reprsente loption: zro ou une fois r.
Ainsi les constantes (littraux) entiers et rel Python
http://docs.python.org/3/reference/lexical_analysis.html) par :
2
sont
dfinis
(voir
185
integer
decimalinteger
nonzerodigit
digit
octinteger
hexinteger
bininteger
octdigit
hexdigit
bindigit
::=
::=
::=
::=
::=
::=
::=
::=
::=
::=
et
floatnumber
pointfloat
exponentfloat
intpart
fraction
exponent
::=
::=
::=
::=
::=
::=
pointfloat | exponentfloat
[intpart] fraction | intpart "."
(intpart | pointfloat) exponent
digit+
"." digit+
("e" | "E") ["+" | "-"] digit+
186
Smantique dynamique
Pour un langage compil, cest la partie de contrle qui a lieu lors de lexcution du programme.
Par exemple, si le type prcis dune variable ne peut tre connue qu lexcution, le contrle
de type est dynamique.
Note: Si un programme sexcute sans erreur (exception,...) mais ne fournit pas le bon rsultat,
on parle d erreur de logique ou d erreur de logique de conception.
14.2.3 Types
Un type de donne dfinit les valeurs que peut prendre une donne, ainsi que les oprateurs qui
peuvent lui tre appliqus.
Un type peut tre:
simple (prdfinis ou non): par exemple: boolen, entier, rel, pointeur (cest--dire
adresse), ou
compos : par exemple, string, tuple, dictionnaire, liste, structure, classe.
Si on prend lexemple de C++ on y trouve des variables simples (par exemple entire), des
pointeurs et des rfrences.
Par exemple:
int i = 18;
int *p = &i;
int &j = i;
int tab[5] = {0,0,0,0,0};
*p = 36;
j = 36;
187
Par contre, Python na pas la notion de pointeur, qui permet explicitement de manipuler des
adresses dans des variables et qui permet tant damusement en programmation C++ (y compris
labsence de garbage collector).
Note: En pratique pointeur (comme p dans le programme plus haut) et rfrence (comme
j) manipulent tous les deux des adresses. La diffrence est que dans le cas du pointeur, si
lutilisateur veut manipuler la variable ou lobjet point, il doit lexprimer explicitement
(comme avec *p = 36 qui assigne la variable pointe par p, cest--dire i, la valeur 36).
Avec les rfrences, le drfrenage (dereferencing) est automatique; on ne peut manipuler
ladresse mais uniquement lobjet rfrenc (comme avec j = 36 qui a le mme effet que
linstruction prcdente).
int i = 0;
189
En 1801, le mtier Jacquard utilisait des trous dans des cartes perfores pour reprsenter
les mouvements du bras du mtier tisser, et ainsi gnrer automatiquement des motifs
dcoratifs.
1840 : Collaboratrice de Babbage, Ada Lovelace, mathmaticienne, dfinit le principe
des itrations successives dans lexcution dune opration. En lhonneur du mathmaticien perse Al Khawarizmi (820), elle nomme le processus logique dexcution dun
programme : algorithme (dformation de Al Khawarizmi). Ada Lovelace a traduit le mmoire du mathmaticien italien Luigi Menabrea sur la Machine analytique, la dernire
machine propose par Charles Babbage.
1854 : Boole publie un ouvrage dans lequel il dmontre que tout processus logique peut
tre dcompos en une suite doprations logiques (ET, OU, NON) appliques sur deux
tats (ZERO-UN, OUI-NON, VRAI-FAUX, OUVERT-FERME).
1887: Herman Hollerith a cr une machine cartes perfores qui a servi au recensement
de 1890.
1863-1895 : On peut galement considrer les rouleaux en papier dun pianola (piano
mcanique) comme un programme limit un domaine trs particulier, quoique non
destin tre exploit par des humains.
191
1958 : LISP (langage impratif et fonctionnel) , spcialis dans le traitement des listes
(LISt Processor), invent par John McCarthy et al. (exemple: fonction factorielle)
Vue densemble :
192
193
1970 - Pascal
1970 - Forth
1972 - C
1972 - Smalltalk
1972 - Prolog
1973 - ML
1978 - SQL (Structured Query Language), au dpart seulement un langage de requtes,
puis tendu par la suite la construction de programme procdural de type SQL/PSM,
PL/SQL,...
194
195
197
198
CHAPTER
FIFTEEN
200
15.2.4 Espaces
Pas despace juste aprs une parenthse ouvrante ou avant une parenthse fermante. espace
aprs une virgule.
201
Ne modifiez pas les paramtres. Exemple: si vous recevez une borne infrieure first et
une suprieure last et que vous devez itrer de la premire la dernire, nincrmentez
pas first dans la boucle, car la signification nen serait plus claire; crez plutt une variable locale pos initialise first.
Sauf si la fonction a comme but de modifier la (structure de) donnes reue en paramtre;
dans ce cas la fonction ne renvoie pas de valeur.
Testez le code au fur et mesure du dveloppement
Crez des scnarios de test, pour lesquels vous choisissez les donnes fournies et vous
vrifiez que le rsultat de la fonction est conforme ce que vous attendez.
Vrifiez les cas particuliers et les conditions aux limites. Exemple: pour le calcul dune
racine carre, que se passe-t-il lorsque le paramtre est un nombre ngatif?
15.3.2 Programmation
Style de programmation
Utilisez la forme raccourcie if(is_leap_year(2008)) plutt que la forme quivalente
if(is_leap_year(2008) == true)
Utilisez la forme return expression_bool plutt que la forme quivalente
if expression bool : # Code proscire !!
res = true
else:
res = false
return res
Nexcutez pas plusieurs fois une fonction alors quune excution suffit en retenant le
rsultat.
Prcisez le domaine de validit des paramtres et grez les erreurs ventuelles avec des
exceptions.
Nutiliser pas les exceptions pour faire des tests lis lalgorithme et non la gestion des
erreurs.
Quelques erreurs classiques
Vous essayez dutiliser une variable avant de lavoir initialise.
Lalignement des blocs de code nest pas respect.
Vous oubliez de fermer un fichier que vous avez ouvert.
203
204
CHAPTER
SIXTEEN
GLOSSAIRE
__main__ le module __main__ est le module par dfaut
algorithme squence dtapes prcises et non ambigus pouvant tre excutes de faon automatique
appel de fonction instruction qui excute une fonction. Elle consiste en le nom de la fonction
suivi par une liste darguments entre parenthses.
argument valeur fournie une fonction quand une fonction est appele. Cette valeur est
assigne au paramtre correspondant dans le corps fonction.
assignation instruction qui assigne une valeur une variable (variable = valeur)
boucle infinie une boucle dont la condition de fin nest jamais satisfaite.
bug une erreur dans un programme
chane vide chane sans caractre et de longueur 0, reprsente par deux apostrophes.
chemin chane de caractres qui identifie un fichier.
chemin absolu chemin qui commence au rpertoire du plus haut niveau du systme.
chemin relatif chemin qui commence depuis le rpertoire courant.
code source un programme crit en langage de haut niveau avant sa compilation ou son interprtation
commentaire information dans un programme destine au lecteur du code source et qui na
pas deffet sur lexcution du programme
compiler traduire un programme crit dans un langage de haut niveau en un langage de bas
niveau en une fois, en vue de sa future excution
concatner joindre bout bout des chanes de caractres
condition expression boolenne dans une instruction conditionnelle qui dtermine quelle
branche doit tre excute
conditions chanes instruction conditionnelle avec une srie de branches alternatives
conditions imbriques instruction conditionnelle qui apparat lintrieur dune autre instruction conditionnelle
205
constante valeur qui ne peut tre modifie, par opposition aux variables
corps dune fonction (body) squence dinstructions dans une dfinition de fonction.
deboguer le processus didentification et de correction des 3 types derreurs de programmation
dcrmenter mettre jour une variable en diminuant sa valeur (souvent de -1).
dfinition de fonction instruction qui cre une nouvelle fonction, spcifie son nom, ses
paramtres, et les instructions quelle doit excuter.
diagramme dtat reprsentation graphique dun ensemble de variables et des valeurs
quelles rfrent
dictionnaire squence mutable de paires clef-valeur.
division entire opration qui divise deux nombres entiers et retourne un entier (uniquement
la partie entire du rsultat)
docstring commentaire multiligne plac au dbut du corps dune fonction, destin sa documentation.
en-tte dune fonction (header) la premire ligne de la dfinition dune fonction (def, nom de
la fonction, liste darguments, caractre deux points).
erreur de syntaxe une violation des rgles dcriture dans un programme qui le rend impossible interprter ou compiler
erreur smantique une erreur dans un programme qui fait que quelque chose de diffrent de
ce que le programmeur voulait raliser se produit
exception une erreur dtecte pendant lexcution du programme
excutable un programme aprs compilation, prt tre excut
expression combinaison de variables, doprateurs et de valeurs et dont le rsultat est une
valeur
expression boolenne expression qui retourne soit vrai (True), soit faux ( False)
lment (item) une des valeurs dune squence.
valuer simplifier une expression en appliquant les oprations dans le but dobtenir la valeur
rsultat
fichier texte squence de caractres stocke dans un support permanent (disque dur, CDROM, etc.).
flot dexcution ordre dans lequel les instructions sont excutes dans un programme.
fonction squence dinstructions qui possde un nom. Les fonctions peuvent prendre des
arguments (ou pas) et peuvent retourner une valeur (ou pas : retourne None).
hachable proprt dun type immuable lui permettant dtre converti de manire dterministe
en un nombre entier.
immuable proprit dune squence dont les lments ne peuvent tre assigns.
206
oprateur symbole spcial qui reprsente une opration simple comme laddition, la multiplication ou la concatnation de chanes de caractres
oprateur de comparaison un des oprateurs qui comparent ses oprandes : ==, !=, <, >, <=
et >=.
oprateur logique un des oprateurs qui combinent des expressions boolennes : and, or et
not.
paramtre variable utilise lintrieur dune fonction qui rfre la valeur passe en argument.
parser examiner un programme et analyser sa structure syntaxique
portabilit le fait quun programme puisse tre excut sur plus dune sorte dordinateurs
porte (scope) la porte dune variable est la zone du programme dans laquelle elle est
disponible. La porte dune variable locale ou dun paramtre est limite sa fonction.
postcondition condition quun code ou une fonction garantit si lensemble des prconditions
sont respectes (= la validit de son rsultat)
prcondition condition que le code ou la fonction suppose vraie pour les entres, avant
dexcuter son travail
print instruction qui ordonne linterprteur Python dafficher une valeur lcran
programme squence dinstructions crites dans un langage de programmation particulier et
qui spcifie comment raliser un calcul ou une tche
prompt les caractres >>> qui indiquent que linterprteur est prt recevoir des instructions
rattraper (une exception) on rattrape une exception dans une clause except, pour y excuter du code spcifique.
rgles de prcdence ensemble de rgles dfinissant lordre dans lequel les expressions impliquant plusieurs oprateurs et oprandes sont values
rpertoire (dossier) un rpertoire possde son propre nom et contient une collection de
fichiers ou dautres rpertoires.
rsolution de problme processus de formulation dun problme (spcification), trouver une
solution et exprimer la solution
script un programme stock dans un fichier (en vue dtre interprt)
smantique la signification (la logique, le sens) dun programme
squence ensemble ordonn, cest--dire un ensemble de valeurs o chaque valeur est identifie par un index entier.
syntaxe la structure et les rgles dun langage de programmation
traceback liste de fonctions qui sont exctues, affiches quand une exception se produit.
tranche (slice) partie dune chane spcifie par un intervalle dindice s.
type classe de valeurs (exemple: entiers (int), rels (float), chanes de caractres (str))
208
valeur unit lmentaire de donnes, comme un nombre ou une chane de caractres, quun
programme manipule
valeur de retour le rsultat dune fonction. Si un appel de fonction est utilis comme une
expression, sa valeur de retour est la valeur de lexpression.
variable nom qui rfre une valeur
variable locale variable dfinie lintrieur dune fonction. Une variable locale ne peut tre
utilise qu lintrieur de sa fonction.
209
210
CHAPTER
SEVENTEEN
17.1 Fonctions
int(x) : convertit x, de type float ou str, en entier
float(x) : convertit x, int ou str, en rel
str(x) : convertit x, int ou float, en str
list(x) : convertit x en list
tuple(x) : convertit x en tuple
help(x) : aide sur x
dir(x) : liste des attributs de x
type(x) : type de x
print ... : imprime
input(x) : imprime le string x et lit le string qui est introduit au clavier
round(x) : valeur arrondie du float x
len(s) : longueur de la squence s
range([start], stop, [step]) : retourne une suite arithmtique dentiers
17.2 Modules
math : accs aux constantes et fonctions mathmatique (pi, sin(), sqrt(x), exp(x),floor(x)
(valeur plancher), ceil(x) (valeur plafond), ...) : exemple: math.ceil(x)
211
213
17.8 Exceptions
try:
...
raise ...
...
except:
...
else:
...
finally:
...
214
INDEX
Symbols
lment, 206
valuer, 206
__main__, 205
A
algorithme, 205
appel de fonction, 205
argument, 205
assignation, 205
B
boucle infinie, 205
bug, 205
C
chane vide, 205
chemin, 205
chemin absolu, 205
chemin relatif, 205
code source, 205
commentaire, 205
compiler, 205
concatner, 205
condition, 205
conditions chanes, 205
conditions imbriques, 205
constante, 206
corps dune fonction, 206
D
dcrmenter, 206
dfinition de fonction, 206
deboguer, 206
diagramme dtat, 206
dictionnaire, 206
division entire, 206
docstring, 206
F
fichier texte, 206
flot dexcution, 206
fonction, 206
H
hachable, 206
I
immuable, 206
import, 207
incrmenter, 207
instruction, 207
instruction conditionnelle, 207
interprter, 207
introspection, 207
itration, 207
L
lancer (une exception), 207
langage de bas niveau, 207
langage de haut niveau, 207
langage impratif, 207
littral, 207
M
mthode, 207
mode interactif, 207
mode script, 207
215
module, 207
mot-cl, 207
N
notation point, 207
O
objet, 207
objet fonction, 207
objet module, 207
oprande, 207
oprateur, 208
oprateur de comparaison, 208
oprateur logique, 208
P
paramtre, 208
parser, 208
porte, 208
portabilit, 208
postcondition, 208
prcondition, 208
print, 208
programme, 208
prompt, 208
R
rpertoire, 208
rsolution de problme, 208
rgles de prcdence, 208
rattraper (une exception), 208
S
smantique, 208
squence, 208
script, 208
syntaxe, 208
T
traceback, 208
tranche, 208
type, 208
V
valeur, 209
valeur de retour, 209
variable, 209
variable locale, 209
216
Index