Esta página propone varios ejercicios corregidos sobre algoritmos, más particularmente sobre el paradigma Divide & Conquer y la programación dinámica.
Ejercicio 1
Escribe un pseudocódigo para un divide y conquistaras algoritmo para encontrar la posición del elemento más grande en una matriz de números. Escriba un pseudocódigo para un algoritmo de fuerza bruta, compárelo con el anterior. Muestre un árbol del proceso del algoritmo divide y vencerás. ¿Cuál es el nivel máximo del árbol para números?
El algoritmo de fuerza bruta es trivial: un bucle.
En cada nivel l, el árbol binario completo se compone de 2 ^ (l-1) hojas. Entonces el total de vértices es 2 ^ l -1. Sea l el nivel del árbol, entonces l = sup (log_2 (n)).
Ejercicio 2
Escribe un pseudocódigo para un algoritmo de divide y vencerás para el problema de exponenciación de calcular a ^ n donde a> 0 y n es un número entero positivo. Escriba un pseudocódigo para un algoritmo de fuerza bruta, compárelo con el anterior. Muestre un árbol del proceso del algoritmo divide y vencerás. ¿Cuál es el nivel máximo del árbol para n no dado? Verifique la terminación, la corrección y la integridad.
Ejercicio 3
Se le da una matriz con números enteros (positivo, negativo, cero) y se supone que debe encontrar la suma contigua máxima en esta matriz. Por lo tanto, debe encontrar una submatriz que dé como resultado la suma más grande. Ejemplo, si la matriz dada es: 5, -6, 7, 12, -3, 0, -11, -6
Suponga que su matriz de entrada se llama A. Lo que debe hacer es formar otra matriz, digamos B, cuyo valor i se calcula utilizando la fórmula recursiva, max (A [i], B [i-1] + A [i ])
Lo que está haciendo de manera eficaz es elegir si desea ampliar la ventana anterior o iniciar una nueva. Puede hacer esto ya que se supone que solo debe seleccionar elementos continuos como parte de sus subconjuntos.
5, -6, 7, 12, -3, 0, -11, -6
La respuesta sería 19 (de la submatriz {7,12})
Ejercicio 4
Utilice la subcadena común más larga para: BDCABA y ABCBDAB
Ejercicio 5
Adapte la subcadena común más larga a la subsecuencia común más larga: BDCABA y ABCBDAB. El problema de la subsecuencia común más larga (LCS) es el problema de encontrar la subsecuencia más larga común a todas las secuencias en un conjunto de secuencias (a menudo, solo dos secuencias).
Se diferencia de los problemas de encontrar subcadenas comunes: a diferencia de las subcadenas, no se requiere que las subsecuencias ocupen posiciones consecutivas dentro de las secuencias originales.
Ejercicio 6
La distancia de Levenshtein es una métrica de cuerda para medir la diferencia entre dos secuencias. De manera informal, la distancia de Levenshtein entre dos palabras es el número mínimo de ediciones de un solo carácter (es decir, inserciones, eliminaciones o sustituciones) necesarias para cambiar una palabra por la otra. Ofrece un programa dinámico para solucionar este problema. Pruebe con MEILENSTEIN y LEVENSHTEIN.
ES 
FR 
EN