Définitions d'un algorithme et d'un programme
Un algorithme est une liste ordonnée d'instructions. Un programme est un algorithme écrit dans un langage compréhensible par une machine.
Algorithme
Un algorithme est une liste ordonnée d'instructions permettant d'effectuer une tâche, de résoudre un problème.
- Les recettes de cuisine sont des algorithmes permettant d'obtenir un plat.
- Les itinéraires déterminés par un GPS sont des algorithmes permettant de passer d'un lieu à un autre.
- Les plans de montage de meubles en kit sont des algorithmes permettant d'obtenir les meubles concernés.
Programme
Un programme est un algorithme écrit dans un langage compréhensible par une machine (ordinateur, calculatrice, etc.)
Se repérer, décrire, exécuter des déplacements
Certains algorithmes permettent de se repérer dans un plan et décrivent des déplacements. Un quadrillage peut être ajouté au plan.
Coordonnées
Pour repérer un objet dans un plan, on peut utiliser un quadrillage comme ceux correspondant au jeu de la bataille navale.
On repère alors une case du quadrillage en donnant la ligne et la colonne de cette case.
Le regroupement des deux informations s'appelle les « coordonnées » de la case dans le quadrillage.
Dans le quadrillage suivant, la case cochée a pour coordonnées \left( 4;F\right).
On peut décrire les déplacements d'un objet sur un quadrillage en utilisant des instructions.
On utilise alors les instructions suivantes :
- avancer de x pas/carreaux/unités, où x est un entier naturel ;
- tourner à gauche de 90°/effectuer un quart de tour à gauche ;
- tourner à droite de 90°/effectuer un quart de tour à droite ;
- faire demi-tour.
On considère un personnage qui se déplace sur le labyrinthe suivant selon le chemin indiqué.
On peut décrire ses déplacements de la façon suivante :
- avancer de 1 carreau ;
- tourner de 90° vers la droite ;
- avancer de deux carreaux ;
- tourner de 90° vers la gauche ;
- avancer de 5 carreaux ;
- tourner de 90° vers la droite ;
- avancer de 1 carreau ;
- tourner de 90° vers la gauche ;
- avancer de 1 carreau ;
- tourner de 90° vers la gauche ;
- avancer de deux carreaux ;
- tourner de 90° vers la droite ;
- avancer de 1 carreau.
Le quadrillage peut être ajouté à un plan de ville, de quartier d'école, etc.
Pour représenter un déplacement sur un plan, on utilise un quadrillage et le nom des rues :
- On repère la rue de départ et on donne son code avec des lettres et des chiffres.
- On indique la direction et le chemin en suivant le nom des rues et en utilisant des verbes : « monter », « descendre », « droite », « gauche », « reculer », « avancer », « tourner ». On peut également utiliser les points cardinaux : nord, est, sud, ouest.
- On donne enfin le code de la case d'arrivée et le nom de la rue.
Programmer des déplacements
Un algorithme permet aussi de programmer un déplacement. On utilise un quadrillage et les mêmes instructions que pour décrire un déplacement.
On peut programmer les déplacements qu'un objet (un lutin, etc.) doit effectuer sur un quadrillage en utilisant les mêmes instructions que pour décrire un déplacement, soit :
- avancer de x pas/carreaux/unités, où x est un entier naturel ;
- tourner à gauche de 90°/effectuer un quart de tour à gauche ;
- tourner à droite de 90°/effectuer un quart de tour à droite ;
- faire demi-tour.
On souhaite faire effectuer un déplacement au lutin dans le labyrinthe suivant pour atteindre la case rouge.
Si l'on programme :
- avancer de 1 carreau ;
- tourner de 90° vers la gauche :
- avancer de 3 carreaux.
Le lutin effectuera le déplacement suivant :
Plusieurs déplacements permettent d'atteindre le même objectif.
Si l'on reprend l'exemple précédent, le programme suivant permet d'atteindre le même objectif :
- avancer de 1 carreau ;
- tourner de 90° vers la droite ;
- avancer de 2 carreaux ;
- tourner de 90° vers la gauche ;
- avancer de 3 carreaux ;
- tourner de 90° vers la gauche ;
- avancer de 1 carreau ;
- tourner de 90° vers la gauche ;
- avancer de 2 carreaux ;
- tourner de 90° vers la droite ;
- avancer de 2 carreaux ;
- tourner de 90° vers la gauche ;
- avancer de 1 carreau ;
- tourner de 90° vers la droite ;
- avancer de 2 carreaux.
Rédiger des programmes de construction géométrique
Les suites d'instructions à effectuer peuvent être données dans un ordre précis lors de programmes de construction géométrique. On peut utiliser des logiciels de géométrie dynamique ou bien des logiciels de programmation.
Le programme de construction géométrique peut être rédigé en français, comme pour expliquer au téléphone à un camarade qui était absent une figure à reproduire.
On considère le programme de construction suivant :
- tracer un segment [AB] de 6 carreaux de longueur ;
- placer le point C, milieu du segment [AB] ;
- placer le point D, milieu du segment [AC] ;
- placer le point E, milieu du segment [CB] ;
- tracer le cercle de centre A passant par D ;
- tracer le cercle de diamètre [AB] ;
- tracer le cercle de centre B passant par C.
On obtient alors la figure suivante :
Les programmes de construction de figures géométriques sont également utiles lorsqu'on construit la figure souhaitée à l'aide d'un logiciel de géométrie dynamique.
Le logiciel Geogebra, par exemple, permet d'afficher le protocole de construction d'une figure.
Les instructions apparaissent dans l'ordre dans lequel elles ont été saisies.
On reprend l'exemple précédent.
Le protocole de construction affiché par le logiciel Geogebra est alors le suivant :
On peut également utiliser des logiciels de programmation pour construire des figures géométriques.
En exécutant le programme ci-dessous, on demande au chat de Scratch de tracer un triangle équilatéral :
