Algorithmique

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.

<table><tr><td>4.1</td> <td width="100%" align="center"> Analyse du problème</td> </tr></table>

<table><tr><td>4.1.1</td> <td width="100%" align="center"> L'algorithmique</td> </tr></table>

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.

<table><tr><td>4.1.2</td> <td width="100%" align="center"> Réalisation d'un programme et analyse descendante</td> </tr></table>

La résolution d'un problème passe par toute une suite d'étapes :

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 :

1. 
   les erreurs syntaxiques : elles se remarquent à la compilation
   et sont le résultat d'une mauvaise écriture dans le langage de
   programmation.
   
2. 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.

<table><tr><td>4.2</td> <td width="100%" align="center"> Présentation de l'environnement</td> </tr></table>

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.

<blockquote>

</blockquote>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.
  

<blockquote>

</blockquote>

<table><tr><td>Initialisation de l'environnement</td> </tr></table>

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.<blockquote>


</blockquote>

<table><tr><td>4.3</td> <td width="100%" align="center"> Structures de programme</td> </tr></table>

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.

<table><tr><td>4.3.1</td> <td width="100%" align="center"> La séquence</td> </tr></table>

<table><tr><td> Algorithmique</td> </tr></table>

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.

<table><tr><td> Exemples et exercices</td> </tr></table>

1. Le robot se trouve dans le coin sud-ouest, orienté vers le
   nord. Avancer de trois cases.
   
2. Idem. Avancer de trois cases, tourner à droite, avancer de cinq
   cases.
   
3. Idem. Avancer de 3 cases, demi-tour, revenir au départ,
   demi-tour.
   
4. Idem. Le robot se promène sur la grille et décrit un carré de
   quatre cases sur quatre.
   

<table><tr><td>4.3.2</td> <td width="100%" align="center"> L'alternative</td> </tr></table>

<table><tr><td> Algorithmique</td> </tr></table>

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é.

<table><tr><td> Exemples et exercices</td> </tr></table>

1. Le robot avance si la case devant lui est libre (pas devant
   un mur).
   
2. Le robot avance si la case devant lui est libre, sinon il
   fait demi-tour.
   
3. 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.
   

<table><tr><td>4.3.3</td> <td width="100%" align="center"> L'itération</td> </tr></table>

<table><tr><td> Algorithmique</td> </tr></table>

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é.

<table><tr><td> Exemples et exercices</td> </tr></table>

1. 
   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.
   
2. Le robot se trouve dans le coin sud-ouest. Aller jusqu'au
   coin nord-ouest.
   
3. Idem. Aller jusqu'au coin nord-ouest et retour.
   
4. Idem. Aller jusqu'au coin nord-est.
   
5. Le Robot est dans le coin NordOuest. Le trésor est soit dans le
   coin Nord Est, soit dans le coin Sud Ouest.
   

<table><tr><td>4.4</td> <td width="100%" align="center"> Procédures</td> </tr></table>

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

<table><tr><td>4.4.1</td> <td width="100%" align="center"> Exemples et exercices</td> </tr></table>

1. 
   Le robot est dans le coin sud ouest orienté vers le nord. Le
   trésor est sur le bord sud. Le trouver.
   
2. Le robot est dans le coin sud ouest orienté vers le nord. Le
   trésor est sur le bord est. Le trouver.
   
3. Le robot est dans le coin sud ouest orienté vers le nord. Le
   trésor est sur un bord. Le trouver.
   
4. Le robot est sur le bord sud, vers l'est. Faire le tour du
   terrain.
   
5. Le robot est placé au hasard. Aller dans un coin, peu importe
   lequel.
   
6. Le robot est placé au hasard. Faire le tour du terrain.
   
7. Le robot est placé au hasard. Le trésor est sur l'un des bord.
   Le trouver.
   
8. Le robot est dans un coin, il avance de 5 cases sans rencontrer
   le mur.
   
9. Le robot et le trésor sont placés au hasard. Le robot doit
   trouver le trésor.
   

<table><tr><td>4.5</td> <td width="100%" align="center"> Ce qu'il faut faire</td> </tr></table>

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.