TDI
Algorithmique
Chapitre 1: Concepts de base
1
Origine du mot algorithme
Un algorithme est un mot d‘origine arabe qu’est
dérivé du nom du scientifique Al-Khawarizmî
(780-850 après J.C).
Au départ, le mot ”algorisme” désignait les règles
nécessaires pour effectuer des calculs
arithmétiques en utilisant la notation décimale. Le
terme algorithme apparaît au XVIIIe siècle.
2
Définitions
Un algorithme est une suite d‘actions (appelées instructions)
ordonnées en séquences qui a pour but de résoudre un
problème donnée.
Un algorithme, c’est une suite fini d’actions, qui une fois
exécuté correctement, conduit à un résultat donné.
Données d’entrée Algorithme Données de sortie
3
Règles de construction
Un algorithme doit respecter les règles suivantes:
Il est précis et défini sans ambiguïté (Bien définir: l'ordre
des étapes qui le constituent, à quel moment il faut cesser
une action, à quel moment il faut en commencer une autre,
comment choisir entre différentes possibilités …)
Il se termine après un nombre fini d‘opérations.
Il est déterministe (une suite d'exécutions à partir des mêmes
données doit produire des résultats identiques).
4
Analyse descendante des problèmes algorithmiques
Une analyse descendante consiste à diviser le problème à résoudre
en plusieurs éléments simples et à continuer la division jusqu’aux
opérations élémentaires.
Sous problème 11
Sous problème 1
Sous problème 12
Sous problème 2
Problème
de base Sous problème 1N
Sous problème N
5
Algorithme et programme
Un algorithmique exprime les instructions résolvant un problème
donné indépendamment des particularités des langages de
programmation.
Analyse et Validation
Spécification Codage
décomposition
Problème Énoncé Algorithmes Programmes Problème résolu
6
Caractéristiques d' un algorithme
Caractéristiques d' un algorithme
L’algorithme est un moyen pour le programmeur de présenter son
approche du problème à d'autres personnes. Un algorithme doit être :
ƒ De haut niveau: l'algorithme doit pouvoir être traduit en n'importe
quel langage de programmation.
ƒ Lisible: il doit être compréhensible.
ƒ Précis: chaque élément de l'algorithme ne doit pas porter à
confusion.
ƒ Concis: un algorithme ne doit pas dépasser plusieurs pages sinon
décomposer le problème en plusieurs sous-problèmes
ƒ Structuré: un algorithme doit être composé de différentes parties
facilement identifiables
Maîtrise de l'algorithmique
La maîtrise de l'algorithmique requiert deux qualités :
ƒ Il faut être méthodique. Avant d’écrire les instructions d'un
algorithme, il faut analyser le problème à résoudre. Il faut ensuite
définir les entrées et les sorties de l'algorithme.
ƒ Il faut être rigoureux. Chaque fois qu'on écrit une série
d'instructions, il faut systématiquement se mettre mentalement à la
place de la machine qui va les exécuter (faire si nécessaire une
simulation sur papier).
Les réflexes du raisonnement algorithmique deviennent spontanés avec
l'expérience.
8
Concept de variable
ƒ Lors de la résolution d’un problème, on va avoir en permanence
besoin de stocker des données en mémoire.
ƒ Ces données peuvent être de plusieurs types: nombre, texte…
ƒ Dés que l’on a besoin de stocker une information dans un
programme, on utilise une variable.
9
ƒ Une variable est un élément (correspond à un espace mémoire)
dont la valeur peut changer au cour de l’exécution de
l’algorithme.
ƒ Une variable possède :
• Un nom, appelé identifiant (étiquette de l’espace
mémoire qui lui est associé)
• Une valeur (contenu de l’espace mémoire)
• Un type qui caractérise l’ensemble des valeurs qu’elle
peut prendre.
10
Déclaration des variables
ƒ Instruction permettant de réserver de l’espace mémoire pour y
stocker la valeur d’une variable.
Syntaxe
Variable identificateur : type
ƒ Une fois qu’un type de données est associé à une variable le
contenu de cette variable doit obligatoirement être du même type
11
Un identificateur est un nom symbolique qui indique la
fonction de la variable dans l’algorithme
Lettre Lettre
Chiffre
(_)
12
Type des variables
Un type (de variable) détermine l’ensemble de valeurs possibles de la
variable déclarées pour désigner la nature du contenu de la variable et les
opérations pouvant être effectuées sur celle-ci.
ƒ Entier : Correspond aux valeurs de l’ensemble des entiers relatifs.
ƒ Réel : Correspond aux valeurs de l’ensemble des réels décimaux
signés.
ƒ Chaîne de caractère: Se compose d'une suite de symboles de
type caractère(une valeur de type chaîne de caractère doit être
placées entre « “ » )
ƒ Logique : Type logique qui peut prendre les valeurs VRAI
ou FAUX.
13
L’opération d’affectation
ƒ Une affectation est une opération qui consiste à associer
(assigner) une valeur donnée à une variable.
ƒ Une affectation détruit le contenu précédent de la variable.
ƒ La valeur d’une variable chaîne de caractères doit être
délimitée par : « ″ »
Syntaxe
Variable ← valeur
14
Les constantes
Une constante correspond à une donnée dont la valeur est
inchangeable durant toute l'exécution du programme.
Syntaxe: CONST identificateur ← valeur
Exemple: CONST pi ← 3.14
15
Les instructions d’entrée et de sortie
Un algorithme doit en général acquérir (saisir) des données à partir
d’un périphérique d’entrée (clavier), fournir et afficher les résultats
de ses traitements sur un périphérique de sortie(écran):
ƒ Lire (variable) : l’exécution de cette instruction permet
d’affecter à une variable la valeur tapée par l’utilisateur sur le
clavier.
ƒ Ecrire (variable | expression) : l’exécution de cette
instruction permet d’afficher la valeur de la variable(ou de
l’expression) sur l’écran.
16
Structure d’un algorithme
Un algorithme respecte généralement la structure suivante:
Algorithme nom_algorithme
Déclaration des variables
Debut
Lecture des données
Traitement des données
Affichage des résultats
Fin
17
Les opérations arithmétiques
ƒ Entre les variables numériques, plusieurs opérations
arithmétique peuvent avoir lieu ; les opérateurs arithmétiques
qu’on peut utiliser dans un algorithme sont : + , - , * , / , mod
et div
ƒ En cas d’absence de parenthèse, une expression qui contient
des opérations arithmétiques est toujours évaluée du gauche
vers la droite et selon l’ordre de priorité suivant :
ƒ Négation
ƒ * , / multiplication et division
ƒ div division entière
ƒ mod reste de la division entière
ƒ + , - addition et soustraction
18
Les opérations relationnels et logique
ƒ Les opérateurs relationnels : = , < , >, <=, >=, < >
ƒ Une expression logique est un élément qui ne peut recevoir que
l’une des deux valeurs : True ou False (Vrai, Faux)
ƒ Not : Permet d'établir la négation logique d'une
expression.
ƒ And : opération de conjonction logique entre deux
expressions.
ƒ Or : Permet d'établir une disjonction logique entre deux
expressions.
19
Priorité des opérateurs
ƒ Dans les expressions contenant des opérateurs de diverses catégories,
les opérateurs sont évalués dans l'ordre suivant:
Opérateurs arithmétiques puis opérateurs relationnels et enfin
opérateurs logiques.
ƒ Les opérateurs relationnels ont la même priorité (ils sont évalués dans
leur ordre d'apparition, de gauche à droite)
ƒ Les opérateurs arithmétiques et logiques sont évalués dans leur ordre
de priorité.
20
Exercice n° 1
Quelles seront les valeurs des variables A, B et C après
exécution de la séquence des instructions suivantes ?
ƒ A←3
B ← 10
C←A+B
B←A+B
A←C
21
Quel est, après exécution de la séquence d’instructions
suivante la valeur de A
A ←A+B
B←A–B
A←A–B
22
Ecrire un algorithme qui permet de permuter les valeurs de
2 variables x et y (exemple au départ x=2 et y=3 on veut
arriver à x=3 et y=2) .
23
Exercice n°4
Écrire un algorithme qui permet d’effectuer une permutation
circulaire des valeurs entières de trois variables x, y, z (c’est-
à-dire la valeur de y dans x, la valeur de z dans y et la valeur
de x dans z.
24
Exercice n°5
Écrire un algorithme qui saisie un nombre entier, calcul et
affiche la somme des chiffres qui composent le nombre saisie
( on suppose que le nombre contient au maximum 5 chiffres)
25
Représentation graphique des algorithmes
Un organigramme est une représentation graphique d’un
algorithme, pour le construire on peut utiliser les symboles
suivants :
….. Début ou fin de …… Instruction
l’organigramme
Opération de lecture
….. ..… Opération de
ou d’écriture
test
26
Les structures algorithmiques
Les structures algorithmiques sont réparties en 3 catégories :
ƒ Structures linéaire d'opérations(exécution séquentielle);
ƒ Structures alternatives (ou conditionnelles) ou de choix : en
fonction d'une condition, on exécute des opérations différentes;
ƒ Structures itératives ou répétitives: sous contrôle d'une
condition, une séquence d'opérations est exécutée
répétitivement.
27
L’instruction de test
Ils permettent de choisir les instructions à exécuter selon l’état (valeur)
d’une condition ( expression logique ).
Syntaxe 1
Si (condition ) Alors
InstructionV1 condition
… InstructionVn
InstructionV1 InstructionF1
Sinon
InstructionF1
… InstructionVn InstructionFn
InstructionFn
Finsi
La séquence vrai (InstructionV1 …InstructionVn) sera exécutée si la
condition est vérifier, dans le cas contraire se sera la séquence faux
(InstructionF1 …InstructionFn) qui sera executée
28
Syntaxe 2
Si (condition ) Alors condition
InstructionV1 InstructionV1
…
InstructionVn Instruction Vn
Finsi
La séquence d’instructions (InstructionV1, …, InstructionVn) sera
exécutée seulement si la condition est vérifiée (valeur vrai), s’elle est
fausse aucune instruction ne sera exécutée.
29
ƒ Une condition peut parfois être composée de deux ou de
plusieurs sous conditions.
ƒ Une instruction de test imbriquée est une instruction dans
laquelle on trouve d’autre instructions de test.
30
Exercice n° 6
Écrire un algorithme permettent de calculer la moyenne de deux
notes et d'afficher la mention selon la moyenne obtenue, comme
suit :
ƒ moyenne< 10 : mention médiocre
ƒ 10<= moyenne <12 : mention passable
ƒ 12<= moyenne <14 : mention assez bien
ƒ 14<= moyenne <16 : mention bien
ƒ 16<= moyenne <18 : mention très bien
ƒ 18<= moyenne <=20 : mention excellent
31
On se propose de calculer le nombre de chiffres pairs d’un nombre
donnée, on suppose que le nombre est un entier qui comporte 5
chiffre aux maximum. En adoptant une démarche descendante,
écrire l’algorithme de résolution de ce problème.
32
La structure de choix
ƒ Une structure de choix permet d'effectuer un choix parmi
plusieurs.
ƒ Une structure de choix est privilégié à une imbrication de tests
«SI » lorsque les valeurs que peut prendre une variable sont
discrètes (constantes).
ƒ Elle permet une présentation plus claire d'un ensemble
d'alternatives imbriquées.
33
Syntaxe 1
Selon (variable ou expression) Faire
< valeur 1> : action 1
…
< valeur N> : action N
Sinon : action par défaut
Fin Selon
ƒ La variable (ou expression) est comparée aux différentes
constantes(valeur 1 à valeur N).
ƒ Les actions exécutées dépendent de ces valeurs (les valeurs peuvent être
énumérée en les séparant par des virgules).
ƒ L'action par défaut est exécutée lorsque la variable n'est égale à aucune
des constantes énumérées.
34
Exemple
Algorithme testchoix
Variable couleur : Chaîne de caractères
Début
Écrire (" saisir couleur de feu ")
Lire (couleur)
Suivant (couleur) Faire "Vert" :
Écrire ("je passe") "Orange" :
Écrire ("je ralentis") "Rouge" :
Écrire ("je m'arrête")
Sinon : Écrire ("ceci n'est pas une couleur de feu")
Fin suivant
Fin
35
Les structures de répétition
ƒ Elles permettent d’exécuter plusieurs fois une même séquence
d’instructions.
ƒ Deux formes existent selon que le nombre de répétitions est
connu avant l'exécution des instructions de répétition ou s'il
n'est pas connu.
ƒ On appellera boucle la séquence ou l’ensemble des instructions
en répétition et itération l'exécution de la liste des instructions.
36
L’instruction Pour … Faire …
II est utilisé lorsque 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.
Syntaxe
pour compteur ← valeur_initiale à valeur_finale Faire
Instruction1
…
Instructionn
Finpour
La compteur va prendre successivement toutes les valeurs entières
comprise entre « valeur_initiale » et « valeur_finale ».
Pour chaque valeur prise par la variable, la liste des
instructions est exécutée.
ƒ L'incrémentation par 1 de la variable est implicite.
37
Les étapes d’exécution d’une boucle « pour » sont les suivantes :
1. Affectation de la valeur_initiale à la variable compteur
2. Test de la valeur du compteur (compteur ≤ valeur_finale)
3. Exécution des instructions de la boucle « pour »
4. Incrémentation de la valeur du compteur
5. Reprendre l’exécution depuis d’étape 2
Compteur=valeur_initiale
Compteur=Compteur +1
Instruction1
Instructionn
Compteur≤valeur_finale
38
Exemple
Algorithme algo1 Algorithme algo2
Variable n : entier Variable n : entier
Début
Début
Pour n ← 1 à 10
Lire (n)
Pour i ← 1 à 10
Pour i ← 1 à 10
Ecrire (n, "x",i, "=" , n*i)
Ecrire (n, "x",i, "=" , n*i)
FinPour
FinPour FinPour
Fin Fin
39
L’instruction Tantque
ƒ L'utilisation d'une boucle « pour » nécessite de connaître à
l'avance le nombre d'itérations désiré.
ƒ Dans beaucoup de cas, on souhaite répéter une séquence
d’instructions 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.
40
Syntaxe
Tantque (condition ) Faire
Instruction1
Instruction1
…
InstructionN Instructionn
condition
Fintantque
ƒ La séquence des instructions de la boucle « tantque » seront
exécuter tant que la condition est vérifiée (valeur vrai)
ƒ Le test est effectué à l’entrée de la boucle ; les instructions de la
boucle « tantque » peuvent ne jamais être exécuter si la condition
était fausse au départ.
ƒ Dans la séquence d’instruction de la boucle « tantque » au moins
une instruction doit faire évoluer la valeur de la condition.
41
Exercice 8
Donner le résultat obtenu par l’exécution de la séquence suivante :
ESSAI ← 1; OK ← Faux
Tant que (Non OK) ET (ESSAI ≤ 3) FAIRE
Ecrire (″ Essai No ″ , ESSAI)
Ecrire (″ Entrez votre mot de passe ″)
Lire (MOT)
Si (MOT <> MOTP) alors
Ecrire (″ Le mot de passe n’est pas correct, recommencez! ″)
ESSAI ← ESSAI + 1
sinon
Ecrire (″ Code correct, vous pouvez passer ! ″)
OK ← Vrai
Finsi
FinTantQue
Si (ESSAI > 3) Alors
Ecrire (″ Carte retenue ″)
Finsi
42
Donner le résultat obtenu par l’exécution de la séquence suivante :
I←1
Ecrire (" Debut " )
Tant que I ≤ 10 Faire
J←1
Tant que (J ≤10) Faire
Ecrire( i * j)
J← J+1
FinTantque
I← I+1
FinTantque
Ecrire (" Fin ")
43
L’instruction Repeter …Jusqu’à
Syntaxe
Repeter
Instruction1
Instruction1
… Instructionn
InstructionN condition
Jusqu'à (condition )
ƒ Les instructions de la boucle sont exécutées au moins une fois
avant d’effectuer le test de la condition;
ƒ L’exécution des instructions de la boucle va se répéter jusqu’à ce
que la condition soit vérifiée.
44
Exercice 10
Écrire un algorithme qui détermine pour le factoriel d’un entier N
en utilisant les boucles du type : Pour, Tant que et Répéter.
45
Écrire un algorithme qui calcul la somme des nombres entrés par
l'utilisateur tant que cette somme est inférieure à mille.
46
Écrire un algorithme qui échange les valeurs de deux nombres.
L'algorithme doit demander à l'utilisateur s'il veut s'arrêter ou
continuer.
47
