Algorithme

Définition

Un algorithme est une suite finie d'opérations non-ambigües permettant de résoudre un problème.

Un bon algorithme doit notamment être :

• clair et précis : il ne doit pas y avoir d'ambiguïté ;

• ordonné : les étapes sont exécutées dans un certain ordre ;

• fini : il doit arriver à un résultat après un nombre fini d'étapes.

Le mot algorithme provient de la forme latine (Algorismus) du nom du mathématicien persan Al Khwarizmi qui a vécu au IXe siècle. Mais les premiers algorithmes remontent aux Babyloniens (-3000 avant JC), avec notamment l'algorithme d'Euclide qui permet de déterminer le plus grand diviseur commun de deux nombres entiers.

Ordinogramme de l'algorithme d'Euclide

Exemples

Il existe différents exemples d'algorithmes:

• une recette de cuisine

• un itinéraire routier

• une notice de montage d'un meuble en kit

• le brossage des dents

• en mathématiques : résoudre une équation du deuxième degré, déterminer si un nombre est premier, etc.

Exercice 1

1. Aidez le chien à rejoindre sa niche en utilisant les flèches: ←, →, ↑ et ↓.

Solution

→ → ↓ → → →

2. Aidez le chien à rejoindre sa niche en écrivant un algorithme avec des mots.

Solution

Avancer, avancer, tourner à droite, avancer, tourner à gauche, avancer, avancer et avancer.

3. Y a-t-il des répétitions dans ton algorithme? Si oui, essayez de formuler autrement pour les éviter.

Solution

Avancer 2 fois, tourner à droite, avancer, tourner à gauche, avancer 3 fois.

Exercice 2

1. Aidez le chien à ramasser tous les os et à rejoindre sa niche en utilisant les flèches: ←, →, ↑ et ↓.

Solution

→ → ↓ → → → ← ← ← ↓ ↓ ← → → → → →

2. Aidez le chien à ramasser tous les os et à rejoindre sa niche avec des mots et sans répétition.

Solution

Avancer 2 fois, ramasser l'os, tourner à droite, avancer, tourner à gauche, avancer 3 fois, ramasser l'os, reculer 3 fois, tourner à droite, avancer 2 fois, tourner à droite, avancer, ramasser l'os, reculer 5 fois.

Exercice 3

1. Aidez le chien à rejoindre sa niche en utilisant les flèches: ←, →, ↑ et ↓.

Solution

→ ↓ ↓ → ↓ ↓ → ↓ ↓ → → → → → →

2. Aidez le chien à rejoindre sa niche avec des mots et sans répétition.

Solution

Faire 3 fois: avancer, tourner à droite, avancer 2 fois, tourner à gauche
Avancer 6 fois

Exercice 4

Aidez le chien à rejoindre sa niche avec des mots et sans répétition.

Solution

Faire 6 fois: avancer tant que possible et tourner à droite.

Du problème à la résolution

Pour résoudre un problème au moyen d'un programme informatique, il y a différentes étapes à suivre :

1. Comprendre et analyser le problème (être capable de l'expliquer)

2. Écrire un algorithme qui résout le problème

3. Programmer l'algorithme dans le langage choisi (pour nous ce sera Python)

4. Exécuter le programme pour obtenir le résultat

5. Tester différents scénarios afin de vérfifier que le programme ne comporte pas d'erreur

Exercice 5

Mettez en pratique différents mécanismes de base d'algorithmique et dans le jeu little-dot. Arriverez-vous à terminer tous les niveaux?