Home
About

Définition d'un algorithme

Cours/Algorithmie/Bases théoriques/Définition d'un algorithme

On doit le mot algorithme à Ada Lovelace (1815-1852) qui est le(a) premier(e) informaticien(ne) de l'histoire. Elle a donné ce nom en hommage à un savant persan du 9ème siècle (né vers 780 et mort en 850 à Bagdad) nommé Al-Khwârizmî qui a publié le premier manuel d'algèbre connu à ce jour.

Algorithme ?

Définition du 'Petit Robert' d'un algorithme :

Un algorithme est un ensemble des règles opératoires propres à un calcul.

Qu'est-ce que ça veut dire ?

Tel monsieur Jourdain, on a utilisé un algorithme pour comprendre ce qu'est un algorithme ! Formalisons le :

Nom : comprendre_une_définition_du_petit_Robert
Entrées :
    m : un mot à définir
Programme :
    1. étant donné la définition de m dans le dictionnaire du 'Petit Robert'
    2. afficher la définition à l'écran
    3. pour chaque mot non compris dans la définition :
       3.1. comprendre_une_définition_du_petit_Robert(mot)

C'est un algorithme tout à fait valable. Ce n'est pas du python, mais c'est :

Règles de construction de l'algorithme utilisé :

Donald Knuth (1938-) liste, comme prérequis d'un algorithme, cinq propriétés :

On peut en déduire la définition suivante : Un algorithme est une succession d'instructions simples et clairement définies. A partir d'entrées, il produit une sortie en un nombre fini d'instructions. Ou, de façon équivalente :

Définition

Un algorithme est défini par les 4 propriétés suivantes :

  1. un algorithme est constitué d'un suite fini d'instructions, chacune décrite avec un nombre fini de symboles
  2. un humain doit pouvoir suivre chaque étape avec un papier et un crayon
  3. exécuter une instruction ne doit pas nécessiter d'intelligence (à part celle pour comprendre l'instruction)
  4. l'algorithme produit un résultat et s'arrête après un nombre fini d'étapes (une étape étant l'application d'une instruction) successives.

On appellera programme un texte qui ne respecte que les 3 premières propriétés : un algorithme est un programme qui s'arrête.

Une recette de cuisine est donc un algorithme, un trajet google maps, etc.

Programmes et Algorithmes

Prenons l'énoncé suivant qui décrit une procédure permettant de chercher un élément particulier dans une suite finie de nombres :

Demander à l'utilisateur :
  - de donner un entier que l'on appellera x
  - de donner une suite d'entiers que l'on appellera t

parcourir chaque élément de t jusqu'à trouver un élément dont la valeur est égale à la valeur de x.
Si on trouve un tel élément, afficher "Vrai" à l'écran.

Pour transformer cette description en algorithme, il faut procéder à plusieurs modifications :

  1. Un programme a un nom pour qu'on puisse le retrouver une fois décrit
  2. L'utilisateur n'existe pas : un programme doit exister en tant que tel. Les entrées (demander des choses à l'utilisateur) et les sorties (afficher des résultats) sont abstraites :
    • on parle de paramètres d'entrées du programme
    • on parle de sortie du programme (le programme rend quelque chose, comme une fonction)

En appliquant ces règles, la description précédente devient :

Nom : recherche
Entrées :
    t : un tableau d'entiers
    x : un entier
Programme :
 
    parcourir chaque élément de t jusqu'à trouver un élément dont la valeur est égale à la valeur de x.
    Si on trouve un tel élément, rendre "Vrai".

Il nous manque cependant encore une chose : si le programme s'arrête il doit rendre quelque chose, ce qui n'est pas le cas ici si on ne trouve pas x dans t. Modifions le :

Nom : recherche
Entrées :
    t : un tableau d'entiers
    x : un entier
Programme :
 
    parcourir chaque élément de t jusqu'à trouver un élément dont la valeur est égale à la valeur de x.
    Si on trouve un tel élément, rendre "Vrai".
    Sinon rendre "Faux".

Notre programme s'arrêtant tout le temps, c'est même un algorithme.

À retenir

Un programme programme possède :

  • un nom
  • des paramètres d'entrées (il peut y en avoir 0). Chaque paramètre à un nom qui pourra être utilisé dans la description du programme et un type qui décrit sa nature.
  • une sortie. Si le programme s'arrête il doit rendre quelque chose.
  • une description qui explicite ce qu'il fait.

Si le programme s'arrête quelque soient ses entrées, c'est un algorithme.

Afficher un résultat à l'écran est différent de rendre un résultat : le premier s'adresse à un utilisateur et est perdu, le second peut être à nouveau utilisé par au autre programme.

La définition très générale d'un algorithme se décline usuellement sous deux formes concrètes :

  1. le pseudo-code : l'écriture (sans ordinateur) d'algorithmes en utilisant un nombre restreint d'instructions générales précisément définies. Un pseudo-code n'est pas directement fait pour être exécuté par un ordinateur, même si l'on peut utiliser la syntaxe d'un langage de programmation pour le décrire (le python, par exemple, est très utilisé pour décrire des algorithmes). Le but ici est de montrer que l'on peut résoudre un problème donné avec un algorithme.
  2. le code : l'écriture d'un programme pouvant s'exécuter sur un ordinateur. Le but sera ici de faire en sorte de vérifier que le code correspond bien au pseudo-code et — surtout — de maintenir son fonctionnement au court du temps.

Par exemple l'algorithme recherche s'écrirait en pseudo-code de cette façon :

algorithme recherche(t: [entier],
                     x: entier
                    ) → booléen:

    pour chaque e de t:
        si e == x:
            rendre Vrai
    rendre Faux

Et en code python (qui est très similaire au pseudo-code) :

def recherche(t, x):
    for e in t:
        if e == x:
            return True
    return False

Ces deux formes ont des buts différents, mais on ne peut exceller dans l'une sans connaître l'autre. Tout théoricien doit avoir de bonnes connaissances pratiques sur ce que peut calculer un ordinateur et — tôt ou tard — il devra programmer ses algorithmes. Réciproquement, tout développeur doit avoir des connaissances fortes en algorithmie pour pouvoir écrire du code performant.

Mais avant de n'utiliser plus que du pseudo-code, regardons ce que cela veut dire d'écrire un algorithme de façon générale et sans autres contraintes que celle de la définition.

Nombre de programmes

La définition générale d'un programme stipule qu'il doit être constitué d'un nombre fini d'instructions, chaque instruction décrite par un nombre fini de symboles. De plus, c'est implicite, mais un programme doit être compris par un humain.

Une infinité de programmes différents

On va se concentrer sur les algorithmes puisque tout algorithme est un programme. De la définition d'un algorithme on peut donc déjà conclure que :

Proposition

Il existe une infinité d'algorithmes différents.

preuve

Si on considère l'instruction Ne fait rien, le texte ci-dessous est un algorithme d'une instruction :

Ne fait rien

En notant alors $R_k$ ($k >0$) l'algorithme de $k$ instructions Ne fait rien à la suite (l'algorithme précédent est $R_1$).

Les algorithmes $R_k$ sont tous différents puisque leurs suites d'instructions sont différentes : il existe donc une infinité d'algorithmes différents.

De la preuve de la proposition précédente montre qu'il existe une infinité d’algorithmes différents mais faisant la même chose : tous les algorithmes $R_k$ pour $k$ entier font la même chose, rien.

On y reviendra, mais savoir ce que fait un algorithme n'est pas un problème simple du tout dans le cas général.

Mais, on peut aussi démontrer :

Proposition

Il existe une infinité d'algorithmes faisant des choses deux à deux différentes.

preuve

On peut par exemple considérer la familles $A_k$ d'algorithmes ($k > 0$) définis tels que $A_k$ soit constitué d'une seule instruction :

Rend l'entier k

Les $A_k$ sont bien des algorithmes puisque chaque entier $k$ se décrit avec un nombre fini de chiffres. De plus, les $A_k$ rendent tous des entiers différents.

Il y a donc beaucoup d'algorithmes possibles... mais en réalité pas tant que ça.

Mais seulement une infinité dénombrable

D'après ce qui précède, un algorithme est un texte. On peut alors considérer que les symboles formant la description de chaque instruction sont des caractères pris dans un alphabet. Pour ne pas être chiche, on peut prendre l'alphabet Unicode qui permet d'écrire, entre autres, en Français et contient un peut moins de 150000 caractères différents.

De là :

Proposition

Un programme est une suite finie $c_1 \dots c_n$ où :

  • $c_i \in \mathcal{U}$ pour tout $1 \leq i \leq n$
  • avec $\mathcal{U}$ l'ensemble des caractères Unicode, $\vert \mathcal{U} \vert \leq 150000$.

On note $\mathcal{A}$ cet ensemble.

preuve

Un algorithme est composée d'une suite finie d'instruction. Comme chaque instruction peut être nommée par un texte et que chaque instruction est décrite un texte en Français, tout algorithme est une suite de caractères Unicode.

Bref, les programmes correspondent à un sous-ensemble de l'ensemble des chaînes de caractères écrites en Unicode. On peut alors utiliser l'ordre entre caractères Unicode (chaque caractère est identifié par un entier) pour ordonner les algorithmes selon l'ordre du dictionnaire :

Proposition

On peut associer à toute chaîne de caractère un entier strictement positif unique.

preuve

Il suffit d'associer le numéro de chaque caractère Unicode écrit avec 6 chiffres. Une chaîne de caractère $(c_i)_{0\leq i < n}$ est alors une suite de $6n$ chiffres. Par exemple : l'instruction "Ne fait rien" correspond au nombre :

$$ \underbracket{000078}_{\text{N}}\underbracket{000101}_{\text{e}}\underbracket{000032}_{\text{ }}\underbracket{000102}_{\text{f}}\underbracket{000097}_{\text{a}}\underbracket{000105}_{\text{i}}\underbracket{000116}_{\text{t}}\underbracket{000032}_{\text{ }}\underbracket{000114}_{\text{r}}\underbracket{000105}_{\text{i}}\underbracket{000101}_{\text{e}}\underbracket{000110}_{\text{n}} $$

Pour éviter tout soucis avec des algorithmes commençant par le caractère Unicode de nombre 0 (un même nombre peut avoir autant de chiffre 0 qu'il veut au début), on fait commencer tout algorithme par le chiffre 1. L'algorithme d'une seule instruction "Ne fait rien" correspond ainsi au nombre :

$$ 1000078000101000032000102000097000105000116000032000114000105000101000110 $$

On associe bien à toute chaîne de caractères $(c_i)_{0\leq i < n}$ un nombre de $6n +1$ chiffres unique.

On déduit immédiatement la proposition suivante :

Proposition

Il y a exactement autant d'algorithmes différents que de nombres entiers.

preuve

Comme à chaque algorithme est associé un entier strictement positif unique, on peut les ranger par nombre croissant et considérer la suite d'algorithmes $(A_k)_{k \geq 1}$ telle que :

  • $A_1$ est l'algorithme de plus petit nombre associé
  • pour $k > 1$, $A_k$ est l'algorithme est dont le nombre associé est le plus petit qui est plus grand que le nombre associé à $A_{k-1}$

On a alors :

  • $A_k$ existe pour entier $k$ (puisqu'il y a une infinité d'algorithmes différents, donc de descriptions différentes)
  • pour tout algorithme $A$, il existe $k$ telle que $A=A_k$

Ce qui implique que la fonction qui associe à tout algorithme sa position dans la suite $(A_k)_{k \geq 1}$ est une bijection entre l'ensemble des algorithme et l'ensemble des entier strictement positifs.

La preuve ci-dessus est classique. Lorsqu'il y a un nombre infini de choses dénombrable, il y en a autant que d'entiers. C'est pourquoi il y a autant d'entiers pair que d'entiers impair que de multiples de 42.

Nombres réels sans algorithme

Savoir qu'il n'y a pas plus d'algorithmes que de nombres entiers est une très information très importante car elle montre qu'un algorithme ne peut pas tout faire. En effet :

Théorème

Il existe strictement plus de nombres réels dans l'intervalle $[0, 1]$ que de nombres entiers strictement positifs.

preuve

On doit cette preuve magnifique au mathématicien allemand Georg Cantor. Elle est basée sur l'argument s'appelant diagonale de Cantor.

On commence en remarquant que l'on peut associer à tout entier $i$ formé des chiffres $c_1\dots c_k$ le réel de représentation décimal $0.c_1\dots c_k$, ce qui démontre qu'il y a au moins autant de réels dans $[0, 1]$ que de nombres entiers.

On suppose ensuite qu'il existe une injection $f: [0, 1] \rightarrow \mathbb{N}$ entre les réels de l'intervalle $[0, 1]$ et les entiers. On peut alors classer tous les réels selon leurs valeurs selon $f$ :

  • on appelle $r_1$ le 1er réel, c'est à dire celui tel que $f(r_1) \leq f(x)$, quelque soit $x \in [0, 1]$
  • on appelle $r_2$ le second réel $r_2$ , c'est à dire celui tel que $f(r_2) \leq f(x)$ pour tout $x \in [0, 1] \backslash \{ r_1 \}$
  • ...
  • on appelle $r_i$ le $i$ème réel : $f(r_i) \leq f(x)$ pour tout $x \in [0, 1] \backslash \{ r_1, \dots, r_{i-1} \}$
  • ...

Chaque réel pouvant s'écrire sous sa représentation décimale (par exemple $0.1034842$), on construit le nombre réel $r$ de $[0, 1]$ tel que sont $i$ème chiffre après la virgule soit :

  • $1$ si le $i$ème chiffre après la virgule de $r_i$ est différent de $1$
  • $2$ si le $i$ème chiffre après la virgule de $r_i$ est $1$

Le nombre $r$ est bien dans $[0, 1]$ mais il ne peut pas être $r_i$ quelque soit $i$ ! Il y a une contradiction (comme notre nombre ne finit ni par 9 ni par 0 il a un unique développement décimal, il apparaît forcément dans notre liste). Notre hypothèse était donc fausse, il ne peut exister d'injection entre les réels de l'intervalle $[0, 1]$ et les entiers.

Il y a donc strictement plus de réels dans $[0, 1]$ que d'entiers.

Le fait qu'il y ait des infinis plus ou moins gros est un résultat que l'on doit à Cantor et qui est très profond. On note communément $\aleph_0$ le nombre d'entiers qui est strictement plus petit que le nombre de réels, noté $\aleph_1$. Une question reste encore en suspend, mais on a pour l'instant toujours pas la réponse, c'est : y a-t-il un infini entre $\aleph_0$ et $\aleph_1$ ? On ne sais pas, mais on pense que non. C'est l'hypothèse du continu.

Pour une introduction en douceur sur ces sujets, consulter cette émission d'Arte, très bien faite.

On déduit du théorème précédent que :

Il existe des réels pour lesquels il n'existe aucun algorithme $A(i)$ qui calcule la $i$ème décimale de $i$ quelque soit $i$

Trouver de tels nombres est compliqué, car pour y penser il faut le décrire et donc en proposer un algorithme... Mais, ils existent.

Objets manipulables par un algorithme

Le terme fini de la définition d'un algorithme est crucial : pour qu'un humain comprenne, et surtout puisse agir, il ne faut pas qu'il y ait un nombre infini de choses à regarder (chaque chose à faire prend un temps de réflexion non nul, une instruction contenant un nombre infini n'est humainement pas réalisable).

On en déduit la définition (très générale) d'une instruction d'un algorithme :

Une instruction d'un algorithme est une règle définie par un nombre fini de symboles.

Fini ne veut pas dire petit nombre. Un algorithme peut utiliser des nombres entiers relatifs aussi grand ou petit qu'il le veut, du moment qu'ils ne soient pas infinis.

Puisque l'on a le droit de ne manipuler que des choses finies, un algorithme ne peut manipuler que des mots d'un alphabet fini. La conséquence fondamentale de ceci est que :

un algorithme ne peut pas manipuler de nombres réels

On ne peut considérer un réel que comme une abstraction (un symbole particulier) ou une approximation (ne considérer qu'un nombre fini de ses décimales).

Prenons $\pi$ par exemple. Il existe des algorithmes qui calculent les décimales de pi, mais on ne pourra jamais écrire que le nombre $\pi$ est le résultat d'un algorithme, puisque l'algorithme doit s'arrêter : on aura qu'un nombre fini de décimales, pas le nombre $\pi$.

On ne pourra considérer $\pi$ que de deux manières :

Ce n'est pas bien grave en général puisque les lois physiques sont presque tout le temps stables (de petits effets impliquent de petites causes) : considérer les réels en notation scientifique en se fixant une précision ne gène pas les calculs physiques.

Faites tout de même attention car parfois, c'est problématique. Pour le calcul d'effets chaotiques comme la météo où de petits effets produisent de grandes causes, certes, mais aussi lorsque l'on prend l'inverse de choses très petites qui du coup deviennent très grandes. Ce sont des problèmes dit de stabilité numérique.

Donc :

Les objets manipulables par un programme sont uniquement les suites finies composés des objets de type :

  • les entiers relatifs
  • les approximations finies de réels
  • les chaînes de caractères

Ces objets sont tous représentables par des suites finies de 0 et de 1 :

On peu aller plus loin en représentant les tableaux de suites finies de "0" et de "1" par une unique suite finie de "0" et de "1". Pour cela on peut utiliser l'encodage suivant :

Ainsi le tableau [00110, 110] sera encodé par la suite 010100100101101100000101101100001. Notez que cet encodage permet d'encoder tout aussi aisément les listes imbriquées de suites finies de 0 et de 1, comme [0, [1, [1]], 0], chaque caractère nécessaire (0, 1, ,, [ et ]) ayant son propre code sur 3 bits.

En conclusion, comme on peut associer une suite finie de de 0 et de 1 à tout algorithme et à tout ce qu'il peut manipuler :

Proposition

Tout ce que peut manipuler un programme est une suite finie de caractères 0 et 1.

Définition

Un caractère (0 ou 1) est appelé bit.

Un bit est l'information minimale que l'on peut véhiculer puisqu'il ne peut avoir que 2 valeurs différentes. Cette unité minimale d'information est très puissante puisque les suites finies de bits permettent non seulement de stocker tous les objets que peut manipuler un algorithme mais aussi les algorithmes eux-même via le codage binaires des chaines Unicode par exemple. On en conclut que :

À retenir

Un algorithme et tout ce qu'il peut manipuler est une suite finie de 0 et de 1.

Algorithmes et démonstration mathématiques

On n'en parlera pas trop dans ce cours (à moins que vous me le demandiez très fort) mais, en gros, les mathématiques sont une partie de l'informatique (certains diraient même, et réciproquement. Des mathématiciens certainement...).

De façon plus précise on a la suite d'équivalences :

  1. faire une démonstration consiste — à partir d'une série finie d'axiomes — à effectuer une suite finie de déductions pour parvenir à un résultat. (Aristote, en -350 environ)
  2. (1) est équivalent à démontrer à l'aide d'une suite finie de déductions qu'une proposition logique est vraie (Hilbert, début XXe siècle)
  3. (en passant, Gödel, en 1931, démontre qu'il existe des propositions logiques qui sont vraies mais qu'il est impossible de démontrer)
  4. Curry puis Howard qui généralise, en 1950 et 1980, montrent que (2) est équivalent à écrire en terme de $\lambda$-calcul
  5. Turing démontre en 1937, que (4) est équivalent à écrire une machine de Turing.
  6. (en passant, Turing démontre qu'il existe des machines de Turing qui ne s'arrêtent jamais et que savoir si une machine de Turing va s'arrêter est indécidable, ce qui est équivalent à (3))