Apprendre l’algorithmique structures de contrôle, introduction à la notion de variable, tutoriel & guide de travaux pratiques algorithmes en pdf.

Inconvénients du langage naturel

Objectifs : sur deux exemples, montrer les inconvénients des langages naturels, pour s’en convaincre de la nécessité d’un formalisme algorithmique pour la rédaction des solutions.
Exemple 1
Si nous demanderons à n élèves d’exprimer en langage naturel la ré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 :
1. A, B, C <—- les données
2. Calculer le discriminant
3. Cas où il est > 0 : x1, x2 = -B +- Rac(Delta) / 4 A.C
4. Cas ou il est nul : x1 = x2 = -B / 2A
Seul le rédacteur connaît avec exactitude l’interprétation des symboles et même de certaines
tournures qu’il utilise.
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 sait comment résoudre une solution 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) / 4 A.C » veut dire qu’il existe deux solutions x1 et x2 et que l’on doit prendre alternativement le signe + ensuite – par son écriture +-. D’autres part, le rédacteur utilise la fonction Rac qui veut dire racine carrée. De plus, pour le rédacteur le signe « . » désigne la 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,
– dans 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.
Exemple 2
Supposons que nous voulions exprimer en langage naturel la résolution de la racine cubique.
Comme à priori, on ne connaît 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 :
Un algorithme possible exprimé en langage naturel serait :
1. Introduction des données
A = 30, x0 = 3 , μ = 0.00005, n = 1
2. Calcul de Xn+1 = ( 2 Xn + A/Xn2 ) / 3
3. Comparaison de la valeur absolue de ( Xn+1 – Xn) et de μ
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
Synthèse
Quelque soit l’algorithme, solution d’un problème donné, il doit être communiqué à 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 conventions, pour décrire un algorithme : le langage algorithmique.

Structures de contrôle, introduction à la notion de variable

Objectifs : Introduire les structures de contrôle du langage algorithmique et écrire des
algorithmes en résonnant sur des « ardoises ».
Structures de contrôle
Tous les algorithmes peuvent être exprimés par les « tournures » suivantes qu’on appelle structures de contrôle du fait qu’elles permettent de contrôler le déroulement des algorithmes :
Le séquencement
Exprime qu’un ensemble d’actions 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 :
Action 1
Action 2
….
Action n
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 :
Action 1
Action 2
….
Action n
FSI
L’alternative
Elle exprime un choix entre deux ensembles d’actions à exécuter selon la valeur d’une condition.
SI condition :
Action 1
Action 2
….
Action n
SINON
Action n+1
Action n+2
….
Action n + p
FSI
Remarque : Chaque action peut être à son tour une répétitive, une conditionnelle, une alternative.
Notion d’ardoise
La 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 valeur 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 à dire ce qui est écrit à un moment donné.
Si A désigne le nom attribué à l’ardoise, on désignera son contenu à un instant donné par (A).
Exemples
Reprenons nos deux algorithmes ( équation du second degré et racine cubique ) et donnons les algorithmes correspondants en utilisant :
– les structures de contrôle présentées,
– les ardoises
Equation du second degré
Nous utilisons un ardoise nommée Ardoise pour mettre la valeur du discriminant. Nous désignerons son contenu par l’écriture (Ardoise).
Introduire les données A, B et C
Ardoise <— B2 – 4 A.C
SI (Ardoise ) > 0 :
Ecrire(  » la première racine est « , – B + Racine(Ardoise) / 4 A.C )
Ecrire(  » la deuxième racine est « , – B – Racine(Ardoise) / 4 A.C )
SINON
SI (Ardoise) = 0
Ecrire(  » Une racine double « , – B / 2A )
SINON
Ecrire(  » Pas de racine réelle  » )
FSI
FSI
L’action Ecrire permet de restituer les résultats.
Racine cubique
Nous utiliserons 3 ardoises. Les ardoises 1 et 2 contiennent à tout moment deux éléments consécutifs de la suite et la troisième leur différence en valeur absolue.
Introduire les valeurs A, X0 et μ
Ardoise1 <— X0
Ardoise2 <— ( 2 (Ardoise1) + A/ (Ardoise1)2 ) / 3
Ardoise 3 <— Absolu ( (Ardoise2) – (Ardoise1) )
TANTQUE ( Ardoise3 ) < μ :
Ardoise1 <— (Ardoise2)
Ardoise2 <— ( 2 (Ardoise1) + A/ (Ardoise1)2 ) / 3
Ardoise 3 <— Absolu ( (Ardoise2) – (Ardoise1) )
FINTANTQUE
Restituer le résultat qui est dans (Ardoise2)

Objets, notion d’affectation et structure d’un algorithme

Objectifs : définir les objets élémentaires manipulés par les algorithmes, introduire la notion
d’affectation et écrire des algorithmes complets.
Variables et constantes
Un algorithme opère sur des objets. A tout objet est associé un nom qui permet de l’identifier de façon unique. C’est généralement 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 V: ariables(ardoises).
– des objets qui ne peuvent pas variés par le déroulement d’un algorithme C: onstantes.
On peut répartir l’ensemble des objets en sous ensembles appelésc lasses ou types. Il existe 4 types standards :
– 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
Expressions sur les objets
Une expression est une suite d’opérandes reliés par des opérateurs.
Une expression peut être :
– arithmétique. On utilisera les opérateurs suivants +,-,/, *. Exemple A + B/C, A/B/C
– logique. Les opérateurs les plus utilisés sont : ET, OU et NON. Exemple X et Y, NON X OU Z
– relationnelle. Les opérateurs utilisés sont : <, <=, >, >=, =, <>. Exemple : A < B, A+5 = B/C
Autres actions du langage algorithmique
Affectation
C’est l’opération de base. Elle permet d’attribuer la valeur d’une expression calculable à une variable. On utilisera le symbole :=.
Exemple : A := (B + C) / D
Lecture
Elle permet d’introduire des données dans des variables. Nous utiliserons l’opération
LIRE( X, Y, Z, …..)
Ce qui est équivalent à
X := première donnée
Y := deuxième donnée
Z := troisième donnée
Ecriture
Elle permet de restituer des résultats. Nous utiliserons l’opération
ECRIRE(Expression1, Expression2,……)
Structure d’un algorithme
Un algorithme est composé de deux 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ées)
– opérations finales ( écritures, .. )
La description algorithmique est la suivante :
ALGORITHME Nom
En-tête: définition des objets
DEBUT
Corps : définition du corps
FIN
 Exemples
Remarquer dans les algorithmes qui suivent qu’on n’utilise plus la notion d’ardoise. C’est désormais une variable. Noter aussi qu’on n’utilise non plus les parenthèses pour désigner le contenu d’une variable. Une variable désigne contenant quand elle est placée à gauche du signe d’affectation et contenu quand elle figure dans une expression.

I. Cours d’algorithmique
Partie 1. Concepts de base de l’algorithmique
COURS 1. Une introduction à l’algorithmique
1.1 Introduction
1.2 Mise en oeuvre d’une application
1.3 Exemples d’algorithmes
1.4 Quelques définitions du mot ‘algorithme’
1.5 Propriétés
COURS 2. Inconvénients du langage naturel
2.1 Exemple 1
2.2 Exemple 2
2.3 Synthèse
COURS 3. Structures de contrôle, introduction à la notion de variable
3.1 Structures de contrôle
3.2 Notion d’ardoise
3.3 Exemples
COURS 4. Objets, notion d’affectation et structure d’un algorithme
4.1 Variables et constantes
4.2 Expressions sur les objets
4.3 Autres actions du langage algorithmique
4.4 Structure d’un algorithme
4.5 Exemples
TRAVAUX DIRIGES
Partie 2. Programmation PASCAL
COURS 5. Présentation générale du langage PASCAL
5.1 Vocabulaire
5.2 Objets
5.3 Expressions
5.4 Instructions
5.5 Structure d’un programme
5.6 Exemples
COURS 6. Entrées/Sorties PASCAL
6.1 Lecture
6.2 Ecriture
6.3 Les fichiers TEXT
TRAVAUX DIRIGES
Partie 3. Expérimentation sur la machine de Turing
COURS 7. Machine-caractères
7.1 Présentation
7.2 Exemples
COURS 8. Machine-nombres
8.1 Présentation
8.2 Structure de contrôle  » POUR »
8.3 Exemples
TRAVAUX DIRIGES
Partie 4. Programmation modulaire
COURS 9. Actions composées
9.1 Exemple d’introduction : calcul de Cnp
9.2 Actions composées
9.3 Fonctions
9.4 Prédicats
9.5 Utilisation en PASCAL
COURS 10. Analyse descendante
10.1 Définition
10.2 Caractéristique
10.3 Technique
10.4 Exemple
COURS 11. Communication entre modules
11.1 Nomenclature
11.2 Portée des objets
11.3 Communication entre modules
COURS 12. Illustration de l’analyse descendante et la communication entre modules à travers un exemple
12.1 Enoncé
12.2 Les différents modules
12.3 Rédaction de la solution
TRAVAUX DIRIGES
Partie 5. Objets composés
COURS 13. Les objets composés
13.1 Introduction
13.2 Définition de type
13.3 Déclaration des variables
13.4 Accès
13.5 Utilisation en PASCAL
Partie 6. Vecteurs
COURS 14. Notion de vecteur
14.1 Introduction
14.2 Caractéristiques
14.3 Définition formelle
14.4 Terminologie et Notation
14.5 Accès à un élément du vecteur
14.6 Vecteur ordonné
14.7 Mesures
14.8 Description algorithmique
COURS 15. Algorithmes sur les vecteurs
15.1 Algorithmes traitant un seul vecteur
15.2 Algorithmes traitant plusieurs vecteurs
15.3 Algorithmes de mise à jour
15.4 Algorithmes de tri
15.5 Utilisation en PASCAL
COURS 16. Vecteurs de vecteurs
16.1 Vecteurs de vecteurs ou matrices
16.2 Tableaux à n dimensions
16.3 Représentation mémoire
16.4 Description algorithmique
TRAVAUX DIRIGES
Partie 7. Listes linéaires chaînées
COURS 17. Les listes linéaires chaînées
17.1 Notion d’allocation dynamique
17.2 Exemple
17.3 Définition d’une liste linéaire chaînée
17.4 Modèle sur les listes linéaires chaînées
COURS 18. Algorithmes sur les listes et programmation en PASCAL
18.1 Algorithmes sur les listes
18.2 Utilisation en PASCAL
TRAVAUX DIRIGES
Partie 8. Fichiers
COURS 19. Introduction aux fichiers et Opérations fondamentales sur les fichiers
19.1 Raisons de l’utilisation des mémoires secondaires
19.2 Fichier
19.3 Structure de fichier
19.4 Fichiers physiques et fichiers logiques
19.5 Ouverture, création et fermeture
19.6 Lecture et écriture
19.7 Détection de la fin de fichier
19.8 L’opération Positionner ( « SEEK » )
19.9 Utilisation en PASCAL
19.10 Exemple : programmation des opérations de base
COURS 20. Concepts fondamentaux des structures de fichiers
20.1 Fichiers continus ( ‘Stream’)
20.2 Structures des champs
20.3 Structures des articles
20.4 L’accès séquentiel
20.5 L’accès direct
20.6 Article d’en-tête
20.7 Accès aux fichiers et organisation de fichier
20.8 Exemple d’utilisation en PASCAL
COURS 21. Maintenance de fichiers
21.1 Maintenance de fichiers
21.2 Réorganisation
21.3 Exemple : programmation du module de réorganisation
COURS 22. Tri de fichiers
22. 1 Tri de tout le fichier entièrement en mémoire
22. 2 Tri entièrement en mémoire uniquement des clés du fichier
22. 3 Tri par fusion
22.4 Exemple : programmation du tri par fusion
II. Annexes

…………