X ENS Informatique Commune PSI PT 2007

(Durée : 2 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de copie.
On attachera une grande importance à la concision, à la clarté, et à la précision de la rédaction.

Le temps d'exécution d'une fonction est le nombre d'opérations élémentaires (addition, soustraction, multiplication, division, affectation, etc.) nécessaire au calcul de . Lorsque ce temps d'exécution dépend d'un paramètre , il sera noté . On dit que la fonction s'exécute en temps s'il existe tel que pour tout , on a .

Un tailleur de tissus dispose d'une grande pièce de tissu ainsi que d'une liste de produits qu'il peut fabriquer à l'aide de ce tissu. La pièce de tissu n'a qu'une seule dimension, il s'agit donc d'un ruban de longueur . Pour chaque produit, le tailleur sait quelle quantité de tissu est nécessaire et il connaît son prix de vente. Le tailleur doit décider quels produits il va réaliser pour maximiser sa rentrée d'argent . Chacun des produits réalisables a une longueur et un prix de vente , . Toutes les dimensions et prix de vente sont des entiers strictement positifs.

Dans cette partie, chaque produit peut être réalisé un nombre arbitraire de fois (éventuellement nul). Un découpage (non optimal) possible est illustré ci-dessous pour .

Informatiquement, on stockera la suite des longueurs et des prix de vente dans deux tableaux et de éléments. On remarquera aussi que la découpe du tissu est commutative, puisque découper le produit puis le produit donne le même résultat que découper le produit puis le produit .

Question 1 Considérer l'exemple suivant : et . Calculer lorsque .
Question 2 Reprendre l'exemple précédent avec .
On se place d'abord dans les cas ou . Pour , on calcule tous les prix de vente obtenus en coupant , ou fois le premier produit et le reste du tissu avec le
deuxième produit. Et on retient le maximal. De même pour , on commence par couper plusieurs fois le premier produit, puis le deuxième produit et le reste avec le troisième produit.
Question 3 Écrire la fonction coutRuban2Produits qui prend en arguments les longueurs et les prix de ventes de deux produits et la longueur totale du ruban de tissu ; et qui retourne le prix de vente maximal possible après découpe.
Question 4 Écrire la fonction coutRuban3Produits qui prend en arguments les longueurs et les prix de ventes de trois produits et la longueur totale du ruban de tissu ; et qui retourne le prix de vente maximal possible après découpe.

On peut montrer qu'un tel algorithme de calcul prend un temps exponentiel en dans le cas général de produits. On va donc utiliser une méthode dite de «programmation dynamique» dans ce cas général en prenant pour acquise la formule de récurrence suivante, où est le coût maximal obtenu après découpe des produits pour un ruban de longueur :

Par convention, on posera que le maximum de l'ensemble vide vaut 0 . On stockera les valeurs de pour dans un tableau M.

Question 5 Écrire la fonction coutRuban qui prend en arguments les tableaux des longueurs et des prix de vente des produits, ainsi que la longueur du ruban; et qui retourne le prix de vente maximal en calculant le tableau M décrit précédemment. Donner un ordre de grandeur du temps d'exécution de cette fonction.

Pour imprimer la solution donnant le prix de vente maximal, il faut se souvenir de la coupe pratiquée pour obtenir ce maximal. Pour cela, on utilise un tableau tel que donne l'indice du produit tel que soit maximal. Lorsque , on posera . Une liste de découpes réalisant la valeur peut alors être retrouvée à partir du tableau . Par exemple, la première coupe est , la seconde , jusqu'à ce qu'on tombe sur la valeur par défaut -1 .
Question 6 Écrire la fonction decoupageRuban qui prend en arguments les tableaux des longueurs et des prix de vente, ainsi que la longueur du ruban; et qui imprime la liste des découpes successives produisant la valeur , en calculant le tableau . Donner un ordre de grandeur du temps d'exécution de cette fonction.

Dans cette partie, le tailleur ne peut fabriquer plus d'une fois le produit car la demande n'excède pas ce nombre.

Question 7 Trouver une formule de récurrence donnant le coût maximal que l'on peut obtenir avec un ruban de longueur en ne découpant que parmi les produits .

On stockera les valeurs de pour et dans un tableau M à deux dimensions.

Question 8 Écrire une fonction coutRubanSansRepetitions( ) qui prend en arguments les tableaux des longueurs et des prix de vente des produits ainsi que la longueur du ruban; et qui retourne le prix de vente maximal en calculant le tableau M décrit précédemment. Donner un ordre de grandeur du temps d'exécution de cette fonction.

Question 9 Réécrire cette fonction en ne se servant que de deux tableaux de éléments, réduisant la taille mémoire utilisée à .