INFORMATIQUE
algorithmique
Présenté par Ing Y. Rémy OKE
Algorithme et Programmation
Email: [Link]@[Link] Ing Y. Rémy OKE 1
Différentes problématiques
❑ Terminaison : terminera en un temps fini.
❑ Complexité en temps : terminera en un temps
borné (raisonnable).
❑ Complexité en espace : terminera en utilisant une
quantité de mémoire bornée (raisonnable).
❑ Correction : si l’algorithme termine en donnant une
proposition de solution, alors cette solution est
correcte.
❑ Complétude : pour un espace de problèmes donné,
l’algorithme, s’il termine, donnera toujours des
propositions de solutions.
Algorithme et Programmation
Ing Y. Rémy OKE 2
Objectifs du cours d’algorithmique
❑ Concevoir des algorithmes simples ;
❑ Analyser les performances d’un algorithme
:notion de complexité ;
❑ Algorithmes fondamentaux : description et
complexité ;
❑ Structures de données performantes :
tableaux dynamiques, tableaux triés, listes
chaînées, arbres, tables de hachage, (graphes)..
Algorithme et Programmation
Ing Y. Rémy OKE 3
Objectifs du cours d’algorithmique
Algorithme et Programmation
Ing Y. Rémy OKE 4
Définition
Un algorithme fait passer d’un état initial à un état
final de façon déterministe. Il doit respecter les
règles suivantes :
➢ Il est définit sans ambiguïté
➢ Il se termine après un nombre fini d’opérations
➢ Il doit être effectif : toutes les opérations doivent
être effectuées par un homme par des moyens
manuels.
➢ Il manipule des objets qui doivent être définis de
manière très précise.
Un algorithme est une suite d’actions ordonnées en
séquence qui porte sur des objets d’un univers fini.
Algorithme et Programmation
Y. Rémy OKE 5
I- Notion d’objet
Trois éléments permettent de caractériser un
objet :
➢ Son identificateur : il représente une suite
quelconque de caractères alphanumériques (sans
espace) commençant obligatoirement par une
lettre. De préférence, le nom est choisi en rapport
avec le contenu de l’objet.
➢ Sa valeur : constante ou variable
➢ Son type : entier, réel, caractère, chaîne de
caractères
Algorithme et Programmation
Ing Y. Rémy OKE 6
II- Définition du type de données
Booléen : ensemble des constantes (vrai ou faux), ensembles
des opérateurs ET, OU, NON
Numérique : entier, réel, ensemble des constantes : R ou Z
Ensemble des opérateurs : toutes les opérateurs
arithmétiques et trigonométriques. Pour les opérateurs les
plus courantes, nous notons :
+ : addition
X : multiplication
- : Soustraction
/ : Division
^ : Elévation à la puissance
div : La division entière
mod : le reste d’une division
ent : la partie entière d’un réel
Algorithme et Programmation
Ing Y. Rémy OKE 7
II- Définition du type de données
Chaîne de caractères : Une chaine est:
➢ Soit une chaine vide
➢ Soit un caractère suivi d’une chaine de
caractères
Les tableaux
C’est une structure de données linéaire qui
permet de stocker les données de même type.
Chacune des variables est repérée par un
indice indiquant la position de la donnée dans
le tableau.
Algorithme et Programmation
Ing Y. Rémy OKE 8
III- Présentation d’un algorithme
Algorithme et Programmation
Ing Y. Rémy OKE 9
III- Présentation d’un algorithme
Algorithme et Programmation
Ing Y. Rémy OKE 10
III- Présentation d’un algorithme
Algorithme et Programmation
Ing Y. Rémy OKE 11
IV- Instruction d’un algorithme
1- Instruction simple
1.1- Affectation
Algorithme et Programmation
Ing Y. Rémy OKE 12
IV- Instruction d’un algorithme
1- Instruction simple
Algorithme et Programmation
Ing Y. Rémy OKE 13
IV- Instruction d’un algorithme
1- Instruction simple
Algorithme et Programmation
Ing Y. Rémy OKE 14
V- Instructions conditionnelles
5-1 conditions alternatives
Format Général
Si <condition >
Alors < action 1>
Sinon <action 2>
fsi
Lorsque l’évaluation de la condition produit la valeur
➢ Vrai : l’action 1 est exécutée
➢ Faux l’action 2 est exécutée
Action 1, comme action 2 peut être Soit
➢ Une Instruction
➢ Un ensemble d’instructions
➢ Un algorithme
Algorithme et Programmation
Ing Y. Rémy OKE 15
V- Instructions conditionnelles
Algorithme et Programmation
Ing Y. Rémy OKE 16
V- Instructions conditionnelles
Algorithme et Programmation
Ing Y. Rémy OKE 17
V- Instructions conditionnelles
Algorithme et Programmation
Ing Y. Rémy OKE 18
V- Instructions conditionnelles
5-2- Condition de choix multiple
Format général
Suivant > variable ou expression faire
<entier 1> : < action 1>
< entier 2 > : < action2>
<entier 3> : < action 3>
< entier n > : < action n>
Sinon : <action par défaut>
Finsuivant
Ou
Suivant < variable ou expression > faire
‘lettre 1’ : < action 1>
‘lettre n’ : < action n >
Sinon : < action par défaut >
Finsuivant Algorithme et Programmation
Ing Y. Rémy OKE 19
V- Instructions conditionnelles
Algorithme et Programmation
Ing Y. Rémy OKE 20
VI- LES BOUCLES
Algorithme et Programmation
Ing Y. Rémy OKE 21
VI- LES BOUCLES
Algorithme et Programmation
Ing Y. Rémy OKE 22
VI- LES BOUCLES
Algorithme et Programmation
Ing Y. Rémy OKE 23
VI- LES BOUCLES
Algorithme et Programmation
Ing Y. Rémy OKE 24
VI- LES BOUCLES
Algorithme et Programmation
Ing Y. Rémy OKE 25
VI- LES BOUCLES
Algorithme et Programmation
Ing Y. Rémy OKE 26
VI- LES BOUCLES
RÉPÉTITION D’UN TRAITEMENT À NOMBRE ITÉRATIONS
INCONNU « TANT QUE … FAIRE »
Exemple ; Algorithme FaitLeTotal {Cet algorithme fait la somme des nbVal
données qu'il saisit, arrêt à la lecture de -1}
constante (STOP : entier) ←-1
variables val, totalValeurs: entiers
début
totalValeurs←0
afficher("Donnez une valeur,", STOP, " pour finir.") {amorçage}
saisir(val)
tant que val ≠STOP faire
totalValeurs←totalValeurs+ val {traitement}
afficher("Donnez une autre valeur,", STOP, " pour finir.")
saisir(val) {relance}
ftq
afficher("La somme des valeurs saisies est", totalValeurs)
Algorithme et Programmation
fin Ing Y. Rémy OKE 27
VI- LES BOUCLES
COMPARAISON BOUCLES « POUR » ET « TANT QUE »
pour cpt ←1à nbVal faire
afficher("Donnez une valeur :")
saisir(valeur)
totalValeurs←totalValeurs+ valeur {cumul}
Fpour
Est équivalent à
cpt ←0
tant que cpt <nbVal faire
afficher("Donnez une valeur :")
saisir(valeur)
totalValeurs←totalValeurs+ valeur {cumul}
cpt ←cpt + 1 {compte le nombre de valeurs traitées}
Algorithme et Programmation
ftq Ing Y. Rémy OKE 28
VI- LES BOUCLES
Implicitement, l’instruction pour:
➢ initialise un compteur
➢ incrémente le compteur à chaque pas
➢ vérifie que le compteur ne dépasse pas la borne
supérieure
Explicitement, l’instruction tant que doit
➢ initialiser un compteur {amorçage}
➢ incrémenter le compteur à chaque pas {relance}
➢ vérifier que le compteur ne dépasse pas la borne
supérieure {test de boucle}
Algorithme et Programmation
Ing Y. Rémy OKE 29
VI- LES BOUCLES
QUAND CHOISIR « POUR » OU «
TANT QUE » ?
Nombre d’itération connu à l’avance : POUR
➢ Parcours de tableaux
➢ Test sur un nombre donné de valeurs
Boucle s’arrête sur événement particulier : TANT QUE
➢ Itération avec arrêt décidé par saisie
utilisateur
Algorithme et Programmation
Ing Y. Rémy OKE 30
VI- LES BOUCLES
BOUCLE « RÉPÉTER …TANT QUE »
Répéter
(ré) affectation de la (des) variable(s) de
condition traitement
Tant que <expression logique (vraie)>
Fonction: exécuter une suite d’instructions au moins
une fois et la répéter tant qu’une condition est
remplie
Remarque: le traitement dans l’exemple précédent
se limite à la réaffectation de la variable de condition
(saisir(valeur)) Algorithme et Programmation
Ing Y. Rémy OKE 31
VI- LES BOUCLES
COMPARAISON «RÉPÉTER» ET «TANT QUE»
Répéter
afficher("Donnez une valeur positive paire :")
saisir(valeur)
tant que (valeur < 0 ou(valeur % 2) ≠0)
Équivaut à
afficher("Donnez une valeur positive paire :")
saisir(valeur)
tant que (valeur < 0 ou(valeur % 2) ≠0) faire
afficher("Donnez une valeur positive paire:")
saisir(valeur)
ftq Algorithme et Programmation
Ing Y. Rémy OKE 32
VI- LES BOUCLES
Boucle tant que
➢ condition vérifiée avant chaque exécution du
traitement
➢ le traitement peut donc ne pas être exécuté
➢ de plus : la condition porte surtout sur la saisie de
nouvelles variables (relance)
Boucle répéter … tant que
➢ condition vérifiée après chaque exécution du
traitement
=>le traitement est exécuté au moins une fois
➢ de plus: la condition porte surtout sur le résultat
du traitement
Algorithme et Programmation
Ing Y. Rémy OKE 33
VI- LES BOUCLES
DE L’ÉNONCÉ À LA BOUCLE
saisir des données et s'arrêter dès que leur somme
dépasse 500
somme ←0
répéter
saisir(val)
somme ←somme + val
tant que somme ≤500
saisir(val)
somme ←val
tant que somme ≤500 faire
saisir(val)
somme ←somme + val
Algorithme et Programmation
ftq Ing Y. Rémy OKE 34