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 convient de l'écrire une seconde fois 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 une exactitude qui n'est pas celle de la programmation finale, une exactitude intermédiaire où le choix entre algorithmes détaillés 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.
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ù cela de change pas radicalement 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 les arcs correspondent à des actions transformant le système.
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".Grafico"`.
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 niveau d'échelle élevé. Et donc que 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 interfaciel nous pousse naturellement à concevoir des arcs d'un graphe à un autre.
Le terme `x".arco"` désigne la liste des arcs partant de `x`. Le terme `x".arco_"` désigne la liste des arcs arrivant sur `x`. Le terme `x".hijo"` désigne la liste des noeuds fils. Le terme `x".padre"` désigne la liste des noeuds parents. 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` :
Objet |
Instruction |
Description |
Graphe `G` |
`G".""nodo"` |
La liste des noeuds du graphe `G`. |
| .
Noeud `x` |
`x".grafico"` |
Le graphe auquel appartient le noeud `x`. |
`x".arco"` |
La liste des arcs sortant de `x`. | |
`x".arco_"` |
La liste des arcs entrant sur `x`. | |
`x".hijo"` |
La liste des fils de `x`. | |
`x".padre"` |
La liste des parents de `x`. | |
Arc `p`
|
`p".initio"` |
Le noeud de départ de l'arc `p`. |
`p".fin"` |
Le noeud d'arrivé de l'arc `p`. |
De même, on donne un rôle plus important aux références `"initio", "fin", "hijo", "padre", "arco", "arco_"` et `"arco_"`, 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.
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. Pour éviter les erreurs de dépassement de borne d'indice, on choisie une numérotation cyclique, faisant que tout indice entier est interprété modulo la taille de la liste.
`L[i] = L[i % L".tamano"]`
Les cases d'une liste sont modifiables. Exemple : `L[i]"≔"x`
Alors, il ne faut pas voir là le choix d'un algorithme de traitement des listes, qui, avec quelques modifications complémentaires accessoires peuvent tous être rendus de complexité comparable, mais le choix d'une façon de nommer simplement les choses. La liste sert aussi de file et de pile, qui, nommées dans un espace de noms constitue une mémoire partagée entre plusieurs sous-programme, et servent de canaux de transmission entre sous-programmes comme on le verra au chapitre 9.
L'ajout d'un élément dans une liste nécessite une méthode qui doit préciser le lieu où l'on insère cet élément dans la liste, et qui par défaut le place en fin de liste. Et ce n'est pas un choix algorithmique, juste un choix de représentation. La liste pouvant représenter à la fois une pile et une file, la méthode d'ajout est désignée pareillement. Considérons une liste `L`. Et considérons l'instruction suivante :
`x"≫"L`
Cela signifie que l'on ajoute l'élément `x` à la liste `L`. Et par défaut on le place à la fin de la liste. On pourrait le placer au début de la liste, mais les avantages en complexité reste faible, elle peuvent d'ailleurs faire l'objet d'une optimisation lors de la programmation donc après la conception de l'algorithme. 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 vont trancher la question.
Mais il est toujours possible d'affiner l'algorithme et on développe le langage comme suit : Si on souhaite l'insérer à la position `i` (modulo la taille de la liste `"+"1`) en déplaçant l'élément s'y trouvant et les suivants d'une case vers le haut, on notera
`x"≫"[i]L`
Et réciproquement, si l'on souhaite retirer de la liste le dernier élément placé, on exécutera l'instruction `x"≪"L` et si on souhaite retirer l'élément en place `i` (modulo la taille de la liste), en déplaçant les éléments suivants d'une case vers le bas, on exécutera `x"≪"[i]L`.
La taille de la liste est donnée par l'attribut `"n"`. Ainsi `L".n"` désigne la taille de la liste `L`. Dans cette notation, l'instruction `x"≫"[i]L, x"≪"[i]L` ne change rien. Et celle-ci non plus `x"≪"[i]L,x"≫"[i]L`. Il faut que la taille de `L` soit incrémenté après l'interprétation de la commande, juste au moment de l'insertion `x` dans `L`, de telle sorte que la valeur `L".n"` soit calculée avant l'incrémentation de la taille, et qu'elle soit modulo la taille `"+"1`. Ainsi nous avons :
`x"≫"L = x"≫"[L".tamano"]L`
`x"≫"[i]L = x"≫"[i % (L".tamano+"1)]L`
La liste peut être être utilisée comme un sac ou un ensemble ou un arrangement ou une pile ou une file. Cela fait apparaitre d'autres attributions, tel l'appartenance, le retrait d'une occurences, etc...
`x"∈" L`
`x"⋘" L`
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 notre langage en cours de route.
|
Liste `L` |
`L".tamano"` |
La taille de la liste `L`. |
| `L[i]` |
L'élément en place numéro `i` (modulo la taille de la liste) dans la liste `L`. Sachant que les numéros de place commence par zéro. La place numéro `"-"1` correspond à la dernière place. |
|
`x"≫"L` |
Empile `x` dans `L`. Cela modifie `L`. | |
`x"≪"L` |
Dépile `x` de `L`. Cela modifie `x` et `L`. | |
`x"≫"[i]L` |
Insère `x` dans `L` à la position `i` (modulo la taille de la liste `"+"1`). Cela modifie `L`. | |
`x"≪"L` |
Enlève `x` dans `L` qui est à la position `i`. Cela modifie `x` et `L`. |
Plus propre à la nature d'ensemble :
| Liste `L` | `x"∈" L` |
Teste si `x` est dans la liste `L`. |
`x"⋘" L` |
Si `x` est dans la liste `L` alors retire une occurence de `x`. |
On peut ajouter des méthodes supplémentaires telles que par exemples :
Liste `L` |
`L".ord"(v("."))` |
Trie la liste `L` selon l'ordre de la valuation `v(x)` des éléments `x`. |
`L".ord"(r(".,."))` |
Trie la liste `L` selon la relation d'ordre `r(x,y)` appliquée à un couple d'éléments `(x,y)`. |
Avec ce langage sur les listes, nous pouvons cheminer dans un graphe à partir d'un noeud `r` en prenant succéssivement le fils n°`0`, puis le dernier fils, puis le fils numéro `4` (toujours modulo le nombre de fils du noeud) à l'aide de l'instruction suivante :
`r".hilos"[0]".hilos"["-"1]".hilos"[4]`
L'instruction ne retourne `"nada"` que si l'un des noeuds parcouru n'a pas de fils.
Objet |
Instruction |
Description |
|
Global |
`G "=nuevoGrafico"()` |
Crée un nouveau graphe `G` vide. |
Graphe `G` |
`x"≫"G".nodo"` |
Ajoute au graphe `G`, un nouveau noeud `x` (en dernière position). |
`x"≫[i]"G".nodo"` |
Ajoute au graphe `G`, un nouveau noeud `x` en le plaçant en position `i` (modulo la taille de la liste `"+"1`) et en déplaçant les éléments suivants d'une case vers le haut. | |
`G".eliminar"()` |
Elimine le graphe `G`. Supprime tous ses noeuds et arcs y accédant ou y partant | |
Noeud `x` |
`"arco"(x,y)` |
Ajoute un arc partant de `x` et allant sur `y` (en position `(0, 0)`). |
`"arco"(x,n,y,m)`
|
Ajoute un arc partant de `x` et allant sur `y` en le plaçant en position `(n, m)`, numérotation cyclique, et en déplaçant les éléments suivants d'une case vers le haut). | |
`x".eliminar"()` |
Elimine le noeud `x` ainsi que tous les arcs liée à `x`. | |
Arc `p` |
`p".eliminar"()` |
Elimine l'arc `p`. |
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"`.
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 seconde partie. En attendant, on commence superficiellement en proposant la notation suivante :
On ajoute une boucle plus rudimentaire :
Ces trois opérations de choix `EEx "∈" E"/"(...), AAx "∈" E, "ට"x "∈" E` se font par défaut au hasard. L'algorithme pourra préciser un ordre. Les blocs, débutant avec `EE,AA,"ට"` se terminent avec la parenthèse fermante s'il y a une parenthèse ouvrante avant les instructions `EE,AA,"ට"`, ou par un passage à la ligne sans indentation. Puis, comme dans les formules logique, il n'est pas nécessaire de mettre des parenthèses dans une succession de boucle imbriquée telle que par exemple :
`AAx "∈" E, AAy"∈" E, Ez"∈" E"/"(...), ... `
Ne nous formalisons pas avec les définitons précédentes concernant les listes. Ici, il s'agit d'un ensemble, le symbole `"≫","≪"` sont interprétés différemment, et l'inférence de type enlève l'ambiguité.
Tel un fractal, un programme, s'il est suffisament complexe, comprendra des sous-programmes qui se comportent comme des programmes. Un programme contiendra des sous-programmes, c'est à dire ayant une entrée, et une sortie. La programmation consistera alors à raccorder les différentes sorties aux différentes entrées de ces différents sous-programmes. Cela permet de mettre en oeuvre la pile des appels avec un contexte distinct pour chaque appel d'un sous-programme.
Un programme peut ne pas s'arréter et s'exécuter en parallèle avec d'autres programmes. Il comprend alors deux types d'entrée/sortie particulièrement simples que sont celles transmises avant le début de son exécution comme entrée ou à la fin de son exécution comme sortie à travers des médiums appelés variables d'entrée/sortie, et celles transmises en cours de route à travers des médiums appelés flux d'entrée/sortie.
Puis il comprend une autre entre/sortie plus complexe que sont les graphes partagés qu'il explore et modifie. Et cela comprend non seulement les graphes mais toute structure de données partagées par plusieurs sous-programmes.
Le programme se décompose en sous-programmes qui peuvent s'éxecuter en parallèles et qui sont reliés entre-eux par des variables d'entrés/sortie et des flux d'entré/sortie. L'algorithmie se contente de ces deux modes. Reste à trouver la meilleur notation. Les programmes ou sous-programmes sont des blocs de codes, c'est à dire des n-uplets d'instruction, c'est pourquoi nous utiliserons les parenthèses `( )` pour encadrer un bloc de code et non les crochets `{ }` que l'on réserve au énumération où l'on peut permuter deux éléments quelconques.
Les noms des variables globales et de flux globaux occupent l'espace de noms du programme principale. L'aspect fractal se manifeste également dans les espace de noms, faisant que des espaces de noms existe à tous les niveaux, et qu'ils héritent des espaces de noms parent.
Le bloc de code est un `n`-uplet d'instructions qui commence éventuellement par énumérer les variables d'entrée suivit par le symbole "|" puis par énumérer les instructions suivit par le symbole "|" puis par énumérer les variables de sortie. Exemple `(A,B|...|C,D)`. Les variables de sortie sont identifiées à l'échelle d'une strate et de doivent apparaitre comme variable de sortie qu'une seul fois. Avec cette règle, toutes variables de sortie définie une composition arborescente unique de sous-programmes aboutissant à son calcul.
Les flux ou canaux sont des éléments essentiels de programmation. Ils sont identifiés globalement par une lettre préfixé par l'un des symbole `"།"z, "༐"z`, selon que la conexion est synchrone ou asynchrone. On accroit la puissance de programmation en les identifier à des éléments ordinaires avec toutes les commoditées qui les accompagnent, sur lesquels on ajoute par dessus les méthodes spécifiques aux canaux. La variable désignant le flux se comporte comme une variable contenant le premier terme du flux.
Un flux connecté de façon asynchrone peut être vide. Apparait donc un terme spécifique pour indiquer un flux vide. C'est le terme désignant rien, noté `sf"nada"` ou de façon court par le symbole `"□"`.
La plus part du temps les flux se terminent. Apparait donc un autre terme spécifique pour indiquer la fin du flux de termes. C'est le terme de fin-de-transmission. On le notera `"∎"`. Ces deux termes sont associés à des mécanismes d'exception.
Le canal possède deux modes d'écriture, un mode d'écriture synchrone, et un mode d'écriture asychrone. Et deux modes de lecture, la lecture et la prévue.
Si il y a plusieurs demande d'écritures synchrones, elle sont mise dans une file d'attente. Et les demandes d'écritures asynchrones passe devant les demandes d'écriture synchrone bloquée pour être tout de suite exécutées.
Si le canal n'utilise pas d'écriture asynchrone, il est dit synchrone et d'implémentation plus simple. Par contre si le canal est utilisé avec des écritures asynchrones, il se comporte comme une file, une mémoire tampon, capable d'enfiler un grand nombre d'éléments.
Un canal peut être cloné plusieurs fois. On le note en metttant un indice `"།"z, "།"z_0,"།"z_1,"།"z_2`
La lecture ainsi que la prévue peuvent tomber sur `sf"nada"` indiquant que le canal n'a pas encore envoyé de données, et sur `"∎"` indiquant une fin de transmission. On prédéfinit quatres gestions d'évènement que sont la fin de transmission d'un canal, l'activation d'un canal, le dépassement d'une quantité de mémoire d'un canal, la lecture d'un élément particulier sur un canal :
Ces gestionnaires peuvent être placé à plusieurs endroits. Lorque l'évènement se produit, le signal est capturer par les blocs de code en exécutions, puis successivement par les blocs de codes parents et ainsi de suite.
Deux variables `x,y` peuvent être égales `x"="y`, mais davantage elles peuvent désigner la même valeur `x"≡"y`. Puis certaines parties de l'élément `x` peuvent être partagés. Le cas générale s'appelle un terme, et certaines parties du terme peuvent être partagé avec d'autres termes.
On définie des priorités et autres mécanismes syntaxiques dans le but de réduire l'usage des parenthèses, dont on ne sait pas encore très bien la forme que cela va prendre. Le but consiste à réduire la taille des algorithmes formels en les constituant en un emboitement d'opérations arithmético-informatiques fondamentales.
Un des permiers algorithmes de base à concevoir est l'exploration d'un graphe. Cela consiste à énumérer tous les noeuds du graphe accessible à partir d'un ensemble de noeuds de départ `D` en parcourant les arcs dans leur sens autorisés.
L'algorithme consiste à étendre progressivenment l'ensemble des noeuds atteints `E` tout en réduisant l'ensemble des noeuds à explorer `F` qui forme une frontière entre les noeuds déjà explorés et les noeuds inconnus. La frontière `F` contient les noeuds connus mais non encore explorés.
L'ensemble des noeuds de départs constitue les premiers noeuds connus mais non encore explorés, `E"≔"D`. Et donc il constitue l'ensemble des noeuds à explorer `F"≔"D`. On prend un noeud dans la frontière `F` et on explore ses noeuds fils. Si le noeud fils est déjà connu, c'est à dire s'il appartient à `E`, alors dans ce cas ne rien faire, sinon ajouter le fils dans `E` et dans `F`. Une fois tous les fils traités, on retire le noeud de `F`. Et on recommence jusqu'a ce que `F` soit vide.
`(D |`
`"var" E"≔"D`
`"var" F"≔"D`
`"ට"x"∈" F, x"≪"F, (AAy "∈" x".hilos", y "∉" E => y"≫"E, y"≫"F)`
`| E)`
Le concept d'ensemble frontière `F` entre les noeuds déjà traités et les noeuds inconnus, qui regroupe les noeux connus qu'il faut traiter, permet de définir après-coup la stratégie de parcours du graphe, en précisant dans quel ordre sont traiter les éléments de `F`.
On considère que le retrait de `x` de `F` est un traitement de bas niveau de protocole, c'est pourquoi on remplace `"ට"x"∈" F, x"≪"F,...` par `AAx "∈" F, ...`
`(D |`
`"var" E"≔"D`
`"var" F"≔"D`
`AA x "∈" F,AAy "∈" x".hilos", y "∉" E => y"≫"E, y"≫"F`
`| E)`
On représente la procédure sous forme d'un bloc de code avec une entrée `D` et une sortie `E`. La procédure en cours d'exécution, possédant la variable locale `E` doit pouvoir être interrogée de l'extérieur, c'est à dire qu'une requète peut lui demander de transmettre le résultat partiel qu'elle a calculé. De plus, la variable `E` étant traitée après son initialisation comme un flux d'entrée, on doit pouvoir y greffer une dérivation pour ainsi rediriger une copie du flux vers d'autres processus. Notez que, le graphe lui-même peut ne pas être construit en mémoire. Les noeuds sont alors des états et les arcs des actions qui font passer d'un état à un autre état. C'est en permettant d'exprimer ces différents interfaçages, interactions et connexions que l'on donne toute la liberté d'application de l'algorithme. L'algorithme peut être réécrit en utilisant deux canaux publics `D` et `E` dédoublés.
---- 27 février 2026 ----
Si on veut utiliser les arcs du graphe, on remplace simplement l'instruction :
`"por" y "∈" x".hilos", y "∉" E => y"≫"E, y"≫"F`
par :
`"por" p "∈" x".arco", p".s""∉" E => p".s""≫"E, p".s""≫"F`
L'algorithme peut s'écrire littéralement :
1. Fonction EXPLORER-GRAPHE(D) où D est un ensemble de noeuds.
2. Initialise l'ensemble des noeuds connus égale à D.
3. Initialise la frontière égale à D.
4. Faire en boucle :
1. Si la frontière est vide alors arréter et retourner l'ensemble des noeuds connus.
2. Choisir un noeud dans la frontière.
3. Pour chaque noeud fils, s'il n'est pas déjà connu.
1. Ajouter-le dans la frontière.
2. Ajouter-le dans l'ensemble des noeuds connus.
4. Retirer le noeud choisi de la frontière.
On munie chaque arc `p` d'un attribut de distance, `p".dist"`. Et on souhaite rechercher les chemins les plus courts partant d'un noeud `r`. De tels chemins peuvent être multiples si les distances sont égales, et forme un sous-graphe couvrant tous les noeux.
Il n'est pas nécessaire de mémoriser tous les arcs qui constitue les chemin les plus courts. En effet, si l'on connait les disance minimale de la racine pour chaque noeud, alors à partir de n'importe quel noeud, pour retrouver les chemins les plus court, on choisie les noeuds fils dont la distance minimale est égale à la distance minimal du noeud père plus la distance de l'arc emprunté. Cette remarque simplifie le problème au seul calcul des distances minimales.
Une approche simple consiste souvent à mémoriser le résultat dans le graphe lui-même. On munit les noeuds `x` d'un attribut supplémentaire mémorisant la distance au noeud `r` la plus petite connue, `x".dist"`. Cet attribut est initialisé à `x".dist="∞` sauf pour le noeud `r` qui vaut `r".dist="0`.
La structure de données étant posée, voyons comment nous pouvons déduire un algorithme presque naturellement en le construisant par tâtonnement. On part d'un exemple générale que l'on essaye de résoudre.
On explore le graphe à partir de la racine `r`. Ainsi la frontière `F` vaut initialement `F"="{r}`. L'exloration d'un noeud `x` consiste à explore chaque arc partant de `x`. Pour un arc `p` partant de `x`, on ajoute la distance minimum connu de `r` à `x` mémorisé dans `x".dist"` à la distance de l'arc `p".dist"` et on compare cette nouvelle distance avec la distance minimum connu du noeud d'arrivé de l'arc `p".s.dist"`. Si elle est supérieure ou égale alors elle ne modifie pas la distance minimal connue. Par contre, si elle est inférieure, alors l'arc fait un raccourci et modifie la distance minimal connu du noeud d'arrivé de l'arc. Les conséquences de cette modification sont traités simplement en réexplorant le noeud. Donc nous appliqu'on la règle suivante :
`(x".dist"+p".dist" < p".s.dist") => (p".s.dist"= x".dist"+p".dist")`
Comme le noeud dont la distance minimum a été modifiée, a été placé dans la frontière, les conséquences de cette révision de la distance minimum seront assurément traitées. L'algorithme s'arrète lorsque `F` est vide.
| `{r |` `"por" x"∈"r".grafico.nodo", x".dist="oo` `r".dist =" 0` `"var" F"="{r}` `AA x "∈" F,"por" p "∈" x".arco", (x".dist"+p".dist" < p".s.dist") => (p".s.dist" ≔ x".dist"+p".dist", p".s" "≫"F), x"≪"F` `}` |
L'algorithme calcul les distances minimales qu'il stoque dans l'attribut `"dist"` des noeuds du graphe. Donc il ne retourne rien et fait une modification des attributs `"dist"` des noeuds du graphe.
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. Et nous procédons presque par duplication, en s'inspirant de la résolution dialectique d'une proposition du premier ordre transformant la proposition en un algorithme de recherche de résolution. La notation d'exploration logique est la suivante :
Si le code du programme et écrit avec ce langage et ne se modifit pas en cours de route, et si les ensembles `E` utilisés sont finis et fixes, alors l'arrêt du programme est sûre (il n'y a pas de boucle sans fin). Deux modes d'appelle sont alors possible. Le premier mode, dit de test, est pour juste savoir si l'action est possible. Dans ce mode, après l'exécution du programme, toutes les modifiations sont annulées et seul l'éventuel signal d'échec est remonté. Le second mode dit d'action, execute le programme. Cependant si le programme émet un signal d'échec, aucune action n'aura eu lieu et les deux modes coïncideront
La situation se complique lorsque l'on autorise la modification des ensembles `E` en cours d'exécution. Le choix de l'ordre dans lequel parcours les indexes devient déterminant.
La description précédente est trop éloignée des opérations informatiques élémentaires. On peut donc proposer une autre approche plus classique de construction du langage à partir de ces opérations et objets jugés fondamentaux et parmi lesquels on trouvera l'ensemble, l'énumérateur, la liste, le graphe, etc., mais, en intégrant une partie de ce qui précède de manière plus souple. On ne journalise pas tout, seuls certains blocs, appelés blocs tests.
De la même façon qu'un 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 les arcs correspondent à des actions (transformation du système), une liste peut ne pas exister en mémoire (en particulier si elle est infinie) et être bien défini par son interface de commande. C'est ce que l'on appelle un énumérateur. Pour l'algorithme, les deux objets (liste et énumérateur) ayant le même interface, la seule distinction réside dans la complexité différente de certaines opérations.
---- 23 février 2026 ----
Les blocs de code peuvent émettre des flux et lire des flux. Et il existe un flux d'entrée standart et un flux de sortie standart pour chaque bloc de code. L'ajout d'un élément `x` dans le flux de sortie standart se note `x"≫"`. La lecture d'un élément du flux d'entré standart se note `"≫"x`.
Un bloc de code formant une boucle que l'on doit exécuter indéfiniment est préfixé par le symbole `oo`.
L'instruction qui met fin au bloc de code avant la fin et retourne ce qui suit, se note par le symbole `➥`.