UNIVERSITE ST.

CHARLES LWANGA DE SARH

Algorithmique I
L1, Génie Informatique

2018-2019

UE : ALG102

Par : Dedjinh NINO PAYANG

« La maîtrise de l‘algorithmique requiert deux qualités : avoir une certaine intuition et être
méthodique et rigoureux »
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

I. Introduction

Définition des termes

- Algorithmique = la science qui étudie les algorithmes, mot provenant du nom d‘un
mathématicien arabe du IXème siècle Muhamed El-Khawarizmi qui était membre d‘une
académie des sciences à Bagdad.
 Algorithme = Suite finie, séquentielle de règles que l‘on applique à un nombre fini de
données, permettant de résoudre des classes de problèmes semblables.
 Algorithme = enchaînement des actions nécessaires à l‘accomplissement d‘une tâche.
Exemple : Trouver son chemin
Extrait d‘un dialogue entre un touriste égaré et un autochtone.
– Pourriez-vous m‘indiquer le chemin de la gare, s‘il vous plait ?
– Oui bien sûr : vous allez tout droit jusqu‘au prochain carrefour, vous prenez a` gauche au
carrefour et ensuite la troisième rue à droite, et vous verrez la gare juste en face de vous.
– Merci.
Dans ce dialogue, la réponse de l‘autochtone est la description d‘une suite ordonnée
d‘instructions (allez tout droit, prenez a` gauche, prenez la troisième à droite) qui manipulent des
données (carrefour, rues) pour réaliser la tâche désirée (aller a` la gare). Ici encore, chacun a déjà
été confronté à ce genre de situation et donc, consciemment ou non, a déjà construit un
algorithme dans sa tête (ie. définir la suite d‘instructions pour réaliser une tâche). Mais quand on
définit un algorithme, celui-ci ne doit contenir que des instructions compréhensibles par celui qui
devra l‘exécuter (des humains dans l‘exemple précèdent).
Dans ce cours, nous devrons apprendre à définir des algorithmes pour qu‘ils soient
compréhensibles — et donc exécutables — par un ordinateur.
Exemple : Algorithme d’Euclide : permettant de calculer le PGCD de deux nombre A et B
A et B deux nombres

Diviser A par B Remplacer B par C

Mettre le reste en C Remplacer A par B

NON
C=0 ?

OUI

Afficher B

1
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

NB : Pour un problème donné, plusieurs algorithmes ou aucun sont possibles.

Un algorithme se termine en un temps fini.
Un algorithme ne dépend pas du langage dans lequel il est implanté, ni de la machine qui
exécutera le programme correspondant.
Validité d’un algorithme :
La validité d‘un algorithme est son aptitude à réaliser exactement la tâche pour laquelle il a été
conçu. Si l‘on reprend l‘exemple de l‘algorithme de recherche du chemin de la gare, l‘étude de
sa validité consiste à s‘assurer qu‘on arrive effectivement à la gare en exécutant scrupuleusement
les instructions dans l‘ordre annonce.
La robustesse d’un algorithme : est son aptitude à se protéger de conditions anormales
d‘utilisation.
Dans l‘exemple précèdent, la question de la robustesse de l‘algorithme se pose par exemple si le
chemin proposé a été pensé pour un piéton, alors que le « touriste ´égaré » est en voiture et que la
« troisième a` droite » est en sens interdit.
La réutilisabilité d’un algorithme : est son aptitude à être réutilisé pour résoudre des tâches
équivalentes à celle pour laquelle il a été conçu.
L‘algorithmique permet ainsi de passer d‘un problème à résoudre à un algorithme qui décrit la
démarche de résolution du problème. La programmation a alors pour rôle de traduire cet
algorithme dans un langage « compréhensible » par l‘ordinateur afin qu‘il puisse exécuter
l‘algorithme automatiquement.
Notion d’Instructions
Fondamentalement, les ordinateurs, quels qu‘ils soient, ne comprennent que quatre catégories d'ordres
(d'instructions). Ces quatre familles d'instructions sont :
„ l‘affectation de variables
„ la lecture / écriture
„ les tests
„ les boucles
Un algorithme informatique se ramène donc toujours à la combinaison de ces quatre petites briques
de base. Il peut y en avoir quelques-unes, quelques dizaines, et jusqu‘à plusieurs centaines de milliers.

Tout traitement demandé à la machine, est fait par l‘exécution séquencée d‘opérations appelées
instructions.
Une instruction est donc une suite finie d'actions ou d‘opérations exécutables à entreprendre en
respectant une chronologie imposée.

2
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

Exemple d’une recette de cuisine : Problème

Préparation d’une Sauce viande pour 2 personnes :
Ingrédients :
4 tomates fraiches
2 oignons
2 pommes Des données
Un verre d’huile
½ kg de viande
125 g d’épices
Du sel
Préparation :
Peler, évider et découper les tomates, l’oignon, les pommes et la viande.
Mettre la marmite au feu
Mettre de l’huile, le laisser chauffer et mettre l’oignon Instructions
Mettre la tomate, faire tourner
Puis mettre la viande et du sel…
Ajouter les condiments, laisser cuire encore pendant 10min

Plat servit
Résultat
Chaque microprocesseur a son jeu d‘instructions de base dont le nombre varie selon le type
d‘architecture du processeur. On peut classer ces instructions de base en 5 grands groupes : les
opérations arithmétiques (+, -, *, /. . .), les opérations logiques (not, and, or. . .), les instructions de
transferts de données (load, store, move. . .), les instructions de contrôle du flux d‘instructions
(branchements impératifs et conditionnels, boucles, appels de procédure. . .), et les instructions d‘entrée-
sortie (read, write. . .).
Le traitement de ces instructions par le microprocesseur passe ensuite par 5 étapes :
 fetch : chargement depuis la mémoire de la prochaine instruction a exécuté,
 décode : décodage de l‘instruction,
 load operand : chargement des données nécessaires a l‘instruction,
 execute : exécution de l‘instruction,
 result write back : mise a` jour du résultat dans un registre ou en mémoire

Une suite d‘instructions écrit dans un langage compréhensible par un ordinateur est appelée un
programme.

Programmation
Un algorithme exprime la structure logique d‘un programme informatique et de ce fait est indépendant du
langage de programmation utilisé. Par contre, la traduction de l‘algorithme dans un langage particulier
dépend du langage choisi et sa mise en œuvre dépend ´également de la plateforme d‘exécution.
La programmation d‘un ordinateur consiste à lui « expliquer » en détail ce qu‘il doit faire, en sachant
qu‘il ne « comprend » pas le langage humain, mais qu‘il peut seulement effectuer un traitement
automatique sur des séquences de 0 et de 1. Un programme n‘est rien d‘autre qu‘une suite d‘instructions,
encodées en respectant de manière très stricte un ensemble de conventions fixées à` l‘avance par un
langage informatique. La machine décode alors ces instructions en associant à chaque « mot » du langage
informatique une action précise. Le programme que nous écrivons dans le langage informatique a` l‘aide
d‘un éditeur (une sorte de traitement de texte spécialisé) est appelé programme source (ou code source).

II. Structure d’un algorithme

Algorithme =Procédure décrivant, étape par étape, une méthode permettant de résoudre un problème.

3
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

• Chaque étape est décrite de façon précise;

• Chaque étape est déterministe: produit des résultats uniques;
• L‘algorithme s‘arrête après un nombre fini d‘instructions
• Reçoit des données en entrée;
• Produit des données en sortie;

ETAPES D’UN ALGORITHME

Préparation du traitement
- données nécessaires à la résolution du problème

Traitement
- résolution pas à pas,
- après décomposition en sous-problèmes si nécessaire

Edition des résultats

- impression à l‘écran,
- dans un fichier, etc.

LANGAGE ALGORITHMIQUE (Le Pseudo-code)

Pseudo-Code: c‘est une notation très simple et compréhensible pour l‘homme mais pas par la machine,
sa structure est toutefois proche du code des langages de programmation (C, Pascal). Notation standard
mais pas rigoureuse.
Un programme algorithmique débute par le mot-clé Algorithme suivi du nom du programme. Ce nom ne
doit plus être réutilisé dans la suite du programme.

Syntaxe :
Algorithme NomAlgorithme
{Ceci est un commentaire}
Début
... Instructions (actions) ;
Fin
Exemple :
Algorithme VotreNom
{il demande à l‘utilisateur de saisir son nom }
Variable nom : chaine de caractère
Début
Ecrire (―Bonjour comment vous vous appelez ? ! ") ;
Lire (nom) ;
Fin

Règle :
• Il faut avoir une écriture rigoureuse
• Il faut avoir une écriture soignée : respecter l’indentation
• Il est nécessaire de commenter les algorithmes
• Il existe plusieurs solutions algorithmiques à un problème posé

4
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

• Il faut rechercher l‘efficacité de ce que l‘on écrit

1
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

III. Variables et données

En mathématiques, une « variable » est généralement une inconnue, qui recouvre un nombre
non précis de valeurs.
En informatique, une variable possède à un moment donné une valeur et une seule.
Une variable peut être vue comme une case en mémoire vive, que le programme va repérer
par une étiquette (une adresse ou un nom). Pour avoir accès au contenu de la case (la valeur
de la variable), il suffit de la designer par son étiquette : c‘est-a-dire soit par son adresse en
mémoire, soit par son nom.
Un programme a besoin de stocker provisoirement des valeurs (information). Ces valeurs
peuvent être de plusieurs types : elles peuvent être des nombres, du texte, etc.
Toujours est-il que dès que l‘on a besoin de stocker une information dans un programme, on
utilise une variable.

Une donnée est donc = valeur stockée dans une variable.

a. Déclaration et utilisation des variables

Les variables utilisées dans le programme principal doivent être déclarées auparavant. La
déclaration des constantes est initiée par le mot-clé const. La déclaration des variables est
initiée par le mot-clé variable. Le type de chaque variable doit être précisé lors de la
déclaration. Les constantes ne sont pas typées
En pseudo code la syntaxe est la suivante : Variable « nomVariable » : type
Exemple : Variable nombrePair : Entier

Les noms de variables sont des identificateurs arbitraires, de préférence assez courts
mais aussi explicites que possible, de manière à exprimer clairement ce que la variable est
censée référencer (la sémantique de la donnée référencée par la variable). Les noms des
variables doivent en outre obéir à quelques règles simples :
– Un nom de variable est une séquence de lettres (a. . .z , A. . .Z) et de chiffres (0. . .9), qui
doit toujours commencer par une lettre.

Seules les lettres ordinaires sont autorisées. Les lettres accentuées, les cédilles, les espaces, les
caractères spéciaux tels que $, #, @, etc. sont interdits.
En algorithmique tout comme en pascal on ne tient pas compte de la casse (majuscules /
minuscules). Ce n'est pas le cas dans la plupart des autres langages de programmation.

- Une fois nommée, il est souvent nécessaire de modifier la valeur de la donnée référencée
par une variable. C‘est le rôle de l‘instruction d‘affectation.
- L‘affectation est l‘opération (instruction) qui consiste à attribuer une valeur à une variable.
Syntaxe (en pseudo-code) : NomVariable valeur ;
(L‘opérateur d‘affectation utilisé ici est une flèche)
Exemple : Variable a : Entier ;
a 100 ; {cela signifie que la valeur 100 est rangé dans la variable a}

2
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

b. Types de variables
Un type définit les valeurs que peut prendre une donnée (en particulier une variable).
Les différents types de variables sont :
- Type Entier
- Type réel
- Type Booléen : prends deux valeurs (vraies ou fausses)
- Type caractère noté « car » et chaine de caractère notée « chaine »
- Type constante : une variable dont la valeur associée ne varie pas au cours du programme
Opérateurs de calcul disponibles pour les types de base :
- Entiers : + ; – ; * ; div ; mod (c‘est le reste de la division)
- Reels: +; –; *; /
- Booléens: and ; or ; not
Opérateurs de comparaison (le résultat est un booléen) :
strictement plus grand que… >
plus petit ou égal à… <=
plus grand ou égal à… >=
égal à… =

différent de… <>

strictement plus petit que… <

IV. Fonctions d’entrée-sortie

Sont appelées fonctions d‘entrée/sortie, les fonctions qui permettent d‘introduire des données à
l‘ordinateur et d‘afficher des informations à l‘écran.
a. Fonction de lecture :
La fonction de lecture est la fonction qui nous permet d‘introduire des informations à l‘aide du
clavier, elle interrompt l‘exécution du code jusqu‘à ce que l‘utilisateur saisisse l‘information
demandée.
En pseudo-code nous utiliseront la syntaxe suivante : Lire (nomVariable) ;
Exemple : Variable nom : caractère ;// déclaration de la variable nom de type caractère
Lire (nom) ; // on demande à l‘utilisateur de saisir son nom.

a. Fonction d’écriture
La fonction d‘écriture est la fonction qui nous permet d‘afficher à l‘écran le résultat du
programme ou une information pour guider l‘utilisateur

En pseudo-code nous utiliseront la syntaxe suivante : Ecrire (" texte à afficher") ;

Exemple : Variable nom : chaine // déclaration de la variable nom de type chaine de caractère

Ecrire(" Entrez votre nom :") //l‘information entre griffes s‘affiche à l‘écran
Lire (nom) // on demande à l‘utilisateur de saisir son nom.

3
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

Exercice : Quel résultat produit le programme suivant ?

Variables val, double : reel

Début
val 231
double Val * 2
Ecrire (val)
Ecrire (double)
Fin

V. Types objet
Un objet en informatique est un ensemble d‘élément de type basique rattaché les uns autres.
a. Chaine de caractères
Une chaîne de caractères est une application s : S → car où S est une séquence finie d‘entiers
positifs {0, . . . , n} et caractère est l‘ensemble des 256 caractères du code ascii.
Une chaîne se décrit en extension en écrivant le mot avec des guillemets : s = ―a1 . . . an‖.
La notation s[i] pour i = 0, . . ., (n − 1) dénote la lettre à la position i + 1 dans la chaîne s.
Pour déclarer une variable de type chaine de caractère nous utiliserons la syntaxe suivante :
Variable « nomVariable » : chaine ;
Exemple : variable nom : chaine ;
nom "Mamadou" ;
nom[1] = ‗a‘

la longueur de la chaine est donnée par une fonction predefnie, en pseudo-code nous utiliserons la
syntaxe suivante : Longueur (nomVariable) :
exemple : Longueur (nom) = 7

b. Dates
La construction de types Objet peut être faite en combinant tous les types de base et les types déjà
définis.

Objet date (
Entier jour
Entier mois
Entier année
)
L‘utilisation se fait en utilisant le point ―.‖

objet date t1,t2

[Link] = 10
[Link] = 5
[Link] = 2008
...
t2 = t1 (copie de toute la structure = 3 variables)

4
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

VI. Structures de contrôle

Un programme n'est jamais une suite linéaire d'ordres. On doit pouvoir faire des choix : le
programme devient conditionnel.

Si un traitement identique (ou presque identique) se répète plusieurs fois, on doit pouvoir faire en
sorte de ne l'écrire qu'une fois : le programme devient itératif
Les choix et les boucles itératives sont les deux types majeurs de structures de contrôle d'un
algorithme.
Une condition est une comparaison entre deux valeurs de même type. Elle signifie qu‘une
condition est composée de trois éléments :

 „- une valeur
 „ - un opérateur de comparaison
 „ - une autre valeur
Certains problèmes exigent parfois de formuler des conditions qui ne peuvent pas être exprimées
sous la forme simple.
L‘informatique met à notre disposition quatre opérateurs logiques : ET, OU, NON, et XOR.
Exemple : « X est compris entre 5 et 8 ».
En fait cette phrase cache non une, mais deux conditions.
Car elle revient à dire que
( X est supérieur à 5) ET (X est inférieur à 8 )
Il y a donc bien là deux conditions, reliées par un opérateur logique « ET »

a. Instructions conditionnelles
Exprimer un choix, c'est décider d'exécuter ça... ou ça. La machine doit pouvoir décider lequel des
"ça" elle exécute. Elle va donc analyser une condition, puis prendre une décision.
Conditionnalité
Le cas le plus simple du choix est la « condition »
SI (condition) ALORS
... Instructions
FIN SI
Si booléen Alors
…. Instructions
Fin si
La dualité suppose le choix entre une alternative de traitements
SI condition ALORS
... instructions 1
SINON
... Instructions 2
FIN SI
Exemple :
Allez tout droit jusqu‘au prochain carrefour
Si la rue à droite est autorisée à la circulation Alors
Tournez à droite
Avancez
Prenez la deuxième à gauche
Sinon
Continuez jusqu‘à la prochaine rue à droite
5
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

Prenez cette rue

Prenez la première à droite
Fin si
b. Conditionnelles imbriquées
Le branchement ou encore appelé imbrication est une généralisation de la structure de contrôle
conditionnelle, lorsque le nombre de traitements différents est plus grand que deux.

SI (condition1) ALORS
... instructions ...
SINON SI (condition2) ALORS
... instructions ...
SINON SI (condition3) ALORS
... instructions ...
SINON
... Instructions
FIN SI
Exemple : Écrire un programme qui donne l‘état de l‘eau selon sa température : solide, liquide ou
gazeuse.
Variable T : Entier
Début
Ecrire ("Entrez la température de l‘eau :")
Lire (T)
Si (T =< 0 )Alors
Ecrire "C‘est de la glace"
sinon
Si (T > 0 Et T < 100) Alors
Ecrire ("C‘est du liquide")
sinon
Ecrire ("C‘est de la vapeur")
Finsi
Finsi
Fin

c. Instructions de répétition (boucle)

Les structures de boucles sont invoquées quand il s'agit de répéter un traitement plusieurs fois
dans des conditions quasiment similaires.
La programmation obtenue par l'écriture de boucles est dite "itérative".
Les structures de boucle diffèrent par les nombres minimum et maximum d'itérations. On les
classe en trois types :
- La boucle conditionnelle : TANTQUE
- La boucle répétition indéterminée : RÉPÉTER-JUSQU’À
- La boucle déterminée : POUR

La boucle conditionnelle TANTQUE

Dans cette structure, on commence par tester la condition ; si elle est vérifiée, le traitement est
exécuté.
Syntaxe : TANT QUE (condition) FAIRE
... instructions
FIN TANTQUE

6
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

Exemple :
Variable N, A : entier
DEBUT
N5;
A1;
TANTQUE (N > 0) FAIRE
AA×N
N  N -1
FIN TANTQUE
AFFICHER A
FIN
La boucle répétition indéterminée RÉPÉTER-JUSQU’À
La Dans cette structure, le traitement est exécuté une première fois puis sa répétition se poursuit
jusqu‘à ce que la condition soit vérifiée.
REPETER
... instructions ...
JUSQU‘À CE QUE condition
... suite ...
Exemple :
Variable N, A : entier
DEBUT
N 5 ;
A 1 ;
REPETER
AA×N
N  N -1
JUSQU‘A (N = 1)
AFFICHER A
FIN

NB : La condition de la structure RÉPÉTER-JUSQU‘À est inversée par rapport à la structure

TANTQUE équivalente
Exemple :
Nombre 0
TANTQUE (Nombre > 0) FAIRE
ÉCRIRE ( "Nombre positif?")
LIRE (Nombre)
FINTANTQUE

RÉPÉTER
ÉCRIRE ("Nombre positif?")
LIRE (Nombre)
JUSQU‘À (Nombre < 0)

La boucle déterminée POUR

Dans cette structure, la sortie de la boucle d‘itération s‘effectue lorsque le nombre souhaité de
répétition est atteint.
Syntaxe : Pour (Variable allant de V1 à V2) faire
... instructions ...
Finpour
7
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

Exemple
A 1
Pour (i allant de 1 à 5 ) faire
A A×i
Fin pour
NB : Trois structures répétitives sont disponibles laquelle utiliser dans un algorithme?
Voici quelques règles à considérer
- Si le nombre d‘itérations est déterminé par une variable compteur Utiliser la structure POUR
- Si au moins une itération est requise Utiliser la structure RÉPÉTER-JUSQU’À
- Dans les autres circonstances Utiliser la structure TANTQUE

8
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

VII. les Tableaux

a°) Tableau à une dimension

Un tableau est une variable de types complexe elle peut être définie comme un ensemble
des variables (simple) de même type. Chaque cellule d’un tableau est considérée comme une
variable de type simple. On peut accéder à cette cellule à travers son indice.

Exemple : soit un tableau nommé tab, de type Entier et qui est composé de 10 éléments.

Déclaration tab : Tableau [1..10] : Entier

Pour affecter la valeur x à la cellule de tab d’indice k, il suffit de faire tab[k]X

Exemple : tab :Tableau[1..3] : réel

Tab[0]2,5
2,5
Tab[1]-3,6 
-3,6
Tab[0] 4,2 4,2

On accède à la ieme valeur d’un tableau en utilisant la syntaxe suivante :

nomTableau[indice]

Exemple : tab :Tableau[1..10] : Entier

Tab[2]-5 /* met la valeur -5 dans la 3eme cellule du tableau puisqu’on commence à

compter à partir de 0 */

En considérant le cas où a est une variable de type Entier, a  tab[2] /*met l’entier se trouvant
dans la cellule 3 du tableau dans la variable a.*/

Lire (tab[1]) /* demande à l’utilisateur de saisir un entier qui sera stocké dans la cellule 2.*/

Exercice d’application : Ecrire un algorithme qui affiche la moyenne des notes d’une promotion
de 15 étudiants saisies par le prof.

Algorithme moyenneClasse

Variable Som, Moy :reel

I : Entier

Tab : Tableau[1..15]

Debut

Som  0

9
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

Pour (i allant de 0 à 14) faire

Som  Som + tab[i]

finPour

Moy  som/15

Ecrire(“La moyenne de cette classe est :”, Moy)

Fin

Exercice (homework) : Ecrire un algorithme qui calcule le produit scalaire de deux vecteurs U et
V. puis affiche le résultat.

b°) Tableau à deux dimensions

Un tableau à deux dimensions est une matrice, dont chaque ligne est un tableau à une
dimension :
Tableau à 1 dimension

[ ]

Pour déclarer un tableau a deux dimensions la syntaxe est la suivante :

Tab : Tableau [intervalle1][intervalle2] : Type

Avec intervalle1 = l’intervalle de la 1ere dimension du tableau c’est-à-dire le nombre de ligne du

tableau.

Et intervalle2 = l’intervalle de la 2eme dimension du tableau c’est-à-dire le nombre de colonne

du tableau.

Le parcours de ce type de tableau nécessite deux variables (i et j) appelés indice de parcours.

Pour accéder aux éléments de la ieme ligne et jeme colonne d’un tableau, la syntaxe est la
suivante :

a  Tab[i][j] /*on met la valeur de l’élément situé à la ieme ligne et jeme

colonne dans la variable a */

Tab[i][j]  2 /* met 2 dans la cellule du tableau de ligne i et de colonne j

Exercice : Ecrire un algorithme qui réalise l’addition de deux matrices A et B de même dimension.
Le résultat sera mémorisé dans une troisième variable qui sera ensuite affichée.

10
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

VIII. Fonctions

Un sous-algorithme utilise les variables déclarées dans l’algorithme (appelées variables

globales). Il peut aussi avoir ses propres variables (dites locales) déclarées dans l’espace qui lui
est réservé ; mais qui ne peuvent être utilisées que dans ce sous-algorithme et nulle part ailleurs
car sa portée (visibilité) est limitée au bloc qui la contient. L’espace de ces variables locales n’est
réservé que lorsque le sous-algorithme est appelé et est libéré dès la fin de l’exécution.
b- Un sous-algorithme est déclaré de manière générale c.-à-d. qu’il peut être appelé
plusieurs fois avec différentes valeurs grâce à des arguments. Ces derniers, bien qu’ils soient
facultatifs, sont dits paramètres et sont clairement déclarés, au besoin, dans l’entête du sous-
algorithme.
Un paramètre est une valeur 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. On
distingue deux types de paramètres :
- 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.

- 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. On les définit
indépendamment à chaque appel du sous-algorithme dans l’algorithme principal.
L’exécution d’un sous-algorithme (procédure ou fonction) se fait par une instruction
d’appel (voir sections suivantes). L’application de cette instruction génère un saut vers le sous-
algorithme appelé. La terminaison de ce sous-algorithme redémarre la suite d’instruction
interrompue par l’appel.

Types de sous-algorithme
Un sous-algorithme peut se présenter sous forme de fonction ou de procédure. 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 affiche le(s) résultat(s) demandé(s).

1. Définition, syntaxe et mécanisme de passage de paramètres

Une fonction est un bloc d'instructions qui porte un nom, son identificateur qui prend des
valeurs en entrée par l'intermédiaire de paramètres qui calcule et renvoie un résultat conforme à
sa spécification et aux conditions de son appel

Le profil (ou signature) d'une fonction est constitué de la liste de types des valeurs entrées
et du type de la valeur renvoyée en résultat liste des types des valeurs d'entrée → type du
résultat

Exemples :

maxdeux : (entier, entier) → entier

Sous-chaine : (chaine de caractères, entier, entier) → chaine de caractères

a. Définition de la fonction

11
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

Une fonction peut être définie n'importe où, à l'extérieur d'un algorithme. La définition de
la fonction se compose de : son en-tête qui comprend :

 son identificateur
 la liste de ses paramètres formels et de leur type
 le type de la valeur qu'elle renvoie
 des déclarations locales (constantes ou variables)
 les instructions qui calculent son résultat
 au moins une instruction retourné qui renvoie la valeur résultat

Fonction <ident-fonction>
(<ident-paramètre> : <type> <role>
...
<ident-paramètre> : <type> <role>) : <type>
/* spécification et conditions d'appels */
Variables locales
<ident-variable> : <type>
....
<ident-variable> : <type>
Début
<instructions>
retourner <expression>
Fin

Attention : Il est indispensable de spécifier chaque fonction, et de préciser les conditions

dans lesquelles elle doit être appelée. En effet si le programmeur qui intègre une fonction à un
de ses programmes ne respecte pas les conditions d'appels, il n'a aucune garantie sur ce que fera
la fonction dans son programme.

b. Appel de la fonction

La fonction est appelée depuis un algorithme principal, ou depuis une autre fonction (ou
procédure2), dans l'expression où le résultat qu'elle renvoie doit être utilisé.

<ident-fonction>(<ident-paramètre>, ..., <ident-paramètre>)

c. Passage de paramètres

Dans la définition de la fonction on parle du: paramètres formels

Dans l'appel de la fonction on parle du : paramètres effectifs (ou réels)

Il doit y avoir une correspondance biunivoque entre les paramètres formels et les
paramètres effectifs, la correspondance étant régie par l'ordre d'écriture.

À l'appel de la fonction, le premier paramètre effectif passe sa valeur au premier

paramètre formel, le deuxième paramètre effectif passe sa valeur au deuxième paramètre
formel, et ainsi de suite. La fonction exécute son code puis renvoie son résultat.

12
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

Les paramètres qui se correspondent doivent avoir des types compatibles.

2. Fonctions prédéfinies

Il existe des fonctions prédéfinies, souvent organisées en bibliothèques de fonctions qui

regroupent les fonctions par domaine (math, chaînes de caractères, système, etc.).:

 Fonctions mathématiques : racine, fonctions trigonométriques, etc.

Exemple : pour calculer l'hypoténuse d'un triangle rectangle

lire (a, b)

C ← racine ((a * a) + (b * b))

 fonction sur les chaînes de caractères : longueur, sous chaine

Exemple : pour afficher les trois premiers caractères d'une chaîne

lire(chaine)

si nbcar >= 3 alors

écrire ('Début : ', sous_chaine(chaine, 1, 3))

finsi

il est possible de définir des nouvelles fonctions si elles sont nécessaire, c'est à dire de leur
donner un identificateur et de programmer les calculs qui conduisent à ce qu'elles doivent
renvoyer.

3. Rôle d'une fonction

Une fonction prend des données par l'intermédiaire de ses paramètres, et renvoie un
résultat conforme à sa spécification, à condition que les conditions d'appels soient respectées.
13
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

Par exemple : un algorithme ne doit pas appeler une fonction racine avec un paramètre de valeur
négative, si cela arrive, c'est l'algorithme qui est faux, pas la fonction.

Exemple : Les deux algorithmes Maxquatre ci-dessous calculent le maximum de quatre

nombres entiers.

Dans le premier algorithme, la même instruction conditionnelle est répétée trois fois, aux
noms des variables près dans le deuxième algorithme, les trois instructions conditionnelles
analogues sont remplacées par des appels à une même fonction qui s'applique à des valeurs
différentes. Ceci rend plus compréhensible ce que fait l'algorithme en évitant de dupliquer des
instructions identiques.

Algorithme Maxquatre_1

Variables
a, b, c, d : entier /* nombres d’étude */
mab, mcd : entier /* maxima intermédiaires */
maxi : entier /* maximum des 4 nombres */
Début
Lire (a, b, c, d)
si a > b alors
mab ← a
Sinon
mab ← b
finsi
si c > d alors
mcd ← c
sinon
mcd ← d
finsi
si mab > mcd alors
maxi ← mab
sinon
maxi ← mcd
finsi
écrire(maxi)
Fin

Algorithme Maxquatre_2

Variables
idem ci-dessus
Début
Lire (a, b, c, d)
mab ← maxdeux(a, b)
mcd ← maxdeux(c, d)
14
Par : Nino Payang DEDJINH
Université St Charles Lwanga de Sarh
Filière : Génie Informatique Niveau : L1, Semestre 1
Code UE : ALG102

maxi ← maxdeux(mab, mcd)

Écrire (maxi)
Fin

Définition de la fonction maxdeux

Fonction maxdeux(x, y : entier) : entier

mxy : entier /* maximum de x et de y */
Début
si x > y alors
mxy ← x
sinon
mxy ← y
finsi
retourner (mxy)
Fin

4. Intérêt des fonctions

 Ne pas dupliquer du code
 Offrir une meilleure lisibilité car le lecteur peut comprendre ce que fait une fonction,
uniquement à la lecture de son nom, sans avoir à déchiffrer du code.
 Partager le développement entre différentes équipes qui se spécialisent.
 Construire des bibliothèques de fonction pour réutiliser ce qui a déjà été fait.

15
Par : Nino Payang DEDJINH