Diviser pour régner et programmation dynamique

Cette page propose plusieurs exercices corrigés sur les algorithmes, plus particulièrement sur le paradigme Divide & Conquer (Diviser pour régner) et la programmation dynamique.

Diviser pour régner et la programmation dynamique

Exercice 1

Écrivez un pseudo-code pour un algorithme de division et de conquête permettant de trouver la position du plus grand élément dans un tableau de nombres. Écrivez un pseudo-code pour un algorithme de force brute, comparez avec le précédent. Montrez un arbre du processus de l’algorithme diviser pour mieux régner. Quel est le niveau maximal de l’arborescence pour les nombres ?

Solution

diviser pour régner programmation dynamique exercices corrigés

L’algorithme de force brute est trivial : une boucle.

A chaque niveau l, l’arbre binaire complet est composé de 2^(l-1) feuille. Donc le total des sommets est 2^l -1. Soit l le niveau de l’arbre, donc l=sup(log_2 (n)).

Exercice 2

Écrivez un pseudo-code pour un algorithme de division pour régner pour le problème d’exponentiation du calcul de a^n où a>0 et n est un entier positif. Écrivez un pseudo-code pour un algorithme de force brute, comparez avec le précédent. Montrez un arbre du processus de l’algorithme diviser pour mieux régner. Quel est le niveau maximum de l’arbre pour n non donné ? Vérifier la terminaison, l’exactitude et l’exhaustivité.

Solution

diviser pour régner programmation dynamique exercices corrigés

Exercice 3

On vous donne un tableau avec des entiers (positif, négatif, zéro) et vous êtes censé trouver la somme contiguë maximale dans ce tableau. Par conséquent, vous devez trouver un sous-tableau qui donne la plus grande somme. Exemple, si le tableau donné est : 5, -6, 7, 12, -3, 0, -11, -6

Solution

Supposons que votre tableau d’entrée s’appelle A. Ce que vous devez faire est de former un autre tableau, disons B, dont chaque valeur i est calculée en utilisant la formule récursive, max(A[i], B[i-1]+A[i ])

Ce que vous faites effectivement, c’est que vous choisissez d’étendre la fenêtre précédente ou d’en démarrer une nouvelle. Vous pouvez le faire puisque vous n’êtes censé sélectionner que des éléments continus dans le cadre de vos sous-ensembles.

5, -6, 7, 12, -3, 0, -11, -6

La réponse serait 19 (du sous-tableau {7,12} )

Exercice 4

Utilisez la sous-chaîne commune la plus longue pour : BDCABA et ABCBDAB. L’algorithme est décrit comme suit:

diviser pour régner programmation dynamique exercices corrigés sous-chaîne commune

Solution

diviser pour régner programmation dynamique exercices corrigés sous-chaîne commune

Exercice 5

Adaptez la sous-chaîne commune la plus longue à la sous-séquence commune la plus longue : BDCABA et ABCBDAB. Le problème de la plus longue sous-séquence commune (LCS) consiste à trouver la plus longue sous-séquence commune à toutes les séquences d’un ensemble de séquences (souvent seulement deux séquences).

Cela diffère des problèmes de recherche de sous-chaînes communes : contrairement aux sous-chaînes, les sous-séquences ne sont pas obligées d’occuper des positions consécutives dans les séquences d’origine.

Solution

diviser pour régner programmation dynamique exercices corrigés sous-séquence maximum

diviser pour régner programmation dynamique exercices corrigés sous-séquence maximum

Exercice 6

La distance de Levenshtein est une métrique de chaîne permettant de mesurer la différence entre deux séquences. De manière informelle, la distance de Levenshtein entre deux mots est le nombre minimum de modifications d’un seul caractère (c’est-à-dire des insertions, des suppressions ou des substitutions) nécessaires pour changer un mot en l’autre. Proposer un programme dynamique pour résoudre ce problème. Essai avec MEILENSTEIN et LEVENSHTEIN.

Solution

diviser pour régner programmation dynamique exercices corrigés distance de Levenshtein

diviser pour régner programmation dynamique exercices corrigés distance de Levenshtein

Partager
fr_FRFR
%d blogueurs aiment cette page :