Informatique
à l'heure de l'intelligence artificielle

1) Algorithme et langage de programmation

Comment écrire un algorithme ? L'algorithme est d'abord écrit en langue naturelle. Mais l'ambiguité des phrases va bloquer le lecteur sur chaque incertitude d'interprétation. C'est pourquoi il est intéressant de proposer une seconde écriture dans un langage formelle qui enlève cette incertitude. On l'écrit alors dans un langage adapté, sur mesure.

Néanmoins, les deux descriptions sont nécessaires. Car elles ne portent pas exactement les mêmes informations. L'une, littéraire, va indiquer des informations intuitives de haut niveaux de protocole. L'autre, formelle, va rendre le propos exacte. Mais cette exactitude ne sera pas celle de la programmation finale. C'est une exactitude intermédiaire où le choix entre algorithmes de complexité du même ordre n'est pas fait.

On va donc développer un langage très général. Mais le choix d'un langage n'est pas politiquement neutre, d'autant plus qu'il s'avance comme prétendument universel... Nous n'utiliserons pas de termes anglais, eu égard au contexte géopolitique guerrier dans lequel nous sommes malheureusement plongés.... Dans le but de contrer l'hégémonisme de la langue anglaise et ce qu'il illustre, la domination du monde unipolaire anglo-saxon opposée à la majorité du monde...., nous promouverons l'espagnol, une langue d'un empire déchu ayant depuis longtemps renoncé à dominer le monde, et que nous érigerons comme seconde langue internationale à l'initiative de l'Occident pour rivaliser avec l'anglais, rétablir un équilibre, et garantire un passage en douceur vers le multilatéralisme des nations. Notez que la plus part des mots clefs pourront par la suite être remplacés par des symboles mathématiques, mettant ainsi fin à la querelle des langues.

2) Les graphes

Les mathématiques nous proposent des objets très généraux telles les graphes que l'on utilise en algorithmie. On ne va pas programmer la structure sous-jacente du graphe, on va juste définir l'interface qui nous permet de construire le graphe et de l'interroger..., et de même pour d'autres structures plus savantes.... Reste à choisir la structure de graphe très générale la plus amène à proposer une interface universelle adapté à l'algorithmie. On opte pour le choix d'une structure constructive informative optimale. Le graphe orienté dans lequel les noeuds sont ordonnées, et où chaque noeud possède une liste de fils ordonnées, et donc par symétrie, une liste d'antécédents également ordonnées. Néanmoins le graphe n'étant pas spécialement planaire, il ne parait pas justifié d'introduire dès le départ un ordre sur l'ensemble réuni des arcs entrants et sortants d'un noeud. Puis dans le cas général, les arcs doivent pouvoir être multiples, et former des boucles.

L'interface d'interrogation du graphe nous donne un mini-langage de programmation, ce qui nous permet d'écrire formellement les algorithmes. Supprimant ainsi les ambiguités, ils deviennent davantage lisibles.

Dans ce premier niveau de rédaction d'un algorithme, il n'est pas nécessaire de distinguer ce qui relève du référençage ou de l'exécution d'une méthode, dans la mesure où un post-développement est possible permettant de ne pas changer la complexité de l'algorithme. Autrement dit, ces méthodes sans paramètre ont une forme d'appel identique à celle des attributs, et s'appellent des références.

Le graphe peut ne pas exister en mémoire mais être bien défini par son interface de commande où les noeuds du graphe correspondent à des états d'un système et où les arcs correspondent à des actions transformant le système.

Puis le graphe peut s'avérer être un arbre. Un arbre aura donc le même interface de commande. Autrement dit, un arbre est un graphe qui possède la propriété d'être un arbre.

Il y a deux types de notation, celle du langage fonctionnel et celle du langage objet. La trancription est quasi immédiate comme dans l'exemple suivant : `x".titi"(a,b) := y` est remplacé par `"TITI"(x,a,b):=y`

3) Interface de lecture du graphe (langage objet)

Le défaut des informaticiens est de donner au variables des noms long qui rendent la lecture mathématique des programmes plus que pénible. On remédit à cela en créant des espace de noms locaux où les varaibles sont désignés par une seule lettre. Par contre, les attributs étant déjà locaux, ils ont des noms courts, et il n'est pas utile de les renommer de façon plus court.

Les variables sont représentées par une lettre en italiques, tandis que les attributs sont écrit en caractère droit et comprennent souvent plusieurs lettres.

Le langage le plus général est alors quasi-canonique. Il comprend la référence `G".nodo"` qui désigne la liste des noeuds du graphe `G`. On opte pour cette condition simple : chaque noeud `x` n'appartient qu'à un seul graphe noté `x".grafo"`.

Comme les attributs sont des méthodes, on leur donne la plus part du temps un rôle plus important en les rendant modifiables, sous entendant tout un traitement accompagnant cette modification pour garantire l'intégrité de la structure.

Rappelons que le but est d'écrire formellement un algorithme à un haut niveau de protocole. Et donc, si une méthode alternative ne change pas la compexité du calcul, elle est équivalente et il n'est pas besoin de préciser laquelle des méthodes est choisie.

Pour accéder aux arcs du graphe, on passera par l'intermédiaire des noeuds. Notez qu'un arc peut partir d'un noeud du graphe `G`, pour aller sur un noeud d'un autre graphe `H`. La recherche de la plus grande capacité d'expression possible avec le moins de complication d'interface, nous pousse naturellement à concevoir des arcs d'un graphe à un autre.

Le terme `x".arcos"` désigne la liste des arcs partant de `x`. Le terme `x".arcos_"` désigne la liste des arcs arrivant sur `x`. Le terme `p".initio"` désigne le noeud de départ de l'arc `p`. Le terme `p".fin"` désigne le noeud d'arrivé de l'arc `p` :

Dans de nombreux algorithme les graphes n'ont pas d'arcs multiples et les arcs ne sont pas utilisés explicitement. C'est pourquoi on propose d'accéder directement à la liste des fils et à la liste des parents à l'aide de deux nouvelles références. Le terme `x".hijos"` désigne la liste des noeuds fils. Le terme `x".padres"` désigne la liste des noeuds parents.

De même, on donne un rôle plus important aux références `"nodo", "grafo", "initio", "fin", "hijos", "padres", "arcos"` et `"arcos_"`, en les rendant modifiables.

À ceci s'ajoutent des attributs supplémentaires sur les noeuds et les arcs, autant que de besoin. Ainsi l'arc peut posséder une distance `p".dist"`, le noeud peut posséder un poid `x".poid"`. Et ces attributs peuvent prendre une autre forme en étant mémorisés de façon externe à la structure dans des tableaux `"dist"[p]` et `"poid"[x]`.

L'objet noeud ne semble pas avoir d'existence propre en dehors de sa structure. Autrement dit, le noeud redevient un objet général mais affiliés obligatoirement à une seule structure de graphe à la fois. Il n'en est pas de même pour l'arc. Un arc étant un lien entre deux noeuds quelconques qui chacun appartient à un graphe, l'arc est un objet générale non affilié liant deux noeuds qui sont, eux, des objets affiliés chacun à un graphe.

4) Interface de lecture du graphe (langage fonctionnel)

Les variables sont représentées par une lettre en italiques, tandis que les fonctions sont écrit en caractère droit majuscule et comprennent souvent plusieurs lettres.

Le langage le plus général est alors quasi-canonique. Il comprend la référence `"NODO"(G)` qui désigne la liste des noeuds du graphe `G`. On opte pour cette condition simple : chaque noeud `x` n'appartient qu'à un seul graphe noté `"GRAFO"(x)`.

On donne à ces fonctions la plus part du temps un rôle plus important en les rendant modifiables, sous entendant tout un traitement accompagnant cette modification pour garantire l'intégrité de la structure.

Rappelons que le but est d'écrire formellement un algorithme à un haut niveau de protocole. Et donc, si une méthode alternative ne change pas la compexité du calcul, elle est équivalente et il n'est pas besoin de préciser laquelle des méthodes est choisie.

Pour accéder aux arcs du graphe, on passera par l'intermédiaire des noeuds. Notez qu'un arc peut partir d'un noeud du graphe `G`, pour aller sur un noeud d'un autre graphe `H`. La recherche de la plus grande capacité d'expression possible avec le moins de complication d'interface, nous pousse naturellement à concevoir des arcs d'un graphe à un autre.

Le terme `"ARCOS"(x)` désigne la liste des arcs partant de `x`. Le terme `"ARCOS_"(x)` désigne la liste des arcs arrivant sur `x`. Le terme `"INITIO"(p)` désigne le noeud de départ de l'arc `p`. Le terme `"FIN"(p)` désigne le noeud d'arrivé de l'arc `p`.

Dans de nombreux algorithme les graphes n'ont pas d'arcs multiples et les arcs ne sont pas utilisés explicitement. C'est pourquoi on propose d'accéder directement à la liste des fils et à la liste des parents à l'aide de deux nouvelles références. Le terme `"HIJOS"(x)` désigne la liste des noeuds fils. Le terme `"PADRES"(x)` désigne la liste des noeuds parents.

De même, on donne un rôle plus important aux fonctions `"NODO", "GRAFO", "INITIO", "FIN", "HIJOS", "PADRES", "ARCOS"` et `"ARCOS_"`, en les rendant modifiables.

À ceci s'ajoutent des attributs supplémentaires sur les noeuds et les arcs, autant que de besoin. Ainsi l'arc peut posséder une distance `"DIST"(p)`, le noeud peut posséder un poid `"PESO"(x)`. Et ces attributs peuvent prendre une autre forme en étant mémorisés de façon externe à la structure dans des tableaux `"DIST"[p]` et `"PESO"[x]`.

L'objet noeud ne semble pas avoir d'existence propre en dehors de sa structure. Autrement dit, le noeud redevient un objet général mais affiliés obligatoirement à une seule structure de graphe à la fois. Il n'en est pas de même pour l'arc. Un arc étant un lien entre deux noeuds quelconques qui chacun appartient à un graphe, l'arc est un objet générale non affilié liant deux noeuds qui sont, eux, des objets affiliés chacun à un graphe.

Nous avons ainsi défini classiquement l'interface de gestion d'un graphe, d'usage générale. Le but maintenant consiste à concevoir un langage évolué, de traitement sur ce graphe. Mais nous n'allons pas faire ce travail directement sur un une structure de graphe générale, nous progresserons par étape en commençant par les graphes les plus simples. Et le graphe le plus simple est la liste.

5) Les listes

Le plus simple des graphes est une liste qui peut être circulaire et qui peut se décaler aussi bien d'une case vers la droite que d'une case vers la gauche. Adapter le langage pour utiliser ce graphe rudimentaire qu'est la liste est notre premier travail. Viendra pas la suite d'autre type de graphe rudimentaire un peu plus sophistiqué que la liste qui donneront également le besoin d'adapter le langage de programmation à leur usage intensif.

Les éléments d'une liste ont une place indicée dans la liste partant de `0` à `n"-"1` ou `n` est la taille de la liste. C'est ainsi qu'on la conçoit en pensé, mais il ne s'agit pas de décrire une implémentation. Il ne faut pas voir là le choix d'un algorithme de traitement des listes, qui avec quelques modifications complémentaires peuvent être rendus de complexité égale, mais une façon de nommer simplement les choses.

Le langage devant être choisi sur mesure, notre façon de faire ne doit pas consister à le prédéfinir, mais seulement à le définir tant que de besoin. Nous complèterons donc la plus grosse partie de notre langage en cours de route.

La liste sert de file et de pile, deux fonctionnements essentiels qu'il convient de pouvoir noter simplement. Ces files et piles, nommées dans un espace de noms de portée plus large, constituent des mémoires partagées entre plusieurs processus. Ils servent alors de canaux de transmission, appelé aussi flux, entre sous-programmes, comme on le verra dans la description fractale des programmes. Le choix le plus simple consiste à utiliser les 2 symboles de direction `"≫"` où `"≪"` pour indiquer le sense de déplacement d'un élément, et on ajoute un second symbole "_" pour indiquer qui joue le rôle de la liste ou du flux émmetteur ou récepteur.

`x"≫_"L` : Ajout de `x` dans le flux `L` par la gauche.
`x"≪_"L` : Retrait de `x` du flux `L` par la gauche.
`L"_≫"x` : Retrait de `x` du flux `L` par la droite.
`L"_≪"x` : Ajout de `x` dans le flux `L` par la droite.

L'idée est de généralisé la notion de flux de donnée en l'identifiant au devenir de toute variable. Le flux ne contenant qu'une donnée `x` est identique à la donnée `x` en question. Ce faisant toute variable est un flux ne possèdant qu'une seule donnée au départ. Comme toutes les variables désignent des flux, le symbole de direction ne suffit pas, il faut préciser qui joue le rôle de flux et qui joue le rôle d'élément.

Puis si un seul argument est souligné alors se second symbole "_" n'est pas utile. Ainsi par exemple `x"≫_"L` est équivalent à `x"≫"underline L`

On réserve le nom simple de la variable pour désigné la tête du flux, et le nom souligné désigne le flux sous forme d'une liste.

Lorsque les flux sont asynchrones, celui-ci peut être vide. Le flux vide est désigné par la valeur `"nada"`, et toute lecture ou extraction de ce flux retourne `"nada"`.

On visualise le flux `underlineL` par une succession de cases, et on fait entrer les nouveau éléments par la gauche ou par la droite :

`underline L = (underlineL[0],underlineL[1],underlineL[2],...,underlineL[n])`

Et la tête du flux est désignée par `L= underlineL[n]`

L'instruction `x"≫"underline L` va ajouter l'élément `x` dans la liste `underline L` par sa gauche. Elle va agrandire la liste d'une case, puis décaler la liste d'une case, et placer `x` dans `underline L[0]`.

L'instruction `underline L"≪"x` va ajouter l'élément `x` dans la liste `underline L` par sa gauche. Elle va agrandire la liste d'une case, et placer `x` dans `underline L[n"+"1]`.

On utilise le symbole dans un sens ou dans l'autre, mais toujours en soulignant une et une seule des deux variables pour indiquer laquelle joue le rôle de flux (c'est à dire qui joue le rôle de liste), et laquelle joue le rôle d'élément.

Puis il faut trouver une notation pour le cas où on lit l'élément en tête à droite sans le retirer, `x:=underline L[0]`, ou en tête à gauche sans le retirer, `x:=underlineL["-"1]` ou plus simplement `x:=L`. On adopte la notation des indices négatifs (en y ajoutant la taille de la liste pour retrouver le bon indice). Mais la notation la plus courte est bien le nom simple de la variable ici `L` qui désigne la tête du flux `underline L` c'est à dire `underline L["-"1]`.

`L= underline L["-"1]`

Notez que l'on préfère utiliser le symbole d'affectation `:=` qui est distinct du symbole de test d'égalité `=`.

Considérer une liste `A = (1,2,3)`, on crée un flux `L` en l'initialisant avec les trois éléments de la liste `A` comme suit `underline L := A`. Après cette instruction, on constate que `L=3` et `underline L[0]=1`.

Comprenez-bien qu'il ne s'agit pas d'un choix d'un algorithme par rapport à un autre, mais seulement une convention d'écriture. On définit le fonctionnement d'une liste pouvant servire de pile et de file dans un sens comme dans l'autre, et que l'on identifit à la liste des valeurs d'une variable. On pourrait s'organiser autrement, mais les avantages en complexité pourront toujours être retrouvés lors de la post-programmation de l'algorithme dans une recherche d'optimisation. C'est pourquoi d'un point de vue algorithmique cela ne compte pas, et que seul, l'habitus, la convention, apportées par le langage, ainsi que son pouvoir expressif à travers une syntaxe simple, remporte le choix.

La liste peut aussi être utilisée comme un sac ou un ensemble ou un arrangement. Sans démultiplier la typologie on crée d'autres opérations telles le test d'appartenance, le retrait d'une occurences, etc. :

Mais rappelons-nous, le langage devant être choisi sur mesure, notre façon de faire ne doit pas consister à le prédéfinir, mais seulement à le définir tant que de besoin.

Avec ce langage sur les listes, nous pouvons cheminer dans un graphe à partir d'un noeud `r` en prenant succéssivement le fils n°`3`, puis le fils numéro `0`, puis le fils numéro `2` à l'aide de l'instruction suivante :

`r".hilos"[3]".hilos"[0]".hilos"[2]`

Cette instruction retourne `"nada"` si les noeuds en question n'ont pas assez de fils.

6) Interface de construction du graphe (en langage objet)

La liste des opérations de construction de base est ainsi complète. Et elles sont valables quelque soit les valeurs des paramètres, du moment qu'ils ont les bons types.

Si on élimine un noeud `x` ou un arc `p`, après l'opération, la variable contient `"nada"`. Et les opérations sur `"nada"` ou avec un paramètre égal à `"nada"` ne modifie rien et retournent `"nada"`.

7) Interface de construction du graphe (en langage fonctionnel)

La liste des opérations de construction de base est ainsi complète. Et elles sont valables quelque soit les valeurs des paramètres, du moment qu'ils ont les bons types.

Si on élimine un noeud `x` ou un arc `p`, après l'opération, la variable contient `"nada"`. Et les opérations sur `"nada"` ou avec un paramètre égal à `"nada"` ne modifie rien et retournent `"nada"`.

6) Un premier langage de base minimaliste

C'est l'arithmétique qui engendre les algorithmes comme elle engendre la logique du premier ordre. On propose d'opter pour une notation des algorithmes prétendument plus universelle, comme l'est la notation des formules de logique du premier ordre. Cela sera discuté dans la troisième partie.

On adopte un symbole distinct de l'égalité pour l'affectation de variable. Pour modifier la valeur de `x` par celle de `y` :

`x:=y`

L'instruction d'arrêt du programme avec retour du résultats `r` se fait avec l'instruction :

`"⇴"r`

Les instructions sont séparée par des virgules ou des passages à la ligne. Les sous-programme commencent par une parenthèse ouvrante et se termine par la parenthèse fermante correspondante. Un sous-programme est un n-uplet d'instructions. Pour spécifier les données `x,y,z` d'entrées du programme on utilise comme première instruction :

`(x,z,z ↦ ...)`.

Les conditions sont présentées comme des clauses de Horn où la virgule joue le rôle de conjonction de priorité syntaxique plus faible que l'implication. Exemple :

`a">"b,  b">"c  =>  x:=a`

Autrement dit, le séparateur d'instrution "virgule" change de rôle lorsqu'il suit un teste pour jouer le rôle d'une opération de conjonction logique.

On commence par rechercher la notation à la fois la plus lègère et la plus utile. La boucle « Tant que `A` faire ... », est remplacée par l'expression

`"ට" A, ...`

Où `A` et ... sont des instructions ou des sous-programmes. Puis il convient d'avoir une notation plus particulièrement intuitive lorsqu'il s'agit de parcourir tous les éléments d'un ensemble, d'un arangement, d'un sac, d'une liste ou d'un flux :

`AAx "∈" E, ...`

Cela débute une boucle qui exécute pour chaque élément de `E` les instructions qui suivent. La stratégie de choix de `x` n'est pas précisé, et `E` s'aparente à un sac ou une liste d'éléments. Mais que se passe-t-il lorsque la valeur de l'ensemble `E` évolue en cours de route ?. La boucle utilise une copie de `E` noté `dotE`. Et à chaque choix d'un `x` dans `dotE` celui-ci est retiré de `dotE` avant l'éxecution du corps. Puis au cours de l'exécution du corps, si `E` est modifié par l'ajout ou la suppression d'un élément `y` alors `dotE` l'est également. La boucle peut donc dans certain cas ne jamais s'arréter. Tout ce passe comme si les flux d'entré/sortie concernant `E` était dupliqué pour concerner `dotE` à l'exception du retrait de `dotE` de l'élément choisie `x` à chaque début d'itération. La stratégie de choix de `x` peut être précisé comme suit :

`AAx "∈" E"/"(x"≪"E), ...`

Où l'instruction `(x"≪"E)` s'applique non pas sur `E` mais sur la copie de `E` noté `dotE` qui préside la boucle.