Algorithmique et Programmation A. Alikacem. Semaine 3 Semaine 3 Bâtir un algorithme Lecture: chapitre 3 des notes de cours Rappel des outils algorithmiques

Algorithmique et Algorithmique et ProgrammationProgrammation

A. AlikacemA. Alikacem

Semaine 3 Semaine 3 Bâtir un algorithme

Lecture: chapitre 3 des notes de cours

Rappel des outils algorithmiques

Conception des algorithmes

La documentation dans les algorithmes

Comment bâtir un programme?En suivant l’une ou l’autre des multiples méthodologies de développement…

On y retrouve généralement un ensemble de points communs: Analyse et définition des besoins : ce que l’on s’attend

que le programme devra réaliser comme tâche. L’analyse et la spécification du problème se fera dans un langage naturel.

Spécification du programme : définir spécifiquement chaque fonctionnalité du programme.

Conception: décomposition du programme en sous-problème (définition des modules du programme) ainsi que le développement des algorithmes nécessaires au fonctionnement du programme. La conception des algorithmes s’appuiera sur l’analyse et la spécification du problème.

Programmation: traduction des algorithmes dans le langage de programmation choisi pour la réalisation du programme. On parle d’implantation.

Comment bâtir un programme?

Tests et validation: phase durant laquelle le bon fonctionnement, ainsi que la conformité du programme aux spécifications sont vérifiés.

Maintenance : activité qui assure l’entretien et le bon fonctionnement du programme tant et aussi longtemps qu’il sera utilisé.

Documentation du programme: chaque étape énoncée doit être documentée pour assurer la pérennité du programme.

Comment bâtir un programme?

Algorithme

Programme

Ordinateur

Description formelle

Transcription

CompilationLangage de programmation

Langage machine

ExécutionSolution

Problème

Étapes de la construction d’un Étapes de la construction d’un programmeprogramme

Rappel

Les Les composantescomposantes d d’un ordinateur’un ordinateur

Définition C’est la spécification d’une séquence d’étapes pouvant être

exécutée de façon automatique par un ordinateur. Une décomposition en instructions simples de n'importe quel

processus. Donne la structure du programme. Un algorithme doit être simple à traduire dans un langage de

programmation.

L’algorithmique impérative

Propriétés :

Un nombre fini d’étapesUn nombre fini d’opérations par étapeUne suite d’opérations primitivesFournit un résultat (décidabilité)Chaque opération est

non ambiguë Effective

calculabilité

L’algorithmique impérative

Programmation impérativeProgrammation impérative

Ce paradigme repose sur les notions suivantes:

La mémoire principale Les variables L’action L’état Changement d’état

Variables et constantesVariables et constantes Une variable possède deux attributs :

un nom (identificateur); un type, qui définit l'utilisation possible de cette

variable en spécifiant ses propriétés. Un contenu modifiable

Une constante possède : un nom; un type; un contenu non modifiable :

Déterminé avant l’exécution de l’algorithme;

Action = événement produit par un acteur (exécutant) Durée finie Produit un résultat prévisible et sans ambiguïté Modifie l'état de la machine (actions internes)

Précondition Spécification de l'état mémoire avant l'exécution de l'action

Postcondition Spécification de l'état mémoire après l'exécution de l'action

Exemple: incrémenter x{A: x < n}

{A: x n}

Notion d’actionNotion d’action

Etat de la mémoire Valeur de l'ensemble des variables à l'instant t

Etat du processeur Contenu de la mémoire interne du processeur à l'instant t

Adresses

100Entier x dont la valeur à l'instant t vaut 65535

0000 00000000 00001111 11111111 1111

Notion d’étatNotion d’état

Expression construite à partir de constantes, de variables et d'opérateurs Evaluation lors de l'exécution Valeur dépendant de l'état du programme Exemple: x x + 1

Définition explicite du flot de contrôle

=> Suite ordonnée d'actions qui modifient l'état du processus

Changement d’étatChangement d’état

Répéter débutDEMANDER nfin

Tant Que (???)

DEMANDER n

{A: n est un entier compris entre 0 et 10}

DEMANDER n

{A: n vaut 1 ou 2}

Répéter débutDEMANDER nfin

Tant Que (????)

Les assertions (1)Les assertions (1)La validation de donnéesLa validation de données

L’unité de commande et de contrôle (UCC) En charge de contrôler le déroulement d’un programme. Elle dirige le

fonctionnement de toutes les autres unités (UAL, mémoire, entrée/sortie) Exécute un programme instruction par instruction, dans l’ordre (de haut en bas)

ou elles sont écrites. Cependant, et très souvent, on aura besoin de briser la séquentialité:

en utilisant des structures de contrôle d’alternatives; en utilisant des structures de contrôle de répétitions; en faisant des appels de sous-programmes, caractérisés

par une référence (appel) à un bloc à l’intérieur d’un autre bloc

L’UCCL’UCC

SI condition est vrai alors

DÉBUT

Instructions

FIN

Structures d’alternativesStructures d’alternatives

Début Si n = 0 ou n = 1Alors Début fact 1 Fin fact 1 Répéter i [2, n] Début fact fact * i Fin Fin

SI condition est vrai alors

DÉBUT

Instructions v

FIN

SINON

DÉBUT

Instruction f

FIN

Structures d’alternativesStructures d’alternativesDébut Si n = 0 Alors Début fact 1 Fin Sinon Début Si n = 1 Alors Début fact 1 Fin Sinon Début fact 1 Répéter i [1, n] Début fact fact * i Fin Fin Fin Fin

Structures d’alternativesStructures d’alternatives

Cas V de

v1 : b1

v2 : b2...vn : bn

Autrement c

FinCas

Début Cas n de 0 : Début fact 1 Fin 1 : Début fact 1 Fin Autrement : Début fact 1 Répéter i [2, n] Début fact fact * i Fin Fin FinCasFin

RÉPÉTER n FOIS

DÉBUT

Instructions

FIN

Structures de répétitionsStructures de répétitions

DébutSi n = 1 ou n = 0 alors

Débutfact 1Fin

SinonDébutfact 1

Répéter n-1 foisDébutfact fact * i

FinFin

Fin

i 2

i i + 1

RÉPÉTER i [1,n] DÉBUT

Instructions

FIN


DébutSi n = 1 ou n = 0 alors

Débutfact 1Fin

SinonDébutfact 1

Répéter i [2, n]Débutfact fact * iFin

FinFin

RÉPÉTER

DÉBUT

Instructions

FIN

TANT QUE condition

Structures de répétitionsStructures de répétitionsDébut Si n = 1 ou n = 0 alors Début fact 1 Fin Sinon Début fact 1 i 1Répéter

Début fact fact * i i i + 1Fin

Tant Que i < n+1Fin Fin

TANT QUE condition

DÉBUT

Instructions

FIN


Début Si n = 1 ou n = 0 alors Début fact 1 Fin Sinon Début fact 1 i 2Tant Que i < n+1

Début fact fact * i i i + 1Fin

Fin Fin

TANT QUE condition

DÉBUT

Instructions

FIN


Début i 1 fact 1 Tant Que i < n Début i i + 1 fact fact * i Fin Fin

RemarqueRemarque

Répéter i [1, n] début Bloc fin

i 1Tant Que i <= n début Bloc i i + 1 fin

i 1Répéter n fois début Bloc i i + 1 fin

i 1Répéter début Bloc i i + 1 finTant Que i <= n

DEMANDER n{A: n est un entier positif ou nul}S 0Répéter n fois

début S S + 1fin

AFFICHER S

DEMANDER n{A: n est un entier positif ou nul}S 0Répéter i [1, n]

début S S + ifin

AFFICHER S

DEMANDER n{A: n est un entier positif ou nul}S 0i 0Tant Que n i

début S S + i i i + 1fin

AFFICHER S

DEMANDER n{A: n est un entier positif ou nul}S 0i 0Répéter

début S S + i i i + 1fin

Tant Que n iAFFICHER S

Algorithme : Calculer n! pour un entier n 0début{ Assertion : n est un entier 0 }i 0fact 1Tant que i < n

débuti i + 1fact fact * ifin

fin

Il est impératif que dans tout schéma de répétition conditionnelle la valeur de la condition puisse changer, sinon nous serions dans une boucle sans fin (boucle infinie);

On doit faire précéder la structure de contrôle de la boucle Tant Que par des instructions de démarrage (initialisation).

Pour s’assurer qu’un algorithme structuré se termine il est suffisant de vérifier que chaque boucle se termine.

Une première condition nécessaire est qu’au moins une des variables de la condition c soit modifiée dans la portée de la boucle.

RemarqueRemarque

Technique de la sentinelleTechnique de la sentinelleTant que ce n’est pas fini Début Instructions du bloc à exécuter Fin

total 0

Tant que il y a un étudiant à traiter Début Demander note total total + note Fin

Début total 0

n 0 Demander note

{ A: .. } Tant Que note -1 Début total total + note

n n + 1 Demander note

{A: .. } Fin

moyenne total / n Afficher moyenneFin

Dans le cas du mode conversationnel, la fin d’une suite d’informations saisie à l ’aide d’un processus itératif est indiquée au moyen de la technique de la sentinelle.

La documentation: les commentaires dans les algorithmes

Vous aurez à considérer 4 types de commentaires

des commentaires d'identification des grandes étapes;des commentaires explicatifs; des commentaires du type assertions;les commentaires de spécification formelle;les commentaires de spécification d’un bloc;

Les commentaires dans les algorithmes

Il est très important de bien documenter un algorithme, il n’en sera que plus facile à lire.

On retrouve 2 types de commentaires que l’on peut utiliser pour documenter un algorithme:– Les commentaires généraux.– Les assertions.

Placer dans fact la valeur de n! sans modifier l'entier n 0.

Début { de l'algorithme }{ Assertion : n est un entier 0 }« Voici tout de que nous savons ici. »

Si n = 1 ou n = 0 alorsDébut { des cas n = 1 ou n = 0 }{ Assertion : n est un entier dans [0, 1], inchangé }« Cette assertion est exacte à chaque fois que nous passons ici. »fact 1{ Assertion : n est un entier dans [0,1], inchangé et fact contient n!}« Notre objectif est atteint dans ces cas. »

Fin { des cas n = 1 ou n = 0 }Sinon

Début { des cas 2 }{ Assertion : n est un entier 2 inchangé}« Voici tout ce que nous savons ici. »

fact 1Répéter i [1, n] :

Début { Répéter }{ Assertion : n est un entier 2 inchangé, i est un entier dans [1, n]

et fact contient (i-1)! }fact fact * i{ Assertion : n est un entier 2 inchangé, i est un entier dans [1, n]

et fact contient i!}Fin { Répéter}{ Assertion : n est un entier 2 inchangé et fact contient n!} « Notre objectif est atteint dans ces cas. »

Fin { des cas 2}{ Assertion : n est un entier 0 inchangé et fact contient n!}« Notre objectif est atteint dans tous les cas exigés. »

Fin { de l'algorithme }

Exemple p. 52Exemple p. 52

Les commentaires généraux auront 2 utilités:– Identifier les grandes étapes de l’algorithme– Expliquer certaines séquences d’opérations qui

peuvent sembler plus ou moins claires à première vue

Les commentaires dans les algorithmes

Forme structurée, validation Forme structurée, validation des algorithmes et assertionsdes algorithmes et assertions

Le principal avantage de la forme structurée est la restriction du nombre possible de «chemins» dans l’exécution de l’algorithme.

En chaque point de l’algorithme on n’a qu’une provenance possible. On peut alors prouver l’exactitude d’un algorithme en insérant des assertions.

Une assertion est une expression logique qui est vraie. Elle est utilisée pour montrer certaines conditions que l’on suppose vraies à un point donné d’un algorithme.

Une assertion dans un algorithme doit être considérée lors de l’implantation de l’algorithme : les conditions sont à être interprétées dans le langage de

programmation choisi; elles devraient également pouvoir être vérifiées lors de

l’exécution du programme.

Les assertions (2)Les assertions (2)Les post-conditionsLes post-conditions

Début

Demander n

{ Assertion : n est un entier 0 }

Si n = 1 ou n = 0 alors

Début

fact 1

Fin

Sinon

Début

fact 1

Répéter i [1, n] :

Début

fact fact * i

Fin

Fin

{ Assertion : n est un entier 0 inchangé et fact contient n!}

Fin

Si

Alors

Idée de base Abstraire Décomposer Combiner

Structuration des actions Séquentielle Conditionnelle Itérative

Tout ce qu’on peut faire sur ordinateur peut être exprimé au moyen de l’affectation et d’alternatives et des répétitions.

Conception d’algorithmesConception d’algorithmes

Conception d’algorithmesConception d’algorithmes

• Question à résoudre par une solution informatique

• Instance d'un problème = entrée nécessaire pour calculer une solution du problème

• Ensemble de données

• Ensemble de résultats

= solution informatique au problème

• Description d ’un ensemble d'actions

• Exécution dans un certain ordre

Problème Algorithme

La démarche

Conception d’algorithmes

Souvent le problème est "mal posé"... Rechercher l'indice du plus petit élément d'une suite

=> Spécifier = produire un énoncé

Énoncé = texte où sont définies sans ambiguïté : L'entrée (données du problème) La sortie (résultats recherchés) Les relations (éventuelles) entre les données et les résultats

Que dois-je obtenir ? Soit I l'ensemble des indices des éléments égaux au

minimum d'une suite. Déterminer le plus petit élément de I.

7 1 3 1 51 2 3 4 5

2, 4 ?

SynthèseSynthèseLes 3 étapes principales pour arriver à la résolution d’un problème sur un ordinateur:

comprendre le problème initial et préciser les données fournies (entrées);

préciser les résultats attendus (sorties); déterminer le processus qui permet de passer des

entrées aux sorties (l’algorithme): Commencer par décrire les grandes étapes Raffiner chacune des étapes jusqu’à avoir tout décrit en

termes d’instructions primitives Insérer des assertions aux endroits clés dans l’algorithme

Calcul de l'intérêt et de la valeur acquise par une somme placée pendant un an à intérêt simple.

• Données fournies:

Deux nombres représentant les valeurs de la

somme placée et du taux d'intérêt

• Résultats désirés:

Deux nombres représentant l'intérêt fourni par la somme placée ainsi que la valeur obtenue après placement d'un an

Exemple (1)

Il nous faut maintenant décrire les différentes étapes permettant de passer des donnés aux résultats. Nos connaissances générales nous permettent d'exprimer cette règle:

"Pour obtenir l'intérêt fourni par la somme,il suffit de multiplier la somme par le taux d'intérêt divisé par cent; la valeur acquise s'obtient en additionnant ce dernier montant et la somme initiale."

Exemple (1)

Dans cet exemple simple apparaissent les trois étapes qui

caractérisent la résolution d'un problème sur ordinateur:

Comprendre la nature du problème posé et préciser

les données fournies ("entrées"ou "input" en anglais),

préciser les résultats que l'on désire obtenir ("sorties"

ou "output" en anglais), déterminer le processus de

transformation des données en résultats: l’algorithme!

Exemple (1)

Les grandes étapes de l'algorithme :

(1) Prendre connaissance de la somme initiale et du taux d'intérêt.

(2) Multiplier la somme par le taux; diviser ce produit par 100;

le quotient obtenu est l'intérêt de la somme.

(3) Additionner ce montant et la somme initiale; cette somme est la valeur

acquise.

(4) Afficher les valeurs de l'intérêt et de la valeur acquise.

Toutes ces étapes peuvent être exprimées directement par des instructions primitives…aucun raffinement à faire.

Exemple (1)

L’algorithme en pseudo code:

DEMANDER sommeInitiale

{Assertion: sommeInitiale est un réel > 0}

DEMANDER taux

{Assertion: taux est un réel > 0 et <= 100}

intérêt sommeInitiale * taux / 100

valeurAcquise sommeInitiale + intérêt

AFFICHER intérêts, valeurAcquise

{Assertion: intérêts et valeurAcquises représentent l'intérêt fourni par le

placement de sommeInitiale et la somme obtenue après placement d'un an }

Exemple (1)

Voici les règles d'un jeu très simple: deux joueurs A et B se cachent la main droite derrière le dos. Chacun choisit de tendre un certain nombre de doigts (de 0 à 5), toujours derrière le dos. Les deux joueurs se montrent la main droite en même temps. Si la somme des nombres de doigts montrés est paire, le premier joueur a gagné, sinon c'est le second.

Le problème consiste à faire prendre la décision par un ordinateur.

Exemple (2)

Exprimé en français, l'algorithme se présente comme suit:

- prendre connaissance du nombre de doigts de A- prendre connaissance du nombre de doigts de B- calculer la somme de ces deux nombres- si la somme est paire, A est le gagnant- si la somme est impaire, B est le gagnant.

Pour déterminer si un nombre est pair ou impair, il suffit de calculer le

reste de la division par 2 (.. modulo 2 ou %2): il vaut 0 dans le premier

cas et 1 dans le second. Remarquez qu’il n’y aucun raffinement à faire,

tout peut être décrit en termes d’instructions de base….

Exemple (2)

DÉBUTDEMANDER na,nb{A:na et nb sont des entiers positifs ou nuls}reste (na + nb) % 2si reste = 0 alors début

AFFICHER"Le joueur A a gagné." fin sinon début

AFFICHER "Le joueur B a gagné" fin

AFFICHER "Bravo pour le gagnant!« {A: le gagnant est désigné}

FIN

Exemple (2)

Exemple (3)

Soit l'équation mathématique “ ax2 + bx + c = 0 ”. Écrire un algorithme qui nous fait passer à une situation finale acceptable si notre situation initiale est acceptable.

Analyse

Description des situations initiales acceptables :

a, b et c sont des valeurs réelles bien définies et contenus

dans des variables de même nom.

Delta contient la valeur de l'expression mathématique “ b2 - 4ac ”

Description des situations finales acceptables :

a, b, c et Delta n'ont pas été modifiées.

Nous avons affiché “ Pas de racine réelle. ” si et seulement

si l'équation ne possède effectivement pas de racine réelle.

Nous avons affiché “ Racine double. ” si et seulement si

l'équation possède effectivement une racine réelle double.

Nous avons affiché “ Deux racines réelles. ” si et seulement si

l'équation possède effectivement deux racines réelles distinctes.

Rien d'autre n'a été affiché ou imprimé depuis la situation initiale.

Exemple (3)

Conception de l'algorithme:

Avant de faire cette conception, écrivons d'une façon très schématique une solution à ce problème.

{ Assertion : Les valeurs de a, b et c sont des nombres réels. } { Assertion : La situation initiale est satisfaite. } { Instructions de l’algorithme à développer. } { Assertion : La situation finale est satisfaite dans tout le domaine.}

Cette assertion estune façon de préciserle domaine que nousdevons satisfaire.

C’est cette partie quenous devrons détailler.

Exemple (3)

Delta < 0

Delta = 0

Afficher« Pas de racine réelle. »

Afficher« Racine double. »

Afficher« Deux racines réelles. »

Vrai

Faux

Faux

Vrai

Algorithme formulé dans un organigramme

Algorithme formulé dans un organigramme

Delta 0 dans ce rectangle.

{ Assertion : Les valeurs de a, b et c sont des nombres réels }

Si Delta < 0 Alors

Début

Afficher “ Pas de racine réelle. ”

Fin

Sinon

Début

Si Delta = 0 Alors

Début

Afficher “ Racine double. ”

Fin

Sinon

Début

Afficher “ Deux racines réelles. ”

Fin

Fin

{ Assertion : …..}

Algorithme formulé en pseudo-code

Algorithme formulé en pseudo-code

Un algorithme qui ajoute une journée à une date donnée.

Exemple (4)

DEBUTDEMANDER j,m,a{A: a représente une année dans le calendrier grégorien, m un mois dans

l’année et j un jour du mois}max 30SI m=1 OU m=3 OU m=5 OU m=7 OU m=8 OU m=10 OU m=12 ALORS début

max 31 fin

SI m=2 ALORSdébutmax 28SI (a % 4 = 0) ET NON (a % 100 =0) ALORS début

max 29 fin

SI (a % 400=0) ALORS débutmax 29fin

finj j+1SI j>max ALORS début

j 1m m+1SI m>12 ALORS début

m 1 a a+1 fin

finAFFICHER j,m,a{A: j, m et a représentent la date du lendemain}

FIN

Ensemble d‘instructions à exécuter pour résoudre une instruction complexe

Expression en terme de primitives (instructions de base)

Exemples Calculer les racines d'une équation du second degré Lister des éléments d’un dossier étudiant Trier un ensemble de noms par ordre alphabétique

L’approche descendante permet d’expliciter une action complexe en une suite d'actions primitives: abstraction.

Les instructions composées Les instructions composées (complexes)(complexes)

Méthode de résolution de problèmes qui nous aide à formuler de bons algorithmes.Elle consiste à

considérer un problème dans son ensemble, préciser les données nécessaires et les résultats attendus décomposer le problème en plusieurs sous-problèmes plus

simples qui seront traités séparément et éventuellement décomposés eux-mêmes de manière encore plus fine (raffinement)

L’approche descendanteL’approche descendante

Exemple p.32 dans les notes de coursExemple p.32 dans les notes de cours

Imaginons un robot domestique à qui nous devons fournir

un algorithme lui permettant de préparer une tasse de café

soluble. Une première version de l'algorithme pourrait être:

(1) faire bouillir de l'eau

(2) mettre le café dans la tasse

(3) ajouter l'eau dans la tasse

Approche descendanteApproche descendante

(1) faire bouillir l'eau peut être affinée en

(1.1) remplir la bouilloire d'eau

(1.2) brancher la bouilloire sur le secteur

(1.3) attendre l'ébullition

(1.4) débrancher la bouilloire

(2) mettre le café dans la tasse pourrait être affiné en

(2.1) ouvrir le pot à café

(2.2) prendre une cuiller à café

(2.3) plonger la cuiller dans le pot

(2.4) verser le contenu de la cuiller dans la tasse

(2.5) fermer le pot à café


(3) ajouter de l'eau dans la tasse pourrait être affinée en

(3.1) verser de l'eau dans la tasse jusqu'à ce que celle-ci soit pleine

Certaines étapes étant encore trop complexes et sans doute

incompréhensibles pour notre robot, il faut les affiner davantage.

(1.1) remplir la bouilloire d'eau peut nécessiter les affinements suivants:

(1.1.1) mettre la bouilloire sous le robinet

(1.1.2) ouvrir le robinet

(1.1.3) attendre que la bouilloire soit pleine

(1.1.4) fermer le robinet


Quand doit-on arrêter le raffinement? Lorsque l’on a décrit l’algorithme en des termes que

l’ordinateur peut comprendre On doit donc connaître les instructions primitives,

quelle sorte d‘instructions le processeur peut interpréter.

Un programme sera donc une suite d’instructions primitives, comprises directement par l’ordinateur.

Les algorithmes que nous écrivons doivent donc refléter cette décomposition.

Approche descendante Approche descendante

L’approche descendanteL’approche descendante

Dans le cas du robot, « Brancher la bouilloire » est une instruction que le robot est en mesure de comprendre

Par contre, « Remplir la bouilloire » est une instruction trop complexe et doit être décomposée à nouveau.

Décomposition fonctionnelle

Si une instruction donnée n'est pas primitive, c'est-à-dire qu'elle n'est pas assez explicite pour qu'un ordinateur l'interprète directement, elle doit être décomposée en instructions primitives.

Chaque décomposition sera encapsulée dans un bloc d ’instructions.

L‘ analyse descendante est une des méthodes pour obtenir cette décomposition.

La décomposition fonctionnelle permet de rapides construction de programmes, la possibilité de leur réutilisation pour en construire d’autres en plus d’en assurer une rapide et efficace maintenance.

Les blocs algorithmiques

Utilisés afin de découper un algorithme en plusieurs sous-tâches.

Cette façon de procéder s’inscrit très bien dans l’approche descendante et la décomposition fonctionnelle.

Chaque tâche à accomplir est alors détaillée au sein d’un bloc algorithmique.

• On peut ré-écrire l’algorithme lendemain de la façon suivante:

Bloc B1 – la date du lendemain

DEBUT

Déterminer une date (Bloc B2)

Déterminer le dernier jour du mois m (Bloc B3)

Déterminer la date du jour suivant (Bloc B4)

AFFICHER « La journée suivante est: », j, m, a

{A:….}

FIN


Bloc B2 – Déterminer une date

DEBUT

DEMANDER j, m, a

{A: j est un entier compris entre 1 et 31}

{A: m est un entier compris entre 1 et 12}

{A: a est un entier représentant une année dans le calendrier}

{A:…}

FIN


Bloc B3 – Déterminer le dernier jour du moisDEBUT

max 30;SI m=1 OU m=3 OU m=5 OU m=7 OU m=8 OU m=10 OU m=12 ALORS

DEBUT max 31;FIN

SI m=2 ALORS débutmax 28;SI a est une année bissextile (voir B5)

ALORS débutmax 29;fin

fin {A:…}FIN


Bloc B4 – Déterminer la date du jour suivantDÉBUT

j j+1;SI j > max ALORSdébut

j 1;m m+1;SI m>12 ALORS début

m 1;a a+1;fin

fin

{A:…}FIN


Bloc B5 vérification si une année donnée est une année bissextile DEBUT

bis FAUXSI (a % 4 = 0) ET NON (a % 100 = 0)

ALORS débutbis VRAI;fin

SI (a % 400=0) ALORS début

bis VRAI;fin

{A:…}FIN


La documentation: les commentaires de spécification dans

les algorithmes

Vous aurez à considérer 4 types de commentaires

des commentaires d'identification des grandes étapes;des commentaires explicatifs; des commentaires du type assertions;les commentaires de spécification formelle d’un bloc;les commentaires de spécification internes à un bloc;

Les (4) commentaires de spécification formelle nous aideront à spécifier l’interface de chaque bloc issu d’une décomposition.

Les (8) commentaires internes à un bloc nous aideront à construire les instructions du bloc tout en assurant sa rapide maintenance.

Les commentaires de spécification

L’en-tête du bloc d ’instruction implantant une tâche

Pré-conditions conditions devant être vraies au départ pour assurer le bon fonctionnement du bloc d ’instructionsPost-conditions conditions étant vraies (observables) après

exécution (correcte, i.e. les pré-conditions sont respectées) des instructions du bloc. Sinon,

indiquer la ou les actions à entreprendre dans l ’exécution du bloc.Valeur(s) retournée(s) en output de l ’exécution des instructions du bloc

si les pré-conditions sont respectées, sinon indiquer ce que fournira le bloc.

Ce type de commentaires spécialisés sera utilisé essentiellement lors de la décomposition fonctionnelle d’une solution lors d ’une résolution d’un problème donné. Ainsi, chaque tâche qui en découle de la décomposition doit être spécifiée par les 4 commentaires suivant:

Les commentaires d’interface d’un bloc

Les commentaires de spécification internes à un blocLes commentaires de spécification servent à spécifier un bloc d’un algorithme: Ce qu’il fait La façon dont il procède pour atteindre son but Les données nécessaires Les résultats qu’il fournit

Ces commentaires sont internes aux blocs. Ils aideront au développement rapide des blocs, ainsi qu’à leur validation de façon plus efficace.

Définitions Objectifs: ce commentaire sert à décrire le but visé

par le bloc. Méthode: la façon dont on procède pour atteindre le

but décrit au commentaire précédent Besoins: toutes les données dont le bloc aura

besoin pour atteindre son but. Connus: les données que l’on connaît d’avance,

que l’on n’aura pas besoin de demander au bloc appelant ni à l’usager.

Les (8) commentaires de spécification d’un bloc

Entrées: les données qui parviennent du bloc appelant.

Sorties: les données que le bloc renvoie au bloc appelant

Résultats: toute conséquence du bloc qui n’est pas visible par les autres blocs, exemple: les affichages.

Hypothèses: Les conditions nécessaires au bon fonctionnement du bloc. Ces hypothèses concernent:

les données en entrée du bloc; les données lues (saisies) dans le bloc.

Les commentaires de spécification d’un bloc

DEMANDER nbEtudiants {Assertion: nbEtudiants 0}

Bloc B2… {.. Besoin : n , le nombre entier dont il faut calculer le factoriel Entrée : n .. Hypothèses : n 0 } Début {début du bloc} {A: n 0 } …..

Les assertions (3)Les assertions (3)Validation des hypothèsesValidation des hypothèses

Bloc B3.. { les 8 commentaires de spécification internes } début {début du bloc} … {A: post-condition de B3} fin {fin du bloc}

Bloc B1… { les 8 commentaires de spécification internes } début{début du bloc} … Calcul de la moyenne d'une série de notes (voir B3) {A: la variable moy contient la moyenne des notes} …. {A: post-condition de B1} fin {fin du bloc}

Les assertions (4)Les assertions (4)Les post-conditionsLes post-conditions

Exercice

Compléter l’algorithme suivant en y insérant dans chaque bloc:

Les assertions aux endroits requis Les 8 commentaires de spécification internes

Bloc B1: un traitement bien spécial

début

Demander CP

Afficher CP

TANT QUE CP ‘!’

début

faire le traitement (voir détails Bloc B2)

fin

fin

Bloc B2: le traitement

début

Demander CL

SI CL = CP ALORS début

Afficher le caractère de soulignement '_ ’

fin

Afficher CL

CP CL

fin


début

Demander CP

Afficher CP

TANT QUE CP ‘!’

début


fin

fin


début

Demander CL



fin

Afficher CL

CP CL

fin

J’ai besoin de quoi?


début

Demander CP

Afficher CP

TANT QUE CP ‘!’

début


fin

fin


début

Demander CL



fin

Afficher CL

CP CL

fin

CP et CL!


début

Demander CP

Afficher CP

TANT QUE CP ‘!’

début


fin

fin


début

Demander CL



fin

Afficher CL

CP CL

fin

On quitte B1


début

Demander CP

Afficher CP

TANT QUE CP ‘!’

début


fin

fin


début

Demander CL



fin

Afficher CL

CP CL

fin

On a quitté...

J ’ai besoin de quoi?


début

Demander CP

Afficher CP

TANT QUE CP ‘!’

début


fin

fin


début

Demander CL



fin

Afficher CL

CP CL

fin

On a quitté...

CP et CL!


début

Demander CP

Afficher CP

TANT QUE CP ‘!’

début


fin

fin


début

Demander CL



fin

Afficher CL

CP CL

fin

Flux de donnéesentre B1 et B2

CP et CL!


début

Demander CP

Afficher CP

TANT QUE CP ‘!’

début


fin

fin


début

Demander CL



fin

Afficher CL

CP CL

fin

CP

CPCP…CL

Une entrée

Une sortie


début

Demander CP

Afficher CP

TANT QUE CP ‘!’

début


fin

fin


début

Demander CL



fin

Afficher CL

CP CL

finOn revient au point d’appel

Le point d ’appel

Questions:

Qu’affiche cet algorithme si les données lues sont:

" Etes vous efficace? ... Bonne chance!! "

(Les guillemets ne font pas partie des données)

Quel est le rôle du caractère ! dans l'algorithme?

Est ce que c’est le même espace mémoire qui est associé à CP dans B1 et B2? En d’autres termes, est ce que c’est la même variable? Attention, ne confondez pas valeur assignée à une variable et variable (l’abstraction d’une cellule mémoire)

Exercice


début

Demander CP

Afficher CP

TANT QUE CP ‘!’

début


fin

fin


début

Demander CL

SI CL = X ALORS début

Afficher '_ ’

fin

Afficher CL

X CL

fin

Paramètres formels de B2

Paramètre formel deB1mais effectif pour B2

Documents

Algorithmique et Programmation A. Alikacem. Semaine 3 Semaine 3 Bâtir un algorithme Lecture: chapitre 3 des notes de cours Rappel des outils algorithmiques