Algorithmes et algorithmique
Nous utilisons FFFFFFFFFFFFFF des algorithmes en permanence, non seulement en mathématiques et en informatique ou plus généralement dans le domaine des sciences, mais tout simplement dans la vie quotidienne pour réaliser une quantité de tâches incroyablement variées. Nous nous servons d'algorithmes pour nous habiller, préparer du café, calculer nos impôts, vérifier l'état d'un véhicule, etc. Une synthèse des multiples définitions du mot algorithme pourrait être :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étaphore, 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 problématiques propres et spécifiques au langage employé (pour filer la métaphore : 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 satisfaisante 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 formellement 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) aboutissaient immanquablement à 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é proposé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. Autrement 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 conjecturait 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'expression 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 synonymes. 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 transformation é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ématique, 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+\) respectivement 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 :
Langage naturel | Langage abstrait | Modèle de calcul abstrait | Langage abstrait | Langage naturel | ||||
donnée | \(\xrightarrow[]{\text{encodage}}\) | \(x\in\Sigma^*\) | \(\xrightarrow[]{\phantom{\text{entrée}}}\) | algorithme programme | \(\xrightarrow[]{\phantom{\text{sortie}}}\) | \(y\in\Gamma^*\) | \(\xrightarrow[]{\text{décodage}}\) | résultat |
instance | entrée | calcul | sortie | réponse |
Un premier problème
À titre d'illustration, étudions un premier problème. On veut déterminer si un mot est un palindrome, 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
un palindrome (vous pouvez tester vos propres phrases). Ce problème est extrêmement simple à résoudre, il suffit de comparer les lettres du mot avec celles de ce même mot écrit à l'envers. Mais si cette procédure est limpide pour un être humain, il est vraisemblable qu'il faudra encore de sérieuses avancées en informatique avant qu'une machine ne soit en mesure de l'interpréter telle quelle pour décider si un mot est un palindrome ou non.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
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 compare \(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. Finalement 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.
Ici, l'expérience aléatoire consiste à tirer un mot \(u\) de \(A^n\) au hasard, l'espace d'échantillonnage \(\Omega\) est donc le langage \(A^n\). Pour calculer le nombre d'instructions exécutées, on peut se contenter d'étudier la boucle #2 puisque les instructions #1 et #3 ne sont exécutées qu'une seule fois. Pour \(k\in[1,\lfloor\frac{n}{2}\rfloor]\) on définit l'évènement \[\Omega_k:=\{u\in \Omega\ |\ p(u)=k\}\] La probabilité \(\text{Prob}\,[\Omega_k]\) est donc la probabilité que la condition (\(i < j\) et \(u_i=u_j\)) soit testée \(k\) fois. Si \(p(u)=k\) cela signifie que les \(k-1\) premières égalités sont satisfaites et que la \(k\)-ème ne l'est pas, sauf si \(k=\lfloor\frac{n}{2}\rfloor\) auquel cas cela signifie que toutes les égalités ont été satisfaites (et donc que le mot est un palindrome). Justifiez que \begin{equation*} \text{Prob}\,[\Omega_k] = \begin{cases} \text{Prob}\,[u_{k}\not=v_{k}]\times\displaystyle\prod_{i=1}^{k-1} \text{Prob}\,[u_i=v_i]&\text{si}\ k\in[1,\lfloor\frac{n}{2}\rfloor],\\ \displaystyle\prod_{i=1}^{k} \text{Prob}\;[u_i=v_i]&\text{si}\ k=\lfloor\frac{n}{2}\rfloor+1. \end{cases} \end{equation*} Montrez que \begin{equation*} \forall i\in[1,\lfloor\frac{n}{2}\rfloor],\quad \text{Prob}\;[u_i=v_i]=\frac{1}{q}\ \text{et}\ \text{Prob}\;[u_i\not=v_i]=1-\frac{1}{q} \end{equation*} Montrez que les évènements \(\Omega_k\) sont incompatibles (i.e. deux-à-deux disjoints) et forment une partition de \(\Omega\). Chaque mot de \(\Omega_k\) demande \(k\) tests, en déduire que le nombre moyen de fois où l'instruction #2 est exécutée pour traiter un mot de longueur \(n\) est égal à \begin{equation*} \left(\frac{1}{q}\right)^{\lfloor\frac{n}{2}\rfloor+1}+ (q-1){\color{yellow}\underbrace{\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor+1}k\left(\frac{1}{q}\right)^{k}}_{S}}. \end{equation*} Utilisez le formulaire de combinatoire pour calculer la somme \(S\). En notant que l'instruction #2a est exécutée une fois de moins que l'instruction #2, calculez le nombre moyen d'instructions exécutées par l'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 :
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)Mentionnons pour commencer l'extraordinaire maladresse (c'est un point de vue très personnel) commise lors de la conception du langage C, à savoir coder l'affectation à l'aide du symbole mathématique \(=\) dont la signification universelle est l'égalité. Ce choix imposait un codage différent pour l'égalité logique, d'où le bégaiement \(==\). Le concepteur de Python, Guido van Rossum, a jugé bon de reproduire cet impair qui constitue pourtant une source inépuisable d'erreurs. Le langage Pascal (et quelques autres), plus inspiré sur ce point, code l'affectation avec les deux symboles \(:=\) ce qui a l'énorme avantage, en rendant l'écriture asymétrique, de conserver la dynamique temporelle de la lecture de l'opération d'affectation. Cette notation a été adoptée par les mathématiciens pour distinguer une assertion ou un résultat comme \((x+y)^2=x^2+2x+y^2\), d'une définition d'un nouvel objet mathématique comme \(E:=\{a,b\}\) qui permet de baptiser \(E\) la paire \(a,b\). Dans notre pseudo-langage algorithmique nous utiliserons la flèche à gauche \(\leftarrow\).
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érateurs 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]Cette écriture, aussi séduisante soit-elle pour le développeur pressé, a pour gros défaut de cacher le nombre d'opérations exécutées par l'interprète Python pour évaluer cette expression et par conséquent laisser croire au programmeur débutant que ces questions ne sont pas essentielles. Nous y reviendrons dans le chapitre consacré à la complexité.