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.
Puis, l'Intelligence Artificielle a révolutionner la façon de programmer. En prenant comme base de langage, Python, un choix totalement répandu dans le monde scientifique, l'IA peut transcrire avec une très grande facilité tout pseudo code en Python. Il peut transcire directement l'algorithme décrit en langue naturelle aussi bien qu'un langage formelle sur mesure transcrivant cette algorithme. Et il propose des programmes testes permettant de vérifier l'exactitude du calcul fait par le programme.
Les mathématiques nous proposent des objets très généraux telles les graphes que l'on utilise en algorithmie et dans la conception des structures de données. 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ée à 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, le but étant de supprimer les ambiguités et de compléter la description littérale de l'algorithme par une forme exacte.
Le langage python nous offre une base maléable pour pouvoir construire notre interface. Si nous la décrivons suffisament précisement, l'IA pourra la programmer tout aussi précisement. Et il nous suffira de l'exécuter pour pouvoir la tester.
Dans ce premier niveau de rédaction d'un algorithme, on conçoit un graphe entièrement en mémoire. Par la suite nous considérerons des graphes plus vastes ne pouvons pas tenir en mémoire, mais qui seront toujours bien définis par l'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.
Pour simuler cette situation, on crée deux couches logiciels, une premier couche qui comprend le graphe en entier appelé le modèle monde, et une seconde couche qui contient l'algorithme de recherche n'utilisant que son interface de commande de lecture du graphe.
Le défaut des informaticiens est de donner au variables des noms long qui rendent la lecture mathématique des programmes assez 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 déjà des noms courts, et il n'est pas utile de les renommer de façon plus courte.
Les variables sont représentées par une lettre en italiques, tandis que les attributs sont écrits en caractère droit et comprennent plus souvent plusieurs lettres.
Le langage le plus général est alors défini de façon 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"`.
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".salidas"` désigne la liste des arcs partant de `x`. Le terme `x".entradas"` 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` :
La liste des noeuds du graphe `G`. Le graphe auquel appartient le noeud `x`. La liste des arcs sortant de `x`. La liste des arcs entrant sur `x`. Le noeud de départ de l'arc `p`. Le noeud d'arrivé de l'arc `p`.
Tous ces attributs sont privés, c'est à dire en lecture seul de l'extérieur du modèle monde.
À 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".peso"`. On permet ainsi l'ajout d'un attribut à une classe du modèle monde, mais cela reste un ajout local, de valeur `"None"` par défaut, qui peut ainsi être utilisé par l'algorithme.
L'objet noeud est 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.
Objet |
Instruction |
Description |
Grafo `G` |
`G ="Grafo"(N"="10,b"="3,s"="1)` |
Crée un nouveau graphe `G` de `N` sommets, avec un nombre moyen d'arc sortant par noeud `b`, et une graine de hasard `s` |
`G".destruir"()` |
Elimine le graphe `G`. Supprime tous ses noeuds. | |
Nodo `x` |
`x="Nodo"(G)` |
Crée un nouveau noeud `x` dans le graphe `G`. |
`x".destruir"()` |
Elimine le noeud `x` ainsi que tous les arcs partants ou arrivants sur `x`. | |
Arco `p` |
`a="Arco"(x,y)` |
Crée un arc partant du noeud `x` et allant sur le noeud `y`. |
`a".destruir"()` |
Elimine l'arc `a`. |
La modification du graphe se fait avec ces seules commandes qui maintiennent l'intégrité de la structure de données.
Sur le prompt suivant, ChatGPT programme les trois classes.
On écrit en Python La classe `"Nodo"` comprend : Lorsque l'on détruit un arc, on le retire de la liste des arcs entrants du noeud d'arrivé de l'arc, et on le retire de la liste des arcs sortants du noeud de départ de l'arc. Lorsqu'on détruit un noeud `x` appartenant à un graphe `G`, on détruit tous les arcs sortant de `x` et tous les arcs entrant dans `x`, et on retire `x` de `G".nodo"` Lorsqu'on crée un graphe, on passe en paramètre `N"="10` et `b"="3` et on construit un nouveau graphe ayant les caractéristiques suivantes : Lorsqu'on détruit un graphe, on détruit tous ses noeuds. |
Le squelette de notre langage est correctement établi. Pour réduire l'aspect verbeux, on devra utiliser des opérateurs mathématiques désignés par des symboles (un caractère unique) plutôt que par une chaine de caractères.