Exercice 1 : (probléme cout min)
Étant donné une matrice_coût [] [] et une position (m, n) dans cette matrice, écrivez une fonction qui renvoie le coût du chemin minimal qui permet d’atteindre (m, n) à partir de (0, 0). Chaque cellule de la matrice représente un coût pour traverser cette cellule. Le coût total d'un chemin à atteindre (m, n) est la somme de tous les coûts sur ce chemin (y compris la source et la destination). Vous ne pouvez traverser que les cellules inférieures d’une cellule donnée, c’est-à-dire d’une cellule donnée (i, j), les cellules (i + 1, j), (i, j + 1) et (i + 1, j + 1) peut être parcouru. Vous pouvez supposer que tous les coûts sont des entiers positifs. Par exemple, dans la figure suivante, quel est le chemin de coût minimal vers (2, 2)?
Le chemin avec un coût minimum est mis en évidence dans la figure suivante. Le chemin est (0, 0) -> (0, 1) -> (1, 2) -> (2, 2). Le coût du chemin est de 8 (1 + 2 + 2 + 3) comme le montre la figure suivante :
Q1 : ecrire un algorithme qui permet de résoudre ce probléme
Q2 : calculer la complexité de cet algorithme
Q3 : prouver que ce ptobléme peut étre résolut utilisant la programmation dynamique
Exercice 2 : (probléme plus longue sous-séquence croissantes)
Le problème de la plus longue sous-séquence croissante (LIS) consiste à trouver la longueur de la sous-séquence la plus longue d'une séquence donnée, de sorte que tous les éléments de la sous-séquence soient triés par ordre croissant. Par exemple, la longueur de LIS pour {10, 22, 9, 33, 21, 50, 41, 60, 80} est de 6 et LIS est de {10, 22, 33, 50, 60, 80}.
Q1 : Proposer un algorithme récursive simple pour résoudre ce problème
Q2 : calculer la complexité de l’algorithme
Q3 : prouver que ce problème peut être résolut utilisant la programmation dynamique
Exercice 3 :
Étant donné deux chaînes de caractères str1 et str2 et les opérations inférieures pouvant être effectuées sur str1. Trouvez le nombre minimal de modifications (opérations) nécessaires pour convertir «str1» en «str2» :Insérer, éliminer et Remplacer. Toutes les opérations ci-dessus ont un coût égal.
Exemples :
Ex1: Entrée: str1 = "geek", str2 = "gesek" Sortie: 1. Nous pouvons convertir str1 en str2 en insérant un 's'.
Ex2 : Entrée: str1 = "cat", str2 = "cut" Sortie: 1 Nous pouvons convertir str1 en str2 en remplaçant "a" par "u".
Ex3 : Entrée: str1 = "sunday", str2 = "saturday" Sortie: 3. Les trois derniers et les premiers caractères sont identiques. Nous avons essentiellement besoin de convertir "un" en "atur". Cela peut être fait en utilisant trois opérations. Remplacez 'n' par 'r', insérez t, insérez a.
Q 1 : écrire un algorithme récursif qui permet de résoudre ce problème
Q2 : Calculer la complexité de l’algorithme
Q3 : prouver que ce problème peut être résolut utilisant la programmation dynamique en indiquant quels sont les sous problèmes et le chevauchement des problèmes.
Q4 : proposer une solution utilisant la programmation dynamique
Exercice 4 : (echange de monnaie )
Étant donné une valeur N, si nous souhaitogns changer de monnaie pour N cents et que nous avons une offre infinie de pièces de valeur S = {S1, S2, .., Sm}, combien de façons pouvons-nous effectuer le changement? L'ordre des pièces n'a pas d'importance.
Par exemple, pour N = 4 et S = {1,2,3}, il existe quatre solutions: {1,1,1,1}, {1,1,2}, {2,2}, {1, 3}. La sortie devrait donc être 4. Pour N = 10 et S = {2, 5, 3, 6}, il existe cinq solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} et {5,5}. Donc, le résultat devrait être 5.
Exercice 5 : (Multiplication de la chaîne matricielle)
Calculer le nombre de multiplication nécessaire pour calculer :
A(5,4) * b(4*6)* c(6,2)* d(2,7)
Ecrire un algorithme qui permet de trouver la combinaison qui donne le minimum d’opérations