Algorithmes et algorithmique

L'algorithmique est le domaine des sciences qui étudie les règles et les techniques impliquées dans la conception et l'analyse des algorithmes. On peut résumer l'algorithmique a un unique objectif :

La conception d'un algorithme n'est donc qu'une partie de l'objectif à atteindre, il faut également s'assurer que l'algorithme est efficace, ce qui se traduit dans ce contexte par une économie des ressources en temps et en espace. Les deux aspects sont abordés dans la phase de conception et la phase d'analyse qui ne sont pas étanches, elles constituent le fil rouge de ce cours.

Il faut prendre garde à ne pas confondre un algorithme avec un programme informatique au sens des langages de programmation. Pour faire une mé­ta­phore, l'algorithme est au programme ce que le plan de construction est à l'ouvrage. Le programme informatique est donc la réalisation effective sur machine et comporte des pro­blé­ma­ti­ques propres et spécifiques au langage employé (pour filer la mé­ta­pho­re : topographie, matériaux, engins et outils disponibles pour la construction, etc.).

Revenons à la première définition d'un algorithme. Même si elle résume de manière tout à fait sa­tis­fai­san­te le concept, elle est inutilisable en l'état pour en faire le socle d'une théorie. Le problème est identique à celui qu'a rencontré le mathématicien G. Cantor quand il a voulu définir for­mel­lement le concept universel d'ensemble et édicter des règles pour les construire. Sa définition et le principe d'abstraction (tout prédicat engendre un ensemble constitué des éléments qui le satisfont) abou­tis­saient im­man­qua­ble­ment à des paradoxes, et il a fallu attendre les travaux de Zermello et Fraenkel en théorie des ensemble (résumée en théorie zf) pour comprendre qu'il était nécessaire d'établir des règles strictes pour construire de nouveaux ensembles à partir du germe que constitue l'ensemble des entiers naturels \(\mathbf N\). Les travaux ultérieurs du mathématicien K. Gödel ont alors permis de cerner les limites de toute théorie mathématique.

Les recherches effectuées par les mathématiciens pour formaliser la notion de calcul ou d'algorithme, et ceci bien avant que le mot ordinateur n'existe, ont été aussi prolifiques et précieuses que celles qui ont abouti à la théorie axiomatique des ensembles zf utilisée de nos jours. Il existe d'ailleurs de multiples intersections entre ces deux théories. De nombreux modèles mathématiques ont été pro­po­sés pour cadrer au plus juste ce concept et on sait aujourd'hui que tous les formalismes qui reprennent de façon parfois fort différente les propriétés caractéristiques d'un algorithme (finitude des opérations, déterminisme du processus, finitude des règles, etc.) sont tous équivalents. Au­tre­ment dit, ce que l'on est capable de résoudre comme problèmes, ou ce que l'on est en mesure de calculer, ne dépend pas du modèle algorithmique choisi, du moment que ce modèle respecte les propriétés universellement reconnues comme caractéristiques d'un algorithme. C'est ce que con­jec­tu­rait le logicien américain Alonzo Church, inventeur du \(\lambda\)-calcul, avant même que l'on ne prouve formellement l'équivalence des modèles abstraits en lice.

Un algorithme est donc un modèle de calcul abstrait. Par analogie avec les modèles concrets, l'ex­pres­sion de ces calculs est souvent qualifiée de programme et elle est intimement liée au modèle mathématique considéré. Dans ce contexte abstrait, algorithme et programme sont donc quasi sy­no­ny­mes. Le mode opératoire d'un algorithme reste largement indépendant du modèle considéré. Un algorithme traite des données qui constituent son entrée pour calculer d'autres quantités qui sont interprétées comme un résultat et constituent sa sortie.

Une première approche imagée est de considérer un algorithme comme une machine mécanique qui traite une matière première pour la transformer en produit fini. La description du fonctionnement rudimentaire d'un hachoir à viande devrait suffir à comprendre l'hypotypose.

matière \(\Downarrow\) première
	\(\Rightarrow\) produit fini

La viande en morceau est fournie en entrée dans l'entonnoir et la rotation de la manivelle l'entraîne vers le disque couteau à l'aide d'une vis sans fin. La machine renvoie en sortie la viande hachée.

Une deuxième approche plus formelle est la vision fonctionnelle. L'écriture schématique \(x\stackrel{f}{\longmapsto}y\) d'une fonction mathématique \(f\) induit une dynamique plus proche de celle du fonctionnement d'un algorithme que de la définition d'une fonction. L'idée suggérée par cette écriture en la lisant de gauche à droite est qu'un objet \(x\) est transformé en un objet \(y\) par l'entremise de la fonction \(f\), la tran­sfor­ma­tion étant souvent décrite à l'aide d'une expression algébrique, comme par exemple \(x\mapsto x^2 -3x + 1\). Une autre écriture classique précise la nature des objets \(x\) et \(y\) en spécifiant l'ensemble de départ et l'ensemble d'arrivée : \begin{equation} f:\begin{matrix} E\rightarrow F\\ {\color{yellow}x}\mapsto \color{#BBF}y \end{matrix} \end{equation} On peut résumer l'articulation entre un algorithme et ses entrées/sorties par un schéma qui s'en inspire fortement : \(x\) est assimilé à l'entrée de l'algorithme, \(y\) à la sortie, les ensembles de départ et d'arrivée précisent le type des données, et la fonction \(f\) joue le rôle de l'algorithme  :

Nous allons affiner ce premier schéma. L'entrée comme la sortie sont modélisées respectivement par deux mots définis sur un alphabet d'entrée \(\Sigma\) et un alphabet de sortie \(\Gamma\) (l'ensemble des mots sur un alphabet \(A\) est noté \(A^*\)). L'entrée du programme est obtenue via un schéma d'encodage qui désigne de manière un peu pompeuse une façon de traduire les données réelles et bien concrètes de notre monde en objets abstraits qui pourront être manipulés par des outils d'une théorie mathé­mati­que, comme par exemple un triplet de trois octets \(({\color{#F00}R},{\color{#0F0}V},{\color{#00F}B})\in[0,255]^3\) peut représenter une couleur sur un écran. C'est ce que j'ai fait ici même avec les codes hexadécimaux \(\verb+F00+\), \(\verb+0F0+\) et \(\verb+00F+\) res­pec­ti­ve­ment pour distinguer ces trois couleurs dans le texte. Symétriquement, la sortie du programme est elle même interprétée à l'aide d'un schéma de décodage. Notons pour finir que l'ensemble des paramètres particuliers d'un problème, et par conséquent le mot de \(\Sigma^*\) qui en résulte via le schéma d'encodage, est qualifié d'instance du problème. La taille d'une instance \(x\in\Sigma^*\), et par extension la taille de la donnée, est la longueur du mot u, c'est-à-dire le nombre de ses symboles. La figure ci-dessous résume tout ceci :

Un premier problème

À titre d'illustration, étudions un premier problème. On veut déterminer si un mot est un pa­lin­dro­me, c'est-à-dire un mot qui s'écrit exactement de la même façon à l'endroit et à l'envers. Le mot sévir qui s'écrit rivés à l'envers n'est pas un palindrome (mais un anacyclique car dans les deux sens le mot a un sens !) alors que le mot radar en est un. Le problème se généralise souvent à des phrases entières en ne tenant compte que des lettres et en omettant les espaces et autres symboles. Par exemple la phrase suivante

Trouver une méthode pour résoudre un problème est une première victoire, mais il reste quelques étapes à franchir avant d'être en mesure d'en tirer un programme informatique efficace. La méthode décrite dans la phrase comparer les lettres du mot avec celles de ce même mot mais écrit à l'envers est imprécise, incomplète et ambiguë. Elle est suffisante pour un être humain car il est capable de

• définir les termes employés : qu'est ce qu'une lettre, qu'est ce qu'un mot, qu'est ce que comparer signifie ?
• compléter les informations manquantes : compare-t-on les lettres de gauche à droite ? de droite à gauche ? autrement ?
• lever les ambiguités grâce au contexte : que signifie à l'envers ? une rotation de 180° de chaque lettre du mot ? du mot tout entier ? écrire le mot de droite à gauche ?

L'analyse du problème permet de déterminer le cadre théorique adéquat pour sa résolution et ainsi de choisir les modèles de données les mieux adaptés pour y parvenir. On parle parfois d'algèbre de conception. Ce sont les structures algébriques utilisées en mathématiques qui sont les outils privilégiés pour représenter les objets à manipuler. Nous verrons que les modèles de données informatiques sont majoritairement des structures algébriques bien connues ou des déclinaisons plus ou moins fidèles. Ces modèles de données sont à leur tour déclinés en structures de données dans les langages de programmation.

Dans le cadre de la résolution du problème du palindrome, la théorie des langages, tout au moins une part homéopathique, s'avère adaptée à sa description formelle. On se donne \(A=\{a_0,a_1,\ldots,a_{q-1}\}\) un ensemble fini appelé alphabet constitué des lettres ou symboles \(a_i\). Toute suite finie (on dit aussi séquence) \(u\) de \(n\) lettres de \(A\) est appelée mot de longueur \(n\), longueur que l'on désigne par \(|u|\) ou \(\#u\). On note \(A^n\) l'ensemble (fini) de tous les mots de longueur \(n\) et \(A^*\) l'ensemble (infini) de tous les mots possibles. Notons que par analogie avec les langues naturelles et par soucis d'économie, on écrit les termes de la séquence sans les séparer par des virgules contrairement à l'usage général pour les suites. Le miroir d'un mot \(u=u_1u_2\ldots u_n\) est le mot \(u_nu_{n-1}\ldots u_1\). Un langage est un sous-ensemble de \(A^*\). Par exemple, la langue française est un langage (fini), c'est un sous-ensemble strict de tous les mots que l'on peut constituer avec les symboles de l'alphabet latin \(A=\{a,b,c,\ldots,z\}\), le mot algorithme est un mot de la langue française contrairement au mot albeaurythme.

Un mot de la langue française est donc modélisé par une séquence \(u=u_1u_2\ldots u_n\). Ce passage du réel à l'abstrait et le choix que nous avons fait pour représenter un mot de la langue française constitue précisément un schéma d'encodage. À présent, savoir si un mot codé \(u=u_1u_2\ldots,u_n\) est ou non un palindrome se traduit par la question \begin{equation}\label{eq:egseq} %\stackrel{?}{=} ou \overset{?}{=} u_1u_2\ldots u_n \stackrel{?}{=} u_nu_{n-1}\ldots u_1 \end{equation}

Ce lemme permet de valider cette approche et l'assertion (\ref{eq:egseq2}) suggère un procédé itératif pour s'assurer que l'égalité (\ref{eq:egseq}) est satisfaite ou non. Si l'on note \(v\) le miroir de \(u\), il suffit de vérifier que \(u_i=v_i\) successivement pour tous les indices \(i\) variant de \(1\) à \(n\). Si à une étape donnée \(u_i\not=v_i\) avec \(i\leq n\), il est inutile d'aller plus loin, en revanche si toutes les égalités ont pu être vérifiées, on peut affirmer que \(u\) est un palindrome. On peut résumer tout ceci par un algorithme qui procède en deux phases, la première construit le mot miroir \(v\) (lignes #1 à #2b), la seconde com­pa­re \(u\) et \(v\) (lignes #3 à #5) :

Il est manifeste que le nombre d'instructions exécutées pour décider si un mot \(u\) est un palindrome ou non, dépend de la longueur \(n\) du mot \(u\) mais aussi de la nature du mot, sans même définir précisément ce que l'on entend par instruction. En effet, comme nous l'avons déjà noté, il est inutile dans la deuxième phase de continuer les comparaisons si deux symboles \(u_i\) et \(v_i\) sont distincts, ce qui peut survenir bien avant d'atteindre la fin du mot. Nous allons dans ce chapitre et en première approximation considérer que chaque ligne de cet algorithme définit une instruction, notion qui sera formalisée au chapitre suivant. Les instructions #1, 3 et 5 ne sont exécutées qu'une seule fois. Les instructions #2a et 2b le sont \(n\) fois chacune. L'instruction #2 est exécutée \(n+1\) fois. Pour un mot \(u\) donné, notons \(p(u)\in[1,n+1]\) la plus petite valeur de \(i\) telle que la condition \(i\leq n\) et \(u_i=v_i\) n'est plus satisfaite, soit : \begin{equation*} p(u) := \min\{i\in[1,n+1]\ \ |\ \ i>n\ \text{ou}\ u_i\not=v_i\}. \end{equation*} Alors l'instruction #4 est exécutée \(p(u)\) fois et l'instruction #4a exactement \(p(u)-1\) fois. Fi­na­le­ment en sommant, on en dénombre \begin{equation} 3+2n+(n+1)+p(u)+(p(u)-1)=3n+2p(u)+3. \end{equation} Le nombre d'instructions exécutées est minimal quand les deux premiers symboles sont distincts, i.e. \(u_1\not=v_1\), soit \(3n+5\) instructions si \(p(u)=1\). Le maximum est atteint quand \(u=v\), soit \(5n+5\) si \(p(u)=n+1\).

Le lecteur avisé aura deviné qu'il est possible d'être plus économe pour décider si un mot \(u\) est un palindrome ou non avant même que l'exercice précédent ne suggère de modifier la fin de la boucle. On peut faire encore mieux en évitant tout simplement de construire préalablement le mot \(v\)  et en comparant directement les symboles de \(u\) entre eux :

Il y a cette fois \(2\lfloor\frac{n}{2}\rfloor +3\) instructions exécutées dans le pire des cas et \(3\) dans le meilleur des cas ce qui est bien meilleur qu'avec notre premier algorithme.

Cette étude nous a permis de mettre en évidence les 4 grandes étapes à franchir pour passer d'un problème à sa résolution à l'aide d'un algorithme :

1. analyse et modélisation du problème ;
2. conception de l'algorithme ;
3. preuve de la validité de l'algorithme ;
4. analyse des performances de l'algorithme.

Programmation

L'écriture d'un programme informatique dans un langage particulier pour la résolution effective d'un problème constitue une 5ème étape qui recèle elle aussi des difficultés, de nature et de magnitude différentes selon le langage utilisé. Il faut en premier lieu trouver les structures correspondant aux modèles utilisés ou les construire quand elles n'existent pas. Par exemple la gestion des chaînes de caractères et des listes en Python est simple et agréable et particulièrement délicate et fastidieuse en langage C (avec d'autres atouts en contrepartie).

Adaptons les deux algorithmes en langage Python et observons à travers cet exemple quelques un des écueils inhérents à la programmation  :

def Est-Palindrome1(u):
    n = len(u)
    v = []
    i = 0
    while (i < n):
        v = u[i] + v
        i = i + 1
    i = 0
    while (i < n) and (u[i] == v[i]):
        i = i + 1
    return (i >= n)     


def Est-Palindrome2(u):
    i = 0
    n = len(u)
    while (i < n//2) and (u[i] == u[n - i]):
        i = i + 1
    return (i >= n//2)     

Mais revenons à notre problème. La première difficulté est que la structure de chaîne de caractères commence son indexation à 0 et non à 1 comme nous l'avons fait dans l'algorithme. L'impact n'est pas anodin, le résultat de l'exercice 1 qui nous a permis de prouver que l'algorithme était juste suppose que l'indice \(i\) appartient à l'intervalle \([1,n]\) et non \([0,n-1]\). L'adaptation sans analyse mathématique préalable peut s'avérer périlleuse et occasionne une perte de temps considérable en développement. Ici les inégalités larges des tests initiaux ont été remplacées par des inégalités strictes. Le double \(//\) désigne le quotient de la division euclidienne, il s'agit donc bien de la partie entière de \(\frac{n}{2}\).

Un danger plutôt pervers se cache dans la condition \((i < n)\ \text{and}\ (u[i] == v[i])\) de la boucle while de la première fonction. L'écriture de cette condition est parfaitement naturelle puisqu'elle ne fait que transposer ce que nous ferions à la main, à savoir tant que l'on n'a pas atteint la fin du mot et que les lettres sont identiques, on avance. Mais comment un programme informatique opère-t-il pour évaluer une expression ? Une première phase consiste à faire une analyse lexicale et à segmenter la chaîne de caractères en unités lexicales (tokens), constantes, opérateurs, identificateurs, etc. (Ces notions seront étudiées en détail dans le cours de théorie des langages et compilation en troisième année). Les unités lexicales sont ensuite rangées dans un arbre syntaxique :

Chaque opérateur est rangé dans un nœud de cet arbre binaire dont les fils sont les opérandes, le nombre de fils correpondant à l'arité de l'opérateur. Ici nous sommes en présence d'opé­ra­teurs binaires (\( < \) ou \( == \) par exemple) et unaire (\([\ ]\)). Le procédé est éminemment récursif, si un opérande est lui même une expression, son nœud est la racine du sous-arbre qui la représente. Cet arbre est ensuite évalué récursivement, chaque nœud est alors remplacé par le résultat de l'opération.

On voit poindre le problème potentiel. En soi, l'expression logique \((i < n)\wedge (u_i=v_i)\) n'a aucune dimension temporelle et on pourrait permuter les deux opérandes de la conjonction, soit l'expression \((u_i=v_i) \wedge (i < n)\), sans que cela change quoi que ce soit à sa valeur logique. Néanmoins, nous lisons de la gauche vers la droite et nous savons que la valeur de vérité d'une expression de la forme \(P_1\wedge P_2\wedge\cdots\wedge P_n\) est fausse dès qu'un \(P_i\) est faux sans qu'il soit nécessaire d'évaluer les \(P_k\) pour \(k>i\). A priori, rien n'indique comment l'arbre syntaxique va être évalué, il est même envisageable qu'il soit évalué dans son intégralité ce qui invaliderait l'algorithme puisqu'une fois que l'indice \(i\) atteint la valeur \(n\) la quantité \(u[i]\) n'est plus définie. Fort heureusement, les compilateurs et interprètes modernes évaluent les expressions comme nous imaginons qu'ils doivent le faire, mais il est préférable d'écrire des programmes robustes. On peut avantageusement réécrire la fonction #1 de la manière suivante :

def Est-Palindrome-Bis(u):
    n = len(u)
    v = []
    i = 0
    while (i < n):
        v = u[i] + v
        i = i + 1
    i = 0
    oncontinue = True;
    while (i < n) and oncontinue:
        oncontinue = (u|i] == v[i])
        i = i + 1
    return (i >= n)     

def Est-Palindrome-Ter(u):
    return u == u[::-1]