Simulation par forme

Graphes

Un graphe orienté G = (S, A) est défini par un ensemble de sommets S et un ensemble d’arcs A ⊆ S ×S. Les ensembles S et A sont respectivement notés V (G) et E(G). Dans le reste de ce manuscrit, le terme “graphe” sera régulièrement utilisé pour décrire un graphe orienté. Exemple 12. Soient S = {a,b,c} un ensemble de sommets et A = {(a,b),(b,c),(c,b)} un ensemble d’arcs. Le graphe orienté G qui vérifie V (G) = S et E(G) = A est représenté en figure 1.1. L’arité entrante d’un sommet s dans un graphe G = (S, A) est définie par le nombre d’arêtes uniques (s 0 ,s) dans A. L’arité sortante d’un sommet s dans un graphe G = (S, A) est définie par le nombre d’arêtes uniques (s,s 0 ) dans A. L’arité d’un sommet est la somme de son arité entrante et de son arité sortante. Pour G = (S, A) et G 0 = (S 0 , A 0 ) deux graphes, le graphe G 0 inclut le graphe G’, noté G ⊆ G 0 , si et seulement si S ⊆ S 0 et A ⊆ A 0 . On appelle chemin toute séquence de nœuds (s1,s2,…) telle que (si ,si+1) ∈ A pour tout i. Un cycle est un chemin (s1,s2,…sk) qui vérifie s1 = sk. Un graphe G est acyclique s’il ne dispose d’aucun cycle. Dans un graphe acyclique, les sommets d’arité sortante 0 sont appelés les puits, et les sommets d’arité entrante 0 sont appelés les sources. Pour G = (S, A) un graphe, G est un arbre si et seulement si pour toute paire de sommets (s,s 0 ), il n’existe au plus qu’un seul chemin possible pour aller de s à s 0 dans G. Les puits d’un arbre sont appelés les feuilles, et les sources sont appelées les racines. Un graphe étiqueté est défini par un ensemble de sommets S, un ensemble d’arêtes A et un ensemble d’étiquettes E, tels que A ⊆ S ×E ×S. Une arête (s,e,s 0 ) signifie que l’étiquette e décore l’arête allant de s vers s 0 . Un graphe G = (S, A) est fortement connexe si et seulement si, pour toute paire s,s 0 de sommets distincts, il existe un chemin de s vers s 0 et un chemin de s 0 vers s. De façon similaire, une composante fortement connexe de G est un ensemble maximal S 0 ⊆ S tel que pour toute paire s,s 0 de sommets distincts dans S 0 , il existe un chemin de s vers s 0 et de s 0 vers s parmi les sommets S 0 . On nomme composante fortement connexe terminale d’un graphe toute composante fortement connexe dont il est impossible de sortir. Formellement, pour G = (S, A) et S 0 un sous-ensemble de S, S 0 décrit une composante fortement connexe terminale si et seulement si S 0 est une composante fortement connexe et si pour tout s,s 0 ∈ S, si s ∈ S 0 et (s,s 0 ) ∈ A, alors s 0 ∈ S 0 .

Fonctions booléennes

L’ensemble des nombres booléens est noté B et défini par B = {0,1}. Une fonction booléenne est une fonction définie de B A → B, pour A un certain ensemble. Pour f : B A → B, l’arité de f est le cardinal de A. Une porte booléenne est une fonction parmi ¬, ∨ et ∧. La porte ¬, aussi appelée “non logique”, est d’arité un et est définie par ¬0 = 1 et ¬1 = 0. Les portes ∨ et ∧ sont d’arité deux : la porte ∨, aussi appelée “ou logique”, vaut 1 si et seulement si au moins une de ses deux entrées est évaluée à 1. la porte ∧, aussi appelée “et logique”, vaut 1 si et seulement si ses deux entrées sont évaluées à 1. Les portes booléennes sont combinées pour former des graphes qui permettent le calcul de fonctions booléennes. Ces graphes sont acycliques, et ne possèdent qu’un seul puit. Les sources d’un tel graphe représentent les variables de la fonction booléenne, et chaque autre sommet est associé à une porte booléenne qui calcule sa valeur selon la valeur des nœuds incidents. Il est important que l’arité entrante de chaque sommet qui dispose d’une porte corresponde à l’arité de la porte : arité entrante 1 pour une porte non, et arité 2 pour une porte ou, ou et. Pour exécuter la fonction booléenne d’un tel graphe, on note la valeur de chaque variable, et on remonte le long des arcs du graphe jusqu’au puit du réseau, en exécutant les portes rencontrées sur le chemin. La valeur trouvée au puit du réseau correspond à l’évaluation de la fonction encodée par le réseau. Dans le cas général, ces objets sont appelés circuits booléens. Exemple 13. Soit S = {a,b,c,p1,p2} un ensemble de nœuds, et les arêtes A = {(a,p1), (b,p1),(c,p2),(p1,p2)}. On associe à p1 la porte logique ou, et à p2 la porte logique et. Le circuit booléen C associé encode une fonction booléenne f d’arité 3 dont la table de vérité est a b c f 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 Le graphe du circuit défini dans l’exemple 13 est représenté en figure 1.2. Lorsqu’un tel graphe possède la propriété supplémentaire d’être un arbre, on l’appelle une formule booléenne. La structure d’une formule booléenne permet de la représenter sous la forme d’une formule mathématique, en représentant la structure de l’arbre grâce à des parenthèses. Exemple 14. On considère le circuit booléen C décrit dans l’exemple 13. Le graphe du circuit C possède la propriété d’être un arbre, et est donc également une formule booléenne. Son écriture sous forme de formule est (a ∨b)∧c.

Machines de Turing 

Les machines de Turing sont un modèle de calcul que l’on peut représenter comme un robot qui avance et recule sur un ruban infini d’information. Le robot dispose d’une tête de lecture et écriture, d’un état et d’une table de transition. Cette table contient une entrée pour chaque état et chaque valeur de lecture possible; pour chacune de ces paires, cette table retourne une valeur à écrire, un déplacement optionnel et un nouvel état pour la machine de Turing. Mettre à jour la machine repose sur la lecture de cette table et l’application de son résultat. Ce calcul peut ne jamais s’arrêter; cependant on définit souvent des états spéciaux, dit finaux, qui une fois établis vérouillent la machine dans une position et préviennent toute autre modification. C’est une convention pour signifier la fin du calcul d’une machine de Turing. On fait la distinction entre les machines de Turing déterministes et les machines de Turing non déterministes sur le critère qu’une machine de Turing déterminisite dispose toujours d’un et un seul choix en toute circonstance. Une machine de Turing non déterminisite peut au contraire disposer d’une table de transition qui définit au moins deux possibles résultats pour les mêmes circonstances. 1.6.1 Cas déterministe Formellement, une machine de Turing déterministe se définit comme un quintuplet (S,Λ,s0,δ,F), où S est un ensemble fini d’états, Λ est l’alphabet des symboles du ruban, s0 est un état de S dit initial, δ : S ×Λ → S ×Λ×{−1,0,+1} est la fonction qui encode la table de transition, et F décrit le sous-ensemble des états de la machine dits finaux. Le ruban de la machine de Turing est représenté par un vecteur bi-infini R ∈ Λ Z . Pour mettre à jour une telle machine T = (S,Λ,s0,δ,F) depuis un état s sur le ruban R ∈ Λ Z , et telle que la position de la tête soit actuellement un certain z ∈ Z, nous calculons (s 0 , y,p) = δ(s,Rz ). Il résulte de cette mise à jour que la machine T est maintenant à l’état s 0 et sa tête à la position z + p, et le nouveau ruban R 0 est défini en tout point égal à R excepté R 0 z = y. Dans le cas particulier où l’état actuel de la machine est dans F, la machine n’est pas mise à jour. 

 Cas non déterminisite

Une machine de Turing non déterministe est un quintuplet (S,Λ,s0,∆,F), où S,Λ,s0 et F sont définis de la même façon que pour une machine déterministe. Ici, ∆ est défini comme un sous-ensemble de S ×Λ×S ×Λ×{−1,0,+1}, tel que pour toute paire (s,x), il existe au moins un triplet (s 0 , y,p) tel que (s,x,s 0 , y,p) ∈ ∆. Ainsi, pour tout quintuplet (s,x,s 0 , y,p) ∈ ∆, la machine a la possibilité de passer de l’état s à l’état s 0 lorsqu’elle lit la valeur x, en entraînant l’écriture de l’état y et le déplacement p. Mettre à jour une machine de Turing non déterministe à partir d’une valeur de lecture x et d’un état s repose sur la sélection d’un quintuplet (s,x,s 0 , y,p) ∈ ∆. Lorsque plusieurs tels quintuplets existent, le calcul est non déterministe; plutôt que de disposer d’une exécution possible, la machine possède plusieurs possibilités. On considèrera en général chaque possibilité comme dessinant un arbre de configurations dont la racine est la configuration initiale de la machine, telle que chaque nœud de l’arbre dispose d’autant de fils qu’il y a de possibles mises à jour de la configuration qui correspond au nœud. Ainsi, les feuilles de l’arbre correspondent aux différentes façons dont la machine peut terminer son calcul à partir de cette configuration initiale.