Resolución de problemas de optimización mediante técnicas divide y vencerás

[pic 2]

ESCUELA POLITECNICA NACIONAL

[pic 3]

FACULTAD DE INGENIERÍA DE SISTEMAS

ALGORITMOS (SIC324)

DEBER No: 7

Alumno:

Andrés Llumiquinga

Henry Guanoluisa

Marlon Pachacama

PROFESORA: Dra. María Pérez

FECHA DE ENTREGA: 12-08-2020

Deber de: 

Técnicas de Divide y Vencerás

Práctica No.: 07

Tema:

Resolución de problemas de optimización mediante técnicas divide y vencerás.

Objetivos:

• Aprender a utilizar la estrategia de DV para descomponer un problema en subproblemas más simples del mismo tipo.
• Estudiar y diseñar algoritmos (recursivos) Divide y Vencerás
• Estudiar el diseño y la implementación de los algoritmos de Ordenación

Marco teórico:

DV es una técnica de diseño de algoritmos que consiste en resolver un problema a partir de la solución de subproblemas del mismo tipo que el original y de tamaño más pequeño (formulación recursiva). En caso de que los subproblemas sigan siendo relativamente grandes se aplicará nuevamente dicha técnica hasta alcanzar subproblemas lo suficientemente pequeños para ser solucionados de manera directa e independiente.

La resolución de un problema mediante DV abarca los siguientes pasos:

1. Plantearse el problema de forma que pueda ser descompuesto en k subproblemas del mismo tipo que el original y de menor tamaño. Es decir, si el tamaño de la entrada es n, se ha de conseguir dividir el problema en k subproblemas (donde 1 ≤ k ≤ n), cada uno con una entrada de tamaño nk y donde 0 ≤ nk < n. Este paso, se conoce como división.
2. En segundo lugar, se resuelven independientemente todos los subproblemas directamente, si son elementales. En caso contrario, se resuelven forma recursiva. El hecho de que el tamaño de los subproblemas sea estrictamente menor que el problema original, garantiza la convergencia a los casos elementales o casos base.
3. El siguiente paso consiste en combinar las soluciones obtenidas en el paso 2 para construir la solución del problema original.

Características de los problemas que se pueden resolver mediante “divide y vencerás”

• El problema se puede descomponer en otros del mismo tipo que el original y de tamaño más pequeño (formulación recursiva).
• Los subproblemas pueden resolverse de manera independiente.
• Los subproblemas son disjuntos, sin solapamiento.
• La solución final se puede expresar como combinación de las soluciones de los subproblemas.

Algoritmo de Karatsuba

De la misma manera que la multiplicación entre enteros de longitud n puede descomponerse

(Karatsuba, 1962) siguiendo un criterio de partición binaria, la adición entre enteros, por ejemplo, u más v, es igualmente afrontable a través del mismo tipo de subdivisión:

[pic 4]

Figura 1. Ilustración de la descomposición de Karatsuba.

Con el apoyo de la bibliografía, se puede recordar cómo dicha operación dentro de un contexto

multiplicativo, u * v, se expresa matemáticamente usando el citado algoritmo como:

[pic 5]

Fórmula 1. Algoritmo de Karatsuba de multiplicación entre enteros.

Con la definición en Fórmula 1, y teniendo en cuenta que la adición entre enteros de longitud n

puede definirse como una composición de cálculos de sucesores (Booth, 1951), de manera que se denota la operación de cálculo del y-esimo sucesor de w como:

[pic 6]

Figura 2. Notación para operación de cálculos de sucesores.

Partiendo de la nomenclatura anterior, sin requerir de más desarrollo matemático, el resultado

directo de aplicar la expresión que figura en la Fórmula 1 al cómputo de operaciones en nuestro

contexto aditivo quedaría modelado con la fórmula:

[pic 7]

Fórmula 2. Algoritmo de Karatsuba de adición entre enteros.

Dicho esto, se entenderá la adición de un entero como la concatenación de elementos sucesores de los elementos involucrados en la operación teniendo en cuenta ciertas potencias por la base en la que se está trabajando, en este caso: base 10; las cuales suelen significar simples desplazamientos.

Entendidos estos últimos como una acción de trasladar dígitos, d, en determinada base, B, cambiando su peso significativo; tal que como refleja la Ilustración 3:

[pic 8]

Figura 3. Técnica de desplazamiento de dígitos en determinada Base.

Algoritmo de Strassen`s

Tradicionalmente, la multiplicación de matrices "a mano" se llevó siempre a cabo multiplicando y sumando los elementos de cada fila y cada columna, obteniendo el valor de aquel elemento que perteneciera a la fila y a la columna en cuestión. Así, el elemento en la posición (2, 3) de una matriz resultado, se obtenía multiplicando cada elemento de la fila 2 del multiplicando por cada elemento de la columna 3 del multiplicador, y sumándolos. Nunca hubo ningún problema con este algoritmo hasta la llegada de las ciencias de la computación, y la búsqueda por encontrar el algoritmo más rápido posible, es decir, un algoritmo de menor complejidad.

El algoritmo de multiplicación de matrices tradicional tenía una complejidad de Θ(). El surgimiento de diversas técnicas de programación llevó al intento de lograr un algoritmo de una complejidad menor aplicando esas técnicas, pues el manejo de matrices es una parte fundamental de la informática. Por ejemplo, el tratamiento de imágenes, computacionalmente hablando, es el tratamiento de matrices de enormes dimensiones.

Para el conjunto de los algoritmos que vamos a mencionar en este documento, partimos del hecho de que las matrices son cuadradas y de lado igual a una potencia de dos, a fin de que se puedan dividir correctamente.

...