QCM - Algorithmes d'approximation

QCM - Algorithmes d'approximation

Question 1. Un algorithme d'approximation est utilisé pour :

Résoudre des problèmes P en temps logarithmiqueObtenir une solution approchée d'un problème NP-complet en temps polynomialProuver qu'un problème est NP-completTrouver la solution exacte d'un problème NP-complet

Question 2. Pour un problème de minimisation, une $2$-approximation garantit que :

La solution est au moins $2$ fois meilleure que l'optimaleLa solution est au plus $2$ fois plus grande que l'optimaleLa solution est exactement $2$ fois l'optimaleLa solution est au plus $1/2$ de l'optimale

Question 3. Pour un problème de maximisation, une $0.5$-approximation garantit que :

La solution est au moins la moitié de l'optimaleLa solution est au plus la moitié de l'optimaleLa solution est exactement la moitié de l'optimaleLa solution est au plus $2$ fois l'optimale

Question 4. Quelle est la différence entre un problème d'optimisation et un problème de décision ?

Aucune différenceUn problème d'optimisation renvoie un booléen, un problème de décision renvoie une solutionUn problème de décision renvoie un booléen, un problème d'optimisation renvoie une solution optimaleUn problème d'optimisation est toujours dans P

Question 5. Une couverture par sommets d'un graphe est :

Un ensemble de sommets tel que chaque arête a au moins une extrémité dans cet ensembleUn ensemble d'arêtes couvrant tous les sommetsUn chemin passant par tous les sommetsUn ensemble de sommets indépendants

Question 6. L'algorithme glouton qui ajoute les deux extrémités d'une arête pour COUVERTURE-OPT est une :

$1$-approximation$2$-approximation$3$-approximationIl n'y a pas de garantie d'approximation

Question 7. La méthode Branch-and-Bound est :

Un algorithme polynomial d'approximationUne méthode exacte qui reste en temps exponentiel mais accélère la recherche exhaustiveUn algorithme gloutonUne méthode probabiliste

Question 8. Un ensemble stable d'un graphe est :

Un ensemble de sommets tous reliés deux à deuxUn ensemble de sommets sans arête entre euxUn ensemble d'arêtes sans sommet communUn chemin hamiltonien

Question 9. Le rapport d'approximation $\alpha$ doit être :

Une variable dépendant de l'instanceUne constante indépendante de l'instanceToujours égal à $2$Toujours inférieur à $1$

Question 10. Si $S$ est un ensemble stable maximal de $G$, alors $\bar{S}$ (le complémentaire de $S$) est :

Un ensemble stableUne couverture par sommetsUn couplageUn chemin hamiltonien