Rapport sur
l’algorithmique
Proposer à : M. Benetachfine Ilyass
Réaliser par : Aicha Idaani
Filière : Gi 21
Sommaire :
[Link]
[Link] structures conditionnelles
[Link] structures répétitives
IV. Les tableaux et les matrices
V. Les fonctions et les procédures
VI. Les tris
I. Introduction :
Définition :
L'algorithmique : est un ensemble d'instructions logiques appliquées à
des données pour obtenir un résultat spécifique ou résoudre un
problème.
Variable : est un espace mémoire dans l’ordinateur qui passe un
identifient est un type
Type : soit réel, entier, booléen, caractère
Identifient : le nom de variable
Déclaration : réservation d’un espace dans la mémoire de l’ordinateur et
permet d’informer l’ordinateur l’existence d’une donnée
Affectation : l’affectation est une opération qui consiste à attribuer à une
valeur
L’instruction écrire : permet d’afficher la valeur d’une expression sur un
périphérique de sortie (écran
L’instruction lire : permet de demander à l’utilisateur de fournir des
informations, chaque information donnée par l’utilisateur est stockée
dans une variable
Les étapes d’un algorithme :
Analyse Pseudocode Trace
Compréhension du Rédaction d'une Exécution manuelle ou
problème, identification représentation textuelle avec des exemples de
des données d'entrée et des étapes de données pour vérifier le
des résultats attendus. l'algorithme, sans fonctionnement et la
syntaxe de logique de l'algorithme.
programmation
spécifique.
Expression arithmétique : +, *, -, \, %
Expression de comparaison : <,>
II. Les Structures conditionnelles
Les structures conditionnelles : Sont des structures dont les instructions sont
exécutées selon les raiponces des conditions
Structure conditionnelle (si)
Structure conditionnelle (selon)
III. Les structures répétitives
Les structures répétitives : sont des boucles permet d’exécuter plusieurs
fois une séquence d’instructions
La boucle Pour : permet d’exécuter une séquence d’instruction un nombre
de fois connue fixe là l’avance. Elle utilise une variable indice de contrôle d
itérations caractériser par :
Sa valeur initiale, Sa valeur finale et Son pas de variation
Tant que : cette boucle permet de répéter un bloc d’instruction Tant
qu’une condition est vraie
La vérification de la condition s’effectuer avant l’exécution des instructions
celle-ci sont peuvent donc ne jamais exécutées
Répéter jusqu’à : cette boucle permet de répéter un bloc d’instruction tan
qu’une condition soit vérifiée
La vérification de la condition s effectuer après l’exécution des instructions
celle-ci sont donc exécutées au moins une fois
IV. Les tableaux et les matrices
o Un tableau : est une structure des données qui a bien un ensemble
d’espace mémoire consécutif séquentiel qui possède le même type, un
identifient, et une taille
Afficher Les élément d’un tableau :
Variable
Réel : note[1…..n]
Entier : i
Début
Pour i de 1 a n faire
Ecrire (note)
Fin pour
Fin
Remplir un tableau :
Variable
Réel : note[1…..n]
Entier : i
Début
Pour i de 1 a n faire
Ecrire (donner note [i])
Lire (note[i])
Fin pour
Fin
o Les matrices : un tableau de deux dimensions, le première indice
représente le numéro de linge, le deuxième indice représente le numéro
de colonne
Affichage des éléments d’une matrice :
Variable
Réel : note[1…..n][1…..m]
Entier : i, j
Début
Pour i de 1 a n faire
Pour j de 1 a m faire
Ecrire (mat[i][j])
Fin pour
Fin pour
Fin
Remplir une matrice :
Variable
Réel : note[1…..n][1…..m]
Entier : i, j
Début
Pour i de 1 a n faire
Pour j de 1 a m faire
Ecrire (mat[ i ][, j , ])
Lire (mat[i][j])
Fin pour
Fin pour
Fin
V. Les fonctions et les procédures
Une fonction : est une suite d’instruction regroupées sous un nom, elle
prend en entrée de paramètres et retourne un résultat
Une procédure : est une suite d’instruction regroupées sous un nom, elle
prend en entrée des paramètres mais qui ne retourne rien
VI. Les tris
Le tri par sélection
Variable
Entier : T[1…n], i, j, min, c
Début
Pour i de 1 à n – 1
min ← T[i]
Pour j de i + 1 à n
Si T[j] < min alors
min ← T[j]
Fin Si
Fin Pour
Si min < T[i] alors
c ← T[i]
T[i] ← min
min ← c
Fin Si
Fin Pour
Fin
Exemple
T = [5, 3, 8, 1, 2]
1er passage (i = 1)
min ← T[1] = 5
Parcours pour j :
j = 2: T[2] = 3 (min devient 3)
j = 3: T[3] = 8 (min reste 3)
j = 4: T[4] = 1 (min devient 1)
j = 5: T[5] = 2 (min reste 1)
Après la boucle, on a min = 1 et min < T[1] (1 < 5).
Donc, on échange :
c = T[1] = 5
T[1] = 1
T[4] = 5
État du tableau après le 1er passage : T = [1, 3, 8, 5, 2]
2e passage (i = 2)
min ← T[2] = 3
Parcours pour j :
j = 3: T[3] = 8 (min reste 3)
j = 4: T[4] = 5 (min reste 3)
j = 5: T[5] = 2 (min devient 2)
min < T[2] (2 < 3). On échange :
c = T[2] = 3
T[2] = 2
T[5] = 3
État du tableau après le 2e passage : T = [1, 2, 8, 5, 3]
Après toutes les itérations, le tableau est trié :
T = [1, 2, 3, 5, 8]
Sa complexité :
Meilleur cas : O(n2)
Pire cas : O(n2)
Tri par insertion
Variable
Entier : T[1…n], i, j, x
Début
Pour i de 2 à n faire
x ← T[i]
j←i
Tant que (j >= 1 et T[j - 1] > x) faire
T[j] ← T[j - 1]
j←j-1
Fin Tant Que
T[j] ← x
Fin Pour
Fin
Exemple
T = [5, 2, 9, 1, 5, 6]
1er passage (i = 2)
x ← T[2] = 2
j←2
Tant que (j >= 1 et T[j - 1] > x):
T[2] = T[1] → T = [5, 5, 9, 1, 5, 6]
j ← 1 (car 2 > 1, continuer)
T[1] = T[0] → (n'est pas exécuté, car T[0] n'existe pas)
On sort de la boucle.
T[1] ← 2 → T = [2, 5, 9, 1, 5, 6]
2e passage (i = 3)
x ← T[3] = 9
j←3
Tant que (j >= 1 et T[j - 1] > x):
T[3] = T[2] → (n'est pas exécuté, car 5 < 9)
On sort de la boucle.
T[2] ← 9 → T = [2, 5, 9, 1, 5, 6]
Après l'exécution complète de l'algorithme, le tableau est trié :T = [1, 2, 5, 5,
6, 9]
Sa complexité :
Meilleur cas : O(n)
Pire cas : O(n2)
Tri par bulles
Variable
Entier : tab[1…n], j ,c
Booléen : Test
Début
Répéter
Test ← Vrai
Pour j allant de n à 2 faire
Si tab[j] < tab[j - 1] Alors
c ← tab[j]
tab[j] ← tab[j-1]
tab[j-1] ← c
Test ← Faux
Fin Si
Fin Pour
Jusqu’à (Test = Vrai)
Fin
Exemple
Test est initialisé à Vrai.
Parcours du tableau de j = 5 à j = 1 :
1. j = 5 : Compare tab[5] (2) avec tab[4] (1) → Pas d'échange.
2. j = 4 : Compare tab[4] (1) avec tab[3] (8) → Échange : tab = [5, 3, 1, 8, 2],
Test devient Faux.
3. j = 3 : Compare tab[3] (1) avec tab[2] (3) → Échange : tab = [5, 1, 3, 8, 2],
Test reste Faux.
4. j = 2 : Compare tab[2] (1) avec tab[1] (5) → Échange : tab = [1, 5, 3, 8, 2],
Test reste Faux.
Après plusieurs itérations, le tableau sera finalement trié :
tab = [1, 2, 3, 5, 8]
sa complexité :
Meilleur cas : O(n)
Pire cas : O(n²)
Tri rapide
Fonction Partition(T, p :entier, r :entier )
Variable :
Entier : c
début
pivot ← T[r]
i←p-1
Pour j de p à r - 1 faire
Si T[j] ≤ pivot Alors
i←i+1
c← T[i]
T[i] ← t[j]
T[j] ← c
Fin Si
Fin Pour
c← t[i+1]
T[i+1] ← T[i]
T[i] ←c
Retourner i + 1
Fin Fonction
Fonction Tri-rapide(T, p : entier, r :entier )
Entier : q
début
Si p < r Alors
q ← Partition(T, p, r)
Tri-rapide(T, p, q - 1)
Tri-rapide(T, q + 1, r)
Fin Si
Fin Fonction
Exemple
Tableau[ 4, 3, 2]
Étape 1 : Premier appel à Tri-rapide
Nous appelons Tri-rapide(4, 3, 2).
[Link]
Choisissons 2 comme pivot.
Initialisons i = -1.
Parcours des éléments :
4 : 4 > 2 (pas d'échange)
3 : 3 > 2 (pas d'échange)
À la fin du parcours, nous échangeons le pivot 2 avec 4 :
Résultat après partition : 2, 3, 4
Étape 2 : Appels récursifs
Nous avons maintenant deux sous-ensembles à trier :
Tri-rapide( ) (aucun élément à gauche de 2)
Tri-rapide(3, 4) (à droite)
Sous-ensemble : Tri-rapide(3, 4)
1. Partition
Choisissons 4 comme pivot.
Initialisons i = 2.
Parcours des éléments :
3 : 3 < 4 → i = 3, pas d'échange
Finalement, nous échangeons le pivot 4 avec 4 (pas de changement) :
Résultat après partition : 3, 4
Étape 3 : Nouveaux appels récursifs
Tri-rapide(3) (ne fait rien)
Tri-rapide(4) (ne fait rien)
Résultat final
Après avoir appliqué l'algorithme de tri rapide, nous avons trié les éléments :
Éléments triés : 2, 3, 4
Sa complexité :
Meilleur cas : O(nlog(n))
Pire cas : O(n2)
tri par fusion
procédure fusion(entier[] :tab, entier[] :tmp, entier: x, entier: y, entier: z)
variable
entier k,i,j
Début
i <-x ;
j <- y + 1;
pour k de a à z faire
si ((j > z) ou (i <= y et tab[i] < tab[j])) alors
tmp[k] <- tab[i];
i <- i + 1;
Si non
tmp[k] <- tab[j];
j <- j + 1;
fin si
fin pour
pour k de x à z faire
tab[k] <- tmp[k];
fin pour
fin procédure
Procédure tri_fusion(entier[] : tab, entier : a, entier : c, entier: b)
début
Si a < c alors
b<- (a + c) / 2
tri_fusion(tab, a, b)
tri_fusion(tab, b + 1, c)
fusion(tab, a, b, c)
Fin Si
Fin Procédure
Exemple
[15, 3, 9, 6, 12, 5, 1].
Étapes du Tri par Fusion
Diviser :
[15, 3, 9, 6, 12, 5, 1] → [15, 3, 9] et [6, 12, 5, 1]
[15, 3, 9] → [15] et [3, 9]
[3, 9] → [3] et [9]
[6, 12, 5, 1] → [6, 12] et [5, 1]
[6, 12] → [6] et [12]
[5, 1] → [5] et [1]
Fusionner :
Fusionner [3] et [9] → [3, 9]
Fusionner [15] et [3, 9] → [3, 9, 15]
Fusionner [6] et [12] → [6, 12]
Fusionner [5] et [1] → [1, 5]
Fusionner [6, 12] et [1, 5] → [1, 5, 6, 12]
Fusion finale :
Fusionner [3, 9, 15] et [1, 5, 6, 12] → [1, 3, 5, 6, 9, 12, 15]
Résultat final :
Le tableau trié est [1, 3, 5, 6, 9, 12, 15].
Sa complexité
Meilleur cas : O(nlogn)
Pire cas : O(nlogn)
discussion :
Le tri par fusion est souvent préféré pour sa complexité stable de
(𝑛log𝑛)O(nlogn) et sa stabilité, en faisant un excellent choix pour de grands
ensembles de données.