Les correcteurs attendent des réponses précises et concises aux questions posées. On demande à plusieurs reprises de proposer des algorithmes. On exprimera ces algorithmes avec un point de vue de haut niveau, sans décrire leur implantation effective ni les structures de données utilisées (cf l'algorithme proposé dans l'énoncé de la question 1.5). La complexité d'un algorithme doit toujours être comprise comme le nombre d'opérations élémentaires (calculs, comparaisons, ...) nécessaires à son exécution.
1 Algorithmique des graphes
Un multi-graphe orienté fini (graphe dans la suite) est un couple ( ) où est un ensemble fini dont les éléments sont appelés les nœuds et où est un ensemble fini dont les éléments sont appelés les arcs. À chaque arc est associé un nœud initial et un nœud final . Soit un ensemble, un graphe valué dans est un graphe ( ) muni d'une application . Les éléments de sont appelés les étiquettes.
Graphiquement, un nœud est représenté par un point, un arc par une flèche orientée du point vers le point , éventuellement surmontée de l'étiquette . Il peut y avoir plusieurs flèches entre deux mêmes nœuds, ainsi que des flèches bouclant sur un nœud.
Un chemin (fini) du graphe est une suite finie d'arcs dont les extrémités sont consécutives : , et . Le chemin commence en et se termine en . On dit également que le chemin va de à . On utilise la notation condensée pour indiquer qu'il existe un chemin allant du nœud au nœud . La longueur du chemin, notée , est égale au nombre d'arcs. Par convention, on considère qu'il existe un chemin de longueur nulle allant de à , pour tout nœud . Un circuit est un chemin de longueur non nulle qui commence et se termine en le même nœud.
Soit un graphe et un couple de nœuds distingués . Le graphe émondé correspondant est le graphe ( ) défini comme suit :
Question 1.1.
Proposer et justifier un algorithme prenant en entrée un graphe et un couple de nœuds distingués et retournant en sortie le graphe émondé. On réduira autant que possible la complexité, et on évaluera son ordre de grandeur.
Soit un graphe valué dans les réels par . On suppose que l'on a ; pour , on suppose naturellement que et . Il y a donc au plus un arc pour chaque couple de nœuds. On pose et (où est le cardinal de l'ensemble ). À un chemin , on associe son poids . Par convention, un chemin de longueur nulle a pour poids 0 .
On définit , matrice à valeurs dans , de la façon suivante (avec , pour tout ) :
Le coefficient est donc égal au poids maximal d'un chemin de longueur 0 ou 1 de à ( s'il n'existe pas de tel chemin).
Question 1.2.
a) Dans le graphe , montrer qu'il existe un circuit de poids strictement positif si et seulement s'il existe un circuit de poids strictement positif et de longueur au plus .
b) On définit pour (avec , pour tout ) :
où la dernière égalité provient de ce que .
Montrer qu'il existe un circuit c tel que si et seulement 'il existe et tels que .
c) En déduire qu'il existe un algorithme de complexité prenant en entrée le graphe , et répondant 'oui' s'il existe un circuit de poids strictement positif, 'non' dans le cas contraire.
Question 1.3.
Soit et deux matrices carrées de même dimension et à coefficients dans . On note la matrice définie par
On remarque que l'équation (1) peut aussi s'écrire sous la forme matricielle : .
Vérifier que l'opération est associative. Montrer que, grâce à cette propriété, on peut modifier l'algorithme de la question précédente de façon à obtenir un algorithme de complexité .
Question 1.4.
On ordonne les nœuds de de façon à identifier et . On définit pour ,
Montrer qu'il existe un circuit c tel que si et seulement s'il existe tels que .
En déduire qu'il existe un algorithme de complexité prenant en entrée le graphe , et répondant 'oui' s'il existe un circuit de poids strictement positif, 'non' dans le cas contraire.
Question 1.5.
On définit l'algorithme suivant, prenant en entrée le graphe , et retournant 'oui' s'il existe un circuit de poids strictement positif, 'non' dans le cas contraire.
Détection-Circuit-Strictement-Positif ( $N, E, \varphi$ )
pour tout $u \in N$ faire
valeur $[u] \leftarrow 0$
pour $i \leftarrow 1$ à $\operatorname{Card}(N)$ faire
pour tout $(u, v) \in E$ faire
Actualisation $(u, v, \varphi)$
si $\exists(u, v) \in E$, valeur $[v]<\operatorname{valeur}[u]+\varphi(u, v)$
alors retourner 'oui'
sinon retourner 'non'
Actualisation
si valeur valeur
alors valeur
Justifier la validité de cet algorithme et montrer que sa complexité est .
2 Transducteurs
Étant donnés deux ensembles et et une fonction , on note le domaine de , c'est-à-dire le sous-ensemble de sur lequel est définie. Un alphabet est toujours supposé fini et non vide. Étant donné un alphabet , l'ensemble des mots finis sur muni de l'opération de concaténation est noté ; l'élément neutre de cette opération, le mot vide, est noté . La longueur d'un mot est notée .
Un transducteur (fini) est un sextuplet , où et sont deux alphabets, est un ensemble fini, et où et sont des fonctions. Les éléments de sont appelés les états. Un état est dit initial si et final si . On appelle ensemble des transitions, l'ensemble défini .
On associe au transducteur le graphe ( ) valué par . Si , on a et . Graphiquement, on représente un transducteur à l'aide de son graphe associé auquel on ajoute, pour chaque nœud initial , une flèche entrante étiquetée , et, pour chaque nœud final , une flèche sortante étiquetée .
Le transducteur hérite de la terminologie et des notations du graphe associé. On définit ainsi la notion de chemin dans le transducteur. On représente le chemin sous la forme
On écrira également sous la forme condensée , avec et . On dira que le mot est l'étiquette (mot) d'entrée du chemin et que le mot est l'étiquette (mot) de sortie du chemin. Par convention, pour un chemin de longueur nulle, l'étiquette d'entrée est et celle de sortie est . Un chemin est dit réussi s'il mène d'un état initial à un état final.
Étant donnés deux alphabets et , une transduction est une application de dans , l'ensemble des parties de . A un transducteur est associée une transduction qui est dite réalisée par et qui est définie comme suit :
En particulier, s'il n'existe aucun chemin réussi de mot d'entrée , on a .
En résumé, un transducteur peut être vu comme une machine prenant en entrée un mot de et retournant en sortie un langage de .
Exemple. On considère le transducteur avec , et avec , et non défini pour les autres triplets. Ce transducteur est représenté sur la figure 1 (lorsqu'il y a plusieurs transitions pour un même couple d'états, on représente une seule flèche avec plusieurs étiquettes).
Fig. 1: Le transducteur .
À un mot est associé l'ensemble des mots obtenus en remplaçant certaines des occurrences de par et en ajoutant à la fin des mots. Par exemple, on a .
Question 2.1.
Construire un transducteur sur les alphabets et réalisant la transduction suivante (ici, comme dans la suite, on identifie le mot et le singleton ) :
Question 2.2.
On considère la transduction qui à un mot associe l'ensemble de ses facteurs (soit un mot , un facteur de est soit le mot vide, soit un mot de la forme avec ). Construire un transducteur réalisant .
Question 2.3.
On associe à un entier non nul sa représentation binaire définie de façon unique comme suit :
L'objectif est d'obtenir un transducteur calculant la représentation binaire de la somme de deux entiers. Soit et deux entiers non nuls avec et . Si et sont de longueurs différentes, supposons par exemple que , alors on pose . On définit le mot sur l'alphabet comme la somme chiffre à chiffre de et de , c'est-à-dire avec .
Proposer un transducteur à deux états sur les alphabets et , prenant en entrée le mot miroir de et retournant en sortie le mot miroir (on appelle mot miroir du mot , le mot ). En déduire un transducteur prenant en entrée et retournant en sortie .
Une transduction , vérifiant pour tout dans , peut être vue comme une fonction . Par exemple, la transduction de la question 2.1 est une fonction, mais celle de la question 2.2 n'en est pas une. Un transducteur est fonctionnel si est une fonction.
Question 2.4.
On a représenté ci-dessous un transducteur sur les alphabets et . Établir, en justifiant la réponse, si ce transducteur est fonctionnel ou non. Déterminer la transduction associée.
Question 2.5.
Construire un transducteur tel que pour tout mot d'entrée u. Établir s'il est encore possible de construire un tel transducteur si l'on impose que l'alphabet des mots de sortie ne contienne qu'une lettre.
3 Transducteurs séquentiels
Dans un transducteur, un état est dit accessible s'il existe un chemin menant d'un état initial à ; il est dit co-accessible s'il existe un chemin menant de à un état final. Un transducteur dont tous les états sont à la fois accessibles et co-accessibles est dit émondé. Partant d'un transducteur, on peut, à l'aide d'un algorithme semblable à celui de la question 1.1, obtenir un transducteur émondé réalisant la même transduction. Dans toute la suite, on ne considère que des transducteurs émondés.
On peut aisément transformer un transducteur en un autre réalisant la même transduction et tel que, pour tout état initial , l'étiquette soit le mot vide. Dans toute la suite, on suppose que les transducteurs vérifient cette dernière propriété.
Un transducteur est dit séquentiel si :
est un singleton;
.
La définition d'un transducteur séquentiel est à rapprocher de celle d'un automate déterministe. Il est immédiat qu'un transducteur séquentiel est fonctionnel. Une fonction est dite séquentielle si elle est réalisable par un transducteur séquentiel. Étant donné un transducteur fonctionnel mais non séquentiel, un problème important est de déterminer s'il existe un autre transducteur, séquentiel celui-ci, réalisant la même fonction.
Note culturelle: les transducteurs séquentiels peuvent être implantés de façon effective ce qui les rend très importants dans la pratique. Ils interviennent notamment en compilation, en arithmétique des ordinateurs ou encore dans l'étude du génome.
Pour , on note le plus long préfixe (facteur gauche) commun de et de . On définit, ,
La fonction est dite à variation bornée si (on utilise la même notation . et
Question 3.1.
Montrer que .. Montrer que la fonction de la question 2.1 n'est pas à variation bornée.
Soit un transducteur fini. On dit que deux états et sont jumelés si pour toute paire de chemins
où et sont des états initiaux, les étiquettes de sortie vérifient la propriété suivante : soit , soit il existe tel que ( ) ou ( ). Cette propriété peut s'exprimer de la façon équivalente suivante :
(i) ;
(ii) si , alors les mots infinis ( ) et ( ) sont égaux.
Un transducteur vérifie la propriété de jumelage si tous ses couples d'états sont jumelés.
Question 3.2.
Soit un transducteur sur et , où est un alphabet à une seule lettre. On note , où est l'ensemble des états du transducteur. Proposer et justifier un algorithme de complexité prenant en entrée , et retournant 'oui' si vérifie la propriété de jumelage, 'non' dans le cas contraire. Indication : on pourra construire un graphe valué d'ensemble de nœuds et utiliser les algorithmes de la partie 1 .
On se replace dans le cadre d'alphabets de cardinalité finie quelconque. On va démontrer, en plusieurs étapes, le théorème qui suit.
Théorème de séquentialité (Choffrut, 1978). Soit une fonction de dans réalisée par un transducteur . Les propriétés suivantes sont équivalentes :
la fonction est séquentielle;
la fonction est à variation bornée;
le transducteur vérifie la propriété de jumelage.
Question 3.3.
Soit une fonction séquentielle de dans . Montrer que est à variation bornée.
On en déduit que la fonction de la question 2.1 n'est pas séquentielle.
Question 3.4.
Les transducteurs obtenus en réponse à la question 2.3 sont notés respectivement pour celui opérant sur les mots miroirs et pour l'autre. Déterminer, en justifiant la réponse, si les fonctions et sont séquentielles ou non.
Question 3.5.
On considère quatre mots et dans . On suppose qu'il existe tel que ou . Montrer que l'on .
Question 3.6.
Soit un transducteur vérifiant la propriété de jumelage. On note la longueur maximale de l'étiquette de sortie d'un arc, c'est-à-dire . On pose . Pour tout couple de chemins
où et sont des états initiaux, montrer que .
Question 3.7.
Montrer l'équivalence entre les propriétés 2 et 3 du théorème de séquentialité.
Soit et des mots tels que , alors par définition . Soit une partie non vide de , on définit préfixe de et on définit comme l'ensemble des mots de longueur maximale dans . On montre aisément que est réduit à un seul élément et que pour tout , il existe tel que .
Soit un transducteur. On va définir ci-dessous à l'aide d'un procédé itératif éventuellement infini le quintuplet . Cette construction se comprend mieux à l'aide de la figure 2 , ou encore en l'appliquant directement à la résolution de la question 3.8. L'ensemble est inclus dans l'ensemble des parties finies non vides de , et et sont des fonctions.
On commence par définir . On pose et .
Soit un élément déjà construit de et soit . S'il existe et , tels que , alors on définit et comme suit. On pose pour ,
Soit et . On définit
On a alors et .
Fig. 2: Une partie d'un transducteur et du quintuplet associé.
Question 3.8.
En utilisant la construction décrite ci-dessus, obtenir un transducteur séquentiel réalisant la même fonction que le transducteur de la question 2.4.
Question 3.9.
Soit un transducteur et soit le quintuplet associé. Soit . Montrer que pour tout , il existe tel que . On suppose de plus que vérifie la propriété de jumelage. Montrer que pour tout et tout , on a (où et sont définis comme à la question 3.6). En déduire que l'ensemble est fini.
Question 3.10.
Soit un transducteur fonctionnel vérifiant la propriété de jumelage. Construire un transducteur séquentiel réalisant la fonction . Proposer et justifier un algorithme prenant en entrée un transducteur , retournant 'non' si n'est pas une fonction séquentielle et retournant dans le cas contraire un transducteur séquentiel réalisant .
On a ainsi démontré, à l'aide des questions 3.3 à 3.10 , le théorème de séquentialité. Ce faisant on a obtenu un algorithme permettant de 'séquentialiser' un transducteur (lorsque cela est possible). La complexité de cet algorithme est exponentielle. En effet, lorsque tous les mots de sortie sont égaux au mot vide, cet algorithme se réduit à l'algorithme classique de déterminisation d'un automate dont la complexité est exponentielle.
Si on ne cherche pas à séquentialiser effectivement le transducteur mais seulement à décider de la séquentialité de alors ceci peut être réalisé à l'aide d'un algorithme de complexité polynômiale. Dans le cas où l'alphabet des mots de sortie ne contient qu'une lettre, l'algorithme de la question 3.2 permet de décider de la séquentialité lorsqu'il est appliqué à un transducteur fonctionnel. D'autre part, il existe un algorithme basé sur la même construction et de même complexité permettant de tester la fonctionnalité. Lorsque les alphabets sont de cardinalité quelconque, il existe encore des algorithmes polynômiaux permettant de décider de la fonctionnalité et de la séquentialité.
ENS Option Informatique MP 2000 - Version Web LaTeX | WikiPrépa | WikiPrépa
