L'ordinateur effectue
des traitements sur des données. L'objectif de cette partie est de se
sensibiliser et se familiariser avec la logique sous-jacente à l'activité de
l'ordinateur : la logique des traitements. On montre à l'aide d'une interface
simple, le maniement d'un robot, comment décomposer un problème en problèmes
plus simples et les structures de contrôle du déroulement d'un traitement.
L'algorithmique
est une suite de raisonnements ou d'opérations qui fournit la solution d'un
problème.
Le programme ne sera que la traduction de l'algorithme dans un
langage de programmation, c'est-à-dire, un langage plus simple que le français
dans sa syntaxe, sans ambiguités, que la machine peut utiliser et transformer
pour exécuter les actions qu'il peut décrire. Pascal, C, Java, Visual Basic,
sont des noms de langages de programmation.
| 1.2 |
Réalisation d'un
programme et analyse
descendante | | La
résolution d'un problème passe par toute une suite d'étapes :
Enoncé du problème et données
¯
Spécification
¯
Cahier
des charges
¯
Analyse
¯
Algorithme
¯
Traduction
en langage et édition
¯
Programme Source
¯
Compilation
¯
Programme
exécutable
¯
Exécution
¯
Résultats
Le travail est ici surtout basé sur
l'analyse et l'écriture de l'algorithme.
La réalisation d'un programme
passe par l'analyse descendante du problème : il faut réussir à trouver les
actions élémentaires qui, en partant d'un environnement initial, nous conduisent
à l'état final. Une fois ces actions déterminées, il suffit de les traduire dans
le langage de programmation choisi.
Durant l'écriture d'un programme, on
peut être confronté à 2 types d'erreur :
- les erreurs syntaxiques : elles se remarquent à la compilation et sont le
résultat d'une mauvaise écriture dans le langage de programmation.
- les erreurs sémantiques : elles se remarquent à l'exécution et sont le
résultat d'une mauvaise analyse. Ces erreurs sont beaucoup plus graves car
elles peuvent se déclencher en cours d'exploitation du programme.
Pour
vous permettre d'éviter les erreurs les plus simples, nous avons mis à votre
disposition un logiciel qui permet de saisir un algorithme sans avoir à
connaître la syntaxe d'un langage de programmation. Ainsi, toutes les erreurs
syntaxiques sont évitées. Vous vous concentrerez donc uniquement sur la partie
sémantique de l'écriture d'un programme.
| 2 |
Présentation de
l'environnement | |
Un
robot se déplace dans un domaine rectangulaire de dimensions finies, divisé en
cases. Cet espace sera délimité par une frontiére.
Les cases pourront
être vides, marquées ou contenir un trésor. C'est le robot qui dépose
éventuellement des marques pour laisser la trace de son passage, tel le metit
poucet.
Figure 4.1 : Le robot sur son terrain avec un
trésor Le robot sait réaliser quelques actions élémentaires et faire
quelques observations sur son environnement, appelés des tests.
- Actions
-
 | Avancer : Le robot avance dans sa direction d'une case. S'il se trouvait devant un mur, le programme
s'arrête et vous invective (en principe pas trop méchammment).
| ADroite : Le robot tourne d'un quart de tour vers la droite
(ou, si vous préférez, dans le sens des aiguilles d'une montre, ou encore,
dans le sens anti-trigonométrique).
| DeposerMarque : Le robotdépose une marque à l'endroit où il se
trouve.
| EnleverMarque : Le robotefface la marque à l'endroit où il se
trouve. Si cet emplacement ne contient pas de marque, cette action ne fait
rien. |
| | |
Tests
| DevantMur : la réponse est oui s'il se trouve devant
un mur, non dans tous les autres cas.
| Devant Marque : la réponse est oui s'il se trouve
devant une marque, non dans tous les autres cas.
| Sur Marque : la réponse est oui s'il se trouve sur une
marque, non dans tous les autres cas. |
| |
Les tests
peuvent être combinés avec des opérateurs logiques.
| Le Non inverse la valeur du test. Par exemple Non Devant
Mur est vrai si le robot n'est pas devant un mur.
| Le Et permet de tester deux conditions. Par exemple Devant
Mur et Sur Marque est vrai si le robot est sur une
marque et devant un mur. Ce test est faux dans tous les autres cas,
c'est-à-dire, si le robot n'est pas devant un mur ou si le robot n'est
pas sur une marque.
| Let Ou permet de tester si au moins une conditions est vraie. Par
exemple Devant Mur ou Sur Marque est vrai si le
robot est sur une marque ou devant un mur. Ce test est faux dans tous les
autres cas, c'est-à-dire, si le robot n'est pas devant un mur et si le
robot n'est pas sur une marque. |
| |
Figure 4.2 : La fenêtre de saisie d'un
algorithme
| Initialisation de
l'environnement | |
Si
vous ne précisez rien, le robot est placé au hasard sur le terrain, dans une
direction aléatoire. Vous pouvez lui imposer (dans certaines limites) une
position et une orientation initiales.
Attention : vous ne pouvez
utiliser ces instructions qu'une seule fois par programme ; vous ne pouvez pas
les utiliser après une quelconque action du robot.
- Place du tresor
- : les valeurs possibles sont : Hasard, UnBord,
BordNord, BordSud, UnCoin, BordEst,
BordOuest, CoinNE, CoinNO, CoinSE et
CoinSO.
- Place du robot
- : les valeurs possibles sont : Hasard, UnBord,
BordNord, BordSud, BordEst, UnCoin,
BordOuest, CoinNE, CoinNO, CoinSE et
CoinSO.
- Orientation du robot
- : les valeurs possibles sont : Hasard, Nord,
Sud, Est et Ouest.
Figure 4.3 : La fenêtre de pour la saisie des
initialisations
| 3 |
Structures de
programme | |
Un
programme est une suite d'actions. L'exécution du programme correspond à l'éxécution de la suite des actions qui le compose. Les structures de contrôle
indiqueront comment s'organisent les actions dans le temps, comment elles
s'enchaînent.
Il y a 3 types de structures : la séquence, l'alternative
et l'itérative.
La
séquence est la structure la plus simple que l'on puisse
trouver.
L'exécution d'une telle structure correspond à l'exécution des
instructions les unes à la suite des autres. En langage algorithmique, cela
donne :
Instruction1
Instruction2
Instruction3
...
InstructionN
On exécute d'abord Instruction1 puis Instruction2,
Instruction3,... et enfin InstructionN.
- Le robot se trouve dans le coin sud-ouest, orienté vers le nord. Avancer
de trois cases.
- Idem. Avancer de trois cases, tourner à droite, avancer de cinq
cases.
- Idem. Avancer de 3 cases, demi-tour, revenir au départ, demi-tour.
- Idem. Le robot se promène sur la grille et décrit un carré de quatre cases
sur quatre.
L'alternative
est une structure qui permet l'exécution d'une action ou d'une séquence
d'actions à partir du moment où une condition est vérifiée.
SI condition
FAIRE
Instruction1
SINON
Instruction2
FIN DU SI
Si la condition condition est vraie, les instructions dans
Instruction1 sont exécutées. Dans le cas contraire, ce sont les
instructions dans Instruction2 aui sont exécutées.
La partie
SINON n'est pas obligatoire, quand elle n'existe pas et que la
condition condition n'est pas vérifiée, aucun traitement n'est
réalisé.
- Le robot avance si la case devant lui est libre (pas devant un
mur).
- Le robot avance si la case devant lui est libre, sinon il fait
demi-tour.
- Le robot se trouve dans le coin nord-est, orienté vers l'ouest. Le robot
doit avancer de deux cases au plus. Si le robot se trouve devant un trésor
lors de son déplacement, il est si content qu'il fait un tout sur place avant
de se jeter dessus.
L'itérative
est une structure qui permet l'exécution d'une action ou d'une séquence
d'actions tant qu'une condition est vérifiée.
TANT QUE condition
Instructions
FIN DU TANT QUE
Si la condition condition est vraie, les instructions dans
Instructions sont exécutées. Puis, on retourne tester la condition.
Dans le cas contraire, l'itération est terminée. On dit alors que l'on sort de
la boucle.
La condition est toujours évaluée avant de faire le
traitement. Donc, si la condition n'est jamais vraie, le traitement n'est jamais
effectué.
- Le robot se trouve dans le coin sud-ouest, orienté vers le nord. Le trésor
se trouve sur le bord ouest. Dirigez le robot pour qu'il atteigne le trésor.
- Le robot se trouve dans le coin sud-ouest. Aller jusqu'au coin nord-ouest.
- Idem. Aller jusqu'au coin nord-ouest et retour.
- Idem. Aller jusqu'au coin nord-est.
- Le Robot est dans le coin NordOuest. Le trésor est soit dans le coin Nord
Est, soit dans le coin Sud Ouest.
L'écriture
de procédures a principalement deux avantages. Elle permet de rendre les
algorithmes plus lisibles, et donc plus faciles à comprendre, à corriger, à
modifier ; elle permet de << factoriser >> les algorithmes et donc
de rendre plus courte leur écriture : un morceau d'algorithme qui se répète
souvent peut devenir une procédure qui sera utilisée chaque fois que cela sera
nécessaire.
Par exemple, on veut faire faire le tour du terrain au robot
partant du coin Nord Ouest, orienté vers l'est. Il suffit d'écrire l'algorithme
suivant :Tant Que Non Devant Mur
Avancer
Fin du Tant que
A droite
Tant Que Non Devant Mur
Avancer
Fin du Tant que
A droite
Tant Que Non Devant Mur
Avancer
Fin du Tant que
A droite
Tant Que Non Devant Mur
Avancer
Fin du Tant que
A droite
On peut créer une procédure qui dit : << Je vais jusqu'au mur et je
tourne à droite >>. Appelons << Jusqu'au mur >> cette
procédure. Elle s'écrit facilement
Tant Que Non Devant Mur
Avancer
Fin du Tant que
A droite
Maintenant, le programme va utiliser la procédure en s'écivant plus
simplement de cette façon :Jusqu'au mur
Jusqu'au mur
Jusqu'au mur
Jusqu'au mur
| 4.1 |
Exemples et
exercices | |
- Le robot est dans le coin sud ouest orienté vers le nord. Le trésor est
sur le bord sud. Le trouver.
- Le robot est dans le coin sud ouest orienté vers le nord. Le trésor est
sur le bord est. Le trouver.
- Le robot est dans le coin sud ouest orienté vers le nord. Le trésor est
sur un bord. Le trouver.
- Le robot est sur le bord sud, vers l'est. Faire le tour du terrain.
- Le robot est placé au hasard. Aller dans un coin, peu importe lequel.
- Le robot est placé au hasard. Faire le tour du terrain.
- Le robot est placé au hasard. Le trésor est sur l'un des bord. Le trouver.
- Le robot est dans un coin, il avance de 5 cases sans rencontrer le mur.
- Le robot et le trésor sont placés au hasard. Le robot doit trouver le
trésor.
Les
exercices sur le robot sont énoncés en vous présentant un cahier des charges.
Par exemple : << le robot se trouve dans un coin, le faire avancer de
3 cases en ligne droite sans qu'il ne rencontre de mur. >>. Vous
devez écrire l'algorithme tel qu'il se présente dans la fenêtre de saisie du
logiciel.
Nous insistons sur plusieurs points :
| Il faut respecter la syntaxe et la présentation des algorithmes. Ne pas
oublier de mettre en particulier les ALORS, SINON, FIN DE SI, les TANT QUE et
FIN DE TANT QUE. Toutefois, les abréviations TQ et FIN TQ sont
autorisées.
Les décalages vers la droite des instructions (cette
opération se nomme << indentation >>) dans les structures
tels que le SI ou le TANT QUE sont nécessaires.
| Tout doit être précisé. Si vous utilisez des procédures, celles-ci doivent
être décrites, même si elle a déjà été décrite en cours ou en TD. |
|
|
.htm_cmp_sumipntg010_vbtn.gif){kind=small}
