INGENIERÍA DE SISTEMAS TÉCNICAS DE DISEÑO DE ALGORITMOS. PARTE I

Algoritmos y Estructura de Datos I

Página 1

UNIVERSIDAD CATÓLICA DE SANTA MARÍA ESCUELA PROFESIONAL DE INGENIERÍA DE SISTEMAS

SESIÓN 03:

TÉCNICAS DE DISEÑO DE ALGORITMOS. PARTE I I OBJETIVOS  Definir las técnicas de diseño de algoritmos.  Valorar los métodos de fuerza bruta, recursividad y divide y vencerás, programación dinámica y algoritmos voraces.

II TEMAS A TRATAR  Método de Fuerza Bruta  Recursividad  Divide y Vencerás

III MARCO TEORICO 1. Método de Fuerza Bruta La búsqueda por fuerza bruta, búsqueda combinatoria, búsqueda exhaustiva o simplemente fuerza bruta, es una técnica trivial pero muy a menudo usada, que consiste en enumerar sistemáticamente todos los posibles candidatos para la solución de un problema, con el fin de chequear si dicho candidato satisface la solución al mismo. Por ejemplo, un algoritmo de fuerza bruta para encontrar el divisor de un numero natural n consistiría en enumerar todos los enteros desde 1 hasta n, chequeando si cada uno de ellos divide n sin generar resto. Otro ejemplo de búsqueda por fuerza bruta, en este caso para solucionar el problema de las ocho reinas (posicionar ocho reinas en el tablero de ajedrez de forma que ninguna de ellas ataque al resto), consistiría en examinar todas las combinaciones de posición para las 8 reinas (en total 64! /56! = 178.462.987.637.760 posiciones diferentes), comprobando en cada una de ellas si las reinas se atacan mutuamente. La búsqueda por fuerza bruta es sencilla de implementar y, siempre que exista, encuentra una solución. Sin embargo, su coste de ejecución es proporcional al numero de soluciones candidatas, el cual es exponencialmente proporcional al tamaño del problema. Por el contrario, la búsqueda por fuerza bruta se usa habitualmente cuando el numero de Karim Guevara, Álvaro Fernández, Leticia Laura

Sesión 03

Algoritmos y Estructura de Datos I

Página 2

soluciones candidatas no es elevado, o bien cuando este puede reducirse previamente usando algún otro método heurístico. Es un método utilizado también cuando es más importante una implementación sencilla que una de mayor rapidez. Este puede ser el caso en aplicaciones críticas donde cualquier error en el algoritmo puede acarrear serias consecuencias, o también en aplicaciones destinadas a demostrar teoremas matemáticos. Este algoritmo es usado como método base para mediciones de rendimiento de otros algoritmos o metas heurísticas. La búsqueda por fuerza bruta no se debe confundir con backtracking, método que descarta un gran numero de conjuntos de soluciones, sin enumerar explícitamente cada una de las mismas.

Implementación de la búsqueda por fuerza bruta Algoritmo básico Para poder utilizar la búsqueda por fuerza bruta a un tipo especifico de problema, se deben implementar las funciones primero, siguiente, valido, y mostrar. Todas recogerán el parámetro indicando una instancia en particular del problema: 1. primero (P): genera la primera solución candidata para P. 2. siguiente (P, c): genera la siguiente solución candidata para P después de una solución candidata c. 3. valido (P, c): chequea si una solución candidata c es una solución correcta de P. 4. mostrar (P, c): informa que la solución c es una solución correcta de P. La función siguiente debe indicar de alguna forma cuando no existen mas soluciones candidatas para el problema P después de la última. Una forma de realizar esto consiste en devolver un valor "nulo". De esta misma forma, la función primero devolverá un valor "nulo" cuando no exista ninguna solución candidata al problema P. Usando tales funciones, la búsqueda por fuerza bruta se expresa mediante el siguiente algoritmo: c  primero(P) Mientras c != null Hacer Si valido(P,c) Entonces mostrar(P,c) c  siguiente(P,c) FinMientras

Por ejemplo, para buscar los divisores de un entero n, la instancia del problema P es el propio numero n. la llamada primero (n) devolverá 1 siempre y cuando n⩾1, y "nulo" en otro caso; la función siguiente (n,c) debe devolver c + 1 si c=1) instancias del mismo problema, pero de tamaño menor gracias a lo cual se puede aplicar inducción, llegando a un punto donde se conoce el resultado (el caso base). Nota: aunque los términos "recursión" y "recursividad" son ampliamente empleados en el campo de la informática, el término correcto en castellano es recurrencia. Sin embargo este último término es algo más específico.

Funciones definidas de forma recurrente Aquellas funciones cuyo dominio puede ser recursivamente definido pueden ser definidas de forma recurrente. El ejemplo más conocido es la definición recurrente de la función factorial n!:

Con esta definición veamos como funciona esta función para el valor del factorial de 3: 3! = 3 · (3-1)! = 3 · 2! = 3 · 2 · (2-1)! = 3 · 2 · 1! = 3 · 2 · 1 · (1-1)! = 3 · 2 · 1 · 0! =3·2·1·1 =6

La implementación del cálculo recursivo del factorial de un número sería el siguiente: public int factorial(int x) { if (x > -1 && x < 2) return 1; // Cuando -1 < x < 2 devolvemos 1 // puesto que 0! = 1 y 1! = 1 else if (x < 0) return 0; // Error no existe factorial de // números negativos return x * factorial(x - 1); // Si x >= 2 devolvemos el producto // de x por el factorial de x - 1 }

El seguimiento de la recursividad programada es casi exactamente igual al ejemplo antes dado, para intentar ayudar a que se entienda mejor se ha acompañado con muchas explicaciones los distintos sub-procesos de la recursividad. X = 3 //Queremos 3!, por lo tanto X inicial es 3 X >= 2 -> return 3*factorial(2); X = 2 //Ahora estamos solicitando el factorial de 2 X >= 2 -> return 2*factorial(1); X = 1 // Ahora estamos solicitando el factorial de 1 X < 2 -> return 1; [En este punto tenemos el factorial de 1 por lo que volvemos marcha atrás resolviendo todos los resultados]

Karim Guevara, Álvaro Fernández, Leticia Laura

Sesión 03

Algoritmos y Estructura de Datos I

Página 5

return 2 [es decir: return 2*1 = return 2*factorial(1)] return 6 [es decir: return 3*2 = return 3*factorial(2)*factorial(1)] // El resultado devuelto es 6

3. Divide y Vencerás En la cultura popular, divide y vencerás hace referencia a un refrán que implica resolver un problema difícil, dividiéndolo en partes mas simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia. La solución del problema principal se construye con las soluciones encontradas. En las ciencias de la computación, el termino divide y vencerás (DYV) hace referencia a uno de los mas importantes paradigmas de diseño algorítmico. El método esta basado en la resolución recursiva de un problema dividiéndolo en dos o más subproblemas de igual tipo o similar. El proceso continúa hasta que estos llegan a ser lo suficientemente sencillos como para que se resuelvan directamente. Al final, las soluciones a cada uno de los subproblemas se combinan para dar una solución al problema original. Esta técnica es la base de los algoritmos eficientes para casi cualquier tipo de problema como, por ejemplo, algoritmos de ordenamiento (quicksort, mergesort, entre muchos otros),multiplicar números grandes (Karatsuba), análisis sintácticos (análisis sintáctico top-down) y la transformada discreta de Fourier. Por otra parte, analizar y diseñar algoritmos de DyV son tareas que llevan tiempo dominar. Al igual que en la inducción, a veces es necesario sustituir el problema original por uno mas complejo para conseguir realizar la recursión, y no hay un método sistemático de generalización. El nombre divide y vencerás también se aplica a veces a algoritmos que reducen cada problema a un único subproblema, como la búsqueda binaria para encontrar un elemento en una lista ordenada. Estos algoritmos pueden ser implementados mas eficientemente que los algoritmos generales de “divide y vencerás”; en particular, si es usando una serie de recursiones que lo convierten en simples bucles. La corrección de un algoritmo de “divide y vencerás”, esta habitualmente probada por medio de una inducción matemática, y su coste computacional se determina resolviendo relaciones de recurrencia.

Diseño e implementación La resolución de un problema mediante esta técnica consta fundamentalmente de los siguientes pasos: 1. En primer lugar ha de plantearse el problema de forma que pueda ser descompuesto en k subproblemas del mismo tipo, pero de menor tamaño. Es decir, si el tamaño de la entrada es n, hemos 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. A esta tarea se le conoce como división. 2. En segundo lugar han de resolverse independientemente todos los subproblemas, bien directamente si son elementales o bien de forma recursiva. El hecho de que el tamaño de los subproblemas sea estrictamente menor que el tamaño original

Karim Guevara, Álvaro Fernández, Leticia Laura

Sesión 03

Algoritmos y Estructura de Datos I

Página 6

del problema nos garantiza la convergencia hacia los casos elementales, también denominados casos base. 3. Por ultimo, combinar las soluciones obtenidas en el paso anterior para construir la solución del problema original. Los algoritmos divide y vencerás (o divide and conquer, en ingles), se diseñan como procedimientos generalmente recursivos. Funcion dv  AlgoritmoDyV (p: TipoProblema) Si esCasoBase(p) Entonces retornar resuelve(p) Sino TipoProblema : subproblemas[] subproblemas = divideEnSubproblemas(p) TipoSolucion : soluciones_parciales[] Para sp itera subproblemas soluciones_parciales.push_back(AlgoritmoDYV(sp)) Fin_Para retornar mezcla(soluciones_parciales) Fin_Si FinFuncion

Por el hecho de usar un diseño recursivo, los algoritmos diseñados mediante la técnica de Divide y Vencerás van a heredar las ventajas e inconvenientes que la recursión plantea:  Por un lado el diseño que se obtiene suele ser simple, claro, robusto y elegante, lo que da lugar a una mayor legibilidad y facilidad de depuración y mantenimiento del código obtenido.  Por contra, los diseños recursivos conllevan normalmente un mayor tiempo de ejecución que los iterativos, además de la complejidad espacial que puede representar el uso de la pila de recursión. Sin embargo, este tipo de algoritmos también se pueden implementar como un algoritmo no recursivo que almacene las soluciones parciales en una estructura de datos explicita, como puede ser una pila, cola, o cola de prioridad. Esta aproximación da mayor libertad al diseñador, de forma que se pueda escoger que subproblema es el que se va a resolver a continuación, lo que puede ser importante en el caso de usar técnicas como Ramificación y acotación o de optimización.

Eligiendo los casos base En cualquier algoritmo recursivo, hay una libertad considerable para elegir los casos bases, los subproblemas pequeños que son resueltos directamente para acabar con la recursión. Elegir los casos base más pequeños y simples posibles es más elegante y normalmente nos da lugar a programas más simples, porque hay menos casos a considerar y son más fáciles de resolver. Por ejemplo, un algoritmo quicksort de ordenación podría parar cuando la entrada es una lista vacía. En ambos casos, solo hay que considerar un caso base a considerar, y no requiere procesamiento. Por otra parte, la eficiencia normalmente mejora si la recursión se para en casos relativamente grandes, y estos son resueltos no recursivamente. Esta estrategia evita la sobrecarga de llamadas recursivas que hacen poco o ningún trabajo, y pueden también permitir el uso de algoritmos especializados no recursivos que, para esos casos base, son Karim Guevara, Álvaro Fernández, Leticia Laura

Sesión 03

Algoritmos y Estructura de Datos I

Página 7

mas eficientes que la recursión explicita. Ya que un algoritmo de DyV reduce cada instancia del problema o subproblema aun gran numero de instancias base, estas habitualmente dominan el coste general del algoritmo, especialmente cuando la sobrecarga de separación/unión es baja.

Compartir subproblemas repetidos Para algunos problemas, la recursión ramificada podría acabar evaluando el mismo subproblema muchas veces. En tales casos valdría la pena identificar y guardar las soluciones de estos subproblemas solapados, una técnica comúnmente conocida como memorización. Llevado al límite, nos lleva a algoritmos de “divide y vencerás” de bottom-up tales como la programación dinámica y análisis gráfico.

Ventajas Resolución de problemas complejos Este modelo algorítmico es una herramienta potente para solucionar problemas complejos, tales como el clásico juego de las torres de Hanoi. Todo lo que necesita este algoritmo es dividir el problema en subproblemas más sencillos, y estos en otros mas sencillos hasta llegar a unos subproblemas sencillos (también llamados casos base). Una vez ahí, se resuelven y se combinan los subproblemas en orden inverso a su inicio. Como dividir los problemas es, a menudo, la parte más compleja del algoritmo. Por eso, en muchos problemas, el modelo solo ofrece la solución más sencilla, no la mejor.

Eficiencia del algoritmo Normalmente, esta técnica proporciona una forma natural de diseñar algoritmos eficientes. Por ejemplo, si el trabajo de dividir el problema y de combinar las soluciones parciales es proporcional al tamaño del problema (n); además, hay un numero limitado p de subproblemas de tamaño aproximadamente igual a n/p en cada etapa; y por ultimo, los casos base requieren un tiempo constante (O(1)); entonces el algoritmo divide y vencerás tiene por cota superior asintótica a O(nlogn). Esta cota es la que tienen los algoritmos divide y vencerás que solucionan problemas tales como ordenar y la transformada discreta de fourier. Ambos procedimientos reducen su complejidad, anteriormente definida por O(n2). Para terminar, cabe destacar que existen otros enfoques y métodos que mejoran estas cotas.

Paralelismo Este tipo de algoritmos se adapta de forma natural a la ejecución en entornos multiprocesador, especialmente en sistemas de memoria compartida donde la comunicación de datos entre los procesadores no necesita ser planeada por adelantado, por lo que subproblemas distintos se pueden ejecutar en procesadores distintos.

Acceso a memoria Los algoritmos que siguen el paradigma Divide y vencerás, tienden naturalmente a hacer un uso eficiente de las memorias caches. La razón es que una vez que un subproblema es lo suficientemente pequeño, el y todos sus subproblemas se pueden, en principio, solucionar dentro de esa cache, sin tener acceso a la memoria principal, que es del orden de decenas de veces mas lenta. Un algoritmo diseñado para aprovechar la memoria cache de esta manera se Karim Guevara, Álvaro Fernández, Leticia Laura

Sesión 03

Algoritmos y Estructura de Datos I

Página 8

llama modelo caché-olvidadiza, olvidadiza porque no contiene el tamaño de la memoria como parámetro explícito. Por otra parte, estos algoritmos se pueden diseñar para muchos problemas importantes, tales como ordenación, la multiplicación de matrices, de manera que se haga un uso óptimo de la cache. En contraste, el acercamiento tradicional para explotar la cache es hacer bloques, de esta forma, el problema se divide explícitamente en las partes de tamaños apropiados para que se pueda utilizar al cache de forma óptima, pero solamente cuando el algoritmo es mejorado para el tamaño específico de la cache de una maquina particular. La misma ventaja existe en lo que respecta a otros sistemas jerárquicos de memoria, por ejemplo NUMA o memoria virtual, así como para niveles múltiples de cache: una vez que un subproblema es suficientemente pequeño, puede ser solucionado dentro de un nivel dado de la jerarquía, sin tener que acceder al más alto (más lento). Sin embargo, la clase de optimalidad asintótica descrita aquí, análoga a notación O mayúscula, no hace caso de factores constantes, y el añadir mejoras adicionales específicas de la máquina y cache no es un requerimiento para alcanzar el óptimo en un sentido absoluto.

Control del redondeo En computaciones con aritmética redondeada, por ejemplo con los números en aritmética flotante, un algoritmo de divide y vencerás podría dar resultados más exactos que un problema iterativo equivalente superficialmente. Por ejemplo, se pueden sumar N números tanto como con un bucle simple que suma cada dato a una variable simple, o mediante un algoritmo de DyV que rompe el conjunto de datos en dos mitades, recursivamente computa cada suma y luego une las 2 sumas. Mientras que el segundo método realiza las mismas sumas que el primero, y cuesta más por las llamadas recursivas, normalmente es más exactoDesventajas

La principal desventaja de este método es su lentitud en la repetición del proceso recursivo: los gastos indirectos de las llamadas recursivas a la resolución de los subproblemas, junto con el hecho de tener que almacenar la pila de llamadas (el estado en cada punto en la repetición), pueden empeorar cualquier mejora hasta entonces lograda. Esta tarea, sin embargo, depende del estilo de la implementación: con casos base lo suficientemente grandes, se reducen los gastos indirectos de la repetición de las llamadas. Otra desventaja o inconveniente importante, es la dificultad o incluso inconveniencia de aplicar el método a situaciones en las que la solución al problema general no se deriva de la suma directa y simple de los subproblemas (partes). Esto se presenta por ejemplo cuando son relevantes las interacciones o efectos mutuos entre los subproblemas, lo que genera nuevos subproblemas, al considerar cada una de estas interacciones, incrementando exponencialmente el número de subproblemas a considerar, al incrementarse la complejidad de la situación general y de sus componentes. De modo similar, el algoritmo puede no ser aplicable cuando las interacciones no son predecibles de preciso.

IV ACTIVIDADES 1. Leer atentamente la teoría de los algoritmos y buscar implementaciones de los mismos en internet.

Karim Guevara, Álvaro Fernández, Leticia Laura

Sesión 03

Algoritmos y Estructura de Datos I 2.

Página 9

Ahora implementarlos en cualquier lenguaje de programación.

V EJERCICIOS 1. Recurrencia: Implementar en C++, los siguientes algoritmos recursivos: a) b) c) d) e) f)

Factorial n! = n × (n-1)! Sucesión de Fibonacci f(n) = f(n-1) + f(n-2) Números de Catalan C(2n, n)/(n+1) Las Torres de Hanoi Función de Ackermann Máximo Común Divisor de dos números.

2. Algoritmo Divide y Vencerás: Implementarla solución de los siguientes problemas: a) Multiplicación de Enteros Grandes: algoritmo eficiente para multiplicar números de tamaño considerable, que se salen de los límites de representación, y no abordable con los algoritmos clásicos debido al excesivo coste. b) Subvector de suma máxima: Algoritmo eficiente para encontrar subcadenas dentro de un vector evitando tener que recorrer todo el vector desde cada posición.

VI BIBLIOGRAFIA Y REFERENCIAS  Wikipedia (para las implementaciones) BIBLIOGRAFÍA BÁSICA  D.S.Malik, “DATA STRUCTURES USIGN C++”, Thomson Learning, 2003  J. Galve. “ALGORITMIA”, Ed.Adisson Wesley, España, 2000.  Brassard, “ANÁLISIS DE ALGORITMOS”, Ed. Mc. Graw Hill., España, 1999., BIBLIOGRAFÍA COMPLEMENTARIA  Wirth M., “ALGORITMOS Y ESTRUCTURA DE DATOS”, Ed. Addison Wesley, México, 1997  Aho. “DISEÑO Y ANÁLISIS DE ALGORITMOS”, Ed. Addison Wesley. USA, 1999.  Deitel & Deitel “COMO PROGRAMAR EN C/C++”. Editorial Prentice Hall, 1995.

Karim Guevara, Álvaro Fernández, Leticia Laura

Sesión 03