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 ( N, E ) où N est un ensemble fini dont les éléments sont appelés les nœuds et où E est un ensemble fini dont les éléments sont appelés les arcs. À chaque arc e ∈ E est associé un nœud initial i(e) ∈ N et un nœud final f(e) ∈ N. Soit K un ensemble, un graphe valué dans K est un graphe ( N, E ) muni d'une application φ : E → K. Les éléments de K sont appelés les étiquettes.
Graphiquement, un nœud est représenté par un point, un arc e par une flèche orientée du point i(e) vers le point f(e), éventuellement surmontée de l'étiquette φ(e). 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) p du graphe est une suite finie d'arcs dont les extrémités sont consécutives : p = (e_1, e_2, …, e_k), e_i ∈ E, et f(e_i) = i(e_(i + 1)). Le chemin p commence en i(e_1) et se termine en f(e_k). On dit également que le chemin va de i(e_1) à f(e_k). On utilise la notation condensée x → y pour indiquer qu'il existe un chemin allant du nœud x au nœud y. La longueur du chemin, notée |p|, est égale au nombre d'arcs. Par convention, on considère qu'il existe un chemin de longueur nulle allant de u à u, pour tout nœud u. Un circuit est un chemin de longueur non nulle qui commence et se termine en le même nœud.
Soit un graphe (N, E) et un couple de nœuds distingués (i, j). Le graphe émondé correspondant est le graphe ( N^′, E^′ ) défini comme suit :
N^′ = {u ∈ N : i → u, u → j} et E^′ = {e ∈ E : i(e) ∈ N^′, f(e) ∈ N^′}.
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 G = (N, E) valué dans les réels par φ : E → ℝ. On suppose que l'on a E ⊂ N × N; pour e = (u, v) ∈ E, on suppose naturellement que i(e) = u et f(e) = v. Il y a donc au plus un arc pour chaque couple de nœuds. On pose n = Card(N) et m = Card(E) (où Card(S) est le cardinal de l'ensemble S ). À un chemin p = (e_1, …, e_k), on associe son poids w(p) = φ(e_1) + ⋯ + φ(e_k). Par convention, un chemin de longueur nulle a pour poids 0 .
On définit W = (W_(ij))_(i, j ∈ N), matrice à valeurs dans ℝ ∪ { − ∞}, de la façon suivante (avec max(a, − ∞) = max(− ∞, a) = a, pour tout a ∈ ℝ ∪ { − ∞} ) :
W_(ij)^((0)) = {0, si i = j; − ∞, sinon, W_(ij)^((1)) = {φ((i, j)), si (i, j) ∈ E; − ∞, sinon, W_(ij) = max(W_(ij)^((0)), W_(ij)^((1))).
Le coefficient W_(ij) est donc égal au poids maximal d'un chemin de longueur 0 ou 1 de i à j ( − ∞ s'il n'existe pas de tel chemin).
Question 1.2.
a) Dans le graphe G, 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 n.
b) On définit pour i, j ∈ N, k ≥ 2 (avec a + (− ∞) = (− ∞) + a = − ∞, pour tout a ∈ ℝ ∪ { − ∞} ) :
où la dernière égalité provient de ce que ∀j, W_(jj) ≥ 0.
Montrer qu'il existe un circuit c tel que w(c) > 0 si et seulement s 'il existe i ∈ N et k ∈ {1, …, n} tels que U_(ii)^((k)) > 0.
c) En déduire qu'il existe un algorithme de complexité O(n^4) prenant en entrée le graphe G, et répondant 'oui' s'il existe un circuit de poids strictement positif, 'non' dans le cas contraire.
Question 1.3.
Soit P et Q deux matrices carrées de même dimension et à coefficients dans ℝ ∪ { − ∞}. On note P ⊗ Q la matrice définie par
(P ⊗ Q)_(ij) = max_l(P_(il) + Q_(lj))
On remarque que l'équation (1) peut aussi s'écrire sous la forme matricielle : U^((k)) = U^((k − 1)) ⊗ W.
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é O(n^3 logn).
Question 1.4.
On ordonne les nœuds de N de façon à identifier N et {1, …, n}. On définit pour i, j, k ∈ N,
Montrer qu'il existe un circuit c tel que w(c) > 0 si et seulement s'il existe i ∈ N, k ∈ N ∪ {0} tels que V_(ii)^((k)) > 0.
En déduire qu'il existe un algorithme de complexité O(n^3) prenant en entrée le graphe G, 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 G, 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'
Justifier la validité de cet algorithme et montrer que sa complexité est O(nm).
2 Transducteurs
Étant donnés deux ensembles E et F et une fonction f : E → F, on note dom(f) le domaine de f, c'est-à-dire le sous-ensemble de E sur lequel f est définie. Un alphabet est toujours supposé fini et non vide. Étant donné un alphabet A, l'ensemble des mots finis sur A muni de l'opération de concaténation est noté A^∗; l'élément neutre de cette opération, le mot vide, est noté 1_(A^∗). La longueur d'un mot w est notée |w|.
Un transducteur (fini) T est un sextuplet T = (Q, A, B, T, I, F), où A et B sont deux alphabets, Q est un ensemble fini, et où I : Q → B^∗, F : Q → B^∗ et T : (Q × A × Q) → B^∗ sont des fonctions. Les éléments de Q sont appelés les états. Un état q est dit initial si q ∈ dom(I) et final si q ∈ dom(F). On appelle ensemble des transitions, l'ensemble défini parE_T = {(p, a, u, q) ∈ (Q × A × B^∗ × Q) : (p, a, q) ∈ dom(T), T(p, a, q) = u}.
On associe au transducteur T le graphe ( Q, E_T ) valué par φ : E_T → A × B^∗. Si e = (p, u, v, q) ∈ E_T, on a i(e) = p, f(e) = q et φ(e) = (u, v). Graphiquement, on représente un transducteur à l'aide de son graphe associé auquel on ajoute, pour chaque nœud initial q, une flèche entrante étiquetée I(q), et, pour chaque nœud final q, une flèche sortante étiquetée F(q).
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 p = (q_0, u_1, v_1, q_1), (q_1, u_2, v_2, q_2), …, (q_(n − 1), u_n, v_n, q_n) sous la forme
p = q_0→−^(u_1|v_1)q_1→−^(u_2|v_2)q_2 ⟶ ⋯ ⟶ q_(n − 1)→−^(u_n|v_n)q_n.
On écrira également p sous la forme condensée q_0→−^(u|v)q_n, avec u = u_1 u_2⋯u_n ∈ A^∗ et v = v_1 v_2⋯v_n ∈ B^∗. On dira que le mot u est l'étiquette (mot) d'entrée du chemin et que le mot v est l'étiquette (mot) de sortie du chemin. Par convention, pour un chemin de longueur nulle, l'étiquette d'entrée est 1_(A^∗) et celle de sortie est 1_(B^∗). Un chemin est dit réussi s'il mène d'un état initial à un état final.
Étant donnés deux alphabets A et B, une transduction est une application de A^∗ dans P(B^∗), l'ensemble des parties de B^∗. A un transducteur T = (Q, A, B, T, I, F) est associée une transduction f_T : A^∗ → P(B^∗) qui est dite réalisée par T et qui est définie comme suit :
f_T(u) est l'ensemble des I(p)vF(q) tels qu 'il existe un chemin réussi p→−^(u|v)q.
En particulier, s'il n'existe aucun chemin réussi de mot d'entrée u, on a f_T(u) = ∅.
En résumé, un transducteur peut être vu comme une machine prenant en entrée un mot de A^∗ et retournant en sortie un langage de B^∗.
Exemple. On considère le transducteur T = ({1, 2}, {a, b}, {a, b, c}, T, I, F) avec dom(I) = {1}, dom(F) = {1}, I(1) = 1_(B^∗), F(1) = c, et avec T(1, a, 1) = a, T(1, a, 2) = c^3, T(1, b, 1) = b, T(2, b, 1) = 1_(B^∗), et T 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 T.
À un mot u est associé l'ensemble f_T(u) des mots obtenus en remplaçant certaines des occurrences de ab par c^3 et en ajoutant c à la fin des mots. Par exemple, on a f_T(baba^3 b^2) = {baba^3 b^2 c, baba^2 c^3 bc, bc^3 a^3 b^2 c, bc^3 a^2 c^3 bc}.
Question 2.1.
Construire un transducteur sur les alphabets A = {a} et B = {b, c} réalisant la transduction suivante (ici, comme dans la suite, on identifie le mot w et le singleton {w} ) :
f(1_(A^∗)) = 1_(B^∗) et f(a^n) = {b^n, si n pair; c^n, si n impair .
Question 2.2.
On considère la transduction f : A^∗ → P(A^∗) qui à un mot associe l'ensemble de ses facteurs (soit un mot w = w_1 w_2⋯w_n, w_i ∈ A, un facteur de w est soit le mot vide, soit un mot de la forme w_i w_(i + 1)⋯w_j avec 1 ≤ i ≤ j ≤ n ). Construire un transducteur réalisant f.
Question 2.3.
On associe à un entier non nul n sa représentation binaire ⟨n⟩ ∈ {0, 1}^∗ définie de façon unique comme suit :
Si n = ∑_(i = 0)^k w_i 2^i, w_i ∈ {0, 1}, w_k = 1, alors ⟨n⟩ = w_k w_(k − 1)⋯w_0
L'objectif est d'obtenir un transducteur calculant la représentation binaire de la somme de deux entiers. Soit n et m deux entiers non nuls avec ⟨n⟩ = u_k⋯u_0 et ⟨m⟩ = v_l⋯v_0. Si ⟨n⟩ et ⟨m⟩ sont de longueurs différentes, supposons par exemple que l < k, alors on pose v_(l + 1) = ⋯ = v_k = 0. On définit le mot w sur l'alphabet {0, 1, 2} comme la somme chiffre à chiffre de u et de v, c'est-à-dire w = w_k⋯w_0 avec w_i = u_i + v_i.
Proposer un transducteur à deux états sur les alphabets {0, 1, 2} et {0, 1}, prenant en entrée le mot miroir de w et retournant en sortie le mot miroir de⟨n + m⟩ (on appelle mot miroir du mot x_1⋯x_k, le mot x_k⋯x_1 ). En déduire un transducteur prenant en entrée w et retournant en sortie ⟨n + m⟩.
Une transduction f : A^∗ → P(B^∗), vérifiant Card(f(u)) ≤ 1 pour tout u dans A^∗, peut être vue comme une fonction f : A^∗ → B^∗. 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 T est fonctionnel si f_T est une fonction.
Question 2.4.
On a représenté ci-dessous un transducteur sur les alphabets A = {a} et B = {b}. É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 T tel que Card(f_T(u)) = |u|^2 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 q est dit accessible s'il existe un chemin menant d'un état initial à q; il est dit co-accessible s'il existe un chemin menant de q à 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 q, l'étiquette I(q) soit le mot vide. Dans toute la suite, on suppose que les transducteurs vérifient cette dernière propriété.
Un transducteur T = (Q, A, B, T, I, F) est dit séquentiel si :
dom(I) est un singleton;
∀p ∈ Q, ∀a ∈ A, Card{q ∈ Q : (p, a, q) ∈ dom(T)} ≤ 1.
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 f : A^∗ → B^∗ 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 u, v ∈ A^∗, on note u ∧ v le plus long préfixe (facteur gauche) commun de u et de v. On définit, ∀u, v ∈ A^∗,
d(u, v) = |u| + |v| − 2|u ∧ v|.
La fonction f : A^∗ → B^∗ est dite à variation bornée si (on utilise la même notation d(.,.)surA^∗ et B^∗)
∀k ≥ 0, ∃K ≥ 0, ∀u, v ∈ dom(f), d(u, v) ≤ k ⟹ d(f(u), f(v)) ≤ K.
Question 3.1.
Montrer que d(.,.)définitunedistancesurA^∗. Montrer que la fonction de la question 2.1 n'est pas à variation bornée.
Soit T = (Q, A, B, T, I, F) un transducteur fini. On dit que deux états p et q sont jumelés si pour toute paire de chemins
i→−^(u_1|v_1)p→−^(u_2|v_2)p et j→−^(u_1|w_1)q→−^(u_2|w_2)q,
où i et j sont des états initiaux, les étiquettes de sortie vérifient la propriété suivante : soit v_2 = w_2 = 1_(B^∗), soit il existe x ∈ B^∗ tel que ( w_1 = v_1 x, xw_2 = v_2 x ) ou ( v_1 = w_1 x, xv_2 = w_2 x ). Cette propriété peut s'exprimer de la façon équivalente suivante :
(i) |v_2| = |w_2|;
(ii) si v_2 ≠ 1_(B^∗), w_2 ≠ 1_(B^∗), alors les mots infinis ( v_1 v_2 v_2 v_2⋯ ) et ( w_1 w_2 w_2 w_2⋯ ) sont égaux.
Un transducteur T vérifie la propriété de jumelage si tous ses couples d'états sont jumelés.
Question 3.2.
Soit T un transducteur sur A et B, où B est un alphabet à une seule lettre. On note n = Card(Q), où Q est l'ensemble des états du transducteur. Proposer et justifier un algorithme de complexité O(n^6) prenant en entrée T, et retournant 'oui' si T vérifie la propriété de jumelage, 'non' dans le cas contraire. Indication : on pourra construire un graphe valué d'ensemble de nœuds Q × Q 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 f une fonction de A^∗ dans B^∗ réalisée par un transducteur T. Les propriétés suivantes sont équivalentes :
la fonction f est séquentielle;
la fonction f est à variation bornée;
le transducteur T vérifie la propriété de jumelage.
Question 3.3.
Soit f une fonction séquentielle de A^∗ dans B^∗. Montrer que f 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 T_1 pour celui opérant sur les mots miroirs et T_2 pour l'autre. Déterminer, en justifiant la réponse, si les fonctions f_(T_1) et f_(T_2) sont séquentielles ou non.
Question 3.5.
On considère quatre mots v_1, v_2, w_1 et w_2 dans A^∗. On suppose qu'il existe x ∈ A^∗ tel que (w_1 = v_1 x, xw_2 = v_2 x) ou (v_1 = w_1 x, xv_2 = w_2 x). Montrer que l'on a, ∀v_3, w_3 ∈ A^∗, d(v_1 v_2 v_3, w_1 w_2 w_3) = d(v_1 v_3, w_1 w_3).
Question 3.6.
Soit T = (Q, A, B, T, I, F) un transducteur vérifiant la propriété de jumelage. On note M la longueur maximale de l'étiquette de sortie d'un arc, c'est-à-dire M = max{|T(p, u, q)| : (p, u, q) ∈ dom(T)}. On pose n = Card(Q). Pour tout couple de chemins
i→−^(u|v)p et j→−^(u|w)q,
où i et j sont des états initiaux, montrer que d(v, w) ≤ 2n^2 M.
Question 3.7.
Montrer l'équivalence entre les propriétés 2 et 3 du théorème de séquentialité.
Soit u, v et w des mots tels que u = vw, alors par définition v^(− 1)u = w. Soit U une partie non vide de B^∗, on définit pr(U) = {v ∈ B^∗ : ∀u ∈ U, v préfixe de u} et on définit ⋀U comme l'ensemble des mots de longueur maximale dans pr(U). On montre aisément que ⋀U est réduit à un seul élément et que pour tout u ∈ U, il existe v ∈ U tel que u ∧ v = ∧ U.
Soit T = (Q, A, B, T, I, F) un transducteur. On va définir ci-dessous à l'aide d'un procédé itératif éventuellement infini le quintuplet T_s = (Q_s, A, B, T_s, I_s). 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 Q_s est inclus dans l'ensemble des parties finies non vides de Q × B^∗, et T_s : (Q_s × A × Q_s) → B^∗ et I_s : Q_s → B^∗ sont des fonctions.
On commence par définir q_0 = {(i, 1_(B^∗)) : i ∈ dom(I)}. On pose q_0 ∈ Q_s, dom(I_s) = {q_0} et I_s(q_0) = 1_(B^∗).
Soit q = {(q_1, w_1), …, (q_k, w_k)} un élément déjà construit de Q_s et soit a ∈ A. S'il existe i ∈ {1, …, k} et r ∈ Q, tels que (q_i, a, r) ∈ dom(T), alors on définit q ⋅ a et q⋆a comme suit. On pose pour i ∈ {1, …, k},
V(q_i, w_i, a), = {(r, v) ∈ Q × B^∗ : T(q_i, a, r) = v}; W(q_i, w_i, a), = {w_i v ∈ B^∗ : ∃r ∈ Q, T(q_i, a, r) = v}
Soit W = ⋃_i W(q_i, w_i, a) et w = ⋀W. On définit
q ⋅ a = ⋃_i{(r, w^(− 1)w_i v) : (r, v) ∈ V(q_i, w_i, a)}, et q⋆a = w
On a alors q ⋅ a ∈ Q_s, (q, a, q ⋅ a) ∈ dom(T_s) et T_s(q, a, q ⋅ a) = q⋆a.
Fig. 2: Une partie d'un transducteur T et du quintuplet T_s 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 T un transducteur et soit T_s le quintuplet associé. Soit q ∈ Q_s. Montrer que pour tout (p, v) ∈ q, il existe (q, w) ∈ q tel que v ∧ w = 1_(B^∗). On suppose de plus que T vérifie la propriété de jumelage. Montrer que pour tout q ∈ Q_s et tout (p, v) ∈ q, on a |v| ≤ 2n^2 M (où n et M sont définis comme à la question 3.6). En déduire que l'ensemble Q_s est fini.
Question 3.10.
Soit T un transducteur fonctionnel vérifiant la propriété de jumelage. Construire un transducteur séquentiel réalisant la fonction f_T. Proposer et justifier un algorithme prenant en entrée un transducteur T, retournant 'non' si f_T n'est pas une fonction séquentielle et retournant dans le cas contraire un transducteur séquentiel T^′ réalisant f_T.
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 T mais seulement à décider de la séquentialité de f_T 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é.
Pas de description pour le moment
Commentaires• ENS Option Informatique MP 2000
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Sujet proche avec corrigéX ENS Informatique C MPI 2025X-ENS · 2025Corrigé
Même année, CCINPCCINP Option Informatique MP 2000CCINP · 2000Corrigé
Sujet proche avec corrigéCentrale Option Informatique MP 2024Centrale · 2024Corrigé
Même année, XPolytechnique Option Informatique MP 2000X · 2000Corrigé
