Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

dynam Programmation dynamique A Principe général B Application Triangle de Pascal Série mondiale Multiplication cha? née de matrices Les plus courts chemins CProgrammation dynamique Principe général ? Souvent pour résoudre un problème de taille n on s'ape

Programmation dynamique A Principe général B Application Triangle de Pascal Série mondiale Multiplication cha? née de matrices Les plus courts chemins CProgrammation dynamique Principe général ? Souvent pour résoudre un problème de taille n on s'aperçoit qu'il est composé de plusieurs sous problèmes identiques Si on résout chaque sous exemplaire séparément sans tenir compte de cette duplication on obtient un algorithme très ine ?cace Par contre si on résout chaque sous exemplaire di ?érent une seule fois en sauvegardant les résultats on obtient un algorithme performant ? Idée de base Éviter de calculer deux fois la même chose normalement en utilisant une table de résultats déjà calculés remplie au fur et à mesure qu'on résout les sous problèmes CProgrammation dynamique Principe général ? Remarques ?? C'est une méthode ascendante On commence d'habitude par les sous problèmes les plus petits et on remonte vers les sous problèmes de plus en plus di ?cile ?? La programmation dynamique est souvent employée pour résoudre des problèmes d'optimisation satisfaisant le principe d'optimalité Dans une séquence optimale de décisions ou de choix chaque sous-séquence doit aussi être optimale CProgrammation dynamique Application Calcul de Cnp ? Formules Cnp Cn- p- Cn- p C Cn Cnn ? On peut donner un algorithme récursif CProgrammation dynamique Application Calcul de Cnp ? On peut aussi faire le calcul par programmation dynamique triangle de Pascal CProgrammation dynamique Application Série mondiale ? A et B disputent une série de matchs au maximum n- ? L'équipe gagnante est celle qui reporte n victoires ? La probabilité que A gagne est une partie q ? La probabilité que B gagne est une partie q CProgrammation dynamique Application Série mondiale ? On dé ?nit P i j comme la probabilité que A remporte la série sachant qu'elle doit encore gagner i victoires contre B j victoires ? On a ainsi P j A a déjà gagné la série et j P i A a déjà perdu la série et i ? P indé ?ni ? P i j q P i- j q P i j- i j CProgrammation dynamique Application Série mondiale ? Algorithme récursif P i j Si i et j P Sinon Si i et j P Sinon Si i et j P q P i- j q P i j- CProgrammation dynamique Application Série mondiale ? T k temps d'exécution de P i j avec k i j ? Équation de récurrence T k T k- b ? Solution T k C k C O k O i j ? P n n O n CProgrammation dynamique Application Série mondiale ? Programmation dynamique P i j Pour S i j P S P S Pour k S - P k S -k q P k- S -k q P k S -k- Finpour Finpour ? C'est O n CProgrammation dynamique Application Série mondiale ? Utilisation d'une table CProgrammation dynamique Application Les plus courts chemins Algorithme de Floyd ? Le problème consiste à trouver les plus courts chemins entre chaque couple