TD

COURS
ALGORITHMIQUE

[Link]

Pr Filali Reda
ESTC – DEP GI
 ALGORITHMIQUE
ALGORITHMIQUE Introduction

[Link]/elearning-center

• L’algorithmique : Une discipline

❑ Essentielle
o Résolution de problèmes : L'algorithmique permet de résoudre des problèmes techniques
complexes.
o Optimisation des processus : Automatisation et optimisation des tâches pour économiser du
temps et des ressources.

❑ Cruciale pour des secteurs stratégiques. comme

1. Analyse de données
o Traitement et extraction d’informations à partir de vastes ensembles de données.
2. Intelligence artificielle
o Algorithmes au cœur des technologies d'IA et d'apprentissage automatique .
3. Cybersécurité
o Développement d'algorithmes pour la détection des intrusions et la protection des
données.
1
2
 ALGORITHMIQUE Objectifs

[Link]/elearning-center

Aborder les notions spécifiques à

l'algorithmique
Comme:

• Affectation de variables
• Instructions d'Entrées\Sorties
• Schémas Conditionnels
• Schémas Itératifs
• Utilisation de Tableaux
• Langage Pseudo Code.

2
 DÉFINITION ET STRUCTURE Concepts
D’UN ALGORITHME Généraux
[Link]/elearning-center
• Algorithme : Suite d’étapes logiques et structurées élaborées dans le but
Définition de résoudre un problème donné.
• Il doit terminer après un certain nombre de séquences bien défini.
• La maîtrise de l’algorithmique est primordiale avant de passer proprement à la
Intérêt programmation sur ordinateur.
• L’algorithmique exprime les instructions résolvant un problème donné
indépendamment des particularités de syntaxe propre à chaque langage.
• Pseudo-code : langage de programmation purement conventionnel et
Ecriture par
incompréhensible par un ordinateur.
Pseudo-Code
• Il nous permet de nous affranchir des problèmes de syntaxes propres à chaque
langage.
1. Trouver une idée maitresse pour solutionner le problème.
Méthodologie 2. S’assurer que la solution est bien compatible avec le résultat escompté.
3. Etablir une liste de toutes les variables mises en jeu, pour solutionner le
problème.
4. Affecter à chaque variable un nom significatif.
5. Détailler les étapes de l’algorithme, et si besoin, décomposer les étapes en
sous étapes.
6. Ajouter des commentaires à chaque étape (facultatif).
3
7. Exécuter l’algorithme 4
 DÉFINITION ET STRUCTURE
Exercice
D’UN ALGORITHME
[Link]/elearning-center
Afficher le résultat de passage des étudiants d’une classe de 20 en se basant sur la
Enonce moyenne de leurs deux notes écrites (N1) et orales (N2). Si la moyenne est
supérieure ou égale à 10 l’étudiant est déclaré admis. Dans le cas contraire, il est
déclaré non admis.
Initialisation

i 1
Solution tant que (i < = 20) Lecture
{1
lire (Nom, N1, N2)
Affichage
Boucle Moy  (N1 + N2) / 2
si (Moy > =10 ) alors {afficher (Nom, ‘Admis’)}
sinon {afficher (Nom, ‘non Admis’)}
i  i+1
Affectation
}2

1 Debut de boucle Test

2 Fin de boucle Incrémentation

4
5
 DÉFINITION ET STRUCTURE Operations
Exemple de
D’UN ALGORITHME base
[Link]/elearning-center

1. AFFECTATION DE VARIABLES : Comme l’instruction : Moy  (N1 + N2) / 2 .

Si on attribue à une variable une valeur de départ on dit qu’on a une initialisation
2. LECTURE : Comme l’instruction lire (Nom, N1, N2). Utile lorsque le programmeur
doit donner une valeur. Dans le cas étudié, l’utilisateur introduit une valeur de type
chaîne de caractères (nom) et deux valeurs de type réel.
3. ECRITURE : Comme l’instruction afficher (Nom, ‘Admis’.)
Utile lorsque le programmeur doit afficher la valeur d’une variable.
4. TEST ( L'INSTRUCTION si ... alors ... sinon...)
Comme montré dans l’exemple. On l'utilise lorsqu’on a une condition.
Si cette dernière est vérifiée, alors on a l’instruction 1
sinon on a l’instruction 2 (fig1). Le sinon est parfois optionnel et non nécessaire (fig2).
Généralement, on peut avoir les deux cas de figures :
Cas 1 Cas 2
si (condition) alors {instr1} si (condition) alors {instr1}
Sinon {instr2}
Ex1 Ex2
si (x>=0) alors {y  racine(x)} si (x>=0) alors {y  racine(x)}
sinon{afficher(" Impossible")}

5
Instr 1 et instr 2 peuvent être un bloc d’instructions. 6
 DÉFINITION ET STRUCTURE Operations de
D’UN ALGORITHME base
[Link]/elearning-center
Condition testée avant d'exécuter le bloc de code. Si elle n’est pas vérifiée, on ne
rentre pas dans la boucle et le bloc ne sera pas exécuté.
5. Boucles
i 1

tant que
tant que (i < = 20)

Boucle
Pseudo – Code :
• Une boucle est utilisée quand on désire éviter {lire (Nom, N1, N2)
la répétition d'une même partie de code. Il Moy (N1 + N2) / 2
tant que (expression vraie)
existe 3 types de boucles principaux. si (Moy > =10 ) alors {Afficher (Nom, ‘Admis’)}
{
BLOC D'INSTRUCTIONS sinon {Afficher (Nom, ‘non Admis’)}
i i+1}
• Si dans leur finalité elles conduisent au même }
résultat, elles restent cependant différentes Le test se faisant après, le bloc est exécuté au moins une fois

repeter ...tant que

dans leur formulation . Pseudo – Code : i 1
Répéter

Boucle
Répéter {lire (Nom, N1, N2)
{ Moy (N1 + N2) / 2
BLOC D'INSTRUCTIONS si (Moy > =10 ) alors {Afficher (Nom, ‘Admis’)}
} sinon {Afficher (Nom, ‘non Admis’)}
tant que (expression vraie) i i+1}
Tant que (i < = 20)
utilisée généralement lorsque le nombre des itérations (répétitions) est connu.

Pseudo – Code : Pour (i 1, i<=20, i i+1)

Boucle

{Lire (Nom, N1, N2)

for

Pour(init, critere cont, Moy (Note1 + Note2) / 2

modif) Si (Moy > =10 ) alors {afficher (Nom, ‘Admis’)}
6 {BLOC D'INSTRUCTIONS} sinon {afficher (Nom, ‘non Admis’)}
} 7
 ALGORITHMIQUE Exercices

[Link]/elearning-center

EXERCICE 1:
1. Ecrire un algorithme qui affiche le plus grand et le plus petit de
deux éléments entiers a et b.
2. Ecrire un algorithme qui affiche le plus grand et le plus petit de
trois éléments entiers a,b et c.
EXERCICE 2:
1. Ecrire un algorithme qui permet de résoudre ax + b = 0
2. Ecrire un algorithme qui permet de résoudre ax2 + bx + c = 0.
EXERCICE 3:
Soit S = 1 + 1/2 + 1/3 + 1/4 + 1/5 + ........ + 1/999 + 1/1000
Ecrire un algorithme qui calcul S par les diverses méthodes suivantes :
1. En utilisant la structure tant que et en additionnant les termes de
gauche à droite.
2. en utilisant la structure répéter.. Tant que et en additionnant les
termes de droite à gauche.
3. En utilisant la structure pour… et en additionnant séparément les
termes positifs et négatifs chacun de gauche à droite.
4. Modifier l’algorithme pour calculer : 7
S=1 - 1/2 + 1/3 - 1/4 + 1/5 + ........ + 1/999 - 1/1000
 ALGORITHMIQUE Exercices

[Link]/elearning-center

EXERCICE 4:
Début
{P1
Terme 1
I 1
Lire (x)
Tant que (I <= 20)
{AI
Terme  Terme * x/A
P  P + Terme
I  I + 1}
afficher (I,P)
} fin
Quel est le but de cet algorithme ?
EXERCICE 5:
Ecrire un algorithme qui permet de trouver le nombre de termes de la
série nécessaire pour le dépassement d’une valeur arbitraire Val tel
que : 1 + 1/2 + 1/3+ ........+ 1/N >= Val
8
 ALGORITHMIQUE Exercices

[Link]/elearning-center

EXERCICE 6:
• Ecrire un algorithme qui lit une série de nombres dont la fin sera
indiquée par un nombre négatif puis donner le plus grand et le plus
petit de ces nombres.
• Ecrire un algorithme qui lit une série de nombres dont la fin sera
indiquée par l’introduction de deux nombres consécutifs égaux. Le
programme doit aussi afficher le plus grand et le plus petit de ces
nombres.

EXERCICE 7
Soit N un entier naturel.
• Ecrire un algorithme qui affiche le nombre de ses diviseurs.
• En déduire s’il est premier
• Ecrire un algorithme qui affiche l’ensemble de ses diviseurs

9
 ALGORITHMIQUE Exercices

[Link]/elearning-center

EXERCICE 8
Méthode 1 : (algorithme classique basé sur la recherche des diviseurs)
Soit a et b deux entiers naturels.
Écrire un algorithme qui donne PGDC (a,b)
Méthode 2 : (algorithme d’Euclide)
L’algorithme d’Euclide, qui détermine le PGCD de 2 nombres naturels a et b est basé
sur le principe suivant :
si un des nombres est nul, l'autre est le PGCD. sinon il faut soustraire le plus petit
du plus grand et laisser le plus petit inchangé. Puis, on recommence ainsi avec la
nouvelle paire jusqu'à ce qu’un des deux nombres soit nul. Dans ce cas, l'autre
nombre est le PGCD.
Méthode 3 : Il est possible de déterminer le PGCD de 2 nombres naturels a et b
en utilisant les propriétés suivantes. On prendra au départ PGCD = 1
si a et b sont pairs: PGCD = PGCD*2
a=a/2
b=b/2
si a est pair et b impair: a=a/2
si a est impair et b pair: b=b/2
si a et b sont impairs: a=a-b si a>=b
b=b-a si b>a
si a=0: PGCD = PGCD * b 10
si b=0: PGCD = PGCD *