Algorithmique

et structure de données
Abir MHENNI
Dr. Ing. en Informatique
abirmhenni@[Link]
Filière : 1ère année Licence IOT
2023-2024 1
 2
Contenu
1. Introduction à l'algorithmique
2. Environnement algorithmique
3. Structures conditionnelles
4. Structures itératives
5. Sous programmes
6. Tableaux
7. Algorithmes de recherche (recherche par dichotomie)
8. Algorithmes de tri : par sélection, par insertion, à bulle, quick sort, etc.
9. Récursivité
10. Notion de pointeur
11. Enregistrements
12. Listes chainées
 Chapitre 5

Sous programmes

3
 4
Introduction
• Le but de l’utilisation de sous programmes :
▪ décomposition des problèmes en modules (sous problèmes de taille réduite) :
✓ Dans un programme plusieurs séquences d’instructions sont appelées
plusieurs fois et depuis divers points du programme. Il serait donc plus
intéressant d’isoler ces séquences dans un sous programme qui peut être
appelé depuis n’importe quel point du programme.
✓ L’approche modulaire réduit énormément le nombre d’instructions
redondantes (qui se répètent) moyennant l’ajout d’une séquence d’appel
pour le module à différents endroits du programme. D’où la réduction de
la taille du programme (code).
✓ La lisibilité qui facilite notablement la compréhension du programme
 5
Introduction
• Le but de l’utilisation de sous programmes :
▪ Réutilisation du sous-programme
• En résumé, le programme sera plus lisible et plus facile à maintenir (à modifier
éventuellement par la suite)
• Un sous-programme est portion de code analogue à un programme. Déclarée
dans un programme ou dans un sous-programme et dont la partie instruction
peut être exécutée plusieurs fois au cours du traitement du programme grâce à
des appels. On distingue deux formes de sous programmes :
✓ Les procédures
✓ Les fonctions.
 6
Les procédures
• Une procédure est un sous-programme qui effectue un traitement (suite
d’instructions)
• Deux types de procédures existent :
✓ Les procédures sans paramètre
✓ Les procédures avec paramètre
 7
Procédures sans paramètre
• Elles sont utilisées pour éviter d’avoir à réécrire plusieurs fois une même suite
d’instructions figurant plusieurs fois dans le programme.
• Déclaration
Procédure nom_procédure
Déclarations
Début
Suite d’instructions
Fin
• Appel (utilisation)
nom_procédure
 8
Procédures sans paramètre
• Exemple
Algorithme Principal
Var x, y : entier
Procédure Affiche
Var
Début Déclaration de la procédure
Ecrire (‘’Bonjour’’)
Fin
Début
Lire(x)
Lire(y)
Affiche Appel de la procédure
Ecrire(x,y)
Fin
 9
Procédures avec paramètre
• Exemple
Algorithme Principal
Var x, y : entier
Procédure Affiche(var x : entier)
Var
Début Déclaration de la procédure
Ecrire (‘’la valeur = ’’,x)
Fin
Début
Lire(x)
Lire(y)
Affiche(x) Appel de la procédure
Affiche(y)
Fin
 10
Procédures avec paramètres
• Exercice 1 :
• Ecrire une procédure permettant de permuter la valeur de deux variables u et v.
Algorithme Principal Début
Var x, y : entier Lire(x)
Procédure Permute(var u,v : entier) Lire(y)
Var z : entier Ecrire(x,y)
Début Permute(x,y)
z<- u Ecrire(x,y)
u<-v Fin
v<-z
Fin
 11
Paramètres formels
• Une déclaration de procédure peut comporter après le nom de la procédure une
liste de paramètres formels dont la syntaxe est la suivante.
Procédure nom_procédure(liste de paramètres formels)
• Exemple
Procédure Somme(a, b : entier, var c : entier)
Début
c<-a+b
Fin
 12
Paramètres effectifs
• Au cas où la déclaration d’une procédure comprend des paramètres formels,
chaque appel de cette procédure doit comporter des paramètres effectifs
compatibles dont la syntaxe est la suivante.
nom_procédure(liste de paramètres effectifs)
• Il faut que les deux listes de paramètres formels et effectifs aient le même
nombre de paramètres et que les paramètres formels et effectifs correspondants
soient compatibles.
 13
Paramètres effectifs
• Exemple
Algorithme Principal
Var t :réel
X, y : entier
Début
…
interdit parce que le nombre de paramètres formels
Permute(x,y,z) est différent du nombre de paramètres effectifs
…
interdit parce que les paramètres formels et effectifs
Permute(x,t)
ne sont pas compatibles
Fin
 14
Exemple
• Ecrire une procédure sans paramètres qui permet de lire deux nombres, calculer
la somme et le produit et affiche si ces derniers sont positifs ou négatifs. Tester la
procédure dans l’algorithme principal.
 15
Exemple
Algorithme Principal Sinon
Var Ecrire (" a et b sont de signes contraires ")
Procedure calcul FinSi
Var a, b, som, prod : reel ;
Fin
Debut
Début
Lire (a, b)
som = a + b
prod = a * b Calcul
Si prod ≥ 0 Alors Fin
Si som ≥ 0 Alors
Ecrire ("la et b sont positifs")
Sinon
Ecrire ("a et b sont négatifs")
FinSi;
 16
Variables locales et globales
• Variables globales : elles sont déclarées à l’extérieur des sous programmes
• Variables locales : elles sont déclarées à l’intérieur du sous programme
• Une même variable peut Algorithme Principal
apparaître localement dans Var x, y : entier Variables globales
deux sous programmes différents. Procédure Proc(z : entier)
Var T :réel Variables locales
Debut
…
Fin
Début
…
Fin
 17
Passage de paramètres par valeur 17

• Les paramètres effectifs sont lus à l’appel Algorithme passage_valeur

de la procédure puis leurs valeurs sont Var x : entier
affectées à des variables temporaires Procédure Incrémenter(y : entier)
locales à la procédure. Début
Ecrire(y)
• Le x reste intact=0 mais en même temps y<-y+1
on veut l’incrémenter. Donc on utilise Ecrire(y)
cette procédure. Fin
Début
x<-0
Ecrire(x)
Incrémenter(x)
Ecrire(x)
Fin
 18
Passage de paramètres par variable 18

• Les variables d’entrée de la procédure Algorithme passage_variable

(paramètres effectifs) sont liés aux Var x : entier
paramètres formels. Procédure Incrémenter(var y : entier)
Début
• Pendant l’exécution du corps de la
Ecrire(y)
procédure toute action sur les y<-y+1
paramètres formels s’exécutera sur les Ecrire(y)
paramètres effectifs correspondants. Par Fin
conséquent, à la sortie de la procédure, Début
les variables peuvent avoir leurs contenus x<-0
changés. Ecrire(x)
Incrémenter(x)
Ecrire(x)
Fin
 19
Résumé
• Le passage de paramètres par valeur est utilisé pour transmettre une valeur à la
procédure.
• Le passage de paramètres par variable est utilisé pour que la procédure puisse
modifier la valeur d’une variable du programme appelant.
 20
Les fonctions
• Une fonction est un sous programme qui renvoie une valeur d’un seul type.
• Ce type sera celui de la fonction.
• La valeur retournée par la fonction dépend en général des paramètres formels (et
des variables globales)
• Déclaration
Fonction nom_fonction(liste des paramètres formels) : type du résultat retourné
Var Déclarations des variable
Début
Corps fonction
Fin
 21
Les fonctions
• Exemple • Remarque
Fonction Max(x, y : entier) : entier • Le corps de la fonction doit contenir au
moins une instruction de retour de la
Début valeur de la fonction comme suit :
Si x >=y Alors nom_fonction <- expression
Max<-x • Expression doit être de même type que
Sinon la fonction
Max<-y
Finsi
Fin
 22
Les fonctions
• Appel de fonction : Un appel d’une fonction se fait dans une expression
Algorithme Maximum
Var
x1, x2, y1 : réel
Fonction Max(x, y : réel) :réel
Début Modifier cet algorithme
Si x<=y Alors pour calculer le
Max<-x maximum de 4 réels.
Sinon Max <-y
Finsi
Fin
Début
Lire(x1, x2)
y1<-Max(x1, x2)
Ecrire("le maximum est :",y1)
Fin
 23
Exemples
1. Ecrire une fonction qui permet de vérifier si un nombre entier A divise un
nombre entier B.
2. Ecrire une fonction qui permet de vérifier si un caractère donné est une voyelle
ou non (voyelles : 'a', 'e', 'i', 'o', 'u', 'y’)
3. Ecrire une fonction affichant tous les nombres inférieurs à 500 égaux à la
somme des cubes de leurs chiffres.
Exemple : 153 = 13 + 53 + 33 = 1 + 125 + 27
To be Continued …

24