Algorithmique et programmation

Concepts fondamentaux
Mise en œuvre en Go
1
Concepts fondamentaux

Introduction : les concepts d'algorithme, de

processeur et de programme

2
 Qu’est-ce qu’un algorithme ?

• C’est une séquence d’instructions permettant d’atteindre un but que l’on s’est
xé (le problème à résoudre…).

• Ces instructions consistent à modi er l’existant, à répéter des opérations, à

tester certaines conditions et à faire des choix.

Hey, mais c’est ce qu’on fait tous les jours !

3
fi
fi
 Exemples d’algorithmes
Éplucher et découper en morceaux 4 pommes Golden.
• Une recette de cuisine est un Faire une compote : les mettre dans une casserole avec un
algorithme peu d'eau (1 verre ou 2). Bien remuer. Quand les pommes
commencent à ramollir, ajouter un sachet ou un sachet et
demi de sucre vanillé. Ajouter un peu d'eau si nécessaire.
• dont le but (problème à résoudre) Pendant que la compote cuit, éplucher et couper en quatre
est d'obtenir un plat, les deux dernières pommes, puis, couper les quartiers en
nes lamelles.

Préchau er le four à 210°C (thermostat 7).

• elle est décrite par une séquence
d'instructions Laisser un peu refroidir la compote et étaler la pâte brisée
dans un moule et la piquer avec une fourchette.

Verser la compote sur la pâte et placer les lamelles de

• qui utilisent des ingrédients, des pommes.
récipients et des techniques Mettre au four et laisser cuire pendant 30 min max. Surveiller
culinaires. la cuisson. Vous pouvez ajouter un peu de sucre vanillé sur la
tarte pendant que çà cuit pour caraméliser un peu.

4
fi
ff
Exemples d’algorithmes

• Un trajet est un algorithme :

• but : à partir d’un point de départ

et d’un moyen de transport,
arriver à l’endroit voulu

• il est décrit par une séquence

d'instructions

• qui utilisent des positions, des

distances, …

5
Exemples d’algorithmes
• Un « algorithme informatique » est un
algorithme

• but : résoudre un problème

lire prix
• il est décrit par une séquence d'instructions lire reduc
apayer = prix - reduc
• qui utilisent des valeurs, des
emplacements en mémoire

En résumé, un algorithme est l’expression d’une démarche

(une suite d'instructions) dans un langage adapté au
problème.
6
Algorithmes et processeurs
• Les algorithmes ne sont que des plans, des recettes.

• Ils sont réalisés par des processeurs :

• c’est le "processeur" cuisinier qui exécute la recette,

• c’est le "processeur" conducteur qui fait le trajet,

• c’est un processeur informatique qui exécute l’algorithme informatique.

• Les processeurs ont des compétences différentes : il y a de grands chefs et des

apprentis cuisiniers, il y a des processeurs informatiques de bas niveau et des
processeurs évolués.
7
Algorithmes et programmes
• Un programme est la traduction Exemple d'une recette de cuisine : compétence d'un chef cuisinier

d’un algorithme dans le langage Faire une tarte aux pommes

que comprendra le processeur
chargé de l’exécuter. Exemple d'une recette de cuisine : compétence d'un apprenti cuisinier
Éplucher et découper en morceaux 4 pommes.

• On voit donc que le niveau de Faire une compote : les mettre dans une casserole avec un peu
d'eau (1 verre ou 2). Bien remuer. Quand les pommes commencent à
détail de l’algorithme nal et du ramollir, ajouter un sachet ou un sachet et demi de sucre vanillé.
Ajouter un peu d'eau si nécessaire.
programme dépend des
Pendant que la compote cuit, éplucher et couper en quatre les deux
compétences du processeur dernières pommes, puis, couper les quartiers en nes lamelles.
concerné : plus le processeur est Préchau er le four à 210°C (thermostat 7).
compétent, moins il est nécessaire Laisser un peu refroidir la compote et étaler la pâte brisée dans un
de détailler… moule et la piquer avec une fourchette.

…
8
ff
fi
fi
 Algorithmes et programmes ra nage 1
Faire une compote
Mettre la compote et les pommes coupées en
• Principe des ra nages successifs : lamelles sur la pâte
Faire cuire
• on part du but à atteindre
ra nage 2
Exemple : Faire une tarte aux pommes Faire une compote : les mettre dans une casserole
avec un peu d'eau (1 verre ou 2). Bien remuer.
Quand les pommes commencent à ramollir, ajouter
• et on "raf ne" jusqu’à avoir des un sachet ou un sachet et demi de sucre vanillé.
instructions directement Ajouter un peu d'eau si nécessaire.

compréhensibles par le processeur/ Pendant que la compote cuit, éplucher et couper

en quatre les deux dernières pommes, puis, couper
langage cible. les quartiers en nes lamelles.
…

L’algorithme ne dépend pas du processeur : il dépend uniquement du problème

à résoudre. Mais son niveau de détail dépend des compétences du processeur.
9
ffi
ffi
fi
fi
ffi
Concepts fondamentaux

Écriture d'un algorithme simple

avec "The GoPlay Space"

Tracé de gures géométriques simples

10
fi
Le processeur utilisé : le traceur
• Nous allons dans un premier temps travailler avec un processeur particulier
disponible en ligne à cette adresse (que nous vous conseillons de mettre
dans les favoris de votre navigateur).

• Ce processeur est uniquement capable de tracer des gures géométriques

simples (traits, carrés, rectangles, …)

• Il permet d'introduire les bases de la programmation en langage Go, que nous

approfondirons plus tard.

11

fi
 Le traceur

• Ce processeur s'apparente à une machine capable d'effectuer des tracés :

notre but va consister à guider un stylet pour qu'il se déplace sur une feuille
a n de dessiner une gure.

• Pour cela, nous devrons d'abord concevoir (sur papier) l'algorithme

permettant d'exprimer ce tracé dans notre langue, puis traduire cet algorithme
dans le langage du traceur a n d'obtenir un programme.

• Nous pourrons alors lancer le programme a n de véri er que le tracé répond à

notre attente.

12
fi
fi
fi
fi
fi
Le traceur

• Le stylet peut être en position baissée ou levée (il touche ou pas la feuille).

• Le bras portant le stylet se déplace dans une direction donnée : au départ,

cette direction est le nord mais des instructions permettent de la changer.

• Au départ, le stylet est situé au centre de la feuille, en position levée, et sa

direction est le nord.

13
Le traceur

• Pour tracer un trait, il faut mettre le stylet en contact avec la feuille à l'aide de
la commande Down(). La couleur du tracé sera la « couleur courante » (la
dernière choisie, ou noir par défaut).

• La commande Color(couleur) permet de modi er la couleur du stylet. La

couleur doit être exprimée sous la forme d'une chaîne de caractères entre
guillemets. Vous avez le choix entre "black", "red", "yellow", "purple", "green",
"brown", "pink".

• Up() permet de remettre le stylet en position levée.

14
fi
Le traceur
• La direction courante du stylet peut être directement modi ée à l’aide des commandes
Right() et Left(), qui permettent de changer la direction de 90° vers la droite ou la
gauche.

• La commande Pivote(angle) change la direction du nombre de degrés indiqué vers la

droite : Pivote(30), par exemple.

• Quel que soit son contact avec la feuille, le stylet avance d’un certain nombre de pas
dans la direction courante avec la commande Forward(nbPas) : par exemple,
Forward(5) trace un trait de 5 pas dans la direction courante si le stylet est baissé. Si le
stylet est levé, il est simplement déplacé de 5 pas.

• La commande Say(message) permet d'af cher un message : Say("Fini !!!"), par

exemple.
15
fi
fi
 Le traceur : résumé des fonctionnalités

Compétences Exemples dans le langage du traceur

Baisser / relever le stylet Down() / Up()

Tourner vers la droite / vers la gauche de 90° Right(), Left()

Pivoter d'un certain angle vers la droite Pivote(45)

Avancer de nbPas dans la direction courante Forward(6)

Changer la couleur Color("pink")

Af cher un message Say("Yessss !!!")

16
fi
Utilisation du traceur
• Notre première approche des algorithmes va consister à utiliser les
compétences du traceur pour lui faire tracer des gures géométriques simples.

• Pour ce faire, nous écrirons une séquence d'instructions indiquant comment, à

partir d'un état initial, on fera appel aux compétences du traceur pour obtenir
une gure particulière (= but de l'algorithme).

• Puis, nous traduirons cette suite d'instructions dans le langage du traceur.

• Ceci nous permettra aussi d'introduire les premiers concepts de la

programmation : constantes, variables, séquence d'instructions, répétitions,
etc.
17
fi
fi
Premier exemple

Écrire la séquence d'instructions permettant de tracer un carré

violet de 5 x 5 pas

18
Premier exemple : algorithme grossier

Tracer un carré violet de 5 x 5 pas

C'est un algorithme qui n'est pas au niveau de

compétence du traceur (il ne connait pas cette
commande)

=> il faut raf ner cet algorithme

19
fi
Premier exemple : premier raf nage

On raf ne l'algorithme :
Tracer un carré violet de 5 x 5 pas

par la séquence d'instructions :

Initialisations
Dessiner un carré de 5 x 5
Relever le stylet (*)
20
fi
fi
Premier exemple : deuxième raf nage

On raf ne l'instruction "Initialisations" :

1. Choisir la couleur violet

2. Baisser le stylet

Les compétences du traceur permettent de réaliser les étapes 1 et 2 ;

l'initialisation a été ra née.

21
fi
ffi
fi
Premier exemple : deuxième raf nage

On raf ne l'instruction "Dessiner un carré de 5 x 5" :

1. Avancer de 5 pas (donc vers le nord),
2. Tourner à droite (donc vers l'est),
3. Avancer de 5 pas,
4. Tourner à droite (donc vers le sud),
5. Avancer de 5 pas,
6. Tourner à droite (donc vers l'ouest),
7. Avancer de 5 pas.
Les compétences du traceur permettent de réaliser les étapes 1 à 7 ; le
tracé du carré a été ra né.
22
fi
ffi
fi
Premier exemple : l'algorithme nal

1. Choisir la couleur violet,

2. Baisser le stylet,
3. Avancer de 5 pas (donc vers le nord),
4. Tourner à droite (donc vers l'est),
5. Avancer de 5 pas,
6. Tourner à droite (donc vers le sud),
7. Avancer de 5 pas,
8. Tourner à droite (donc vers l'ouest),
9. Avancer de 5 pas
10. Relever le stylet
Ceci est l'algorithme nal (dans le niveau de détail des compétences du
traceur). On peut maintenant le traduire directement dans le langage du
traceur pour obtenir le programme. 23
fi
fi
 Premier exemple
• L'algorithme nal : • Le programme :

1. Choisir la couleur violet,

func main() {
2. Baisser le stylet, Color("purple")
3. Avancer de 5 pas (donc vers le nord), Down()
4. Tourner à droite (donc vers l'est), Forward(5)
Right()
5. Avancer de 5 pas,
Forward(5)
6. Tourner à droite (donc vers le sud), Right()
7. Avancer de 5 pas, Forward(5)
8. Tourner à droite (donc vers l'ouest), Right()
Forward(5)
9. Avancer de 5 pas Up()
[Link] le stylet }

Voir ce lien…
24
fi
Premier exemple

• Le programme : • et le résultat de son exécution par

le traceur:
func main() {
Color("purple")
Down()
Forward(5)
Right()
Forward(5)
Right()
Forward(5)
Right()
Forward(5)
Up()
}

25
Premier exemple : ce qu'on va faire dans cette UE

À partir d'un énoncé (par exemple : "tracer un carré violet de 5 x 5") :

• Écrire un algorithme qui permet d'atteindre ce but

• Par raf nages successifs : du but à atteindre à l'algorithme nal ;

• Traduire cet algorithme dans le langage du processeur pour obtenir le

programme ;

• Exécuter le programme.

26
fi
fi