Algorithmique : présentation

Eric Obermeyer - Actualisation : juin 2014

I) Qu’est-ce qu’un algorithme ?

1) Origine du mot « algorithme »

Le terme  « algorithme »  vient du nom du mathématicien perse  Al-Khwarizmi   (IXième siècle). Il se  référait à l'origine uniquement aux règles d'arithmétique puis le sens du mot a évolué jusqu’à désigner toutes les procédures définies pour résoudre un problème ou accomplir une tâche.

2) Définition

Un algorithme est la description précise d'une suite  finie d'actions s'appliquant à un ensemble de données et qui finalement (c'est à dire à la fin de la suite d'actions) résout le problème posé.

3) Remarque

Avec cette définition, il y a beaucoup d'algorithmes en dehors du champ informatique. Par exemple une recette de cuisine permettant la confection d'un gâteau à partir des ingrédients de base est un algorithme.

  Cependant le terme « algorithme » s'utilise surtout (nous nous plaçons uniquement dans cette optique ici)  lorsque les problèmes peuvent être résolus à l’aide d’un programme exécuté par un ordinateur.

4) Algorithme ou programme ?

Un programme est la traduction d’un algorithme dans un langage de programmation exécutable par un ordinateur.

On peut alors dire qu’un algorithme est un programme dont l’exécutant est l’être humain. Dans la suite, les termes algorithme et programme auront un sens équivalent.

5) Instructions, code

Les instructions sont les actions effectuées par un algorithme (ou un programme).

Le code d’un algorithme est le texte composé de l’ensemble des instructions de cet algorithme.

II) Règles du jeu

1) Règle de base

Il n'y a guère qu'une « règle du « jeu » lors de la conception d’un algorithme: un algorithme doit pouvoir se traduire dans un langage de programmation.

Le choix de ce langage de programmation dépend de la nature ou la complexité du problème posé. Le langage choisi est ici Python.

2) Du problème à sa résolution

Les étapes (A,B,C,D) et les chemins (1,2,3) menant de l’une à l’autre sont toujours les mêmes :

 

(A) Problème à résoudre

          (1) Conception d’un algorithme permettant sa résolution

(B) Algorithme

          (2) Traduction de l’algorithme dans le langage de programmation choisi

(C) Programme

          (3) Exécution du programme par un ordinateur

(D) Solution du problème

3) Pseudo-langage de programmation et pseudo-code

Il n'y a pas de langage « obligatoire » pour écrire un algorithme : un algorithme doit pouvoir être traduit dans un langage de programmation, et c’est tout.

 Tous les langages de programmation ont les mêmes fondements : ils permettent de manipuler des valeurs et des variables à l’aide d’instructions de base que l’on retrouve dans chaque langage.

On peut écrire un algorithme directement dans un langage de programmation, mais il est souvent plus clair de l'écrire dans une langue rigoureuse, qui n’est pas un langage de programmation, mais qui en est très proche.

Un tel langage est un pseudo-langage de programmation. Il n’y a pas de convention universelle pour ce langage, le vocabulaire et les règles changent un peu d’un professeur ou d’un livre à l’autre, mais il doit être facile de s’adapter. Le code d'un algorithme écrit dans ce langage est appelé pseudo-code.

Comme Python (le langage d'application choisi) est un langage de programmation particulièrement concis et clair, on peut l'utiliser (à quelques détails près) comme pseudo-langage.

4) Comment concevoir  un algorithme ?

En s’imposant de ne faire que des opérations et manipulations compatibles avec les principes de base, en sachant que les calculs compliqués ou nombreux seront exécutés correctement et rapidement par l’ordinateur, la seule question que l’on doit se poser est :

 

Comment ferais-je pour résoudre le problème posé avec ma tête, un crayon et une feuille de papier ?

5) Un bon algorithme résout le problème posé, mais le résout aussi:

a) en un temps raisonnable

Indépendamment des performances matérielles  de l’ordinateur et de l’efficacité du compilateur du langage de programmation utilisé,  le coût (c’est le terme employé) en temps d’un algorithme est calculé en évaluant le nombre d’opérations élémentaires (comparaisons, affectations, opérations arithmétiques) effectuées lors de l’exécution de l’algorithme pour une taille n des données entrées. (Voir le cours: "Coût et complexité d'un algorithme")

b) en utilisant un espace mémoire raisonnable

De la même façon qu’un algorithme a un coût temporel, il a aussi un coût spatial, calculé en évaluant la place en mémoire nécessaire à l’exécution de l’algorithme pour une taille n des données entrées.