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

Énoncé(s) donné(s)

Problème de cache

Soit $P = \{p_1,p_2,\dots,p_n\}$ un ensemble d'éléments appelés pages. On considère un cache de capacité $k$ initialement vide avec $k<n$ et une séquence de requêtes $\sigma = (r_1,\dots,r_{|\sigma|})$ où chaque $r_i \in P$ arrive successivement dans cet ordre.

Pour satisfaire une requête, la page associée doit être présente dans le cache. Si elle n'est pas présente, il faut l'ajouter au cache, ce qui a un coût de 1. Si le cache contient déjà k pages différentes, il faut d'abord enlever une page du cache avant d'en rajouter une. Enlever une page du cache n'a pas de coût supplémentaire.

L'objectif est de minimiser le coût total pour satisfaire les requêtes $\sigma$. Noter que les seules décisions importantes consistent à choisir quelle page enlever du cache lorsque l'on doit rajouter une nouvelle page à un cache plein.

$\ex 1$ Montrer que le coût minimum pour $k=1$, $P = \{a,b,c,d,e,f\}$ et $\sigma = (a,b,e,d,e,f,a,b,e,d)$ est égal à 7.

$\ex 2$ Si l'ensemble des requêtes $\sigma$ est connu, donnez un algorithme simple aboutissant à un coût optimal. La preuve d'optimalité est demandée.

Indication : pour prouver l'optimalité de la solution, on pourra considérer une solution optimale qui coincide avec la solution proposée pendant un temps maximal.

On suppose maintenant que l'on ne connait pas l'ensemble des requêtes $\sigma$ dès le départ, mais seulement celle que l'on doit satisfaire actuellement. La prochaine requête est révélée une fois la requête actuelle satisfaite.

Afin d'évaluer la performance d'un algorithme $A$ qui aboutit à un coût $C_\sigma ^A$ dépendant de $\sigma$, on utilise la quantité suivante :

$c(A) = \underset{n \in \mathbb{N}, \sigma \in P^n}{sup} \frac{C_\sigma ^A}{OPT_\sigma}$

où $OPT_\sigma$ représente le coût optimal d'un algorithme connaissant $\sigma$ à l'avance.

$\ex 3$ Soit l'algorithme $LFU$ (less frequently used) qui élimine toujours la page présente dans le cache qui a été le moins demandée jusqu'à présent. Montrer que $c(LFU)$ est infini

$\ex 4$ Soit $A'$ un algorithme qui a connaissance de la requête à satisfaire, ainsi que de la suivante. Montrer qu'il existe un algorithme $A$ ayant seulement connaissance de la requête à satisfaire tel que $c(A) \leq c(A')$.

$\ex 5$ Montrer que, pour une valeur de $n$ bien choisie, pour toute séquence $\sigma$, il existe une solution de coût au plus $\frac{|\sigma|}{k} + k$.
En déduire que tout algorithme déterministe $A$ (i.e., n'ayant pas recours à l'aléatoire) respecte $c(A) \geq k$

$\ex 6$ Soit l'algorithme $LRU$ (least recently used) qui élimine toujours la page présente dans le cache qui a été demandée le moins récemment. Montrer que $c(LRU) = k$.

$\ex 7$ Montrer que $\underset{n \in \mathbb{N}, \sigma \in P^n}{sup} \frac{ LRU_\sigma ^{2k} }{OPT_\sigma ^k} = 2$ où $LRU_\sigma ^{2k}$ est le coût de l'algorithme LRU sur l'instance $\sigma$ avec un cache de taille $2k$ et $OPT_\sigma ^k$ est le coût d'une solution optimale sur l'instance $\sigma$ avec un cache de taille k.

Indication(s) fournie(s) par l'examinateur pendant l'épreuve

Pour la 4, l'examinateur m'a donné la réponse après des essais infructueux de ma part.

Commentaires divers

Je n'ai pas du tout réussi ce sujet, n'ayant fait que les questions 1 et 3. Pour les 2 et 4, j'ai proposé des solutions qui n'aboutissaient pas, alors l'examinateur m'a donné les réponses.

J'ai tout de même eu 10/20, alors le sujet devait être difficile.

L'examinateur était très gentil et laissait le temps de proposer des solutions fausses et farfelues, il a fait l'effort d'essayer de les comprendre avant de proposer une vraie solution.