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ⁿ)

Capítulo 2. Complejidad Temporal de Métodos Recursivos

Algoritmos Recursivos

Un algoritmo recursivo es aquel que expresa la solución a un problema en términos de una llamada a sí mismo. Esta llamada a si mismo se denomina llamada recursiva o recurrente. Para evitar un ciclo sin fin es muy importante definir lo que se conoce como el caso base o condición de corte.

A lo largo del curso se utiliza la notación de pseudocódigo de forma tal que cada uno pueda utilizar el lenguaje de programación que le resulte más familiar para implementar el algoritmo.

A continuación presentamos un ejemplo general de un método recurrente.

Este algoritmo genérico sirve para ilustrar a que nos referimos cuando decimos caso base.

Llamamos 'proceso' a una función que se encargue de realizar algo con la entrada, ya sea sumarle una constante o ejecutar cualquier cosa que sea de interés para nuestro problema.

En el caso que la entrada al método A no cumpla la condición de base, se efectúa la llamada recurrente, restando una constante 'c' a la entrada.

Es lógico que se reduzca la entrada en alguna forma, sino no podríamos llegar nunca al caso base y de esa manera finalizar la ejecución del algoritmo.

Consideraremos dos formas de reducir la entrada: restando o dividiendo. Con cualquiera de ellas estamos logrando el objetivo. Sin embargo, veremos que el análisis de complejidad temporal varía dependiendo del caso.

Antes de profundizar en cada caso, notar las siguientes definiciones para comprender la notación:

Caso 1: Sustracción sobre la entrada

Este es el caso visto en el ejemplo del método A. La función que representa el costo para estos casos es

Para este caso de sustracción, lo que determina el costo del algoritmo será el valor de 'a' respecto de 1 como se ve a continuación:

Caso 2: División de la entrada

En este caso, en lugar de restar algún elemento de la entrada, lo que hacemos es dividir la misma generando así entradas más pequeñas para la llamada recursiva. La función que representa el costo para este caso es

El costo del algoritmo en estos casos estará determinado por la relación existente entre los parámetros a, b y k (grado del polinomio f(n))

En el próximo capítulo utilizaremos estas funciones para analizar la complejidad temporal de algunos ejemplos de métodos recurrentes.

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

Capítulo 1. Algoritmos y Complejidad Temporal

¿Qué es un algoritmo?

Básicamente, un algoritmo es un conjunto finito de instrucciones ordenadas. Transforman datos de entrada en datos de salida resolviendo algún problema en particular.

Con salida correcta queremos decir que, ante una determinada entrada válida, se genere un resultado esperado.

Es independiente del lenguaje de programación. Cuando lo trasladamos a un lenguaje en particular, estamos generando un programa.

Vamos a considerar dos tipos distintos de complejidad para el análisis de algoritmos:

• Temporal: Medida de eficiencia o de tiempo.
• Espacial: Cuánto me ocupa la resolución del algoritmo.

No nos ocuparemos en el curso de la complejidad espacial, pero es importante tenerla en cuenta cuando se dispone de recursos limitados.

Complejidad Temporal

Podemos organizar la Complejidad Temporal en dos categorías:

• Teórica: Podemos hacer un análisis previo a la ejecución.
• Real: Tenemos dependencia del hardware, recursos, etc.

Centraremos nuestra atención sobre la Complejidad Temporal Teórica. De aquí en adelante nos referiremos a ella simplemente como complejidad temporal.

Para realizar el análisis del costo de un algoritmo debemos tener en cuenta:

• La cantidad de datos de entrada (tamaño de la entrada).
• Análisis de las operaciones elementales (suma, asignación, comparación, etc).
• Análisis de casos (mejor, promedio, peor).

En general, el costo de un algoritmo dependerá del tamaño de la entrada y por ello resulta conveniente definirlo como una función de n donde n representará el tamaño de la entrada.

Utilizaremos O(n) para expresar la función del costo de un algoritmo:

Dependiendo del tamaño de la entrada tendremos los siguientes costos (ordenados de menor a mayor costo):

• O(c) - Constante. Es independiente de los datos de entrada. En general las operaciones elementales tienen un costo constante (suma, asignación, comparación).
• O(log n) - Logarítmica. 
• O(n) - Lineal. La cantidad de operaciones crece linealmente con la cantidad de elementos de entrada.
• O(n*log n)
• O(n²) ... O(n^x) - Polinomiales.

También están aquellas que no son aplicables para un algoritmo:

• O(xⁿ)
• O(n!)

En el próximo capítulo aplicaremos estos conceptos a métodos recursivos.

Fuentes: 

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