Programmation dynamique

Chaîne de multiplications matricielles

: Implémentez l’algorithme vu en cours pour trouver le parenthésage optimal pour la multiplication chaînée de matrices . Votre algorithme doit prendre en entrée une suite de longueur contenant les dimensions des matrices et doit renvoyer le nombre minimal de produits scalaires qu’on doit effectuer afin de multiplier ces matrices ainsi que le parenthésage optimal lié à ce nombre.

Testez votre implémentation pour une suite de matrices dont les dimensions sont données par la séquence , c’est-à-dire, la matrice est de dimension , la matrice est de dimension etc. Votre programme doit renvoyer pour cet exemple comme nombre minimal de produit scalaires à effectuer. Le parenthésage optimal associé à ce nombre est

Egg drop

Supposons que nous nous retrouvons devant un très haut immeuble avec un sac rempli d’œufs. Tous nos œufs sont identiques et très durs à casser. On s’intéresse à savoir quel est l’étage le plus haut duquel on peut lâcher un œuf sans qu’il ne se casse. Cependant, on souhaite répondre à cette question en cassant le moins d’œufs possible. Notre problème algorithmique peut alors se formuler de la façon suivante : Étant donné le nombre d’étages de l’immeuble et le nombre d’œufs disponibles, quel est le nombre minimum d’essais qu’on doit faire afin de déterminer l’étage critique, ç.-à-d. l’étage à partir duquel tous les œufs se cassent.

On fait plusieurs suppositions :

On note le nombre d’œufs qu’on possède et le nombre d’étages de l’immeuble.

Cas

Si nous ne possédons qu’un seul œuf, il n’y a qu’une seule façon de procéder : On lance d’abord l’œuf depuis l’étage 1, ensuite depuis l’étage 2, puis 3 etc. jusqu’à ce que soit l’œuf se casse soit il survit à une chute du tout dernier étage. Dans le pire cas, cette procédure nécessitera étapes, et est alors la réponse à notre problème.

Problème général avec œufs et étages.

La stratégie consiste à lâcher un œuf de chaque étage possible (de à ) et calculer récursivement le nombre minimal de lâchers nécessaires dans le pire cas. L’étage qui donne la valeur minimale dans le pire cas fera partie de la solution.

Sous-structure optimale

Quand on lâche un œuf d’un étage , deux cas sont possibles :

  1. L’œuf se casse. Si l’œuf se casse à l’étage , alors nous n’avons qu’à vérifier avec les œufs restant les étages inférieurs à . Le problème est dans ce cas réduit à un problème avec étages et œufs.

  2. L’œuf ne se casse pas. Si l’œuf ne se casse pas après l’avoir lâché de l’étage , alors nous n’avons qu’à tester les étages supérieurs à . Dans ce cas, notre problème se réduit à un problème avec étages et œufs.

Puisque nous cherchons à minimiser le nombre d’essais dans le pire cas, on considère la valeur maximale de ces deux cas et on choisit l’étage qui donne le nombre minimal d’essais.

On note eggDrop(n,h) le nombre minimal d’essais pour trouver l’étage critique (celui à partir duquel les œufs se brisent). Cette valeur peut être calculée de façon récursive en utilisant l’équation récursive suivante :

: Écrire une fonction en Python, qui prend en entrée le nombre d’œufs et le nombre d’étages et qui renvoie le nombre optimal d’essais en se basant sur l’équation de récurrence ci-dessus.

Testez que pour et votre programme renvoie . Testez l’efficacité de votre programme pour des valeurs plus grandes. Que se passe-t-il ? Pourquoi ?

Résoudre le problème à l’aide de la programmation dynamique.

Si vous dessinez l’arbre de la récursivité pour des petites valeurs de et de vous allez remarquer qu’avec l’approche précédente, certains sous-problèmes sont résolus plus d’une fois. Comme c’est le cas d’autres problèmes typiques de la programmation dynamique, le re-calcul des mêmes sous-problèmes peut être évité en sauvegardant les solutions de chaque sous-problème dans un tableau. Ce tableau sera rempli des valeurs les plus petites aux valeurs les plus élevées.

: Concevoir un algorithme et l’implémenter ensuite en Python pour résoudre le problème selon les principes de la programmation dynamique.