مسابقة دكتوراه 2015 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — الموضوع 03

مسابقة تخصص · Recherche Opérationnelle

Formation Doctorale ROM, Concours d'accès — Épreuve de Réseaux et Optimisation, USTHB, Faculté de Mathématiques, Département de Recherche Opérationnelle — 18 Octobre 2015.

التمرين 1

Exercice 1 — Forêt de poids maximum et arbre de poids minimum

#graph-theory#maximum-forest#minimum-spanning-tree#polynomial-time

Soit $R=(X,E,p)$ un réseau connexe, avec $p:E\to \mathbb{Z}$ .

Question 1. a) Décrire un algorithme de recherche d'une forêt de poids maximum, en précisant sa taille et sa complexité. b) Donner une formulation de ce problème sous forme d'un programme linéaire en 0-1. c) En déduire que ce problème est polynomial. d) Montrer que si tous les poids sont positifs, alors la forêt de poids maximum est un arbre. e) Comment modifier cet algorithme pour la recherche d'un arbre de poids maximum ?

Question 2. On suppose les distances positives. a) Donner une formulation du problème de recherche d'un arbre de poids minimum sous forme d'un programme linéaire en 0-1. b) Formuler une adaptation de l'algorithme décrit à la question 1 pour résoudre ce problème. c) En déduire que ce problème est polynomial. d) Sachant que le problème du voyageur de commerce est NP-Complet, montrer que le problème de recherche d'un arbre dont tous les sommets sont de degré au plus égal à 2 est NP-Complet.

◀الحل

1.

Algorithme glouton : trier les arêtes par poids décroissant, ajouter une arête si elle ne crée pas de cycle. Complexité $O(m\log m)$ avec structure union-find.

Formulation 0-1 : maximiser $\sum p(e)x_e$ sous contraintes d'acyclicité $\sum_{e\in E(S)} x_e \leq |S|-1$ pour tout $S \subseteq X$ , $x_e \in \{0,1\}$ .

Si tous les poids sont positifs, une forêt maximum doit être connexe sinon on peut toujours ajouter une arête positive entre composantes.

2.

Même formulation avec minimisation et adaptation gloutonne : algorithme de Kruskal / Prim. Polynomial.

Le problème d'arbre de degré au plus 2 est équivalent à chercher un chemin hamiltonien ou un cycle hamiltonien selon les variantes, donc NP-Complet par réduction du TSP / Hamiltonien.

التمرين 2

Exercice 2 — Sac de regret minimal et programmation dynamique

#dynamic-programming#knapsack#regret-minimization

Soit $n$ objets, de poids respectifs $p_i$ et de regret $r_i$ , et soit $P$ un entier. On appelle regret d'un sac la somme des regrets des objets qui ne sont pas dans le sac. On cherche un sac de poids inférieur ou égal à $P$ qui soit de regret minimal.

Modéliser ce problème à l'aide d'un programme mathématique.
Définir un schéma de programmation dynamique.
Notons $F_k(E)$ le regret minimum d'un sac de poids inférieur ou égal à $P-E$ parmi les objets $\{k,\dots,n\}$ . Comment se définit la solution du problème initial par rapport à cette notation ?
Que vaut $F_n(E)$ ?
Établir l'équation de récurrence satisfaite par les $F_k$ .
En déduire un algorithme pour résoudre le problème et donner sa complexité.

◀الحل

1.

Variables binaires $x_i \in \{0,1\}$ indiquant si l'objet est pris. Minimiser le regret des objets non pris :

\min \sum_{i=1}^n r_i(1-x_i)

sous la contrainte de poids $\sum p_i x_i \leq P$ .

2-5.

On pose $F_k(E)$ = regret minimum à partir de l'objet $k$ avec capacité restante $P-E$ .

Solution initiale : $F_1(0)$ .

Cas terminal : $F_n(E) = 0$ si $p_n \leq P-E$ et qu'on prend $n$ , sinon $r_n$ .

Récurrence :

F_k(E) = \min\{r_k + F_{k+1}(E), \; F_{k+1}(E+p_k)\}

si $E+p_k \leq P$ , sinon seulement le premier terme.

6.

Algorithme DP classique en $O(nP)$ temps et $O(nP)$ ou $O(P)$ mémoire.

→←

→السابقProblème de Cauchy pour EDPs d’évolution التاليConcours Doctorat 2015 — Université Djilali Liabès - Sidi Bel Abbès — Épreuve N°03←