Deuxième contrôle continu – 1 avril 2016

Durée: 2h30

Graphes

Considérez le graphe ci-dessous :

: Le graphe est-il dirigé, non-dirigé, complet, connexe ?

: Écrire la matrice d’adjacence du graphe.

: Donner un arbre couvrant minimal, en détaillant les étapes de l’algorithme de Prim.

Programmation linéaire

On considère le programme linéaire suivant :

Maximiser \(6x + 5y\)
Sous
\(\begin{array}{c r r r} -x& + 4y& ≥& -16,\\ 6x& - 4y& ≤& 30,\\ 2x& + 5y& ≤& 6, \end{array}\)

\(x≥0\) et \(y≤0\).

: Mettre le programme linéaire sous forme standard.

: Dessiner la région faisable du programme linéaire.

: Mettre le programme linéaire sous forme relaxée en ajoutant des variables de relaxation.

: Trouver la solution du programme linéaire en détaillant les étapes de l’algorithme du simplexe.

NP-complétude

On rappelle le problème du sac à dos : étant donné un ensemble d’entiers positifs \(S = \{x_1, x_2, \dots, x_n\}\), et un entier \(t≥0\), déterminer s’il existe un sous-ensemble \(S'⊂S\) tel que

\[t = \sum_{x∈S'} x.\]

Étant donné un ensemble \(T = \{y_1, y_2, \dots, y_n\}\) d’entiers positifs, le problème de la partition consiste à déterminer s’il existe un sous-ensemble \(T'⊂Τ\) tel que

\[\sum_{y∈T'}y = \sum_{y∉T'} y.\]

: Prouver que partition \(≤_P\) sac à dos, i.e. que toute instance du problème partition peut être transformée en une instance de sac à dos équivalente.

: Soit \(S=\{x_1, x_2, \dots, x_n\}\) et \(t≥0\) une instance de sac à dos. Soit \(M=\sum_{x∈S}x\), et soit \(T\) l’ensemble

\[T=\{x_1,\dots,x_n,M+1-t,t+1\}.\]

Prouver que \(T\) est une instance de partition équivalente à \((S,t)\).

: Prouver que partition est NP-complet.

Programmation

Le but de cette partie est de programmer un algorithme efficace pour trouver la paire de points les plus proches dans l’espace, parmi un ensemble donné.

: Écrire une fonction dist qui prend en entrée les coordonnées de deux points dans l’espace, et qui donne en sortie la distance Euclidienne entre les points.

: Écrire une fonction min_dist qui prend en entrée une liste de points (donnés comme des paires (x,y)), qui calcule la distance entre chaque paire de points, et qui donne en sortie les deux points les plus proches et leur distance. Écrivez votre code de sorte à faire exactement \(n(n-1)/2\) calculs de distance.

On peut faire mieux que l’algorithme naïf de min_dist en appliquant une technique de type diviser pour régner. On procède de la façon suivante :

• On détermine une droite verticale \(L\) qui divise en deux l’espace, de sorte à ce que la moitié des points se trouvent à droite de \(L\), et l’autre moitié à gauche. Pour effectuer cette opération de façon efficace, il est nécessaire de maintenir une liste de points ordonnée.

• On applique récursivement sur les points à gauche et à droite de \(L\), obtenant ainsi deux paires \(p_g\) et \(p_d\) de points.

• La paire la plus proche sera soit \(p_g\), soit \(p_d\), soit une paire de points qui se trouvent l’un à gauche, et l’autre à droite de \(L\). Dans ce troisième cas, il suffit de s’intéresser uniquement aux points qui sont à distance au plus \(\min(p_g,p_d)\) de \(L\).

: Écrire une fonction min_dist_rec avec les mêmes entrées et sorties que min_dist, et qui implante l’algorithme décrit ci-dessus.