Examen AAC 1ère session

Rappel: un langage est récursif si il existe un algorithme pour décider l’appartenance à ce

langage.

Exercice 2 : Maximum

Soit un tableau T de n entiers; on suppose qu’il existe un indice p, 0 ≤ p < n tel que la

suite T [0], T [1], ..., T [p] soit strictement croissante et la suite T [p], T [p + 1], ..., T [n − 1] soit

strictement décroissante. Par exemple, si n = 6 et T [0] = 1, T [1] = 6, T [2] = 12, T [3] =

16, T [4] = 9, T [5] = 4, alors p = 3.

Proposer un algorithme en O(log n) pour déterminer p.

// il existe p tel que T[0]< T[1]<..<T[p] > T[p+1]>.....T[n-1];

a=0;

b=n-1;

while (a<b){ // invariant : a <=p <=b

m=a+b/2; // a<=m<b car a<b

2

if (T[m] <T[m+1]) //ok car m+1<=b

a=m+1;

else b=m;

}

//a=p=b

return a;

Remarque on a bien (b − a) qui décroît strictement à chaque itération, d’où l’arrêt. La correction

est prouvée en utilisant les assertions qui décorent l’algorithme;

DEUX erreurs faites souvent dans les copies (et peu pénalisées):

. algo qui boucle comme par exemple si on remplace a=m+1 ci-dessus par a=m;

. accès à T [i] avec i hors des bornes du tableau par exemple ici avec un test T [m − 1] < T [m]

Exercice 3 : Au suivant

On veut pouvoir générer tous les mots sur {a, b} de longueur inférieure ou égale à une valeur

donnée dans l’ordre alphabétique. Par exemple l’énumération pour 3 doit produire:

a

aa

aaa

aab

ab

aba

abb

b

ba

baa

bab

bb

bba

bbb

Q 1. Pour cela, complétez le code des méthodes Suivant() et EstDernier() de la classe

suivante:

class Mot {

//le mot

private char[] cont;

//la longueur du mot courant

private int longueur;

//la longueur maxi

private int longueurmaxi;

//constructeur initialise le mot au mot vide, la longueur au maxi

Mot(int longueurmaxi){

3

this.cont=new char[longueurmaxi];

this.longueur=0;

this.longueurmaxi=longueurmaxi;

}

//tranforme le mot en son suivant pour l’ordre alphabétique

//on peut supposer que this.EstDernier() est faux;

void Suivant(){ A faire}

//retourne vrai Ssi le mot est le dernier dans l’ordre alphabétique: bbbb...bbbbb

boolean EstDernier(){A Faire}

......

}

//tranforme le mot en son suivant pour l’ordre alphabétique

void Suivant(){

if (longueur <longueurmaxi) {longueur++;cont[longueur-1]=’a’;}

else {

while (cont[longueur-1]==’b’) longueur- -; // evt cont[longueur]=’ ’;

//remarque déclenche une exception si Estdernier() est vrai

cont[longueur-1]=’b’;

}}

//retourne vrai Ssi le mot est le dernier dans l’ordre alphabétique bbbb...bbbbb

boolean EstDernier(){

if (longueur<longueurmaxi) return false;

for (int i=0;i <longueur; i++) {

if (this.cont[i]==’a’) return false;

}

return true;

}

Exercice 4 : Plaques

Soit n plaques rectangulaires de dimension (xi, yi) avec xi ≥ yi, 0 ≤ i ≤ n − 1; ces plaques

ont toute la même épaisseur;

Q 1. On cherche à empiler le maximum de ces plaques en respectant la contrainte suivante:

la plaque j ne peut être empilée au-dessus de la plaque i que si xj ≤ xj et yj ≤ yi. Par

exemple, si on a 6 plaques de dimensions respectives (12, 7), (11, 8), (7, 7), (9, 6), (5, 5), (9, 4)

on ne pourra pas empiler toutes les plaques, mais on pourra empiler les plaques 0, 2, 4 dans

cet ordre (il y a d’autres solutions optimales comme 1, 2, 4 ). Le problème est donc:

Donnée: un entier n, le nombre de plaques

un tableau x de taille n contenant les longueurs des plaques

un tableau y de taille n contenant les largeurs des plaques

Sortie: J ⊂ [0, n − 1] de cardinal maximal tel que pour tout i de J et tout j de J, soit

x[i] ≤ x[j] et y[i] ≤ y[j], soit x[i] ≥ x[j] et y[i] ≥ y[j]

Q 1.1. A quelle condition peut-on empiler toutes les plaques en respectant la contrainte?

4

Il faut juste que pour tout i et tout j, si x[i] ≤ x[j], alors y[i] ≤ y[j]

Q 1.2.Glouton?... Pensez-vous que l’algorithme de type glouton suivant donne toujours la

solution optimale? Justifier.

x[i] décroissant.

Trier les plaques par

Initialiser J à l’ensemble vide;

Ajouter 0 à J;

largeur=y[0];

pour i de 1 à n-1

si y[i]< =largeur {

ajouter i à J;

largeur=y[i];}

Non, contre-exemple: (10, 1), (8, 3), (7, 2)

Q 1.3.ou dynamique? En utilisant la programmation dynamique, proposer un algorithme en

O(n2) pour résoudre le problème. Vous pourrez supposer les plaques triées par x[i] décroissant.

Remarque: vous pouvez répondre partiellement en calculant uniquement le nombre maxi-

mal de plaques qu’on peut empiler (i.e. card J).

// les plaques sont triées par $x[i]$ décroissant

int[] nb=new int [n];

//nb[i] sera le nombre

int[] suiv=new int[n];

//suiv[i] sera le no de la première plaque qu’on empile au-dessus de i dans une solution optimale.

int max=0; la hauteur maxi d’une pile

int indmax;

for (int i=n-1;i>=0;i- -)

de plaques maximum qu’on peut empiler au-dessus de la plaque i

nb[i]=0;

suiv[i]=i;

for (int j=i+1; j<n;j++} {

if (y[i]>=y[j]) && (nb[j]>=nb[i]) {

nb[i]=1+nb[j];suiv[i]=j}

}

if (nb[i]>=max) max=1+nb[i]; indmax=i;}

}

ensemble J;

ind=indmax;

J.ajouterr(ind); // première plaque est plaque ind

while nb[ind]>0 {ind=suiv[ind];J.ajouter(ind);} //empiler plaque ind

return(J);

}

Remarque: cela correspond exactement à l’algorithme de recherche d’une plus longue sous-suite

croissante, qui était l’objet d’un exercice d’une feuille de TD!

Q 2. On cherche maintenant à choisir un nombre minimum de plaques telle que pour toute

plaque, il existe une plaque parmi les plaques choisies qui puisse la recouvrir. Dans l’exemple

ci-dessus, on choisirait donc les plaques {0, 1}.

Donnée: un entier n, le nombre de plaques

x, un tableau de taille n contenant les longueurs des plaques

y , un tableau de taille n contenant les largeurs des plaques

5

Sortie: J ⊂ [0, n − 1] de cardinal minimal tel que pour tout i de [0, n − 1], il existe j dans

J tel que x[i] ≤ x[j] et y[i] ≤ y[j].

Remarque: On suppose que deux plaques différentes ont au moins une dimension différente,

c.à.d. si i (cid:54)= j, x[i] (cid:54)= x[j] ou y[i] (cid:54)= y[j].

Q 2.1. Quelle est la solution optimale pour (17, 5), (12, 7), (9, 5), (9, 7), (8, 6)?

(17, 5), (12, 7)

Q 2.2. Peut-il y avoir deux solutions optimales différentes pour la même donnée? Justifier.

Non! Supposons qu’on ait deux solutions différentes S1, S2. Donc, il existe une plaque i qui

est dans l’une et qui n’est pas dans l’autre: on peut supposer sans perte de généralité qu’elle est

dans S1 et pas dans S2. Cette plaque i est couverte par une plaque j de S2 puisque S2 est solution:

x[i] ≤ x[j], y[i] ≤ y[j] avec x[i] < x[j] ou y[i] < y[j] d’après l’hypothèse: deux plaques différentes

ont au moins une dimension différente. Mais comme S1 est solution la plaque j est couverte par une

plaque k de S1: x[j] ≤ x[k], y[j] ≤ y[k]. Donc x[i] ≤ x[k], y[i] ≤ y[k] avec x[i] < x[k] ou y[i] < y[k] : la

plaque i est couverte par la plaque k de S1: mais alors S1 privée de la plaque i est toujours solution

-puisque toute plaque recouverte par i l’est par k- et S1 ne serait pas optimale.

Q 2.3. Proposez un algorithme de type glouton pour le problème. Justifiez sa correction et

analysez sa complexité.

x[i] décroissant, PUIS par y[i] décroissant en cas d’égalité des x

Trier les plaques par

Initialiser J à l’ensemble vide;

Ajouter 0 à J;

largeurmaxi=y[0];

pour i de 1 à n-1

si y[i] >largeurmaxi {

ajouter i à J;

largeurmaxi=y[i];}

Preuve: l’ensemble J ainsi construit est bien une couverture puisque si une plaque n’est pas ajoutée,

c’est qu’elle est couverte par une plaque examinée auparavant. C’est bien une couverture optimale:

quand on ajoute i à J, on est sûr qu’elle ne peut être couverte par aucune autre plaque: une plaque

qui la couvrirait aurait un x >x[i] et un y >= y[i] ou un x >x[i] et un y >=y[i] ( car elles sont

toutes différentes): mais alors on aurait déjà examinée cette plaque, elle serait donc couverte et on

aurait largeurmaxi>=y[i].

Exercice 5 : Processus

Soit un système temps réel avec n processus asynchrones et m ressources. Quand un processus

est actif, il bloque un certain nombre de ressources et une ressource ne peut être utilisée que

par un seul processus. On cherche à activer simultanément k processus.

Le problème de décision DecProc est donc:

Donnée:

n, le nombre de processus

m le nombre de ressources

pour chaque processus i, la liste Pi des ressources qu’il bloque.

k le nombre de processus que l’on souhaite activer

Sortie:

Oui, si on peut activer k processus simultanément, non sinon.

6

Par exemple si n = 4, m = 5, et P1 = {1, 2}, P2 = {1, 3}, P3 = {2, 4, 5}, P4 = {1, 2, 4} on

peut activer simultanément les processus 2 et 3 et donc la réponse est Oui pour k = 2 mais

la réponse est N on pour k = 3.

Q 1. Montrer que le problème DecProc est N P .

Exemple de solution:

Remarque préliminaire: la taille du problème est au moins n + m.

Un certificat est simplement un ensemble de processus, donc un sous-ensemble de {1, ..., n}. Un

certificat peut donc être codé par un vecteur de n booléens et la taille d’un certificat est donc n, donc

inférieure à la taille du problème.

La vérification consiste juste à vérifier que deux processus actifs ne partagent pas une ressource,

et que le cardinal est bien k, soit:

//probleme donne par n, P1, ...Pi

//certificat : ensemble de processus

boolean correct(certificat certif){

ensemble R=ensemble vide; //les ressources utilisees

int card=0; // pour calculer card (certif), le nb de processus actives

pour i de 1 à n

si certif.appartient(i) alors{

card++;

si intersection( Pi, R) est non vide

alors

sinon R=union(R, Pi);}

return False; //conflit sur au moins une ressource

fsi

fpour

return (card == k);}

L’algorithme de vérification est bien polynômial; sa complexité exacte dépend de la complexité de

appartient(), intersection(,) et union(,) mais sera de toute façon polynômiale, le coût de ces

opérations étant polynômial

Remarque 1: si on veut préciser cette complexité -ce qui était non demandé-, soit Pa(x) (resp.

Pin(x), Pu(x)) bornant la complexité de appartient() pour un ensemble de cardinal au plus x (resp.

le test du vide de l’intersection(resp. le calcul de l’union) de deux ensembles de cardinal au plus x), le

coût de l’algo est en O(n ∗ (Pa(n) + Pin(m) + Pu(m))2) soit O(n ∗ (Pa(t) + Pin(t) + Pu(t))2), si t est

la taille du problème.

Remarque 2: pour beaucoup, la notion de certificat semble encore confuse; un certificat est juste

"un essai de solution", pas forcément une solution correcte;

Q 2. En utilisant le fait que le problème Independent Set étudié en TP est N P -dur,

montrer que le problème DecProc est N P -dur.

Remarque: Attention à ne pas se tromper de sens dans la réduction!!!!!

Il fallait réduire Independent Set , connu N P -dur, dans DecProc, et non le contraire.

Il faut donc associer à toute instance I de Independent Set , une instance red(I) de DecProc

telle que red(I) soit positive Ssi I l’est.

Une instance de Independent Set est la donnée d’un graphe (Sommets, Arcs) et d’un entier k0.

On définit red(I) par:

n, le nombre de processus par n = card(Sommets)

m le nombre de ressources p = card(Arcs)

pour chaque processus i, la liste Pi des ressources qu’il bloque par Pi = l’ensemble des arcs

adjacents au sommet i.

k le nombre de processus que l’on souhaite activer par k = ko

La réduction est bien polynomiale (il faut juste calculer card(Sommets), card(Arcs) et pour chaque

sommet, les arcs adjacents).

7

Elle est bien exacte: si I est une instance positive de Independent Set, il existe donc un

sous-ensemble de cardinal k de sommets indépendants:

les k processus associés ne partagent donc

aucune ressource et forment donc un sous-ensemble de cardinal k de processus qu’on peut activer

simultanément: red(I) est positive.

Réciproquemment, si red(I) est positive, il existe un sous-ensemble de k processus qu’on peut

activer simultanément: les k sommets associés ne partagent donc pas d’arcs et sont indépendants: I

est bien positive.

Q 3. Que pensez-vous de la complexité du problème DecProc si chaque processus utilise

une seule ressource?

Le problème devient bien sûr polynômial et peut par exemple être résolu par un glouton:

//probleme donne par n, P1, ...Pi

//certificat : ensemble de processus

boolean solve(){

ensemble R=ensemble vide; //les ressources utilisees

int card=0; // pour calculer e nb de processus actives

pour i de 1 à n

si intersection( Pi, R) est

alors { card++; R=union(R, Pi);}

vide

fsi

fpour

return (card >= k);}

Q 4. Que pensez-vous de la complexité du problème DecProc si chaque ressource est utilisée

par au plus deux processus?

Il est toujours N P −dur puisque, dans les instances obtenues par réduction dans la question 2,

chaque ressource (un arc) est utilisée par au plus deux processus (ses extrémités).

Q 5. Que pensez-vous de la complexité du problème d’optimisation associé OptProc:

Donnée:

n, le nombre de processus

m le nombre de ressources

pour chaque processus i, la liste Pi des ressources qu’il bloque.

Sortie:

k maximum tel qu’on puisse activer k processus simultanément.

On peut dire qu’il est N P − dur: si on avait un algorithme polynômial pour le problème d’optimisation,

on en aurait un pour celui de décision! (puisque (I(n, m, (P i), k).DecP roc() = (I(n, m, (P i)).OptP roc() >=

k)).

8