Définitionsd'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 ?

• 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 et l'
    4. pour chaque mot non compris dans la définition :
       4.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 :

• 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 s'arrête bien à un moment (au pire une fois que l'on a passé en revue 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é par son nom suivie 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

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

• finitude : Un algorithme doit toujours se terminer après un nombre fini d’étapes.
• définition précise : Chaque étape d'un algorithme doit être définie précisément, les actions à transposer doivent être spécifiées rigoureusement et sans ambiguïté pour chaque cas.
• entrées : […] des quantités qui lui sont données avant qu'un algorithme ne commence. Ces entrées sont prises dans un ensemble d'objets spécifié.
• sortie : […] des quantités ayant une relation spécifiée avec les entrées.
• rendement : […] toutes les opérations que l'algorithme doit accomplir doivent être suffisamment basiques pour pouvoir être en principe réalisées dans une durée finie par un homme utilisant un papier et un crayon.

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 :

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 peut plus professionnel en ne rendant pas une chaîne de caractère 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 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 := entier) 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écri 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écrite 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 aux 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 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 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.

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 tableaux de bits (dont le type est [bit]) pour nos programmes les rendrait illisible. On défini donc d'autres types qui représentent nos données. Un tableau de bits pourra alors être interprété 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

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é à des suites finies de 0 et de 1, bref à des entiers représenté 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 est vraiment importante Car elle 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 et en les retrouvant en utilisant la procédure inverse au d´´but de l'algorithme !

Ceci montre que tout programme peut être écrit avec un unique paramètre dans $\{0, 1\}^\star$, quite à retrouver les paramètres initiaux en utilisant . Comme les suites finies de 0 et de 1 sont des entiers écrit en base 2, on obtient le résultat fondamental :

Arrêtez vous un instant sur les conséquences de ce que l'on vient de démontrer : on vient de montrer qu'il y a moins d'élément dans $\mathbb{Q}$ (l'ensemble des fractions entière qui est égal à la division de deux entiers et donc en bijection avec $\mathbb{N} \times \mathbb{N}$ lui même en bijection avec à $\{0, 1\}^\star \times \{0, 1\}^\star$) que dans $\mathbb{N}$ (qui est en bijection avec à $\{0, 1\}^\star$). Étonnant, non ?

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.

On se place ici dans le cadre précédent où un programme prend en paramètre un entier et rend un entier.

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

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

Mais, on peut aussi démontrer :

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 cardiaux que s'il existe une bijection entre les deux. Cette définition est évidente lorsque les ensembles sont fini et elle s'étend lorsque les ensemble sont infinis :

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

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

Ceci montre que :

• les entiers sont en bijection avec $f(\mathbb{N})$ c'est à dire les entiers pairs
• les entiers sont en bijection avec $g(\mathbb{N})$ c'est à dire les entiers impair

Bref : il y a autant d'entier que d'entier pair que d'entiers impair !

À vous, pour voir si vous avez compris :

La remarque précédente est un cas particulier d'un théorème plus général que l'on doit à Cantor et Bernstein :

Jouer avec l'infini est à la fois rigolo et donne le vertige. De nombreux résultats sont contre-intuitif comme le résultat précédent qui montre qu'il peut y avoir autant d'élément dans un ensemble et une partie de celui-ci.

On peut grâce au résultat précédent démontrer :

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ême :

Pour finir, un petit résultat très utile que vous pouvez démontrer :

A'(E):
    E', S' = f^{-1}(E)
    S'' = A(E')

    Si S' == S'':
        rendre 1
    sinon:
        rendre 0

Algorithmes et démonstration 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 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))