Formules de récurrences seulement Flashcards
(16 cards)
Quelles sont les conditions d’initialisations du problème de retour de monnaie en programmation dynamique?
C[i,0] = 0 : 0 $ à compléter
C[0,j] = +∞ : j$ à compléter mais 0 monnaie à notre disposition
C[i,j] = +∞ si j<0 : Contrainte d’intégrité réelle
Quelles sont les conditions d’initialisations du problème du sac à dos 0-1 en programmation dynamique?
V[0,j] = 0 : Capacité j mais pas d’objets
V[i,0] = 0 : On a des objets mais zéro capacité
V[i,j] = +∞ si j<0 :Contrainte d’intégrité réelle
Quelles sont les conditions d’initialisations de l’algorithme de floyd marshall en programmation dynamique?
D_0[i, j] = c(i, j) : Quand l’arête existe, le coût pour se rendre du sommet i au sommet j c’est le poids de l’arête entre i et j
D0[i, j] = +∞ : Cas où il n’existe pas pas d’arête entre le sommet i et le sommet j, la distance est donc +inf, représente conceptuellement l’inexistance d’un chemin entre deux sommets.
D0[i, i] = 0: Trivialement, la distance d’un sommet i vers lui même c’est 0.
Quelles sont les conditions d’initialisations du problème du sac à dos 0-1 en programmation dynamique?
V[0,j] = 0 -> Capacité j mais pas d’objets
V[i,0] = 0 -> On a des objets mais zéro capacité
V[i,j] = +inf si j<0 :Contrainte d’intégrité réelle
Quelle est la récurrence pour le problème du sac-à-dos en DP, version 0-1?
V[i,j] = max(V[i-1,j] , V[i-1,j-w_i] + vi]
V[i-1,j]: On a pas d’espace pour mettre l’objet x_i ducoup on passe au prochain objet
V[i-1,j-w_i] + vi: On a pris l’objet x_i, donc on met à jour la capacité du sac et sa valeurs puis on passe au prochain objet (i-1).
Quelle est la récurrence pour le problème du sac-à-dos en DP, version 0-n?
V[i,j] = max(V[i-1,j] , V[i,j-w_i] + vi]
V[i-1,j]: On a pas d’espace pour mettre l’objet x_i ducoup on passe au prochain objet
V[i,j-w_i] + vi: On a pris l’objet x_i, donc on met à jour la capacité du sac et sa valeurs puis on reste sur la même ligne car on peut toujours prendre le même objet (i).
Quelle est la récurrence pour le problème de retour de monnaie en DP?
C[i,j] = min(C[i-1,j] , C[i,j-vi] +1]
C[i-1,j]: La valeur de la pièce est trop grande pour rentrer dans j, donc on passe à celle d’avant
C[i,j-vi] +1: On prend la pièce i alors on update le montant restant j et on incrémente de 1 car on a utilisé 1 pièce.
Quelle est la récurrence pour le problème des plus courts chemins en DP (Algorithme de Floyd Marshall)?
La matrice D_k base toujours sa construction la matrice précédente D_k-1
et chaque nouvelle matrice introduit un nouveau sommet k
par lequel on peut passer
la logique, c’est que la nouvelle matrice pour chaque semaine, soit on prend le même chemin que la dernière matrice, soit on passe par le nouveau sommet par lequel on a introduit et on prend le minimum
D_k [i, j] = min( D_k−1[i, j], Dk−1[i, k] + D_k−1[k, j])
Quelles sont les conditions d’initialisations du problème de recheche de motifs par minimisation de distance d’édition?
D[0,j] = 0: Un motif vide est toujours trouvé dans n’importe quel préfixe du texte sans aucune opération
D[i,0] = i: Il faut i opérations (insertions ou suppressions) pour aligner les i premiers caractères du motif avec rien
Quelle est la récurrence pour du problème de recheche de motifs par minimisation de distance d’édition?
Exactement la même reccurrence que l’alignement global par minimisation de distance, la différence fondamentale est réside dans les conditions d’initialisations
D[i,j] = min( D[i-1,j] + 1, D[i,j-1] + 1 , D[i-1,j-1] + c(i-1,j-1)]
où c(i,j) = 0 si match (i=j), 1 si mistmach (i different de j)
Quelle est la récurrence pour le problème du problème d’alignement local par maximisation de la valeur de similiarité en programmation dynamique?
On cherche à maximiser la valeur de similarité mais seulement localement donc, on introduit des pénalités avec l’option de reset à 0 :
V[i,j] = max([V[i-1,j] -2, V[i,j-1] -2, V[i-1,j-1] + c(i-1,j-1), 0 ]
ou c(i,j) = -1 si mistmatch, +2 si match
Quelle est la récurrence pour le problème du problème d’alignement global par minimisation de la distance d’édition en programmation dynamique?
D[i,j] = min( D[i-1,j] + 1, D[i,j-1] +1 , D[i-1,j-1] + c(i-1,j-1)]
où c(i,j) = 0 si match (i=j), 1 si mistmach (i different de j)
Quelles sont les conditions d’initialisations du problème d’alignement global par minimisation de la distance d’édition en programmation dynamique?
ici ,on cherche à
D(i, 0) = i : i décalage ‘-‘ à faire pour aligner S et avec 0 caractère de T
D(0, j) = j: j décalage opérations à faire pour aligner 0 caractère de S avec T
Quelles sont les conditions d’initialisations du problème d’alignement global par maximisation de la valeur de similiarité en programmation dynamique?
On cumule les pénalités:
D(i,0) = -2 x i
D(0,j) = -2 x j
Quelles sont les conditions d’initialisations du problème d’alignement local par maximisation de la valeur de similiarité en programmation dynamique?
On no cumule pas les pénailités car on ne s’intérésse pas à l’alignement global. On met 0 basically:
D[i,0] = 0 -> Rien à aligner localement:
on commence à tout moment, pas de pénalité
D[0,j] = 0 -> Rien à aligner localement: meme délire, on commence à tout moment, pas de pénalité
Quelle est la récurrence pour le problème du problème d’alignement global par maximisation de la valeur de similarité en programmation dynamique?
On cherche à maximiser donc, on introduit des pénalités:
V[i,j] = max([V[i-1,j] -2, V[i,j-1] -2, V[i-1,j-1] + c(i-1,j-1) ]
ou c(i,j) = -1 si mistmatch, +2 si match
