On désire distribuer un ensemble de 9 tâches {T1,... T9} dont les durées sont respectivement {1h, 4h, 6h, 3h, 8h, 2h, 5h, 7h, 4h}. Il s'agit de les distribuer entre le moins possible de personnes mais la durée totale pour une personne ne doit pas dépasser 8h.

1. Déterminer la répartition des 9 tâches permettant de rendre minimum le nombre de personnes nécessaires.
   
   solution: {8h} {7h 1h} {6h 2h} {5h 3h} {4h 4h}
   soit: {T5} {T8 T1} {T3 T6} {T7 T4} {T2 T9}
   
2. Comment déterminer cette répartition si le nombre et la durée des tâches à réaliser est quelconque? Donnez le principe de la recherche de solution.
   
   Il faut donner un algorithme énumérant toutes les possibilités (et non donner une heuristique). Ici, on peut proposer de prendre les tâches dans l'ordre où elles se présentent et, pour chaque tâche non encore allouée:
   
   a) allouer la tâche à chaque personne déjà existante
   b) créer une nouvelle personne et lui allouer la tâche (sauf si on a déjà trouvé une solution avec moins de personnes)
   
   Attention à ne pas considérer qu'il n'y a que 2 tâches par personne: c'est vrai dans l'exemple, mais ce n'est pas le cas général
   
3. Proposez une heuristique rapide (sans retour arrière).
   
   On peut remarquer que l'ordre des tâches n'a pas d'importance.
   Par conséquent, on peut ordonner les tâches par durée décroissante, puis affecter une tâche à la personne qu'elle "occupe" le mieux (heuristique gloutonne).
   Dans l'exemple, cela conduit à la solution.
   
4. Proposez un minorant simple (à calculer) du nombre de personnes nécessaires.
   
   Il faut au moins un nombre de personnes égal à la somme des durées des tâches divisée par la durée maximum de travail par personne.
   Dans l'exemple, c'est la solution trouvée, elle est donc nécessairement minimale.
   Une erreur fréquente est de considérer le durée moyenne d'une tâche (durée totale sur nombre de tâches): ce n'est pas une mesure de qualité.
   
5. Déduisez des questions 3 et 4 une mesure de la qualité de la solution obtenue.
   
   Il suffit de prendre le rapport entre la solution trouvée et le minorant trouvé à la question précédente. Ce rapport mesure le "taux d'occupation moyen" des personnes à qui on a distribué les tâches.
   Dans l'exemple, ce rapport est de 1 (100%), ce qui indique nécessairement une solution optimale. mais le 100% n'est pas toujours atteint, c'est en cela que cette mesure de qualité n'est qu'indicative.

Une solution consiste en la machine suivante:

• l'alphabet est {a, c, B}
• les états sont {q0, q1, q2, q3}
• programme:
  • (q0 B G q0) (q0 c G q0) (q0 a G q1)
  • (q1 a G q1) (q1 c a q2) (q1 B B q1)
  • (q2 a D q2) (q2 c G q3) (q2 B G q3)
  • (q3 a c q3) (q3 c D q3) (q3 B G q0)
• cette machine remplace chaque occurence de "ca" par "ac" et recommence jusqu'à ce qu'il n'y en ait plus. L'état terminal est l'état q1.

1. Pour n = 0, la fonction etmoidonc renvoie 0. Quant à la fonction quefaisje, elle boucle et ne renvoie donc rien. Une modification possible pour corriger le problème est d'ajouter au début le même test que celui qui figure dans la seconde fonction.
   

   fonction quefaisje(n) si n < 0 ^0 sinon, si n pair ^1 + quefaisje(n/2) sinon ^quefaisje((n-1)/2)

   fonction etmoidonc(n) si n < 0 ^0 sinon selon (n modulo 4) 0 : ^2 + etmoidonc(n/4) 1 : ^1 + etmoidonc((n-1)/4) 2 : ^1 + etmoidonc((n-2)/4) 3 : ^etmoidonc((n-3)/4)

   
   
2. Calculez, pour chacune de ces fonctions, la valeur renvoyée quand n = 4p+3 est égale à la valeur renvoyée pour n = p.
   en effet, quefaisje(4p+3) = quefaisje(2p+1) = quefaisje(p).
   
3. Si l'on regarde aussi ce qui se passe pour n = 4p+1, n=4p+2, n=4p+3, on en conclut que ces deux fonctions sont équivalentes et renvoient toujours la même valeur:

   n	f(n) = quefaisje(n)	f(n) = etmoidonc(n)
   4p	f(p)+2	f(p)+2
   4p+1	f(p)+1	f(p)+1
   4p+2	f(p)+1	f(p)+1
   4p+3	f(p)	f(p)

4. A chaque étape, la fonction quefaisje divise n par 2, il faudra donc log2(n) étapes pour calculer quefaisje(n). La fonction etmoidonc, elle, divise n par 4 et sera donc de complexité log4(n)=log2(n)/2.

Réponse à la question qui n'était pas posée: La valeur renvoyée par ces fonctions, si n est une puissance de 2 , est égale à log2(n). On en déduit alors que ces fonctions calculent le nombre de "0" après le premier "1" dans la représentation de n en base 2.

retour à l'énoncé