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
Sous

et .

: 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 , et un entier , déterminer s’il existe un sous-ensemble tel que

Étant donné un ensemble d’entiers positifs, le problème de la partition consiste à déterminer s’il existe un sous-ensemble tel que

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

: Soit et une instance de sac à dos. Soit , et soit l’ensemble

Prouver que est une instance de partition équivalente à .

: 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 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 :

: É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.