--------------------------------------------------------------------------------------- III. Algorithmes déterministes et non déterministes Disk-LeXic --------------------------------------------------------------------------------------- ! Salut à tous . ! L'article que vous allez lire est inspiré d'un article ! qui lui même s'est inspiré d'un article de Floyd. ! Exceptionnellement, vous ne trouverez ici que de la ! théorie. Si malgré tout, vous tenez à vérifier que votre ! microprocesseur puisse calculer durant 10^24 siècles sans ! bugger une seule fois, libre à vous de tenter de mettre ! en application les explications qui suivent. ! Je nierais avoir été responsable de l'indisponibilité des ! ressources dont disposait votre ordinateur. ! Sur ce, bonne lecture. I. Algorithmes non déterminites : _________________________________ Souvent les programmes, pour résoudre des problèmes combinatoires, peuvent s'écrirent simplement de manière non déterministe, en utilisant une fonction à valeurs multiples De tels programmes, bien qu'ils ne peuvent pas s'executer sur des calculateurs conventionnels, peuvent êtres traduit mécaniquement en programmes traditionnels utilisant le back-tracking. Typiquement, le Back-tracking résout un problème par l'énumération exhaustive de l'ensemble des solutions possibles. Si, à un moment donné, la tentative de solution ou une solution partielle est trouvée inconstante avec le problème posé, le programme "backtracke" : remet les variables à la valeur qu'elles avaient juste avant l'essai infructueux et essaie une autre alternative au même niveau. Quand toutes les alternatives à un même niveau ont été essayées, le programme remonte à un niveau supérieur pour essayer les autres alternatives. Les algorithmes non déterministes ressemblent aux autres algorithmes exceptés en deux points. 1) L'utilisation d'une fonction à valeurs multiples. Choix (X) dont les valeurs sont les entiers positifs inférieurs ou égaux à X. 2) Tous les points de terminaison sont étiquetés par succès ou échec. II. Passage d'un algorithme non déterministe à un aglorithme déterministe : ___________________________________________________________________________ [ BEGIN ] Le but est de transformer un algorithme non déterministes S par une suite |S+ de transformations en un algorithme |-- déterministe. |S- S+ correspond à la partie "descente" et S- à la partie "retour en arrière". notation: -T sera une variable auxiliaire -M sera une pile -W sera la pile d'écriture -R sera la pile de lecture -f sera une expression quelconque -p sera une expression booleenne Toute les branches de l'organigramme non déterministe seront étiquettées par des lettres. 1) S+ { | A v [Empiler X dans M] | [X <- f] | B v S { | A v [X <- f] ===============|> | B v S- { | A' v [Depiler M vers X] | B' Avant d'affecter une nouvelle valeur à X, l'ancienne valeur est stockée dans la pile M afin de pouvoir la récupérer lors du retour en arrière. 2) S+ { | A v ----------- oui-| Test P |-non | ----------- | v B v C S { | A v - -------- oui-| Test P |-non =============|> | ---------- | v B v C S- { \B' C'/ \ / \ / \ / \ / --- | | v A' Le branchement ne causant pas de perte d'information, rien n'est prévu pour le retour. 3) S+ { | A v [Empiler f dans W] | B v S { | A v [Ecrire f] =================|> | B v S- { | B' v [Depiler W] | A' v Toutes les écritures sont empilées pour pouvoir être imprimées si un succès est atteint. 4) S+ { | A v --------- |R vide |-non------ --------- | | | oui [Depiler A vers X] | | [Lire X] | | | -------------->| | v B S { | A v [Lire X] =================|> | v B S- { | B' v [Dépiler X dans R] | A' v Parce que la lecture est irréversible, une pile R, initialement vide, est utilisée pour empiler toutes les lectures sur lesquelles on effectuera éventuellement un retour. 5) S+ { Depart | A v S { Depart | A =================|> v S- { | A' v Stop Toutes les solutions possibles ont été passées en revuen l'algorithme déterministe s'arrête. 6) S+ { | A | | S { | A | v ==================|> | [Echec] | | | S- { | | | | A' v Un échec déclenche toujours le retour. 7) S+ { | A v [Ecrire W sans] [ le détruire ] | ---------------- |Un seul calcul|-oui-- | suffit-il | | ---------------- [Stop] | non | S { | A | v ==================|> | [Succès] | | | S- { | | | | A' v En atteignant un succès, toutes les écritures accumuulées sont imprimées. Si toutes les solutions du problème sont désirées, on effectuera un retour. 8) S+ { | A | B v v [Empiler 0] [Empiler 1] [ dans M ] [ dans M ] | | ---------> <------ | C v S { \A B/ \ / \ / \ / - =================|> | | C v S- { | C' v [Depiler M vers T} | v ------- non-| T=0 |-oui | ------- | v A' v B' Au point ou deux chemins se rencontrent, on doit repérer quel chemin a été pris. 9) S+ { | A v [Empiler X dans M] | [X<-1] |<--------- -------- | | X<=f |-non------ -------- | | | | | oui | | | B | | v | | | | | | S { | A | | v =================|> | | [X<-Choix(f)] | | | B | | v | | | | | | S- { | B' | | v | | [X<-X+1] | | | | | ----------- | | -------------- | v [Depiler M vers X] | A' v On sauve la variable X dans la pile M et on attribue la valeur 1 à X. Après que toutes les possibilités (pour chaque valeur particulière de choix (f)) aient été essayées, la valeur immédiatement plus grande est essayée. Quand toutes les valeurs ont été essayées, la valeur initiale de X est remise et le retour continue. 1a) S+ { | A v [X<-f(x)] | B v S { | A v [X<-f(X)] ===================|> | v B S- { | B' [X<-f(X)] | A' v Ce n'est pas la peine d'empiler X si f a un inverse facilement calculable. exemple: x <- x+1 inverse x <- x-1 x <- vrai inverse x <- faux 8a) S+ { \A B/ \ / \ / \ / - | | C v S { \A B/ \ / \ / \ / - ==================|> | | C (Où P est toujours v vrai sur A et faux sur B.) S- { | C' ------- oui-| P! |-non | ------- | v A' v B' Très souvent, lorsque deux chemins se joignent, on peut savoir lequel a été pris en regardant les variables du programme. [ END ] This is the end. Vous avez désormais de quoi vous prendre la tête quelques soirées. Pour envoyer des dons, une petite pièce, un chèque ou les cordonnées bancaires d'un compte bien rempli en suisse, veuillez adressez vos offres à l'adresse suivante : disk-lexic@caramail.com