Culture digitale : Sous module2

Algorithmique
Définition
Un algorithme est une suite finie et ordonnée d’instructions permettant de
résoudre un problème précis.
L’algorithmique est la discipline qui couvre l’ensemble des principes à
savoir pour développer un algorithme
Algorithme != programme informatique
On peut écrire un algorithme soit avec un
 Pseudocode : langage humain simple et universel
 Algonigrame : Un schéma structuré utilisé souvent dans la
pédagogie

Pseudocode
Pour déclarer une nouvelle variable : Variable nom-de-la-variable, type
Nom-de-la-variable 
donnée

Pour déclarer une variable sur Algobox, on clique sur le bouton Déclarer nouvelle variable.

On fait le choix du nom (tout en suivant les règles conventionnelles de nomenclature des variables)
puis on sélectionne le type de la variable.

Pour affecter une valeur à une variable, on clique sur Affecter valeur à une variable

Pour définir une fonction : Fonction nom-de-la-fonction (arguments : type)

Instructions
Fin
Il faut définir les fonctions avant le début du l’algorithme

Pour demander une information de chez l’utilisateur on peut utiliser

l’instruction Ecrire
Pour affecter une donnée proposée par l’utilisateur à une variable on
utilise Lire
Sur Algobox, on utilise les boutons Ajouter Afficher et Ajouter Lire pour écrire des messages,
afficher des résultats, et bien évidemment récupérer des données de l’utilisateur.

Pour déclarer une condition : Si condition alors

Instructions
Sinon
Instructions
FinSi

Sur Algobox, on peut commencer une condition en cliquant sur le bouton Ajouter Si…Alors.

On peut aussi traiter le cas de la condition contraire en cliquant l’option de Si non dans la boite de
dialogue

On distingue trois types de boucles :

1. Les boucles tant que…. Qui répètent les instructions tant que la
condition est vérifiée
2. Les boucles répéter .... jusqu'à : on y répète des instructions jusqu'à
ce qu'une
certaine condition soit réalisée.

3. Les boucles pour ou avec compteur : on y répète des instructions en

faisant évoluer
un compteur (variable particulière) entre une valeur initiale et une
valeur finale.
TantQue (condition)
//Pour chaque iteration on évalue la condition si elle est toujours Vrai
// Le nb d’iterations n’est pas connu. Il depend de la Valeur de
condition
// Une des instructions doit absolument changer la Valeur de la
condition sinon le
programme tourne indéfiniment
FinTantQue
Répéter
//la boucle Répéter//Jusqu’a s’éxécute au moins une fois et s’arête
quand la condition
deviant Vrai
// Le nb d’iterations n’est pas connu. Il depend de la Valeur de
condition
 // Une des instructions doit absolument changer la Valeur de la
condition sinon le
programme tourne indéfiniment
Jusqu’à (condition)
Pour compteur = initiale à finale pas valeur du pas
//Le nb d’itérations est connu bien avant le début de la boucle
//La variable compteur est en général de type entier (à déclarer
auparavant)
// Le Pas est un entier positif ou négatif. Peut ne pas être utilisé car
par défaut = 1.
// Initiale et Finale peuvent être des valeurs, variables définies..
FinPour

Afin d’insérer une boucle dans AlgoBox, on utilise les boutons Ajouter Pour…DE….A et Ajouter
Tant…que

Un tableau est une structure de donnée qui permet de stocker les données
Syntaxe de création est le suivant
Variable nom-de-tableau[dimension] : tableau de type
Exercices
Algorithme : Moyenne
Variable Tableau-de-notes[2] : nombres
Variable i :entier
Début
Tableau-de-note[2]0
Pour i=1 à 5
Ecrire (« Veuillez saisir la note numéro »,i)
Lire(Tableau-de-notes[1])
Tant que Tableau-de-notes[1]<0 ou Tableau-de-
notes[1]>20
Ecrire (« On a identifié une erreur. Veuillez vérifier La
note »)
FinTantque
Tableau-de-notes[2] Tableau-de-note[2]+ Tableau-
de-note[1] )
Fin Si
FinPour
 Ecrire(« Votre moyenne est » ,Tableau-de-notes[2]/5
Fin
Algorithme : Saisi-de-notes
Variables Tableau-de-notes[20,4] : tableaux des entiers
Variable i,j : entier
Début
Pour i = 1 à 4
Pour j=1 à 20
Ecrire (« Saisir la note de la matière »,i, « pour l’élève »,j)
Lire Tableau-de-notes[j,i]
FinPour
FinPour
Fin

Un tableau dynamique est un tableau dont la taille dépend est définie lors
de l’exécution. La syntaxe de déclaration d’un tableau dynamique est le
suivant :
Variable nom-de-tableau[] : tableau de type

Pour supprimer un élément de ce tableau on peut utiliser :

Supprimer nom-tableau[indice-élément]
Pour récupérer la longueur d’un tableau : longueur(nom-tableau)

La structuration des données dans un tableau est une condition nécessaire

pour les bien manipuler. On parle précisément de la recherche et du tri.
La méthode intuitive à suivre lors de la recherche est de parcourir tout le
tableau jusqu’à ce qu’on trouve la valeur recherchée. Or une telle
approche n’est point efficace vu sa complexité.
Ainsi pour trouver un élément plus rapidement on applique l’une des
méthodes suivantes :
Méthode de dichotomie
La condition pour utiliser cette méthode est d’avoir un tableau t trié par
ordre croissant.
Si on cherche un élément e de t ; on commence par le comparer au milieu
m de t :
 Si e=m, c’est gagné.
  Si e<m, on réapplique la méthode sur la moitié gauche
 Si e>m, on réapplique la méthode sur la partie droite
Voici l’algorithme de la dichotomie :
Algorithme dichotomie
Variables Trouve : booléen
i,j,e : entiers
TAB [100] : tableau des entiers
Début
Ecrie (« Quelle valeur cherchez-vous ? »)
Lire e
Trouve  faux
i0
j longueur(Tab)
Tant que i<=j et trouve=faux faire
Si TAB[(i+j) /2] = e alors
Trouve  vrai
Sinon
Si TAB[(i+j) /2] < e alors
i (i+j)/2 + 1
Sinon
j (i+j)/2 - 1
Finsi
FinSi
FinTantque
Fin
Méthode d’interpolation
C’est une amélioration de la dichotomie, dans laquelle on ne coupe pas le
tableau du milieu mais on cherche à deviner sa position probable en
tenant compte de sa valeur par rapport aux extrêmes.
Les conditions pour appliquer cette méthode est d’avoir un tableau trié par
ordre croissant avec des valeurs uniformes.
• Droite-gauche: la taille de la portion actuelle de tableau
• Elem_cher – tab[gauche]: la distance entre la valeur de l’élément
cherché et la plus petite valeur actuelle
• Tab[droite]-tab[gauche]: écart total des valeurs dans la portion
actuelle
• Le tout donne une coefficient de positionnement relatif dans la portion
[gauche..droite]

Voici l’algorithme de l’interpolation :

Tant que (g ≤ d ET val_Cher ≥ Tab[gauche] ET (val_Cher ≤ Tab[droite et

trouve=faux)

pos←g+((val_Cher-Tab[g])*(d-g))/(Tab[d]-Tab[g])

Si Tab[pos] = val_Cher alors

trouve ← vrai
Sinon
Si val_Cher > Tab[pos] alors
g ← pos + 1
Sinon
d ← pos - 1
FinSi
FinSi
FinTantQue
Comme déjà annoncé ces méthodes ne fonctionnent que lorsque le
tableau est trié par ordre croissant ainsi pour s’assurer de ça on fait appel

à l’algorithme suivant
 Et alors si le tableau n’est pas trié, on le fait nous-mêmes à travers divers
méthodes :
Tri à bulle : en place et stable

Le tri à bulles (ou bubble sort en anglais) est un algorithme de tri simple
mais peu efficace. Il fonctionne en comparant et en échangeant des
éléments adjacents dans un tableau (ou une liste) jusqu'à ce que tous
les éléments soient triés dans l'ordre croissant (ou décroissant).

Principe du tri à bulles :

1. Parcours du tableau : On compare les éléments deux à deux, et on les

échange s'ils ne sont pas dans l'ordre.
2. Répétition : On répète ce processus jusqu'à ce qu'aucun échange ne soit
nécessaire (le tableau est trié).
3. Effet "bulles" : Les plus grands éléments "remontent" vers la fin du
tableau, comme des bulles qui montent à la surface.

Voici le pseudo-code correspondant :

Variables i,j,temp: entiers
Tab[6]:tableau des entiers <- [8,5,10,11,2,0]
Début
Pour i de longueur(tab)-2 à 1 pas -1
Pour j de 0 a i
Si (tab[j] >tab[j+1) alors
Temp <- tab[j]
Tab[j] <- tab[j+1]
Tab[j+1] <- temp
FinSi
FinPour
FinPour
Fin
Tri par sélection : en place et stable/non-stable
• Tri par sélection (selection sort) : consiste à parcourir le tableau
pour trouver l’élément le plus petit (ou le plus grand), puis à
l’échanger avec l’élément en première position (ou dernière
position). Ensuite, on recommence le processus sur le sous-
tableau restant, c’est-à-dire à partir de la position suivante,
jusqu’à ce que tout le tableau soit trié
Voici l’algorithme utilisé pour cette méthode :
Variables i, j, temp, indice_pg :entiers
tab[10]: tableau des entiers
Début
i<- longueur(tab)-1 (on commence par la dernière case)
Tantque (i>0) (On boucle tant qu’on n’a pas placé tous les plus grands à
la fin)
Indice_pg<-0
Pour j de 0 à i
Si tab[j]>tab[indice_pg] alore
Indice_pg <-j
FinSi
FinPour
Temp <- tab[indice_pg]
Tab[indice_pg] <- tab[i]
Tab[i] <- temp
i <- i-1
FinTantque
Fin
Tri par insertion : en place et stable

Initialisation : Le tableau est divisé en deux parties : une partie triée (à

gauche) et une partie non triée (à droite).

Insertion : On prend un élément de la partie non triée et on l'insère à sa

place correcte dans la partie triée, en décalant les éléments plus grands
vers la droite.

Répétition : On répète le processus jusqu’à ce que tout le tableau soit

trié.

Variables : Tab[0..n-1] : tableau d’entiers

i, j, x : entiers
Début
Pour i de 1 à n - 1
x ← Tab[i] // élément à insérer
j ← i – 1 // Décaler les éléments plus grands
vers la droite
Tant que (j ≥ 0 ET Tab[j] > x)
Tab[j + 1] ← Tab[j]
j←j-1
FinTantQue // Insérer l'élément à sa place
Tab[j + 1] ← x
 FinPour
Fin

Le tri peut être en place s’il ne demande pas de mémoire supplémentaire ou

bien non en place si l’opposé. De même, on dit que le tri est stable s’il
n’échange pas l’ordre des éléments égaux et non-stable s’il le fait.