Licence de Sciences et Technologies, option Informatique
Algorithmique Avancée
TD 5: octobre/novembre 2006
Programmation Dynamique

1. On considère le calcul du nombre de partitions d'un entier positif n. Une partition est une division de n en parts où l'ordre des parts n'est pas pris en compte. Donc, par exemple, 4 a les 5 partitions, {4}, {3,1}, {2,2}, {2,1,1} et {1,1,1,1}.

   1. Dans le cour on vous a donné un algorithme de ce calcul en utilisant une récurrence sur le nombre de partitions avec plus grande part i,
   2. En donner un autre avec une récurrence sur le nombre de partitions en j parts,
   3. Quelle est la différence entre les deux récurrences? Pourquoi?
   4. Donner un autre algorithme plus performant qui a comme paramètre un majorant de la plus grande part (ou du nombre de parts) au lieu du nombre exact.
2. Je veux découper une pièce de bois en sections de superficie maximum 1000 cm². Le bord supérieur et le bord inférieur de la pièce sont des lignes brisées A₁,…,A_n d'une part et B₁,…,B_m de l'autre, et les extrémités latérales sont les segments A₁,B₁ et A_n,B_m. Je dois couper suivant des traits rectilignes joignant certains des points A_i à certains des points B_j sans faire deux coupes qui se croisent, sauf à un des points A_i ou B_j.
   Il y a deux tableaux Cout et Droite à deux dimensions avec les données: Cout[i][j] le coût de faire une coupe de A_i à B_j et Droite[i][j] la superficie en cm² de la partie à droite de cette coupe.
   Donner un algorithme qui calcule le coût minimum de la découpe (en utilisant la programmation dynamique).

---

File translated from T_EX by T_TH, version 3.05.
On 30 Oct 2006, 16:12.