Base d'épreuves orales scientifiques de concours aux grandes écoles

Énoncé(s) donné(s)

Un processus $P$ est une séquence finie d'actions atomiques abstraites distinctes $(a_i)_{i\in [|0;n|]}$. On note $P[i]$ l'action d'indice $i$ de $P$ quand elle existe.

Un système $S$ est un ensemble de processus $P_1,...,P_k$ dont les actions sont toutes différentes.

Un entrelacement de S = {$P_1,...,P_k$} est une séquence finie d'actions $(a_l)_{1 \leq l \leq L}$ qui vérifie les conditions suivantes:
- les $a_l$ sont différentes deux à deux,
- pour tout $1 \leq l \leq L$, il existe (i,j) tel que $a_l=P_i[j]$ (chaque action d'un entrelacement est une action d'un processus),
- si $a_{l_1}=P_i[j_1]$, $a_{l_2}=P_i[j_2]$, alors $l_1 \leq l_2 \implies j_1 \leq j_2$ (les actions d'un même processus apparaissent dans l'ordre dans un entrelacement).

La taille d'un processus $|P|$ est le nombre d'action qu'il contient. De manière similaire, la taille d'un entrelacement est le nombre d'actions qu'il contient.

Un entrelacement est complet si toutes les actions de tous les processus du système apparaissent dans l'entrelacement.

1) Soit $P_1=(a_1,a_2,a_3)$, $P_2=(b_1,b_2)$, $S= \{ P_1,P_2 \}$.
Donner deux entrelacements différents de taille 3 pour le système $S$.
Donner quatre entrelacements complets de $S$.

2) Quelle est la taille d'un entrelacement complet de $S=\{P_i\}_{1\leq i \leq N}$ ?

3) Si $P_1$ est de taille 1 et $P_2$ de taille n, décrire les entrelacements complets de $\{P_1,P_2\}$.

4) Exprimer le nombre d'entrelacements complets d'un système $S=\{P_1,P_2\}$ en fonction de |$P_1$| et |$P_2$|.

5) Généraliser à $S=\{P_i\}_{1 \leq i \leq N}$.

6) Si le nombre de processus est fixé, et que le nombre total d'actions est fixé, quand le nombre d'entrelacements complets est-il maximal ?

 

Pour un système $S=\{P_i\}_{1 \leq i \leq N}$, on dispose d'une fonction $\delta_S$ (qu'on notera $\delta$ quand S est identifié clairement) qui donne le coût de passer d'une action atomique à une autre:
$\delta_S(a,b) \geq 0$ est le coût de passer de l'action atomique $a$ à l'action atomique $b$.
Le coût d'un entrelacement $E=(a_l)_{1\leq l \leq L}=(P_{i_l}[j_l])_{1 \leq l \leq L}$ est la somme des coûts de passage d'une action à l'action suivante, c'est à dire:
$\delta(E)= \underset{\sum}{1\leq l < L}\delta(P_{i_l}[j_l],P_{i_{l+1}}[j_{l+1}])$.

L'objectif est de trouver un entrelacement complet de coût minimal.

 

7) Donner un algorithme naïf qui résout le problème dans le cas général. Etudier sa terminaison, sa correction et sa complexité.

8) Si $S= \{(a_{l,i})_{1 \leq i \leq K_l} \}_{1 \leq l \leq N}$, on note $S-(p_1,...p_N)= \{(a_{l,i})_{p_i+1 \leq i \leq K_l} \}_{1 \leq l \leq N}$
(le système obtenu en enlevant les $p_i$ premières actions des processus $P_i$ à $S$) et $\epsilon (s,p_1,...,p_N)$ l'ensemble des entrelacements complets de $S-(p_1,...p_N)$ qui commencent par $a_{p_s+1}$.
Donner une relation sur $min \{ \delta(E) | E \in \epsilon (s,p_1,...,p_N) \}$ et en déduire un algorithme qui résout le problème dans le cas général. Etudier sa terminaison, sa correction et sa complexité.

 

On dispose d'un ensemble de cellules V=x,y,z,....
Une mémoire est une fonction partielle $\sigma : D \subset V \to \mathbb{N}$ où $D$ est un ensemble fini de cellules.
Une action concrète sur une mémoire est une affectation $x \leftarrow E$ où $E$ est une expression arithmétique simple (addition, multiplication, puissance) faisant éventuellement intervenir des cellules.
On appelle $val(E)_{\sigma}$ la valeur de $E$ dans la mémoire $\sigma$ (obtenue selon des règles standards) quand elle existe (si E fait référence à une cellule qui n'est pas dans le domaine de $\sigma$, elle n'a pas de valeur).
$\sigma[C]$ est la mémoire après l'action $C$ définie par:
-$\sigma[x \leftarrow E](x)=val(E)_{\sigma}$ si elle existe
-pour tout $y$ du domaine de $\sigma$, $\sigma[x \leftarrow E](y)=\sigma(x)$ si $y \neq x$
Si $C_1,C_2,...,C_k$ est une séquence d'actions concrètes, $\sigma[C_1,C_2,...,C_k]=\sigma[C_1][C_2]...[C_k]$.
On suppose maintenant que les actions abstraites des processus sont liées à des actions concrètes (deux actions abstraites peuvent être liées à la même action concrète), ce qui permet de donner un sens à $\sigma[E]$ où $E$ est un entrelacement.
On écrira, par abus de notation $P=\{C_i\}_i$ pour désigner un processus dont les actions abstraites sont liées, dans l'ordre aux actions concrètes $C_i$.

 

9) On prend $P_1=(x \leftarrow x+1,x \leftarrow x+1)$, $P_2=(x \leftarrow 2*x)$, $S= \{P_1,P_2 \}$.
En partant d'une mémoire $\sigma_0: \{x\} \to \mathbb{N}$ définie par $\sigma_0(x)=0$, donner toutes les mémoires que l'on peut obtenir après un entrelacement complet de $S$.

10) Exprimer le nombre de mémoires différentes que l'on peut obtenir après un entrelacement complet d'un système quelconque.

 

Commentaires divers

Début assez simple, beaucoup de dénombrement, quelques algorithmes simples, un naïf et un autre basé sur la programmation dynamique.

La question 9 peut se faire rapidement sans lire les explications sur la mémoire (c'est ce que l'examinateur m'a proposé de faire quand j'avais fini de présenter ce que j'avais préparé, avant de revenir sur la 8 où la relation est plus dure à trouver).