Comparación de algoritmos KMP y Boyer-Moore
Enviado por Programa Chuletas y clasificado en Otras materias
Escrito el en 
español con un tamaño de 3,79 KB
Compare los algoritmos KMP y Boyer-Moore
Ambos algoritmos se emplean en la búsqda de patrones en secuencias. En cuanto a la metodología q emplean podemos decir q el algoritmo Knuth-Morris-Pratt (KMP) realiza la comparación d caracteres del patrón de izquierda a derecha, al contrario q el algoritmo Boyer-Moore (BM) q lo compara de derecha a izquierda. Sin embargo, ambos desplazan el patrón de izquierda a derecha con respecto a la secuencia.Ambos tratan de aprovechar el conocimiento del patrón adquirido en cada comparación. El algoritmo BM es un algoritmo sublineal y por ello no necesita examinar todos los caracteres de la ocurrencia del patrón. Se basa n dos reglas para realizar las comparaciones y se utilizará una u otra dependiendo de en qué carácter falle la comparación. El KMP utiliza siempre el mismo criterio en sus comparaciones. También cabe destacar, q el algoritmo KMP se basa en el cálculo de un vector llamado siguiente para saber como desplazar el patrón P cuando falle en alguna comparación con la secuencia S, sin embargo, el algoritmo BM necesita para su implementación el cálculo de dos vectores d1 y d2 (para cada una de las reglas). En cuanto al coste computacional, diremos q en el caso de estos dos algoritmos, dependerá del número de comparaciones a realizar, En el KMP sabemos q realizará como máximo n comparaciones (siendo n la longitud en caracteres de la secuencia) y en el caso de BM sabemos q el número de comparaciones será inferior a n en la mayoría de los casos, normalmente empleará m + n/m comparaciones (siendo m la longitud del patrón). Por lo q se deduce q el algoritmo BM es más eficiente q el KMP. Además aumenta su eficie n cia cuanto mayor es m.
Compare KMP y búsqda directa
Ambos son algoritmos q se emplean en la búsqda de patrones.En cuanto a la metodología sabemos q el algoritmo de Búsqda Directa compara el p atrón P con la secuencia S carácter a carácter hasta q encuentra la coincidencia, si existe. El algoritmo KMP también compara el patrón P con la secuencia S y lo hace también de izquierda a derecha, la diferencia reside en q el algoritmo KMP aprovecha el “conocimiento” adquirido en las anteriores comparaciones. En cuanto al número de comparaciones tenemos q el algoritmo de Búsqda Directa emplea por lo general un número proporcional a n·m, donde n es la longitud de la secuencia y m es la longitud del patrón, y en el mejor de los casos n = m. Por otra parte tenemos q el algoritmo KMP emplea como máximo n comparaciones, por lo q podemos decir q es más eficiente.
Expliq el algoritmo de Mezcla directa
Es un algoritmo de clasificación de datos en memoria secundaria (también conocido como combinación directa) y consiste en realizar sucesivas pasadas de mezcla tratando de obtener secuencias ordenadas cada vez más largas hasta q finalmente se
obtiene una única secuencia ordenada con la totalidad de los elementos.Inicialmente se supone q si existen n datos en la secuencia inicial no ordenada se pueden descomponer en n secuencias ordenadas de longitud uno. Después, se combinan
estas secuencias dos a dos, y se obtienen n/2 secuencias ordenadas de longitud 2.Repitiendo el proceso se llega finalmente a obtener una única secuencia ordenada de longitud n.
Ambos algoritmos se emplean en la búsqda de patrones en secuencias. En cuanto a la metodología q emplean podemos decir q el algoritmo Knuth-Morris-Pratt (KMP) realiza la comparación d caracteres del patrón de izquierda a derecha, al contrario q el algoritmo Boyer-Moore (BM) q lo compara de derecha a izquierda. Sin embargo, ambos desplazan el patrón de izquierda a derecha con respecto a la secuencia.Ambos tratan de aprovechar el conocimiento del patrón adquirido en cada comparación. El algoritmo BM es un algoritmo sublineal y por ello no necesita examinar todos los caracteres de la ocurrencia del patrón. Se basa n dos reglas para realizar las comparaciones y se utilizará una u otra dependiendo de en qué carácter falle la comparación. El KMP utiliza siempre el mismo criterio en sus comparaciones. También cabe destacar, q el algoritmo KMP se basa en el cálculo de un vector llamado siguiente para saber como desplazar el patrón P cuando falle en alguna comparación con la secuencia S, sin embargo, el algoritmo BM necesita para su implementación el cálculo de dos vectores d1 y d2 (para cada una de las reglas). En cuanto al coste computacional, diremos q en el caso de estos dos algoritmos, dependerá del número de comparaciones a realizar, En el KMP sabemos q realizará como máximo n comparaciones (siendo n la longitud en caracteres de la secuencia) y en el caso de BM sabemos q el número de comparaciones será inferior a n en la mayoría de los casos, normalmente empleará m + n/m comparaciones (siendo m la longitud del patrón). Por lo q se deduce q el algoritmo BM es más eficiente q el KMP. Además aumenta su eficie n cia cuanto mayor es m.
Compare KMP y búsqda directa
Ambos son algoritmos q se emplean en la búsqda de patrones.En cuanto a la metodología sabemos q el algoritmo de Búsqda Directa compara el p atrón P con la secuencia S carácter a carácter hasta q encuentra la coincidencia, si existe. El algoritmo KMP también compara el patrón P con la secuencia S y lo hace también de izquierda a derecha, la diferencia reside en q el algoritmo KMP aprovecha el “conocimiento” adquirido en las anteriores comparaciones. En cuanto al número de comparaciones tenemos q el algoritmo de Búsqda Directa emplea por lo general un número proporcional a n·m, donde n es la longitud de la secuencia y m es la longitud del patrón, y en el mejor de los casos n = m. Por otra parte tenemos q el algoritmo KMP emplea como máximo n comparaciones, por lo q podemos decir q es más eficiente.
Expliq el algoritmo de Mezcla directa
Es un algoritmo de clasificación de datos en memoria secundaria (también conocido como combinación directa) y consiste en realizar sucesivas pasadas de mezcla tratando de obtener secuencias ordenadas cada vez más largas hasta q finalmente se
obtiene una única secuencia ordenada con la totalidad de los elementos.Inicialmente se supone q si existen n datos en la secuencia inicial no ordenada se pueden descomponer en n secuencias ordenadas de longitud uno. Después, se combinan
estas secuencias dos a dos, y se obtienen n/2 secuencias ordenadas de longitud 2.Repitiendo el proceso se llega finalmente a obtener una única secuencia ordenada de longitud n.