Capítulo 7. Divide y Conquista (Parte III)

Continuando con la serie de DyC, veremos en este capítulo un ejemplo de aplicación para resolver un algoritmo que calcule potencias de aⁿ cuando n es potencia de 2.

Antes de aventurarnos a escribir el pseudocódigo, analicemos un poco qué ocurre para a⁸

Podemos ver que los subproblemas 1 y 2 son idénticos, entonces carecería de sentido (en realidad se verá que se desperdiciarían recursos) hacer ambos. 

Lo más conveniente es tomar una sola mitad y luego multiplicar el resultado por sí mismo. Ahora sí podemos adentrarnos en el pseudocódigo para resolver el problema

Para el análisis de complejidad temporal observamos que el tamaño de la entrada disminuye a la mitad cada vez lo cual nos estamos en presencia del Caso 2 para métodos recursivos.

Los valores de a, b y k son 1, 2 y 0 respectivamente. Finalmente vemos que el orden del método para calcular potencias de 2 es O(log n).

Si no hubiésemos simplificado una de las ramas, tendríamos 2 llamadas recursivas en lugar de una sola:

R1 <- CALCULAR_POTENCIA(a, n1)

R2 <- CALCULAR_POTENCIA(a, n1)

De esta forma, a = 2, lo que finalmente se traduce en O(n), es decir, una complejidad temporal mayor a la calculada anteriormente.

Capítulo 6. Divide y Conquista (Parte II)

Como vimos en el Capítulo anterior, la técnica de Divide y Conquista se basa en subdividir un problema en problemas más pequeños similares e independientes entre sí, resolver estos problemas más pequeños y posteriormente juntar esas soluciones parciales (las soluciones de los subproblemas) en una única solución al problema mayor.

Hemos analizado el caso de la Búsqueda Binaria donde se pedía como pre condición que la cadena de números estuviera ordenada. En los próximos capítulos analizaremos métodos de ordenamiento eficientes que utilizan la técnica DyC: MergeSort y QuickSort.

En este capítulo, emplearemos Divide y Conquista para resolver el problema de determinar si una cadena de números está o no ordenada. Presentamos a continuación el pseudocódigo

Para realizar el análisis de complejidad temporal, considerar que el método "obtenerSecuencia" es constante.

El algoritmo puede ser encuadrado entonces en el Caso 2 de métodos recurrentes, con lo cual si a = 2, b = 2 y k = 0, obtenemos un costo para el método de O(n)

En el próximo capítulo veremos algunos ejemplos más de aplicación para DyC

Capítulo 5. Divide y Conquista (Parte I)

Características

La técnica de Divide y Conquista se basa en dividir un problema grande en problemas más pequeños, más simples de resolver, para luego combinar las soluciones y resolver el problema original.

Los subproblemas en los que se divide el problema original deben ser de igual naturaleza entre sí y de igual naturaleza al del problema original. También, estos subproblemas deben ser de menor tamaño que el problema original, de tamaños similares, e independientes entre sí.

Hay casos donde el problema original no se divide en varios subproblemas sino en un único subproblema. La división se realiza en forma recurrente hasta que el tamaño del subproblema sea lo suficientemente pequeño para ser resuelto en forma simple (lo que llamamos el caso base en capítulos anteriores).

Búsqueda Binaria

Veremos el ejemplo más simple y conocido que resuelve la técnica de Divide y Conquista. El problema consiste en indicar si un elemento dado 'x' se encuentra presente en una secuencia ordenada de números 'S' también dada.

La Búsqueda Binaria consiste en seleccionar el elemento que está en el medio de la secuencia S. Si este elemento coincide con el 'x' que se desea encontrar, entonces podemos afirmar que 'x' pertenece a la secuencia 'S'. Sino, ya que la secuencia está ordenada, realizaremos una comparación entre el elemento del medio que seleccionamos y el 'x'.

Tenemos dos posibilidades: el elemento del medio de la secuencia es mayor o menor al 'x' buscado (ya vimos que sucedía si era igual).

Ahora veremos cómo es que nuestro problema original se divide en un subproblema más pequeño. Si el elemento del medio de la secuencia 'S' es mayor al 'x' buscado, al estar la cadena 'S' ordenada, querrá decir que la única chance de encontrar a 'x' estará a la izquierda del elemento medio (la primera mitad de la secuencia 'S').

De esta forma, procederemos a aplicar la misma técnica (seleccionar el elemento medio) pero ahora nuestra nueva secuencia 'S' será la primera mitad de la cadena original.

Así, utilizando Divide y Conquista, hemos logrado reducir el problema original a un subproblema menor (tenemos sólo la mitad de la cadena) con las mismas características que el problema original.

De igual manera, si el elemento del medio de la cadena original 'S' hubiera sido menor al elemento buscado 'x', nos tendríamos que haber quedado con la segunda mitad de la cadena 'S'. Es importante enfatizar que esto es posible pura y exclusivamente si la cadena 'S' está ordenada de menor a mayor, sino no existe forma de saber con qué mitad quedarnos.

Presentamos entonces el pseudocódigo para el algoritmo de Búsqueda Binaria:

Fuentes:
Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.

Capítulo 4. Técnicas de Diseño de Algoritmos

El resto de los capítulos se centrará en el estudio de técnicas de diseño de algoritmos.

Estas técnicas no son más que estrategias para abordar problemas y resolverlos. No significa que sean una receta infalible, de hecho, no existe un algoritmo para escribir algoritmos. 

Nos limitaremos a analizar diferentes técnicas, con sus respectivas características y resolviendo ejemplos para ayudar a una mejor comprensión.

Las técnicas que veremos en los capítulos subsiguientes son:

• Divide y Conquista
• Greedy
• Programación Dinámica
• Backtracking

Capítulo 3. Ejemplos de Análisis de Complejidad Temporal en Métodos Recursivos

Veremos algunos ejemplos de aplicación para lo aprendido en el Capítulo anterior.

Comencemos por analizar la función factorial. Definiremos un algoritmo recurrente para la misma utilizando la notación de pseudocódigo.

Notemos que el caso base ocurre cuando la entrada 'n' es igual a 0 o a 1.

Luego se produce la llamada recursiva decrementando el tamaño de la entrada en una unidad. Esto nos indica que estamos en presencia del Caso 1.

Recordamos del Capítulo 2 que para este caso, el orden de la función venía dado por la relación entre 'a' (la cantidad de veces que se llama la función recursiva) y 1

Como se puede apreciar, aquí realizamos una única vez la llamada recursiva (pues la misma no se encuentra dentro de un bucle), siendo a = 1 entonces.

Nos resta determinar el valor de 'k', el grado del polinomio p(n)

A simple vista podemos ver que existe una única instrucción además de la llamada recursiva, y la misma tiene un valor constante (se devuelve un valor). Por lo tanto, el polinomio p(n) es una constante y finalmente k = 0.

Este análisis nos lleva a determinar el orden la función factorial recursiva en O(n)

A continuación analizaremos la complejidad temporal de ejemplos generales, sin entrar en detalles de qué propósito cumple el algoritmo.

Ejemplo 1

Se da como dato que el orden del método "calcularCondicion" es O(log n) y el orden del método "procesar" es O(n)

Este ejemplo se enmarca dentro del caso 2 ya que el tamaño de la entrada es dividido (en este ejemplo por 3). 

El análisis de complejidad temporal queda:

a = 1 ya que existe una única llamada recursiva. Que no nos confunda el hecho que veamos tengamos la llamada en dos bloques si distintos. Precisamente, por cada instancia de ejecución del método 1 se ejecutará, o bien las instrucciones dentro del bloque 'si', o bien las instrucciones dentro del bloque 'sino', pero nunca se ejecutarán ambas. Por ello a = 1.

Queda claro que b = 3, pues es la cantidad que divide a la entrada

Sólo resta determinar el valor de k. Por los datos proporcionados vemos que la función procesar tiene orden O(n) y la función  calcularCondicion O(log n). Siendo n mayor a log n consideraremos el peor de los casos, o sea, O(n). Esto hace que k = 1.

Resumiendo, debemos ver la relación entre a y b^k siendo a = 1, b = 3 y k = 1. 

Claramente a < b^k ya que 1 < 3. 

Finalmente tenemos que el orden del Método 1 es O(n^k) = O(n)

NOTA: si no existiera la función "procesar", la única función no afectada por la recursividad sería calcularCondicion con un orden O(log n). En dicho caso, debe hacerse el análisis para k = 0 y también k = 1, quedándonos con el que arroje el peor resultado.

Ejemplo 2

Se da como dato que el orden los métodos "calcularCondicion" y "procesar" es O(c), es decir, constantes.

A diferencia del método anterior, aquí podemos ver que existen 2 llamadas recursivas en un único bloque, por lo tanto a = 2.

La entrada se divide en dos, resultando b = 2 y como "calcularCondicion" y "procesar" son ambos métodos constantes, k = 0

Como la entrada es dividida estamos en presencia del caso 2

La relación es a > b^k  siendo el orden O(n^log_b^a), reemplazando los valores nos queda O(n)

Ejemplo 3

Se da como dato que el orden del método "calcularValor" es constante y el orden del método "procesar" es O(n*log n)

Este ejemplo se encuadra en el caso 1 ya que se sustraen elementos de la entrada. Tenemos dos llamadas recursivas, por ende, a = 2. La entrada disminuye en un elemento, por ello, b = 1.

Para el valor de k, el método procesar tiene un O(n*log n) pero notemos que está incluido dentro de un bloque mientras (comunmente llamado while). Entonces debemos multiplicar este orden por la cantidad de veces que se ejecute el bloque. En el peor de los casos, el bloque se ejecutará n veces (ya que ingresa mientras val < n). Por lo tanto el costo del bloque será n * n*log n.

Aquí debemos entonces analizar qué pasa en los casos que k = 2 y k = 3 y quedarnos con el peor.

Vemos que a = 2 es mayor a 1, por ello estamos en presencia de un costo del orden O (a^{n div b}), 

resultando en una complejidad exponencial O(2ⁿ)