DÉPARTEMENT MATH ET INFORMATIQUE

Informatique II

Pr. SADIQ Mounir

2023-2024
Présentation
du module
 Objectif
les compétences à acquérir visées par ce module sont :

- Comprendre et utiliser des fonctions et des

procédures en Python.

- Appliquer la récursivité pour résoudre des problèmes

spécifiques.

- Manipuler des fichiers en Python pour lire, écrire et

modifier des données.

- Calculer la complexité d'un algorithme.

 Présentation du module

• Organisations:

• Cours
• TDs
• TPs

4
 Présentation du module

• Notes
• Examen: 70%
• TPs: 30 %

5
Introduction
 C’est quoi un algorithme?
Pour résoudre un problème informatique, on crée un programme.

Un programme est la réalisation (l’implémentation) d’un

algorithme au moyen d’un langage donné sur une architecture
donnée.

Il existe de nombreux langages de programmation: python, C,

C++, java, javaScript,,,,, Tous les langages de programmation
partagent le même point commun: « la logique »
La logique de programmation est un algorithme

7
 Algorithme vis-à-vis langages de
programmation
Donc, l’algorithme:
- est une suite des instructions ordonnées pour résoudre un
problème

- est indépendant de toute architecture matérielle ou logicielle

- N’est pas destiné à être exécuté par la machine

8
 Représentation
• Organigramme
• Pseudo-code

•  on utilise souvent pseudo code car il est

proche d’un vrai programme

9
 Représentation
En tête

Nom programme

Déclaration
Programme
Constantes
principale
Variables
Sous programme

Corps du programme

Lecture/Ecriture
Affectation
Structures de contrôle
Appel du sous programme
10
 01

Résolution d'un
problème
algorithmique
Résolution de problème
Compréhension de
problème

Analyse

Conception

Résolution

Optimisation

12
 Résolution de problème
Compréhension de Problème
Formulation et reformulation du texte qui décrit le problème à
résoudre
Analyse
Données en entrée
Résultat attendu
Traitement
Conception
- décomposition du problème en sous problème (Top down design)
- spécification du problème ou de chaque sous-problème
Représentation
- algorithme logique du problème ou de chaque sous problème
- algorithme de programmation du problème

13
 14

Analyse d'un problème

algorithmique
• Étant donné le rayon d’un cercle, calculer la
surface et la circonférence d’un cercle.

Entrée Traitement sortie

Pi Pi*Rayon*Rayon la surface d’un cercle

Rayon

Pi Pi*2*Rayon la circonférence d’un

Rayon cercle
 Structure d’un algorithme

Surface (r) Circonférence (r)

Constante: Constante:
PI=3,14 PI=3,14
Variable: Variable:
r: réel r: réel
Début Début
Ecrire (« la surface est: », PI*r*r) Ecrire (« la circonférence est: » ,
Fin PI*2*r)
Fin

15
Structure d’un algorithme
Début

Lire rayon

Calculer surface
PI*rayon*rayon

Calculer circonférence
PI*2*rayon

Afficher la circonférence et la surface

Fin 16
Résolution de problème
Compréhension de
problème

Analyse

Conception

Résolution

Optimisation

17
 Conception: Décomposer pour
simplifier

• Dès qu’on commence à écrire des

programmes importants, il devient difficile
d’avoir une vision globale sur son
fonctionnement et de traquer les erreurs.

18
 Résolution d’un problème
Problème
Formulation et reformulation du texte qui décrit le problème à
résoudre
Analyse
Données en entrée
Résultat attendu
Traitement
Conception: Décomposer pour simplifier
- décomposition du problème en sous problème
- spécification du problème ou de chaque sous-problème
Représentation
- algorithme logique du problème ou de chaque sous problème
- algorithme de programmation du problème

19
 Top down design technique:

Problème complexe
Sous problème 1 Sous problème 2

Sous Sous Sous Sous Sous Sous

problème problème problème problème problème problème
1.1 1.2 1.3 2.1 2.2 2.3
20
 Exemple
• Calculer la surface totale d’un cylindre.
• 1- comprendre le problème:

•  La surface totale d’un cylindre A2 est la somme de la surface latérale A1 et de la

surface des deux extrémités de ce cylindre.
•  La surface latérale du cylindre correspond à un rectangle (enroulé autour du
cylindre) dont la hauteur est h et la largeur est égale à la circonférence du cercle de
rayon r.
•

A2 = A1 + 2πr²
=> A2 = 2πr x h + 2πr²
=> A2 = 2πr (h + r)

21
 Top down design technique
• Calculer la surface totale d’un cylindre

• Résoudre ce problème revient à résoudre les sous

problèmes suivants :
– calculer la surface d’un cercle
– calculer la circonférence d’un cercle
– calculer la surface latéral d’un cylindre

• Chacun de ces sous-problèmes devient un

nouveau problème à résoudre

22
 Top down design technique

Calcul la surface totale

d’un cylindre (A2)

la surface latérale d’un

cylindre (A1): la surface des deux
La circonférence d’un extrémités de ce cylindre :
cercle* h 2*la surface d’un cercle

La circonférence la surface d’un

d’un cercle: cercle :
2πr π*r*r

23
 Top down design technique
• Cette décomposition permet:

– d'aborder le problème progressivement en créant

des niveaux de description de plus en plus
détaillés.
– de réutiliser la résolution de certains sous-
problèmes pour résoudre de nouveaux
problèmes.

24
 25

Analyse d'un problème

algorithmique
A2 = A1 + 2πr²
=> A2 = 2πr x h + 2πr²
=> A2 = 2πr (h + r)

Entrée Traitement sortie

Π=3,14 πr *r la surface d’un cercle
r

Π =3,14 2πr la circonférence d’un

r cercle

la surface d’un cercle

2πr (h + r) la surface totale d’un
la circonférence d’un
cylindre
cercle
 Résolution d’un problème
Problème
Formulation et reformulation du texte qui décrit le problème à
résoudre
Analyse
Données en entrée
Résultat attendu
Traitement
Conception
- décomposition du problème en sous problème
- spécification du problème ou de chaque sous-problème
Représentation
- algorithme logique du problème ou de chaque sous problème
- algorithme de programmation du problème

26
 DÉPARTEMENT MATH ET INFORMATIQUE

Informatique II

Pr. SADIQ Mounir

2023-2024
 Exemple
• Calculer la surface totale d’un cylindre.
• 1- comprendre le problème:

•  La surface totale d’un cylindre A2 est la somme de la surface latérale A1 et de la

surface des deux extrémités de ce cylindre.
•  La surface latérale du cylindre correspond à un rectangle (enroulé autour du
cylindre) dont la hauteur est h et la largeur est égale à la circonférence du cercle de
rayon r.
•

A2 = A1 + 2πr²
=> A2 = 2πr x h + 2πr²
=> A2 = 2πr (h + r)

28
 Structure d’un algorithme
algorithme cylindre
Variables:
Déclarations des
A1,A2,A3,r,h: réel variables
Début :
Ecrire (‘saisir rayon’)
Lire (r ) Le corps de
Ecrire (‘saisir hauteur’) l’algorithme
Lire (h ) (Instructions)
A1Surface (r)
A2Circonférence ( r )
A3 2*A1+h*A2
Ecrire (“ la surface d’un cylindre est:”, A3)
Fin

Surface (r) Circonférence (r)

Constante: Sous problème 1 Constante: Sous problème 2
PI=3,14 PI=3,14
Variable: Variable:
r: réel r: réel
Début Début
Ecrire (la surface est: ‘, PI*r*r) Ecrire (la circonférence est: ‘, PI*2*r)
Fin Fin

29
 Fonctions
et
procédures
 Fonctions
Numérique et
procédures
 Fonctions et procédures

• Dès qu’on commence à écrire des

programmes importants, il devient difficile
d’avoir une vision globale sur son
fonctionnement et de traquer les erreurs.

32
• Solution ?

33
 Top down design technique:

Problème
Sous problème 1 Sous problème 2

Sous Sous Sous Sous Sous Sous

problème problème problème problème problème problème
1.1 1.2 1.3 2.1 2.2 2.3
34
Algorithme et sous algorithmes

35
 Top down design technique
• Cette décomposition permet:

– d'aborder le problème progressivement en créant

des niveaux de description de plus en plus
détaillés.
– de réutiliser la résolution de certains sous-
problèmes pour résoudre de nouveaux
problèmes.

36
 Algorithme et sous algorithmes

Définition: Un sous-algorithme est un bloc faisant

partie d’un algorithme.

• Étant donné qu’il s’agit d’un bloc à part entière,

il possède éventuellement un en-tête, une série
de traitements, et une gestion des résultats tout
comme l’algorithme qui le contient.
37
 Sous algorithme
Donnée d’entrée Définis dans un
(paramètres) programme principale

Déclaration
Séquences Appel
Sous programme d’instructions
(traitement )

Donnée de sortie
(paramètres)

38
Algorithme et sous algorithmes
En tête

Nom programme

Déclaration
Programme
Constantes
principale
Variables
(Appelant)
Sous programme

Corps du programme

Lecture/Ecriture
Affectation
Structures de contrôle
Appel du sous programme
39
Algorithme et sous algorithmes
En tête

Nom, paramètres (fictifs)

Déclaration
Constantes
Variables
Sous
Sous programme un sous-algorithme peut en
Programme appeler un autre.

Corps du programme

Lecture/Ecriture
Affectation
Structures de contrôle
Appel du sous programme 40
 L’appel des sous algorithmes
algorithme cercle
Variables:
r: réel
Début :
Lire (r) Surface (a)
2) exécution
Constante:
Surface (r) PI=3,14
Début
Circonférence (r) Ecrire (la surface est: ‘, PI*a*a)
Fin Fin

Circonférence (a)
Constante:
PI=3,14
Début
Ecrire (la circonférence est: ‘, PI*2*a)
La syntaxe des sous problèmes est donnée à titre
Fin
explicatif , on détaillera dans la suite du cours
l’écriture exacte d’un sous algorithme.
41
 L’appel des sous algorithmes
• Un sous algorithme est obligatoirement caractérisé par un
nom (un identifiant) unique.

• Lorsqu’un sous algorithme a été appelé par un autre

algorithme, son nom devient une nouvelle instruction a
exécuté.

• L’algorithme qui utilise un sous-programme est appelé

algorithme appelant.

• un algorithme peut être appelé dans le corps d'un autre

algorithme afin de résoudre un sous problème.

42
 Fonctions et procédures:
paramètres et arguments

• Un sous-algorithme peut être appelé plusieurs

fois avec différentes valeurs grâce à des
arguments. Ces derniers sont dits paramètres et
sont clairement déclarés, au besoin, dans l’entête
du sous-algorithme. . On distingue deux types de
paramètres: paramètres formels et effectifs

43
 Fonctions et procédures:
paramètres et arguments
Programme appelant Paramètres
effectifs
algorithme cercle
Variables:
Rayon: réel
Début :
Ecrire (‘saisir rayon’)
Lire (Rayon )
Paramètres
Surface (Rayon) formels
Circonférence (Rayon )
Fin
Circonférence (a)
Constante:
PI=3,14
Début
Ecrire (la circonférence est: ‘, PI*2*a)
Fin

44
 Fonctions et procédures:
paramètres et arguments

• Les paramètres dans l’en-tête d’un sous

programme sont les paramètres formels (fictifs)

• Les paramètres utilisés lors de l’appel d’un sous

programme par l’algorithme appelant sont les
paramètres effectifs (réels)

45
Fonctions et procédures: paramètres formels

• Les paramètres formels sont la définition du

nombre et du type de valeurs que devra recevoir
le sous-algorithme pour se mettre en route avec
succès. On déclare les paramètres formels
pendant la déclaration du sous-algorithme.

• Ces paramètres peuvent prendre toutes les

valeurs possibles mais ils sont abstraits (n'existent
pas réellement).
46
Fonctions et procédures: paramètres effectifs

• Les paramètres effectifs sont des valeurs réelles

(constantes ou variables) reçues par le sous-algorithme
au cours de l’exécution du bloc principal. Ce sont des
valeurs du bloc principal dont le sous-algorithme a
besoin pour exécuter avec des données réelles
l’enchaînement d’actions qu’il est chargé d’effectuer.

• Le nombre de paramètres effectifs doit être égal au

nombre de paramètres formels. L'ordre et le type des
paramètres doivent aussi correspondre.

47
 L’appel des sous algorithmes
algorithme cercle
Surface (a)
Variables: Constante:
r: réel Début
PI=3,14

Début : Ecrire (‘ la surface est: ‘, PI*a*a)

Fin
Lire (r)
Surface (r)
Circonférence (r)
Fin

48
 Types de sous-algorithme
• En algorithmique il existe deux types de sous-
programmes :
– Les fonctions,
– Les procédures.

49
 Procédure
Une procédure est introduite par un en-tête, appelé
aussi signature ou prototype, qui spécifie :
– le nom de la procédure,
– les paramètres donnés et leur type,
 La liste des paramètres peut contenir (optionnel)
le mode de passage de chaque paramètre (E, S, E/S).

La procédure ne retourne aucun résultat

50
 Procédure

• La syntaxe retenue pour l’en-tête est la suivante :

procédure nom_procédure (paramètre1: type1, paramètre: type 2,…)

• La liste des paramètres précise, pour chaque

paramètre, son nom, son type.

51
 Procédure
Procèdure nomProcédure (paramètre1: type1, paramètre:
type 2,…)
Variable
Variable 1: type1
Variable 2 : type2
…..
Debut

Traitement voulu

Fin
52
 Programme appelant

algorithme cercle
Variables:
r: réel
Début :
Ecrire (‘saisir rayon’)
Lire (r ) Appel de la procédure
Surface (r) Paramètre effectif
Circonférence ( r )
Fin

Nom_procédure Paramètre formel

Procédure Circonférence (a:réel)

Constante:
PI=3,14
Début
Ecrire (‘’la circonférence est: ‘’, PI*2*a)
Fin

53
 Procédure rappelant une autre en
python
# donne le tableau de multiplication#

def tableau_de_multplication():
print("tableau de 7:")
for i in range(11):
p=7*i
print("7*",i,"=",p)

#Fonction qui donne trois fois le tableau de multiplication#

def triple_tableau_de_multplication():
for i in range(3):
tableau_de_multplication()

#Programme appelant#

triple_tableau_de_multplication()
54
 Procédure avec un seul paramètre en
python
def tableau_de_multplication(n):
""" donne le tableau de multiplication"""
print("tableau de",n,"est:")
for i in range(11):
p=n*i
print(n,"*",i,"=",p)

def triple_tableau_de_multplication(n):
for i in range(3):
tableau_de_multplication(n)

#Programme appelant#
triple_tableau_de_multplication(7)

55
 Procédure avec un seul paramètre en
python
def mult(m):
n=0
print("tableau de",m,":")
while n<11:
p=m*n
print(m,"*",n,"=",p)
n=n+1

#Programme appelant#
mult(3)
56
 Procédure:
Utilisation d’une variable comme
def tableau_de_multplication(n): argument
""" donne le tableau de multiplication"""
print("tableau de",n,"est:")
for i in range(11):
p=n*i
print(n,"*",i,"=",p)

def triple_tableau_de_multplication(n):
for i in range(3):
tableau_de_multplication(n)

#Programme appelant#

a=int(input("donner le tableau de multiplication pour la valeur :"))

triple_tableau_de_multplication(a)
57
 Procédure avec plusieurs paramètres

def mult(n,m,s):

print("tableau de",m,"à partir de",n,"est :")

while n<s:
p=m*n
print(m,"*",n,"=",p)
n=n+1

#Programme appelant#
mult(3,5,12)
58
 Procédure avec plusieurs paramètres
def tableau_de_multplication(n,m):
""" donne le tableau de multiplication"""
print("tableau de",n,"est:")
for i in range(11):
p=n*i
if p%m==0:
print(n,"*",i,"=",p)
print("le rste de la division de",p,"par",m, "est nul")
else:
print(n,"*",i,"=",p)
print("le rste de la division de" ,p,"par",m, "n'est pas nul")

#Programme appelant#
tableau_de_multplication(3,2)
59
 DÉPARTEMENT MATH ET
INFORMATIQUE

Informatique II

Pr. SADIQ Mounir

2023-2024
 Fonctions
Numérique et
procédures
 3

Fonctions en python

def nomDeLaFonction(liste de paramètres):

...
bloc d'instructions
...
[resultat=…..] # […] c’est optionnel
[return resultat]
 4

Fonctions simple sans paramètres en python

#Fonction cube de 3
def cube_3():
return 3*3*3

#Programme appelant#
y=cube()
print(y)
 5

Fonctions avec un seul paramètre en python

#Fonction cube
def cube(x):
return x*x*x

#Programme appelant#
y=cube(3)
print(y)
 6

Fonctions rappelant une autre en python

def cube(x):
return x**3

def volumes_sphere(r):
return 4*3.14*cube(r)/3

# proggramme principal#
a=int(input("la valeur du rayon r est: "))
print("le volume de la sphere de rayon",a,"est:"
, volumes_sphere(a))
 7

Fonctions
Tableau de multiplication(return une liste)
def tableau_de_multplication(n): # n: parametre#
""" donne le tableau de multiplication"""
print("tableau de",n,"est:")
R=[]
for i in range(11):
p=n*i # p,n,i: variable locales#
R=R+[p]
return R

#programme principal#
a=int(input(" le tableau du valeur :"))# a:variable globale#
y=tableau_de_multplication(a) # a:argument de la fonction#
print(y)
print(y[3])
print(y[3:])
print(y[:3])
print(y[3:7])
 8

Procédure vis-à-vis fonction

 Une fonction est un sous-algorithme qui, à partir
de donnée(s), calcul et rend à l’algorithme Un et
Un seul résultat alors qu’en général, une
procédure est un sous-programme qui ne retourne
aucun résultat
paramètre :

• paramètre : lors de l'appel d’un sous algorithme, il

faut passer la valeur du paramètre effectif au paramètre
formel, pendant l'exécution de la procédure appelée, si
le paramètre formel est modifié, il ne faut pas
répercuter cette modification sur le paramètre
effectif.
paramètre (exemple en python)

#Fonction cube
def cube(x):
return x**3

#Programme appelant#
y=int(input("entrer une valeur :"))
print("le cube de",y,"est :",cube(y))
 11

Variables

• On peut manipuler 2 types de variables dans un

sous programme (procédure ou fonction) :
–des variables locales et
–des variables globales.
• •Elles se distinguent par leur portée (leur
"champ de définition " et leur "durée de vie").
 12

Variables
 13

La portée des variables locales et

globales

• Une variable définie au niveau du programme

principal est appelée variable globale.
 Sa portée est totale : tout sous-programme
du programme principal peut utiliser cette
variable
• Une variable définie au sein d’un sous
programme est appelée variable locale.
 La portée d’une variable locale est
uniquement le sous-programme qui la
déclare.
 14

La durée de vie des variables locales et

globales

• Une variable locale n'est connue qu'à l'intérieur du

sous programme ou elle a été définie.
 Elle est créée à l'appel du sous programme et
détruite à la fin de son exécution
• Une variable globale est connue par l'ensemble des
sous programme et le programme principale.
 Elle est définie durant toute l’application et peut
être utilisée et modifiée par les différents sous
programme du programme principale.
 15

Algorithme Variable_globale_locale
Variables:
a, x: entier

fonction F (b:entier)
Variables:
c: entier Portée de la
Début variable
locale b
c b+10 Portée de la
yc*x variable
locale c
Portée de la
variable
retourner (y) globale x

Fin
Début
x5
a5
aF(a)
Ecrire (‘x=‘, x)
Fin
 16

Algorithme Variable_globale_locale
Variables:
a, x: entier

fonction F (b:entier):entier
Variables:
y: entier Variable Variable
Début algorithme fonction
x b+10
yb*x a x b y
retourner (y) 5 3
Fin 5
Début
x3 15
a5 75
aF(a)
75
Ecrire (‘x=‘, x)
Fin

Affichage: x=15
 17

Algorithme Algorithme Algorithme

Variable_globale_locale Variable_globale_locale Variable_globale_locale
Variables: Variables: Variables:
a: entier a: entier a: entier
x: entier x: entier x: entier
fonction F1 fonction F1 fonction F1
(b:entier):entier (b:entier):entier (b:entier):entier
Variables: Variables: Variables:
x: entier x: entier x: entier
y:entier y:entier y:entier
début début début
x3 x3 x3
yb*x yb*x yb*x
retourner (y) retourner (y) retourner (y)
fin fin fin
Début Début Début
x5 x5 x5
a4 a4 a4
aF1(a) a F1(a) aF1(a)
Ecrire (‘x=‘, x) Ecrire (‘x=‘, x) Ecrire (‘a=‘, a)
Fin Fin Fin
Affichage: Affichage: Affichage:

x= 5 x=3 Erreur
 18

Variables locales et globales de même nom ??

Lorsqu'une variable locale et une variable globale portent le
même nom, la portée de la variable locale masque la portée
de la variable globale.

Dans le sous-programme la variable globale

devient inaccessible

Conseil: Il faut faire attention a ne pas cacher involontairement des variables

globales par des variables locales du même nom.
 19

Variable locale
• Une variable locale est une variable déclarée a
l’intérieur d’une fonction :
▫ Par défaut, elles sont visibles uniquement a
l’intérieur de la fonction dans laquelle elles sont
déclarées ;
▫ A la sortie de la fonction, les variables locales sont
détruites et leur valeur perdues.
 20

Variable globale

• Avantages:
si plusieurs fonctions d'un programme ont besoin du même
ensemble de variables. Ce serait alors trop encombrant de passer
toutes les variables comme paramètres d'une fonction à l'autre.

• Inconvénient:
• mémoire saturée
• Des sous programmes qui dépendent du programme principale

 Conseil: Il faut utiliser autant que possible des variables locales

plutôt que des variables globales. Ceci permet d'économiser la
mémoire et d'assurer l'indépendance de la procédure ou de la
fonction.
 21

Variables
• La manière de distinguer la déclaration des variables
locales et globales diffère selon le langage.

En général, les variables déclarées à l'intérieur d'une

fonction ou procédure sont considérées comme variables
locales.
En pseudo-code, on va adopter la règle suivante: les
variables déclarées à l'intérieur d'un sous algorithme
sont considérées comme variables locales et on déclarera
les variables globales dans le programme principale.
 22

python python

def f(b): def f(b):

x=b+10 x=b+10
y=b*x y=b*x
return y return y

#programme principal #programme principal

x=5 x=5
a=4 a=4
a=f(a) a=f(a)
print(x) print(x)

Affichage: Affichage:

x= 5 Erreur
 23

En python

Variables locales ne pourront en effet jamais interférer

avec celles que vous aurez vous-même définies par ailleurs
dans le programme principal
 Module : Algorithmique et Python
MIP/S2

Fonction en python
3. Fonction avec chaine de caractère en python :
Les chaînes de caractères constituent un type de donnée composite. Nous entendons par là une
entité bien définie qui est faite elle-même d’un ensemble d’entités plus petites, en
l’occurrence : les caractères.

Les chaînes de caractères font partie d’une catégorie d’objets Python que l’on appelle des
séquences. On peut effectuer sur les séquences tout un ensemble d’opérations. Vous en
connaissez déjà quelques unes, et nous allons en décrire quelques autres dans les paragraphes
suivants.

Ex : Exécuter les programmes suivants, et observez

a = ' 1\n 2\n 3\n "Soleil !" »'
print(a)

b="Qu'à t-il à me regarder ainsi ?"

print(b)

c='''C'est pratique aussi,

de cette manière là,
surtout quand c'est long. '''
print(c)

3.1. Premières fonctions

 ch=input(text) ouvre une fenêtre avec le texte text, et transforme toute saisie en
chaîne.
 len(ch) revoie le nombre de caractères de la chaîne ch.
 ch[ i ] renvoie le caractère d'indice i de la chaîne ch :

Remarques : Le premier indice est 0, donc le dernier indice est len(ch) - 1

Une chaîne n'est pas modifiable.
( Par exemple ch[3]='A' renverra une erreur.)

3.2. extraction, longueur :

Sous Python, les éléments d’une séquence sont toujours indicés (ou numérotés) de la même
manière, c’est-a-dire à partir de zéro. Pour extraire un caractère d’une chaine, on peut définir
la fonction suivante :
def extraction(CH,x):
return CH[x]
 Module : Algorithmique et Python
MIP/S2
A=input("donner une chaine de caractere : ")
B=int(input("extraire le caractere d'indice: "))
print("le caractere d'indice",B,"de la chaine",A," est :",extraction(A,B))
Si l’on désire déterminer le nombre de caractères présents dans une chaîne, on peut utiliser la
fonction suivante :
def nb_caractere(CH):
return len(CH)
B=input(" donner une chaine de caractere:")
print(" nombre de caractere dans cette chaine est:",nb_caractere(B))

3.3. Extraction de fragments de chaînes

Lorsqu’on travaille avec des chaînes et on souhaite extraire une petite chaîne d’une chaîne
plus longue. Python propose une technique que l’on appelle slicing(« découpage en tranches
»). Elle consiste à indiquer entre crochets les indices correspondant au début et à la fin de la «
tranche » que l’on souhaite extraire :
def extraction_fragment(ch,m,n):
return ch[m:n]
ch=input("doner une chaine de caractere:")
m=int(input("donner le premier indice de lintervalle à extraire:"))
n=int(input("donner le dexieme indice de lintervalle à extraire:"))
print(" la chaine devient :",extraction_fragment(ch,m,n))
3.4. Concaténation, répétition :
Les chaînes peuvent être concaténées avec l’opérateur + et répétées avec l’opérateur * :
Exemple : fonction de concaténation et de répétition :
def concatenation(ch1,ch2):
return "Bonjour "+"Pr. "+ch1+" "+ch2
def repetition():
print(concatenation(ch1,ch2)*3)
ch1=input("votre nom:")
ch2=input("votre prenom:")
repetition()
 Module : Algorithmique et Python
MIP/S2
3.5. Code ASCII
les caractères sont des chaînes particulières de longueur 1 et comme l’ordinateur ne manipule
que des nombres, une première abstraction est d’associer à chaque caractère un code
numérique.
Le code ASCII d’un caractère s’obtient alors avec la primitive ord() et réciproquement le
caractère de code ASCII donné s’obtient avec la primitive chr().
Exemple : fonction code ASCII d’un caractère
def code_ASCII(c):
return ord(c)
c=input("donner un caractere:")
print("le code ASCII de" ,c, "est:",code_ASCII(c))

3.6. Parcours d’une séquence : l’instruction for ... in ... :

Il arrive très souvent que l’on doive traiter l’intégralité d’une chaîne caractère par caractère,
du premier jusqu’au dernier, pour effectuer à partir de chacun d’eux une opération
quelconque. Nous appellerons cette opération un parcours. En nous limitant aux outils Python
que nous connaissons déjà, nous pouvons envisager d’encoder un tel parcours à l’aide d’une
boucle, articulée sur le couple d’instructions for ... in ... :

Exemple1 :Articulation d’une chaine de caractère :

def articulation(ch):

for i in range(len(ch)):

print( "le caractere d'indice" ,i,"est :",ch[i])

ch=input(" donner une chaine de caractere: ")

articulation(ch)

Exemple2 : Écrire une fonction qui prend en entrée une chaîne de caractères et un caractère, et

qui affiche en sortie le nombre d’occurrence de ce caractère

def f(ch,x):
 Module : Algorithmique et Python
MIP/S2
n=0

for i in ch:

if x==i:

n=n+1

return n

ch=input("donner une chaine de caractere:")

x=str(input("donner un caractere :"))

print("le nombre d’occurrence de ce caractère est :",f(ch,x))

Exemple3 : chercher un seul caractère et donner sa position :

1. une fonction « appartient » qui détermine si un caractère donné appartient à
une chaîne de caractères donnée. (La fonction renverra True ou False)
def appartient(ch,x):
for i in ch:
if x==i:
return "true"
return "false"
ch=input("donner une chaine de caractere:")
x=str(input("donner un caractere :"))
print("ce caractère existe dans la chaine :",appartient(ch,x))
2. Écrire une fonction positions renvoyant la liste éventuellement vide des
positions d’un caractère dans une chaîne. Par exemple positions ( "a", dans
"abracadabra") .
def appartient(ch,x):
for i in ch:
if x==i:
return "true"
return "false"
def position(ch,x):
R=[]
 Module : Algorithmique et Python
MIP/S2
for i in range(len(ch)):
if x==ch[i]:
[Link](i)
return R
ch=input("donner une chaine de caractere:")
x=str(input("donner un caractere :"))
print("ce caractère existe dans la chaine :",appartient(ch,x))
print("ce caractère se trouve dans les positions suivant :",position(ch,x))
Exemple 4 : À l’envers

1. Écrire un programme Python qui demande un mot à l’utilisateur puis qui l’écrit
à l’envers.
2. En utilisant la fonction précédente écrire une fonction palindrome pour savoir si
un mot est ou non un palindrome.
Exemple 5 :
On souhaite écrire une fonction anagramme(ch1,ch2)qui teste si le ch2 est un anagramme du
cht1.
Voici un exemple de structure que peu avoir votre programme :
 On va d’abord créer une fonction occurrences qui renverra un tableau contenant le
nombre d’occurrences de toutes lettres. Pour ce faire :
1. On convertit la chaîne en minuscule.
2. On crée un tableau constitué de 26 zéros correspondant aux
occurrences de chaque lettre.
3. On parcourt la chaîne et on met à jour le tableau, c’est à dire par
exemple quand on rencontre un t on rajoute +1 à l’endroit
correspondant à t dans le tableau.
On pourra par exemple écrire quelque chose comme :
for lettre in chaine:
if 97<=ord(lettre)<=122:
tab [ord(lettre)-97]+=1
Numérique Récursivité
 Notion de récursivité

• Lorsque la définition d'un objet fait appel à l'objet

lui même, on parle de définition récursive.

• On rencontre souvent cette notion de récursivité :

– Dans la vie de tous les jours
– En mathématiques
– En informatique

2
Dans la vie de tous les jours :

3
 En mathématiques

• les suites définies par récurrence.

• un puissant moyen de démonstration par
récurrence.

4
En informatique
Définition: On appelle récursive toute fonction ou procédure qui
s’appelle elle même.

Objectif: la récursivité consiste à prendre un problème et à le

résoudre en utilisant ses versions les plus simples.

Comment ?

5
Exemple : Calcul de la somme des N premiers naturels:
la fonction Addition (N)

Comment on peut résoudre ce problème d’une manière récursive?

5 étapes pour résoudre n’importe quel problème récursif

6
Conception d’une solution récursive

Objectif: la récursivité consiste à prendre un problème et à le

résoudre en utilisant ses versions les plus simples.

7
 Conception d’une solution récursive

• Etape 1: quel est l’entrée la plus simple possible pour la fonction, c’est-à-
dire le cas où la fonction peut nous donner une réponse explicite.
•
 exemple: le cas de la fonction Addition (N):
N=1  on a un seul entier qui vaut 1 donc:

Addition (1)1

cas de base

8
 Conception d’une solution récursive

• Etape 2: utiliser des exemples et visualiser les

entrées et les sorties de la fonction
N=3 N=4
N=2

N=1

1 1+2 1+2+3

1+2+3+4

9
 Conception d’une solution récursive
• Etape 3: essayer de trouver la relation entre les
exemples Est-ce
les qu’on
pluspeut
grands avec les exemples
relier Addition(4) avec Addition (3)
petits
Est-ce qu’on peut relier Addition(3) avec Addition (2)
Est-ce qu’on peut relier Addition(2) avec Addition (1)
N=1 N=2 N=3 N=4

1+2
1+2+3

1+2+3+4
10
 Conception d’une solution récursive

• Etape 4: généraliser le modèle

+
=
k

11
Addition (k) Addition (k-1)
 Conception d’une solution récursive
Etape 5: combiner le modèle récursif avec le cas de base
1 Si N=1

Addition (N) = N+Addition (N-1) Sinon

Algorithme récursif: La traduction exacte de la formule de récurrence

Fonction Addition (N : entier) : entier

Si (N = 1) Alors
Retourne (1)
Sinon
Retourne (N + Addition(N - 1))
Fin Si
Fin 12
 Simulation
Addition (5) Addition (4) Addition (3)

5+Addition (4) 4+Addition (3) 3+Addition (2)

5+10=15 4+6 =10 3+3=6

Addition (2)
Addition (1)

2+Addition (1) 1
2+ =3 13
Cas d’arrêt

Une fonction récursive doit toujours

comporter une condition de fin des
appels, pour ne pas avoir une exécution
infinie.

14
 La condition d’arrêt

Comme dans le cas d’une boucle, il faut un cas d’arrêt où l’on ne fait pas
d’appel récursif.

procédure récursive(paramètres)

si TEST_D’ARRET alors
instructions du point d’arrêt
sinon
instructions récursive(paramètres changés) // appel récursif

15
 La condition d’arrêt
Fonction Addition (N : entier) : entier
Début
Si (N = 1) Alors La condition d’arrêt
Retourne (1)
Sinon
Retourne (N + Addition(N - 1)) Appel récursif
Fin Si
Fin

une variable de contrôle : entier naturel qui doit :

- décroître strictement à chaque appel récursif ;
- sa valeur finale mène à des cas de base.

16
 Algorithme récursif
• Un algorithme est dit récursif quand sa mise en œuvre
utilise ce même algorithme.
 Savoir exprimer le problème de taille n en
fonction du même problème de taille inférieur.
• Pour être validé, cet algorithme doit impérativement
vérifier les 2 contraintes de terminaison :
 existence d’un ou plusieurs cas de base (condition d’arrêt)
où l’algorithme est directement effectif ;
 assurance qu’il n’y aura qu’un nombre fini d’appels
récursifs avant de déboucher sur un cas de base. Cette
assurance est fournie par une variable de contrôle
17
Comment fonctionne la récursivité ?
Lorsqu'une fonction s'appelle
elle-même, cela crée une
séquence d'appels récursifs,
et chaque nouvel appel crée
une nouvelle instance de la
fonction, généralement avec
des paramètres différents.
 l’exécution de chaque
fonction est imbriquée de
plus en plus profondément à
chaque appel.

18
 Comment fonctionne la récursivité ?
Addition (5) Addition (4) Addition (3)

5+Addition (4) 4+Addition (3) 3+Addition (2)

5+?=? 4+?=? 3+?=?

Addition (2)
Addition (1)
Comment la machine comprend et
gère ce concept d’imbrication
d'exécution de fonction ?
2+Addition (1) 1 Comment elle garde le bon ordre
d’exécution de tout ça ?
2+ ?= 19
 Comment fonctionne la récursivité?
Notion de pile d’exécution
Définition (Pile d’exécution)
La Pile d’exécution du programme en cours est un
emplacement mémoire destiner à mémoriser les
paramètres, les variables locales ainsi que
l’adresse de retour de chaque fonction en cours
d’exécution.

20
Comment fonctionne la récursivité ?Notion de
pile d’exécution

La pile: structure de donnée ordonnée mais qui

ne permet l’accès qu’à une seule donnée.
 elle sert à mémoriser des choses en attente
de traitement.
Elle fonctionne selon le principe LIFO (Last-In-
First-Out) : Dernier entré premier sorti.
Correspond à une pile d’assiettes

21
Comment fonctionne la récursivité ?Notion de
pile d’exécution

Le principe est d’utiliser une pile, dite pile

d’appel, sur laquelle on empile les calculs en
attente.

22
 Comment fonctionne la récursivité?
Notion de pile d’exécution

 Quand un programme appelle une fonction,

cette fonction va au-dessus de la pile d'appels.
 La fonction au top de la pile sera la première
à être exécutée.
 La dernière fonction appelée sera celle exécutée.

23
 Evolution d’un appel récursif
Fonction Addition (3) : entier
Début
Si (N = 1) Alors
6
Retourne (1)
Sinon
Retourne (3 + Addition(2))
Fin Si
3
Fin

Fonction Addition (2) : entier

Début
Si (N = 1) Alors
Retourne (1)
Sinon
Retourne (2 + Addition(1))
Fin Si
1
Fin

Fonction Addition (1) : entier

Début
Si (N = 1) Alors
Retourne (1)
Sinon
Retourne (N + Addition(N - 1))
Fin Si
Fin

24
Evolution d’un appel récursif
Fonction Addition (N : entier) : entier
Si (N <= 1) Alors
Retourne (1)
Sinon
Retourne (N + Addition(N - 1))
Fin Si
Fin

Dépilement: Phase de la
Empilement: Phase de

remontée
descente

Addition(1) = 1

Addition(2)
Addition(2)
= 2+ Addition(1)
= 2+ 1

Addition(3)
Addition(3)
= 3 + =Addition(2)
3+ 3

Addition(4)
Addition(4)
= 4 + =Addition(3)
4+ 6
25
Evolution d’un appel récursif
Fonction Addition (N : entier) : entier
Si (N <= 1) Alors
Retourne (1)
Sinon
Retourne (N + Addition(N - 1))
Fin Si
Fin

Addition (1) n 1 retourne 1

Addition (2) n 2 retourne 1+2=3

Addition (3) n 3 retourne 3+3=6

Addition (4) n 4 retourne 6+4=10

26
 Evolution d’un appel récursif
L’exécution d’un appel récursif passe par deux phases:

la phase de descente (empilement) et la phase de

remontée (dépilement).

 Dans la phase de descente, chaque appel récursif fait à

son tour un appel récursif.
 En arrivant à la condition d’arrêt, on commence la
phase de remontée qui se poursuit jusqu’à ce que
l’appel initial soit terminé, ce qui termine le processus
récursif.

27
 DÉPARTEMENT MATH ET
INFORMATIQUE

Informatique II

Pr. SADIQ Mounir

2023-2024
Numérique Récursivité
En mathématiques

3
 Evolution d’un appel récursif
Fonction Addition (N : entier) : entier
def Addition(N):
Si (N == 1) Alors:
if N == 1:
Retourne 1
return 1
Sinon
else:
Retourne N + Addition(N - 1)
return N+Addition(N-1)
Fin Si
Fin
print(Addition(4))
Pour N = 4, calculons Addition(4)
 Addition(4) = 4 + Addition(3) = 10

 Addition(3) = 3 + Addition(2) =6

 Addition(2) = 2 + Addition(1) =3

 Addition(1) =1

4
 Exercice

En utilisant la propriété : x n = [Link]−1 (lorsque n > 0) et x 0 = 1,

écrire :
une fonction qui calcule x n (où x et n sont des entiers),
en utilisant la récursion.

def puissance(x,n):
if n==0:
return 1
else:
return x*puissance(x,n-1)
 Type de récursivité

La récursivité terminale

La récursivité non terminale

6
Type de récursivité: récursivité terminale

On dit qu’une fonction est récursive terminale,

si aucun traitement n’est effectué à la
remontée d’un appel récursif sauf le retour
d’un résultat:

7
 Type de récursivité: récursivité
terminale
• Exemple: Algorithme reste de la division
A = Bq + r où (q, r) ∈ N2 et r < B

• Tant qu'il nous reste dans A une quantité

suffisante pour prendre B, on retranche B de A,
c'est-à-dire qu'on prend une fois de plus B de A.

• Lorsqu'on ne peut plus retrancher B de A (parce

que A < B) alors le reste de la division euclidienne
c'est A.
8
• Exemple: Algorithme reste de la division
A = Bq + r où (q, r) ∈ N2 et r < B

• Cas de base:
 Si A < B alors le reste de la division
euclidienne c'est A

9
 Type de récursivité: récursivité
terminale
• Exemple: Algorithme reste de la division
• A=13 et B=4
– A=A-B Reste =1

A=9 et B=4

A=5 et B=4

A=1 et B=4
Reste =1

10
 Type de récursivité: récursivité
terminale
• Définition récursive de la fonction reste par
des équations:
• (1) reste(A, B) = A quand A < B
• (2) reste(A,B) = reste(A − B, B) quand A ≥ B
Fonction Rest (A : entier, B: entier) : entier
Debut
Si (A<B) Alors
Retourne (A)
Sinon
Retourne (Rest (A-B), B)
Fin Si
Fin 11
 Type de récursivité: la récursivité terminale
Fonction Rest (A : entier, B: entier) : entier
Debut
Si (A<B) Alors
Retourne (A)
Sinon
Retourne (Rest (A-B), B)
Fin Si
Fin
calculons Rest(13,4)
 Rest(13,4)
def Rest(A,B):
 Rest(9,4) if A<B:
return A
 Rest(5,4) else:
return Rest(A-B,B)
 Rest(1,4) = 1
print(f(13,4))
12
 Type de récursivité: récursivité terminale

On dit qu’une fonction est récursive terminale, si aucun traitement

n’est effectué à la remontée d’un appel récursif sauf le retour d’un
résultat.

 la valeur retournée est directement la valeur obtenue par un appel

récursif, sans qu’il n’y ait aucune opération sur cette valeur.

 Il n’y a ainsi rien à retenir sur la pile Cette forme de récursivité

est bénéfique pour la gestion de l'espace mémoire de la fonction.

13
 Type de récursivité: la récursivité
non terminale
• Un module récursif est dit non terminal si le
résultat de l’appel récursif est utilisé pour
réaliser un traitement (en plus du retour du
module).

14
 Evolution d’un appel récursif
Fonction Addition (N : entier) : entier
def Addition(N):
Si (N == 1) Alors:
if N == 1:
Retourne 1
return 1
Sinon
else:
Retourne N + Addition(N - 1)
return N+Addition(N-1)
Fin Si
Fin
print(Addition(4))
Pour N = 4, calculons Addition(4)
 Addition(4) = 4 + Addition(3) = 10

 Addition(3) = 3 + Addition(2) =6

 Addition(2) = 2 + Addition(1) =3

 Addition(1) =1

15
la récursivité non terminale récursivité terminale
 Type de récursivité: la récursivité terminale

fonction Addition(N:entier, S:entier):entier

SI N=0 ALORS:

retourner S

retourner Addition (N-1,N+S)

calculons Addition (3,0)

 Addition(3,0)
def Addition(N,S):
 Addition (2,3) if N == 0:
return S
 Addition (1,5)
return Addition(N-1, N+S)
 Addition (0,6) = 6
print(Addition(3, 0))
17
 Avantages et inconvénients

Avantages:
• L’avantage principal de la récursivité est la
simplicité de programmation. Pour écrire un
programme récursif, il suffit de :
– trouver comment réduire le problème de taille n à
un ou plusieurs problèmes de taille plus petite;
– traduire simplement la relation trouvée;
– vérifier la terminaison de l’algorithme.
18
 Avantages et inconvénients
• Les inconvénients sont :

- la multiplication des mémoires allouées au

stockage des résultats en attente, qui peut devenir
rédhibitoire ;
- le nombre de calculs effectués, souvent bien plus
grand qu’en programmation itérative.

19
 Remarques
• A l’opposé de la récursion, l’itération utilise les
structures de contrôle répétitives comme
POUR, TANT QUE, REPETER JUSQU'À

20
Exemple : Calcul de la somme des N premiers naturels:

Algorithme itératif: Cette version est dite itérative car utilise une boucle pour
Exemple : Calcul de la somme des N premiers naturels:

Algorithme itératif: Cette version est dite itérative car utilise une boucle

Fonction Addition (N : entier) : entier

Var : S, i : entier
Pour N = 4, calculons Addition(4)
Debut S0
S 0 S1
Pour i  1 à N Faire S1+2
SS+i S1+2+3
S1+2+3+4
Fin Pour
Retourne (S) Résultat de la fonction: Addition(4)=10
Fin

22
Exemple : Calcul de la somme des N premiers naturels en python:

def f(n):
s=0
for i in range(1,n+1):
s=s+i
return s

print(f(4))
 DÉPARTEMENT MATH ET
INFORMATIQUE

Informatique II

Pr. SADIQ Mounir

2023-2024
Récursivité :
EXEMPLES
 Fonction puissance: récursive non
terminale
• Cas de base simple.

fonction puissance (n:entier,x:entier): entier

Début

Si (n=0)
retourne 1
Sinon
retourne puissance x*(n – 1,x)

Fin
3
 Fonction puissance:
• Cas de base multiples.

fonction puissance (n:entier,x:entier): entier

Début
Si (n=0)
retourne 1
Si (n=1)
retourne x
Sinon
retourne puissance x*(n – 1,x)

Fin
4
 Fonction puissance:
• Cas récursifs multiples.

la fonction puissance(x, n) peut être défini de

la manière suivante:
En supposant que l’on dispose d’une fonction
y = x n//2

5
 Fonction puissance:
• Cas récursifs multiples.

fonction puissance (n:entier,x:entier): entier

Début
Si (n=0):
retourne 1
FinSi
y=puissance(n//2,x)
Si n%2==0:
retourne y*y
Sinon :
retourne x*y*y
FinSi
Fin
6
 Fonction fibonacci: double récursion
la suite de Fibonacci, définie par :

fib(0) = 0 ;
fib(1) = 1 ;
fib (n) =
∀n ≥ 2 , fib(n) = fib(n − 1) + fib(n − 2) ;

C’est une définition récursive : chaque calcul de fib(n) génère 2 appels de fib(n) . Ce qui assure
la validité de cette définition est :
— la présence des cas de base qui ne générant pas d’appel récursif ;
— la certitude qu’il n’y aura qu’un nombre fini d’appels récursifs avant de
tomber sur un cas de base  certitude qui est fournie par la variable n, qui décroît strictement
à chaque appel, et donc finit par valoir 0 ou 1.
7
 Fonction fibonaccie: version
récursive
Version récursive

fonction fib (n:entier): entier

Algorithme récursif:
La traduction exacte de la formule
Début
de récurrence

Si (n<=1) La condition
fib(0) = 0 ; d’arrêt
fib(1) = 1 ; retourne (n)
fib (n) = ∀n ≥ 2 , fib(n) = fib(n − 1) + fib(n − 2) ; Sinon
retourne (fib (n-1)+ fib(n – 2))

Appel récursif
Fin

8
 Evolution de la pile d’appel pour fib(4)

fib(4) = fib (3) + fib (2)

= (fib (2) + fib (1)) + fib (2)
= ((fib (1) + fib (0)) + fib (1)) + fib(2)
= ((1 + fib(0)) + fib (1)) + fib(2)
= ((1 + 0) + fib (1)) + fib(2)
= (1 + fib(1)) + fib(2)
= (1 + 1) + fib(2)
= 2 + fib(2)
= 2 + (fib (1) + fib (0))
= 2 + (1 + fib(0))
= 2 + (1 + 0)
=2+1
=3

9
 Analyse de la fonction fibonacci
récursive
À la racine, vous calculez:
• fib (n) dépend de fib (n-1) et fib
(n-2)
• fib (n-1) dépend à nouveau de fib
(n-2) et de fib (n-3)
• fib (n-2) dépend à nouveau de fib
(n-3) et de fib (n-4)
 des appels récursifs qui gaspillent
beaucoup de données dans le
calcul car on refait beaucoup de
fois les mêmes calculs.

10
Fonction f91(n) : Récursion imbriquée

Fonction f91(n), définie par :

Pour tout entier naturel n <101:

f91(n)=91

11
Fonction f91(n) : Récursion imbriquée

fonction f91(n) (n:entier): entier

Début
Si (n>100):
retourne n-10
Sinon:
retourne f91(f91(n+11) )
FinSi
Fin
12
 Fonctions : Récursion mutuelle.
les fonctions a(n) et b(n) sont définie par :

n: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, . . .
a(n) : 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, . . .
b(n) : 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, . …

13
 Fonction : Récursion mutuelle.
def a(n):
if n==0:
return 1
else:
return n-b(a(n-1))

def b(n):
if n==0:
return 0
else:
return n-a(b(n-1))

14
Chaine de caractère Récursivité
 Opérations sur les chaine de caractères
en python
Soit une chaine de caractères,

Ecrire un algorithme récursif permettant de déterminer sa longueur

def long(ch):
if ch=="":
return 0
else: return 1+long(ch[1:])

print(long("sadiq"))
 Opérations sur les chaine de caractères
Un mot est un palindrome si on peut le lire dans les deux sans de gauche à droite et
de droite à gauche.
Exemple : KAYAK est un palindrome.

Ecrire une fonction récursive permettant de vérifier si un mot est palindrome.

def palindrome(ch):
if len(ch)==1 or len(ch)==0:
return True
if ch[0]==ch[-1]:
return palindrome(ch[1:len(ch)-1])
else:
return False
print(palindrome("amma"))
print(palindrome("kayak"))
Listes Récursivité
 Opérations sur les listes

Écrire une fonction récursive d'entête f(n) qui permet de convertir

un entier naturel n dans le système binaire. Et vise versa .
La suite binaire est stockée dans une liste

def f(L):
def f(n):
n=len(L)
if n==0:
if(n==0):
return [ ]
return(0)
else: return [n%2]+ f(n//2)
else:
return(L[0]*2**(n-1)+f(L[1:n]))
Les enregistrements et les
fichiers
Les enregistrements
 3

Introduction

• Une faculté organise les informations relatives à

ses étudiants dans une liste identique à la suivante:

N°Apogée Nom prenom Cin Filière

a – Donner la structure de données nécessaires pour les objets à utiliser.

b – Donner une déclaration algorithmique de ces objets.
b – Donner une déclaration en python de ces objets.
 4

Introduction

• Le type tableau nous a permis de définir une

structure composée de plusieurs éléments, cette
structure nous permettrait de réunir les
éléments de même type
 5

Introduction
•  La solution est d’utiliser 5 variables de type
tableau
Objet Type
N°apogée Tableau des entiers
Nom Tableau des chaines de
caractère
prenom Tableau des chaines de
caractère
Cin Tableau des chaines de
caractère
Filière Tableau des chaines de
caractère
 6

Introduction

• Si nous voulons établir une structure comportant

en même temps des informations de différents
type, nous devons créer un nouveau type
permettant de les regrouper.
Exemple: les informations concernant un étudiant

 nouvelle structure appelée enregistrement.

 7

Définition et déclaration
• Définition: Un enregistrement est un type de
données défini par l’utilisateur et qui permet de
regrouper dans une même structure des données
de différents types.
 Les variables de type structuré sont appelées enregistrements.
 8

Définition et déclaration

Déclaration:
il faut déclarer un nouveau type, fondé sur
d’autres types existants. Après l’avoir défini, on
peut alors utiliser ce type structuré comme tout
autre type normal en déclarant une ou plusieurs
variables de ce type.
 9

Définition et déclaration
Type structuré:

Etudiant

Nom prénom Filiere N°apogee

Variable d’enregistrement

E1: Etudiant
 10

Définition et déclaration
La déclaration des types structurés se fait, dans les
algorithmes, avant la déclaration des variables.
 11

Définition et déclaration

• Exemple :
Etudiant : enregistrement
code_apogee: entier
nom:chaine
prenom:chaine
CIN:chaine
Filiere: chaine
Fin enregistrement
 12

Définition et déclaration en python

Etudiant={
"code_apogee":0 ,
"nom":"" ,
"prenom":"",
"CIN":"",
"Filiere": "",
}
 13

Définition et déclaration
• Une fois qu’on a défini un type structuré, on
peut déclarer des variables enregistrements
exactement de la même façon que l’on déclare
des variables d’un type primitif.

Syntaxe Exemple :
Nom Var : Nom Enregistrement E1 : Etudiant
 14

Définition et déclaration en python

Etudiant={
"code_apogee":0 ,
"nom":"" ,
"prenom":"",
"CIN":"",
"Filiere": "",
}
e1=Etudiant
 15

Utilisation des enregistrements

Affectation
Consiste à affecter des valeurs aux différents
champs d’une variable enregistrement.

[Link]  valeur
 16

Utilisation des enregistrements en python

Affectation en python
Etudiant={
"code_apogee":0 ,
"nom":"" ,
"prenom":"",
"CIN":"",
"Filiere": "",
}
e1=Etudiant
e1["nom"]="SADIQ"
 17

Accès aux champs d’un enregistrement

• Les champs des enregistrements en
algorithmique sont accessibles à travers leur
nom, grâce à l’opérateur ’.’
Nom [Link] représente la valeur
mémorisée dans le champ de l’enregistrement,
Exemple:
pour accéder au nom de la variable E1, on utilise
l’expression : E1. nom
• Remarque : la lecture d’une telle expression se
fait de droit à gauche : le nom de l’étudiant E1.
 18

Accès aux champs d’un enregistrement

en python
Etudiant={
"code_apogee":0 ,
"nom":"" ,
"prenom":"",
"CIN":"",
"Filiere": "",
}
e1=Etudiant
e1["nom"]="SADIQ"
print(e1["nom"])
 19

Utilisation des enregistrements

Lecture
 Lire ([Link])

Écriture
 Ecrire ([Link])
 20

Accès aux champs d’un enregistrement

en python
Lecture
Etudiant={
"code_apogee":0 ,
"nom":"" ,
"prenom":"",
"CIN":"",
"Filiere": "",
}
e1=Etudiant
e1["nom"]=input("Entrer le nom de l'etudiant 1 :")
e1["code_apogee"]=int(input("Entrer le code apogee de
l'etudiant 1 :"))
 21

Accès aux champs d’un enregistrement

en python
Écriture
Etudiant={
"code_apogee":0 ,
"nom":"" ,
"prenom":"",
"CIN":"",
"Filiere": "",
}
e1=Etudiant
e1["nom"]=input("Entrer le nom de l'etudiant 1 :")
e1["code_apogee"]=int(input("Entrer le code apogee de l'etudiant 1 :"))
print ("le nom de l'etudiant 1 est : ", e1["nom"])
print ("le code apogee de l'etudiant 1 est : ", e1["nom"])
 22

Enregistrements en algorithmique :
Cas particuliers
1. Un champ de type structuré : Un type
structuré peut être utilisé comme type pour
des champs d’un autre type structuré.

• Exemple : Déclarer une structure Personne

qui contient les champs : nom , prenom
et Date de Naissance ( composée du
jour, mois, année ).
 23

Enregistrements en algorithmique : Cas

particuliers

• Une date correspond donc à une entité

du monde réel qu’on doit représenter
par un type enregistrement à 3 champs.

• Si on déclare le type date au préalable, on

peut l’utiliser dans la déclaration du type
personne pour le type de la date de naissance.
 24

Enregistrements en algorithmique : Cas

particuliers
IV-1 Un champ de type structuré :
 25

Enregistrements en python : Cas

particuliers
IV-1 Un champ de type structuré :

date={
"jour":0 ,
"mois":0,
"année":0,
}
Personne={
"nom":"" ,
« nationalité":"",
"date_Naissance":date,
}
 26

Enregistrements en algorithmique : Cas

particuliers
1. Un champ de type structuré :
Pour accéder à l’année de naissance d’une personne p1, il
faut utiliser deux fois l’opérateur ‘.’

 [Link]ée : l’année de la date de naissance de

la personne 1.
 27

Enregistrements en python : Cas

particuliers
IV-1 Un champ de type structuré :

date={
"jour":0 ,
"mois":0,
"année":0,
}
Personne={
"nom":"" ,
"nationalité":"",
"date_Naissance":date,
}
p1=Personne
p1["date_Naissance"]["année"]=input("Entrer l'année de naissance de la Personne 1 :")
print ("l'année de naissance de la Personne 1 :", p1["date_Naissance"]["année"])
 DÉPARTEMENT MATH ET
INFORMATIQUE

Informatique II

Pr. SADIQ Mounir

2023-2024
Les enregistrements et les
fichiers
Les enregistrements
 4

Enregistrements en algorithmique : Cas

particuliers
• Exercice :
1- Définir la structure fournisseur et la structure Produit tel
que:
– Un fournisseur est caractérisé par son code, sa
raison sociale et son numéro de téléphone.
– un produit est caractérisé par son code, son libellé, et
son prix. Aussi, Un produit est livré par un seul fournisseur.
2- Afficher ensuite, le numéro de téléphone du fournisseur
d’un produit p.(algo et python)
 5

algo_structure_exo
Fournisseur: enregistrement
Code: entier
Raison_sociale: chaine
Num_tel: chaine
Fin enregistrement

Produit: enregistrement
Code: entier
Libellé: chaine
prix: réel
F:Fournisseur
Fin enregistrement

Variable P:produit
Début
Ecrire ( « donner les infos du produit »)
Lire (p.F.Num_Tel);
Ecrire (p.F.Num_Tel);
Fin
 6

Fournisseur={
"Code": 0,
"Raison_sociale": "",
"Num_tel": "",
}
Produit={
"Code": 0,
"Libellé": "",
"prix": 0.0,
"F":Fournisseur,
}
p1=Produit
p1["F"]["Num_tel"]=input("Entrer le Num de tel de Fournisseur de Produit 1 :")
print ("le Num de tel de Fournisseur de Produit 1 :", p1["F"]["Num_tel"])
 7

def fournisseur():
fournisseur={}
fournisseur["code"] = int(input("Entrez le code fournisseur: "))
fournisseur["Raison_sociale"] = input("Entrez Raison_sociale : ")
fournisseur["Num_tel"] = int(input("Entrez Num_tel: "))
return fournisseur

def saisir_produit(p):
p["code"] = int(input("Entrez le code de produit : "))
p["Libellé"] = input("Entrez Libellé: ")
p["prix"] = int(input("Entrez prix: "))
p["fournisseur"]=fournisseur()

p1={}
saisir_produit(p1)
print(p1)
print ("le Num de tel de Fournisseur de Produit 1 :", p1["fournisseur"]["Num_tel"])
 8

Enregistrements en algorithmique : Cas

particuliers
2. Un champ de type tableau :

Il est possible aussi qu’un champ de type

structuré soit de type tableau.
 9

Enregistrements en algorithmique : Cas

particuliers
• Exercice :
• Un étudiant sera identifié par son numéro
d’étudiant(NE), son nom, son prénom, sa
date de naissance (qui sera décomposée
en jour,mois et année), un tableau contenant les
moyennes de 5 modules .
• Écrire un algorithme qui permet de définir les
structures de données nécessaires, lire des
informations d’un étudiant et afficher ces
informations
 10

Définition et déclaration
Type structuré:

Etudiant

Nom prénom NE Moy_modue

Date_naissance

jour Mois annee

 11
def tableau():
tab=[]
for i in range(5):
x=float( input(f"Entrez la moyenne de module {i+1}: "))
[Link](x)
return tab
def date_naissance():
etu={}
etu["jour"] = input("Entrez le jour : ")
etu["mois"] = input("Entrez le mois : ")
etu["année"] = input("Entrez le année : ")
return etu
def saisir_etu(e):
e["NE"] = int(input("Entrez le NE : "))
e["nom"] = input("Entrez nom: ")
e["prénom"] = input("Entrez prénom: ")
e["date naissance"]=date_naissance()
e["tableau_moy"]=tableau()
e1={}
saisir_etu(e1)
print(e1)
 12

Enregistrements en algorithmique : Cas

particuliers
3. Tableau de variables structurées :
• Il arrive souvent qu’on veut traiter non pas un seul
enregistrement mais plusieurs.
• Exemple :
• on veut traiter un groupe de personne. Donc, On va
créer un tableau qui regroupe toutes les personnes
du groupe. Il s’agit alors d’un tableau d’enregistr
ement en algorithmique.
Les colonnes sont appelées champs et les lignes
enregistrements.
 13

def tableau():
tab=[]
for i in range(5):
x=float( input(f"Entrez la moyenne de module {i+1}: "))
[Link](x)
return tab

def date_naissance():
etu={}
etu["jour"] = input("Entrez le jour : ")
etu["mois"] = input("Entrez le mois : ")
etu["année"] = input("Entrez le année : ")
return etu

def saisir_etu(n):
tabl=[]
for i in range(n):
e={}
e["NE"] = int(input("Entrez le NE : "))
e["nom"] = input("Entrez nom: ")
e["prénom"] = input("Entrez prénom: ")
e["date naissance"]=date_naissance()
e["tableau_moy"]=tableau()
[Link](e)
return tabl

n=int(input("donner le nombre etudiant"))

print(saisir_etu(n))
Chapitre 5

Manipulation des fichiers en python

Objectif du chapitre :
 Comprendre la notion de fichiers en informatique.
 Manipuler des fichiers en Python pour lire, écrire et modifier des
données.
 Stocker et récupérer des données structurées dans des fichiers.
.

Nous allons nous intéresser dans ce chapitre à l’écriture et à la lecture des

données contenues dans un fichier placé sur un support de mémoire de masse, à
partir d’un programme Python. Cela peut être très utile si vous souhaitez
sauvegarder des données générées par votre programme.
 1. Préliminaires sur la manipulation des fichiers :

1.1. Arbre des fichiers :

Sur un support de mémoire de masse, il y a deux types de structures : les fichiers et les
répertoires (encore appelés dossiers) :
 Un fichier est comme une feuille de papier sur laquelle vous écrivez et vous lisez des
données. Ces données peuvent être des chaînes de caractères, des données numériques,
des objets, etc... Naturellement, cette feuille peut être très longue si le fichier est
volumineux. Un fichier est caractérisé par son nom et par son extension : d’une façon
générale, il s’appelle :nom_fichier.extension.
Les extensions renseignent sur la nature du fichier et surtout sur le logiciel capable de
lire les données de ce fichier. Vous connaissez bien sûr un certain nombre
d’extensions : .doc (ou .docx) pour les fichiers Word, .jpg pour un fichier image ou
encore .py pour un fichier python.
 Un répertoire aussi appelé dossier permet de regrouper plusieurs fichiers : c’est donc
comme une grande pochette dans laquelle on dépose les fichiers. Un répertoire peut
aussi contenir d’autres répertoires qui contiennent eux-même des fichiers et encore
d’autres répertoires...
Lorsqu’un dossier A contient un dossier B : on dit que B est un dossier fils de A (on
dit aussi que c’est un sous-répertoire de A) et que A est le dossier parent de B.
Dans un support de mémoire de masse, il y a toujours un répertoire qui contient tous les autres
répertoires et les fichiers présents sur le disque : on l’appelle le répertoire racine (ou, plus
simplement, la racine)
Par exemple, dans le système d’exploitation Windows, ce
répertoire racine a pour nom C : ou D : ou encore E : , F : ,
etc... (par exemple, le répertoire racine d’une clé USB
insérée dans l’ordinateur va couramment s’appeler E : , F :
ou G : ).
Ainsi, l’organisation des dossiers et fichier sur une support
de mémoire de masse a l’allure d’ un arbre , Voici ce à quoi
ressemble un arbre des dossiers et fichier pour le systèmes
d’exploitation Windows :
  Tout part du répertoire racine. : C:\
 De chaque répertoire ( Users\, Windows\) sont issues des branches qui aboutissent à
des sous-répertoires ( Admin\ , hpastor\, Documents\ )ou à des fichiers ([Link]).
 Aucune branche ne part d’un fichier. C’est ce qu’on appelle une feuille de l’arbre.

1.2. Chemin relatif et chemin absolu :

 Le chemin absolu : Si vous voulez accéder à un fichier, vous pouvez indiquer

comment y arriver à partir du répertoire racine : vous indiquez alors la suite des
dossiers menant au fichier. C’est ce qu’on appelle le chemin absolu.
Par exemple, sous Windows, si vous voulez accéder à un fichier nommé [Link]
contenu dans le dossier essais, lui même présent dans le répertoire racine C : .
Le chemin absolu menant à ce fichier s’écrira : C :\essais\[Link]
 Le chemin relatif : Supposez par exemple que le logiciel avec lequel vous écrivez ou
lisez un fichier soit dans le répertoire essais : il y a toutes les chances que ce soit le
répertoire de travail courant
Imaginez que ce répertoire particulier contient, en plus du fichier [Link], un sous-
répertoire nommé documents, qui contient lui-même un fichier [Link]. Vous avez
donc affaire à une arborescence du style :
–C:
– essais
– [Link]
– documents
– [Link]
Si le fichier est déjà dans le répertoire de travail courant, le chemin relatif est
simplement le nom du fichier. S’il est dans un sous répertoire de ce rép. de trav.
courant , alors le chemin relatif s’écrit à partir du répertoire de travail courant (mais
sans écrire son nom !) et vous indiquez la suites des répertoires menant au fichier
cible.
Dans la convention Windows, qui utilise des " \", vous écrivez :
 Chemin relatif de [Link] : [Link]
 Chemin relatif de [Link] : \documents\[Link]
1.3. Comment connaître et changer le répertoire de travail courant ?

Il y a un moyen de connaître et de changer le répertoire de travail courant avec du code

Python. Le module os est fait pour cela (os =operating system c’est à dire système
d’exploitation).
Prenons un exemple : supposez que le répertoire de travail courant soit C :\Users\Mounir et
que vous avez créé un dossier nommé travail sur le Bureau de votre ordinateur, lui même
situé dans le dossier Mounir.
Vous pouvez écrire dans l’interpréteur ou dans votre fichier de programme les lignes
suivantes :

La fonction getcwd() (current work directory) du module os renvoie le chemin absolu du

répertoire de travail courant et la fonction chdir (nouveau_repertoire) (change directory)
change le répertoire de travail courant : il faut lui indiquer en paramètre le chemin absolu du
nouveau répertoire de travail courant que vous souhaitez, sous a forme d’une chaîne de
caractères (str), c’est à dire "C :/Users/Mounir/Desktop/travail" dans notre cas.

Remarque :
 Windows utilise des anti-slash " \" comme caractère séparateur. Si vous voulez utiliser
la fonction [Link], il faut absolument mettre des double anti-slash " \\" dans le
chemin absolu et donc bien écrire "C :\\Users\\Mounir\\Desktop\\travail", sinon
Python ne comprend pas et génère une erreur de syntaxe.
 Desktop est le nom du bureau dans le langage de la machine.
 2. Lire et écrire du texte dans un fichier :

Nous allons commencer par nous intéresser à l’écriture et à la lecture d’un fichier texte. Ce
type de fichier ne contient qu’une suite de caractères, regroupés dans une seule chaîne de
caractères qui représente tout le texte.
Pour étudier cela , vous allez commencer par créer un dossier test que vous allez placer sur le
Bureau.
2.1. Ouvrir un fichier :

Pour commencer à lire ou à écrire dans un fichier, il faut d’abord l’ouvrir : cela se fait avec la
fonction open. par exemple pour ouvrir en écriture un fichier appelé [Link] dans le
répertoire de travail courant, avec un encodage utf-8 :
Open("[Link]", "w", encoding = "utf-8")
La fonction open qui prend trois paramètres :

 Le premier paramètre est le chemin d’accès au fichier, relatif ou absolu, sous la

forme d’une chaine de caractères, avec le nom du fichier.
Par exemple :
"[Link]" (chemin relatif) ou "C:/Users/.../Desktop/test/[Link]"
(chemin absolu) va ouvrir le fichier [Link] situé dans le répertoire de
travail courant test. Bien entendu, vous pouvez mettre le nom et l’extension que
vous voulez.
 Le second paramètre de la fonction open est le mode d’ouverture du fichier. Il
s’agit de l’un des trois caractères : ’w’, ’r’ ou ’a’ :
o ’w’ (ou "w" c’est la même chose) indique que le fichier est ouvert en
écriture. Si le fichier n’existe pas, il est créé. S’il existe déjà, son
ancien contenu est effacé et vous aller pouvoir réécrire dans le fichier
comme s’il était neuf.
o ’r’ indique que le fichier est ouvert en lecture. Vous ne pourrez que
lire le contenu du fichier. Si celui ci n’existe pas, le programme
s’arrête et une erreur de type FileNotFoundError est générée.
o ’a’ indique que le fichier est ouvert en mode ajout (append). Si le
fichier n’existe pas, il est créé. S’il existe déjà son contenu n’est pas
effacé et les données que vous y écrivez sont ajoutées en fin de
fichier, à la suite de celles qui y sont déjà.
  Le troisième paramètre de open est donc le type de codage des caractères et, pour
ne pas avoir de soucis utiliser la table utf-8 qui est universelle.

2.2. Écrire dans un fichier :

Pour commencer, vous aller créer un fichier qui contient la chaîne de caractères : "ma
phrase". Voici l’exemple :
1. f = open( "[Link]","w", encoding = "utf-8")
2. ch =" ma phrase "
3. [Link](ch)
4. [Link]()

À la ligne 1 la fonction open crée un objet de la classe TextIOWrapper que nous récupérons
dans la variable f. À la ligne 3 nous utilisons la méthode write de f pour écrire la chaîne ch
dans le fichier. On finit le programme en fermant le fichier par la méthode close c’est à dire :
[Link]().
Vous pouvez aller voir dans le dossier test et vous constaterez que le fichier [Link] y a
bien été créé !

2.3. Lecture d’un fichier :

Nous allons maintenant lire le fichier que nous venons de créer. Pour cela, il faut commencer
par l’ouvrir en lecture grâce au paramètre "r", sans oublier d’indiquer à Python le type
d’encodage pour qu’il puisse s’y retrouver. Voici ce que cela donne :

1. f = open( "[Link]","r", encoding = "utf-8")

2. a =f .read()
3. print(a)
4. [Link]()

Nous avons utilisé ici la méthode read de l’objet f : cette méthode renvoie tout le contenu du
fichier sous la forme d’une seule chaîne de caractères que nous stockons dans a. Nous
demandons ensuite d’afficher a à l’aide de la fonction print.
lorsque vous lisez un fichier au moyen de la méthode read, il y a un curseur qui se déplace
dans le fichier et se positionne après le dernier caractère lu. Un nouvel appel de read démarre
la lecture à partir de cette position. Si la position du curseur est à la fin du fichier (plus aucun
caractère à lire), read renvoie une chaîne vide.
Voila un exemple :

1. f = open( "[Link]","r", encoding = "utf-8")

2. a =f .read()
3. print(a)
4. a =f .read()
5. print(a)
6. print("Fin du programme")
7. [Link]()

De même on peut ne lire que les N premiers caractères d’un fichier texte en passant N en
paramètre à read. Cela donne la syntaxe suivante :

1. f = open( "[Link]","r", encoding = "utf-8")

2. a =f .read(2)
3. print(a)
4. a =f .read(4)
5. print(a)
6. print("Fin du programme")
7. [Link]()

La première lecture renvoie les 2 premiers caractères. La seconde lecture renvoie les 4
caractère suivants (le curseur s’est déplacé).
2.4. Écrire plusieurs lignes de texte dans un fichier :
Ecrivons une seconde phrase dans le fichier [Link]. Afin de ne pas l’effacer, nous
allons l’ouvrir dans le mode ’a’ (append) et y écrire : " ma seconde phrase".
1. #Écriture d’une seconde phrase
2. f = open( "[Link]","a", encoding = "utf-8")
3. ch =" ma seconde phrase "
4. [Link](ch)
5. [Link]()
6.
7. #On ouvre maintenant le fichier en lecture
8. f = open( "[Link]","r", encoding = "utf-8")
9. a =f .read()
[Link](a)
[Link]()
Le résultat : Les deux phrases ont été collées bout à bout, sans espace et sans saut de ligne !
Quand vous écrivez des instructions write les unes à la suite des autres, Python va venir coller
les chaînes de caractères bout à bout dans le fichier. Une instruction read renverra toute la
chaîne obtenue sans aucune séparation, ni aucun saut de ligne.
Si vous voulez quand même des séparations ou des sauts de lignes, il faudra les insérer :
 Pour une séparation, vous tapez un espace " " en fin ou en début de chaîne ou encore
un caractère de tabulation "\t".
 Pour imposer un saut de ligne, il faut taper le caractère saut de ligne "\n" à la fin de la
chaîne. Ce caractère est interprété par Python comme un saut de ligne.
Voila un exemple :
1. #Écriture d’une seconde phrase
2. f = open( "[Link]","w", encoding = "utf-8")
3. ch =" ma phrase\nma seconde phrase\nFin programme "
4. [Link](ch)
5. [Link]()
6.
7. #On ouvre maintenant le fichier en lecture
8. f = open( "[Link]","r", encoding = "utf-8")
9. a =f .read()
[Link](a)
[Link]()
Le résultat :

2.5. La méthode readlines

Lorsque dans le fichier, les différentes lignes sont séparées par le caractère "\n", la méthode
readlines renvoie une liste constituée des chaînes de caractères qui composent chaque ligne.
1. f = open( "[Link]","r", encoding = "utf-8")
2. a =f .readlines()
3. print(a)
4. [Link]()
Le résultat :
 DÉPARTEMENT MATH ET
INFORMATIQUE

Informatique II

Pr. SADIQ Mounir

2023-2024
Fichiers
 3

Introduction

• Jusqu‟à présent, les informations utilisées dans

nos algorithmes provient de deux sources :
• 1- soit elles étaient inclues dans l‟algorithme lui-
même.
• 2- soit elles étaient saisit par l‟utilisateur

 Les fichiers peuvent être un support permanent des

données.
 4

Définition

• Les fichiers servent à stocker des informations de manière

permanente, entre deux exécutions d‟un programme.

• En effet, si les variables, qui sont des adresses

de mémoire vive, disparaissent à chaque fin d‟exécution,
les fichiers, eux sont stockés sur des périphériques à
mémoire de masse (disquette, disque dur, CD Rom…).
 5

Organisation des fichiers

• il existe deux catégories de fichiers :
 les fichiers binaires et fichiers textes
• Exemple:
Un fichier codé sous forme d‟enregistrements est appelé un
fichier texte.
Exemple: Un carnet d‟adresses

Le fichier est destiné à mémoriser les coordonnées d‟un certain

nombre de personnes (le nom, le prénom, le numéro de
téléphone et l‟email).
 une personne est stocké par ligne du fichier
(par enregistrement).
 quand on prendra une ligne, on sera sûr qu‟elle contient les
informations concernant une personne, et uniquement cela.
 6

Types d'accès aux fichiers

• Définition:
Le type d‟accès c‟est la manière dont la machine va pouvoir
aller rechercher les informations contenues dans le fichier.
• On distingue :
▫ 1- L‟accès séquentiel
▫ 2- L‟accès direct (ou aléatoire)
 7

Types d'accès aux fichiers

2- L‟accès direct (ou aléatoire)

• On peut accéder directement à l‟enregistrement
de son choix, en précisant le numéro de cet
enregistrement.

• Mais cela veut souvent dire une gestion

fastidieuse des déplacements dans le fichier.
 8

Types d'accès aux fichiers

• Tout fichier peut être utilisé avec l‟un ou l‟autre

des types d‟accès. Le choix du type d‟accès n‟est
pas un choix qui concerne le fichier lui-même,
mais uniquement la manière dont il va
être traité par la machine. C‟est donc dans le
programme, et seulement dans le programme,
que l‟on choisit le type d‟accès souhaité,
 9

Types d'accès aux fichiers

1- L‟accès séquentiel :
• Dans le cas d‟un fichier texte: lecture de fichier ligne par ligne
(enregistrement par enregistrement).

▫ Cela signifie qu‟on ne peut accéder qu‟à la donnée suivant

celle qu‟on vient de lire.

▫ On ne peut donc accéder à une information qu‟en ayant au

préalable examiné celle qui la précède.
 10

Utilisation des fichiers

1-Ouverture:
• Lors de l‟ouverture du fichier il faut préciser
pour quelle opération celui-ci sera utilisé:
Lecture, Ecriture ou Ajout.
• On indiquera aussi par un n° le buffer qui sera la
représentation du fichier en mémoire.
Syntaxe :
OUVRIR “NomFichier” sur numCanal : mode

Python :
fichier=open(" NomFichier ", "mode")
 11

Utilisation des fichiers

• Dans le cadre de ce cours, on se limitera au

type: fichier texte en accès séquentiel.
 12

Utilisation des fichiers

1-Ouverture:

– NomFichier : c‟est le nom du fichier sur le

disque dur.
– numCanal : numéro de canal
– mode : mode d‟ouverture. Il existe trois modes
d‟ouverture
LECTURE : la lecture (lire du fichier)
ECRITURE : l‟écriture (écrire au début du fichier)
AJOUT : l‟ajout (écrire à la fin du fichier)
 13

Utilisation des fichiers

1-Ouverture:
• Exemple :
▫ OUVRIR „[Link]‟ sur 4 :Lecture
▫ OUVRIR „[Link]‟ sur 4 : Ecriture
▫ OUVRIR „[Link]‟ sur 4 : Ajout

Python :
f=open(" [Link] ", " r")

f=open(" [Link] ", "w")

f=open(" [Link] ", " a")

 14

Utilisation des fichiers

1-Ouverture:
Remarques:
1- On peut donner le chemin du fichier.
2- Le N° de canal doit être unique: référence
 Ainsi, si plusieurs fichiers doivent être manipulés
par le même programme, choisissez des références
différentes.
3- Dans un fichier ouvert pour ajout, les
enregistrements seront stockés à la fin du fichier.
4- Dans un fichier ouvert pour Ecriture, les
enregistrements seront écrit au début du fichier.
 15

Utilisation des fichiers

2. Lecture d‟un fichier

Syntaxe :
LireFichier numCanal, nomVariable

Python :

a= [Link]()
 16

Utilisation des fichiers

2. Lecture d‟un fichier
Lire un fichier séquentiel de bout en bout suppose
de programmer une boucle
 L‟instruction LireFichier récupère dans la variable
spécifiée l‟enregistrement suivant dans le fichier,
• (“suivant”, par rapport au dernier enregistrement
lu)
 Si on veut stocker au fur et à mesure en mémoire
vive les informations lues dans le fichier, on a recours à
des tableaux.
 17

2. Lecture d’un fichier

Exemple:

Variables ch : chaine
Début

OUVRIR ‘[Link]’ sur 4 : Lecture

LireFichier 4, ch
Lecture (ch)
Fin
 18

2. Lecture d’un fichier

• EXEMPLE:

f=open("[Link]","w")
[Link]("bonjour\n"+"sadiq mounir\n")
[Link]()
f=open("[Link]","r")
a=[Link]()#line#lines
print(a)
a=[Link]()#line#lines
print(a)
[Link]()
 19

Utilisation des fichiers

3- Ecriture dans un fichier
Syntaxe :
EcrireFichier numCanal, nomVariable

• numCanal : numéro désignant le fichier

• nomVariable : nom de la variable contenant la
valeur à écrire dans le fichier.

Python :
ch="bonjour "
[Link](ch)
 20

Utilisation des fichiers

Exemple :
Variables ch : chaine
Début
OUVRIR ” [Link] ” sur 4 :ecriture
ch ” Bonjour “
EcrireFichier 4, ch
Fin
 21

Utilisation des fichiers

• EXEMPLE:

f=open("[Link]","w")
Ch1= "bonjour\n"
Ch2= "sadiq mounir\n"
[Link](Ch1 + Ch2)
[Link]()
f=open("[Link]","r")
a=[Link]()#line#lines
print(a)
a=[Link]()#line#lines
print(a)
[Link]()
 22

Utilisation des fichiers

4. Fermeture du fichier
• Une fois qu‟on en a terminé avec un fichier, il
ne faut pas oublier de fermer ce fichier.
• On libère le canal qu‟il occupait
Syntaxe :
Fermer ( numCanal )
Python :
[Link]()
 23

Exercice :

• On souhaite sauvegarder et gérer des noms dans un

fichier. Ecrire les algorithmes qui permettent de :

1- Ecrire une fonction saisir() en python qui permet de saisir

n Noms dans un fichier ([Link]).
2- Ecrire une fonction afficher() en python qui permet
d‟Afficher le contenu du fichier
 24

def saisir():
n=int(input("donner le nombre de noms à saisir :"))
f=open("[Link]","w")
for i in range(n):
x=input(f"donner le {i+1}nom :")
[Link](x+"\n")
[Link]()

def afficher():
saisir()
f=open("[Link]","r")
a=[Link]()
print(a)
[Link]()
 25

Algo_exercice
Variables:
nom: chaine
n: entier
Début
Lire (n)
Ouvrir „[Link]‟ sur 1: Ecriture // on peut utiliser aussi ajout
Pour i de 0 à n-1
Ecrire (« saisir nom »)
Lire (nom)
EcrireFichier 1,nom
Fin Pour
Fermer (1)
 26

Algo_exercice
Variables:
nom: chaine
Début
Ouvrir „ [Link]‟ sur 1: Lecture
Tant que non EOF(1)
lireFichier 1,nom
Lecture (nom)
FinTantque
Fermer (1)
 27

Algo_exercice
Variables:
Nom, ch: chaine
n: entier
Début
Lire (n)
Ouvrir „[Link]‟ sur 1: Lecture
Ouvrir „[Link]‟ sur 2: Ecritrure
Tant que non EOF(1)
LireFichier 1, nom
Si ch!=nom
EcrireFichier 2, nom
FinTantQue
Fermer (1)
Fermer (2)
Supprimer („[Link]‟)
Renommer („[Link]‟, „[Link]‟)
Fin
 DÉPARTEMENT MATH ET
INFORMATIQUE

Informatique II

Pr. SADIQ Mounir

2023-2024
Analyse des
algorithmes et
complexité
 3

Problématique
« Un bon algorithme est comme un
couteau tranchant, il fait exactement
ce que l’on attend de lui, avec un
minimum d’efforts. L’emploi d’un
mauvais algorithme pour résoudre un
problème revient à essayer de couper
un steak avec un tournevis : vous
finirez sans doute par obtenir un
résultat digeste, mais vous
accomplirez beaucoup plus d’efforts
que nécessaire, et le résultat aura peu
de chances d’être esthétiquement
satisfaisant»
Introduction à l’algorithmique. Dunod,
1994

 Savoir résoudre un problème est une chose,

le résoudre efficacement en est une autre!
 Objectif
 Imaginez qu’on a deux algorithmes A1 et A2,
les deux peuvent résoudre le même problème P.
Les deux nous donnent des résultats corrects.
Lequel d’entre eux nous allons exploiter ? Le
meilleur ? Comment peut-on mesurer
l’efficacité d’un algorithme ?

1- La correction: est ce que l’algorithme ne boucle

pas ou ne diverge pas, est ce qu’il produit au moins
un résultat et que le résultat de l'algorithme est
effectivement de la forme énoncée par la
spécification

2- L’efficacité: en combien de temps et avec quelles

ressources? Il est souhaitable que nos solutions ne
soient pas lentes, ne prennent pas de l’espace
mémoire considérable.
Objectif
Ce cours essaye de répondre aux
questions suivantes:

Votre algorithme est-il

correcte?
Votre algorithme est-il efficace?

La complexité intervient
alors pour étudier l’efficacité de
deux algorithmes correctes
répondant au même problème.
 6

Complexité temporelle et spatiale

• En Algorithmique, on peut évaluer l’efficacité
des algorithmes selon deux paramètres :

▫ Le premier c’est l’espace mémoire, ceci veut dire,

combien d’espace mémoire va être utilisé par
l’algorithme pour résoudre le problème. (spatiale)

▫ Le deuxième paramètre est la rapidité d’un

algorithme (le temps qu'il faut à l'algorithme pour
s'exécuter). (temporelle)
On s’intéresse dans ce cours, essentiellement, à l’efficacité en
terme de temps d’exécution.
 7

Complexité temporelle

Le temps d’exécution d’algorithme est la ressource

la plus significative qu’il faut quantifier
Complexité temporelle
 8

Le temps d’exécution (contraintes)

• Le temps d’exécution d’un algorithme dépend de plusieurs facteurs :

- Les données utilisées par le programme: quand la taille des

données augmente, le temps d’exécution augmente aussi.

- La machine utilisée (processeur, bus de la carte mère, vitesse et

capacité de la RAM) : même algorithme qui manipulent la même
taille des données, sera plus rapide sur une machine plus puissante. .

• La qualité du compilateur (langage utilisé): le temps d’exécution de

deux programmes avec la même taille de donnée et qui s’exécutent dans la
même machine, dépend de leurs implémentations . Exemple, une
implémentation en java sera moins rapide qu’une implémentation en
langage natif tel que le C.
 9

Le temps d’exécution (en algorithmique)

1- Faire abstraction de la puissance de calcul qui peut
varier d’un ordinateur à un autre et d’un
environnement d’exécution à un autre et on exprime le
temps d’exécution de manière la plus indépendante
possible des conditions pratiques d’exécution.

Ce temps d’exécution dépend donc, de donnée d’entrée

d’un programme.

 les performances de l’ordinateur qui exécute

l’algorithme n’a aucun impacte sur le calcul de la
complexité
 10

Le temps d’exécution (contraintes)

• On ne calcule pas le temps d’exécution avec les
unités de temps (seconde,…). Mais, on utilise des
unités de temps abstraites proportionnelles au
nombre d’opérations effectuées.

Temps d’exécution=nombre d’instruction

(opérations) exécutées lors de la manipulation
des données
 11

Le temps d’exécution (contraintes)

Temps d’exécution=nombre d’instruction

(opérations) exécutées lors de la manipulation
des données

Ce temps d’exécution dépend du nombre de

donnée d’entrée
 12

Calcul du temps d’exécution

• On ne calcule pas le temps d’exécution avec les unités de

temps. Mais, on utilise des unités de temps abstraites
proportionnelles au nombre d’opérations effectuées.

• Le temps d’exécution est exprimé donc, comme une

fonction de la taille des données n que l’algorithme doit
traiter F(n).

F(n)= nombre d’opérations effectuées

 13

Le temps d’exécution (en algorithmique)

• 2- donner l’importance à des données très
grandes parce que les petites valeurs ne sont pas
assez informatives, autrement dit, voir
l’évolution du nombre d’instruction exécutées
lorsqu’on tend n vers l’infinie.

•  Complexité asymptotique
 14

Le temps d’exécution (en algorithmique)

3- évaluer le temps d’exécution pour une donnée

d’entrée de difficulté maximum
 La complexité dans le pire cas
 15

X=5

5 4 12 18 13 6 7 84 78 15

Cas 1: L’élément X qu’on cherche figure dans le premier élément du

tableau Tab le meilleur cas

6 4 12 18 13 5 7 84 78 15

Cas 2: L’élément X se trouve au milieu du tableau  le moyen cas

15 4 12 18 13 6 7 84 78 5

Cas 3: L’élément X figure dans le dernier élément ou bien n’existe pas

dans le tableau  le pire cas
Une donnée d’entrée de difficulté maximum
 16

Le meilleur cas, le moyen cas et le pire cas

A) L’élément X qu’on cherche figure dans le premier élément du tableau Tab:

notre algorithme exécutera le corps de la boucle uniquement une fois seulement,
est ceci quel que soit la taille du table n
 Ce cas est appelé le meilleur cas : C’est le plus petit nombre d’opérations qu’aura à
exécuter l’algorithme sur un jeu de données de taille n.

B) L’élément X se trouve au milieu du tableau:

 Ce cas est appelé le moyen cas: C’est la moyenne des complexités de l’algorithme sur des jeux
de données de taille n

C) L’élément X figure dans le dernier élément ou bien n’existe pas dans le tableau:
notre algorithme exécutera le plus grand nombre d’opérations sur un jeu de données
de taille n.
 Ce cas est appelé le pire cas

 On s’intéresse, essentiellement, au pire cas c’est à dire le scenario durant lequel notre
algorithme recevra les données qui montreront ses pires performances.
 17

Complexité:
• Définition: La complexité d’un algorithme est
une mesure de sa performance asymptotique
dans le pire cas.
le pire cas : évaluer le temps d’exécution pour une donnée d’entrée
de difficulté maximum

Asymptotique: donner l’importance à des données très grandes

parce que les petites valeurs ne sont pas assez informatives,
autrement dit, voir l’évolution du nombre d’instruction exécutées
lorsqu’on tend n vers l’infinie.
 mathématiquement parlant, on cherche a trouvé la limite de la
fonction lorsque n tend vers l’infinie.
 18

Une droite asymptote à

une courbe est une droite
telle que, lorsque l'abscisse
ou l'ordonnée tend vers
Y=ax+b l'infini, la distance de la
courbe à la droite tend vers
0.

Lim (f(x)-Y)=0 Y est asymptote

x ∞

L'objectif n'est alors pas de connaître les variations intermédiaires mais de déterminer
le comportement stable, à l'infini du phénomène mesuré.
 19

Complexité (théorique)

 Quand on calcule la complexité d’un

algorithme, on ne calcule généralement pas sa
complexité exacte, mais son ordre de
grandeur. (une approximation du nombre
d’opération significatives qui doivent être
menées pour exécuter l’algorithme)
 20

Notations asymptotiques: grand-O

Notation de Landau Grand-O:
La relation « O » est une relation de domination d’une fonction par une
autre
 Soit n la taille des données à traiter, on dit qu’une fonction f(n) et en
O(h(n)) si :

h(n)

 f(n) est en O(h(n)) s’il existe un seuil à partir duquel la fonction f(.) est
toujours dominée par h(.), à une constante multiplicative fixée près.

Cette notation exprime la limite supérieure d’une fonction dans un

facteur constant Borne supérieure.
 21

Notations asymptotiques: grand-O

la fonction h(n) constitue une borne supérieure de f(n) à une constante

multiplicative K1 à partir d’une certaine valeur n1 de n
 22

Notations asymptotiques: grand-O

• h(n) domine la fonction f(n) dans ce cas on dit

que la complexité de f (n) est O(h(n)).

• cette notation donne une majoration du nombre

d’opérations exécutées afin d’évaluer la
performance d’un algorithme pour un n très
grand.
 23

Règles de calcul du temps d’exécution

• Chaque instruction basique consomme une unité de

temps (affectation d’une variable, lecture, écriture,
comparaison,…).
• Chaque itération d’une boucle rajoute le nombre
d’unités de temps consommés dans le corps de cette
boucle.
• Chaque appel de fonction/procédure rajoute le nombre
d’unités de temps consommées dans cette fonction.
 Pour avoir le nombre d’opération effectuées par
l’algorithme, on additionne le tout.
 24

F (n) de cet algorithme est:

3+2n2 ~ n2

(1) ordre de grandeur de la

(1) complexité de cet algorithme
(1)
est: n2

n2
(1)
Pour calculer la complexité en
tant qu’approximation de la
fonction du temps, on utilise: la
n2 notation asymptotique
(1) grand-O
 25

Comment calculer la complexité

asymptotique grand-O

- Lorsqu'on étudie la complexité d’un algorithme, on fait la somme des opérations

effectuées par l’algorithme, et on obtient une somme des termes qui dépend de n:

f1(n)+f2(n)+…..+fk(n)

- On s’intéresse à de grandes tailles qui tendent vers l’infini. Donc, seuls les termes
dominants de la formule de la complexité nous importent:

 On oublie les constantes multiplicatives (elles valent 1) f(n)=c*n2 =O(n2)

 On annule les constantes additives f(n)=c+ n2 =O(n2)
 On ne retient que les termes dominants f(n)=c1*n2 + c2*n=O(n2)+O(n)=O(n2)
 26

Comment calculer la complexité

asymptotique grand-O

Exemple, soit :g(n)= 4n3-5n2+2n-7

- On remplace les constantes multiplicatives par 1:
1n3-1n2+1n-7
- On annule les constantes additives : n3-n2+n-0
- On garde le terme de plus haut degré: n3
On a donc la complexité de g(n)= O( n3 )
 27

Propriétés
 P1: la complexité d’une instruction élémentaire
(opération de base): Une instruction dont le temps
d’exécution est indépendant de la taille n des données tel que:
 Opération arithmétique ou logique (+, *, /, -, et, ou, …)
 Opération d’affectation (x 10)
 Vérification d’une condition (x>10)
 Opération d’entrée/sortie ( Lire/Ecrire)

 la complexité d’une instruction élémentaire est O(1)

 28

Propriétés (suite)
 P2: pour une constante O(k)=O(1)

 P3: la multiplication par une constante:

 O (c*f(n))= O(f(n))
 Exemple: O(n2 / 8 )= O(n2)

 P4: L’addition O(f1)+O(f2)=Max {O(f1), O(f2)}

 P5: La multiplication O(f1)*O(f2)= O(f1*f2)

 29

Propriétés (suite)
• P6: la complexité d’une instruction conditionnelle
le temps d’exécution est déterminé aussi par la règle de la somme.

La complexité d’une instruction conditionnelle est: Max{(O(g(n)), O(f1(n)), O(f2(n))}

 30

n<5: vérification d’une

condition O(1)
Ecriture: affectation O(1)

i1 : affectation O(1)

+ *n
Ecriture:
affectation O(1)

La complexité est: Max{O(1),O(1), O(2n)}=O(2n)=O(n)

 31

Propriétés (suite)
• P7: la complexité d’une boucle
▫ On multiplie la complexité du corps de la boucle par le nombre
d’itérations. Exemple pour la boucle la complexité se calcule comme
suit:

i1 : affectation O(1)

+
Ecriture: affectation O(1)
+ *n
Lecture: affectation O(1)
+
Ecriture: affectation O(1)
Opération arithmétique O(1)

La complexité de la boucle est: O(5n)=O(n)

 32

Propriétés (suite)

O(5n)

Max {O(5n)), O(2n)}

La complexité est:
O(5n)=O(n)
O(2n)
 33

Récapitulation

Pour calculer la complexité d’un algorithme:

• On calcule la complexité de chaque partie de
l’algorithme.
• On combine ces complexités conformément aux
règles déjà vues.
• On effectue sur le résultat les simplifications
possibles déjà vues.
 34

Complexité (théorique)

On calcul pas exactement le temps d’exécution des

algorithmes mais on classifie ces algorithme selon des
fonctions courantes en complexité algorithmique

 35

Comment la notation grand-O peut classifier

les algorithmes?
La fonction f(n) de l’algorithme de la version 1 est f(n)=2*n2 pour n>=1  h(n)=n2

Selon la définition de Landau et pour c=2, f(n)=O (n2 )

La fonction f(n) de l’algorithme de la version 2 est f(n)=n2 + n pour n>=1

 n <= n2
 n2 +n <= n2 + n2 = 2*n2
 f(n) <= 2*n2
Selon la définition de Landau et pour c=2, f(n)=O (n2 )

La complexité de l’algorithme version 1 ~ la complexité de l’algorithme version 2

 36

Comment la notation grand-O peut

classifier les algorithmes?
• La complexité temporelle est définie en fonction de
la taille d’entrée n en utilisant la notation grand O

• Nous utilisons la notation grand O pour classer les

algorithmes en fonction de leur temps d’exécution
qui dépend de l’augmentation de la taille des
données n

• La fonction O est le taux de croissance dans le pire

cas en fonction de la taille d’entrée n
 37

La complexité de cet algorithme

est O(1)

O(1)
O(1)

O(1)

O(1)
Max {(O(1), O(1), O(1)}
=> O(1)

O(1)

Max{(O(1), O(1), O(1)}

O(1)
 38

La complexité de cet algorithme

est:
Max (O(1), O(1), O(20))=O(20)
 O(1)

O(1)

O(1)
O(1)
i n+1: O(1)
10 *O(2)=O(20)
O (1)
 39

La complexité de cet algorithme est:

Max (O(1),O(1), O(2n), O(2n), O(1)=
O(2n)=O(n)

O(1)
O(1)
O(1)
i 0 : O(1)
O(1) n* O(2)= O(2n)

O(1)
O(1)
O(1) n*O(1)=
Max= O(1)
O(1) O(2n)

O(1)
 40

matrice
La complexité de cet algorithme est:
Max( O(1), O(1), O(2 n2), O(2 n2))
O(2 n2 )=O(n2)

O(1)
O(1)
O(1)
i 0 : O(1) O(n*(2n+1))=
j0: O(1) O(2n2+n)=
O(2n)
O(1) O(2n2 )

O(1)
i 0 : O(1)
O(n*(2n+1))=
j0: O(1)
O(2 n2+n)=
Ecrire O(1) O(2n)
O(2n2 )