TD d’algorithmique numéro 8 Natacha Portier et Daniel Hirschkoff semaine du 22 au 26 novembre 1999

Question 1 ⋆ Pétrole ⋆

Le professeur Robert Ive est consultant pour une compagnie pétrolière qui projette de construire un grand oléoduc d’Est en Ouest à travers un champ pétrolier. À partir de chaque puits un raccordement doit être connecté directement sur l’oléoduc principal suivant le plus court chemin. Connaissant les coordonnées des puits, comment le professeur trouvera-t’il l’emplacement idéal de l’oléoduc principal qui minimise la longueur totale des raccordements?

Question 2 ⋆ Recherche du ie plus petit ⋆

On considère un tableau de n entiers tous distincts et un entier i compris entre 1 et n. On cherche un algorithme linéaire dans le pire des cas qui sélectionne le ie plus petit. On a déjà trouvé un tel algorithme pour i égal 1, 2, n − 1 et n (TD1). Pour i = ⌊\frac{n+1}{2}⌋ le ie plus petit élément est le médian inférieur. On va ici donner un algorithme pour i quelconque :

1. Si n = 1 l’entier est l’élément cherché.

2. Diviser les n éléments en ⌊n/5⌋ groupes de 5 éléments chacun et un groupe formé des éléments restants.

3. Trier chaque groupe et en prendre le médian.

4. Trouver récursivement le médian x de l’ensemble des ⌈n/5⌉ médians.

5. Partitionner les entrées autour de x en excluant x. Soit k le nombre d’éléments de la partie inférieure (éléments strictement inférieurs à x).

6. Si i = k +1 l’élément cherché est x. Si i ≤ k trouver récursivement le ie plus petit de la partie inférieure. Si i > k trouver récursivement le i − ke plus petit de la partie supérieure.

Question 2.1

Etape 5 : majorer le nombre d’éléments de chacun des deux ensembles de la partition.

Question 2.2

Soit T (n) le temps d’exécution de l’algorithme dans le pire des cas sur une entrée de taille n. Donner la relation de récurrence vérifiée par T. Montrer par substitution que le temps d’exécution est linéaire. Question 2.3

Dans l’algorithme les éléments sont répartis par groupes de 5. Que dire s’ils sont répartis par groupes de 7? Et par groupes de 3? Question 3 ⋆ Médian pondéré ⋆

Pour n éléments distincts x_{1}, ..., x_{n} avec des poids positifs p_{1}, ..., p_{n} tels que

∑_{i=1}^{n} p_{i} = 1

Le médian pondéré (inférieur) est l’élément x_{k} satisfaisant :

∑_{x_{i}<x_{k}} p_{i} < \frac{1}{2} et ∑_{x_{i}>x_{k}} p_{i} ≤ \frac{1}{2}

Démontrer que le médian de x_{1}, ..., x_{n} est le médian pondéré des x_{i} avec les poids p_{i} = 1/n pour i compris entre 1 et n.

Montrer comment calculer le médian pondéré de n éléments dans un temps O(n log n) dans le pire des cas, en utilisant le tri.

Montrer comment calculer le médian pondéré en temps linéaire dans le pire des cas en s’inspirant du deuxième exercice. Question 4 ⋆ Le problème de l’emplacement du bureau de poste ⋆

Considérons un espace métrique (E, d). Soient x_{1}, ..., x_{n} des points de E et leurs poids associés p_{1}, ..., p_{n} (au sens de l’exercice précédent). On souhaite trouver un point x, qui ne soit pas nécessairement un des x_{i}, qui minimise ∑_{i=1}^{n} p_{i}d(x, x_{i}). Question 4.1 ⋆ La dimension 1 ⋆

L’espace (E, d) est l’ensemble des réels muni de la distance usuelle. Montrer que le médian pondéré est une des meilleures solutions. Question 4.2 ⋆ La dimension 2 ⋆

L’espace (E, d) est le plan muni de la distance 1, ou distance Manhattan :

d((x_{1}, y_{1}), (x_{2}, y_{2})) = |x_{1} − x_{2}| + |y_{1} − y_{2}|

Résoudre le problème du bureau de poste.