Scribd
Importer
24 vues4 pages

CC Algo N°2 05/12/2024 - Sans Documents - 30': Centrale Méditerranée

Le document présente un exercice sur la programmation dynamique pour le calcul du produit de matrices. Il décrit les étapes nécessaires pour déterminer le meilleur parenthésage afin de minimiser le nombre de multiplications scalaires. Plusieurs questions sont posées concernant la définition des problèmes, la conception d'un algorithme et la récupération du parenthésage optimal.

Transféré par

jackelruss
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
24 vues4 pages

CC Algo N°2 05/12/2024 - Sans Documents - 30': Centrale Méditerranée

Le document présente un exercice sur la programmation dynamique pour le calcul du produit de matrices. Il décrit les étapes nécessaires pour déterminer le meilleur parenthésage afin de minimiser le nombre de multiplications scalaires. Plusieurs questions sont posées concernant la définition des problèmes, la conception d'un algorithme et la récupération du parenthésage optimal.

Transféré par

jackelruss
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

1A - Informatique Centrale Méditerranée

CC Algo n°2
05/12/2024 - Sans documents - 30’

Préambule
On rappelle que pour résoudre un problème avec un algorithme de programmation dynamique il
faut identifier une série de problème 𝑃𝑖 tes que :
- Vous savez résoudre de façon triviale le problème 𝑃0 ou le problème 𝑃1.
- Vous savez résoudre le problème 𝑃𝑖+1 à partir de la solution du problème 𝑃𝑖. Cela se
matérialise par une formule de récurrence qui vous donne la ou les solutions du
problème 𝑃𝑖+1 en fonction de la ou des solutions du problème 𝑃𝑖.
- Le problème que vous souhaitez résoudre est le problème 𝑃𝑛 pour un certain entier n>1.

Exercice
𝑝×𝑞
On veut calculer le produit de matrices 𝑀 = 𝑀1 × 𝑀2 ×... × 𝑀𝑛. Multiplier une matrice 𝐴 ∈ ℜ
𝑞×𝑟
par une matrice 𝐵 ∈ ℜ en utilisant la méthode standard nécessite 𝑝 × 𝑞 × 𝑟 multiplications
élémentaires.

Question 1
20×5 5×100 100×8 8×30
Considérons 4 matrices 𝐴 ∈ ℜ ,𝐵 ∈ℜ ,𝐶 ∈ℜ ,𝐷 ∈ℜ . On veut calculer le
produit ABCD. En fonction du parenthésage, le nombre de produits varie. Déterminer le nombre
de produits pour calculer ABCD, si on utilise les parenthétisations suivantes :
(𝐴 × 𝐵) × 𝐶) × 𝐷 ou 𝐴 × (𝐵 × 𝐶) × 𝐷

1
Question 2
L’objectif est de concevoir un algorithme déterminant le meilleur parenthésage, c’est-à-dire qui
permet de minimiser le nombre de produits scalaires.
𝑑𝑖−1×𝑑𝑖
On considère que 𝑀𝑖 ∈ ℜ . Définir une série de problèmes 𝑃𝑖 vous permettant de résoudre
le problème posé à l’aide de la programmation dynamique. Justifiez votre choix en montrant
comment vous pouvez résoudre le problème 𝑃𝑖+1 à partir de la résolution du problème 𝑃𝑖. Vous
pourrez considérer des quantités 𝑐(𝑖, 𝑗) où 𝑐(𝑖, 𝑗) est le nombre minimal de produits scalaires
nécessaires pour évaluer le produit des matrices 𝑀𝑖 ×... × 𝑀𝑗, quantités dont il faudra expliciter
le calcul.

2
Question 3 : Ecrire un algorithme de programmation dynamique pour résoudre le problème

3
Question 4 : L'algorithme précédent détermine le coût minimal obtenu avec un parenthésage
optimal mais ne donne pas explicitement le parenthésage optimal. Quelles sont les deux
méthodes pour récupérer la solution d’un algorithme de programmation dynamique, c’est-à-dire
le parenthésage ici ? Modifier l’algorithme précédent pour récupérer et afficher le parenthésage
optimal avec l’une de ces méthodes.

Vous aimerez peut-être aussi