REPOBLIKAN’I MADAGASIKARA

Fitiavana-Tanindrazana –Fandrosoana
--------------------------------------
MINISTERE DE L’ENSEIGNEMENT
SUPERIEUR
ET DE LA RECHERCHE
SCIENTIFIQUE
UNIVERSITE D’ANTSIRANANA
--------------------------------

----------------------------------------

Institut Universitaire des Sciences de l’Environnement et la Société (IUSES)

Matière :

ALGORITHMIQUE

Parcours: SMEBM / M1
Réaliser par: FALIMANANA Jean Cedinot
Responsable :Mr TONGALAZA Mahatoly Odilon

Année universitaires: 2024-2025

 REPOBLIKAN’I MADAGASIKARA
Fitiavana-Tanindrazana –Fandrosoana
--------------------------------------
MINISTERE DE L’ENSEIGNEMENT
SUPERIEUR
ET DE LA RECHERCHE
SCIENTIFIQUE
UNIVERSITE D’ANTSIRANANA
--------------------------------

----------------------------------------

Institut Universitaire des Sciences de l’Environnement et la Société (IUSES)

Matière :

ALGORITHMIQUE

Parcours: SMEBM / M1
Réaliser par: FALIMANANA Jean Cedinot
Responsable :Mr TONGALAZA Mahatoly Odilon

Année universitaires: 2024-2025

3
Table des matières
INTRODUCTION ................................................................................................................................... 6
I. ALGORITHMIQUE ....................................................................................................................... 7
1. Un algorithme ............................................................................................................................ 7
2. Objectif de ce cours ................................................................................................................... 9
3. Les opérateurs.......................................................................................................................... 12
4. Lecture et écriture ................................................................................................................... 15
5. Lecture et écriture ................................................................................................................... 15
6. Chaine des caractères .............................................................................................................. 16
LONGUEUR () ................................................................................................................................ 18
7. Structure conditionnelle à choix multiple ............................................................................. 25
8. ................................................................................................................................................... 29
9. Structures itératives Pour ....................................................................................................... 33
10. Variables scalaires ............................................................................................................... 38
11. Fonction et Procédures ........................................................................................................ 42
12. La récursivité ....................................................................................................................... 47
13. Fonction Factorielle (nbr:Entier):Entier........................................................................... 48
14. Avec une fonction recursive ................................................................................................ 49
II. STRUCTUR DES DONNEE ........................................................................................................ 57
Caractéristiques principales :......................................................................................................... 57
Méthodologie pour spécifier ........................................................................................................... 57
II.1 Structures de données linéaires .......................................................................................... 57
a Notion de structure linéaire ................................................................................................ 57
b Exemples détaillés : ............................................................................................................. 58
 Tableaux : ............................................................................................................................. 58
 Listes chaînées : ................................................................................................................... 58
 Piles (Stack) : ....................................................................................................................... 58
 Files (Queue) ........................................................................................................................ 58
II.2 Structures de données non linéaires................................................................................... 59
Exemples détaillés : ......................................................................................................................... 59
 Arbres : ................................................................................................................................. 59
 Graphes : .............................................................................................................................. 59
 Tables de hachage (Hash Tables): ...................................................................................... 59
CONCLUSION ..................................................................................................................................... 60

4
5
INTRODUCTION
Les structures de données sont des éléments fondamentaux en informatique, permettant
d'organiser et de gérer les données de manière efficace. Elles jouent un rôle crucial dans le
développement de logiciels et d'applications, car elles influencent directement les
performances et la complexité des algorithmes. Les structures de données peuvent être
classées en deux grandes catégories : les structures de données linéaires et les structures de
données non linéaires. Dans ce devoir, nous allons explorer ces deux types de structures, en
fournissant des exemples concrets pour illustrer leur fonctionnement et leur utilité.

6
 I. ALGORITHMIQUE

1. Un algorithme
Est une suite d’opérations élémentaire, dites instructions, qui une fois exécuté correctement,
conduit à un résultat donné.
Vous exécutez toujours des algorithmes dans votre vie quotidienne
- Quand vous faites vos courses au marché
- Quand vous montrez un chemin a un touriste
- Quand vous exécutez une recette de cuisine

Vous créez et exécutez toujours des algorithmes.

Pour résoudre un problème informatique,
On crée souvent un programme pour le résoudre.
Le choix du langage dépend de nombreux facteurs
Par exemple :
- Thématique à traiter
- Maniabilité et portabilité du langage de programmation
- popularité du langage (support disponible)
- Fiabilité
- Syntaxe facile et intuitive
- etc.
Malgré qu’il existe de nombreux langages de programmation, ils partagent tout le même point
commun ″ La logique″

7
La logique de programmation est tout simplement l’algorithme
Un algorithme est indépendant de toute architecture matérielle ou logicielle.

Il n’est pas destiné à être exécuté par la machine.

Il constitue plutôt une ébauche d’un futur programme.
Un algorithme peut être représenté sous forme de :
-Organigramme
- pseudo-code

Le pseudo-code est plus utilise car il est plus proche de la structure d’un vrai
programme.

Début

C’est quoi la valeur de A ?

Valeur de A précisée et récupérée

C’est quoi la valeur de B ?

Valeur de B précisée et récupérée

B=0 ?

C←A/B
Opération invalide

Afficher la valeur de C

Fin

8
 1 Algorithme Division
2 Variables
3
A ,B : Entier
4
C : Réel
5
Début
6

7
Ecrire (‘Entrer la valeur de A : ‘)

8 Lire(A) ;
9 Ecrire (‘Entrer la valeur de B :)
10 Lire(B) ;
11
Si B=0 Alors
12
Ecrire (‘opération invalde !’)
13
Sinon
14
C ˂- A/B ;
15

16 Ecrire (‘Le résultat est : ’, C)

17 FinSi
18 Fin

2. Objectif de ce cours
 Découvrir les bases de l’algorithmique (variable, opérateurs, structures conditionnelles
et itératives, chaines de caractères, tableaux, fonctions et procédures…
 Apprendre à écrire des algorithmes fonctionnels et optimisés.

Les variables et les types

Entier Booléen

Chaine de
Réel
caractère

Une variable est une entité dont la valeur peut changer

D’où le non ʺvariableʺ
On peut imaginer que les variables sont des boites qui ont toutes des non uniques

9
En réalité, une variable est une case mémoire.

Avant de manipuler une variable il faut au préalable définir son type.

Le type représente en quelque sorte la taille et les caractéristiques de la boite.
En Algorithmique, on se contente de définir les types de base.
Ces types sont :

- Les entiers
- Les réels
- Les booléen
- Les chaines de caractères.

Les entiers sont des nombres qui s’expriment sans virgule et peuvent être positifs ou négatifs.
Les entiers s’expriment sur 16 bits (entier courts) ou 32 bits (entiers long).

Les valeurs possibles d’un entier sont exprimées de cette manière :×

-2n ≤ N ≤ +2n-1
N : Nombre entier à exprimer
n : Nombre de bits pour représenter l’entier en mémoire
-2 147 483 648 ≤ N ≤ 2 147 483 647
Les réels sont des nombres qui s’expriment avec une virgule (dite virgule flottante).

Les réels peuvent être codes sur 32 bits (dans ce cas on parle d’une simple précision) ou 64
bits (pour la double précision).

10
Type Intervalle
Byte (octet 0 à 225
Entier simple -32 768 à 32 767
Entier long -2147 483 648 à 2147 483 647
Réel simple -3,40× 1𝑂38 a -1,40× 10−45 pour les valeurs négatives
1,40× 10−38 à pour les valeur positives
Réel double -1,79× 10308 à -4,94× 10−324 pour les valeur négatives
308
4,94× 10−324 à 1,79×10

Les booléens représenter un type qui n’accepte que l’une des deux valeurs ″vrai″ ou ″faux″
(que l’on peut aussi représenter par 1ou 0.

Les chaines de caractères représentent un type qui accepte des caractères alphabétiques,
numérique ou symboles.

Le non de la variable (identifiant) doit contenir seulement des caractères alphabétiques

numériques et le symbole souligné, et il doit commencer par un caractère alphabétique.
Exemples :

Var123
Ma variable
Prénom
Numéro de téléphone
Variables tva : Entier

Variables
Tva : Entier
Prix HT : Réel
Algorithme Non de 1 algo
Variables
Variable1, variable2 . . . : type1
Variable3, Variable4 . . . : type2

Début
Liste des instructions
Fin

11
Algorithme prix TTC
Variables
Tva, quantité : Entier
prix HT , PrixTTC - : Réel
Début
Fin
3. Les opérateurs
Addition Produit Soustraction DIVISION ET OU NON MODULE
Les opérateurs sont des symboles qui permettent d’effectuer des opérations.
Par exemple :
L’addition et la soustraction sont des opérations
Elles sont représentées par les opérateurs + et –
- Operateur d’assignation (ou d’affectation)
- Opérateurs de calcul (operateur arithmétiques)
- Opérateur de comparaison
- Operateurs logiques
Algorithme Mon Algo
Variables
A, B : Entier
Début
Fin
Algorithme Mon Algo
A, B : Entier
Début
A ←10
B←2
Fin
A ←10
B ←A

12
Donc la variable B VAUT 10
Operateurs arthméqués
+ Addition
-soustraction
* produit
/ Division
Div. Division entière (retourne le résultat sous forme entière )
% Modulo (reste de la division)
˄ Puissance (2 ˄ 3 VAUT 8)
A←10
B←2
C←A+B
C vaut 12
C←A/B
C vaut 5
C←A%B
C vaut 0
A ←10
A←A+1
A vaut 11
A←10+2*5-1
A vaut 19
˄,*, /, div et % sont prioritaires à + et –
A ←10 + 2 * ( 5 – 1)
A vaut 18
Opérateurs de comparaison :
= Egalité des valeurs
< Strictement inferieur
>Strictement supérieur

13
˂= Inférieur ou égal

˃= Supérieur ou égal
< >Différent
A←10
B←2
A=B (faux)
A ˃ B (vrai)
A ←10
B ←2
A˃ B ET A ˂ 20 (vrai)
Les Opérateurs logiques utilisés en algorithmique sont :

ET, OU et NON

A B A ET B A OU B
FAUX FAUX FAUX FAUX
FAUX FAUX FAUX VRAI
VRAI VRAI FAUX VRAI
VRAI VRAI VRAI VRAI

A NON A
FAUX VRAI
VRAI FAUX

14
 4. Lecture et écriture
Algorithme Addition variables
A, B,C : Entier Début
A ←10
B ←20
C ←A+B
Fin
- Le programme affiche des messages à l’écran pour que l’utilisateur puisse les lire.
- L’utilisateur soumet au programme des données qu’il saisit, afin dès les traiter.

5. Lecture et écriture
Algorithme Addition
Variables : A, B, C : Entier
Début
A←10
B←20
C←A+B
Fin
Ecriture (‘ veillez entrer un nombre entier : ‘)

Lire (A)
C’est l’équivalent de :
A← L’entrée de l’utilisateur

15
 Algorithme Addition
Variables
A, B, C : Entier
Début
Ecriture (‘ veillez entrer un nombre entier : ‘)

Lire (A)
Ecriture (‘ veillez entrer un nombre entier : ‘)

Lire (B)
C←A+B

Ecriture (‘C’) (la lettre C serra affichée)

Ecrire (la somme vaut c’)
Fin

15+3=18
Début
Ecriture (‘ veillez entrer un nombre entier : ‘)

Lire (A)
Ecriture (‘ veillez entrer un nombre entier : ‘)

Lire (B)
C←A+B
Ecrire (‘ A,’+’,B ,’ = ‘, C)
Ecrire (‘ A ,’+’,B ,’ = ‘, A+B)
Fin

6. Chaine des caractères

ASCII
American standard code for interchangeu

Point aux années 60

16
UNICODE
Mis au point en 1991

17
 Variables Ma Variable : Chaine de caractères
OU
Variables Ma variable : chaine
Algorithme Nom Prénom
Variables
Nom, prénom : chaine de caractères
Début
Ecrire (‘Nom ‘)
Lire (Nom)
Ecrire (prénom :’ )
Ecrire (‘ votre nom compte est : ‘,nom,’ ‘,prénom)
Fin

&
Opérateur de concaténation de caractères
Algorithme Nom prénom
variables
nom ,prénom, nom _complet : chaine de caractères
Début
Ecrire (‘Non : ‘)
Lire (nom)
Ecrire (‘prénom : ‘)
Lire (prénom)

Nom complet ← nom & ‘= , ,& prénom

Ecrire (‘Votre nom complet est : ‘ ,nom complet)
Fin

LONGUEUR ()
Cette fonction permet de calculer le nombre de caractères présents dans la chaîne spécifiée
entre ses parenthèses.
Exemple :

18
Longueur (‘Bonjour’) renvoie la valeur 7
Algorithme Nbr_de_lettres
Variables
Phrase : Chaine de caractères
nbr : Entier
Début
Ecrire (‘Entrez une phrase de votre choix : ‘)
Lire (phrase)
nbr ← longueur (phrase)
Ecrire (‘Votre phrase contient ‘ ,nbr,’ caractères’)
Fin

19
 Les structures conditionnelles

Les structures de contrôle englobent :

- Les structures séquentielles

- Les structures conditionnelles
- Les structures itératives

Face à un feu de signalisation :

Feu vert
Le conducteur continue à rouler

Feu rouge
Le conducteur s’arrête

Feu orange
Selon la situation, le conducteur peut soit s’arrêter ou continuer à rouler
Condition (ou Prédicat)
Si condition est vrai Alors
Traitement 1

Sinon
Traitement 2

FinSi

20
Si Alors
Traitement 1

Sinon
Traitement 2

FinSi
Algorithme Carrefour
Variable
Nbr : Entrer
Début
Ecrire (‘Veuillez spécifier un chiffre parmi 1, 2 ou 3 : ‘)
Lire (nbr)
Si (nbr = 1) Alors
Ecrire (‘Le feu est rouge’)
Sinon
Ecrire (‘Le feu n’ ‘est pas rouge’)
FinSi
Fin

21
Algorithme Carrefour
Variable
nbr : Entrer
Début
Ecrire (‘Veuillez spécifier un chiffre parmi 1, 2 ou 3 : ‘)
Lire (nbr)
Si (nbr = 1) Alors
Ecrire (‘Le feu est rouge’)
FinSi
Si (nbr <> 1) Alors
Ecrire (‘Le feu n’ ‘est pas rouge’)
FinSi
Fin

Algorithme Carrefour
Variable
nbr : Entrer
Début
Ecrire (‘Veuillez spécifier un chiffre parmi 1, 2 ou 3 : ‘)
Lire (nbr)
Si (nbr = 1) Alors
Ecrire (‘Le feu est rouge’)
FinSi
Si (nbr <> 1) Alors
Ecrire (‘Le feu n’ ‘est pas rouge’)
FinSi

Fin

22
Algorithme Carrefour
Variable
nbr : Entrer
Début
Ecrire (‘Veuillez spécifier un chiffre parmi 1, 2 ou 3 : ‘)
Lire (nbr)
Si (nbr = 1) Alors
Ecrire (‘Le feu est rouge’)
Sinon
Ecrire (‘Le feu n’ ‘est pas rouge’)
FinSi
Fin

Algorithme Carrefour
Variable
nbr : Entrer
Début
Ecrire (‘Veuillez spécifier un chiffre parmi 1, 2 ou 3 : ‘)
Lire (nbr)

23
 Si (nbr = 1) Alors
Ecrire (‘Le feu est rouge’)
Sinon
Si (nbr = 2) Alors
Ecrire (‘Le feu est orange’)
Sinon
Ecrire (‘Le feu est vert’)
FinSi
Fin
Algorithme Carrefour
Variable
nbr : Entrer
Début
Ecrire (‘Veuillez spécifier un chiffre parmi 1, 2 ou 3 : ‘)
Lire (nbr)
Si (nbr = 1) Alors
Ecrire (‘Le feu est rouge’)
Sinon
Si (nbr = 2) Alors
Ecrire (‘Le feu est orange’)
Sinon
Ecrire (‘Le feu est vert’)
FinSi
FinSi
Fin

24
 7. Structure conditionnelle à choix multiple
(Structure sélective)

1- Un
2- Deux
3- Trois
4- Quatre
5- Cinq

25
Algorithme chiffres

Variables

Nbr:Entier

Débit

Ecrire (‘Entrerunentiercompris1et5:’)

Lire (nbr)

Si (nbr=1) Alors

Ecrire (‘Un’)

Sinon

Si (nbr=2) Alors

Ecrire (‘Deux’)

Sinon

Si (nbr=3) Alors

Ecrire (‘Trois’)

Sinon

Si (nbr=4) Alors

Ecrire (‘Quatre’)

Sinon

Si nbr=5) Alors

Ecrire (‘Cinq’)

Sinon

Ecrire (‘vous avez peut être saisi un autre chiffre’)

FinSi

FinSi

FinSi

FinSi

FinSi

Fin

26
Selon Sélecteur Faire
Valeur 1 : Traitement 1
Valeur 2 : Traitement 2
…
Valeur n : Traitement n
Sinon : Autre traitement

Fin Selon

Algorithme Chiffres
Variables
nbr : Entrer
Début
Ecrire (‘Entrer un entier compris entre 1 et 5 : ‘)
Lire (nbr)
Selon nbr Faire

1 : Ecrire (‘ Un’)
2 : Ecrire (‘ Deux’)
3 : Ecrire (‘ Trois’)
4 : Ecrire (‘ Quatre’)
5 : Ecrire (‘ Cinq’)
Sinon : Ecrire (‘Vous avez peut être saisi un autre chiffre’)
FinSelon

OU
Selon nbr Faire
Cas 1 : Ecrire (‘ Un’)
Cas 2 : Ecrire (‘ Deux’)
Cas 3 : Ecrire (‘ Trois’)
Cas 4 : Ecrire (‘ Quatre’)
Cas 5 : Ecrire (‘ Cinq’)
Autrement : Ecrire (‘Vous avez peut être saisi un autre chiffre’)
FinSelon

27
Ou encore
Cas ou nbr vaut

1 : Ecrire (‘ Un’ )
2 : Ecrire (‘ Deux’ )
3 : Ecrire (‘ Trois’ )
4 : Ecrire (‘ Quatre’ )
5 : Ecrire (‘ Cinq’ )
Autrement : Ecrire (‘Vous avez peut être saisi un autre chiffre’)
Fin Cas

28
8. Structures itératives

Structures TantQue

Structure itérative ( ou Boucle)

Permet des répéter le même traitement plusieurs fois

24 (𝑜𝑢 2^4)

Vaut

2∗ 2∗ 2∗ 2

225 (ou 2∧ 25)

Vaut
2 * 2 * 2 * 2…*2 (25 fois)
- Boucle TantQue
- Boucle Pour
- Boucle Répété
- TantQue Condition
Liste des instructions
FinTanQue

29
Itération (Répétions de la boucle)
Algorithme Bonjour
Variables
n : entier
Début
Entier ( ‘Entrer le nombre de répétition : ‘)
Lire(n)
TantQue VRAI
Ecrire (‘Bonjour’) Boucle infinie
FinTantQue
Fin

30
Algorithme Bonjour
Variables
n, i : Entier
Début
Ecrire ( entrer le nombre de répétitions : ‘)
Lire (n) n vaut 3
I←0 I vaut 0
TantQue i ˂n I ˂n (vrai)
Ecrire (‘ Bonjour ‘)
i ← i+1
FinTantQue
Fin
Algorithme Bonjour
Variables
n, i : Entier
Début
Ecrire ( entrer le nombre de répétitions : ‘)
Lire (n) n vaut 3
I←0 I vaut 0
TantQue i ˂n I ˂n (vrai)
Ecrire (‘ Bonjour ‘)
i ← i+1
FinTantQue
Fin
Algorithme Bonjour
Variables
n, i : Entier
Début
Ecrire ( entrer le nombre de répétitions : ‘)

31
 Lire (n) n vaut 3
I←0 I vaut 0
TantQue i ˂n I ˂n (faux)
Ecrire (‘ Bonjour ‘)
i ← i+1
FinTantQue
Fin
Algorithme puissance
Variables
N, p, R, 1 : Entier
Début
Ecrire (‘Entrer la base N : ‘)
Lire (N)
Ecrire (‘Entrer 1’ ‘ exposant p : ‘)
Lire (p)
R← 1
i← 1
TantQue i ˂=p
R← R*N
i ← i+1
FinTantQue
Ecrire (N, ‘^’,p,’=’,R)
Fin

32
9. Structures itératives Pour
Algorithme puissance
Variables
N ,P ,R ,i :Entiers
Début
Ecrire ('Entrer la base N : ‘)
Lire (N)
Ecrire (‘Entrer l’exposent p : ‘)
Lire (p)
R—1
I—1
TantQue i˂=p
R—R*N
i—i+1
FintantQue
Ecrire ( N, ‘˄’,P, ‘ =’, R )
Fin
-Initialisation du compteur
- Spécification de la condition
- Changement de la valeur du compteur
Pour compteur – valeur initiale à valeur finale pas valeur Du pas

Fin pour
Pour compteur – valeur initiale à valeur finale
Liste des instructions
FinPpour

33
 Faux
Condition

Mondification du
Vrai
compteur
Bloc

D’instructions

Algorithme puissance
Variables
N, P, R ,i : Entiers
Début
Ecrire (‘Entrer la base N : ‘)
Lire (N)
Ecrire (‘ Entrer l’exposant p : ‘)
Lire (p)
R—1
POUR i—1 à p
R—RN
Finpour
Ecrire (N ,’˄’,p,’=’,R)
Fin
La structure pour est préférée
Si le nombre d’itération et connu d’avance.
La structure TantQue est utilisée
Si on ignore le nombre d’itération

34
 Algorithme Table de multiplication
Variables
I , j : Entier
Début
Pour i – 1 à 9
Pour j – i—1 à 9
Ecrire (i , ‘x’, j,’=’,i*j)
Finpour
Finpour
Fin
-Structure pour : quand on connait d’avance le nombre d’itération à exécuter.
Structure TantQuue : quand on ne connait pas précisément d’itération à exécuter
TanQue
Pour.
Faux
Condition Faux
vrai
Condition

Bloc Mondification
Vrai D’instruction
vrai
Du compteur

Bloc

d’instructions

35
 Algorithme Test
Variables
i : Entier
Début
i – 11
TantQue i˂=10
Ecrire (‘Itération de la boucle exécutée’)
i—i+1
FinTantQue
Fin
Algorithme Test
Variables
I : Entier
Début
Pour i – 11 à 10
Ecrire (‘Itération de la boucle exécutée’)
FinPour
Fin

La structure Répéter est une structure itérative qui permet d’exécuter au moins une itération
avant de vérifier la condition

Bloc d’instruction

vrai
condition

Faux

36
Répéter
Liste des instructions
Jusqu’à condition
Algorithme Test
Variables
i : Entier
Début
i←11
Répéter
Ecrire (‘ Itération de la boucle exécutée’)
i←i+1
Jusqu’à i˃10
Fin
Algorithme Division
Variables
A ,b ,c :Réel
Début
Ecrire (‘Entrer le nombre a : ‘)
Lire (a)
Répéter
Ecrire (‘Entrer le nombre b : ‘)
Lire(b)
Jusqu’à b˂˃0
c←a/b
Ecrire (a,’/’, b’,=’,c)
Fin
-Structure pour : quad on connait d’avance le nombre d’itérations d’avance

- Structure TanQue : quand on ne connait pas précisément le nombre d’itération à

exécuter

37
 - Structure Répéter : quand la condition dépend d’un traitement qui peut etre répétitif
et qui doit s’exécuter au moins une fois

Les tableaux
Tab (n)
Tab [0]
Tab [1]
Tab [2]

Tab [n-2]
Tab [n-1]

10. Variables scalaires

Peuvent contenir une seule valeur
Exemple : Entiers, réel, chaines et booléen
Algorithme Etudiants
Variables
nom1, nom2, nom3, nom4 : chaine de caractères
Début
Ecrire (‘Non de 1 ‘ ‘ étudiant 1 : ‘)
Lire (nom1)
Ecrire (‘Non de 1 ‘ ‘étudiant 2 : ‘)
Lire (‘Nom2)
Ecrire (‘Nom de 1 ‘ ‘ étudiant 3 : ‘)
Lire (‘Nom3)
Ecrire (‘Non de 1 ‘ ‘ étudiant 4 : ‘)
Lire (‘Nom4)
Fin
Un tableau est une variable qui peut contenir plusieurs valeurs à la fois

38
Identifiant du tableau

On commence souvent la numérotation des cases à partir de 0 et on incrémente de 1 pour

passer à la case suivante.

Tableau Identifiant (Nombre_d_éléments) : Type

Tableau nom(40) : Chaine de caractères

Tableau nom[0 … 39] : Chaine de caractères

Nom[numéro_de_la_case]

Pour accéder au 10è𝑚𝑒 é𝑙é𝑚𝑒𝑛𝑡

nom[9] : Si le premier indice est 0

nom[10] : Si le premier indice est 1

Pour accéder au 10è𝑚𝑒 é𝑙é𝑚𝑒𝑛𝑡

nom [9]

39
Algorithme Etudiants
Variables
Tableau nom(40) : Chaine de caractères
i : Entier
Début
Pour i ← 0 à 39
Ecrire (‘Nom de l’’étudiant ‘ , i+1, ‘ : ‘)
Lire (nom[ i ])
FinPour
Fin
Ecrire (‘Le tableau contient ‘, longueur (nom),’ éléments’)
Le message Le tableau contient 40 éléments sera affiché

nom [9]
Algorithme Etudiants
Variables
Tableau nom(40) : Chaine de caractères
i : Entier
Début
Pour i ← 0 à 39
Ecrire ( ‘Nom de l ’ ’étudiant ‘ , i+1,’ : ‘)
Lire (nom[ i ])
FinPour
Pour i ← 0 à longueur (nom) -1
Ecrire (‘Nom de l’’étudiant ‘ , i+1 : ‘,nom[ i])
FinPour
Fin

Une chaîne de caractères est un tableau de caractères. Chaque caractère constituant la chaîne
est mis dans une case qui possède un indice.

40
Algorithme Phrase
Variable
mot : Chaine de caractères
Début
mot ← ‘Bonjour’
Ecrire (mot[ 0 ]) Affiche ‘B’
Ecrire (mot[ 1 ]) Affiche ‘o’
…
Ecrire mot[ 6 ]) Affiche ‘r’
Fin

Algorithme Etudiants
Variables
mot : Chaine de caractères
i : Entier
Début
mot ← ‘Bonjour’
Pour i ← 0 à longueur (mot)-1
Ecrire (mot [ i ])
FinPour
Fin

41
 11. Fonction et Procédures
Fonctions et Factorielle () :Entier
Procédure ligne ()
Algorithme informations
Variables
Non, Prénom, Adresse : chaine de caracteres
i:Entier
Début
Ecrire (‘Non : ‘)
Lire (nom)
Pour i—1 à 20
Ecrire (‘_’)
Finpour
Ecrire (‘prénom : ‘)
Lire (prénom)
Pour i—1 à 20
Ecrire (‘_’)
Finpour
Ecrire (‘adresse : ‘)
Lire (adresse)
Pour i—1 à 20
Ecrire (‘_’)
Finpour
Fin

42
Algorithme informations
Variables
Non, Prénom, Adresse : chaine de caracteres
i:Entier
Début
Ecrire (‘Non : ‘)
Lire (nom)
Pour i—1 à 20
Ecrire (‘_’)
Finpour
Ecrire (‘prénom : ‘)
Lire (prénom)
Pour i—1 à 20
Ecrire (‘_’)
Finpour
Ecrire (‘adresse : ‘)
Lire (adresse)
Pour i—1 à 20
Ecrire (‘_’)
Finpour
Fin

Factoriser un code consiste à le déclarer une seule et l’invoquer selon le besoin

Sous- Programme
Procédure ou fonctions

43
Procédure_Non_de_la procédure ()
Variables
Variable 1 :Type 1 Variables locales
Variable 2 :Type2
…
Début
Traitement voulu
Fin
Portée d’une variable :
-Locale
- Globale
Procédure Ligne ()
Variables
I : Entier
Début
Pour i—1 à 20
Ecrire (-_’)
Finpour
Fin

Ligne ()
Algorithme information
Procédure Ligne ()
Variable
i :Entrer
Début
Pour i—1 à 20
Ecrire (‘_’)
Finpour
Fin

44
 Variables
Non, Prénom, Adresse : chaine de caractères
i:Entier
Début
Ecrire (‘Non : ‘)
Lire (nom)
Ligne ( )
Ecrire (‘prénom : ‘)
Lire (prénom)
Ligne ( )
Ecrire (‘adresse : ‘)
Lire (adresse)
Ligne ( )
Fin

Procédur Nom_de_la_procedur (argument 1 : Type 1, argument 2 : Type 2, …)

Nom_de_la_procedur (valeur 1, valeur 2,…)
Algorithme Informations

Procédure Ligne (nbr : Entier, car : chaine de caractères)

Variables

I : Entier

Début

Pour i<—1à nbr

Ecrire (car)
FinPour

Fin

45
Variables
Nom, prénom, adresse :chaine de caractères
i:Entier
Début
Ecrire (‘Nom:‘)
Lire (nom)
Ligne (20,’_’)
Ecrire (‘prénom:‘)
Lire (prénom)
Ligne (15,’*’)
Écriree (‘Adresse:‘)
Lire(Adresse)
Ligne (10,’+’)
Fin
Une fonction est un sous- -Programme qui retourne un résultat
Fonction nom de la fonction () : type_de_retour
Variables
Variable1 : Type1
Variable2 :Type2
…
Début
Traitement voulu
Retourne Valeur_de_retour
Fin

Factorielle (3)
Ecrire (‘La factorielle de 3 vaut ‘, Factorielle (3)
La factorielle de 3 vaut 6

46
 𝑛!
𝑐𝑛𝑘 =(
𝑛−𝑘 )!∗𝑘!

Algorithme combinaison
Fonction Factorielle (nbr : Entier) : Entier
Variables
R, i : Entier
Début
R←1
Pour i←1 à nbr
R—R*i
Finpour
Retourne R
Fin
Variables
n, k:Entier
C:Réel
Début
Ecrire (‘Entrer n et k svp :‘)
Lire (n, k)
c<—Factorielle(n)/Factorielle (n-k)*Factorielle(k))
Ecrire (‘la combinaison de‘, k,’parmi‘, n’ vaut’, c)
Fin

12. La récursivité
Est le fait d’appeler une fonction depuis son corps

47
 13. Fonction Factorielle (nbr:Entier):Entier
Début
Si nbr=0 alors
Retourne1
Sinon
Retourne nbr*Factorielle (nbr-1)
Fin

nbr*(nbr-1)*(nbr-2)*…*1
La récursivité
Fonctions ( )
Début
….
F()
…..
Fin
Ce qui la même à réexécuter de manière séquentielle
Avec la boucle TantQue
Avec la boucle TantQue Avec la boucle TantQue Avec la boucle TantQue
Algorithme Somme Algorithme Somme Algorithme Somme
Variables Variables Variables
i,s:Entier i, s: Entier i,s:Entier
Début Début Début
s<—0 s<—0 s<—0
i<—1 Pour i<—1 i<—1
TantQuei<=10 s<—s+1 Répéter
s<—s+1 FinPour s<—s+1
i<—i+1 Ecrire(s) i<—i+1
FinTantQue Fin Jusqu’ài>10

48
 Ecrire(s) Fin

Fin

Avec une fonction recursive 1O+ FoncRec (9)

Algorithme Somme 9+ FoncRec (8)

Fonction FoncRec (nbr: Entier): Entier 8+ FoncRec (7)
Début 7+ FoncRec (6)
Retourne nbr+FoncRec (nbr-1) 6+ FoncRec (5)
Fin …
Début 0+ FoncRec (-1)
Écrire (FoncRec(10)) -1++ FoncRec (-2)
Fin …

14. Avec une fonction recursive

Algorithme Somme
Fonction FoncRec (nbr: Entier): Entier
Début
Si nbr=0 Alors
Sinon
Retourne nbr* Factorielle (nbr-1)
finsi
Fin

49
Complexité des algorithme
0(1)
0(n)
0(n2)
0(log(n))
…
Qu’est ce qui fait dire qu’un algorithme est plus efficace qu’un autre ?

Avant toute chose,

Il faut déjà que l’algorithme soit fonctionnel
On juge de l’efficacité des algorithmes sur la quantité des ressources qu’ils exigent à savoir :
Le temps : durée de l’exécution
L’espace : ressources matérielles allouées

Le temps d’exécution de l’algorithme constitue la ressource la plus significative qu’il faut

quantifier
Complexité en temps
On tente de calculer la complexité de maniéré plus générale
Complexité asymptotique

Pour calculer la complexité en tant qu’approximation de la fonction du temps on utilise la

notation
Grand 0
Algorithme saisie

50
Variables
non : chaine de caractères
Début
Ecrire (‘vauller saisis votre non svp :’ ) 0(1) complexéte constante
Lire (nom)
Fin
Algorithme Salaire
Variable
nom,prenom,email : Chaîne de caractères
Début
Ecrire (‘ Veuillez saisir votre nom svp : ‘)
Lire (nom)
Ecrire (‘ Veuillez saisir votre prénom svp : ‘)
Lire (prenoml)
Ecrire (‘ Veuillez saisir votre email svp : ‘)
Lire (email)
Fin
Algorithme Saisie
3 opérations
Variable
O (3)
nom,prenom,email : Chaîne de caractères
Complexité constante
Début
Ecrire ( ‘ Veuillez saisir votre nom svp : ‘)
Lire (nom)
Ecrire (‘ Veuillez saisir votre prénom svp : ‘)
(prénom)
Ecrire (‘ Veuillez saisir votre email svp : ‘)
Lire (email)
Fin
Algorithme Saisie

51
Variable
nom,prenom,email : Chaîne de caractères
Début
3 opérations
Ecrire ( ‘ Veuillez saisir votre nom svp : ‘)
O (1)
Lire (nom)
Complexité constante
Ecrire (‘ Veuillez saisir votre prénom svp : ‘)
(prénom)
Ecrire (‘ Veuillez saisir votre email svp : ‘)
Lire (email)
Fin
Algorithme Recherche
Variable
Tableau tab () : Entier
elem,i : Entier
trouve : Booléen
Début
Ecrire (‘ Entrer un entier svp : ‘)
Lire (elem)
trouve ← Faux
pour i ← 0 à longueur (tab-1)
Si tab [ i ] = elem Alors
trouve ← Vrai
break
FinSi
FinPour
Si trouve=Vrai Alors
Ecrire (‘ L’ indice de l’élément recherché est : ‘ , i)
Sinon
Ecrire (‘ L’ ‘ élément recherché est introuvable ‘)

52
 FinSi
Fin
Algorithme Recherche
Variable
Tableau tab () : Entier
elem,i : Entier
trouve : Booléen
Début
Ecrire (‘ Entrer un entier svp : ‘)
Lire (elem)
trouve ← Faux
pour i ← 0 à longueur (tab-1)
Si tab [ i ] = elem Alors
trouve ← Vrai
break
FinSi
FinPour
Si trouve=Vrai Alors
Ecrire (‘ L’ indice de l’élément recherché est ‘ , i)
Sinon
Ecrire (‘ L’ ‘ élément recherché est introuvable ‘)
FinSi
Fin
Algorithme Recherche
Variable
Tableau tab () : Entier
elem,i : Entier
trouve : Booléen
Début

53
 Ecrire (‘ Entrer un entier svp : ‘)
Lire (elem)
trouve ← Faux
pour i ← 0 à longueur (tab-1) O (n)
Si tab [ i ] = elem Alors
Complexité linéaire
trouve ← Vrai
break
FinSi
FinPour
Si trouve=Vrai Alors
Ecrire (‘ L’ indice de l’élément recherché est ‘ , i)
Sinon
Ecrire (‘ L’ ‘ élément recherché est introuvable ‘)
FinSi
Fin

Algorithme Somme
Variable
Tableau tab1 (100) : Entier
Tableau tab2 (100) : Entier
i,S1,S2 : Entier
Début
S1 ← 0
Pour i ← 0 à 99 O (2n)
S1 ← S1+tab1[ i ] Complexité linéaire
FinPour
Ecrire (‘ La somme des éléments du tableau 1 vaut ‘, S1)
S2 ← 0
Pour i ← 0 à 99

54
 S2 ← S2+tab2[ i ]
FinPour
Ecrire (‘ La somme des élemnts du tableau 2 vaut ‘, S2)
Fin
Algorithme produit
Variable
Tableau tab1(100) : Entier
Tableau tab2(100) : Entier 𝑶 (𝒏𝟐 )
i,j : Entier
Complexité quadratique
Début
Pour i ← 0 à 99
Pour j ← 0 à 99
Ecrire (tab1[ i ] *tab2[ j ])
FinPour
FinPour
Fin
Algorithme Recherche_Dichotomique
Variable
Tableau tab() : Entier
elem, dab,fin,n : Entier
trouve : Booléen
Début
// initialisation et tri du tableau tab[ 0 ] ← 10, tab[ 1 ] ← 15
Ecrire (‘ Entier la valeur que vous recherceher : ‘)
Lire (elem)
dab ← 0
fin ← longueur(tab) -1
n ← (dab+fin) div 2
trouve ← FAUX

55
TrantQue dab <= fin
O ( log(n))
Si tab(n) = elem Alors
Complexité logarithmique
trouve ← VRAI
break
Sinon
Si tab[ n ] > elem Alors
fin ← m-1
Sinon
dab ← m+1
FinSi
FinSi
m ← (dab+fin) div 2
FinTanQue
Si trouve = VRAI Alors
Ecrire (‘ L’ ‘ indice de l’élément recherché est ‘ ,m)
Sinon
Ecrire (‘L’ ‘ élément recherché est introuvable’)
FinSi
Fin

𝑂(𝑛!)

𝑂(𝑛)3 𝑂(𝑛!)
Complexité cubique Complexité factorielle
…

56
 II. STRUCTUR DES DONNEE

Une structure de données est une manière spécifique d'organiser et de stocker des données
dans un ordinateur afin de faciliter leur accès et leur modification. Elle définit la relation entre
les données et les opérations qui peuvent être effectuées sur ces données. Le choix d'une
structure de données appropriée est crucial pour optimiser les performances d'un programme
Caractéristiques principales :
- Accès : Comment les données sont récupérées (par index, par clé, etc.).
- Insertion/Suppression : Facilité d'ajout ou de retrait d'éléments.
- Recherche : Efficacité pour trouver un élément spécifique.
- Espace mémoire : Quantité de mémoire utilisée pour stocker les données
Il reste à choisir :
- Où les éléments peuvent être insérés/extraits
- Comment leurs positions respectives sont déterminées

Aperçu
Idée intuitive
Semblable à une pile d’assiettes.
Politique : Dernier arrivé, premier servi (LIFO).

Méthodologie pour spécifier

 Lister les opérations autorisées avec leurs profils
(Parmi lesquelles on peut distinguer des constructeurs)

 Préciser les prés conditions de chaque opération

 Spécifier le comportement des différentes opérations au moyen
d’axiomes

Les axiomes :
 Ne doivent pas être contradictoires
 doivent permettre de prévoir le résultat de toute opération pour peu
Que les prés conditions soient respectés

II.1 Structures de données linéaires

Les structures de données linéaires organisent les éléments de manière séquentielle, où chaque
élément a un prédécesseur et un successeur (sauf pour le premier et le dernier élément). Elles
sont simples à implémenter et sont largement utilisées dans divers domaines.

a Notion de structure linéaire

57
On maintient une collection dans laquelle on peut insérer et extraire des
Éléments.
l = (a1, a2 . . . an) éventuellement vide

- Chaque élément est placé à une « position » dans la structure

- Tous les autres éléments sont « avant » ou bien « après »
- Pas d’autre hiérarchie entre les éléments

b Exemples détaillés :
 Tableaux :

Description Une collection d'éléments de même type, stockés dans des

emplacements mémoire contigus.
Avantages Accès rapide aux éléments via un index
Inconvénients Taille fixe, nécessitant un redimensionnement coûteux pour
ajouter des éléments

Exemple : Un tableau de nombres entiers `[10, 20, 30, 40]`.

 Listes chaînées :

Description Une séquence de nœuds, où chaque nœud contient une valeur et un

pointeur vers le nœud suivant.
Avantages Taille dynamique, insertion et suppression efficaces.
Inconvénients Accès séquentiel, moins efficace pour les recherches par index.

Exemple : Une liste chaînée représentant une playlist de musique.

 Piles (Stack) :
- Description : Une structure de type LIFO (Last In, First Out), où le dernier élément ajouté
est le premier à être retiré.
- Utilisations : Gestion des appels de fonctions, annulation d'actions dans un logiciel.
- Exemple : Une pile d'assiettes où la dernière assiette posée est la première à être retirée.

 Files (Queue)
- Description: Une structure de type FIFO (First In, First Out), où le premier élément ajouté
est le premier à être retiré.

58
 - Utilisations: Gestion des tâches dans un système d'exploitation, traitement des requêtes.
- Exemple : Une file d'attente à la caisse d'un supermarché.

II.2 Structures de données non linéaires

Les structures de données non linéaires n'organisent pas les éléments de manière séquentielle.
Elles permettent des relations plus complexes entre les éléments, ce qui les rend adaptées à
des problèmes plus sophistiqués.

Exemples détaillés :
Arbres :
- Description : Une structure hiérarchique composée de nœuds, où chaque nœud a un parent
(sauf la racine) et peut avoir plusieurs enfants.
- Types : Arbres binaires, arbres binaires de recherche, arbres AVL.
- Utilisations : Systèmes de fichiers, bases de données, algorithmes de tri.
- Exemple : Un arbre généalogique représentant une famille.

Graphes :
-Description : Une collection de nœuds (ou sommets) connectés par des arêtes. Les graphes
peuvent être dirigés ou non dirigés.

- Utilisations : Modélisation de réseaux sociaux, cartes routières, systèmes de

recommandation.
- Exemple: Un graphe représentant les connexions entre les utilisateurs d'un réseau social.

Tables de hachage (Hash Tables):

Description Une structure qui associe des clés à des valeurs en utilisant une fonction de
hachage.
Avantages Accès rapide aux données, insertion et suppression efficaces.
Inconvénients Risque de collisions, gestion complexe de la mémoire

Exemple : Un annuaire téléphonique où les noms sont associés aux numéros de téléphone.

59
CONCLUSION
Les structures de données sont des éléments fondamentaux en informatique, permettant de
gérer et d'organiser les données de manière efficace. Les structures de données linéaires,
comme les tableaux et les listes chaînées, sont idéales pour des problèmes simples et
séquentiels. En revanche, les structures de données non linéaires, comme les arbres et les
graphes, offrent une flexibilité accrue pour modéliser des relations complexes. Le choix de la
bonne structure de données dépend des besoins spécifiques du problème à résoudre, et une
compréhension approfondie de ces concepts est essentielle pour tout développeur ou ingénieur
en informatique.

60