Programación Dinámica Probabilística

Programaci´n din´mica o a
Problemas, algoritmos y programaci´n o

31 de Agosto 2011

Problemas, algoritmos y programaci´n o

Programaci´n din´mica o a

Problema: diff

El comando diff diff es un comando de Linux que muestra las diferencias en el contenido de dos textos (equivalente a fc.exe de Windows/DOS) ¿C´ando se usa? u Se usa, entre otras cosas, para comparar ediciones (versiones)de un mismo archivo ¿C´mo compara? o El criterio por defecto es buscar l´ ıneas comunes a ambos archivos.

Problemas, algoritmos y programaci´n o

Programaci´n din´mica o a

Problema: diff - Ejemplo

Nueva versi´n o
/** * main class of diff program */ */ class Diff { /* calculate common lines */ int commonLines(File a, File b) { String contentA = read(a); //fixed String contentB = read(b);ParsedText pA = parse(contentA); ParsedText pB = parse(contentB); int result = LCS.calculate(pA, pB); return result; } }

Versi´n “original” o
class Diff { int commonLines(File a, File b) { String contentA = read(b); String contentB = read(b); String[] pA = split(contentA); String[] pB = split(contentB); int result = LCS.calculate(pA, pB); return result; } }

Referencia de colores l´ ıneassin cambios l´ ıneas nuevas l´ ıneas eliminadas

Problemas, algoritmos y programaci´n o

Programaci´n din´mica o a

Problema: diff

Operaciones de moficiaci´n o Sin operaci´n : las l´ o ıneas comunes Inserci´n : las l´ o ıneas no comunes del nuevo Borrado : las l´ ıneas no comunes del “original” ¿Cu´l es el problema? a Para hacer una buena comparaci´n de archivos, hay que tener un oalgoritmo que encuentre la mayor cantidad de l´ ıneas comunes entre a ıneas comunes tienen que aparecer con el ambos. Adem´s, las l´ m´ ısmo orden en ambos archivos.

Problemas, algoritmos y programaci´n o

Programaci´n din´mica o a

Problema: diff
Generalizaci´n o A este problema se lo conoce como encontrar la sub-secuencia com´n de mayor longitud (o Longest Common Subsequence) u Longest CommonSubsequence Entrada: dos sequencias (vectores, arreglos) A y B Salida: la longitud de la sub-secuencia com´n a A y a B mas u larga posible LCS : (T [], T []) → int Ejemplos LCS([X AABBDZ ], [AX AC BDY ]) = 4 LCS([], [XXYY ]) = 0 LCS([123456], [123456]) = 6 LCS([♠♠♠♥], [♥♠♠♠]) = 3
Problemas, algoritmos y programaci´n o Programaci´n din´mica o a

Problema: diff - ¿C´mo se puede resolver? o

M´sproblemas a Se calculan las LCS de todos los prefijos de A contra todos los prefijos de B Entre estos resultados est´ la LCS de A y B a Si n y m son el tama˜o de A y B, la cantidad de LCS que se n van a calcular son (n + 1)(m + 1) Cada prefijo de A se puede identificar con su longitud, que es un n´mero del 0 al n. De la misma forma, cada prefijo de B u se identifica con los n´meros del 0 al m. u LCS2 :(int, int, T [], T []) → int

Problemas, algoritmos y programaci´n o

Programaci´n din´mica o a

Problema: diff - ¿C´mo se puede resolver? o
Ejemplo con los archivos Prefijo 8
/** * main class of diff program */ */ class Diff { /* calculate common lines */ int commonLines(File a, File b) { String contentA = read(a); //fixed String contentB = read(b);

Prefijo 5
class Diff { intcommonLines(File a, File b) { String contentA = read(b); String contentB = read(b); String[] pA = split(contentA);

Algunos valores de LCS2 LCS2 (8, 5, nuevo, original) = 3 LCS2 (4, 1, nuevo, original) = 1 LCS2 (5, 0, nuevo, original) = 0 LCS2 (5, 1, nuevo, original) = 1 LCS2 (6, 2, nuevo, original) = 2
Problemas, algoritmos y programaci´n o Programaci´n din´mica o a

Problema: diff - ¿C´mo se puederesolver? o

Caso 1/3 - Base Alguno de los dos prefijos tiene longitud 0, entonces la LCS es 0 LCS2 (0, , , ) = 0 LCS2 ( , 0, , ) = 0

Problemas, algoritmos y programaci´n o

Programaci´n din´mica o a

Problema: diff - ¿C´mo se puede resolver? o
Caso 2/3 - Terminan igual Los dos prefijos terminan con el mismo elemento, entonces hay una LCS para estos prefijos que termina en este elemento...