Corrigé DS
Bonjour,
J’espère que l’épreuve s’est bien passée !!!!! ci-dessous un corrigé des exercices 2 & 3. Bien sûr c’est
un corrigé « idéal » ( ?).
Exercice 2
Exercice 3
Q 1. Montrer que le problème DecProc est NP.
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 utilisées
Publicité
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 return False; //conflit sur au moins une ressource
sinon R=union(R, Pi);}
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
Publicité
solution", pas forcément une solution correcte;
Q 2. En utilisant le fait que le problème Independent Set étudié en TP est NP-dur,
montrer que le problème DecProc est NP-dur.
Remarque: Attention à ne pas se tromper de sens dans la réduction!!!!!
Il fallait réduire Independent Set , connu NP-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).
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
Publicité
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 vide
alors { card++; R=union(R, Pi);}
fsi
fpour
return (card >= k);}
Publicité
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 NP- 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 NP - 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; (Pi); k):
DecProc() = (I(n; m; (Pi)):OptProc() >=k)).