Introduction à l'algorithmique

En empruntant aux Indiens leur système de numération et d'écriture de position des nombres ce qui facilite grandement les opérations arithmétiques, les Arabes désignèrent le 0 : es-sifr (littéralement, le vide). Le mot fut latinisé en cephirum ; en Italie, il devient zefero puis zéro. L'histoire des mathématiques regorge des inventions arabes : c'est aux Arabes que l'on doit la désignation des inconnues par la lettre x (Xay en espagnol, déformation de chay : la chose). Même si elles sont le fait d'érudits, comme le poète O. Khayyam qui fournit la solution des équations du troisième degré, ces recherches mathématiques ont des finalités pratiques et visent à résoudre des problèmes quotidiens (calcul de surface, aménagement urbain).

La notation symbolique des nombres a été développée au VII^e siècle par un grand astronome indien : Brahmagupta. Abbou Adullah Ibn Moussa dit Al Khorizmi, né en 783, mathématicien ouzbeck de l'Empire des Samanides donna la solution de l'équation du second degré et définit les règles de transformation des expressions (algèbre) à partir des travaux de Brahmagupta. Il écrivit une encyclopédie des procédés de calcul, Kitab al Jabr (de jabara, réduire) qui sera diffusée dans le monde entier, traduite en latin et transmettra ainsi aux Occidentaux les règles de calcul sur la représentation décimale. On appellera « algorithme » un procédé de calcul figurant dans cet ouvrage, le nom de l'auteur se trouvant en tête. Puis on dénommera algorithme tout procédé de calcul, voire tout raisonnement formel.

Divers algorithmes ont été en fait connus dès l'Antiquité dans le domaine de l'arithmétique ou de la géométrie, parmi lesquels, notamment :

• le schéma de calcul du nombre p dû à Archimède ;
• l'algorithme d'Euclide (env. 300 av. J.-C.) qui permet le calcul du plus grand commun diviseur de deux nombres ;
• plusieurs méthodes de résolution d'équation en nombres entiers, à la suite des travaux de Diophante d'Alexandrie au IV^e siècle ;
• les règles de calcul de longueur d'arcs et de surfaces des civilisations égyptienne et grecque.

le schéma de calcul du nombre p dû à Archimède.

En fait, autrefois, un procédé de calcul faisait l'objet d'un discours mathématique en langage clair. L'algorithme d'Euclide était décrit ainsi par un énoncé discursif. Jusqu'au XX^e siècle, il était admis que la solution de tout problème pouvait faire l'objet d'un algorithme et de manière plus générale qu'il existait un algorithme universel permettant de résoudre tout problème, choisissant automatiquement la méthode adaptée à sa solution.

La recherche de cet algorithme universel était un des grands problèmes de la mathématique. Il a été clairement énoncé pour la première fois par Leibnitz.

En 1901, il faisait partie de la série des problèmes ouverts proposés par Hilbert à la sagacité universelle.

L'algorithme est une classe particulière d'opérations intelligentes bien définie mathématiquement dont la définition exacte est :

Suite de prescriptions précises qui dit d'exécuter dans un certain ordre des opérations réalisables pour aboutir au bout d'un nombre fini d'opérations à la solution de tous les problèmes d'un certain type donné.

Ainsi donc durant plusieurs siècles et jusqu'à une période récente, on supposait l'existence d'un algorithme universel, c'est-à-dire l'existence d'un procédé de calcul permettant de résoudre sans réfléchir tout problème donné. De plus il était implicitement admis que toute opération intelligente pouvait être décrite par un algorithme.

Formulé de manière explicite par Leibniz, ce problème fut reposé par HILBERT en 1901, puis ramené au problème dit de la « décision de la décidabilité » également par HILBERT en 1928.

En 1935, un jeune mathématicien anglais, Alan TURING imagina une machine idéale pour exécuter tout algorithme et la décrivit dans une publication célèbre en 1937.

Cette machine était constituée :

• l'état présent de l'unité ;
• ce qu'il y a dans la case ;
• se déplacer d'une case à droite ou à gauche ;
• lire, écrire, effacer ce qu'il y avait dans la case située devant elle,
  • d'une unité de contrôle située devant une case et qui pouvait :
  • d'une bande de papier infinie composée d'une suite de cases pouvant contenir un seul symbole ou être vide.

- l'état présent de l'unité.

Les règles qui fixent l'action sont mises sous forme d'une table des états dans l'unité de contrôle qui alors opère toute seule. TURING montra qu'il existe une table des états pour tout algorithme, et donc qu'il existe une machine de ce type (maintenant appelée « machine de Turing ») pour tout algorithme. Dans le cas d'une machine de Turing binaire, il y a dans chaque case 0, 1 ou rien.

La machine de Turing est un automate algorithmique universel, et TURING pensait avoir décrit la machine intelligente universelle.

Mais en 1931, un mathématicien autrichien, Kurt GÖDEL, avait démontré un théorème célèbre dont une des principales conséquences était que certains problèmes que l'intelligence humaine savait résoudre ne pouvaient pas être résolus par un algorithme ! Et un autre mathématicien, Alonzo CHURCH, montra en 1936 que cela conduisait à l'impossibilité du fameux problème de la décision de la déductibilité, base de l'algorithme universel, et par conséquent à l'impossibilité de réaliser l'algorithme universel.

La vérité scientifique oblige à dire qu'on n'en tira toutes les conséquences que vingt ans après (NOVIKOV, 1955, travaillant sur les chaînes de MARKOV) en s'interrogeant sur des difficultés rencontrées dans l'usage des ordinateurs pour résoudre certains types de problèmes. Nous verrons l'importance de cette question dans les recherches actuelles sur l'intelligence artificielle.

Un autre objet mathématique a aussi joué un rôle important dans la théorie des algorithmes : la chaîne de MARKOV (décrite en 1914 par un mathématicien norvégien, THUE, et dont les propriétés ont été étudiées par le mathématicien russe Andréi A. MARKOV). Il s'agit d'une suite de caractères alignés. Et on se pose le problème de la règle systématique qui, appliquée à cette chaîne, puis encore au résultat, permet d'arriver à une autre chaîne donnée. Ce problème qui semblerait relever des mathématiques amusantes a pris un grand intérêt lorsqu'on a montré qu'il y avait un isomorphisme entre les algorithmes et les chaînes de MARKOV. On disposait donc d'une formalisation mathématique de l'algorithme et les théorèmes sur les transformations des chaînes de MARKOV pouvaient s'appliquer aux algorithmes. Nous avons là un exemple intéressant du rôle que peuvent jouer du jour au lendemain des travaux mathématiques apparemment de la plus totale gratuité.

Un algorithme contient tout ce qui permet de l'exécuter, il est non ambigu et indépendant du contexte. C'est sa définissabilité. Un algorithme définit une classe de problèmes. Il est capable de résoudre tous les problèmes de cette classe. Exemple : l'algorithme de l'addition donne un résultat correct, quels que soient les opérandes. On parle de la massiveté d'un algorithme. Il y a isomorphisme entre un algorithme et la classe de problèmes qu'il résout. Un algorithme doit donner son résultat au bout d'un nombre fini d'opérations, même si ce nombre est très grand et si l'algorithme n'est pas physiquement réalisable. Par exemple l'algorithme combinatoire qui résout le jeu d'échecs est fini au sens mathématique, alors que sa taille interdit de le réaliser physiquement. Il faudrait une mémoire de la taille de l'Univers connaissable ! C'est le problème du « mur du combinatoire ». Un algorithme potentiellement réalisable peut n'être pas physiquement réalisable.

L'objet de l'algorithmique est donc la conception, l'évaluation et l'optimisation des méthodes de calcul en mathématiques et en informatique. Un algorithme consiste en la spécification d'un schéma de calcul, sous forme d'une suite d'opérations élémentaires obéissant à un enchaînement déterminé.

L'art de programmer est l'art de faire résoudre des problèmes par des machines. Un ordinateur étant dénué d'intelligence ; il ne peut donc résoudre que les problèmes pour lesquels existe une méthode de résolution algorithmique, c'est-à-dire une recette déterministe (bien que certaines heuristiques reposent sur l'utilisation d'une forme de hasard). De plus, même si la recette existe en théorie pour résoudre tel ou tel problème, encore faut-il que l'énoncé du problème - l'espace des paramètres - et l'ensemble des solutions soient de dimension finie, en raison de la limitation en taille de la mémoire des machines. Enfin, condition ultime, la mise en œuvre d'un algorithme doit avoir une durée finie. Un problème dont la solution nécessite de disposer d'un temps infini n'est pas considéré comme résoluble par ordinateur. Ces trivialités vont donc limiter nos ambitions de programmeur à une classe de problèmes assez restreinte.

II-A. Un exemple d'algorithme : le SOUNDEX▲

<!-- SOUNDEX Code Generator in Java Script-->

// create object listing the SOUNDEX values for each letter

// -1 indicates that the letter is not coded, but is used for coding

//  1 is for BFPV

//  2 is for CGJKQSXZ

//  3 is for DT

//  4 is for L

//  5 is for MN my home state

//  6 is for Rfunction makesoundex() 

{  

this.a = -1  

this.b =  1  

this.c =  2  

this.d =  3  

this.e = -1  

this.f =  1  

this.g =  2  

this.h = -1  

this.i = -1  

this.j =  2  

this.k =  2  

this.l =  4  

this.m =  5  

this.n =  5  

this.o = -1  

this.p =  1  

this.q =  2  

this.r =  6  

this.s =  2  

this.t =  3  

this.u = -1  

this.v =  1  

this.w = -1  

this.x =  2  

this.y = -1  

this.z =  2}

var sndx=new makesoundex()

// check to see that the input is valid

function isSurname(name) {

if (name=="» || name==null) {

    alert("Please enter surname for which to generate SOUNDEX code.")

            return false  

} else {

   for (var i=0 ; i<name.length ; i++) {

      var letter=name.charAt(i)

      if (!(letter>='a» && letter<='z» || letter>='A» && letter<='Z»)) {

        alert("Please enter only letters in the surname.")

        return false      

                }    

        }  

}  

return true

}

// Collapse out directly adjacent sounds

// 1. Assume that surname.length>=1

// 2. Assume that surname contains only lowercase letters

function collapse(surname) {

  if (surname.length==1) {

    return surname  

  }  

  var lname=(document.myform.surname.value)

  document.myform.lname.value=lname  

  var right=collapse(surname.substring(1,surname.length))

    if (sndx[surname.charAt(0)]==sndx[right.charAt(0)]) {

     return surname.charAt(0)+right.substring(1,right.length)  

         }  

 return surname.charAt(0)+right  }

 // Compute the SOUNDEX code for the surname

 function soundex(form) {

  form.result.value="»  

   if (!isSurname(form.surname.value)) {

    return  

   }    

   var stage1=collapse(form.surname.value.toLowerCase())  

   form.result.value+=stage1.charAt(0).toUpperCase() 

   // Retain first letter  form.result.value+="-» 

   // Separate letter with a dash  

   var stage2=stage1.substring(1,stage1.length)  

   var count=0  

   for (var i=0 ; i<stage2.length && count<3 ; i++) {

    if (sndx[stage2.charAt(i)]>0) {

      form.result.value+=sndx[stage2.charAt(i)]

      count++

    }

  }

  for (; count<3 ; count++) {

    form.result.value+="0»

  }  

  form.surname.select()  

  form.surname.focus()  }

PROGRAM Soundex ;

USES CRT ;

VAR St,St2:STRING ;

    i:BYTE ;

    Voyelle:SET OF CHAR ;

        FUNCTION Majus(Ch :CHAR) :CHAR ;

        BEGIN

        CASE Ch OF  

          «a»,'à','ä','â': Majus :='A» ;

      «e»,'é','è','ê','ë': Majus:='E» ;

          «i»,'ï','î»        : Majus :='I» ;

          «o»,'ô','ö»        : Majus :='O» ;

          «u»,'ù','û','ü»    : Majus :='U» ;

          «c','ç'            : Majus :='C' ;

        ELSE Majus:=UPCASE(Ch) ;

END ;

END ;

BEGIN

Voyelle:=[«A»,'E','I','O','U»] ;

WRITE(«Introduisez une chaîne : ») ;

READLN(St) ;

St2:='' ;

FOR i:=1 TO LENGTH(St) DO

  IF St[i]<>» « THEN St2:=St2+Majus(St[i]) ;

  St :=»' ;

  FOR i:=1 TO LENGTH(St2) DO

  IF NOT (St2[i] IN (Voyelle+[«Y','H','W»])) THEN St:=St+St2[i] ;

  St2:=St[1] ;

  FOR i:=2 TO LENGTH(St) DO

    CASE St[i] OF

      «B»,'P»     : St2:=St2+'1' ;

      «C','K','Q' : St2:=St2+'2' ;

      «D','T'     : St2:=St2+'3' ;

      «L'         : St2:=St2+'4' ;

      «M','N'     : St2:=St2+'5' ;

      «R»         : St2:=St2+'6' ;

      «G»,'J'     : St2:=St2+'7' ;

      «S','X','Z» : St2:=St2+'8' ;

      «F»,'V»     : St2:=St2+'9' ;

  END ;

  St:=St2[1] ;

  FOR i:=1 TO LENGTH(St2) DO

    IF St2[i]<>St[LENGTH(St)] THEN St:=St+St2[i] ;

        IF LENGTH(St)<4 THEN FOR i:=LENGTH(St) TO 4 DO St:=St+'0'

        ELSE IF LENGTH(St)>4 THEN St:=COPY(St,1,4);

        WRITELN(«Le code SOUNDEX vaut : »,St) ;

 END.

BRETON Philippe

Histoire de l'informatique

La Découverte, 1987.

Aho, Hopcroft et Ullman

Structures de données et algorithmes

Addison-Wesley, 1987

Froidevaux, Gaudel et Soria

Types de données et algorithmes

Mc Graw-Hill, 1990

Cormen et Leiserson

Introduction à l'algorithmique

Dunod, 1992

AHO A., ULLMAN J.

Concepts fondamentaux de l'informatique

Dunod 1993.

BEAUQUIER D., BERSTEL J., CHRETIENNE Ph.

Éléments d'algorithmique

Masson 1992.

PATTIS R. E.

Karel the Robot, a gentle introduction to the art of programming

John Wilez & Sons, 1995.