Université Adam Barka d'Abéché (UNABA)

Faculté des sciences Appliquées

Département de Mathématiques

Support de cours de la matière :

Algorithmique

Niveau : Troisième année

Todjirom Nassinda Giraud

Année universitaire 2024-2025

Objectifs du cours :
Cette matière vise à amener progressivement les étudiant à assimiler et utiliser les
concepts et les techniques nécessaires pour construire des algorithmes aux
problèmes rencontrés. Ceci, doit impérativement passé par la compréhension de la
démarche algorithmique et les énoncés nécessaires à sa représentation en pseudo
code.

Mode d’évaluation : Examens écrits, Contrôle continu et Travaux pratiques.

Chapitre 1 Introduction
Pourquoi avons-nous besoin d’étudier les algorithmes ? Si nous voulons devenir des
professionnels de l’informatique, il y a deux raisons à la fois d’ordre théorique et
pratique d’étudier les algorithmes. D’un point de vue pratique, vous devez connaître
un ensemble standard d’algorithmes relevant de différents domaines de calcul. En
plus, vous devez être capable de concevoir de nouveaux algorithmes et analyser leur
efficacité. D’un point de vue théorique, l’étude des algorithmes a été reconnue
comme la pierre angulaire de l’informatique. David Harel, déclare que <<
l'algorithmique est plus qu’une branche de l’informatique et c'est l’âme de
l’informatique et en toute vérité, elle a une grande importance pour la majeure partie
de la science, des affaires et de la technologie.

1.1. Définition d'un algorithme

Bien qu'il n'existe pas pas de définition universellement admise pour décrire cette
notion, il y a un consensus général au sujet de la signification de ce concept.

Une succession finie d’opérations qui donne la solution d’un problème donné. Pour
écrire un algorithme, on utilise un pseudo-langage compréhensible par une
communauté. Donc, l’idée générale d’un algorithme est de donner la solution d’un
problème sous forme d’opérations qui peuvent être traduites dans un langage
compréhensible par la machine tout en le gardant lisible et compréhensible par une
personne ordinaire.

Programme : un programme est un assemblage et un enchaînement d’instructions

élémentaires écrites dans un langage de programmation, et exécuté par un
ordinateur afin de traiter les données d’un problème et renvoyer un ou plusieurs
résultats.

Langage de programmation : un langage de programmation fournit un ensemble de

mots-clés et de règles de syntaxe qui permettent de créer des instructions formant
des programmes et qui peuvent s’exécuter, sans souci, sur une machine.

Notons que même si la majorité des algorithmes sont conçus pour une éventuelle
implémentation d'information, la notion de d'algorithme ne se repose pas
essentiellement sur une telle Assomption. Comme par exemple, le calcul du
problème grand diviseur commun des deux entiers naturels. Cet exemple nous aide à
illustrer plusieurs points importants :

La non ambiguïté exigée pour chaque étape d’un algorithme ne peut jamais être
compromise. La gamme des entrées pour lesquelles un algorithme marche doit être
spécifiée attentivement.

Le même algorithme peut être représenté de différentes façons.

Plusieurs algorithmes pour résoudre le même problème peuvent exister.

Des algorithmes pour le même problème peuvent être basés sur des idées
différentes et peuvent résoudre le problème avec des vitesses radicalement
différentes.

Rappelons que le plus grand diviseur commun de deux entiers positifs non tous nuls
m et n, dénoté), PGCD(nm), est défini comme le plus grand entier naturel qui divise à
la fois m et n.

L’Algorithme d’Euclide est basé sur l’application répétitive de la relation :

PGCD(m,n)=PGCD(n,m) si n#0

Voici une description plus structurée de cet algorithme.

Etape 1. Sin = 0, retourner la valeur de m comme réponse et STOP sinon continuer à

l’Etape 2.

Etape 2. Diviserm par n et affecter la valeur du reste à r .

Etape 3. Affecter la valeur de n à m et la valeur de r à n. Aller à l’Etape 1.

Alternativement, nous pouvons exprimer le même algorithme en pseudo code.

ALGORITHME Euclide(m,n)
//Calcul de GCD(m, n) par l’algorithme d’Euclide
// Input : Deux entiers positifs non tous nuls m et n.
//Output : Le plus grand diviseur commun de m et n.
while (n#0)
do
r<-m modn;
m<-n;
n<-r;
return(m)

Comment savoir que l’algorithme d’Euclide finit éventuellement par s’arrêter ? Ceci
résulte de l’observation que le deuxième nombre de la paire devient plus petit à
chaque itération et ne peut pas devenir négatif. En effet, la nouvelle valeur de n à
l’itération suivante est m mod n, qui est toujours plus petit que n. Donc, la valeur du
deuxième nombre de la paire devient éventuellement zéro et l’algorithme s’arrête.

1.2 Conception d'un algorithme

Lors de la conception d'un algorithme, nous devons nous s'appuyer sur des points
importants.

1.2.1 comprendre le problème

À partir d'une perspective pratique, la première chose qu'on doit faire avant de
concevoir un algorithme est de comprendre complètement le problème à résoudre,
lire attentivement la description du problème et de poser des questions si vous avez
de doutes concernant le problème. Exécuter quelques exemples à la main, penser
aux cas spéciaux et encore des questions si nécessaire.

1.2.2 vérifier les capacités des moyens informatiques

Une fois que vous avez complètement compris le problème, vous avez besoin de
spécifier les capacités des dispositifs informatique cible de votre algorithme. La
grande majorité des algorithmes auparavant utilisés étaient destinés à être exécutée
sur des machines très semblable à la machine de Von Newman, une architecture de
machine proposée par le célèbre mathématicien américain Von Newman.

L'essence de cette architecture est captée par ce que l'on appelle l'architecture mono
-processeur. Sa principale hypothèse est que les instances sont exécutées les unes
après les autres. Par conséquent, les algorithmes conçus pour être être exécutés sur
des telles machines sont appelés des algorithmes séquentiels.

La principale hypothèse du modèle mono-processeur, ne tient plus pour les nouveaux

ordinateurs qui peuvent exécuter des opérations en parallèle. Les algorithmes qui
reposent sur cette cette capacité sont appelés les algorithmes parallèles.

1.2.3 Choisir entre une solution approximative ou exacte

La prochaine décision est de choisir entre résoudre le problème exactement ou le

résoudre approximative ?

Dans le premier cas, on l'appelle l'algorithme exacte et le second cas, l'algorithme

approximatif. On opte souvent pour l'algorithme approximatif parce que
premièrement, il existe des problèmes importants pour lesquels la plupart des
instances ne peuvent pas être résolues exactement.

Exemple : calcul de racine carré, résolution des équations non-linéaires et l'évaluation

des intégrales définies, etc.

Deuxièmement, les algorithmes disponibles pour résoudre exactement certains

problèmes peuvent être lents à cause de la complexité intrinsèque du problème
(problème NP-complet).

Troisièmement, un algorithme approximatif peut être une partie d'un algorithme très
soffistiqué qui résoud un problème.

1.2.4 choisir les structures de données approchées

Certains algorithmes ne demandent pas une ingéniosité quelconque pour représenter

leur entrée, d'autres par contre sont préconçus sur des structures de données
ingénieuses. En outre, certaines techniques de conception des algorithmes que nous
étudierons par la suite dépendent intimement de la structuration ou de la
restructuration des données spécifiant l'instance du problème.

1.3 Technique de conception des algorithmes

Maintenant que tout les composants de la résolution des problèmes algorithmique

sont connus, comment comment concevoir un algorithme pour résoudre un
problème donné ? Ceci est la question principale à laquelle ce cours cherche à
répondre en enseignant plusieurs techniques générales de conception.

Une technique de conception des algorithmes (ou stratégie ou paradigme) est une
approche générale de résolution algorithmique des problèmes qui est appliquable à
une variété des problèmes provenant des différents domaines de l'informatique.

1.3.1 Méthode de description des problèmes

Après avoir conçu un algorithme, vous on a besoin de le décrire d'une certaine façon.
On peut le décrire littéralement (dans une forme libre et aussi dans une forme étape
par étape), ou encore en pseudo-code. Ces sont là les deux options qui sont les plus
utilisés par la spécification des algorithmes.

1.3.2 Vérification de la correction d'un algorithme

Une fois qu'un algorithmes a été spécifié, vous devez montrer sa correction. C'est à
dire, vous devez montrer que l'algorithme produit le résultat désiré pour toute les
entrées légitimes en un temps fini. Pour certains algorithmes une preuve de
correction est assez faille, pour d'autres, elle peut être toute à fait complexe.

Une technique simple pour montrer la correction d'un algorithme consiste à utiliser
une indication mathématique parce que les interations d'un algorithme offre une
suite naturelle d'étape nécessaires pour de telle preuve. La notion de correction pour
les algorithmes approximatifs est moins évidente que celle des algorithmes exactes.
Pour algorithmes d'approximation, on préfère souvent d'être capable de montrer que
l'erreur produit par l'algorithme ne dépasse pas une limite prédéfinie.

Lorsque l'algorithme est trouvé incorrect, on doit soit le reconcevoir avec les mêmes
décisions concernant les instructions de données. La technique de conception ou
dans le cas extrême reconsidérer une ou plusieurs décisions(s).

1.3.3 Analyste des algorithmes

Après la correction, l'efficacité d'un algorithme est très importante, en effet on
distingue deux types d'efficacités des algorithmes

L'efficacité temporelle : indique avec quelle vitesse l'algorithme s'exécute

L'efficacité mémoire : indique combien de l'espace mémoire l'algorithme demande.

Une autre caractéristique désirable est la simplicité, contrairement à l'efficacité, qui

peut être définie précisément et étudier avec une rigueur mathématique. La
simplicité comme la beauté, se trouve à un degré considérable dans les yeux de celui
qui l'a écrit.

Une autre caractéristique désirable d'un algorithme est la généralité. Il y a en effet

deux aspects : la généralité du problème que l'algorithme résoud et la gamme des
entrées qu'il accepte.

1.3.4 Codage des algorithmes

La plupart des algorithmes sont destinés à être ultérieurement implémenté comme

programme informatique. Programmer un algorithme présente à la fois un péril et
une opportunité. Le péril se trouve dans la possibilité de rendre le passage d'un
algorithme à un programme soit incorrecte, soit très inefficace en pseudo-code.

1.4. Structure d'un algorithme

La figure suivante donne la structure générale d’un algorithme :

La première ligne (1) permet juste d’identifier l’algorithme. Donc, le nom attribué ne
change pas l’exécution et les résultats.

Avant de mettre les instructions, il faut déclarer (2) les constantes (3) et les variables
(4) utilisées dans l’algorithme.

La partie principale de l’algorithme se trouve entre les mots clés ‘début’ et ‘fin’ (5).
Elle contient la suite d’instructions à exécuter.
Exemple :

Algorithme Produit

Déclaration

x, y, z : entier

Début

Lire(x, y)

z x *y

Ecrire(z)

Fin

2.4.1. Notion de variable

Une variable est un mot qui permet l’identification de l‘emplacement mémoire où on

stocke une valeur à manipuler.

Malgré que le choix est libre du nom de la variable, il préférable, pour des raisons de
lisibilité et de compréhension de choisir des noms de variables en fonctions de ce
qu’elles représentent. Par exemple : Moyenne, Poids, Taille,…etc.

La notion de type d’une variable est capitale, car elle implique le choix du codage de
la
variable (par exemple, un entier sur 32 bits et un caractère sur 16 bits) ainsi que les
possibilité d’usage ( par exemple : on ne peut pas multiplier un caractère par un
nombre entier).

Exemple de déclaration des variables :

M, Max : Entier
Poids, Moyenne : Réel
Premier : Bouléen

1.4.2. Notion de constante

On peut assimiler la notion d’une constante à une variable dont la valeur ne change
pas au cours de l’exécution de l’algorithme.

Exemple de déclaration des constantes :

TVA = 0,17
N = 50
Admis = Vrai

Chapitre 2. Les types d'instructions

La partie principale d’un algorithme contient la suite d’instruction qui va être traduite
vers un langage de programmation. Il existe quatre types d’instruction dont le détail
est donné par les points suivants.

2.1. Les instructions d’entrée/sortie

Ce type d’instruction est utilisé pour interagir avec l’utilisateur, en lui permettant
d’entrer des
valeurs des variables. Ainsi, le résultat des traitements et des messages
d’information peuvent être affichés à l’utilisateur via ce type d’instruction. En réalité, il
existe plusieurs périphériques et manières pour échanger des données avec un
algorithme ou un programme (via des fichiers, des bases de données, des
formulaires,…). Toutefois, pour se concentrer sur les principes de l’algorithmique, on
se contente par les entrées et les sorties standards, à savoir, l’écriture sur le clavier et
l’affichage sur écran. L’exploitation des autres possibilités vont être abordées dans la
matière dédiée à la programmation.

2.1.1. Instruction d'entrée

C’est l'instruction de lecture de données sur le périphérique d'entrée.

Structure générale :

Lire (variable)
Lire (variable1, variable2,…)

Exemple :

Lire(Taille)
Lire (x, y)
2.1.2. Instruction de sortie

C’est l'instruction de restitution de résultats sur le périphérique de sortie.

Structure générale :
 Écrire (variable)
Écrire (‘message’)
Écrire (‘message’, variable)

Exemple :

Écrire (moyenne)
Écrire (‘ entrer la taille’)
Écrire (‘le résultat est :’, max)

2.2. L’instruction d’affectation

Cette instruction permet d’affecter une valeur à une variable, après l’évaluation d’une
expression logique ou arithmétique.

A la place d’une expression, on peut utiliser une simple valeur ou une variable

Il faut noter que le résultat de l’évaluation de l’expression doit avoir le même type que
la variable qui va le recevoir.

Structure générale :

variable expression

Exemple 1:
x  15,2
x y
x y+ 4

2.3. Test sur l’instruction d’affectation

Objectif : auto-évaluation de la compréhension de l'effet des instructions d'affectation
sur l'état des variables.

Exercice 1

Quelles sont les valeurs des variables a,b et c écrites par l'algorithme suivant ?
 Algorithme Affectation1

Variables :

a,b,c: entier

Début

a  10

b a*2

a a- b/2

cb+

a*2

Ecrire (a,b,c)

Fin.

o a= 10, b=20, c=40

o o a= -5, b=20, c= 10

o o a= 0, b=20, c=20

Exercice 2

Quelle est l'objectif de cette séquence d'instructions ?

xx+y

yx-y

xx-y

o Calculer la différence entre deux

variables.

o o Permuter les valeurs de deux

variables.

o Sans objectif.
2.4. Les instructions conditionnelles

Ces instructions sont utilisées pour faire le choix entre l’exécution ou non des blocs
d’instructions suite à l’évaluation d’une condition. On en distingue trois types :

2.4.1. L’instruction conditionnelle simple

Ce type d’instructions permet de faire le choix entre l’exécution ou non d’un seul boc

d’instructions.

Structure :

SI (Condition) alors
Instructions
Fin Si

Exemple :

A 5
B  12
SI (B>A*2) alors
BA
Fin Si
Ecrire (B)

2.4.2. L’instruction conditionnelle alternative

Ce type d’instructions permet de faire le choix de l’exécution entre deux blocs
d’instructions.

Structure :

SI (Condition) alors
Instructions
Sinon
Instructions
Fin Si
Exemple :

A 5
B  12
SI (B>A*2) alors
BA
Sinon
B A + 4
Fin Si
Ecrire (B)

2.4.3. instruction conditionnelle de choix

Ce type d’instructions permet de faire le choix de l’exécution entre plusieurs blocs
selon la valeur d’une variable donnée.

Structure :

Selon le cas (variable)

Variable = valeur 1: instructions
Variable = valeur 2 : instructions
…
Variable = valeur n : instructions
Sinon
Instructions
Fin Si

Exemple :

Lire (x)
Selon le cas (x) x = 1 : Ecrire
(‘Très Faible’)

x = 2 : Ecrire (‘Faible) x
= 3 : Ecrire (‘Moyen) x =
4 : Ecrire (‘Bien’) x = 5 :
Ecrire (‘Excellent’)
Sinon
Ecrire (‘Valeur hors intervalle acceptée’)
Fin Si
2.5. Test sur l'utilisation des instructions conditionnelles

Objectif : auto-évaluation de la compréhension de du rôle des instructions conditionnelles.

Exercice

Soit l’algorithme suivant :

AlgorithmeTest

Déclarations :

a, b, c : Entier

Début

1: Lire (a, b)

Si (b/2>a) Alors :

2: c b - a

Sinon

3: c b + a

4: a b - c

Fin si

5 :Ecrire (a, b, c)

Fin.

Quelles sont les instructions exécutées pour les valeurs : a = 5, b = 10 ?

2.6. Les instructions itératives (les boucles)

Les instructions itératives ou répétitives, appelées aussi communément par les
développeurs les boucles, permettent d’exécuter plusieurs le même bloc
d’instructions. On en distingue trois types :

2.6.1. L’instruction ou boucle ‘Pour’

Dans ce type d’instructions itératives on connait à l’avance le nombre d’itérations. En
effet, on doit préciser, dans l’entête de l’instruction ‘Pour’, la valeur initiale et la valeur
finale et éventuellement le pas (lorsqu’il est différent de 1).
Structure :

Pour i allant deVI à VF (pas = V) faire

Instructions

Fin Pour

VI : valeur initiale de la variable i,

VF ; valeur finale de la variable i,
V : valeur à ajouter la variable i après chaque itération (par défaut 1).

Exemple :

Pour i allant de 1 à 10 faire

Ecrire (‘L3 Bioinformatique’)
Fin pour

2.6.2. L’instruction ou boucle ‘Tant que

Dans ce type d’instructions itératives on ne connait pas forcement à l’avance le

nombre d’itérations. En effet, on continue la répétition de l’exécution du bloc
d’instructions tant qu’une condition est encore satisfaite.

Tant que (condition) faire

Instructions

Fin Tant que

Exemple :

i =1

Tant que (i <= 10) faire

Ecrire (‘L3 bioinformatique’)
i i + 1
Fin Tant que
2.6.3. L’instruction ou boucle ‘Répéter’
Comme le cas pour l’instruction ‘Tant que’, l’instruction ‘Répéter’ ne permet pas de
connaitre forcement à l’avance le nombre d’itérations. En effet, on continue la
répétition de l’exécution du bloc d’instructions jusqu’à la satisfaction d’une condition.

Structure :

Répéter

Instructions

Jusqu’à (Condition)

Exemple :

i=1

Répéter

Ecrire (‘L3 bioinformatique’)

i i + 1 Jusqu’à (i > 10)

Remarque : L’instruction ‘Tant que’ s’exécute zéro ou plusieurs fois, au moment où,
l’instruction ‘Répéter’ s’exécute une ou plusieurs fois.

Série de TD 1
Exercice 1 :

Écrire un algorithme qui calcule le carré d'un nombre entier donné par l'utilisateur.

Exercice 2 :

Écrire un l'algorithme qui échange les valeurs des variables A et B.

Exercice 3 :

Écrire un algorithme qui résout une équation du premier degré ax+ b=0.

Exercice 4 :

Ecrire un algorithme qui donne la valeur absolue d'un entier.

 Exercice 5 :

Écrire un algorithme qui convertit un nombre de secondes en heures: minutes:

secondes.

Exercice 6 :

Écrire un algorithme qui résout une équation du second degré ax2+ bx +c=0.

Exercice 7 :

Ecrire un algorithme qui détermine si la valeur d'un entier est paire ou impaire.

Exercice 8 :

Ecrire un algorithme qui donne tous les diviseurs d'un entier positif.

Exercice 9 :

Ecrire un algorithme qui calcule le factoriel d'un entier positif.

Exercice 10 :

Ecrire un algorithme qui calcule a puissance b avec a réel et b entier par

multiplication successives.

Exercice 11 :

Ecrire un algorithme qui vérifie si ce nombre est premier ou non.

Exercice 12 :

Ecrire un algorithme qui calcule le PGCD de deux entiers positifs.

Exercice 13 :

Ecrire un algorithme qui détermine si un entier positif est parfait.

Un nombre parfait est un nombre présentant la particularité d'être égal à la somme
de tous ses diviseurs, excepté lui-même.

Exercice 14 :

Ecrire un algorithme qui donne le nombre d'occurrences d'un caractère donné dans
une chaine lue caractère par caractère et qui se termine par un point.

Exercice 15 :
Ecrire un algorithme qui affiche tous les nombres parfaits inférieurs à 1000.

Exercice 16 :

Ecrire un algorithme qui affiche tous les nombres parfaits inférieurs à 1000.

Exercice 17 :

Ecrire un algorithme qui calcule les 10 premiers termes de la suite de Fibonacci. La

suite de Fibonacci est définie par :
F0 = 1
F1= 1
Fn=Fn-2+Fn-1 pour n>1