ENS Informatique MP 2010Sujet

Durée : 4 heures

L'usage de calculatrices électroniques de poche n'est pas autorisé.

Ce sujet, composé de 30 questions, étudie une classe de programmes simples avec variables à valeurs dans ℕ. Les questions peuvent être résolues en admettant les résultats des questions précédentes. Les questions des parties II ou III sont indépendantes des questions des autres parties tandis que des questions de la partie IV dépendent de la partie III.

Les algorithmes peuvent être donnés dans la notation de votre choix du moment qu'elle soit suffisamment précise. Pour chaque algorithme proposé, il est indispensable de justifier sa correction et de donner sa complexité en temps dans le pire des cas en choisissant les paramètres pertinents. Comme d'habitude, il est demandé d'apporter le plus grand soin à la rédaction.

L'usage des calculatrices est interdit.

Dans la suite, ℕ et ℤ représentent respectivement l'ensemble des entiers naturels et l'ensemble des entiers relatifs. Pour l, l^′ ∈ ℤ, [l, l^′] représente l'ensemble des entiers relatifs j tels que l ≤ j ≤ l^′. Un élément x ∈ ℤ^n est dénoté par ⟨x(1), …, x(n)⟩. Pour x, y ∈ ℤ^n, on note x + y l'élément de ℤ^n tel que pour i ∈ [1, n], nous avons (x + y)(i) = ^(def)x(i) + y(i). Pour I ⊆ [1, n], ℤ^I dénote l'ensemble des fonctions I → ℤ. Etant donnés x ∈ ℤ^n et I ⊆ [1, n], on note x_I ∈ ℤ^I, la restriction de x à I ( ℕ^I est défini de façon analogue). Ainsi, pour i ∈ I, nous avons x_I(i) = x(i). Pour n ≥ 1, l'ordre partiel ⪯ sur ℤ^n est défini ainsi : x⪯y ⇔ ^(def) pour i ∈ [1, n], x(i) ≤ y(i). On note x≺y lorsque x⪯y et x ≠ y. Le cardinal d'un ensemble X est dénoté par card(X). NB : dans la suite ⊂ dénote l'inclusion ensembliste stricte tandis que ⊆ dénote l'inclusion non stricte.

Nous allons introduire une famille de programmes simples qui peuvent être vus comme des automates finis auxquels on adjoint la possibilité de mettre à jour des compteurs (variables à valeurs dans ℕ ). Les valeurs des compteurs sont représentées par des vecteurs d'entiers naturels. Un système d'addition de vecteurs avec états (SAVE) est un triplet S = ⟨S, T, n⟩ tel que
− n ≥ 1 (la dimension).

Ainsi, S peut être vu comme un automate fini dont l'alphabet est un sous-ensemble fini de ℤ^n, automate cependant privé des états initiaux et finaux. Une transition ⟨s, u, s^′⟩ de T est aussi notée s → ^u s^′, et u est appelée la mise à jour de la transition. Une paire dans S × ℤ^n est appelée une configuration de S. Une configuration est dite admissible lorsqu'elle appartient à S × ℕ^n. Soit ⊢⊆(S × ℤ^n) × (S × ℤ^n) la relation représentant un pas de calcul et définie ainsi : ⟨s, x⟩⊢⟨s^′, x^′⟩ ⇔ ^(def) il existe une transition ⟨s, u, s^′⟩ dans T telle que x^′ = x + u. On note ⊢_(adm) la restriction de ⊢ aux seules configurations admissibles. Un pseudo-calcul [resp. calcul] de S est une séquence de configurations ⟨s_0, x_0⟩…⟨s_k, x_k⟩ telle que j ∈ [0, k − 1], ⟨s_j, x_j⟩⊢⟨s_(j + 1), x_(j + 1)⟩ [resp. ⟨s_j, x_j⟩⊢_(adm)⟨s_(j + 1), x_(j + 1)⟩ ]. Un calcul ⟨s_0, x_0⟩…⟨s_k, x_k⟩ est donc une exécution du SAVE S vu comme un programme avec n compteurs, de la configuration initiale ⟨s_0, x_0⟩ à la configuration ⟨s_k, x_k⟩. On écrit alors ⟨s_0, x_0⟩⊢_(adm)^∗⟨s_k, x_k⟩ lorsqu'il existe un calcul de la forme ⟨s_0, x_0⟩…⟨s_k, x_k⟩. Les relations ⊢ et ⊢_(adm) dépendent donc toujours d'un SAVE et dans la suite il sera toujours clair quel est le SAVE sous-jacent lorsque ces relations sont utilisées.

QUESTION 1. Ecrire en pseudo-code un algorithme qui prenne en entrée un SAVES = ⟨S, T, n⟩ et une séquence non vide ⟨s_0, x_0⟩…⟨s_k, x_k⟩ de configurations et qui détermine si la séquence est un calcul de S.

Les questions 2,3 et 5 vont faire référence au SAVE S_(mult) = ⟨{A, B}, {t_1, …, t_4}, 4⟩ tel que

La figure ci-dessous représente graphiquement S_(mult) : chaque noeud correspond à un état de contrôle et chaque arc représente une transition, la mise à jour étiquetant l'arc. Dans les réponses, on pourra utiliser les noms de transition se trouvant entre crochets.

Question 2. Calculer l'ensemble {(a; b; c; d) ∈ ℕ^4 : ⟨A, (2; 1; 0; 0)⟩⊢_(adm)^∗⟨ A, (a; b; c; d)⟩}}}{{.
Question 3. Montrer que

On dit alors que S_(mult) calcule faiblement la multiplication. Les SAVE permettent de calculer faiblement de nombreuses autres fonctions usuelles.

Question 4. Déterminer la fonction f telle que

pour le SAVE représenté ci-dessous

Dans la suite, nous cherchons à résoudre les problèmes ci-dessous.
(P1) Etant donnés un SAVE S, une configuration admissible ⟨s, x⟩ et un état de contrôle (acceptant) s_(Acc), existe-t-il x^′ ∈ ℕ^n tel que ⟨s, x⟩⊢_(adm)^∗⟨s_(Acc), x^′⟩ ? En d'autres termes, existe-t-il un calcul qui puisse atteindre un état de contrôle à partir d'une configuration admissible initiale ?
(P2) Etant donnés un SAVE S et une configuration admissible ⟨s, x⟩, l'ensemble des configurations ⟨s^′, x^′⟩ telles que ⟨s, x⟩⊢_(adm)^∗⟨s^′, x^′⟩ est-il infini?

Question 5. Pour le SAVE S_(mult), existe-t-il (a; b; c; d) ∈ ℕ^4 tel que l'ensemble

soit infini? On justifiera sa réponse.
Question 6. Ecrire en pseudo-code un algorithme qui prenne en entrée un tuple (a; b; c; d) ∈ ℕ^4 et qui retourne l'ensemble des tuples (a^′; b^′; c^′; d^′) ∈ ℕ^4 tels que ⟨A, (a; b; c; d)⟩⊢_(adm)^∗⟨ A, (a^′; b^′; c^′; d^′)⟩. On évaluera le temps de calcul en fonction de a + b + c + d.

Par définition, une transition s → ^u s^′ est une auto-transition lorsque s = s^′.
Question 7. Montrer que si l'on possède un algorithme pour résoudre les problèmes (P1) et (P2) restreints aux SAVE sans auto-transition, alors il existe un algorithme pour résoudre les problèmes (P1) et (P2) (sans aucune restriction).

SAV. Pour résoudre les problèmes sur les SAVE, nous introduisons une famille de systèmes un peu plus rudimentaires, qui sont des SAVE sans états de contrôle explicites. Un système d'addition de vecteurs (SAV) est la donnée d'un entier n ≥ 1 (sa dimension) et d'un ensemble fini T ⊆ ℤ^n (dans la suite on identifiera le SAV avec T ). Un élément tr ∈ T sera appelé une transition. Un chemin est une séquence finie de transitions. Le chemin c^′ est un sous-chemin du chemin c = tr_1…tr_k ⇔ ^(def) il existe 1 ≤ j_1 < j_2⋯ < j_(k^′) ≤ k tel que c^′ = tr_(j_1)…tr_(j_(k^′)), ce qui sera noté c^′⊑c.

Promenade. Une configuration x du SAV T est un élément de ℤ^n. Une configuration x est dite admissible lorsque x ∈ ℕ^n. Si c = tr_1…tr_k est un chemin, la promenade ⟨c, x⟩ est la suite de configurations x_0⋯x_k telle que x_0 = x et pour i ∈ [1, k], x_i = x_(i − 1) + tr_i. La promenade x_0⋯x_k est dite induite par le chemin c et de longueur k + 1; c est de longueur k. La configuration x_0 est initiale dans la promenade x_0⋯x_k et x_k est dite finale. De plus, x_k est dite accessible de x_0. La promenade x_0⋯x_k est dite admissible lorsque toutes les configurations intermédiaires sont dans ℕ^n. Dans ce cas, la configuration x_k est dite positivement accessible de x_0. Ce qui nous intéresse vraiment, ce sont les promenades admissibles, ne serait-ce pour résoudre nos problèmes sur les SAVE qui font appel à des configurations admissibles : toutes les composantes sont positives. Cependant, la possibilité d'avoir des valeurs négatives pour certaines configurations d'une promenade d'un SAV, nous sera utile quelquefois.

Dans le reste du sujet, on s'intéresse aux deux problèmes suivants sur les SAV.
(P1') Etant donnés un SAV T et deux configurations admissibles x, y ∈ ℕ^n, existe-t-il une configuration y^′ positivement accessible de x telle que y⪯y^′ ? Le triplet ⟨T, x, y⟩ est appelé une instance du problème de couverture et y^′ est appelée une solution.
(P2') Etant donnés un SAV T et une configuration admissible x ∈ ℕ^n, existe-t-il un nombre infini de configurations positivement accessibles de x ?

Question 8. Montrer que si l'on possède un algorithme pour résoudre les problèmes ( P1^′ ) et ( P2^′ ) sur les SAV, alors il existe un algorithme pour résoudre les problèmes (P1) et (P2) sur les SAVE.

L'objectif de cette partie est de proposer un algorithme qui résolve le problème ( Pl^′ ).

Tailles. Le pic minimal d'un élément x ∈ ℤ^n, noté pic (x), est max({max(0, − x(i)) : i ∈ [1, n]}). Le maximum d'un élément x ∈ ℤ^n, dénoté max(x) est max({x(i) : i ∈ [1, n]}).

On note ‖T‖_(max) le maximum max({|tr(i)| : tr ∈ T, i ∈ [1, n]}). Le pic minimal d'un SAV T, dénoté par pic (T), est max{pic(tr) : tr ∈ T}. La taille de T, notée taille (T), est la valeur n × card(T) × (2 + ⌈log_2(1 + ‖T‖_(max))⌉). On peut remarquer que max(pic(T), card(T)) ≤ 2^(taille (T)) et que ( 1 + ⌈log_2(N)⌉ ) correspond à un nombre suffisant de bits pour représenter l'entier N en binaire (pour les entiers relatifs, un bit est aussi utilisé pour le signe).

Question 9. Définir une instance ⟨T, x, y⟩ du problème de couverture ayant au moins une solution et dont chaque solution soit positivement accessible de x avec une promenade de longueur au moins égale à n × max(y).

Dans la suite, on se fixe un SAV T et une configuration à couvrir y. Pour I ⊆ [1, n], une promenade x_0…x_k est dite I-admissible lorsque pour i ∈ I et j ∈ [0, k], nous avons x_j(i) ≥ 0. Une promenade x_0…x_k est dite I - r-admissible avec r > 0 si pour i ∈ I et j ∈ [0, k], nous avons 0 ≤ x_j(i) < r. Une promenade x_0…x_k est dite I-couvrante si pour i ∈ I, nous avons x_k(i) ≥ y(i), c'est-à-dire y_I⪯(x_k)_I.

QUESTION 10. Soient I ⊆ [1, n] et x_0…x_k une promenade I-admissible et I-couvrante.

QUESTION 11. Soit x_0…x_k une promenade I - r-admissible induite par le chemin c avec I ⊆ [1, n] et r > 0. Montrer qu'il existe un chemin c^′⊑c de longueur strictement inférieure à r^(card (I)) tel que ⟨c^′, x_0⟩ = y_0⋯y_l soit I - r-admissible et (y_l)_I = (x_k)_I. Si de plus, x_0…x_k est I-couvrante, alors y_0⋯y_l est aussi I-couvrante.

QUESTION 12. Ecrire en pseudo-code un algorithme qui prenne en entrée une instance ⟨T, x, y⟩ et un entier k ∈ ℕ et détermine s'il existe une configuration y^′ positivement accessible de x avec un chemin de longueur au plus k telle que y⪯y^′.

Pour x ∈ ℤ^n et I ⊆ [1, n], on note M(I, x) la plus petite longueur d'une promenade I admissible et I-couvrante dont la configuration initiale est x. Si une telle promenade n'existe pas, M(I, x) prend la valeur zéro par défaut.

Dans la suite, on verra que {M(I, x) : x ∈ ℤ^n} possède un maximum. Soit f(I) = ^(def)max({M(I, x) : x ∈ ℤ^n} ). On remarque que f dépend implicitement de T et de y. De plus, pour ∅ ⊂ I ⊆ [1, n], f_⊂(I) = ^(def)max({f(I^′) : I^′ ⊂ I}) et pour m ∈ [0, n], F(m) = ^(def)max({f(I) : I ⊆ [1, n], card(I) ≤ m} ).

Question 13. Calculer F(0).
QUESTION 14. Ecrire en pseudo-code un algorithme qui prenne en entrée une instance ⟨T, x, y⟩ telle que pic(T) × max(y) = 0 et qui détermine s'il existe une configuration y^′ positivement accessible de x telle que y⪯y^′. De plus, lorsque pic(T) × max(y) = 0, majorer F(n).

Dans la suite, on suppose que pic(T) × max(y) ≥ 1. On dit que I ⊆ [1, n] satisfait la propriété (⋆) dans le cas suivant : pour toute promenade ⟨c, x⟩I-admissible et I-couvrante, il existe un chemin c^′ de longueur au plus (f(I) − 1) tel que c^′⊑c et ⟨c^′, x⟩ soit I-admissible et I-couvrante.

QUESTION 15. Soient I^′ ⊂ I ⊆ [1, n] et ⟨c, x_0⟩ = x_0…x_l…x_k une promenade I-admissible et I-couvrante avec 0 ≤ l < k tels que

Montrer qu'il existe un chemin c^′ de longueur au plus r^(card (I)) + f(I^′) − 2 tel que c^′⊑c et ⟨c^′, x_0⟩ est I-admissible et I-couvrante.

QUESTION 16. Soit I ⊆ [1, n] tel que pour chaque I^′ ⊂ I, l'ensemble de composantes I^′ vérifie la propriété (⋆). Montrer que si ⟨c, x⟩ est une promenade I-admissible et I-couvrante alors il existe un chemin c^′⊑c tel que ⟨c^′, x⟩ est I-admissible et I-couvrante, et de longueur inférieure à (pic(T)f_⊂(I) + max(y))^(card(I)) + f_⊂(I) − 1.

QUESTION 17. Lorsque le produit pic (T)max(y) vaut au moins 1 , majorer F(n) en fonction de n, pic(T) et max(y), par exemple par ((pic(T) + 2)max(y))^((n + 1)!).

QUESTION 18. Ecrire en pseudo-code un algorithme qui prenne en entrée une instance ⟨T, x, y⟩ et qui retourne une configuration y^′ positivement accessible de x telle que y⪯y^′ si elle existe, sinon false. On justifiera la correction de l'algorithme et on évaluera le temps de calcul.

Cette partie met en relation les graphes orientés finis et des systèmes d'inéquations, ce qui sera utile dans la partie IV dédiée à la résolution du problème (P2').

Graphe orienté. Un graphe orienté fini G = ⟨S, A⟩ est une paire composée d'un ensemble fini S de sommets et d'un ensemble d'arcs A ⊆ S × S. Pour tout arc a = ⟨s, s^′⟩ ∈ A, on note or (a) l'origine s de a et ex(a) l'extrémité s^′. Un chemin c = a_1…a_k est une séquence d'arcs de A telle que pour i ∈ [1, k − 1], ex(a_i) = or(a_(i + 1)). L'origine du chemin c, notée or(c), est or(a_1) et son extrémité, notée ex(c), est ex(a_k). On dit alors que c est un chemin de or(c) vers ex(c). On admet aussi des chemins vides de longueur 0 , un pour chaque sommet de graphe. Deux chemins c, c^′ sont dits consécutifs si ex(c) = or(c^′). Lorsque c et c^′ sont consécutifs, on note cc^′ le chemin obtenu en concaténant c avec c^′.