Moniteur d'Initiation à l'AlgorithmiqueMonia Suite version 0.38.97 - novembre 2012 |
Ce document tente de présenter, pas à pas, la conception d'un organigramme, la génération du programme source Pseudo-Langage associé, puis l'exploitation de ce dernier une fois rendu exécutable. Le document est principalement destiné aux débutants en programmation informatique. Le lecteur doit néanmoins disposer d'un ordinateur sur lequel est installée la suite Monia.
Ce tutoriel n'est pas un cours d'informatique ! Il aborde cependant quelques notions de base telles que :
Les deux petits exercices proposés vous permettront, je l'espère, d'entrevoir les avantages que peut apporter un outil comme MoniaSuite, mais aussi et surtout d'avoir un infime aperçu des énormes possibilités de la programmation informatique… Il restera bien entendu énormément de choses à apprendre dans ce domaine, mais comme on dit : « le plus dur, c'est de savoir où et comment commencer ! »
Nous allons volontairement choisir, dans un premier temps, un problème simple afin de se concentrer sur les manipulations de la suite logicielle plutôt que sur des problèmes d'analyse : « Calculer la surface d'un disque connaissant son rayon… »
Tout le monde connaît la formule magique ? non ? S = π . R2
Notre programme doit donc être en mesure de recevoir une valeur de rayon, faire le calcul, et produire le résultat.
|
disqsurf), le nom de l'auteur,
et la date de mise à jour…La page de dessin de l'organigramme montre par défaut les points d'entrée (Début) et de sortie (Fin) du programme.
Ces deux symboles sont séparés par une ancre (petit rond noir) qui représente un endroit où d'autres symboles vont pouvoir être insérés.
Chaque ancre peut être sélectionnée par un simple clic (bouton gauche de la souris), elle apparaît alors cerclée de rouge.
|
|
Le texte par défaut contenu dans les symboles est entre accolades : ce n'est pas un hasard ! Il s'agit de délimiteurs de commentaires en Pseudo-Langage.
|
Notre organigramme de premier niveau d'analyse est maintenant construit !
Cette version, si elle est très utile d'un point de vue analytique (même si cela ne paraît pas évident sur un problème aussi simple !), ne permet pas dans l'état d'obtenir un véritable programme exécutable. |
Pour que notre machine adorée puisse exécuter quelque chose, encore faut-il lui « parler » dans un langage qu'elle entend… C'est là qu'interviennent les langages de programmation tels que le Pascal, le C et bien d'autres, malheureusement pour nous, tous basés sur la langue anglo-saxonne ! Heureusement, Monia sait interpréter une version francisée de langage de programmation structurée : le Pseudo-Langage !
Passons donc à la phase 2 : l'analyse détaillée…
[ Sommaire ]
Il peut à priori s'agir de toute valeur appartenant à l'ensemble des réels strictement positifs ; mais une valeur nulle ou négative ne devrait pas perturber notre calcul puisqu'il s'agit d'une élévation au carré (le résultat sera nul ou positif)…
Le programme devra réserver un emplacement mémoire susceptible de stocker une valeur réelle afin d'y placer le rayon ;
en informatique, un tel emplacement est référencé par un nom que l'on nommera R , ou encore rayon (cela s'appelle
un identificateur de variable, le choix du nom est libre mais ne doit ni commencer par un chiffre, ni comporter d'espace).
⇒ en Pseudo-Langage, on écrira tout simplement : rayon est un réel ;
|
Dans MoniaOrg, les variables peuvent être déclarée grâce à l'onglet
|
|
Monia produit des programmes qui fonctionnent en mode terminal (sans interface graphique) ; il y a cependant au moins deux solutions pour
indiquer la valeur du rayon :
• soit en la transmettant en argument sur la ligne de commande ;
• soit en faisant en sorte que le programme pose la question à l'utilisateur, solution que nous allons retenir.
Le programme peut interroger l'utilisateur par le biais de la console (ensemble écran/clavier) : le programme transmet des informations à l'utilisateur en affichant du texte sur l'écran, et l'utilisateur transmet des informations au programme en les tapant au clavier…
Chaque environnement et langage de programmation offre un ensemble de ressources appelées communément des fonctions, au sens mathématique du terme dans la mesure ou elles peuvent renvoyer un résultat après traitement des données qu'elles reçoivent en entrée ; il nous faut ici au moins une fonction permettant d'injecter du texte pour poser la question…
⇒ en Pseudo-Langage : Afficher("Rayon du disque ? " ) ;
# affiche le texte entre guillemets, le point-virgule marque la fin d'instruction
et une autre capable de lire ce qui est tapé au clavier (en supposant que l'utilisateur saisisse bien une valeur numérique)…
⇒ en Pseudo-Langage : Saisir( rayon ) ;
# attend une saisie clavier terminée par Entrée et stocke la saisie dans la variable indiquée (ici rayon)
|
L'identificateur de variable indiqué dans la fonction
|
|
Comment connaître la liste des fonctions à notre disposition ?
• une liste récapitulative est disponible sous MoniaOrg par la commande Aide | Bibliothèque de base
• la documentation complète est accessible depuis MoniaPL par Aide | Pseudo-Langage (F1).
Même si cela ne paraît toujours pas forcément évident sur un exemple aussi trivial, la mise en place d'instructions du langage peut faire perdre le côté informationnel du texte placé lors de l'analyse initiale.
Heureusement, rien ne nous empêche de conserver ce texte en tant que commentaire associé à chacune des étapes de l'organigramme
,
puis modifiez le texte par défaut : invite de saisie du rayon
|
Notons qu'ici, le texte du commentaire n'apporte pas beaucoup de renseignement par rapport à l'instruction proprement dite… Il s'agit juste d'un exemple ; dans la réalité, les commentaires ne doivent pas se contenter de traduire les instructions ! |
La rubrique Outils comporte des commandes permettant d'afficher ou non les commentaires et de forcer leur alignement vertical…
Les curieux l'auront peut-être remarqué, l'éditeur graphique de MoniaOrg dispose d'un système de menu contextuel accessible par clic droit sur un symbole ou une ancre. Les commandes disponibles sont ainsi plus rapidement accessibles !
Fichier | Enregistrer ou plus simplement en cliquant sur
[ Sommaire ]
L'expression du calcul, dans les langages de programmation évolués, ressemble fortement à la forme que l'on a l'habitude d'utiliser en mathématique ( S = πR2 )… avec cependant quelques différences :
<- est composé du signe inférieur et du signe moins…Pi qui renvoie la valeur du fameux nombre Carré() est disponible ;R * R ( * représente le symbole de multiplication).surface.surface <- Pi * rayon * rayonsurface <- Pi * Carré( rayon )[ Sommaire ]
L'utilisateur attend maintenant impatiemment le résultat du calcul ! Il nous faut donc mettre en place dans le dernier symbole une instruction permettant d'injecter du texte sur la console
|
La fonction
|
|
[ Sommaire ]
Notre organigramme est maintenant constitué exclusivement d'instructions conformes à la syntaxe du Pseudo-Langage, mais ce n'est pas encore à proprement parler un programme !
Outils | Traduire en Pseudo-Langage puis choisir un nom d'enregistrement :
le nom disqsurf peut (doit) être conservé, l'extension sera maintenant .pl.Nous possédons maintenant un fichier source disqsurf.pl que nous pouvons ouvrir avec l'EDI MoniaPL (Environnement de Développement Intégré)...
Fichier | Ouvrir ou double-cliquez directement sur le fichier .pl|
La première partie du listing est une entête sous forme de commentaire… Sa présence n'influe pas sur le programme mais est indispensable pour sa traçabilité ! La colorisation syntaxique permet de mieux distinguer les mots clés du langage (en noir), les types de données (en vert), les chaînes de caractères (en bleu) ou encore les noms des ressources de la bibliothèque (en jaune)… Ce programme source n'est pas encore un programme exécutable ! Il nous faut maintenant lancer une série d'opérations qui vont convertir notre texte source en une suite d'instructions compréhensibles par le processeur (celui-ci ne comprend que le binaire…). Heureusement, cette étape compliquée va se résumer pour nous à… un simple clic ! |
|
Exécution | Compiler ou directement sur le raccourci
Surveillez les messages dans la partie basse de l'IHM (Interface Homme-Machine) de MoniaPL, normalement tout est bien qui fini bien : la dernière ligne doit commencer par « Destination… » et se terminer par le nom de l'exécutable fabriqué !
Si ce n'est pas le cas, vérifiez et corrigez le programme source… croisez les doigts, et ré-essayez…
[ Sommaire ]
Commençons par le moyen le plus rapide pour (enfin) pouvoir utiliser notre programme !
Attention : pour une valeur avec des décimales, le séparateur à utiliser est le point ! |
|
Note : avec une version de MoniaPL à terminal intégré, le programme s'exécute directement dans celui-ci.
Méditez quelques secondes et faites un voeu : vous venez peut être pour certains d'écrire votre premier programme informatique qui fonctionne !
Dans le cas d'une version de MoniaPl sans terminal intégré, un autre moyen pour utiliser notre programme, est de démarrer au préalable un terminal (ligne de commandes). Ceci peut se faire en dehors de MoniaPL, mais il faut ensuite se placer dans le répertoire où se trouve notre exécutable. Une méthode plus rapide consiste à demander à MoniaPL de faire cela pour nous :
Exécution | Terminal ou directement sur le raccourci
À partir du terminal, lancer votre programme en tapant simplement son nom suivi de Entrée
(Attention : sous Linux, il faut saisir ./disqsurf )…
Comment améliorer le format d'affichage du résultat ?
⇒ la fonction Afficher() permet de spécifier une taille minimale (en nombre de caractères)
⇒ et un nombre de décimales pour les valeurs réelles…
Afficher("Surface = ", surface:1:3, CRLF ) ;Ce premier exercice guidé est terminé, passons à quelque chose de plus conséquent…
[ Sommaire ]
L'intérêt des organigrammes est de permettre la visualisation de la structure d'un processus (qui ne se traduit d'ailleurs pas forcément en programme informatique, il peut tout aussi bien s'agir d'une recette de cuisine…). Or ce genre de déroulement n'est pas toujours purement linéaire comme dans l'exercice précédent…
Nous allons maintenant étudier un problème dont la résolution fera appel à des prises de décision et des traitements différents suivant les cas : « Évaluer un texte et dire s'il correspond à un palindrome… »
Tout d'abord, qu'est-ce qu'un palindrome ? Un palindrome est un texte ou un mot dont l'ordre des symboles (lettres et chiffres) reste le même, qu'on le lise de gauche à droite ou de droite à gauche.
Par mesure de simplification, nous allons restreindre le jeu de caractères autorisés au code ASCII standard ; ce qui exclu notamment les lettres accentuées. Le codage de ces caractères peut en effet varier d'une machine, voire d'une application, à l'autre…
Quelques exemples ?
[ Sommaire ]
|
Notre application peut respecter le schéma traditionnel :
Pour faire simple, l'étape A se résume à la saisie d'une chaine de caractères, et l'étape C à l'affichage d'un diagnostic booléen (vrai ou faux) : il s'agit d'un palindrome, ou pas… L'étape B, qui doit analyser le texte saisi, va bien évidemment être un peu plus compliquée !
|
|
En étudiant les exemples ci-dessus, on comprend très vite que l'analyse du texte (étape B) doit respecter les deux contraintes suivantes :
B3. Elle doit ensuite comparer le premier caractère avec le dernier, le deuxième avec l'avant-dernier et ainsi de suite jusqu'à arriver aux deux caractères du milieu de chaîne (ou au caractère central si le nombre est impair)… Dès qu'une différence est détectée, on sait que le texte ne peut être un palindrome !
[ Sommaire ]
L'étape d'analyse comportant plusieurs traitements, c'est l'occasion de montrer comment découper fonctionnellement une application en déportant un bloc de traitement dans un sous-programme.
Un sous-programme est une fonction (terme général) susceptible de renvoyer un résultat typé (dont le type est défini : comme par exemple un entier, un réel, …) ; si la fonction ne retourne rien, la terminologie du Pseudo-Langage emploie le terme de procédure.
Édition | Convertir en
puis choisir Appel de sous-programme.Le symbole doit changer d'apparence et avoir maintenant des doubles barres verticales. Cela signifie que le traitement de cette étape est détaillé dans un autre organigramme que nous allons maintenant créer…
Édition | Créer un sous-programme ,
renseignez le nom de la nouvelle fonction et son type de retour ;
puisque le résultat de l'analyse doit dire si oui ou non il s'agit d'un palindrome, nous pouvons choisir le type booléen.|
Le type On remarque que l'ébauche du nouvel organigramme commence cette fois par une étiquette portant son nom,
et qu'elle se termine non pas par Il est maintenant possible de naviguer à sa guise entre le programme principal et son sous-programme en cliquant sur l'onglet correspondant. |
|
Enrichissons maintenant l'organigramme de la fonction :
|
|
On comprend dès à présent que c'est l'étape B3 qui sera chargée de fabriquer la valeur booléenne de retour…
[ Sommaire ]
Une question qu'il est temps de se poser : Comment manipuler le texte à étudier ?
Tout comme dans le premier exercice, il va être nécessaire de réserver de l'espace mémoire pour stocker les données fournies par l'utilisateur ; mais ici, il ne s'agit pas d'une simple valeur numérique entière ou réelle mais d'une suite de caractères (lettres, chiffres, symboles de ponctuation,…) dont on ne connait pas à priori le nombre à l'avance.
La manière la plus courante de stocker une chaîne de caractères en mémoire est de ranger les caractères dans une liste
continue – tableau à une dimension – et de faire suivre cette liste par une valeur particulière jouant le rôle de terminateur
(cette valeur particulière est en fait un caractère de valeur nulle, à ne pas confondre avec le caractère chiffre '0'
qui vaut 48 d'après le code ASCII !).
Une chaîne est toujours spécifiée entre guillemets, un caractère unique est indiqué entre apostrophes.
| Exemple : | la représentation mémoire de la chaîne "ABCD" est |
'A' |
'B' |
'C' |
'D' |
0 |
| indice → | 0 |
1 |
2 |
3 |
4 |
|
chaque case d'indice 0, 1, 2, 3 et 4 est un élément de type Caractère |
||||||
⇒ le Pseudo-Langage propose un type nommé Chaine dont la capacité est de 255 caractères.
⇒ chaque élément de la chaîne possède une adresse distincte de type pCaractère (p pour pointeur).
Nous allons donc pouvoir étoffer notre programme en mettant en place les éléments nécessaires à la saisie de texte et à la transmission d'un lien sur ce texte (au hasard, son adresse de base) au sous-programme afin qu'il puisse le traiter…
texte de type Chaine.Saisir( texte ).La fonction Saisir() place automatiquement le terminateur de chaîne lorsque l'utilisateur finalise
sa frappe par la touche Entrée.
Notre fonction
|
|
Notre programme principal doit encore récupérer le résultat retourné par Analyse() et afficher un diagnostic en conséquence :
diagnostic de type Booléen.diagnostic <- Analyse( texte )Mais comment produire un affichage différent en fonction de la valeur de diagnostic ?
[ Sommaire ]
Les langages informatiques savent interpréter des expressions conditionnelles telles que :
 |
alternative complète → | si <condition> alors <instruction1> sinon <instruction2> |
| alternative partielle → | si <condition> alors <instruction> |
 |
itération à condition initiale → | tant que <condition> faire <instruction> |
 |
itération à condition finale → | répéter <instruction> jusqu'à ce que <condition> |
Ces trois constructions correspondent aux structures fondamentales de la programmation structurée.
Les conditions sont toujours évaluées logiquement, elles valent soit
VRAI soit FAUX, comme le type booléen.
Fort de ce nouveau savoir, nous allons donc remplacer l'étape C d'affichage du diagnostic par une alternative complète du style :
si ( diagnostic = VRAI ) alors
Afficher("Bravo ! c'est un palindrome.", CRLF ) ;
sinon
Afficher("Désolé, ce n'est pas un palindrome.", CRLF ) ;
finsi
Que l'on peut mutualiser en :
si ( diagnostic = VRAI ) alors
Afficher("Bravo ! c'est " ) ;
sinon
Afficher("Désolé, ce n'est pas " ) ;
finsi
Afficher("un palindrome.", CRLF ) ;
La condition doit être inscrite dans le losange, la sortie verticale représente la branche de traitement lorsque la condition
vaut
|
|
Le programme principal est terminé ! Vérifions son fonctionnement…
Si tout va bien, quoi que vous rentriez comme texte, le têtu programme doit vous répondre : « Désolé, ce n'est pas un palindrome. ». Frustrant, non ?
Attaquons-nous donc aux algorithmes de la fonction d'analyse…
[ Sommaire ]
Rappelez-vous : La fonction reçoit en argument l'adresse pTexte du texte à traiter…
Quand on connaît une adresse mémoire, on peut en lire et/ou écrire le contenu. La fonction a donc la possibilité de modifier directement le contenu du texte choisi par l'utilisateur.
Mais par principe, nous allons plutôt faire en sorte de travailler sur une copie du texte.
En effet, on peut ici considérer que les données appartiennent au programme principal et que celui-ci peut en avoir
encore besoin par la suite dans leur état d'origine ; d'ailleurs on demande à Analyse() de nous
dire si le texte est un palindrome, on ne lui demande pas d'altérer ce texte !
temp de type Chaine.On souhaite un moyen de faire une copie conforme d'un tableau de caractères dont le dernier est un terminateur :
⇒ en Pseudo-Langage : Copier( temp, pTexte ) ;
# copie les caractères de pTexte dans temp jusqu'à trouver un terminateur (qui est copié aussi)
Et une solution permettant de forcer une chaîne en majuscules :
⇒ en Pseudo-Langage : Majuscules( temp ) ;
# transforme les caractères 'a'..'z' de temp en 'A'..'Z'
|
|
[ Sommaire ]
Là, il faut réfléchir un peu ! Pour mémoire, il faut éliminer de la chaîne temp tous les caractères n'appartenant
pas à l'intervalle 'A'..'Z'.
La longueur de la chaîne (son nombre de caractères) après traitement sera donc inférieure ou égale à sa longueur de départ, il ne faut donc pas oublier de replacer correctement le terminateur.
Nous pouvons accéder à chacun des caractères un par un en spécifiant son indice dans la chaîne :
temp[0] pour le premier, temp[1] pour le deuxième,…
Comment connaître l'indice du dernier caractère ?
⇒ en Pseudo-Langage : Longueur( temp ) ;
# retourne le nombre de caractères dans temp (hors terminateur)
Notez que Longueur( temp ) est équivalent à l'indice du terminateur puisque l'indiçage commence à 0 !
Les caractères de la chaîne temp sont donc accessibles via un indice entier variant de 0
jusqu'à Longueur( temp ) - 1.
Pour trier nos caractères, nous pouvons par exemple utiliser une variable d'indice de lecture iL
et une variable d'indice d'écriture iE. En faisant varier iL de manière à parcourir tous les caractères,
on utilise iE pour les écrire si ils correspondent à nos critères. Ces deux variables doivent être initialisées sur
le premier emplacement. Ces opérations peuvent toutes se dérouler sur la même zone de mémoire
|
|
|
⇒ en Pseudo-Langage : Inc( v ) ;
# incrémentation du contenu de la variable v, équivalent à : v <- v + 1 ;
⇒ en Pseudo-Langage : Dec( v ) ;
# décrémentation du contenu de la variable v, équivalent à : v <- v - 1 ;
temp, comme par exemple Afficher(temp, CRLF ) ;Tout est conforme à vos attentes ? Oui ? Alors on continue !
[ Sommaire ]
Ultime étape de notre super programme, nous allons enfin savoir détecter ces bizarreries du langage tant recherchées que sont les palindromes…
Dans notre analyse globale, nous avons déjà vu le travail à faire pour la phase B3. Il nous faut un indice permettant de parcourir les caractères à partir du premier, et un autre pour les parcourir à partir du dernier.
Nous allons bien sûr travailler sur notre chaîne temp, et nous pouvons réutiliser les deux variables entières iL et
iE ; mais leur rôle change ici, et les commentaires « indice de lecture » et « indice d'écriture » n'ont plus de sens !
Les puristes peuvent, s'ils le souhaitent, déclarer une nouvelle paire de variables avec des noms adaptés…
Analyse <- FAUX en sélectionnant le symbole puis en cliquant
sur Édition | Supprimer ou sur le raccourci
L'étape B3 de l'organigramme doit être remplacée par le traitement suivant :
iL à 0, pour accéder au premier caractère ;iE à Longueur(temp)-1 , pour accéder au dernier caractère ;Analyse à VRAI, on considère en effet par défaut que le texte est
effectivement un palindrome et on va tenter de prouver le contraire en comparant les caractères ;iL <= iE, la condition permet de détecter la fin de parcours de la chaîne ;
la branche de l'itération doit comparer les caractères d'indices iE et iL et positionner Analyse
à FAUX dès qu'une différence est trouvée. Elle se poursuit par la modification des indices iL et iE :
Notre application est maintenant terminée, elle est capable d'analyser des textes (max ≈ 250 caractères), à condition qu'ils ne contiennent pas de lettres accentuées… |
|
[ Sommaire ]
Pour finir, une version complète du programme retravaillé sous MoniaPL afin de montrer la lisibilité du Pseudo-Langage :
# ----------------------------------------------------------------------------
# Nom : palindrome.pl
# Sujet : testeur de palindrome (accents non pris en charge)
# Version : 0.1
#
# Auteur : alain
# Création : 29/05/2010
# Mise à jour : 18/11/2012
# ----------------------------------------------------------------------------
Programme palindrome ;
# variables globales
VARIABLES texte est une Chaine ;
diagnostic est un Booléen ;
# fonction d'analyse du texte, valeur de retour = diagnostic booléen
# ----------------------------------------------------------------------------
# argument pTexte : pointeur sur le début du texte
FONCTION Analyse( pTexte : pCaractère ) : booléen ;
VARIABLES temp est une Chaine ;
iL est un Entier = 0 ; # indice de lecture
iE est un Entier = 0 ; # indice d'écriture
DEBUT
Copier(temp, pTexte ) ; # B1. copie du texte
Majuscules( temp ) ;
TANT QUE ( iL < Longueur( temp ) ) FAIRE # B2. filtrage des caractères
SI ( (temp[iL] >= 'A')ET( temp[iL] <= 'Z') ) ALORS
temp[iE] <- temp[iL] ;
Inc( iE ) ;
FINSI
Inc( iL ) ;
FINTQ
temp[iE] <- caractère(0) ;
iL <- 0 ; # B3. comparaison par paires
iE <- Longueur( temp ) - 1 ;
Analyse <- VRAI ;
TANT QUE ( iL <= iE ) FAIRE
SI ( temp[iL] <> temp[iE] ) ALORS
Analyse <- FAUX ;
FINSI
Inc( iL ) ;
Dec( iE ) ;
FINTQ
FIN
# programme principal
DEBUTPROG
Afficher("Votre texte ? ") ; # A. saisie du texte
Saisir( texte ) ;
diagnostic <- Analyse( texte ) ; # B. analyse
SI ( diagnostic = VRAI ) ALORS # C. production du résultat
Afficher("Bravo ! c'est " ) ;
SINON
Afficher("Désolé, ce n'est pas " ) ;
FINSI
Afficher("un palindrome.", CRLF ) ;
FINPROG
[ Sommaire ]