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}.

(a) 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,

(b) En donner un autre avec une récurrence sur le nombre de partitions en j parts,

(c) Quelle est la différence entre les deux récurrences? Pourquoi?

(d) 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^{2}. Le bord supérieur et le bord inférieur de la pièce sont des lignes brisées A_{1}, ⋯, A_{n} d’une part et B_{1}, ⋯, B_{m} de l’autre, et les extrémités latérales sont les segments A_{1}, B_{1} 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^{2} 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).