Chapitre 1: Les ingrédients d’un algorithme

Contenus Capacités attendues Commentaires
Constructions élémentaires Mettre en évidence un corpus de constructions élémentaires. boucles non bornées, appels de fonction. Séquences, affectation, conditionnelles, boucles bornées,

Alan Turing a montré que pour que les machines puissent résoudre des problèmes, il fallait traduire ces problèmes en algorithmes. Dans ce chapitre, nous allons voir quels sont les ingrédients de base d’un algorithme, puis comment les écrire en Python.

Le mot algorithme vient d'Al-Khwârizmî (en arabe : الخوارزمي), nom d'un mathématicien persan du IXe siècle.
Le mot algorithme vient d'Al-Khwârizmî (en arabe : الخوارزمي), nom d'un mathématicien persan du IXe siècle.
 Public domain via Wikimedia Commons

1 Les ingrédients des Algorithmes

Un algorithme utilise cinq ingrédients de base:

  1. Un algorithme est un chemin à parcourir pas à pas, une séquence d’instructions.
  2. Cependant, il ne faut pas forcément effectuer toutes les instructions en fonctions de conditions: les instructions conditionnelles.
  3. Nous avons aussi besoin d’une autre construction, la boucle d’instructions qui permet de faire durer ou répéter une opération autant de fois que nécessaire.
  4. Nous introduisons la notion de variable ou de paramètre qui permettra de modifier le programme en fonction de ces paramètres.
  5. La dernière construction, qui consiste à regrouper un bloc d’instructions dans une fonction, va nous permettre de réutiliser différentes fonctionnalités, comme les briques d’un jeu de Lego, pour réaliser une construction logicielle.

Les ingrédients des algorithmes sur le site Interstices

2 Traduire des algorithmes en Python

Pour que les ordinateurs réalisent nos algorithmes, nous devons écrire les séquences d’instructions dans un langage de programmation, dans notre cas Python.

2.1 Séquence d’instructions

En Python, les lignes du programme sont exécutées de haut en bas, à l’exception:

  • Des lignes de commentaires qui commencent #.
print("Hello")
# print("World")

N’affichera que "Hello" en sortie, car la deuxième ligne est commentée donc non exécutée.

  • Des lignes de bloc qui sont indentées par rapport à la colonne de gauche.
print("Hello")
    print("World")

Renvoie une erreur IndentationError, car la deuxième ligne est indentée et ne devrait pas l’être.

2.2 Les variables

C’est un moyen de donner un nom à des valeurs afin de pouvoir les réutiliser aisément par la suite.

PI = 3.141592653589793
R = 1 
print("Le périmètre est:", 2*PI*R)
print("La surface est:", PI*R**2)

>>sortie

Le périmètre est: 6.283185307179586
La surface est: 3.141592653589793

Nous avons ici affecté deux variables PI et R dont nous pouvons nous servir tout au long du programme par la suite.

2.3 Instructions conditionnelles

Il s’agit de blocs d’instructions exécutés en fonction de certaines conditions, nous voyons ici:

  • if(si en français), qui peut être complété par un
  • else(sinon en français).
age = int(input("Quel âge avez-vous?")
if age > 14:
    print("OK")
else:
    print("not OK")

Il existe également le mot-clé, elif(sinon si en français) en Python. Qui permet de tester plusieurs conditions.

age = int(input("Quel âge avez-vous?")
if age > 18:
    print("Vous ne devriez plus être en lycée!")
elif age > 14:
    print("OK")
else:
    print("not OK")

Attention à l’ordre des conditions, car le bloc de la première condition vérifiée est le seul exécuté.

2.4 Boucle d’instructions

Pour effectuer des répétitions en boucle, on utilise les instructions:

  • for: pour en français.
  • while: tant que en français.

Les deux types de boucles sont interchangeables, on préfère cependant utiliser:

  • for si le nombre d’itérations est connu à l’avance.
  • while si l’arrêt s’effectue à une condition.
for i in range(5):
    print(i)

>>sortie

0
1
2
3
4
i = 0 # initialisation
while i < 5: # condition d'arrêt
    print(i)
    i = i + 1 # incrémentation de l'indice

>>sortie

0
1
2
3
4

2.5 Les fonctions

Il s’agit de blocs d’instructions exécutés à la demande, on les définit par le mot-clef def.

def dit_bonjour(prenom):
    print("Bonjour " + prenom)

Nous venons de définir la fonction, mais pour l’instant, il ne se passe rien.

Pour exécuter le code de la fonction, il faut maintenant appeler la fonction avec une valeur pour l’exécuter.

# on appelle la fonction avec l'argument Ada
dit_bonjour("Ada")

>>sortie

Bonjour Ada

Une fonction peut prendre zéro ou plusieurs paramètres séparés par des virgules en entrée.

# import du module datetime
import datetime


# fonction sans argument
def heure():
    print("Il est:", datetime.datetime.now().time())

# appel de la fonction
heure()

>>sortie

Il est: 15:14:56.712057

Une fonction peut renvoyer une valeur grâce au mot-clé return.

def aire_rectangle(L, l):
    """Fonction qui renvoie l'aire d'un rectangle"""
    return L * l

# appel est affectation de la valeur renvoyée à la variable S
S = aire_rectangle(3,5)

print("L'aire est:", S)

>>sortie

L'aire est: 15