Partie 1.
Concepts de base de l’algorithmique
COURS 1 : Une introduction à l'algorithmique
COURS 2 : Inconvénients du langage naturel
COURS 3 : Structures de contrôle, introduction à la notion de variable.
COURS 4 : Objets, notion d’affectation et structure d’un algorithme
Partie 1.
Concepts de base de l’algorithmique
COURS 1 : Une introduction à
l'algorithmique 
1.1 Introduction
L'utilisation d'un ordinateur pour la résolution d'une application ( travail que l'on soumet à un ordinateur ) nécessite tout un travail de préparation. N'ayant aucune capacité d'invention, l'ordinateur ne peut en effet qu’exécuter les ordres qui lui sont fournis par l'intermédiaire d'un programme. Ce dernier doit donc être établi de manière à envisager toutes les éventualités d'un traitement.
1. 2 Mise en œuvre d'une application
Plusieurs étapes sont nécessaires pour mettre en œuvre une application :
Etape 1 : Définition du problème
Il s’agit de déterminer toutes les informations disponibles et la forme des résultats désirés.
Etape 2 : Analyse du problème
Elle consiste à trouver le moyen de passer des données aux résultats. Dans certains cas on peut être amené à faire une étude théorique. Le résultat de l’étape d’analyse est un algorithme. Une première définition d’un algorithme peut être la suivante :
‘On appelle algorithme une suite finie d'instructions indiquant de façon unique l'ordre dans lequel doit être effectué un ensemble d'opérations pour résoudre tous les problèmes d'un type donné.
Sachez aussi qu’il existe des problèmes pour lesquels on ne peut trouver une solution et par conséquent il est impossible de donner l’algorithme correspondant.
Etape 3 : Ecriture d'un algorithme avec un langage de description algorithmique.
Une fois qu’on trouve le moyen de passer des données aux résultats, il faut être capable de rédiger une solution claire et non ambigu�. Comme il est impossible de le faire en langage naturel pour les raisons que nous donnerons par la suite, l’existence d’un langage algorithmique s’impose.
Etape 4 : Traduction de l'algorithme dans un langage de programmation.
Les étapes 1, 2 et 3 se font sans le recours de la machine. Si on veut rendre l’algorithme concret ou pratique, il faudrait le traduire dans un langage de programmation. Nous dirons alors qu’un programme est un algorithme exprimé dans un langage de programmation.
Etape 5 : Mise au point du programme
Quand on soumet le programme à la machine, on peut être confronté à deux types de problèmes :
-la machine corrige l’orthographe, c’est ce qu’on appelle syntaxe dans le jargon de la programmation.
-la machine traduit le sens exprimé par le programme.
Si les résultats obtenus sont ceux attendus, la mise au point du programme se termine.
Si nous n’obtenons pas de résultats, on dira qu’il y a existence des erreurs de logique. Le programme soit ne donne aucun résultat, soit des résultats inattendus soit des résultats partiels.
Dans ce cas, il faut revoir en priorité si l’algorithme a été bien traduit, ou encore est-ce qu’il y a eu une bonne analyse.
1.3 Exemples d'algorithmes
Exemple1
L’algorithme de résolution de l’équation ax2 + bx + c = 0 dans l’ensemble des réels est le suivant
| 1. Calcul du discriminant, soit delta 2. Si delta > 0 alors il ya deux solutions données par les formules : X1 = ( -b + racine carrée(delta) ) / 4ac X1 = ( -b - racine carrée(delta) ) / 4ac 3. Si Delta = 0 alors il y a une solution double donnée par la formule : X = -b / 2a 4. Si Delta < 0 alors il n'y a pas de solution dans l'ensemble des réels. |
Exemple 2
| 1. Donner une valeur arbitraire à X0 2. Calculer les valeurs X1, X2, ...Xn par la formule de récurrence : Xn+1 = ( 2 Xn + A/ Xn2 ) / 3 S'arrêter des que la différence entre deux termes consécutifs devient inférieure à une précision donnée. |
Autres exemples en bref : Recette de cuisine, Traçage de fonction, Ouverture d’un coffre
1.4 Quelques définitions du mot ‘algorithme’
On peut définir un algorithme comme suit :
- résultat d'une démarche logique de résolution d'un problème. C' est le résultat de l'analyse.
- procédé de calcul, qui permet à partir de données numérique et en suivant un plan de calcul très précis, d'obtenir le résultat d'un calcul.
- résultat de l’étape d'analyse
1.5 Propriétés
On peut énoncer les cinq propriétés suivantes que doit satisfaire un algorithme :
Généralité : un algorithme doit toujours être conçu de manière à envisager toutes les éventualités d'un traitement.
Finitude : Un algorithme doit s’arrêter au bout d'un temps fini.
Définitude :toutes les opérations d'un algorithmes doivent être définies sans ambigu�té
Répétetivité : généralement, un algorithme contient plusieurs itérations, c’est à dire des actions qui se répètent plusieurs fois.
Efficacité : Idéalement, un algorithme doit être conçu de telle sorte qu’il se déroule en un temps minimal et qu’il consomme un minimum de ressources.
COURS 2
:Inconvénients du langage naturel
2.1 Exemple 1
Si nous demandons à n élèves d’exprimer en langage naturel la solution de l’équation du second degré ax2 + bx + c = 0 il est clair que nous aurons n solutions différentes. Chaque élève utilise son propre vocabulaire, ses propres nominations, ses propres symboles.
Une solution possible serait :
| A, B, C <-- les
données Calculer le discriminant Cas o� il est >0 : x1, x2 = -b +/- Rac(Delta) / 4ac Cas o� il est nul : x1=x2 = -b/2a |
Seul le rédacteur connaît avec exactitude, l’interprétation des symboles qu’il utilise et même certaines tournures
Essayons de recenser quelques problèmes de la solution envisagée.
Le signe � veut dire implicitement pour le rédacteur introduire les données dans A, B et C.
Pour le rédacteur, le calcul du discriminant est évident. Par contre c’est un mot étrange, qui ne veut rien dire pour quelqu’un qui ne comment résoudre une équation du second degré.
On peut faire plusieurs remarques sur la ligne 3 :
Pour le rédacteur le mot ‘il’ se rapporte au discriminant.
Pour le rédacteur, l’écriture ‘x1, x2 = -b +/- Rac(Delta) / 4ac veut dire qu’il existe deux solutions x1 et x2 que l’on doit prendre alternativement le signe + ensuite le signe – par son écriture +/-. D’autre part, le rédacteur utilise la fonction Rac pour désigne la racine carrée. Enfin pour le rédacteur le signe ‘.’ Désigne multiplication.
Comment voulez-vous que l’on comprenne tout ça quand on ne connaît pas la technique de résolution d’une équation du second degré.
En résumé, nous constatons les faits suivants :
pour une solution donnée, il peut exister un ensemble presque illimité d’expressions différentes. Si n élèves, on a n solutions distinctes.
Pour chaque expression, on trouve des notations propres au rédacteur, ce qui entraîne des ambigu�tés et donc des interprétations différentes.
2.2 Exemple 2 : Supposons que nous voulions exprimer en langage naturel la résolution de la racine cubique.
Comme à priori nous connaissons pas la démarche à suivre, nous utiliserons le résultat mathématique suivant :
On démontre que la suite suivante converge vers la racine cubique d'un nombre positif A :
| Donner une valeur arbitraire à X0 Xn+1 = ( 2 Xn + A/ Xn2 ) / 3 test d'arrêt : valeur absolue ( Xn+1 - Xn) < � � étant la précision. |
Commençons dans un premier temps par dérouler le principe du calcul à la main ( ou avec une calculatrice ne possédant pas la racine cubique ) avec les valeurs suivantes :
A = 30 ; x0 = 3 ; � = 0.00005
Les détails de calcul sont présentés dans la table suivante :
N |
Xn |
(Xn)2 |
A/ (Xn)2 |
2Xn |
2Xn+A/(Xn)2 |
Xn+1 |
|Xn+1 – Xn| |
0 |
3 |
9 |
3.33 |
6 |
9.33 |
3.11 |
0.11 |
1 |
3.11 |
9.6721 |
3.1017 |
6.22 |
9.3217 |
3.10723 |
0.00277 |
2 |
3.10723 |
9.65487 |
3.10723 |
6.2144 |
9.32169 |
3.10723 |
0 .0000 |
3 |
3.10723 |
Un algorithme possible exprimé en langage naturel
| 1.
Introduction des données A = 30, x0 = 3 , � = 0.00005 2. Calcul de Xn+1 = ( 2 Xn + A/Xn2 ) / 3 3. Comparaison de valeur absolue de ( Xn+1 - Xn) et � 4. Si Valeur absolue( Xn+1 - Xn) > � reprendre le calcul en 2 sinon continuer 5. Imprimer le résultat |
En plus des inconvénients cités plus haut, on constate dans cet exemple la difficulté d'automatiser le principe de répétition
2.3 SynthèseQuelque soit l'algorithme, solution d'un problème donné, il doit être communiquer à l'ensemble. Ceci ne peut se faire en langage naturel pour les principales raisons suivantes :
- difficulté d'exprimer certaines idées telles que la répétitive.
- ambigu�té
- plusieurs façons d'exprimer la même solution avec risque d'interprétations différentes.
La solution est donc d’utiliser un formalisme, ensemble de convention, pour décrire un algorithme. Le Langage Algorithmique( L.A)
COURS 3
:Structures de contrôle, introduction à la notion de variable
Objectifs : Introduire les structures de contrôle du langage algorithmique et écrire des algorithmes en raisonnant sur des ‘ardoises’.
3.1 Structures de contrôle
Tous les algorithmes peuvent être exprimés par les tournures suivantes qu’on appelle structure de contrôle du fait qu’elles permettent de contrôler le déroulement des algorithmes.
Le séquencement
Exprime qu’un ensemble d’action est exécuté dans un ordre bien précis.
La répétitive :
Elle exprime qu’un ensemble d'actions se déroule plusieurs fois tant qu'une condition reste vérifiée.
| Tantque condition : act1 act2 .... actn Fintantque |
la condition constitue le critère d'arrêt.
La conditionnelle
Elle exprime qu’un ensemble d'actions est exécuté que si une condition est vérifiée.
| Si condition : act1 act2 .... actn Fsi |
L'alternative
Elle exprime un choix entre deux ensembles d'actions à exécuter selon la valeur d'une condition.
| Si condition : act1 act2 .... actn Sinon Actn+1 Actn+2 .... actn+p Fsi |
Remarque : chaque action peut être à son tour une répétitive, une conditionnelle ou une alternative.
3.2 Notion d’ardoisesLa propriété importante d’une ardoise est la possibilité d’écrire et d’effacer des informations continuellement. Ainsi une ardoise peut contenir une valeur à un moment donné et une autre plus tard dans le temps.
A tout ardoise on peut associer un nom, par exemple le nom de son propriétaire ( contenant).
On peut également lui associer un contenu, c’est ce qui est écrit à un moment donné.
Si A désigne le nom attribué à une ardoise, on désignera son contenu à un instant donné par (A).
3.3 ExemplesReprenons nos deux algorithmes ( équation du second degré et racine cubique) et donnons les algorithmes correspondant en utilisant :
les structures de contrôle
les ardoises
Equation du second degré
| Introduire les
données A, B et C Ardoise <-- B2 - 4.A.C SI (Ardoise ) > 0 : La première racine est -B + Racine(Ardoise) / 4 A.C La deuxième racine est -B - Racine(Ardoise) / 4 A.C SINON SI (Ardoise) = 0 Une racine double : -B / 2A SINON Pas de racine réelle FSI FSI |
Racine cubique
| Introduction les données A
= 30, x0 = 3 , � = 0.00005 Ardoise1 <-- X0 Ardoise2 <-- ( 2 (Ardoise1) + A/(Ardoise1)2 ) / 3 Ardoise3 <-- valeur absolue de ((Ardoise2) - (Ardoise1)) TANTQUE (Ardoise3) < � Ardoise1 <-- (Ardoise2) Ardoise2 <-- ( 2 (Ardoise1) + A/(Ardoise1)2 ) / 3 Ardoise3 <-- valeur absolue de ((Ardoise2) - (Ardoise1)) FINTANTQUE Restituer le résultat qui est dans Ardoise2. |
COURS 4
:Objets, notion d’affectation et structure d’un algorithme
Objectifs : définir les objets élémentaires manipulés par un algorithme, introduire la notion d’affectation et écrire des algorithmes complets.
4.1 Variable et constanteUn algorithme opère sur des objets. A tout objet est associé un nom qui permet de l'identifier de façon unique. C'est une suite de caractères alphanumériques dont le premier est alphabétique.
On distingue deux types d'objets :
- des objets qui peuvent varier durant le déroulement d'un algorithme : Variables( ardoises).
- des objets qui ne peuvent pas variés par le déroulement d'un algorithme : Constantes.
On peut répartir l'ensemble des objets en sous ensembles appelés classe ou type. Il existe 4 type standard :
ENTIER : l’ensemble des entiers relatifs
REEL : l’ensemble des réels
BOOLEEN : les valeurs Vrai et Faux
CAR : l’ensemble des chaînes de caractères.
En langage algorithmique, on définit les objets comme suit :
| CONST Type Nom= valeur VAR Nom1, Nom2, ... : Type |
Exemples
CONST REEL PI=3.14
VAR A, B , C : ENTIER
VAR X, Y : CAR
4.2 Expressions sur les objetsUne expression est une suite d’opérandes reliés par des opérateurs.
Une expression peut être
arithmétique : on utilisera les opérateurs +,-,/, *, **
logique : les opérateurs utilisés sont ET, OU, et NON
relationnelle : les opérateurs utilisés sont <, <=, >, >=, =, <>
4.3 Autres actions du langage algorithmique
Affectation
C’est l’opération de base. Elle permet d’affecter la valeur d’une expression calculable à une variable. On utilisera le symbole ‘:=’
Exemple : A := (B+C) /D
Lecture
Elle permet d’introduire les données dans les variables. Nous utiliserons l’opération
| LIRE(X, Y, …) |
Ce qui est équivalente à
X := première donnée
Y := deuxième donnée
Ecriture
Elle permet de restituer les résultats. Nous utiliserons l’opération
| ECRIRE( Expression1, Expression2, …) |
Un algorithme est composé de 2 parties :
- définition des données : en-tête
- corps de l'algorithme
l'en-tête précise
- le nom de l'algorithme
- définition des objets manipulés
Le corps est un ensemble d'actions ordonnées composé généralement de 3 parties:
- initialisations ( lectures, .. )
- itérations ( parcours d'un ensemble de donné)
- opérations finales ( écritures, .. )
La description algorithmique est la suivante
| Algorithme nom Var Définition des objets Debut Définition du corps Fin |
Remarquer dans les algorithmes qui suivent qu’on utilise plus la notion d’ardoise. C’est désormais une variable. Noter aussi qu’on utilise non plus les parenthèses pour désigner le contenu d’une variable. Une variable désigne contenant quand elle est à gauche du signe d’affectation et contenu quand elle figure dans une expression
Avec ces considération, on peut maintenant écrire des algorithmes complets.
| ALGORITHME Equation VAR A, B, C, DELTA : REEL DEBUT LIRE ( A, B, C) Delta := B**2 - 4*A*C SI Delta > 0 : Ecrire ( 'Première racine : ', -B + Racine(Delta) / 4* A*C Ecrire ( 'Deuxième racine : ', -B - Racine(Delta) / 4 *A*C SINON SI Delta = 0 Ecrire('Une racine double :', -B / ( 2*A) SINON Ecrire('Pas de racine réelle') FSI FSI FIN |
Racine cubique
| ALGORITHME
Racine_cubique VAR A, X0, Mu, Ancien, Nouveau, Difference : REEL DEBUT LIRE(A, X0, Mu) Ancien := X0 Nouveau := ( 2 Ancien + A/(Ancien)2 ) / 3 Difference := valeur absolue de (Nouveau - Ancien) TANTQUE Difference < Mu Ancien := Nouveau Nouveau := ( 2 Ancien + A/(Ancien)2 ) / 3 Difference := valeur absolue de (Nouveau - Ancien) FINTANTQUE Ecrire(Nouveau) FIN |
1. Exprimer en langage naturel les solutions des problèmes suivants :
la somme des N premiers naturels.
La somme des N premiers nombres impairs.
2. Proposer des conventions pour exprimer la répétitive et la conditionnelle.
3. Ecrire les corps des algorithmes suivants (en raisonnant sur les ardoises) :
- Calcul de la somme S = 1 + 2 + . . . + N pour N donné.
- Déterminer les N premiers termes de la suite définie par :
U0 = U1 = 1
Un = Un-1 + Un-2 pour n > 1
- Calcul de la somme des N premiers termes de la suite xi/ i pour x donné.
- Calcul de la somme x - x3/3 + x5/5 - .. en prenant N termes
5. Ecrire l'algorithme permettant de déterminer
- la somme des N premiers entiers naturels.
- la somme des N premiers nombres impairs.
6. Ecrire l'algorithme qui reconnaît si un nombre est premier ou non.
7. Ecrire un algorithme qui calcule la somme des N premiers nombres premiers.
8. Ecrire les algorithmes qui réalisent les fonctions suivantes :
- la somme 22 + 42 + 62 + ....... en prenant N termes.
- le PGCD de 2 entiers positifs A et B donnés.
- la factorielle d'un nombre A donné.
9. On dispose d'une machine qui ne sait qu'additionner. Écrire l'algorithme réalisant le produit de 2 nombres A et B donnés.