DS 4 (MP2I 2022-2023) — Placement des convives¶

Devoir surveillé · MP2I · 2022-2023 · partie II du DS 4 (2 h 30 au total)

Cours : Algorithmes gloutons · Complexité

OCaml et complexité¶

C'est le grand jour où vous fêtez avec vos amis et votre famille votre réussite aux concours. Vous organisez un grand repas et vous souhaitez, par commodités, placer le maximum de convives sur une même table.

Problème : certains de vos convives ne s'entendent pas (sûrement une dispute sur leur langage de programmation préféré) et ne souhaitent pas être placés à la même table. Comment allouer des tables aux convives en essayant d'en avoir le moins possibles ?

On considère que chacun de vos \(n\) convives est identifié de manière unique par un numéro dans \(\range{0}{n-1}\) et que l'on dispose d'une matrice :

val ami : bool array array

de dimension \((n,n)\) telle que ami.(i).(j) soit vrai lorsque i et j sont amis. Cette relation étant considérée symétrique on a toujours ami.(i).(j) = ami.(j).(i).

Un tableau table de longueur \(n\) qui associe à chaque convive un numéro dans \(\range{0}{p-1}\) est appelé une affectation des convives à \(p\) tables. Ainsi table.(i) vaut k quand on place le convive i à la table k.

Question 7

Écrire une fonction de prototype

val valide : int array -> bool

qui s'assure que l'on n'a jamais placé à une même table deux personnes qui ne sont pas amies.

Corrigé

let valide table =
  let n = Array.length table in
  let is_valide = ref true in
  for i = 0 to n-1 do
    for j = i+1 to n-1 do
      (* pas amis et à la même table *)
      if not ami.(i).(j) && table.(i) = table.(j)
      then is_valide := false
    done
  done;
  !is_valide

Question 8

Quelle est la complexité de la fonction précédente ?

Corrigé

On parcourt chaque case de la moitié de la matrice, donc \(O(n^2)\) cases et pour chaque case on effectue un traitement en \(O(1)\), donc la complexité est en \(O(n^2)\).

Note : si les personnes sont presque toutes amies, il serait plus raisonnable de travailler sur la liste des inimitiés.

On va essayer de construire une affectation valide de manière incrémentale ainsi :

au départ on initialise le tableau table avec des valeurs quelconques (prenez -1 par exemple)
Pour \(i\) allant de 0 à \(n-1\)
- on suppose qu'il y a un numéro valide dans table pour tous les convives de numéro \(< i\) et qu'il n'existe pas de couple \((j,k)\) où \(j,k < i\) qui ne soient pas amis et tels que table.(j) = table.(k).
- on calcule la liste des numéros de tables de tous les convives de numéro \(< i\) qui ne sont pas amis avec \(i\).
- on en déduit le plus petit numéro \(\ge 0\) de table qui ne soit pas dans cette liste
- on affecte ce numéro à \(i\) en le plaçant dans table.(i).

Question 9

On suppose qu'il y a 6 convives, de 0 à 5, et que les inimitiés sont les suivantes :

0 et 2 sont ennemis
2 et 3 sont ennemis
2 et 4 sont ennemis
3 et 4 sont ennemis
1 et 5 sont ennemis

Dérouler l'algorithme précédent avec précision et en déduire une affectation en trois tables.
Peut-on faire mieux ?

Corrigé

On va construire i -> table.(i) de manière incrémentale :
- \(0 \mapsto 0\)
- \(1 \mapsto 0\)
- \(2 \mapsto 1\) car il a 0 comme ennemi \(< 2\) et qu'il est déjà à la table 0.
- \(3 \mapsto 0\) car il a 2 comme ennemi \(< 3\).
- \(4 \mapsto 2\) car il a 2 et 3 comme ennemis \(< 4\).
- \(5 \mapsto 1\) car il a 1 comme ennemi \(< 5\).
On ne peut pas faire mieux que trois tables, car comme 2, 3 et 4 ne s'apprécient pas deux à deux, il faut les placer sur trois tables différentes. La solution précédente est donc optimale.

Question 10

Écrire une fonction de prototype

val tables_ennemis : int array -> int -> int list

telle que l'appel à tables_ennemis table i renvoie la liste des numéros de table (avec possiblement des répétitions) des ennemis du convive \(i\) dont le numéro est \(< i\).

Corrigé

let tables_ennemis table i =
  let rec cherche j =
    if j < 0
    then []
    else let l = cherche (j-1) in
      if not ami.(i).(j)
      then table.(j) :: l
      else l
  in cherche (i-1)

Question 11

Quelle est la complexité de cette fonction ?

Corrigé

C'est la boucle induite par la fonction récursive qui compte car on n'y effectue que des opérations en temps constant, donc la complexité est en \(O(i)\).

Question 12

Écrire une fonction de prototype

val plus_petit_absent : int list -> int

qui prend une liste d'entiers et renvoie le plus petit entier naturel qui n'est pas présent dans la liste.

Votre réponse devra être linéaire pour avoir tous les points, mais un algorithme non linéaire aura au moins la moitié des points.

Question 13

En déduire une fonction de prototype

val affecte : unit -> int array

qui réalise l'algorithme d'affectation présenté ci-dessus.

Corrigé

let affecte () =
  let n = Array.length ami in
  let table = Array.make n 0 in
  for i = 1 to n-1 do
    let l = tables_ennemis table i in
    table.(i) <- plus_petit_absent l
  done;
  table

Question 14

Quelle est sa complexité en supposant que plus_petit_absent est linéaire ?

Corrigé

Les deux appels dans la boucle sont en \(O(i)\), donc, comme \(i \le n\), la complexité totale est en \(O(n^2)\).

Question 15

Établir un petit contre-exemple démontrant que cette fonction ne réalise pas le plus petit nombre de tables.

Corrigé

Premier contre-exemple :
- 0 est ennemi avec 1
- 1 est ennemi avec 0
- 2 est ennemi avec 3
- 3 est ennemi avec 1 et 2
On va dérouler l'algorithme :
- \(0 \mapsto 0\)
- \(1 \mapsto 1\) car évite \(\{0\}\)
- \(2 \mapsto 0\) car évite \(\emptyset\)
- \(3 \mapsto 2\) car évite \(\{0,1\}\)
On obtient donc \((0,1,0,2)\) en 3 tables alors que \((0,1,1,0)\) en deux tables est optimal.
Un contre-exemple classique :
- 0 est ennemi avec 1, 2 et 3
- 1 est ennemi avec 0, 2 et 4
- 2 est ennemi avec 0, 1 et 5
- 3 est ennemi avec 0, 4 et 5
- 4 est ennemi avec 1, 3 et 5
- 5 est ennemi avec 2, 3 et 4
On va dérouler l'algorithme :
- \(0 \mapsto 0\)
- \(1 \mapsto 1\) car évite \(\{0\}\)
- \(2 \mapsto 2\) car évite \(\{0,1\}\)
- \(3 \mapsto 1\) car évite \(\{0\}\)
- \(4 \mapsto 0\) car évite \(\{1\}\)
- \(5 \mapsto 3\) car évite \(\{0,1,2\}\)
Or l'affectation \((0,1,2,1,2,0)\) est valide et utilise une table de moins.

Le contre-exemple qu'on vient de voir en reste un en renumérotant les convives.