Algorithmique
ALGORITHME
Définition
Suite de raisonnements ou d'opérations qui fournit la solution de
certains problèmes.
Objectifs
- Un algorithme sert à transmettre un savoir faire.
- Il décrit les étapes à suivre pour réaliser un travail.
1
Formalisme
• Un algorithme doit être lisible et compréhensible par plusieurs personnes.
• Il doit donc suivre des règles. Il est composé d'une entête et d'un corps.
• L'entête comprend :
- Nom : le nom de l'algorithme
- Partie déclarative (variable, constante, structure)
- Rôle : ce que fait l'algorithme
- Données : les données fournies à l'algorithme
- Résultat : ce que l'on obtient à la fin du traitement
- Principe : le principe utilisé dans l'algorithme
• Le corps :
- il est délimité par les mots clés début et fin.
2
Formalisme
• Exemple d'algorithme :
Nom : AddDeuxEntiers.
Rôle : additionner deux entier et mémoriser le résultat
Données : les valeurs à additionner.
Résultat : la somme des deux valeurs.
Principe : Additionner deux entiers a et b et mettre le résultat dans c.
début
c←a+b
fin
Lexique :
a : entier
b : entier 3
c : entier
Les variables
• Une variable est une entité qui contient une information, elle possède :
• Un nom, on parle d’identifiant
• Une valeur
• Un type qui caractérise l’ensemble des valeurs que peut prendre la variable
• L’ensemble des variables est stocké dans la mémoire de l’ordinateur
4
Les variables
• Type de variable
• Entier pour manipuler des entiers
• Réel pour manipuler des nombres réels
• Booléen pour manipuler des valeurs booléennes
• Caractère pour manipuler des caractères alphabétiques et numériques
• Chaîne pour manipuler des chaînes de caractères permettant de représenter
des mots ou des phrases.
5
Les constantes
• Est un objet contenant une donnée non modifiable dans un programme.
• Elle se déclare à l’aide du mot clé const.
• Exemple : const tva⃪0.1925; pi ⃪ 3.14;
6
Opérateur, opérande et expression
• Un opérateur est un symbole d’opération qui permet d’agir sur des
variables ou de faire des “calculs”
• Une opérande est une entité (variable, constante ou expression) utilisée
par un opérateur
• Une expression est une combinaison d’opérateur(s) et d’opérande(s),
elle est évaluée durant l’exécution de l’algorithme, et possède une
valeur (son interprétation) et un type
7
Les opérateurs sur les numériques
• On retrouve tout naturellemment +, -, *, /
• Avec en plus pour les entiers div et mod, qui permettent respectivement de calculer une
division entière et le reste de cette division,
par exemple :
11 div 2 vaut 5
11 mod 2 vaut 1
• L’opérateur d’égalité (=)
• L’opérateur d’inégalité (≠)
• Et pour les types possédant un ordre les opérateurs de comparaison
<, ≤, >, ≥
8
Variables – Exercices d’applications
Exercice 1.1
Quelles seront les valeurs des variables A, B et C après exécution des
instructions suivantes ?
Variables A, B de entier ; Variables A, B, C de entier ;
Début Début
A←1; A←5;
B←A+3 ; B←3;
A←3; C←A+B;
Fin A←2;
C ←B –A;
Exercice 1.2 Fin
Que produit l’algorithme suivant ?
Var A, B, C de caractères ;
Début
A ← "423" ;
B ← "12" ;
9
C ←A&B ;
Fin
Les entrées / sorties
• Un algorithme peut avoir des interactions avec l’utilisateur
• Il peut demander à l’utilisateur de saisir une information afin de la stocker dans une
variable
Exemple :
lire(quantite);
Récupère la valeur de la quantité et stocke dans la variable quantite.
• Il peut afficher un résultat (du texte ou le contenu d’une variable)
Exemple :
ecrire(liste d'expressions);
afficher(x, y+2, "bonjour") ;
10
Les entrées / sorties – Exercices d’applications
Exercice 2.1
Ecrire un programme qui demande un nombre à l’utilisateur, puis qui calcule
et affiche le carré de ce nombre.
Exercice 2.2
Ecrire un programme qui demande l’année de naissance de l’utilisateur, puis
qui calcule son âge.
Exercice 2.3
Ecrire un programme qui demande à l’utilisateur son nom, sa filière et son
niveau, puis qui affiche : Bonjour, suivi du nom, filière et niveau de
l’utilisateur.
Par exemple si l’utilisateur entre Ali, GIM et 1, le programme affichera
’’ Bonjour Ali, vous êtes en GIM 1’’
11
Boucles Instruction conditionnelle
• L’instruction si alors sinon permet de conditionner l’exécution d’un algorithme à
la valeur d’une expression booléenne. La syntaxe est la suivante :
si expression booléenne alors
suite d’instructions exécutées si l’expression est vrai
sinon
suite d’instructions exécutées si l’expression est fausse
finsi
◆ La deuxième partie de l’instruction est optionnelle. La syntaxe est la
suivante :
si expression booléenne alors
suite d’instructions exécutées si l’expression est vrai 12
finsi
Instruction conditionnelle
• Exemple
Algorithme ValeurAbs ;
Variables valeur, valeurabsolue : entier ;
Rôle : Calcule la valeur absolue d’un entier
Données : La valeur à calculer (valeur)
Résultat : La valeur Absolue (valeurabsolue)
Principe : Si valeur < 0, on la multiplie par -1
début
si valeur ≥ 0 alors
valeurabsolue ← valeur ;
sinon
valeurabsolue ← valeur * -1 ;
finsi
fin 13
L'instruction cas
• Lorsque l’on doit comparer une même variable avec plusieurs valeurs, comme
par exemple :
si a=1 alors
faire une chose
sinon
si a=2 alors
faire une autre chose
sinon
si a=4 alors
faire une autre chose
sinon
...
finsi
finsi
finsi 14
• On peut remplacer cette suite de si par l’instruction cas
L'instruction cas
• Sa syntaxe est :
cas où v vaut
v1 : action1
v2 : action2
...
vn : actionn
autre : action autre
fincas
v1,. . . ,vn sont des constantes de type scalaire (entier, caractère,…)
action i est exécutée si v = vi (on quitte ensuite l’instruction cas)
action autre est exécutée si quelque soit i, v ≠ vi
15
L'instruction cas
Exemple : écrire un algorithme qui associe les chiffres 1 à 7 au 7 jours de
la semaine:
Algorithme jourSemaine;
Var jour : chaine[10];
Debut
cas ou jour vaut
1 : jour ⃪ ‘’lundi’’ ;
2 : jour ⃪ ‘mardi’’ ;
3 : jour ⃪ ‘mercredi’’ ;
4 : jour ⃪ ‘jeudi’’ ;
5 : jour ⃪ ‘vendredi’’ ;
6 : jour ⃪ ‘samedi’’ ;
7 : jour ⃪ ‘dimanche’’ ;
autre : ecrire (‘’ Pas un jour de la semaine ’’); 16
fincas
fin
Les itérations
• Il arrive souvent dans un algorithme qu'une même action soit répétée plusieurs
fois, avec éventuellement quelques variantes.
Il est alors fastidieux d'écrire un algorithme qui contient de nombreuses fois la
même instruction. De plus, ce nombre peut dépendre du déroulement de
l'algorithme.
Il est alors impossible de savoir à l'avance combien de fois la même instruction
doit être décrite.
Pour gérer ces cas, on fait appel à des instructions en boucle qui ont pour effet de
répéter plusieurs fois une même instruction.
Deux formes existent :
- La première, si le nombre de répétitions est connu avant l'exécution de
l'instruction de répétition,
- La seconde s'il n'est pas connu.
L'exécution de la liste des instructions se nomme itération. 17
Répétitions inconditionnelles
• Il est fréquent que le nombre de répétitions soit connu à l'avance, et que
l'on ait besoin d'utiliser le numéro de l'itération afin d'effectuer des calculs
ou des tests. Le mécanisme permettant cela est la boucle Pour.
• Forme de la boucle Pour est :
Pour variable de valeur initiale à valeur finale pas valeurdupas faire
liste d'instructions
fpour
Exemple : Un algorithme qui affiche le dix premiers nombre partant de 1.
Algirithme lesDixNombres ;
Var i : entier;
Debut
Pour i ← 1 à 10 pas de 1 faire
Ecrire (i);
Fpour 18
Fin
Les répétitions conditionnelles
• L'utilisation d'une "boucle pour" nécessite de connaître à l'avance le
nombre d'itérations désiré, c'est-à-dire la valeur finale du compteur. Dans
beaucoup de cas, on souhaite répéter une instruction tant qu'une certaine
condition est remplie, alors qu'il est à priori impossible de savoir à
l'avance au bout de combien d'itérations cette condition cessera d'être
satisfaite. Dans ce cas, on a deux possibilités :
- La boucle Tant que
- La boucle Répéter jusqu'à
• Syntaxe de la boucle Tant que :
tant que condition faire
liste d'instructions
fintantque
• Exemple
Un utilisateur peut construire des rectangles de taille quelconque,
à condition que les largeurs qu'il saisit soient supérieures à 1 pixel. 19
Les répétitions conditionnelles
Algorithme : saisirLargeurRectangle ;
Variable largeur : entier ;
Rôle : Vérification validité largeur saisie
Données : La largeur
Principe : Tant que la largeur est < 1, on demande de resaisir la largeur
début
écrire ("indiquez la largeur du rectangle :");
lire(largeur) ;
tant que largeur < 1 faire
écrire ("erreur : indiquez une valeur strictement positive");
écrire ("indiquez la largeur du rectangle :");
lire(largeur); 20
fintantque
fin
Les répétitions conditionnelles
• Cette instruction a une condition de poursuite dont la valeur est de type
booléen et une liste d'instructions qui est répétée si la valeur de la
condition de poursuite est vraie : la liste d'instructions est répétée autant
de fois que la condition de poursuite a la valeur vraie.
• Syntaxe de la boucle Répéter jusqu'à :
Répéter
liste d'instructions
jusqu'à condition vrai
La séquence d'instructions est exécutée au moins une fois et jusqu'à ce
que l'expression soit vraie. Dès que la condition est vrai, la répétitivité
s'arrête.
21
Les répétitions conditionnelles
Algorithme : saisirLargeurRectangle ;
Variable largeur : entier;
Rôle : Vérification validité largeur saisie
Données : La largeur
Principe : Tant que la largeur est < 1, on demande de resaisir la largeur
début
Répéter
écrire ("indiquez la largeur du rectangle :") ;
lire(largeur) ;
si largeur < 1 alors
écrire ("erreur : indiquez une valeur strictement
positive") ;
finsi
jusqu'à largeur >= 1 22
fin
Les répétitions conditionnelles
• Différences entre les boucles Tant que et Répéter jusqu’à :
- La séquence d'instructions est exécuter au moins une fois dans la
boucle Répéter jusqu'à, alors qu'elle peut ne pas être exécuter
dans le cas du Tant que.
- Dans les deux cas, la séquence d'instructions doit
nécessairement faire évoluer la condition, faute de quoi on
obtient une boucle infinie.
23
Les tableaux
• Lorsque les données sont nombreuses et de même type, afin d'éviter de
multiplier le nombre des variables, on les regroupe dans un tableau
• Le type d'un tableau précise le type (commun) de tous les éléments.
• Syntaxe :
Nomtableau : Tableau[borne_inf ... borne_sup] le type
• En général, nous choisirons toujours la valeur 0 pour la borne inférieure
dans le but de faciliter la traduction de l'algorithme vers les autres langages
(C, Java, ...). Pour un tableau de 10 entiers, on aura :
tab : tableau[0..9] de entier
24
Les tableaux
• Les tableaux à une dimension ou vecteurs
0 1 2 3 4 5 6 7 8 9
45 54 1 -56 22 134 49 12 90 -26
• Ce tableau est de longueur 10, car il contient 10 emplacements.
• Chacun des dix nombres du tableau est repéré par son rang, appelé
indice
• Pour accéder à un élément du tableau, il suffit de préciser entre
crochets l'indice de la case contenant cet élément.
Pour accéder au 5ème élément (22), on écrit : Tab[4]
25
Les tableaux
• Les instructions de lecture, écriture et affectation s'appliquent aux
tableaux comme aux variables.
x ← Tab[0]
La variable x prend la valeur du premier élément du tableau, c'est à dire :
45
Tab[6] ← 43
Cette instruction a modifiée le contenu du tableau
26
Les tableaux
Dans l'exemple suivant, le programme initialise un à un tous les éléments
d'un tableau de n éléments :
InitTableau
début
pour i de 0 à n-1 faire
tab[i] ← 0
fpour
fin
Variables :
- i : entier ; (indice d'itération)
- n : entier ; (taille du tableau)
- tab : tableau [0..n-1] de entier 27
Les tableaux
• Les tableaux à deux dimensions ou matrices
Lorsque les données sont nombreuses et de même nature, mais
dépendent de deux critères différents, elles sont rangées dans un
tableau à deux entrées.
0 1 2 3 4 5 6
0 12 28 44 2 76 77 32
1 23 36 51 11 38 54 25
2 43 21 55 67 83 41 69
Ce tableau a 3 lignes et 7 colonnes. Les éléments du tableau sont
repérés par leur numéro de ligne et leur numéro de colonne.
28
Tab[1, 4] = 38
Les tableaux
• La variable T[L, C] s'appelle l'élément d'indice L et C du tableau T.
T[0, 0] T[0, 1] T[0, 2] T[0, 3] T[0, 4]
T[1, 0] T[1, 1] T[1, 2] T[1, 3] T[1, 4]
T[2, 0] T[2, 1] T[2, 2] T[2, 3] T[2, 4]
Tableau T à 3 lignes et 5 colonnes.
• Les tableaux peuvent avoir n dimensions.
29
Les procédures et les fonctions
Une application, surtout si elle est longue, a toutes les chances de devoir
procéder aux mêmes traitements, ou à des traitements similaires, à plusieurs
endroits de son déroulement. Par exemple, la saisie d’une réponse par oui ou par
non (et le contrôle qu’elle implique), peuvent être répétés dix fois à des
moments différents de la même application, pour dix questions différentes. Pour
cela,
- Répéter le code correspondant autant de fois que nécessaire.
- La structure d'un programme écrit de cette manière est lourde.
Solution:
- Séparer ce traitement du corps du programme et à regrouper les instructions
qui le composent en un module séparé.
- La lisibilité est assurée ; le programme devient modulaire.
30
Les procédures et les fonctions
Les procédures
La procédure est un sous programme qui ne retourne pas de résultat.
Elle comporte également :
▪ L’entête
▪ Une partie déclarative
▪ Un corps
Déclaration d’une procédure
La syntaxe est la suivante :
Procédure nom de la procédure(paramètre 1:type1 … paramètre n:typen );
Déclaration des constantes locales
Déclaration des variables locales
Début
Description des actions à effectuer par la procédure
FinProc
31
Les procédures et les fonctions
32
Les procédures et les fonctions
Les fonctions
La fonction est un sous programme qui retourne résultat.
Elle comporte également :
▪ L’entête
▪ Une partie déclarative
▪ Un corps
Déclaration d’une fonction
La syntaxe est la suivante :
fonction Nomfonction(paramètre 1:type1 … paramètre n:typen ) :type de retour;
Déclaration des constantes locales
Déclaration des variables locales
Début
Description des actions à effectuer par la procédure
Retourne(paramètre de retour)
33
FinFonc
Les procédures et les fonctions
34
Les procédures et les fonctions
Différence entre fonction et procédure :
Fonction Procédure
Retourne un résultat Ne retourne pas un résultat
A un type de retour N’a pas un type de retour
On peut pas écrire et lire On peut écrire et lire
dans le corps dans le corps
35
Les procédures et les fonctions
Exercice 3.1
Écrivez une fonction qui renvoie la somme de cinq nombres fournis en
argument.
Exercice 3.2
Ecrire une fonction factoriel qui renvoie le factoriel d’un nombre passé
en paramétre.
Exercice 3.3
Écrivez une procédure qui demande cinq nombres à l’utilisateur.
Exercice 3.4
Écrivez une procédure qui demande l’année de naissance à l’utilisateur
36
et affiche son âge.
Les fonctions récursives
• Une fonction récursive est une fonction qui pour fournir un résultat,
s’appelle elle-même un certain nombre de fois.
• Exemple : la formule de calcul du factoriel d’un nombre n s’écrit :
n!=1x2x3x…xn
Ce qui peut se programmer avec une boucle Pour.
37
Les fonctions récursives
Une autre manière de voir les choses, serait de dire que :
n ! = n x (n-1) !
D’où, le factoriel d’un nombre, c’est ce nombre multiplié par la factorielle du
nombre précédent.
• Pour programmer cela, il faut une fonction Facto, chargée de calculer le
factoriel. Cette fonction effectue la multiplication du nombre passé en
argument par le factoriel du nombre précédent.
Et cet factoriel du nombre précédent va bien entendu être elle-même calculée
par la fonction Fact.
38
Les fonctions récursives
• Pour terminer, il nous manque la condition d'arrêt de ces auto-appels de la
fonction Facto.
Dans le cas d'un calcul du factoriel, on s’arrête quand on arrive au
nombre 1, pour lequel le factoriel est par définition 1.
Fonction Facto (n : Entier) : Entier;
Début
Si n = 1 alors
Renvoyer 1
Sinon
Renvoyer Facto(n - 1) * n
Finsi
Fin 39
Les fonctions récursives
• Pour conclure sur la récursivité, trois remarques fondamentales.
- La programmation récursive, pour traiter certains problèmes, peut être très
économique, elle permet de faire les choses correctement, en très peu de
lignes de programmation.
- En revanche, elle est très dispendieuse de ressources machine. Car il faut
créer autant de variable temporaires que de " tours " de fonction en attente.
- Toute fonction récursives peut également être formulée
en termes itératifs ! Donc, si elles facilitent la vie du
programmeur, elle ne sont pas indispensable.
40
Les algorithmes de tri
• Les algorithmes de tri, sont utilisés principalement pour les
tableaux et les listes, ils peuvent aller du plus simple au plus
compliquer.
• Le tri à bulle
C’est un des algorithmes le plus connu. Bien qu’il soit rarement
efficace en terme de temps de calcul, il est néanmoins correcte.
• Le tri par insertion
Peut être intéressant pour des tableaux ayant déjà été triés, mais où
l’on doit rajouter quelques nouveaux éléments.
41
Les algorithmes de tri
• Le tri par sélection
Le but est désormais de déplacer chaque élément à sa position définitive.
Chaque échange met un élément en position définitive. Cependant, aucun échange
n’est inutile, car un élément qui a été bien placé, ne sera plus testé par la suite.
• Le tri shell
C’est une amélioration du tri par insertion.
L’intérêt de ce tri, est qu’il créé rapidement un fichier presque trié, en appliquant un
dernier par insertion, celui-ci sera beaucoup plus rapide.
• Le tri rapide (Quick Sort)
Ce tri est récursif. On cherche à trier une partie du tableau, délimitée par les indices
gauche et droite.
42
Les algorithmes de tri
• Le tri par création
Lorsqu’il est nécessaire de disposer simultanément du tableau initial et du tableau trié,
on peut recopier le tableau initial puis effectuer un tri sur la copie ou adapter un des
algorithmes précédents.
• Le tri par fusion
Il utilise un algorithme de fusion de deux tableaux triés en un seul plus
grand, appelé récursivement sur les deux moitiés du tableau, jusqu’à une
taille de tableau de 1.
43
Les algorithmes de recherche
• La recherche séquentielle
A partir d’un tableau trié, on parcours ce tableau élément par élément
jusqu’à trouver le bon élément.
• La recherche dichotomique
La recherche dichotomique recherche un élément dans un tableau trié et
retourne l’indice d’une occurrence de cet élément.
44
