FORMATION Cours d'algorithme pour les débutants

Chapitre I : Notion d’algorithme​

I- Généralités :
Avant d’aborder le concept d’algorithme il est important de préciser le contexte de son utilisation :
· Utilisé en informatique.
· Traitement de l’information (Fonction de base de l’informatique).

1- L’informatique ? Pourquoi ? :
Travaux répétitifs, lents et dangereux ==> exigent une grande précision ==> incompatible avec la nature humaine ==>l’ordinateur.

2- Traitement de l’information :
On entend par traitement de l’information la manipulation d’une entité ayant un sens.
Exemple : la somme de deux entiers 21 et 36 est un traitement de l’information, 21 et 36 sont des informations sur lesquelles se fera le traitement d’addition.

2.a- Traitement semi-automatique :
L’utilisation d’une calculatrice simple met en évidence trois fonctions principales :
· Une fonction d’entrer de données,
· Une fonction de traitement de données,
· Une fonction de sortie des résultats.

Bonjour visiteur, Merci de vous Inscrire ou de vous connectez pour voir les liens!

​

Si une action est composée, elle met en jeu plusieurs actions élémentaires, l’opérateur établit d’abord un plan de son calcul, c.à.d. qu’il décompose l’action composée en une suite d’opérations simples qu’on peut mémoriser sur un support quelconque, puis il suit le plan en utilisant éventuellement ce support pour mémoriser les résultats intermédiaires qui seront réutiliser dans la suite du calcul.

Exemple : ( 2 + 7/3 )*6

Plan évaluation_expression
Début

Diviser 7 par 3
Ajouter 2 au résultat
Multiplier le résultat par 6​

Fin

2.b- Traitement automatique :
Dans le type précédé il n’y avait d’automatique que l’exécution des opérations plan, leur enchaînement est assuré par l’opérateur, pour que la machine puisse exécuter automatiquement le plan il faut :

· Une fonction de mémorisation des actions de données et des résultats intermédiaires.
· Une fonction de séquencement (enchaînement des actions élémentaires) les actions sont exécutées les unes après les autres selon un certain plan, le choix d’une action peut dépendre du résultat des actions précédentes. Ce plan d’exécution est ce qu’on appelle « programme ».

Bonjour visiteur, Merci de vous Inscrire ou de vous connectez pour voir les liens!

​

Mémoire :
Mémoire principale (centrale) :
· Est une mémoire intégrée à l’ordinateur.
· A la fin du travail les informations sont perdues.
· Elle est constituée d’une suite d’emplacement (numéroté de 0 à nombre total) dont chacun peut contenir une certaine information.
· L’adresse associée à un emplacement est utilisée par le processeur (unité de traitement est de séquencement) pour accéder à un emplacement pour voir son contenu (Lecture) ou pour y mettre une information (Ecriture).
· Un emplacement est une suite d’élément binaire (Bits). Un bit est égal à 0 ou 1.

Mémoire secondaire :
· C’est une mémoire externe connectable à un ordinateur ( Bande, Disquette, Disque, …), chacune de ces mémoires à ses propres caractéristiques de capacité et d’utilisation.
· Un ordinateur peut avoir un nombre quelconque de ces mémoires.
· Elle complète la mémoire centrale en conservant les informations qu’elles ne peuvent y être conservées parce qu’elles sont : Volumineuses et permanentes.
· La communication entre la mémoire centrale et la mémoire secondaire est réalisée par les fonctions entrer/sortie.

Fonction d’entrer/sortie :
Les fonctions d’entrer/sortie sont les deux seules fonctions permettant la communication de l’ordinateur avec son entourage.

Entrer : transfert des informations d’une mémoire secondaire ou d’un dispositif d’entrer au mémoire centrale.

Sortie : transfert des informations d’une mémoire centrale au mémoire secondaire à un dispositif de sortie.

3- Résolution d’un problème par ordinateur :
Pour résoudre un problème par ordinateur on prépare un plan de sa solution, et on le soumit à un ordinateur, l’ordinateur mémorise le plan et exécute les actions les unes après les autres en conservant les résultats intermédiaires dans sa mémoire, le résultat final sera donné en sortie.

Méthode de résolution d’un problème :
Soit à résoudre une équation de 2nd degré Ax² + Bx + C = 0 avec A, B, C et X des réels et A ¹ 0.
Il est déconseillé d’essayer de trouver une solution directement pour tout problème complexe, il faut toujours le décomposer en sous problèmes plus élémentaires, les résoudre séparément, et composer la solution finale de ces sous solutions.

Décomposition du problème :
· Fixer A, B et C.
· Calculer delta.
· Discussion du delta et calcul des racines.

Fixation de A, B et C :
Ces objets sont les paramètres de notre problème. Pour fixer la valeur d’un objet, on utilise (pour le moment) un plan prédéfini « LIRE » qui consiste à affecter à un objet une valeur donnée par l’utilisateur.

Plan FixerABC

A, B, C sont des réels ​

Début

LIRE(A)
LIRE(B)
LIRE(C) ​

Fin

Calcul du delta :

Plan Delta

A, B, C, Delta sont des réels ​

Début

Delta = B*B – 4 * A * C ​

Fin

Discussion du delta et calcul des racines :

Plan Racines

A, B, C, Delta, X1, X2 sont des réels ​

Début

Si Delta < 0 alors

Ecrire("Pas de solution réelle")​

Sinon

Si Delta = 0 alors

Début

X1 = - B / (2 * A )
Ecrire ("Racine double X = ", X1) ​

Fin​

Sinon

Début

X1 = (- B + sqrt(delta)) / (2 * A) // sqrt = racine carrée
X2 = (- B - sqrt(delta)) / (2 * A)
Ecrire (X1, X2) ​

Fin ​

Fin


Solution finale :

Plan Equation

A, B, C, Delta, X1, X2 sont des réels ​

Début

LIRE(A,B,C) // {1er Plan}
Delta = B*B – 4 * A * C // {2ème Plan}
Si Delta < 0 alors // {3ème Plan}

Ecrire("Pas de solution réelle")​

Sinon

Si Delta = 0 alors

Début

X1 = - B / (2 * A )
Ecrire ("Racine double X = ", X1) ​

Fin​

Sinon

Début

X1 = (- B + sqrt(delta)) / (2 * A)
X2 = (- B - sqrt(delta)) / (2 * A)
Ecrire (X1, X2)​

Fin ​

Fin

Remarques :
1. Chaque problème met en jeu un certain nombre d’objets, et pour chaque objet on pourra faire correspondre :
· Un nom : qui permettra de le désigner dans la description du traitement.
· Un type : indiquant la nature de cet objet.
· Une valeur : affectée à cet objet à un instant donné.

2. Les phrases comprises entre accolade ouvrante et accolade fermante n’ont d’autre signification que l’explication pure et simple des effets des actions.

II- Définition d’un algorithme :
Suite finie d'opérations élémentaires constituant un schéma de calcul ou de résolution d'un problème.
L’algorithme est l’unique moyen actuel pour résoudre un problème par un ordinateur.
Un algorithme exprimé en un langage d’ordinateur est appelé programme, ainsi les langages des ordinateurs sont appelés langages de programmation.
Programmer c’est savoir soumettre à un ordinateur une séquence de directives ou d’instructions en vue de résoudre un problème donné.

III- Structure d’un algorithme :
De l’exemple précédent on peut déduire la structure suivante :
· En-tête de l’algorithme.
· Partie déclarative.
· Partie actions ou corps de l’algorithme.

1- En-tête de l’algorithme :
Il permet de donner un nom a l’algorithme ; Il est constitué du mot clé Algorithme, suivi d’un identificateur.
Syntaxe : Algorithme <Identificateur>
Identificateur : C’est une chaîne de caractères indiquant le nom de l’algorithme.

2- Partie déclarative :
La partie déclarative peut contenir différentes sortes de déclarations ; elle est délimitée par l’en-tête de l’algorithme et le mot réservé « Début ». Dans cette partie on décrit la structure et les propriétés des objets.

3- Partie action ou corps de l’algorithme :
Cette partie contient les différents traitements ou actions que vont subir les différents objets du problème, ainsi que l’affichage des résultats. Elle est délimitée par le mot réservé « Début » et le mot réservé « Fin » .

Algorithme <Identificateur>

<Partie Déclaration>

Début

<Partie Action>

Fin.

Exemple : Ecrire un algorithme qui fait la somme de deux nombres entiers.


Algorithme Somme

A, B, S sont des entiers ​

Début

Lire (A)
Lire (B)
S = A + B
Ecrire (S) ​

Fin

Bonne lecture.

 

Chapitre II : Représentation d’un algorithme​

I- Enchaînement d’actions :

Exemple :

Il s’agit de définir le processus qui nous permet de calculer le quotient Q et le reste R de la division de deux entiers positifs A et B. On suppose que nous ne savons pas diviser deux nombres et que nous ne disposons pas d’une machine susceptible de le faire, cependant il faut faire des hypothèses et supposant que nous savons :

- Lire un nombre ou une suite de nombres
- Comparer deux nombres
- Additionner un nombre à un autre
- Soustraire un nombre d’un autre
- Imprimer un nombre
- Nous arrêtons
- Répéter une opération ou une suite d’opérations

Trouver l’algorithme de la division consistera à enchaîner une suite d’opérations de base à effectuer pour déterminer Q et R connaissant A et B.

Supposant que A = 13 et B = 4.



Trouver Q et R de la division de A par B se ramène donc à :

- Lire deux nombres A et B
- Soustraire B de A autant de fois que possible
- Q égale le nombre de soustractions effectuées
- R égale le résultat de la dernière soustraction



L’algorithme de cet enchaînement est le suivant :

Algorithme division

A, B, Q, R sont des entiers ​

Début

Lire (A, B) // {Fixation de A et B}
Q = 0 // {Initialisation de Q }
Tantque A >= B faire
Début

A = A – B // {Soustraction B de A}
Q = Q + 1 // {Incrémentation de Q}​

Fin
R = A
Ecrire (Q,R) {Affichage de Q et R}​

Fin.

II- L’instruction d’affectation :

Syntaxe : <identificateur> = <expression>

Exemple :

A = 25
Delta = B*B – 4*A*C​

III- Les opérations de lecture et d’écriture :

1- L’instruction d’entrée : L’instruction Lire permet la lecture des variables d’entrée.

Syntaxe : Lire (Liste_de_variables)

Liste_de_variables : une ou plusieurs variables séparées par des virgules.

Exemple :

Lire(a,b) // L’algorithme demande à l’utilisateur les valeurs de a et b.​

2- L’instruction de sortie : L’instruction Ecrire permet l’affichage des résultats ou des messages.

Exemple :

Ecrire (Delta) // Affiche la valeur de delta.
Ecrire (‘C’EST UN MESSAGE’) // Affiche : C’EST UN MESSAGE.

X1 = 20 ; X2 = - 6
Ecrire (‘Les racines sont : ‘, X1,’et ‘, X2) // Affiche : Les racines sont : 20 et - 6​

Bonne Lecture.

 

Chapitre III : Structures algorithmiques​

I- Introduction :
Dans un algorithme les instructions sont exécutées séquentiellement, c. à d. dans l’ordre où elles apparaissent. Or, la puissance d’un algorithme, provient essentiellement :
- De la possibilité d’effectuer des choix, autrement dit d’avoir un comportement qui puisse dépendre des résultats intermédiaires.
- De la possibilité de répéter l’exécution d’une série d’instructions.

II- Les structures de contrôle :
1- Le branchement (Aller à) (GOTO):
Cette instruction permet un saut vers une ligne (antérieure ou postérieure) indiquée par une étiquette.

Syntaxe :

GOTO <Nom de l'étiquette>
.........................
<Nom de l'étiquette> :
<Code de l'étiquette>​

Exemple :
Algorithme Etiquette
Début

Aller à 1
A :
…………
…………
1 :
…………
…………
Aller à A
………… ​

Fin.

Pour plus d'informations :

Bonjour visiteur, Merci de vous Inscrire ou de vous connectez pour voir les liens!

2- Le choix :
a- Structure alternative :

Si <Condition> Alors

<Bloc d’instruction 1>​

Sinon

<Bloc d’instruction 2> ​

Fin​

Condition : c’est une expression logique simple ou composée avec des opérateurs logiques ET, OU et NON.
La condition doit être exprimée de manière à n’offrir que deux réponses possibles : OUI / NON. Si la réponse est OUI le Bloc d’instruction 1 qui suit le symbole ALORS est exécuté. Si la réponse est NON le Bloc d’instruction 2 qui suit le symbole SINON est exécuté.

Il peut arriver qu’il n’y a pas d’instruction à exécuter si la condition est fausse, alors la structure alternative s’exprime par :

Si <Condition> Alors

<Bloc d’instruction> ​

Fin​

Exemple : Ecrire un algorithme qui affiche la plus petite valeur de deux nombres entiers.

Algorithme Min2Val
A, B sont des entiers
Début

Lire (A,B)
Si A<B alors

Ecrire (‘La plus petite valeur est ‘,A)​

Sinon

Ecrire (‘La plus petite valeur est ‘,B)​

Fin​

Fin.

Autre solution :

Algorithme Min2Val
A, B, Min sont des entiers
Début

Lire (A,B)
Min = A
Si Min > B alors

Min = B​

Fin
Ecrire (‘La plus petite valeur est ‘,Min)​

Fin.

Tests emboîtés :
Dans certaines applications les branches d’une structure alternative peuvent faire appel à une autre division. Par exemple si après avoir identifié l’âge d’une personne, les personnes aux yeux bleus et les personnes aux yeux noirs doivent également être identifiés, on aura alors recours à une deuxième alternative dans l’une ou bien dans les deux branches de la première.

Exemple : Ecrire un algorithme qui détermine et affiche le maximum de trois nombres entiers.
1. Lecture des données
2. Recherche de la plus grande valeur par comparaison de paire
3. Impression de la valeur trouvée.

Algorithme Max3Val
A, B, C, Max sont des entiers
Début

Lire (A,B,C)
Si A>B alors

Si A>C alors

Max = A​

Sinon

Max = C​

Fin​

Sinon

Si B>C alors

Max = B​

Sinon

Max = C ​

Fin​

Fin
Ecrire (‘La plus grande valeur est ‘,Max)​

Fin.

Pour plus d'informations :

Bonjour visiteur, Merci de vous Inscrire ou de vous connectez pour voir les liens!

b- Structure multiple (Choix) (Selon):
Les tests simples permettent de réaliser, au mieux, un choix parmi deux possibilités. Il est parfois utile d’effectuer des traitements variés en fonction de cas beaucoup plus nombreux. On utilise alors le concept de tests multiples qui permettent de comparer un objet à toute une série de valeurs et d’exécuter, en fonction de la valeur effective de l’objet, différents blocs d’instructions.

Syntaxe :

Choix <Expression>

Cas1 : <Bloc d’instruction 1>
Cas2 : <Bloc d’instruction 2>
…………
CasN : <Bloc d’instruction N>
Autres Cas : <Bloc d’instruction> ​

Fin ​

Exemple : Ecrire un algorithme de calcul d’un prix TTC à partir des données suivantes :
- Prix hors taxe,
- Code TVA :

A pour 7 %
B pour 12,32 %
C pour 18,6 %
D pour 33,33 %​

L’algorithme affichera la valeur du taux de TVA et le prix TTC correspondant. Dans le cas où l’utilisateur fournit un code incorrect, l’algorithme proposera C comme réponse par défaut et il affichera un message précisant cette décision.

Algorithme CalculTTC
Prix, TTC, TVA sont des réels
Code est un caractère
Début

Ecrire (‘Entrer le prix hors taxe : ‘)
Lire (prix)
Ecrire (‘Entrer le code associé pour appliquer le taux TVA :’)
Lire (code)
Selon code

Cas ‘A’ : TVA = 7
Cas ‘B’ : TVA = 12,32
Cas ‘C’ : TVA = 18,6
Cas ‘D’ : TVA = 33,33
Autres Cas :

Début

Ecrire (‘Vous avez entré un code erroné, le taux qui va être appliqué c’est le taux correspondant au code C’)
TVA = 18,6​

Fin​

Fin
TTC = Prix + Prix * TVA / 100
Ecrire (‘Le taux TVA = ’, TVA)
Ecrire (‘Le prix TTC = ’, TTC) ​

Fin.

Pour plus d'informations :

Bonjour visiteur, Merci de vous Inscrire ou de vous connectez pour voir les liens!

A Suivre ...​

Bonne Lecture.

 

Suite Chapitre III : Structures algorithmiques​

3- Les structures de répétition (Itération) :
Une répétition consiste à exécuter une ou plusieurs instructions un certain nombre de fois. On parle alors de boucle. D’une manière générale, il existe deux façons de répéter des instructions :

- D’une manière conditionnelle (on dit aussi indéfinie) : la poursuite ou l’abandon de la répétition sont conditionnés par ce qui se passe au sein de la boucle.
- D’une manière inconditionnelle (on dit aussi définie) : les instructions sont répétées un nombre de fois bien déterminé.

3.1- Répétition conditionnelle :
a- Boucle TANTQUE :
Syntaxe :

Tantque <Condition> faire

<Action>​

Fin​

<Condition> : est une expression logique.
<Action> : peut être une action élémentaire (simple) ou une action composée. Elle se répète tant que la condition est vraie, et s’arrête dés qu’elle soit fausse.

Exemple :

Tantque (la cloche n’a pas sonné) faire

Étudier​

Fin.​

L’exécution de cette boucle se déroule comme suit :
a- Evaluation de la condition
b- Décision de répétition ou d’arrêt :

Si la condition est vraie alors on exécute l’action étudier et on reprend à partir de a. Si la condition est fausse alors l’action de répétition se termine.

Remarque : Un grave problème peut se poser de cet exemple. Si la cloche ne sonne jamais, la condition de répétition restera infiniment vraie. L’action étudier sera répété infiniment.

Changeons l’exemple :

Tantque (la cloche n’a pas sonné) faire

Étudier 2 heures​

Fin​

On peut croire que cette action il faut étudier 2 heures et terminer l’action de répétition. Ce n’est pas le cas. L’exemple c’est le même que le précédent sauf que le test de la condition se fera après chaque 2 heures.

Changeons l’exemple :

Tantque (la cloche n’a pas sonné) et (l’heure < 19h) faire

Etudier​

Fin​

La condition est composée de 2 conditions logiques reliés par l’opérateur « et ». Cette condition est fausse si l’une des conditions est fausse.
L’action étudier pourra donc être interrompue par la sonnerie de la cloche ou par l’heure. Nous sommes donc sur de l’arrêt de l’action.

Exemple : Ecrire un algorithme qui calcule la somme arithmétique S = 1 + 2 + 3 + … + N.
- Fixer la valeur de N
- Initialement la somme égale 0
- La première valeur de la suite égale 1
- Pour chaque nouvelle valeur de la suite on l’ajoute à la somme cumulée
- Ecrire la somme.

Algorithme somme
N, I, S sont des entiers
Début

Lire (N)
S = 0
I = 1
Tantque I<=N faire

S = S + I
I = I + 1​

Fin
Ecrire (S)​

Fin.

Pour plus d’informations :

Bonjour visiteur, Merci de vous Inscrire ou de vous connectez pour voir les liens!

b- Boucle Répéter :
Dans la boucle Tantque, la condition est évaluée avant d’exécuter la première instruction. Certains cas exigent le contraire, c’est à dire, l’évaluation de la condition se fait après l’exécution de la dernière instruction de la boucle. Un tel algorithme correspond à une boucle répéter et s’écrit ainsi :

Syntaxe :

Répéter

<Action> ​

Jusqu’à <Condition> ​

L’action à l’intérieur de la boucle sera répétée jusqu’à ce que la condition soit vraie. Au contraire de la boucle Tantque, l’utilisation d’une boucle répéter garantie que l’action sera exécutée au moins une fois puisque le test a lieu après son exécution.

Exemple : Ecrire un algorithme qui pour chaque couple (A, B : entier) imprime sa somme ; le dernier couple est égale à (0, B).

Algorithme addition
A, B, Somme sont des entier
Début

Lire(A,B)
Si A<> 0 alors

Répéter

Somme = A+B
Ecrire (A,’+’,B,’=’,Somme)
Lire(A,B) ​

Jusqu’à A=0 ​

Fin​

Fin.

3.2- Répétition inconditionnelle :
La boucle POUR :
De nombreux problèmes exigent une boucle itérative ne nécessite pas l’emploi de la structure Tantque ou la structure répéter. A la place on utilise la structure répétitive Pour. La syntaxe de cette boucle est la suivante :

Syntaxe :

Pour <identificateur> = <valeur initiale> à <valeur finale> faire

<Action>​

Fin​

<identificateur> : C’est une variable de contrôle de type ordinal.
<valeur initiale> et <valeur finale> peuvent être des constantes ou des expressions.

On utilise une variable de contrôle de boucle dont le rôle consiste à contrôler le nombre d’itérations de la boucle. A chaque itération la variable de contrôle prend une nouvelle valeur automatiquement et séquentiellement. La liste de valeurs contient généralement une série d’entiers négatifs, positifs ou les deux en ordre croissant ou décroissant. La boucle se termine lorsque cette liste de valeurs est épuisée.

Remarque : il est possible d’utiliser la variable d’itération à l’intérieur de la boucle dans toute instruction du moment que celle-ci ne modifie pas sa valeur.

Exemple :
Écrire un algorithme qui pour chaque couple (A, B : entier) imprime sa somme ; le nombre de couples est connu.

Algorithme addition
Var A, B, Somme, nbrcouples, I sont des entiers
Début

Lire(nbrcouples)
Pour I = 1 à nbrcouples faire

Lire(A,B)
Somme = A+B
Ecrire (A,’+’,B,’=’,Somme)​

Fin​

Fin.

Pour plus d’information :

Bonjour visiteur, Merci de vous Inscrire ou de vous connectez pour voir les liens!

III- Les expressions logiques :
Les expressions logiques sont des expressions simples réunies entre elles par les opérateurs ET, OU et NON.

• 0 = Faux
• 1 = Vrai

- L’opérateur logique ET placé entre deux conditions donne la valeur vraie si les deux conditions qui l’encadrent sont vraies.

​

- L’opérateur logique OU placé entre deux conditions donne la valeur vraie si au moins une des deux conditions est vraie.

​

- L’opérateur logique NON placé devant une condition donne la valeur vraie si la condition est fausse et la valeur fausse si la condition est vraie.

​

Exemple :
Écrire un algorithme qui détermine et affiche le maximum de trois nombres entiers.
La solution qu’on a vu consiste à effectuer des comparaisons emboîtées. Ces emboîtements peuvent être éliminés grâce aux expressions logiques.

Algorithme Max3val
A, B, C, Max sont des entiers
Début

Lire (A, B, C)

Si (A>B) et (A>C) alors

Max = A​

Fin

Si (B>A) et (B>C) alors

Max = B​

Fin

Si (C>A) et (C>B) alors

Max = C​

Fin

Ecrire (‘La plus grande valeur est :’ Max)​

Fin.

On remarque que les emboîtements ont été éliminés et l’algorithme est devenu plus facile à comprendre. On peut noter aussi que tous les tests sont effectués. Pour éviter l’exécution de tous les tests on écrit l’algorithme comme suit :

Algorithme Max3val
A, B, C, Max sont des entiers
Début

Lire (A, B, C)
Si (A>B) et (A>C) alors

Max = A​

Sinon

Si (B>A) et (B>C) alors

Max = B​

Sinon

Si (C>A) et (C>B) alors

Max = C​

Fin​

Fin​

Fin
Ecrire (‘La plus grande valeur est :’ Max)​

Fin.

Bonne Lecture.