Définitions 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.

On va montrer quelques propriétés générales d'un programme et d'un algorithme.

Algorithme ?

Qu'est-ce que ça veut dire ? Cherchons dans le Petit Robert :

• algorithme : ensemble des règles opératoires propres à un calcul
• calcul : enchaînement des instructions nécessaires à l'accomplissement d'une tâche
• tâche : ...

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. lire la définition puis, pour chaque mot non compris dans la définition, chercher ce mot dans le Petit Robert

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

• compréhensible
• chaque instruction (lire une définition, comprendre un mot, ...) peut être caractérisée par un petit texte en français
• notre algorithme est récursif (il s'appelle lui-même) mais s'arrête bien à un moment (au pire une fois que l'on a passé en revue et compris tous les mots du dictionnaire)

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

• des paramètres en entrée mais au plus une sortie (qui peut être une structure composée comme une liste par exemple).
• le retour d'un algorithme est la dernière instruction qu'il fait, en rendant la sortie (ici, il ne rend rien)
• une description de ce qu'il fait
• l'exécution d'un algorithme est signifiée par son nom suivi de parenthèses contenant ses paramètres
• afficher à l'écran n'est PAS un retour de fonction/méthode/algorithme : l'algorithme continue de fonctionner après l'affichage

On peut en déduire la définition suivante : Un programme est une succession d'instructions simples et clairement définies. Ou, de façon équivalente :

Un algorithme est un programme qui s'arrête à coup sûr :

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

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 "J'ai trouvé ton entier dans la liste ! Je suis trop trop fort !" à l'écran.

Pour transformer cette description en programme/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ée 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 "J'ai trouvé ton entier dans la liste ! Je suis trop trop fort !".

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 "J'ai trouvé ton entier dans la liste ! Je suis trop trop fort !".
    Sinon rendre "L'entier n'est pas dans la liste".

Notre programme s'arrête tout le temps : c'est un algorithme.

On peut le rendre un peu plus professionnel en ne rendant pas une chaîne de caractères mais un booléen (Vrai s'il est dans la liste et Faux sinon) :

Nom : recherche
Entrées :
    t : un tableau d'entiers
    x : un entier
Sortie :
    un booléen
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`.

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 cours du temps.

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

algorithme recherche(T: []int, x: int) → bool:
    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.

Objets manipulables par un programme

Le terme fini de la définition d'un programme/algorithme est crucial : pour qu'un humain comprenne, et surtout puisse agir, il faut que :

• chaque algorithme soit décrit par un texte fini
• chaque instruction doit s'exécuter en un temps fini
• chaque donnée manipulée doit être de taille finie

Donc la description du programme ainsi que les données doivent être décrites avec un "langage" formé avec des mots d'un alphabet fini.

Par exemple le programme suivant qui énumère tous les entiers :

Nom : énumère
Programme :
    x = 0
    répéter le bloc de deux instructions suivant :
        écrire x en base 10 sur une feuille de papier
        x = x + 1

Même si le programme ne s'arrête pas, chaque étape est bien finie :

• x est toujours un entier que l'on peut décrire comme des mots de l'alphabet $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$
• écrire un nombre sur une feuille de papier est toujours possible et prendra un temps proportionnel au nombre de ses chiffres à écrire.
• ajouter 1 à x est possible en posant l'addition et cela prendra un temps proportionnel à son nombre de chiffres et l'on peut décrire le principe de l'addition en français, donc avec un nombre fini de symboles (les lettres, les chiffres et quelques symboles de ponctuation)

La conséquence fondamentale de ceci est que :

Une conséquence directe de la proposition précédente est qu'un programme ne peut pas manipuler de nombres réels.

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 n'aura qu'un nombre fini de décimales, pas le nombre $\pi$. On ne pourra le considérer que de deux manières :

• soit comme un symbole et l'utiliser pour faire des opérations sur lui (comme $2 + \pi$, ou $\frac{3\pi}{3}$, ...) de façon formelle, c'est-à-dire sans jamais connaître sa valeur
• soit comme une valeur approchée de lui (3.1415 par exemple) et ainsi rendre des valeurs approchées des différentes opérations.

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

Or :

La proposition précédente montre que l'on peut représenter toute suite finie d'éléments d'un ensemble fini par une suite finie de 0 et de 1 de façon unique. On en déduit le résultat que tout le monde connaît :

Cependant n'utiliser que des suites finies de bits pour nos programmes les rendrait illisibles. On définit donc d'autres types qui représentent nos données. Une suite finie de bits pourra alors être interprétée selon les cas comme :

• un entier relatif :
  • positif en utilisant leur notation binaire et en les faisant commencer par un 0, par exemple 3 sera encodé par 011 (le 0 tout à gauche signifiant que l'entier est positif)
  • négatif en utilisant le complément à deux de la représentation binaire de son opposé. Ainsi -3 sera encodé par 101 (un entier négatif ainsi représenté commencera toujours par un 1)
• une approximation finie d'un réel en utilisant la norme IEEE 754. Par exemple 3.1415 en codage IEEE 754 sur 32 bits correspond à l'entier binaire : 01000000010010010000111001010110 (j'ai utilisé un convertisseur)
• une chaîne de caractères en utilisant le code utf-8. Par exemple "Yop !" correspond au nombre hexadécimal 0x596F702021 (là aussi, j'ai utilisé un convertisseur) qui en binaire vaut : 0000010110010110111101110000001000000010
• la vérité ou la fausseté
• ...

On pourrait se poser la question de pourquoi utiliser des bits alors que :

Le second symbole n'est pas là pour coder la donnée mais pour la terminer ! Si l'on n'avait qu'un seul symbole, comment savoir lorsque la séquence est finie ? Il faut explicitement déterminer la fin de ce qu'on écrit.

Au final :

Nombres de paramètres d'entrée d'un programme

On vient de voir que tous les objets manipulables par des programmes peuvent être assimilés à des suites finies de 0 et de 1, bref à des entiers représentés en base 2. On peut 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.

Cette proposition montre que l'on peut toujours représenter un algorithme à $p > 1$ paramètres dans $\{0, 1\}^\star$ en un algorithme avec $p-1$ paramètres dans $\{0, 1\}^\star$ en fusionnant les deux premiers paramètres (en utilisant l'injection définie dans la proposition précédente). On pourra ensuite retrouver ces deux paramètres en utilisant la procédure inverse au début de l'algorithme.

De là, tout programme peut être écrit avec un unique paramètre dans $\{0, 1\}^\star$, quitte à retrouver les paramètres initiaux en utilisant la réciproque de notre procédure de compactage des paramètres. Comme les suites finies de 0 et de 1 sont des entiers écrits en base 2, on obtient le résultat fondamental :

Terminons avec un petit exercice pour voir si vous avez compris :

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

De la définition d'un algorithme on peut donc déjà conclure que :

Ne fait rien
rend 1

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, puis rendent 1.

On peut cependant aussi démontrer que :

Rend l'entier k

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 l'alphabet Unicode. De là :

Bref, les programmes correspondent à un sous-ensemble de l'ensemble des chaînes de caractères écrites en Unicode. On peut alors utiliser la proposition sur les suites binaires pour avoir la proposition suivante :

On déduit immédiatement la proposition suivante :

La preuve ci-dessus est classique et est basée sur le fait que deux ensembles sont de même cardinal s'il existe une bijection entre les deux. Cette définition est évidente lorsque les ensembles sont finis et elle s'étend lorsque les ensembles sont infinis :

Il faut faire un peu attention avec les infinis, par exemple les deux fonctions suivantes sont des injections :

• $f(n) = 2n$ pour tout entier positif $n$,
• $g(n) = 2n+1$ pour tout entier positif $n$.

Ceci montre que :

• il n'y a pas plus d'entiers que d'entiers pairs,
• il n'y a pas plus d'entiers que d'entiers impairs.

On peut alors utiliser le théorème suivant pour en conclure qu'il y a autant d'entiers que d'entiers pairs et que d'entiers impairs !

Dont on déduit le célèbre théorème :

Jouer avec l'infini est à la fois rigolo et donne le vertige. De nombreux résultats sont contre-intuitifs comme le résultat précédent qui montre qu'il peut y avoir autant d'éléments dans un ensemble et une partie de celui-ci. Par exemple nos injections précédentes montrent qu'il y a autant d'entiers pairs que d'entiers impairs que d'entiers !

À vous, pour voir si vous avez compris :

Enfin, ce théorème permet de démontrer que :

D'un point de vue informatique, on conclut de cette partie que tout ce qu'on manipule en informatique sont des suites finies de 0 et de 1, que ce soit les données ou les programmes eux-mêmes :

Algorithmes et démonstrations mathématiques

On n'en parlera pas trop dans ce cours (cela a plus sa place dans un cours de logique ou de calculabilité) mais, en gros, les mathématiques sont une partie de l'informatique (certains, des mathématiciens certainement, diraient même, et réciproquement...).

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 termes 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))