Informatique A

# Rapport

Concours X-ENS, informatique A, filière MP, année 2010.

Rapport de l'épreuve écrite  
ENS Informatique MP 2010

Éric Colin de Verdière, Stéphane Demri, Yves Robert

Septembre 2010

## 1 Présentation du sujet

Ce sujet porte sur l'étude des systèmes à addition de vecteurs avec états (SAVE) et sur la résolution des problèmes suivants : atteignabilité d'un état de contrôle et déterminer quand l'ensemble des configurations admissibles terminant un calcul à partir d'une configuration initiale donnée est infini. Ces systèmes forment une classe de programmes simples avec variables à valeurs dans $\mathbb{N}$ ; ils peuvent être vus comme des automates finis auxquels on adjoint la possibilité de mettre à jour des compteurs (variables à valeurs dans $\mathbb{N}$). Le sujet considère donc un modèle de calcul relativement rudimentaire pour lequel la difficulté de l'analyse des SAVE provient du fait que les variables ne peuvent prendre une valeur négative le long d'un calcul.

La partie I traite d'un SAVE particulier qui calcule faiblement la multiplication et elle introduit aussi une classe restreinte de SAVE, les SAV, pour lesquels il n'y a plus d'états de contrôle. En fait, les questions 7 et 8 montrent pourquoi se restreindre aux SAV permet quand même de traiter les problèmes sur les SAVE (mais peu de candidats ont abordé la question 8). La partie II traite de la résolution du problème de couverture sur les SAV, ce qui permet alors de résoudre le problème de l'atteignabilité d'un état de contrôle sur les SAVE. La partie III, partie préparatoire pour la partie IV, a pour but principal de montrer comment l'existence de chemins dans un graphe orienté fini peut s'exprimer comme la résolution de systèmes d'inéquations. Finalement, la partie IV utilise la partie III pour proposer une solution au problème de l'existence d'une infinité de configurations admissibles positivement atteignables d'une configuration admissible donnée d'un SAV. La partie III, indépendante des parties I et II, a plutôt été bien traitée dans sa première moitié.

## 2 Remarques générales

Pour une épreuve de quatre heures, ce sujet était d'une longueur très importante. La notation a été adaptée en conséquence. Les questions les plus difficiles (16, 17, 22, 26, 27, 28, 29, 30) n'ont pratiquement pas été abordées.

Le sujet portait essentiellement sur l'étude des calculs issus des SAVE et nécessitait un traitement mathématique avant la conception d'algorithmes corrects. Une preuve rigoureuse de l'égalité de la question 3 a peu été proposée par les candidats, conduisant quelquefois à énoncer des propriétés fausses sur les calculs des SAVE. Plus de rigueur était attendue ici, comme pour le reste des questions.

Plusieurs questions demandaient d'écrire des pseudo-algorithmes (par exemple les questions 1, 6, 12, 14, 18). Il est bon de rappeler ici qu'avant de définir un pseudo-algorithme, décrire les variables et leur utilisation sont des préliminaires qui facilitent la compréhension du pseudo-algorithme.

## 3 Informations quantitatives

Cette épreuve a été traitée par 387 candidats. La moyenne globale a été de 9,98 sur 20 avec un écart-type de 3,98. Les notes variaient entre 1,2 et plusieurs 20. Vu la longueur du sujet, traiter les quinze premières questions assurait la note maximale. La partie IV n'a été pratiquement pas abordée, à part quelques réponses à la question 25. Il en est de même de la seconde partie de la partie III (questions 22, 23 et 24).

Un peu plus d'un tiers des candidats ont trouvé les douze configurations admissibles de la question 2, ce qui est peu rapport à la difficulté de la question. Ceux qui sont passés par la construction systématique d'un arbre ont pu en effet effectuer une recherche exhaustive. Cependant, tenter de définir l'ensemble de façon paramétrée (par le nombre de passages dans chaque transition) ou raisonner sur les configurations atteintes au fur et à mesure, a souvent donné lieu à des solutions incomplètes, voir erronées.

## 4 Corrigé

**Question 1.** Écrire en pseudo-code un algorithme qui prenne en entrée un SAVE $\mathcal{S} = \langle S, T, n \rangle$ et une séquence non vide $\langle s_0, x_0 \rangle \ldots \langle s_k, x_k \rangle$ de configurations et qui détermine si la séquence est un calcul de $\mathcal{S}$.

**Réponse 1.** Étant donnée une séquence non vide $\langle s_0, x_0 \rangle \ldots \langle s_k, x_k \rangle$, il faut vérifier que les conditions suivantes soient assurées :

- pour $i \in [0, k]$, $x_i \in \mathbb{N}^n$,
- pour $i \in [0, k-1]$, $\langle s_i, x_{i+1} - x_i, s_{i+1} \rangle \in T$.

L'énoncé n'interdit pas que la séquence soit réduite à $\langle s_0, x_0 \rangle$ avec $\langle s_0, x_0 \rangle \in S \times \mathbb{Z}^n$ et autoriser une telle séquence est donc correct (même si ce n'était pas dans l'esprit de la notion de calcul).

L'algorithme ci-dessous prend en entrée le SAVE $\langle S, T, n \rangle$ et la séquence $\langle s_0, x_0 \rangle \ldots \langle s_k, x_k \rangle$.

```
cal := true ; i := 0 ;
while (cal and i ≤ k) do
begin
  if i > 0 then cal := (cal and s_{i-1} —(x_i − x_{i-1})→ s_i ∈ T) ;
  j := 1 ;
  while (cal and j ≤ n) do
  begin
    cal := (cal and x_i(j) ≥ 0) ;
    j := j + 1 ;
  end
  i := i + 1 ;
end
return cal ;
```

L'utilisation de `while` permet de s'arrêter dès que l'on sait que la séquence n'est pas un calcul (si c'est effectivement le cas).

**Question 2.** Calculer l'ensemble

$$\left\{ \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} \in \mathbb{N}^4 : \left\langle A, \begin{pmatrix} 2 \\ 1 \\ 0 \\ 0 \end{pmatrix} \right\rangle \vdash^*_{\mathrm{adm}} \left\langle A, \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} \right\rangle \right\}.$$

**Réponse 2.** La façon la plus simple de répondre est de construire l'arbre des configurations admissibles accessibles (omis ici). On obtient alors les 12 quadruplets suivants en construisant l'arbre.

$$
\begin{pmatrix} 2 \\ 1 \\ 0 \\ 0 \end{pmatrix}
\begin{pmatrix} 2 \\ 0 \\ 1 \\ 0 \end{pmatrix}
\begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \end{pmatrix}
\begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \end{pmatrix}
\begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}
\begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}
\begin{pmatrix} 0 \\ 1 \\ 0 \\ 2 \end{pmatrix}
\begin{pmatrix} 0 \\ 1 \\ 0 \\ 1 \end{pmatrix}
\begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}
\begin{pmatrix} 0 \\ 0 \\ 1 \\ 2 \end{pmatrix}
\begin{pmatrix} 0 \\ 0 \\ 1 \\ 1 \end{pmatrix}
\begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}
$$

**Question 3.** Montrer que

$$\left\{ \begin{pmatrix} a \\ b \\ d \end{pmatrix} \in \mathbb{N}^3 : d \le a \times b \right\} = \left\{ \begin{pmatrix} a \\ b \\ d \end{pmatrix} \in \mathbb{N}^3 : \exists \begin{pmatrix} a' \\ b' \\ c' \end{pmatrix} \in \mathbb{N}^3,\ \left\langle A, \begin{pmatrix} a \\ b \\ 0 \\ 0 \end{pmatrix} \right\rangle \vdash^*_{\mathrm{adm}} \left\langle A, \begin{pmatrix} a' \\ b' \\ c' \\ d \end{pmatrix} \right\rangle \right\}.$$

**Réponse 3.** On commence par introduire une notation. À chaque calcul $\langle s_0, x_0 \rangle \ldots \langle s_k, x_k \rangle$, on peut associer une unique séquence $t_0 \cdots t_{k-1}$ de transitions telle que pour $j \in [0, k-1]$, $t_j = \langle s_j, u, s_{j+1} \rangle$ soit l'unique transition de $T$ telle que $x_{j+1} = x_j + u$. Si le calcul est réduit à $\langle s_0, x_0 \rangle$ alors la séquence de transitions associée est réduite à la séquence vide $\varepsilon$.

Soit $x_0 = \begin{pmatrix} a \\ b \\ 0 \\ 0 \end{pmatrix}$ avec $a, b \ge 0$. Chaque calcul de la forme $\langle A, x_0 \rangle \ldots \langle A, x_k \rangle$ admet une séquence de transitions associée de la forme ci-dessous

$$(t_1)^{\alpha_1} t_2 (t_4)^{\beta_1} t_3 (t_1)^{\alpha_2} t_2 (t_4)^{\beta_2} \cdots (t_1)^{\alpha_N} t_2 (t_4)^{\beta_N} t_3 (t_1)^{\alpha_{N+1}},$$

avec $\alpha_1, \beta_1, \ldots, \alpha_N, \beta_N, \alpha_{N+1} \ge 0$ et $N \ge 0$. Comme d'habitude $(t)^i$ représente la séquence de longueur $i$ avec $i$ occurrences de $t$, c'est-à-dire $(t)^0 \stackrel{\mathrm{def}}{=} \varepsilon$ et $(t)^{i+1} \stackrel{\mathrm{def}}{=} t \cdot (t)^i$. Voici quelques observations utiles :

1. La seule transition modifiant la première composante est $t_2$ et il s'agit d'une décrémentation. Par conséquent, $N \le a$.
2. La seule transition modifiant la quatrième composante est $t_4$ et il s'agit d'une incrémentation. Comme la valeur initiale de la quatrième composante est 0 dans le calcul, nous avons $x_k(4) = \beta_1 + \cdots + \beta_N$.
3. Dans le calcul, la somme de la seconde composante et de la troisième composante est constante. En effet, soit une transition ne modifie aucune de ces deux composantes, soit une transition incrémente une composante mais décrémente l'autre. Cette somme est exactement égale à $b$ (la valeur initiale de la seconde composante plus la valeur initiale de la troisième composante). Par conséquent, pour $i \in [1, N]$, nous avons $\max(\alpha_i, \beta_i) \le b$.

Ainsi, on obtient $x_k(4) \le a \times b$. On peut remarquer que montrer seulement qu'il existe un calcul terminant en $\langle A, x_k \rangle$ avec $x_k(4) = a \times b$ n'est pas suffisant.

Pour obtenir l'inclusion dans l'autre sens, prenons maintenant $M \in [0, a \times b]$. Si $M = 0$, on prend le calcul réduit à la configuration admissible initiale. Sinon, il existe $q \in [0, a-1]$ et $r \in [0, b-1]$ tels que $M - 1 = q \times b + r$. Par conséquent, il existe $q \in [0, a-1]$ et $r' \in [0, b]$ tels que $M = q \times b + r'$. Soit le calcul $\langle A, x_0 \rangle \ldots \langle A, x_k \rangle$ dont la séquence de transitions associée est exactement :

$$\overbrace{(t_1)^b t_2 (t_4)^b t_3 (t_1)^b t_2 (t_4)^b \cdots (t_1)^b t_2 (t_4)^b}^{q\ \text{fois}} (t_1)^b t_2 (t_4)^{r'} t_3.$$

On peut vérifier que précisément $x_k(4) = q \times b + r' = M$.

**Question 4.** Déterminer la fonction $f$ telle que

$$\left\{ \begin{pmatrix} a \\ b \\ e \end{pmatrix} \in \mathbb{N}^3 : e \le f(a, b) \right\} = \left\{ \begin{pmatrix} a \\ b \\ e \end{pmatrix} \in \mathbb{N}^3 : \exists \begin{pmatrix} a' \\ b' \\ c' \\ d' \end{pmatrix} \in \mathbb{N}^4,\ \left\langle C, \begin{pmatrix} a \\ 0 \\ b \\ 0 \end{pmatrix} \right\rangle \vdash^*_{\mathrm{adm}} \left\langle A, \begin{pmatrix} a' \\ b' \\ c' \\ e \end{pmatrix} \right\rangle \right\}$$

pour le SAVE représenté ci-dessous.

États de contrôle $C$, $A$ et $B$.

- boucle $[t_5]$ sur $C$, de vecteur $\begin{pmatrix} -1 \\ 1 \\ 1 \\ 0 \end{pmatrix}$ ;
- arc $[t_6]$ de $C$ vers $A$, de vecteur $\begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}$ ;
- boucle $[t_1]$ sur $A$, de vecteur $\begin{pmatrix} 0 \\ -1 \\ 1 \\ 0 \end{pmatrix}$ ;
- arc $[t_3]$ de $A$ vers $B$, de vecteur $\begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}$ ;
- arc $[t_2]$ de $B$ vers $A$, de vecteur $\begin{pmatrix} 0 \\ -1 \\ 0 \\ 0 \end{pmatrix}$ ;
- boucle $[t_4]$ sur $B$, de vecteur $\begin{pmatrix} 0 \\ 1 \\ -1 \\ 1 \end{pmatrix}$.

**Réponse 4.** Nous allons vérifier que $f(a, b) = a^2 + ab$. Soit $x_0 = \begin{pmatrix} a \\ 0 \\ b \\ 0 \end{pmatrix}$ avec $a, b \ge 0$.

Pour cela, il ne suffit pas de montrer que

$$a^2 + ab \in \left\{ d \in \mathbb{N} : \exists \begin{pmatrix} a' \\ b' \\ c' \end{pmatrix} \in \mathbb{N}^3,\ \left\langle C, \begin{pmatrix} a \\ 0 \\ b \\ 0 \end{pmatrix} \right\rangle \vdash^*_{\mathrm{adm}} \left\langle A, \begin{pmatrix} 0 \\ b' \\ c' \\ d \end{pmatrix} \right\rangle \right\}.$$

Chaque calcul de la forme $\langle C, x_0 \rangle \ldots \langle A, x_k \rangle$ admet une séquence de transitions associée de la forme ci-dessous

$$(t_5)^{\gamma} t_6 (t_1)^{\alpha_1} t_2 (t_4)^{\beta_1} t_3 (t_1)^{\alpha_2} t_2 (t_4)^{\beta_2} \cdots (t_1)^{\alpha_N} t_2 (t_4)^{\beta_N} t_3 (t_1)^{\alpha_{N+1}},$$

avec $\gamma, \alpha_1, \beta_1, \ldots, \alpha_N, \beta_N, \alpha_{N+1} \ge 0$ et $N \ge 0$. Avant de franchir la première transition $t_1$, s'il y en a une, la configuration admissible courante est de la forme $\begin{pmatrix} a_0 \\ a_1 \\ b + a_1 \\ 0 \end{pmatrix}$ avec $a = a_0 + a_1$. En particulier,

$$\left\langle C, \begin{pmatrix} a \\ 0 \\ b \\ 0 \end{pmatrix} \right\rangle \vdash^*_{\mathrm{adm}} \left\langle A, \begin{pmatrix} 0 \\ a \\ a + b \\ 0 \end{pmatrix} \right\rangle.$$

On remarque alors que le sous-système réduit aux états de contrôle $A$ et $B$ correspond au SAVE $\mathcal{S}_{\mathrm{mult}}$ une fois la première composante oubliée. Par la question 3, on a donc,

$$\left\{ \begin{pmatrix} a \\ b \\ d \end{pmatrix} \in \mathbb{N}^3 : d \le a(a + b) \right\} = \left\{ \begin{pmatrix} a \\ b \\ d \end{pmatrix} \in \mathbb{N}^3 : \exists \begin{pmatrix} a' \\ b' \\ c' \end{pmatrix} \in \mathbb{N}^3,\ \left\langle A, \begin{pmatrix} 0 \\ a \\ a + b \\ 0 \end{pmatrix} \right\rangle \vdash^*_{\mathrm{adm}} \left\langle A, \begin{pmatrix} 0 \\ a' \\ b' \\ d \end{pmatrix} \right\rangle \right\}$$

et donc

$$\left\{ \begin{pmatrix} a \\ b \\ e \end{pmatrix} \in \mathbb{N}^3 : e \le a^2 + ab \right\} \subseteq \left\{ \begin{pmatrix} a \\ b \\ e \end{pmatrix} \in \mathbb{N}^3 : \exists \begin{pmatrix} a' \\ b' \\ c' \\ d' \end{pmatrix} \in \mathbb{N}^4,\ \left\langle C, \begin{pmatrix} a \\ 0 \\ b \\ 0 \end{pmatrix} \right\rangle \vdash^*_{\mathrm{adm}} \left\langle A, \begin{pmatrix} a' \\ b' \\ c' \\ e \end{pmatrix} \right\rangle \right\}.$$

Comme par ailleurs,

$$\left\{ \begin{pmatrix} a_0 \\ a_1 \\ d \end{pmatrix} \in \mathbb{N}^3 : d \le a_1(a_1 + b) \right\} = \left\{ \begin{pmatrix} a_1 \\ b \\ d \end{pmatrix} \in \mathbb{N}^3 : \exists \begin{pmatrix} a' \\ b' \\ c' \end{pmatrix} \in \mathbb{N}^3,\ \left\langle A, \begin{pmatrix} a_0 \\ a_1 \\ b + a_1 \\ 0 \end{pmatrix} \right\rangle \vdash^*_{\mathrm{adm}} \left\langle A, \begin{pmatrix} a_0 \\ a' \\ b' \\ d \end{pmatrix} \right\rangle \right\},$$

nous obtenons aussi l'inclusion dans l'autre sens.

**Question 5.** Pour le SAVE $\mathcal{S}_{\mathrm{mult}}$, existe-t-il $\begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} \in \mathbb{N}^4$ tel que l'ensemble

$$\left\{ \begin{pmatrix} a' \\ b' \\ c' \\ d' \end{pmatrix} \in \mathbb{N}^4 : \left\langle A, \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} \right\rangle \vdash^*_{\mathrm{adm}} \left\langle A, \begin{pmatrix} a' \\ b' \\ c' \\ d' \end{pmatrix} \right\rangle \right\}$$

soit infini ? On justifiera sa réponse.

**Réponse 5.** La réponse est une variante de la réponse à la question 3. Soit $x_0 = \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} \in \mathbb{N}^4$. Chaque calcul de la forme $\langle A, x_0 \rangle \ldots \langle A, x_k \rangle$ admet une séquence de transitions associée de la forme ci-dessous

$$(t_1)^{\alpha_1} t_2 (t_4)^{\beta_1} t_3 (t_1)^{\alpha_2} t_2 (t_4)^{\beta_2} \cdots (t_1)^{\alpha_N} t_2 (t_4)^{\beta_N} t_3 (t_1)^{\alpha_{N+1}},$$

avec $\alpha_1, \beta_1, \ldots, \alpha_N, \beta_N, \alpha_{N+1} \ge 0$ et $N \ge 0$. Voici quelques autres observations utiles :

1. La seule transition modifiant la première composante est $t_2$ et il s'agit d'une décrémentation. Par conséquent, $N \le a$ et la valeur de la première composante dans le calcul est toujours dans l'intervalle $[0, a]$.
2. La seule transition modifiant la quatrième composante est $t_4$ et il s'agit d'une incrémentation. Comme la valeur initiale de la quatrième composante est $d$ dans le calcul, la valeur de la quatrième composante dans le calcul est toujours dans l'intervalle $[d, d + (\beta_1 + \cdots + \beta_N)]$.
3. Dans le calcul, la somme de la seconde composante et de la troisième composante est constante. En effet, soit une transition ne modifie aucune de ces composantes, soit une transition incrémente une composante mais décrémente l'autre. Cette somme est exactement égale à $b + c$. Par conséquent, la valeur de la seconde ou de la troisième composante dans le calcul est toujours dans l'intervalle $[0, b + c]$.
4. Par ailleurs, pour $i \in [1, N]$, nous avons $\max(\alpha_i, \beta_i) \le b + c$. Par conséquent, la valeur de la quatrième composante dans le calcul est toujours dans l'intervalle $[d, d + a \times (b + c)]$.

Comme dans le calcul, toutes les composantes ont des valeurs bornées, il n'existe pas de $\begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} \in \mathbb{N}^4$ tel que

$$\left\{ \begin{pmatrix} a' \\ b' \\ c' \\ d' \end{pmatrix} \in \mathbb{N}^4 : \left\langle A, \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} \right\rangle \vdash^*_{\mathrm{adm}} \left\langle A, \begin{pmatrix} a' \\ b' \\ c' \\ d' \end{pmatrix} \right\rangle \right\}$$

soit infini.

**Question 6.** Écrire en pseudo-code un algorithme qui prenne en entrée un tuple $\begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} \in \mathbb{N}^4$ et qui retourne l'ensemble des tuples $\begin{pmatrix} a' \\ b' \\ c' \\ d' \end{pmatrix} \in \mathbb{N}^4$ tels que

$$\left\langle A, \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} \right\rangle \vdash^*_{\mathrm{adm}} \left\langle A, \begin{pmatrix} a' \\ b' \\ c' \\ d' \end{pmatrix} \right\rangle.$$

On évaluera le temps de calcul en fonction de $a + b + c + d$.

**Réponse 6.** La question ne le précise mais il s'agit de répondre pour le SAVE $\mathcal{S}_{\mathrm{mult}}$. Une réponse dans le cas général est aussi acceptée.

Une conséquence de la réponse à la question précédente est que l'ensemble des configurations admissibles présentes dans un calcul dont la configuration initiale est $\begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}$ est fini et de cardinal au plus $K = 2 \times (a + 1) \times (b + c + 1)^2 \times (a \times (b + c) + 1)$ (on multiplie par 2 car il y a deux états de contrôle). On peut même se restreindre à $K = 2 \times (a + 1) \times 2(b + c + 1) \times (a \times (b + c) + 1)$ car la somme de la seconde composante et de la troisième composante est toujours égale à $b + c$. Notons que $K$ ne dépend pas de la valeur $d$. L'algorithme décrit ci-dessous termine puisque on passe au plus $K$ fois dans la boucle principale. Ci-dessous, $Attente$ est la liste de configurations admissibles en attente de traitement, $Traitees$ est l'ensemble des configurations admissibles déjà traitées et $E$ est l'ensemble qui sera retourné. Voici l'algorithme.

```
Attente := (⟨A, (a, b, c, d)⟩) ; E := ∅ ; Traitees := ∅ ;
while Attente ≠ nil do
begin
  Soit config = ⟨s, (a', b', c', d')⟩ le premier élément de la liste Attente,
  que l'on retire de cette liste ;
  for s' —u→ s'' ∈ {t_1, t_2, t_3, t_4} do
  begin
    if (a', b', c', d') + u ∈ ℕ⁴ and s' = s
       and ⟨s'', (a', b', c', d') + u⟩ ∉ Traitees then
    begin
      Attente := cons(⟨s'', (a', b', c', d') + u⟩, Attente) ;
    end
  end
  Traitees := Traitees ∪ {config} ;
  if s = A then E := E ∪ {(a', b', c', d')} ;
end
return E ;
```

La boucle principale est empruntée au plus $K$ fois et avec une structure de données raisonnable pour les ensembles, chaque passage dans la boucle nécessite un temps de calcul en $\mathcal{O}(K)$. Ainsi, l'algorithme ci-dessus calcule l'ensemble $E$ en temps $\mathcal{O}(K^2)$, ce qui est polynomial en $a + b + c + d$. Voici deux remarques relatives à cette question :

- Si $\left\langle A, \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} \right\rangle \vdash^*_{\mathrm{adm}} \left\langle A, \begin{pmatrix} a' \\ b' \\ c' \\ d' \end{pmatrix} \right\rangle$ alors $\begin{pmatrix} a' \\ b' \\ c' \\ d' \end{pmatrix} \in [0, a] \times [0, b + c]^2 \times [d, d + a(b + c)]$.

Un autre algorithme possible consiste à énumérer les éléments de $[0, a] \times [0, b + c]^2 \times [d, d + a(b + c)]$ atteignables, mais ils ne le sont pas tous, ce qui rend la conception d'un tel algorithme plus difficile. Par exemple, on peut remarquer que non seulement $b' + c' = b + c$ mais aussi $d' \le d + (a - a')(b + c)$.

- Même si l'ensemble des tuples recherchés $\begin{pmatrix} a' \\ b' \\ c' \\ d' \end{pmatrix}$ est de cardinal polynomial en $a + b + c$, le nombre de calculs partant de $\begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}$ est par contre exponentiel en $a + b + c$, d'où l'intérêt de stocker les configurations admissibles déjà atteintes.

**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).

**Réponse 7.** Soit $\mathcal{S} = \langle S, T, n \rangle$ un SAVE. Nous allons effectivement construire un SAVE $\mathcal{S}' = \langle S', T', n \rangle$ sans auto-transition avec $S \subseteq S'$ et $T \subseteq T'$ tel que pour toutes les configurations admissibles $\langle s, x \rangle$ et $\langle s', x' \rangle$ de $\mathcal{S}$, nous avons $\langle s, x \rangle \vdash^*_{\mathrm{adm}} \langle s', x' \rangle$ dans $\mathcal{S}$ si et seulement si $\langle s, x \rangle \vdash^*_{\mathrm{adm}} \langle s', x' \rangle$ dans $\mathcal{S}'$.

En particulier, pour toute configuration admissible $\langle s, x \rangle$ de $\mathcal{S}$ et pour tout état de contrôle $s_{\mathrm{Acc}} \in S$, il existe $x' \in \mathbb{N}^n$ tel que $\langle s, x \rangle \vdash^*_{\mathrm{adm}} \langle s_{\mathrm{Acc}}, x' \rangle$ dans $\mathcal{S}$ si et seulement s'il existe $x' \in \mathbb{N}^n$ tel que $\langle s, x \rangle \vdash^*_{\mathrm{adm}} \langle s_{\mathrm{Acc}}, x' \rangle$ dans $\mathcal{S}'$. Ainsi, la résolution de (P1) sur les SAVE sans auto-transition permet de résoudre (P1) dans le cas général.

Si $\mathcal{S}$ ne contient pas d'auto-transitions, alors $\mathcal{S}' = \mathcal{S}$. Dans le cas contraire (le seul cas intéressant ici), soit $s_1, \ldots, s_N$ l'ensemble des états de contrôle $s$ de $S$ admettant dans $T$ une auto-transition de la forme $\mathrm{tr} = s \xrightarrow{u} s$ (il peut y en avoir plusieurs pour un même état de contrôle $s$). Soit $s'_1, \ldots, s'_N$ de nouveaux états de contrôle et posons $S' \stackrel{\mathrm{def}}{=} S \uplus \{s'_1, \ldots, s'_N\}$.

L'ensemble des transitions $T'$ est obtenu à partir de $T$ en remplaçant chaque transition de la forme $\mathrm{tr} = s \xrightarrow{u} s$ par $\mathrm{tr}' = s \xrightarrow{\begin{pmatrix} 0 \\ \vdots \\ 0 \end{pmatrix}} s'$ (cette transition pouvant provenir de plusieurs auto-transitions de $\mathcal{S}$) et $\mathrm{tr}'' = s' \xrightarrow{u} s$. Par induction sur la longueur des calculs, on peut montrer les deux propriétés suivantes :

- Pour toutes les configurations admissibles $\langle s, x \rangle$ et $\langle s', x' \rangle$ de $\mathcal{S}$ (et donc $s, s' \in S$), nous avons $\langle s, x \rangle \vdash^*_{\mathrm{adm}} \langle s', x' \rangle$ dans $\mathcal{S}$ si et seulement si $\langle s, x \rangle \vdash^*_{\mathrm{adm}} \langle s', x' \rangle$ dans $\mathcal{S}'$. Dans les séquences de transition associées, il suffit de remplacer une auto-transition $\mathrm{tr}$ par $\mathrm{tr}'\mathrm{tr}''$, et réciproquement.
- Pour tous les états de contrôle $s_i$ ayant une auto-transition dans $\mathcal{S}$, pour toutes les configurations admissibles $\langle s, x \rangle$ et $\langle s_i, x' \rangle$ de $\mathcal{S}'$, nous avons $\langle s, x \rangle \vdash^*_{\mathrm{adm}} \langle s_i, x' \rangle$ dans $\mathcal{S}'$ si et seulement si $\langle s, x \rangle \vdash^*_{\mathrm{adm}} \langle s'_i, x' \rangle$ dans $\mathcal{S}'$.

Le second point implique pour toute configuration admissible $\langle s, x \rangle$ de $\mathcal{S}$, l'ensemble des configurations $\langle s', x' \rangle$ telles que $\langle s, x \rangle \vdash^*_{\mathrm{adm}} \langle s', x' \rangle$ dans $\mathcal{S}$ est infini si et seulement si l'ensemble des configurations $\langle s', x' \rangle$ telles que $\langle s, x \rangle \vdash^*_{\mathrm{adm}} \langle s', x' \rangle$ dans $\mathcal{S}'$ est infini. En effet, l'infinité de l'ensemble des configurations admissibles atteignables dans $\mathcal{S}'$ ne peut pas être due seulement aux configurations admissibles ayant un état de contrôle dans $S' \setminus S$. Ainsi, la résolution de (P2) sur les SAVE sans auto-transition permet de résoudre (P2) dans le cas général.

Une autre solution consiste à définir $\mathcal{S}'$ comme la copie de deux versions de $\mathcal{S}$ où chaque transition passe d'une copie à l'autre. Cela permet aussi d'éliminer les auto-transitions à moindre coût.

**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.

**Réponse 8.** Soit $\mathcal{S} = \langle S, T, n \rangle$ un SAVE sans auto-transition. On peut se restreindre à ce cas, d'après la question 7. Nous allons construire un SAV $T'$ pour lequel les états de contrôle de $\mathcal{S}$ sont codés par l'ajout de $\mathrm{card}(S)$ composantes qui prendront la valeur 0 ou 1. La présence de 1 en $(n + i)$ième position d'une configuration code que l'état de contrôle courant est le $i$ième état de contrôle de $S$. Voici les détails.

Soit $\rho$ une bijection (arbitraire) de $S$ vers $\{1, \ldots, \mathrm{card}(S)\}$ et $X$ le sous-ensemble de $\mathbb{Z}^{n + \mathrm{card}(S)}$ tel que

$$X = \left\{ x \in \mathbb{Z}^{n + \mathrm{card}(S)} : x_{[n+1,\ n + \mathrm{card}(S)]} = e_i \in \mathbb{N}^{\mathrm{card}(S)}\ \text{pour un}\ i \in [1, \mathrm{card}(S)] \right\}$$

en notant $e_i(j) = 0$ si $i \neq j$ et $e_i(i) = 1$.

Nous posons aussi $X^+ = X \cap \mathbb{N}^{n + \mathrm{card}(S)}$. Soit $T'$ le SAV tel que pour $\mathrm{tr} = s \xrightarrow{u} s' \in T$ ($s \neq s'$ par hypothèse), la transition $\mathrm{tr}' \in T'$ est définie ainsi :

- $(\mathrm{tr}')_{[1, n]} = u$,
- pour $t \in S \setminus \{s, s'\}$, $\mathrm{tr}'(\rho(t)) = 0$,
- $\mathrm{tr}'(\rho(s)) = -1$ et $\mathrm{tr}'(\rho(s')) = 1$.

Soit $h$ la bijection entre les configurations de $\mathcal{S}$ et celles de $X$ telle que

$$h(\langle s, x \rangle)_{[n+1,\ n + \mathrm{card}(S)]} = e_{\rho(s)}\quad \text{et}\quad h(\langle s, x \rangle)_{[1, n]} = x.$$

Pour chaque calcul $\langle s_0, x_0 \rangle \ldots \langle s_k, x_k \rangle$ dans $\mathcal{S}$, on peut lui associer la promenade positive

$$h(\langle s_0, x_0 \rangle) \ldots h(\langle s_k, x_k \rangle)$$

dans $T'$ dont chaque configuration est dans $X^+$. De même, à chaque promenade positive $y_0 \cdots y_k$ dans $T'$ composée de configurations de $X^+$, la séquence $h^{-1}(y_0) \cdots h^{-1}(y_k)$ est un calcul dans $\mathcal{S}$. Ainsi, étant donnés une configuration admissible $\langle s, x \rangle$ de $\mathcal{S}$ et un état de contrôle $s_{\mathrm{Acc}}$, les propositions suivantes sont équivalentes :

- il existe $x' \in \mathbb{N}^n$ telle que $\langle s, x \rangle \vdash^*_{\mathrm{adm}} \langle s_{\mathrm{Acc}}, x' \rangle$,
- l'instance $\langle T', h(\langle s, x \rangle), h(\langle s_{\mathrm{Acc}}, (0, \ldots, 0) \rangle) \rangle$ du problème de couverture a une solution.

La résolution de (P1$'$) sur les SAV permet de résoudre (P1) sur les SAVE sans auto-transition et donc sur tous les SAVE d'après la question 7. De même, étant donnée une configuration admissible $\langle s, x \rangle$ de $\mathcal{S}$, les propositions suivantes sont équivalentes :

- l'ensemble des configurations $\langle s', x' \rangle$ telles que $\langle s, x \rangle \vdash^*_{\mathrm{adm}} \langle s', x' \rangle$ est infini,
- le nombre de configurations positivement accessibles de $h(\langle s, x \rangle)$ dans $\mathcal{S}'$ est infini.

On remarque ici que pour toute configuration positivement accessible de $h(\langle s, x \rangle)$, le vecteur composé des $n$ dernières composantes ne peut prendre qu'un nombre fini de valeurs (dans un ensemble de cardinal $\mathrm{card}(S)$). Ainsi, la résolution de (P2$'$) sur les SAV permet de résoudre (P2) sur les SAVE sans auto-transition et donc sur tous les SAVE d'après la question précédente.

**Question 9.** Définir une instance $\langle T, x, y \rangle$ 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 \times \max(y)$.

**Réponse 9.** Soit $\langle T, x, y \rangle$ l'instance telle que $T = \{e_1, \ldots, e_n\} \subseteq \mathbb{N}^n$, $x = \langle 0, \ldots, 0 \rangle \in \mathbb{N}^n$ et $y = \langle m, \ldots, m \rangle \in \mathbb{N}^n$ pour un entier $m > 0$. Comme $y = x + m e_1 + \ldots + m e_n$, si $c = \mathrm{tr}_1 \cdots \mathrm{tr}_k$ est un chemin et $\langle c, x \rangle$ est une promenade dont la configuration finale est supérieure à $y$ alors nécessairement $k \ge m \times n = \max(y) \times n$.

**Question 10.** Soient $I \subseteq [1, n]$ et $x_0 \ldots x_k$ une promenade $I$-admissible et $I$-couvrante.

1. Pour chaque $\Delta \in \mathbb{Z}^n$ tel que $\Delta_I \in \mathbb{N}^I$, montrer que la séquence $(x_0 + \Delta) \ldots (x_k + \Delta)$ est une promenade $I$-admissible et $I$-couvrante.
2. Supposons qu'il existe $0 \le \alpha < \beta \le k$ tels que $(x_{\alpha})_I = (x_{\beta})_I$ avec $\Delta = x_{\alpha} - x_{\beta}$. Montrer que la séquence $x_0 \ldots x_{\alpha - 1}(x_{\beta} + \Delta) \ldots (x_k + \Delta)$ est une promenade $I$-admissible et $I$-couvrante.

**Réponse 10.** Soit $c = \mathrm{tr}_1 \ldots \mathrm{tr}_k$ un chemin tel que la promenade $\langle c, x \rangle$ soit la suite de configurations $x_0 \cdots x_k$.

1. Pour $j \in [1, k]$, $x_j - x_{j-1} = (x_j + \Delta) - (x_{j-1} + \Delta) = \mathrm{tr}_j \in T$ et donc $(x_0 + \Delta) \ldots (x_k + \Delta)$ est une promenade. Par ailleurs, comme $\Delta_I \in \mathbb{N}^I$ alors pour $i \in I$ et $j \in [0, k]$, $(x_j + \Delta)(i) \ge 0$. La promenade $(x_0 + \Delta) \ldots (x_k + \Delta)$ est donc $I$-admissible. De plus, comme $\Delta_I \in \mathbb{N}^I$ alors pour $i \in I$, $(x_k + \Delta)(i) \ge x_k(i) \ge y(i)$. La promenade $(x_0 + \Delta) \ldots (x_k + \Delta)$ est donc $I$-couvrante.
2. Comme $\Delta_I = \langle 0, \ldots, 0 \rangle \in \mathbb{N}^I$, d'après le point 1 ci-dessus, $(x_{\beta} + \Delta) \ldots (x_k + \Delta)$ est une promenade $I$-admissible et $I$-couvrante car $x_{\beta} \ldots x_k$ est aussi $I$-admissible et $I$-couvrante. De plus, par hypothèse, $x_0 \ldots x_{\alpha - 1}$ est une promenade $I$-admissible (mais pas nécessairement $I$-couvrante). Par ailleurs, comme $x_{\beta} + \Delta = x_{\alpha}$ et $x_{\alpha} - x_{\alpha - 1} \in T$, la séquence $x_0 \ldots x_{\alpha}$ est aussi une promenade $I$-admissible. En conclusion,

$$x_0 \ldots x_{\alpha - 1}(x_{\beta} + \Delta) \ldots (x_k + \Delta)$$

est une promenade $I$-admissible et $I$-couvrante.

**Question 11.** Soit $x_0 \ldots x_k$ une promenade $I$-$r$-admissible induite par le chemin $c$ avec $I \subseteq [1, n]$ et $r > 0$. Montrer qu'il existe un chemin $c' \sqsubseteq c$ de longueur strictement inférieure à $r^{\mathrm{card}(I)}$ tel que $\langle c', x_0 \rangle = y_0 \cdots y_l$ soit $I$-$r$-admissible et $(y_l)_I = (x_k)_I$. Si de plus, $x_0 \ldots x_k$ est $I$-couvrante, alors $y_0 \cdots y_l$ est aussi $I$-couvrante.

**Réponse 11.** La preuve est par induction sur la longueur $k$ de $c$. Si la longueur de $c$ est strictement inférieure à $r^{\mathrm{card}(I)}$, alors prenons $c' = c$. Dans le cas contraire, supposons à présent que la propriété soit vraie pour $k \le N$ et considérons une promenade $x_0 \ldots x_{N+1}$ induite par le chemin $\mathrm{tr}_1 \ldots \mathrm{tr}_{N+1}$ qui est $I$-$r$-admissible [resp. et $I$-couvrante]. Comme $N + 1 \ge r^{\mathrm{card}(I)}$, il existe $0 \le \alpha < \beta \le N + 1$ tels que $(x_{\alpha})_I = (x_{\beta})_I$. Posons $\Delta = x_{\alpha} - x_{\beta}$ ; nous avons $\Delta_I = \langle 0, \ldots, 0 \rangle \in \mathbb{N}^I$. D'après la question 10(2), $x_0 \ldots x_{\alpha}(x_{\beta + 1} + \Delta) \cdots (x_{N+1} + \Delta)$ est $I$-admissible [resp. et $I$-couvrante]. Par ailleurs, pour $i \in I$ et $j \in [\beta + 1, N + 1]$, $(x_j + \Delta)(i) = x_j < r$. Donc, $(x_{N+1} + \Delta)_I = (x_k)_I$ et $x_0 \cdots x_{\alpha}(x_{\beta + 1} + \Delta) \cdots (x_{N+1} + \Delta)$ est aussi $I$-$r$-admissible et possède au plus $N + 1$ configurations. Par hypothèse d'induction, il existe une séquence $j_1 \cdots j_l$ avec $l < r^{\mathrm{card}(I)}$ et $1 \le j_1 < \ldots < j_l \le (N + 1) - (\beta - \alpha)$ telle que $\langle \mathrm{tr}_{j_1} \ldots \mathrm{tr}_{j_l}, x_0 \rangle = y_0 \cdots y_l$ est $I$-$r$-admissible [resp. et $I$-couvrante] et $(y_l)_I = (x_{N+1} + \Delta)_I = (x_k)_I$. Nous avons par ailleurs $\mathrm{tr}_{j_1} \ldots \mathrm{tr}_{j_l} \sqsubseteq \mathrm{tr}_1 \ldots \mathrm{tr}_{N+1}$.

**Question 12.** Écrire en pseudo-code un algorithme qui prenne en entrée une instance $\langle T, x, y \rangle$ et un entier $k \in \mathbb{N}$ et détermine s'il existe une configuration $y'$ positivement accessible de $x$ avec un chemin de longueur au plus $k$ telle que $y \preceq y'$.

**Réponse 12.** Nous supposons que $T$ contienne $p$ transitions $\mathrm{tr}_0, \ldots, \mathrm{tr}_{p-1}$ (ordre arbitraire). Nous allons coder toutes les séquences de transitions de longueur égale à $k$ par des entiers entre $0$ et $p^k - 1$ (en base $p$). Pour chaque séquence, on vérifie si on a pu atteindre positivement une configuration couvrant $y$.

```
if y ⪯ x then return true else
begin
  trouve := false ;
  for s = 0 to p^k − 1 do
  begin
    y' = x ; i := 1 ; adm := true ;
    while ( not trouve and i ≤ k and adm ) do
    begin
      u := ith digit of s in {0, …, p − 1} (s écrit en base p) ;
      if y' + tr_u ∈ ℕ^n then
      begin
        y' := y' + tr_u ;
        trouve := (y ⪯ y') ;
      end
      else adm := false ;
      i := i + 1 ;
    end
  end
  return trouve ;
end
```

Un algorithme récursif est aussi tout à fait envisageable. La condition d'arrêt porte sur $k = 0$ ou bien la configuration courante est supérieure ou égale à $y$.

**Question 13.** Calculer $F(0)$.

**Réponse 13.** Pour $x \in \mathbb{Z}^n$, la séquence $x$ composée d'une unique configuration est $\emptyset$-admissible et $\emptyset$-couvrante (car sans contrainte sur les composantes de $[1, n]$). Par conséquent, $M(\emptyset, x) = 1$ pour toutes les configurations $x$. Ainsi, $f(\emptyset) = 1$ et $F(0) = 1$.

**Question 14.** Écrire en pseudo-code un algorithme qui prenne en entrée une instance $\langle T, x, y \rangle$ telle que $\mathrm{pic}(T) \times \max(y) = 0$ et qui détermine s'il existe une configuration $y'$ positivement accessible de $x$ telle que $y \preceq y'$. De plus, lorsque $\mathrm{pic}(T) \times \max(y) = 0$, majorer $F(n)$.

**Réponse 14.** Voici l'algorithme.

```
Soit I l'ensemble {i ∈ [1, n] : x(i) < y(i)}.
if I = ∅ then return true else
begin
  cover := true ;
  for i ∈ I do cover := (cover and (∃ tr ∈ T tq tr(i) ≥ 1)) ;
  return cover ;
end
```

Si $\max(y) = 0$ alors on peut prendre $y' = x$. Sinon, $\mathrm{pic}(T) = 0$ et donc chaque composante de $y$ peut être atteinte (ou dépassée) en moins de $\max(y)$ pas. Ainsi, $F(n) \le n \times \max(y) + 1$.

**Question 15.** Soient $I' \subset I \subseteq [1, n]$ et $\langle c, x_0 \rangle = x_0 \ldots x_l \ldots x_k$ une promenade $I$-admissible et $I$-couvrante avec $0 \le l < k$ tels que

- $I'$ satisfait la propriété $(\star)$,
- $x_0 \ldots x_{l-1}$ est $I$-$r$-admissible avec $r = \mathrm{pic}(T) f(I') + \max(y)$ et $(x_l)_I \notin [0, r - 1]^I$,
- pour $i \in I$, nous avons $i \in (I \setminus I')$ si et seulement si $x_l(i) \ge r$.

Montrer qu'il existe un chemin $c'$ de longueur au plus $r^{\mathrm{card}(I)} + f(I') - 2$ tel que $c' \sqsubseteq c$ et $\langle c', x_0 \rangle$ est $I$-admissible et $I$-couvrante.

**Réponse 15.** Considérons une promenade $x_0 \ldots x_l \ldots x_k$ vérifiant les hypothèses de la question et induite par le chemin $\mathrm{tr}_1 \cdots \mathrm{tr}_k$. Si $l \ge r^{\mathrm{card}(I)}$, d'après la question 11, il existe une promenade $y_0 \cdots y_{l'}$ telle que

- $l' < r^{\mathrm{card}(I)}$,
- $y_0 = x_0$, $(y_{l'})_I = (x_l)_I$,
- $y_0 \ldots y_{l'}$ est $I$-$r$-admissible,
- il existe $1 \le j_1 < \cdots < j_{l'} \le l$ tels que $y_0 \ldots y_{l'}$ est induite par $\mathrm{tr}_{j_1} \cdots \mathrm{tr}_{j_{l'}}$.

Soit $y_0 \cdots y_{l'} \cdots y_{l' + (k - l)}$ la promenade induite par le chemin $\mathrm{tr}_{j_1} \cdots \mathrm{tr}_{j_{l'}} \mathrm{tr}_{l+1} \cdots \mathrm{tr}_k$. On peut remarquer que pour $j \in [0, (k - l)]$, $(y_{l' + j})_I = (x_{l + j})_I$. Par conséquent, la promenade $y_0 \cdots y_{l'} \cdots y_{l' + (k - l)}$ est $I$-$r$-admissible et $I$-couvrante et en particulier $y_{l'} \cdots y_{l' + (k - l)}$ est $I'$-$r$-admissible et $I'$-couvrante.

Par définition de $f(I')$ et comme $I'$ satisfait $(\star)$, il existe une promenade $z_0 \cdots z_{l''}$ $I'$-admissible et $I'$-couvrante telle que

- $z_0 = y_{l'}$,
- il existe $l + 1 \le m_1 < \cdots < m_{l''} \le k$ tel que $z_0 \cdots z_{l''}$ soit induite par $\mathrm{tr}_{m_1} \cdots \mathrm{tr}_{m_{l''}}$,
- $l'' < f(I')$.

Comme $(r, \ldots, r) \le (z_0)_{I \setminus I'}$ car $(z_0)_I = (y_{l'})_I = (x_l)_I$, pour $j \in [0, l'']$, $(r - \mathrm{pic}(T) \times j, \ldots, r - \mathrm{pic}(T) \times j) \le (z_j)_{I \setminus I'}$. Par conséquent, $z_0 \cdots z_{l''}$ est aussi $I$-admissible et $\langle \max(y), \ldots, \max(y) \rangle \le (z_{l''})_{I \setminus I'}$, et donc cette promenade est aussi $I$-couvrante. En conclusion, la promenade

$$\langle \mathrm{tr}_{j_1} \cdots \mathrm{tr}_{j_{l'}} \mathrm{tr}_{m_1} \cdots \mathrm{tr}_{m_{l''}}, x_0 \rangle$$

est $I$-couvrante et $I$-admissible et $l' + l'' \le r^{\mathrm{card}(I)} + f(I') - 2$.

**Question 16.** Soit $I \subseteq [1, n]$ tel que pour chaque $I' \subset I$, l'ensemble de composantes $I'$ vérifie la propriété $(\star)$. Montrer que si $\langle c, x \rangle$ est une promenade $I$-admissible et $I$-couvrante alors il existe un chemin $c' \sqsubseteq c$ tel que $\langle c', x \rangle$ est $I$-admissible et $I$-couvrante, et de longueur inférieure à $(\mathrm{pic}(T) f_{\subset}(I) + \max(y))^{\mathrm{card}(I)} + f_{\subset}(I) - 1$.

**Réponse 16.** Soit $x_0 \cdots x_k$ une promenade $I$-admissible et $I$-couvrante induite par le chemin $c = \mathrm{tr}_1 \cdots \mathrm{tr}_k$.

Si $x_0 \cdots x_k$ est $I$-$(\mathrm{pic}(T) f_{\subset}(I) + \max(y))$-admissible alors d'après la question 11, il existe une promenade $y_0 \cdots y_l$ $I$-admissible et $I$-couvrante avec $l < (\mathrm{pic}(T) f_{\subset}(I) + \max(y))^{\mathrm{card}(I)}$ et $x_0 = y_0$ induite par $\mathrm{tr}_{j_1} \cdots \mathrm{tr}_{j_l}$ avec $1 \le j_1 < \cdots < j_l \le k$. On obtient bien la bonne borne puisque $f_{\subset}(I) \ge 1$.

Si $x_0 \cdots x_k$ n'est pas $I$-$(\mathrm{pic}(T) f_{\subset}(I) + \max(y))$-admissible alors il existe $l' \le k$ et $\emptyset \subset I' \subseteq I$ tel que la première configuration dont une valeur soit supérieure ou égale à $\mathrm{pic}(T) f(I') + \max(y)$ est $x_{l'}$, et $I'$ est l'ensemble de composantes de $x_{l'}$ atteignant au moins cette valeur. D'après la question 15, il existe une séquence $1 \le j_1 < \ldots < j_l \le k$ avec $l \le (\mathrm{pic}(T) f(I') + \max(y))^{\mathrm{card}(I)} + f(I') - 2$ telle que $\langle \mathrm{tr}_{j_1} \ldots \mathrm{tr}_{j_l}, x_0 \rangle$ soit une promenade $I$-admissible et $I$-couvrante. Ainsi, $l \le (\mathrm{pic}(T) f_{\subset}(I) + \max(y))^{\mathrm{card}(I)} + f_{\subset}(I) - 2$.

**Question 17.** Lorsque le produit $\mathrm{pic}(T) \max(y)$ vaut au moins 1, majorer $F(n)$ en fonction de $n$, $\mathrm{pic}(T)$ et $\max(y)$, par exemple par $((\mathrm{pic}(T) + 2) \max(y))^{(n+1)!}$.

**Réponse 17.** Soit $g$ la fonction telle que $g(0) = 1$ et $g(m + 1) = (\mathrm{pic}(T) g(m) + \max(y))^{m+1}$ pour $m \ge 0$. On commence par énoncer quelques propriétés immédiates (en supposant $\mathrm{pic}(T) \max(y) \ge 1$) :

- pour $\emptyset \subset I \subseteq [1, n]$ avec $\mathrm{card}(I) = m$, $f(I) \le F(m)$ et $f_{\subset}(I) \le F(m - 1)$ (par définition de $F$),
- pour $m \in [0, n]$, $F(m) \le g(m)$ en utilisant un raisonnement analogue à celui de la question précédente,
- $g(0), \ldots, g(n) \ge 1$,
- $(\mathrm{pic}(T) + 2) \max(y)\, g(m - 1) \ge \mathrm{pic}(T) g(m - 1) + \max(y) + g(m - 1)$.

On peut donc montrer par récurrence sur $m$, que pour $m \in [0, n]$,

$$g(m) \le \bigl( (\mathrm{pic}(T) + 2) \max(y) \bigr)^{(m+1)!}.$$

Pour $m = 0$, la preuve est immédiate. Supposons la propriété vraie pour $m$. Nous avons $g(m + 1) \le \bigl( \mathrm{pic}(T) g(m) + \max(y) \bigr)^{m+1} + g(m)$ et

$$\bigl( \mathrm{pic}(T) g(m) + \max(y) \bigr)^{m+1} \le \bigl( \mathrm{pic}(T) g(m) + \max(y) + g(m) \bigr)^{m+1}.$$

Par conséquent, $g(m + 1) \le \bigl( (\mathrm{pic}(T) + 2) \max(y)\, g(m) \bigr)^{m+1}$. Par hypothèse d'induction, $g(m) \le \bigl( (\mathrm{pic}(T) + 2) \max(y) \bigr)^{((m+1)!)}\,^{m+1}$ et donc

$$g(m + 1) \le \bigl( (\mathrm{pic}(T) + 2) \max(y) \bigr)^{m+1} \bigl( (\mathrm{pic}(T) + 2) \max(y) \bigr)^{(m+1) \times (m+1)!}.$$

Par conséquent,

$$g(m + 1) \le \bigl( (\mathrm{pic}(T) + 2) \max(y) \bigr)^{(m+1) + (m+1) \times (m+1)!} \le \bigl( (\mathrm{pic}(T) + 2) \max(y) \bigr)^{(m+2)!}.$$

En conclusion, $F(n) \le g(n) \le \bigl( (\mathrm{pic}(T) + 2) \max(y) \bigr)^{(n+1)!}$.

**Question 18.** Écrire en pseudo-code un algorithme qui prenne en entrée une instance $\langle T, x, y \rangle$ et qui retourne une configuration $y'$ positivement accessible de $x$ telle que $y \preceq y'$ si elle existe, sinon `false`. On justifiera la correction de l'algorithme et on évaluera le temps de calcul.

**Réponse 18.** On a vu qu'étant donnés un SAV $T$, une configuration initiale $x \in \mathbb{N}^n$ et une configuration $y \in \mathbb{N}^n$, il existe $y'$ positivement accessible de $x$ telle que $y \preceq y'$ si et seulement s'il existe une promenade positive de longueur inférieure à $F(n)$ dont la configuration initiale est $x$ et la configuration finale est supérieure à $y$. Posons $F'(n) = \bigl( (\mathrm{pic}(T) + 2) \max(y) \bigr)^{(n+1)!}$, qui est un majorant de $F(n)$.

Le nombre de chemins ayant $F'(n)$ transitions est fini et est égal à $\mathrm{card}(T)^{F'(n)}$. S'il existe un chemin $c = \mathrm{tr}_1 \ldots \mathrm{tr}_{F'(n)}$ avec $\langle c, x \rangle = x_0 \cdots x_{F'(n)}$ tel qu'il existe $l \le F'(n)$ vérifiant $y \preceq x_l$ et $x_0 \cdots x_l$ est une promenade positive alors l'existence d'une configuration $y'$ est assurée (dans le cas contraire il n'existe pas de telle configuration).

L'algorithme ci-dessous illustre cette procédure. Le codage de l'énumération des séquences de transitions de longueur $F'(n)$ n'est pas difficile mais serait un peu fastidieux. L'itération ci-dessous sur $T^N$ cache ce point. L'algorithme ci-dessous est une variante de celui de la question 12, où la longueur du chemin est au plus $\bigl( (\mathrm{pic}(T) + 2) \max(y) \bigr)^{(n+1)!}$.

```
if y ⪯ x then return x else
begin
  N := ((pic(T) + 2) max(y))^{(n+1)!} ; trouve := false ;
  for tr_1 … tr_N ∈ T^N do
  begin
    y'' = x ; i := 1 ; adm := true ;
    while ( not trouve and i ≤ N and adm ) do
    begin
      y'' := y'' + tr_i ;
      if y'' ∉ ℕ^n then adm := false else trouve := (y ⪯ y'') ;
      if trouve then y' := y'' ;
      i := i + 1 ;
    end
  end
  if trouve then return y' else return false ;
end
```

La valeur positive maximale d'une position sur un tel chemin est $\max(x) + \lVert T \rVert_{\max} F'(n)$ et donc chaque somme nécessite un temps de calcul en $\mathcal{O}\bigl( n \bigl( \log(\lVert T \rVert_{\max}) + \log(\max(x) + \lVert T \rVert_{\max} F'(n)) \bigr) \bigr)$. La vérification pour chaque chemin de la propriété peut se faire en temps de calcul en $\mathcal{O}\bigl( F'(n) \times \bigl( n \bigl( \log(\lVert T \rVert_{\max}) + \log(\max(x) + \lVert T \rVert_{\max} F'(n)) \bigr) \bigr) \bigr)$. Le temps total de calcul est de l'ordre de $\mathcal{O}\bigl( \mathrm{card}(T)^{F'(n)} \times \bigl( F'(n) \times \bigl( n \bigl( \log(\lVert T \rVert_{\max}) + \log(\max(x) + \lVert T \rVert_{\max} F'(n)) \bigr) \bigr) \bigr) \bigr)$.

**Question 19.** Construire un graphe $G = \langle S, A \rangle$ dont on puisse montrer l'existence des images ci-dessous. On donnera des justifications.

1. Il existe des images de chemin $\mathcal{I}, \mathcal{I}' : A \to \mathbb{N}$ telles que $\mathcal{I} + \mathcal{I}'$ ne soit pas l'image d'un chemin de $G$. $(\mathcal{I} + \mathcal{I}')(a)$ est défini par $\mathcal{I}(a) + \mathcal{I}'(a)$ pour chaque arc $a$.
2. Il existe des fonctions $\mathcal{I}, \mathcal{I}' : A \to \mathbb{N}$ qui ne soient images d'aucun chemin de $G$ et dont $\mathcal{I} + \mathcal{I}'$ est l'image d'un chemin.
3. Il existe une fonction $\mathcal{I} : A \to \mathbb{N}$ qui soit image de deux chemins distincts de $G$.

**Réponse 19.** Considérons le graphe ci-dessous (contenant assez de nœuds pour traiter toutes les sous-questions).

- Composante de gauche : cycle orienté d'arcs $a_1, a_2, a_3, a_4$ ($a_1$ et $a_2$ en partie haute, $a_3$ et $a_4$ en partie basse).
- Composante de droite : chaîne de cinq sommets $\circ \xrightarrow{a_5} \circ \xrightarrow{a_6} \circ \xrightarrow{a_7} \circ \xrightarrow{a_8} \circ$.

1. $\mathcal{I}(a_1) = \mathcal{I}(a_2) = 1$ et pour $i \notin \{1, 2\}$, $\mathcal{I}(a_i) = 0$. $\mathcal{I}'(a_5) = 1$ et pour $i \neq 5$, $\mathcal{I}'(a_i) = 0$.
2. $\mathcal{I}(a_5) = \mathcal{I}(a_7) = 1$ et pour $i \notin \{5, 7\}$, $\mathcal{I}(a_i) = 0$. $\mathcal{I}'(a_6) = \mathcal{I}'(a_8) = 1$ et pour $i \notin \{6, 8\}$, $\mathcal{I}'(a_i) = 0$.
3. $\mathcal{I}(a_1) = \mathcal{I}(a_2) = \mathcal{I}(a_3) = \mathcal{I}(a_4) = 1$ et pour $i \notin \{1, 2, 3, 4\}$, $\mathcal{I}(a_i) = 0$. Voici deux chemins possibles : $a_1 a_2 a_3 a_4$, $a_3 a_4 a_1 a_2$.

**Question 20.** Soient $c_1$ et $c_2$ deux chemins ayant un sommet en commun et dont $or(c_2) = ex(c_2)$. Montrer qu'il existe un chemin $c$ tel que $\mathcal{I}_c = \mathcal{I}_{c_1} + \mathcal{I}_{c_2}$, $or(c) = or(c_1)$ et $ex(c) = ex(c_1)$.

**Réponse 20.** Soit $s$ un sommet commun aux deux chemins. Comme $or(c_2) = ex(c_2)$, il existe un chemin $c'_2$ tel que $\mathcal{I}_{c'_2} = \mathcal{I}_{c_2}$ et $or(c'_2) = ex(c'_2) = s$ (il suffit éventuellement de modifier l'origine du chemin cyclique).

- Si $or(c_1) = s$ alors $c = c'_2 c_1$ est un chemin tel que $\mathcal{I}_c = \mathcal{I}_{c_1} + \mathcal{I}_{c_2}$.
- Si $ex(c_1) = s$ alors $c = c_1 c'_2$ est un chemin tel que $\mathcal{I}_c = \mathcal{I}_{c_1} + \mathcal{I}_{c_2}$.
- Si $c_1 = c'_1 c''_1$ avec $ex(c'_1) = s$ et $or(c''_1) = s$ alors $c = c'_1 c'_2 c''_1$ est un chemin tel que $\mathcal{I}_c = \mathcal{I}_{c_1} + \mathcal{I}_{c_2}$.

On peut vérifier facilement que $or(c) = or(c_1)$ et $ex(c) = ex(c_1)$.

**Question 21.** Soient $G = \langle S, A \rangle$ un graphe orienté fini et $c = a_1 \ldots a_k$ un chemin de $s$ à $s'$ avec pour image $\mathcal{I}_c : A \to \mathbb{N}$. Montrer les propriétés ci-dessous.

**(I)** $G_{\mathcal{I}_c}$ est connexe.

**(II)** Si $s = s'$ alors pour $t \in S$, $\displaystyle \sum_{a \in A\ \mathrm{tq}\ ex(a) = t} \mathcal{I}_c(a) - \sum_{a \in A\ \mathrm{tq}\ or(a) = t} \mathcal{I}_c(a) = 0$.

**(III)** Si $s \neq s'$ alors

- pour $t \in S \setminus \{s, s'\}$, $\displaystyle \sum_{a \in A\ \mathrm{tq}\ ex(a) = t} \mathcal{I}_c(a) - \sum_{a \in A\ \mathrm{tq}\ or(a) = t} \mathcal{I}_c(a) = 0$,
- $\displaystyle \sum_{a \in A\ \mathrm{tq}\ ex(a) = s} \mathcal{I}_c(a) - \sum_{a \in A\ \mathrm{tq}\ or(a) = s} \mathcal{I}_c(a) = -1$,
- $\displaystyle \sum_{a \in A\ \mathrm{tq}\ ex(a) = s'} \mathcal{I}_c(a) - \sum_{a \in A\ \mathrm{tq}\ or(a) = s'} \mathcal{I}_c(a) = 1$.

**Réponse 21.** Posons $c = a_1 \cdots a_k = \langle s_0, s_1 \rangle \cdots \langle s_{k-1}, s_k \rangle$.

(I) Le graphe $G_{\mathcal{I}_c} = \langle S', A' \rangle$ satisfait $S' = \{s_0, \ldots, s_k\}$ et $\{a_1, \ldots, a_k\} = A'$. Prenons $t, t' \in S'$. Il existe $i, j$ tels que $t = s_i$ et $t' = s_j$. Si $i = j$, le chemin vide va de $t$ vers $t$. Si $i < j$ [resp. $j < i$] alors $a_{i+1} \cdots a_j$ est un chemin de $t$ vers $t'$ [resp. $t'$ vers $t$] dans $G_{\mathcal{I}_c}$. Par conséquent, $G_{\mathcal{I}_c}$ est connexe.

(II) Supposons $s = s'$. Pour chaque $j \in [1, k - 1]$, il y a dans le chemin $c$, un arc entrant dans $s_j$ (l'arc $a_j$) et un arc sortant de $s_j$ (l'arc $a_{j+1}$). Pour chaque $t$ n'apparaissant pas sur le chemin $c$, aucun arc n'entre en $t$ et aucun arc ne sort de $t$. Par ailleurs, $a_1$ sort de $s_0$ et $a_k$ entre en $s_k = s_0$, ce qui permet de conclure que (II) est vérifié.

(III) La preuve est analogue à celle pour la condition (III).

**Question 22.** Soient $G = \langle S, A \rangle$ un graphe orienté fini et $\mathcal{I} : A \to \mathbb{N}$ une fonction. Montrer que $\mathcal{I}$ est l'image d'un chemin dans $G$ si et seulement s'il existe $s, s' \in S$ tels que les conditions (I), (II) et (III) de la question 21 soient vérifiées.

**Réponse 22.** Il reste à montrer que si $\mathcal{I} : A \to \mathbb{N}$ vérifie (I), (II) et (III) pour un couple $s, s' \in S$ alors $\mathcal{I}$ est l'image d'un chemin de $s$ vers $s'$. Dans la suite on supposera que $s \neq s'$ et donc que $\mathcal{I}$ vérifie non trivialement (I) et (III) (le cas $s = s'$ se traite de façon analogue). Nous avons donc :

- $G_{\mathcal{I}}$ est connexe,
- pour $t \in S \setminus \{s, s'\}$, $\displaystyle \sum_{a \in A\ \mathrm{tq}\ ex(a) = t} \mathcal{I}_c(a) - \sum_{a \in A\ \mathrm{tq}\ or(a) = t} \mathcal{I}_c(a) = 0$,
- $\displaystyle \sum_{a \in A\ \mathrm{tq}\ ex(a) = s} \mathcal{I}_c(a) - \sum_{a \in A\ \mathrm{tq}\ or(a) = s} \mathcal{I}_c(a) = -1$,
- $\displaystyle \sum_{a \in A\ \mathrm{tq}\ ex(a) = s'} \mathcal{I}_c(a) - \sum_{a \in A\ \mathrm{tq}\ or(a) = s'} \mathcal{I}_c(a) = 1$.

Un chemin $c$ est dit fermé lorsque $ex(c) = or(c)$.

Soit $c_1, c_2, \ldots, c_p, c_{p+1}, \ldots, c_N$ une séquence de chemins telle que

- $\mathcal{I}_{c_1} + \cdots + \mathcal{I}_{c_N} = \mathcal{I}$,
- $c_1, c_2, \ldots, c_p$ sont des chemins non fermés,
- $c_{p+1}, \ldots, c_N$ sont des chemins fermés.

Une telle séquence existe toujours, en prenant par exemple $p = \sum_{a \in A} \mathcal{I}(a)$, $N = p$ et chaque chemin $c_i$ est réduit à un seul arc. Nous allons montrer que la valeur minimale de $N$ pour une telle séquence est exactement 1.

Comme $c_{p+1}, \ldots, c_N$ est une séquence de chemins fermés, pour $j \in [p + 1, N]$ et pour $t \in S$, $\displaystyle \sum_{a \in A\ \mathrm{tq}\ ex(a) = t} \mathcal{I}_{c_j}(a) - \sum_{a \in A\ \mathrm{tq}\ or(a) = t} \mathcal{I}_{c_j}(a) = 0$. Par conséquent, nous avons donc

- pour $t \in S \setminus \{s, s'\}$,

$$\sum_{a \in A\ \mathrm{tq}\ ex(a) = t} \sum_{j \in [1, p]} \mathcal{I}_{c_j}(a) - \sum_{a \in A\ \mathrm{tq}\ or(a) = t} \sum_{j \in [1, p]} \mathcal{I}_{c_j}(a) = 0,$$

- $\displaystyle \sum_{a \in A\ \mathrm{tq}\ ex(a) = s} \sum_{j \in [1, p]} \mathcal{I}_{c_j}(a) - \sum_{a \in A\ \mathrm{tq}\ or(a) = s} \sum_{j \in [1, p]} \mathcal{I}_{c_j}(a) = -1$,
- $\displaystyle \sum_{a \in A\ \mathrm{tq}\ ex(a) = s'} \sum_{j \in [1, p]} \mathcal{I}_{c_j}(a) - \sum_{a \in A\ \mathrm{tq}\ or(a) = s'} \sum_{j \in [1, p]} \mathcal{I}_{c_j}(a) = 1$.

Par conséquent, pour $t \in S \setminus \{s, s'\}$, si $t = ex(c_j)$ pour un $j \in [1, p]$ alors il existe $j' \in [1, p]$ tel que $or(c_{j'}) = t$ ($j \neq j'$ car les chemins dans $c_1, c_2, \ldots, c_p$ ne sont pas fermés). Ainsi, si $p > 1$, alors il existe $t \in S \setminus \{s, s'\}$, tel que $t = ex(c_j)$ pour un $j \in [1, p]$. Il existe donc $j' \in [1, p]$ tel que $or(c_{j'}) = t$. On remarque alors que la séquence obtenue en remplaçant $c_j, c_{j'}$ par $c_j c_{j'}$ vérifie les contraintes d'une telle séquence mais est de longueur $N - 1$, ce qui contredit la minimalité de $N$.

Ainsi $p = 1$. Soit donc une séquence $c_1, c_2, \ldots, c_N$ telle que $c_1$ est un chemin non fermé de $s$ vers $s'$, et $c_2, \ldots, c_N$ est une séquence de chemins fermés. Si aucun sommet apparaissant dans les arcs de $c_2, \ldots, c_N$ n'apparaît aussi dans $c_1$, cela contredit la connexité de $G_{\mathcal{I}}$. Ainsi, il existe $j \in [2, N]$ tel que $c_1$ et $c_j$ partage un sommet. D'après la question 20, il existe un chemin $c$ de $s$ vers $s'$ tel que $\mathcal{I}_c = \mathcal{I}_{c_1} + \mathcal{I}_{c_2}$. On remarque alors que la séquence obtenue en remplaçant $c_1, c_j$ par $c$ vérifie les contraintes d'une telle séquence mais est de longueur $N - 1$, ce qui contredit la minimalité de $N$. Ainsi $p = N = 1$.

En conclusion, $\mathcal{I}$ est l'image d'un chemin de $s$ vers $s'$.

**Question 23.** Soient $\mathcal{B}_0, \mathcal{B}_1, \mathcal{B}_2 \in \mathbb{Z}^{N \times \alpha}$ et $b_0, b_1, b_2 \in \mathbb{Z}^N$. Définir un algorithme pour déterminer s'il existe $y \in \mathbb{N}^{\alpha}$ tel que $\mathcal{B}_0\, y \ge b_0$, $\mathcal{B}_1\, y > b_1$ et $\mathcal{B}_2\, y = b_2$ en utilisant la fonction $\mathrm{SOL}^+$.

**Réponse 23.** Nous avons $\mathcal{B}_1\, y > b_1$ si et seulement s'il existe $i \in [1, N]$ tel que $\mathcal{B}_1\, y \ge (b_1 + e_i)$. De même, $\mathcal{B}_2\, y = b_2$ si et seulement si $\mathcal{B}_2\, y \ge b_2$ et $(-\mathcal{B}_2)\, y \ge (-b_2)$ avec $(-\mathcal{B}_2) = (-b^2_{i, j})$ lorsque $\mathcal{B}_2 = (b^2_{i, j})$ et $(-b_2)(i) = -b_2(i)$. Ainsi, il existe $y \in \mathbb{N}^{\alpha}$ tel que $\mathcal{B}_0\, y \ge b_0$, $\mathcal{B}_1\, y > b_1$ et $\mathcal{B}_2\, y = b_2$ si et seulement s'il existe $i \in [1, N]$ tel que

- $\mathcal{B}_0\, y \ge b_0$,
- $\mathcal{B}_1\, y \ge (b_1 + e_i)$,
- $\mathcal{B}_2\, y \ge b_2$ et $(-\mathcal{B}_2)\, y \ge (-b_2)$.

Chaque système a au plus $4N$ équations, le nombre de variables est toujours $\alpha$ et la constante maximale est $\beta + 1$ si $\beta$ est la constante maximale pour $\mathcal{B}_0, \mathcal{B}_1, \mathcal{B}_2, b_0, b_1, b_2$. L'existence de $y$ consiste à vérifier si l'un des $N$ systèmes admet une solution en utilisant à chaque fois $\mathrm{SOL}^+$.

**Question 24.** Soit $G = \langle S, A \rangle$ et $G' = \langle S', A' \rangle$ deux graphes orientés finis tels que $S' \subseteq S$, $\emptyset \subset A' \subseteq A$ et $G'$ est connexe ($G'$ est un sous-graphe de $G$). Soient $\mathcal{B} = (b_{i, j}) \in \mathbb{Z}^{\alpha \times \mathrm{card}(A')}$ une matrice avec $\alpha > 0$ et $b \in \mathbb{Z}^{\alpha}$. À l'aide de la procédure $\mathrm{SOL}^+$, définir un algorithme qui détermine s'il existe un chemin $c$ dans $G$ tel que

- $G_{\mathcal{I}_c} = G'$,
- $\mathcal{B} x \ge b$ avec $x \in \mathbb{N}^{\mathrm{card}(A')}$ et pour $i \in \{1, \ldots, \mathrm{card}(A')\}$, $x(i) = \mathcal{I}_c(\rho(i))$, étant donnée une bijection arbitraire $\rho : \{1, \ldots, \mathrm{card}(A')\} \to A'$ (contrainte sur l'image de $c$).

**Réponse 24.** Pour chaque arc $a \in A'$, nous introduisons la variable $x_{\rho(a)}$. Les équations ou inéquations suivantes doivent être vérifiées :

- $\mathcal{B} \begin{pmatrix} x_1 \\ \vdots \\ x_{\mathrm{card}(A')} \end{pmatrix} \ge b$,
- pour $a \in A'$, $x_{\rho(a)} \ge 1$ et pour $a \in A \setminus A'$, $x_{\rho(a)} = 0$,
- une des deux conditions ci-dessous est vérifiée :
  - pour $t \in S'$,

$$\sum_{a \in A'\ \mathrm{tq}\ ex(a) = t} x_{\rho(a)} - \sum_{a \in A'\ \mathrm{tq}\ or(a) = t} x_{\rho(a)} = 0,$$

  - il existe $s \neq s' \in S'$ tels que
    - pour $t \in S' \setminus \{s, s'\}$,

$$\sum_{a \in A'\ \mathrm{tq}\ ex(a) = t} x_{\rho(a)} - \sum_{a \in A'\ \mathrm{tq}\ or(a) = t} x_{\rho(a)} = 0,$$

    - $\displaystyle \sum_{a \in A'\ \mathrm{tq}\ ex(a) = s} x_{\rho(a)} - \sum_{a \in A'\ \mathrm{tq}\ or(a) = s} x_{\rho(a)} = -1$,
    - $\displaystyle \sum_{a \in A'\ \mathrm{tq}\ ex(a) = s'} x_{\rho(a)} - \sum_{a \in A'\ \mathrm{tq}\ or(a) = s'} x_{\rho(a)} = 1$.

Comme la connexité est garantie par la condition « pour $a \in A'$, $x_{\rho(a)} \ge 1$ et pour $a \in A \setminus A'$, $x_{\rho(a)} = 0$ » (en effet $G'$ est connexe), l'existence d'un chemin revient à évoquer $\mathrm{SOL}^+$ pour au plus $\mathrm{card}(S')^2$ systèmes (correspondant aux différentes origines et extrémités possibles du chemin) et en se ramenant à seulement des inéquations comme cela est fait dans la réponse de la question 23.

**Question 25.** Soit $x_0 \ldots x_k$ une promenade auto-couvrante. Montrer que pour $\Delta \in \mathbb{Z}^n$, $(x_0 + \Delta) \ldots (x_k + \Delta)$ est aussi auto-couvrante.

**Réponse 25.** Il existe $l \in [0, k - 1]$ tel que $x_l \prec x_k$. Pour $j \in [1, k]$, $x_j - x_{j-1} = (x_j + \Delta) - (x_{j-1} + \Delta) \in T$ et donc $(x_0 + \Delta) \ldots (x_k + \Delta)$ est aussi une promenade. En particulier, $(x_k - x_l) = (x_k + \Delta) - (x_l + \Delta)$ et $\langle 0, \ldots, 0 \rangle \prec (x_k - x_l)$, par conséquent $(x_0 + \Delta) \ldots (x_k + \Delta)$ est aussi auto-couvrante.

**Question 26.** Soient $r > 0$, $I \subseteq [1, n]$ et $\mathcal{S} = \langle S, T', n \rangle$ un SAVE tels que

- $S \subseteq [0, r - 1]^{\mathrm{card}(I)}$,
- pour $s, s' \in S$ et $\mathrm{tr} \in T$, nous avons $s \xrightarrow{\mathrm{tr}} s' \in T'$ si et seulement si $s + \mathrm{tr}_I = s'$,
- $\left\langle S, \bigl\{ (s, s') \in S \times S : \exists\, \mathrm{tr} \in T,\ s \xrightarrow{\mathrm{tr}} s' \bigr\} \right\rangle$ est connexe.

Montrer que s'il existe un pseudo-calcul $\langle s_0, x_0 \rangle \ldots \langle s_k, x_k \rangle$ dans $\mathcal{S}$ tel que $\{s_0, \ldots, s_k\} = S$, $(x_0)_I = s_0$ et $x_0 \prec x_k$, alors il existe un pseudo-calcul $\langle s'_0, x'_0 \rangle \ldots \langle s'_{k'}, x'_{k'} \rangle$ dans $\mathcal{S}$ tel que

3. $s'_0 = s_0$, $x'_0 = x_0$, $s'_{k'} = s_k$ et $x'_0 \prec x'_{k'}$,
4. $k' \le \mathcal{F}(n, r, \mathrm{taille}(T))$ où $\mathcal{F}(n, r, \mathrm{taille}(T))$ est une expression à définir, construite à partir de fonctions polynômes, exponentielles et de constantes (indépendantes des arguments).

On pourra par exemple chercher à majorer $\mathcal{F}(n, r, \mathrm{taille}(T))$ par $\bigl( r^{2n} \times 2^{\mathrm{taille}(T)} \bigr)^{C \times (2 \times r^{2n} + n + 1)}$.

**Réponse 26.** Soit $\langle s_0, x_0 \rangle \ldots \langle s_k, x_k \rangle$ un pseudo-calcul vérifiant les hypothèses. On peut commencer par remarquer que pour $j \in [0, k]$, $(x_j)_I = s_j$. Soit $G = \langle S, A \rangle$ le graphe orienté fini tel que

$$A = \left\{ \langle s, s' \rangle \in S \times S : \exists\, \mathrm{tr} \in T,\ s \xrightarrow{\mathrm{tr}} s' \right\}.$$

Par hypothèse, $G$ est connexe.

Soit $X$ l'ensemble de triplets $\langle \mathrm{tr}, s, s' \rangle$ pour lesquels il existe $j \in [0, k - 1]$ vérifiant $x_j + \mathrm{tr} = x_{j+1}$ et $\langle s, s' \rangle = \langle (x_j)_I, (x_{j+1})_I \rangle$. Soit $\mathcal{I}$ l'image du chemin $\langle s_0, s_1 \rangle \cdots \langle s_{k-1}, s_k \rangle$ dans $G$ et $\mathcal{I}' : X \to \mathbb{N}$ l'image « étendue » telle que pour $\langle \mathrm{tr}, s, s' \rangle \in X$, $\mathcal{I}'(\langle \mathrm{tr}, s, s' \rangle)$ est égale à $\mathrm{card}\bigl( \{ j \in [0, k - 1] : x_j + \mathrm{tr} = x_{j+1} \} \bigr)$. On peut observer que pour $\langle s, s' \rangle \in A$, nous avons

$$\mathcal{I}(\langle s, s' \rangle) = \sum_{s \xrightarrow{\mathrm{tr}} s' \in T'} \mathcal{I}'(\langle \mathrm{tr}, s, s' \rangle).$$

Pour chaque triplet $\langle \mathrm{tr}, s, s' \rangle \in X$, nous considérons la variable $x^{\mathrm{tr}}_{s, s'}$. Par abus de notation, une image étendue $\mathcal{I}' : X \to \mathbb{N}$ sera considérée comme un tuple dans $\mathbb{N}^{\mathrm{card}(X)}$. Le cardinal de $\mathrm{card}(X)$ est majoré par $\mathrm{card}(T) \times r^{2n}$, ce qui va correspondre au nombre de variables du système qui va être construit.

Par construction de $X$, pour $\langle s, s' \rangle \in A$,

$$\sum_{s \xrightarrow{\mathrm{tr}} s' \in T'} \mathcal{I}'(\langle \mathrm{tr}, s, s' \rangle) \ge 1.$$

Par conséquent, pour $\langle s, s' \rangle \in A$, l'image étendue $\mathcal{I}'$ est solution de l'équation

$$\sum_{s \xrightarrow{\mathrm{tr}} s' \in T'} x^{\mathrm{tr}}_{s, s'} \ge 1.$$

Le nombre d'inéquations de ce type est majoré par $r^{2n}$.

Comme $x_0 \prec x_k$, il existe $i \in [1, n]$ tel que

- pour $i' \in [1, n] \setminus \{i\}$, $\displaystyle \sum_{\langle \mathrm{tr}, s, s' \rangle \in X} \mathcal{I}'(\langle \mathrm{tr}, s, s' \rangle)\, \mathrm{tr}(i') \ge 0$,
- $\displaystyle \sum_{\langle \mathrm{tr}, s, s' \rangle \in X} \mathcal{I}'(\langle \mathrm{tr}, s, s' \rangle)\, \mathrm{tr}(i) \ge e_i$.

Par conséquent, l'image étendue $\mathcal{I}'$ est solution des équations suivantes pour un $i \in [1, n]$ :

- pour $i' \in [1, n] \setminus \{i\}$, $\displaystyle \sum_{\langle \mathrm{tr}, s, s' \rangle \in X} x^{\mathrm{tr}}_{s, s'}\, \mathrm{tr}(i') \ge 0$,
- $\displaystyle \sum_{\langle \mathrm{tr}, s, s' \rangle \in X} x^{\mathrm{tr}}_{s, s'}\, \mathrm{tr}(i) \ge e_i$.

Le nombre d'inéquations de ce type est égale à $n$.

D'après la question 21, si $s_0 = s_k$ alors pour $s \in S$,

$$\sum_{\langle \mathrm{tr}, s, s' \rangle \in X} \mathcal{I}'(\langle \mathrm{tr}, s, s' \rangle) - \sum_{\langle \mathrm{tr}, s', s \rangle \in X} \mathcal{I}'(\langle \mathrm{tr}, s', s \rangle) = 0.$$

Par conséquent, pour $s \in S$, l'image étendue $\mathcal{I}'$ est solution de l'équation

$$\sum_{\langle \mathrm{tr}, s, s' \rangle \in X} x^{\mathrm{tr}}_{s, s'} - \sum_{\langle \mathrm{tr}, s', s \rangle \in X} x^{\mathrm{tr}}_{s', s} = 0.$$

Le nombre d'équations de la sorte est majoré par $r^n$, ce qui correspond à $2 r^n$ inéquations.

Lorsque $s_0 \neq s_k$, pour $s \in S \setminus \{s_0, s_k\}$, l'image étendue $\mathcal{I}'$ est solution de l'équation

$$\sum_{\langle \mathrm{tr}, s, s' \rangle \in X} x^{\mathrm{tr}}_{s, s'} - \sum_{\langle \mathrm{tr}, s', s \rangle \in X} x^{\mathrm{tr}}_{s', s} = 0.$$

De même, l'image étendue $\mathcal{I}'$ est solution des équations :

- $\displaystyle \sum_{\langle \mathrm{tr}, s_0, s' \rangle \in X} x^{\mathrm{tr}}_{s_0, s'} - \sum_{\langle \mathrm{tr}, s', s_0 \rangle \in X} x^{\mathrm{tr}}_{s', s_0} = 1$,
- $\displaystyle \sum_{\langle \mathrm{tr}, s_1, s' \rangle \in X} x^{\mathrm{tr}}_{s_1, s'} - \sum_{\langle \mathrm{tr}, s', s_1 \rangle \in X} x^{\mathrm{tr}}_{s', s_1} = -1$.

Soit un des $n$ systèmes d'inéquations décrit ci-dessous avec au plus

- $\mathrm{card}(T) \times r^{2n}$ variables,
- $r^{2n} + 2 r^n + n$ inéquations.

De plus $\beta \le \max\bigl( \mathrm{card}(T) \times r^{2n},\ \lVert T \rVert_{\max},\ 1 \bigr) \le 2^{\mathrm{taille}(T)} r^{2n}$. $\mathcal{I}'$ est donc solution d'un de ces systèmes. Par Borosh & Treybig, si un de ces systèmes admet une solution entière positive, il existe une solution dont chaque composante est bornée par

$$\bigl( 2^{\mathrm{taille}(T)} r^{2n} \bigr)^{C(2 r^{2n} + n)}.$$

Soit $\mathcal{I}'_0$ une petite solution (et on sait qu'elle existe car $\mathcal{I}'$ est aussi solution). Nous posons $k' = \sum_{\langle \mathrm{tr}, s, s' \rangle \in X} x^{\mathrm{tr}}_{s, s'}$ et donc $k' \le 2^{\mathrm{taille}(T)\, r^{2n}} \times \bigl( 2^{\mathrm{taille}(T)} r^{2n} \bigr)^{C(2 r^{2n} + n)}$. Notre majorant de $\mathcal{F}(n, r, \mathrm{taille}(T))$ sera donc

$$\bigl( 2^{\mathrm{taille}(T)} r^{2n} \bigr)^{C(2 r^{2n} + n + 1)}.$$

On peut construire la fonction $\mathcal{I}_0 : A \to \mathbb{N}$ telle que pour $\langle s, s' \rangle \in A$, nous ayons $\mathcal{I}_0(\langle s, s' \rangle) = \sum_{s \xrightarrow{\mathrm{tr}} s' \in T'} \mathcal{I}'_0(\langle \mathrm{tr}, s, s' \rangle)$. Comme pour $\langle s, s' \rangle \in A$ nous avons

$$\sum_{s \xrightarrow{\mathrm{tr}} s' \in T'} \mathcal{I}'_0(\langle \mathrm{tr}, s, s' \rangle) \ge 1,$$

nous pouvons conclure que $\mathcal{I}_0(\langle s, s' \rangle) \ge 1$. Ainsi $G_{\mathcal{I}_0} = G$ est connexe. Dans le cas $s_0 = s_k$ (l'autre cas admet un traitement analogue), nous avons aussi pour $s \in S$,

$$\sum_{a \in A\ \mathrm{tq}\ or(a) = s} \mathcal{I}_0(a) - \sum_{a \in A\ \mathrm{tq}\ ex(a) = s} \mathcal{I}_0(a) = 0.$$

Par conséquent, par la question 22 et la définition de $\mathcal{I}_0$ à partir de $\mathcal{I}'_0$, il existe une séquence $s'_0 \mathrm{tr}_1 s'_1 \cdots \mathrm{tr}_{k'} s'_{k'}$ telle que

- $c = \langle s'_0, s'_1 \rangle \cdots \langle s'_{k'-1}, s'_{k'} \rangle$ est un chemin dans $G$ tel que $\mathcal{I}_c = \mathcal{I}_0$,
- $s_0 = s_k = s'_0 = s'_{k'}$,
- pour $j \in [0, k' - 1]$, $\langle \mathrm{tr}_{j+1}, s_j, s_{j+1} \rangle \in X$,
- pour $\langle \mathrm{tr}, s, s' \rangle \in X$, nous avons

$$\mathcal{I}'_0(\langle \mathrm{tr}, s, s' \rangle) = \mathrm{card}\bigl( \{ j \in [0, k' - 1] : \langle \mathrm{tr}, s, s' \rangle = \langle \mathrm{tr}_{j+1}, s_j, s_{j+1} \rangle \} \bigr).$$

Par conséquent $\langle \mathrm{tr}_1 \cdots \mathrm{tr}_{k'}, x_0 \rangle$ est une promenade $I$-$r$-admissible. Finalement, il existe $i \in [1, n]$ tel que

- pour $i' \in [1, n] \setminus \{i\}$, $\displaystyle \sum_{j \in [1, k']} \mathrm{tr}_j(i') \ge 0$,
- $\displaystyle \sum_{j \in [1, k']} \mathrm{tr}_j(i) \ge e_i$.

Ainsi si $x'_{k'}$ est la dernière configuration de $\langle \mathrm{tr}_1 \cdots \mathrm{tr}_{k'}, x_0 \rangle$ alors $x_0 \prec x'_{k'}$. De plus,

$$\langle (x_0)_I, x_0 \rangle \cdots \langle (x_0 + \mathrm{tr}_1 + \cdots + \mathrm{tr}_{k'})_I,\ x_0 + \mathrm{tr}_1 + \cdots + \mathrm{tr}_{k'} \rangle$$

est un pseudo-calcul de $\mathcal{S}$ vérifiant les propriétés annoncées.

**Question 27.** Soient $I \subseteq [1, n]$ et $r > 1$ tels qu'il existe une promenade $x_0 \ldots x_k$ $I$-$r$-admissible et auto-couvrante. Montrer qu'il existe alors une telle promenade commençant en $x_0$ de longueur au plus $r^{\mathrm{card}(I)} + \mathcal{F}(n, r, \mathrm{taille}(T))$.

**Réponse 27.** Soit $x_0 \cdots x_k$ une promenade $I$-$r$-admissible et auto-couvrante avec $x_l \prec x_k$ (et donc $l \in [0, k - 1]$). D'après la question 11, il existe une séquence $j_1, \ldots, j_{\alpha}$ telle

- $1 \le j_1 < \cdots < j_{\alpha} \le l$,
- $\alpha < r^{\mathrm{card}(I)}$,
- $\langle \mathrm{tr}_{j_1} \cdots \mathrm{tr}_{j_{\alpha}}, x_0 \rangle = y_0 \cdots y_{\alpha}$ est une promenade $I$-$r$-admissible,
- $(y_{\alpha})_I = (x_l)_I$.

Considérons la promenade $y_0 \cdots y_{\alpha} \cdots y_{\alpha + (k - l)}$ induite par le chemin $\mathrm{tr}_{j_1} \cdots \mathrm{tr}_{j_{\alpha}} \mathrm{tr}_{l+1} \cdots \mathrm{tr}_k$. Cette promenade est $I$-$r$-admissible et auto-couvrante car $y_{\alpha} \prec y_{k + (k - l)}$.

Construisons le SAVE $\mathcal{S} = \langle S, T', n \rangle$ suivant :

- $S = \{ s \in [0, r - 1]^{\mathrm{card}(I)} : \exists\, j \in [\alpha, k + (k - l)]\ (y_j)_I = s \}$,
- pour chaque $s, s' \in S$, s'il existe $j \in [\alpha, k + (k - l) - 1]$ tel que $\langle s, s' \rangle = \langle (y_j)_I, (y_{j+1})_I \rangle$ alors pour $\mathrm{tr} \in T$, $s \xrightarrow{\mathrm{tr}} s' \in T'$ si et seulement si $s + \mathrm{tr}_I = s'$.

Comme $y_0 \cdots y_{\alpha} \cdots y_{k + (k - l)}$ est une promenade $I$-$r$-admissible, $\bigl\langle S, \bigl\{ \langle s, s' \rangle \in S \times S : \exists\, \mathrm{tr} \in T,\ s \xrightarrow{\mathrm{tr}} s' \bigr\} \bigr\rangle$ est connexe. La promenade $y_{\alpha} \cdots y_{k + (k - l)}$ peut être vue comme la séquence suivante de configurations dans $\mathcal{S}$ :

$$\langle (y_{\alpha})_I, y_{\alpha} \rangle \cdots \langle (y_{k + (k - l)})_I,\ y_{k + (k - l)} \rangle$$

avec $y_{\alpha} \prec y_{k + (k - l)}$. Les hypothèses de la question 26 sont vérifiées. Il existe donc une séquence de configurations $\langle s_0, z_0 \rangle \ldots \langle s_{l'}, z_{l'} \rangle$ telle que

- $z_0 = y_{\alpha}$, $s_0 = (y_{\alpha})_I$, $s_{l'} = (y_{k + (k - l)})_I$ et $z_0 \prec z_{l'}$,
- pour $j \in [0, l' - 1]$, il existe $s_j \xrightarrow{\mathrm{tr}} s_{j+1} \in T'$ telle $z_j + \mathrm{tr} = z_{j+1}$,
- $l' \le \mathcal{F}(n, r, \mathrm{taille}(T))$.

La séquence $y_0 \cdots y_{\alpha - 1} z_0 \cdots z_{l'}$ est donc une promenade $I$-$r$-admissible, auto-couvrante et de longueur inférieure à $r^{\mathrm{card}(I)} + \mathcal{F}(n, r, \mathrm{taille}(T))$.

**Question 28.** Majorer $G(0)$ en fonction de $n$ et $\mathrm{taille}(T)$.

**Réponse 28.** Commençons par une définition utile. Si $c = \mathrm{tr}_1 \ldots \mathrm{tr}_k$ est un chemin, l'effet de ce chemin, dénoté par $\mathrm{ef}(c)$, est la somme $\mathrm{tr}_1 + \cdots + \mathrm{tr}_k$. Par convention, l'effet de la séquence vide $\varepsilon$ est égal à $\langle 0, \ldots, 0 \rangle \in \mathbb{Z}^n$.

Pour toute configuration $x \in \mathbb{Z}^n$, il existe une promenade $\langle c, x \rangle$ $\emptyset$-admissible et auto-couvrante si et seulement s'il existe $i \in [1, n]$ tel que le système ci-dessous (indépendant de $x$) ait une solution :

$$\sum_{\mathrm{tr} \in T} x_{\mathrm{tr}} \times \mathrm{tr} \ge e_i$$

où pour chaque transition $\mathrm{tr}$, on associe une variable $x_{\mathrm{tr}}$. En effet, si $x_0 \cdots x_k$ est $\emptyset$-admissible et auto-couvrante induite par le chemin $\mathrm{tr}_1 \cdots \mathrm{tr}_k$ alors il existe $l < k$ tel que $\langle 0, \ldots, 0 \rangle \prec \mathrm{ef}(\mathrm{tr}_{l+1} \cdots \mathrm{tr}_k)$ et donc la promenade $\langle \mathrm{tr}_{l+1} \cdots \mathrm{tr}_k, x_0 \rangle$ est aussi $\emptyset$-admissible et auto-couvrante. D'après le résultat de Borosh et Treybig, si ce système admet une solution entière positive alors il existe une solution entière positive dont toutes les valeurs sont bornées par

$$\max\bigl( \lVert T \rVert_{\max},\ \mathrm{card}(T),\ 1 \bigr)^{C \times n}.$$

Comme $\lVert T \rVert_{\max}, \mathrm{card}(T) \le 2^{\mathrm{taille}(T)}$, on obtient $G(0) \le 2^{\mathrm{taille}(T) \times C \times n}$.

**Question 29.** Pour $\emptyset \subset I \subseteq [1, n]$, majorer $g(I)$ en fonction de $g_{\subset}(I)$, $\mathrm{pic}(T)$, $\mathrm{taille}(T)$ et $n$. On pourra par exemple montrer $g(I) \le \bigl( \mathrm{pic}(T) g_{\subset}(I) \bigr)^{\mathrm{card}(I)} + \mathcal{F}\bigl( n, \mathrm{pic}(T) g_{\subset}(I), \mathrm{taille}(T) \bigr)$.

**Réponse 29.** Soit $x_0 \cdots x_k$ une promenade $I$-admissible et auto-couvrante avec $x_l \prec x_k$ (et donc $l \in [0, k - 1]$).

Si $x_0 \cdots x_k$ est $I$-$(\mathrm{pic}(T) g_{\subset}(I))$-admissible alors d'après la question 27, il existe une promenade $y_0 \cdots y_{l'}$ $I$-admissible et auto-couvrante avec

$$l' \le \bigl( \mathrm{pic}(T) g_{\subset}(I) \bigr)^{\mathrm{card}(I)} + \mathcal{F}\bigl( n, \mathrm{pic}(T) g_{\subset}(I), \mathrm{taille}(T) \bigr)$$

et $x_0 = y_0$.

Si $x_0 \cdots x_k$ n'est pas $I$-$(\mathrm{pic}(T) g_{\subset}(I))$-admissible alors il existe $l' \le k$ et $\emptyset \subset I' \subseteq I$ tels que la première configuration dont une valeur est supérieure ou égale à $\mathrm{pic}(T) g(I')$ est $l'$, et $(I \setminus I')$ est l'ensemble de composantes de $x_{l'}$ atteignant au moins cette valeur.

Considérons la promenade $y_0 \cdots y_{k + (k - l)}$ induite par le chemin $\mathrm{tr}_1 \cdots \mathrm{tr}_k \mathrm{tr}_{l+1} \cdots \mathrm{tr}_k$ et dont $y_0 = x_0$. Par définition, pour chaque position $j \in [0, k]$, $y_j = x_j$, et $y_k \prec y_{k + (k - l)}$. On peut donc facilement vérifier que $y_0 \cdots y_{k + (k - l)}$ est une promenade $I$-admissible et auto-couvrante aussi. D'après la question 11, il existe une séquence $j_1, \ldots, j_{\alpha}$ telle

- $1 \le j_1 < \cdots < j_{\alpha} \le l'$,
- $\alpha < \bigl( \mathrm{pic}(T) g(I') \bigr)^{\mathrm{card}(I)} \le \bigl( \mathrm{pic}(T) g_{\subset}(I) \bigr)^{\mathrm{card}(I)}$,
- $\langle \mathrm{tr}_{j_1} \cdots \mathrm{tr}_{j_{\alpha}}, y_0 \rangle = z_0 \cdots z_{\alpha}$ est une promenade $I$-$(\mathrm{pic}(T) g_{\subset}(I))$-admissible,
- $(z_{\alpha})_I = (y_{l'})_I = (x_{l'})_I$.

Considérons la promenade $z_0 \cdots z_{\alpha} \cdots z_{k + (k - l) - l'}$ induite par le chemin

$$\mathrm{tr}_{j_1} \cdots \mathrm{tr}_{j_{\alpha}} \mathrm{tr}_{l' + 1} \cdots \mathrm{tr}_k \mathrm{tr}_{l + 1} \cdots \mathrm{tr}_k.$$

Cette promenade est $I$-admissible et auto-couvrante car $z_{\alpha + (k - l')} \prec z_{2k - l - l'}$.

Par définition de $g(I')$, il existe une promenade $z'_0 \cdots z'_{\beta}$ $I'$-admissible, auto-couvrante et telle que $\beta \le g(I')$ et $z'_0 = z_{\alpha}$. Comme $(z_{\alpha})_I = (y_{l'})_I = (x_{l'})_I$, pour $i \in (I \setminus I')$, $z'_0(i) \ge \mathrm{pic}(T) g(I')$. Par conséquent la séquence

$$z_0 \cdots z_{\alpha} z'_1 \cdots z'_{\beta}$$

est une promenade $I$-admissible, auto-couvrante et de longueur bornée par

$$\alpha + \beta \le \bigl( \mathrm{pic}(T) g(I') \bigr)^{\mathrm{card}(I)} + g(I') \le \bigl( \mathrm{pic}(T) g_{\subset}(I) \bigr)^{\mathrm{card}(I)} + \mathcal{F}\bigl( n, \mathrm{pic}(T) g_{\subset}(I), \mathrm{taille}(T) \bigr)$$

(car $r < F(n, r, \mathrm{taille}(T))$).

**Question 30.** Définir un algorithme qui prenne en entrée un SAV $T$ et une configuration admissible et qui détermine si l'ensemble des configurations positivement accessibles de $x$ est infini.

**Réponse 30.** On a vu qu'étant donnés un SAV $T$ et une configuration initiale $x \in \mathbb{N}^n$, l'ensemble des configurations positivement accessibles de $x$ est infini si et seulement s'il existe une promenade positive de longueur inférieure à $G(n)$ et auto-couvrante dont la configuration initiale est $x$.

L'algorithme commence par majorer $G(n)$ en utilisant le fait que

$$G(0) \le 2^{\mathrm{taille}(T) \times C \times n}$$

et pour $m \in [1, n]$, $G(m) \le \bigl( \mathrm{pic}(T) G(m - 1) \bigr)^m + \mathcal{F}\bigl( n, \mathrm{pic}(T) G(m - 1), \mathrm{taille}(T) \bigr)$. Posons $G'(0) = 2^{\mathrm{taille}(T) \times C \times n}$ et $G'(m) = \bigl( \mathrm{pic}(T) G'(m - 1) \bigr)^m + \mathcal{F}\bigl( n, \mathrm{pic}(T) G'(m - 1), \mathrm{taille}(T) \bigr)$ pour $m \in [1, n]$.

Le nombre de chemins ayant $G'(n)$ transitions est fini et est égal à $\mathrm{card}(T)^{G'(n)}$. S'il existe un chemin $c = \mathrm{tr}_1 \ldots \mathrm{tr}_{G'(n)}$ avec $\langle c, x \rangle = x_0 \cdots x_{G'(n)}$ tel qu'il existe $l, l' \le G'(n)$ vérifiant $x_l \prec x_{l'}$ et $x_0 \cdots x_{l'}$ est une promenade positive alors l'ensemble des configurations positivement accessibles est infini.

La valeur positive maximale d'une position sur un tel chemin est $\max(x) + \lVert T \rVert_{\max} G'(n)$ et donc chaque somme nécessite un temps de calcul en $\mathcal{O}\bigl( n \bigl( \log(\lVert T \rVert_{\max}) + \log(\max(x) + \lVert T \rVert_{\max} G'(n)) \bigr) \bigr)$. La vérification pour chaque chemin de la propriété peut se faire en temps de calcul en $\mathcal{O}\bigl( G'(n) \times \bigl( n \bigl( \log(\lVert T \rVert_{\max}) + \log(\max(x) + \lVert T \rVert_{\max} G'(n)) \bigr) \bigr) \bigr)$. Le temps total de calcul est de l'ordre de $\mathcal{O}\bigl( \mathrm{card}(T)^{G'(n)} \times \bigl( G'(n) \times \bigl( n \bigl( \log(\lVert T \rVert_{\max}) + \log(\max(x) + \lVert T \rVert_{\max} G'(n)) \bigr) \bigr) \bigr) \bigr)$.

## Annexe A : exemple d'un petit langage algorithmique

**instructions élémentaires** : l'affectation $e := e'$, les appels de procédure $p(e_1, \ldots, e_n)$.

**structures de contrôle** :

- $i\,;\, i'$ : composition séquentielle des instructions
- `begin` $i$ `end` : parenthésage (on peut aussi utiliser une indentation)
- `if` $e$ `then` $i$ `else` $i'$ : conditionnelle
- `for` $x = e$ `to` $e'$ `do` $i$ : itération (dont les bornes sont calculées avant entrée dans la boucle ; $x$, $e$, $e'$ sont de type entier)
- `while` $e$ `do` $i$ : boucle, le test d'arrêt $e$ étant évalué à chaque itération.