Capítulo 21. Algoritmos Greedy: Ejemplo de la mochila (Parte III)

Realizamos una ligera modificación al pseudocódigo del algoritmo de la mochila para poder almacenar los elementos que forman parte de la solución y devolverlos como resultado

Pseudocódigo

Análisis de Complejidad Temporal

El análisis es idéntico al realizado para el algoritmo del capítulo previo. La complejidad queda en el orden O(n*log(n)) si utilizamos MergeSort para ordenar la cadena por la razón Beneficio/Peso.

Capítulo 20. Algoritmos Greedy: Ejemplo de la mochila (Parte II)

Presentamos el pseudocódigo del ejemplo que resolvimos manualmente en el capítulo anterior.

Pseudocódigo

Análisis de Complejidad Temporal

Cabe señalar una importante diferencia respecto del análisis temporal para el ejemplo del cambio. Fijemos nuestra atención en el bloque 'mientras' y las condiciones:

i <= longitud(S) y capacidadParcial < P

En el peor de los casos, el bloque se ejecutará 'n' veces, siendo 'n' la cantidad de elementos en la secuencia S. Es decir, tiene mayor peso la condición i <= longitud(S) que la condición capacidadParcial < P.

Esto es así debido a que los objetos son finitos y no pueden repetirse en el armado de la solución final. Distinto era el caso en el ejemplo del cambio donde teníamos instancias infinitas de cada moneda y el objetivo era cubrir un importe P.

 

Las sentencias contenidas en el bloque 'mientras' tienen una complejidad constante dando un costo de O(n) para todo el bloque por lo explicado anteriormente.

Se observa entonces que la complejidad temporal del algoritmo dependerá del método de ordenamiento elegido para "ordenarPorBeneficioPeso". Si utilizamos MergeSort la complejidad temporal de MOCHILA_GREEDY nos queda en O(n*log(n)).

No debe sorprendernos que la complejidad en algoritmos Greedy venga dada por el método de ordenamiento utilizado ya que es la forma más eficiente que encontramos para implementar la estrategia de selección.

En el próximo capítulo haremos una ligera modificación al pseudocódigo de forma que nos permita guardar los elementos que serán almacenados en la mochila.

Fuentes:

Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda

Capítulo 19. Algoritmos Greedy: Ejemplo de la mochila (Parte I)

Continuando con los Algoritmos Greedy, centraremos nuestra atención en el ejemplo de la mochila. La descripción del problema es la siguiente:

Se tienen n objetos y una mochila con capacidad P. Cada uno de los n objetos tiene dos propiedades: peso y beneficio. Para i = 1, 2, ..., n, el objeto i tiene un peso p_i y un beneficio b_i. Tanto el peso como el beneficio son siempre positivos.

Además, los objetos pueden ser fraccionados, esto quiere decir que puedo llevar 1/2, 1/3 o cualquier otra fracción de un objeto.

Matemáticamente si una fracción x_i (0<x_i<1) del objeto i es colocada en la mochila, esta fracción contribuye en un peso x_i*p_i y en un beneficio x_i*b_i.

Para dejar en claro esto último, si tengo un objeto i cuyo peso es 12 y beneficio es 9, si decido llevar 1/3 del objeto, la contribución de este objeto al problema sería:

Peso = x_i*p_i = 1/3*12 = 4. 
Benefición = x_i*b_i = 1/3*9 = 3. 

Aclarado todo esto, el objetivo del problema es llenar la mochila de forma tal que se maximice el beneficio de los objetos transportados sin exceder la capacidad P (peso total) de la mochila.

Vamos a resolver un ejemplo de este problema en forma manual y en el siguiente capítulo lo haremos a través del pseudocódigo. Supongamos entonces que tenemos la siguiente instancia del problema:

La capacidad P de la mochila es 12 y poseemos el conjunto de elementos:

Elementos = { (p = 5; b = 4) , (p = 7; b = 5), (p = 2; b = 3), (p = 6; b = 3), (p = 4; b = 5) }

Con el fin de abreviar la nomenclatura representaremos a cada elemento e_i con el par (p_i, b_i). De esta forma, el conjunto anterior es simplemente:

Elementos = { (5,4), (7,5), (2,3), (6,3), (4,5) }

Recordemos que en los algoritmos Greedy podía identificarse una función selección, muchas veces asociada a la forma de ordenar el conjunto de elementos candidatos. En forma intuitiva, ya que el objetivo es maximizar el beneficio y los objetos pueden fraccionarse, convendría ordenar los elementos por su relación beneficio/peso en forma decreciente. Así, el conjunto de elementos ordenado por b/p nos queda:

Elementos = { (2,3), (4,5), (5,4), (7/5), (6, 3) }

Ahora, deberíamos ir tomando cada uno de estos elementos y verificar que no nos excedamos de la capacidad P de la mochila. Llamaremos W al peso parcial y B al beneficio parcial tras la elección de cada elemento (actúan como contadores).

Empecemos entonces tomando el primer elemento del conjunto ordenado, el (2,3). Nuestros contadores quedan:

W = 2
B = 3

Ya que no nos excedimos de la capacidad P, procedemos a elegir el siguiente elemento (4, 5):

W = 2 + 4 = 6
B = 3 + 5 = 8

Siendo que 6 es menor a P = 12 elegimos un tercer elemento, el (5,4):

W = 6 + 5 = 11
B = 8 + 4 = 12

El peso parcial acumulado aún no excede la capacidad de nuestra mochila, es por ello que podemos elegir un nuevo elemento: el (7,5).

W = 11 + 7 = 18 
B = 12 + 5 = 17

¿Qué ha pasado? Hemos superado la capacidad total P de la mochila. Siendo que el peso acumulado W del paso anterior era igual a 11, sólo necesitábamos contribuir en 1 para alcanzar la capacidad total. Aquí es cuando debemos fraccionar el elemento.

Es fácil ver que con la fracción 1/7 cumpliremos nuestro cometido y los acumuladores quedarán:

W = 11 + 1/7*7 = 12
B = 12 + 1/7*5 = 89/7

Todo esto realizado en forma intuitiva deriva en la solución óptima. Vale aclarar que debería demostrarse matemáticamente, cosa que excede el alcance de nuestro curso.

Esto mismo que hemos hecho manualmente, se verá plasmado en pseudocódigo en el siguiente capítulo.

Capítulo 18. Algoritmos Greedy: Ejemplo del cambio

En este y capítulos posteriores iremos analizando distintos ejemplos de aplicación de la técnica de algoritmos Greedy. Comenzaremos con estudiar el más sencillo de todos: el problema del cambio.

Se desea encontrar la forma de devolver un vuelto de valor 'v' con monedas de denominaciones d₁, d₂, ..., d_n considerando que existe una cantidad infinita de monedas de cada denominación.

Por ejemplo, queremos devolver $1.83 y disponemos de monedas de 1, 5, 10, 25, 50 centavos y 1 peso. La forma más sencilla e intuitiva de hacerlo es con una moneda de 1 peso, una moneda de 50 centavos, una moneda de 25 centavos, una moneda de 5 centavos y tres monedas de 1 centavo.

Esto que hacemos en forma intuitiva (devolver la cantidad pedida con la menor cantidad posible de monedas) puede expresarse en el siguiente algoritmo:

Cómo se estudió en el capítulo 16, debería ser posible identificar las 4 funciones que caracterizan a los algoritmos Greedy.

Así, el conjunto de candidatos es el conjunto de monedas disponibles y se dispone de infinitas monedas de cada denominación. El conjunto de candidatos pendientes viene dado por las posiciones mayores o iguales a i en la cadena 'monedas'.

La función selección es la que elige el elemento de la posición i sumado a que las monedas están ordenadas de mayor a menor (se indicó como 100 la moneda de 1 peso para diferenciarla de la moneda de 1 centavo).

La función de factibilidad es la que pregunta si s + monedas[i] < v (es decir, está preguntando si al sumarle el candidato elegido en ese momento al vuelto parcial 's', no nos estamos pasando del valor v a devolver).

La función solución es la que evalúa s < v y la función objetivo, implícita, es la que minimiza la cantidad de monedas.

Debemos tener en cuenta que este algoritmo es correcto para las denominaciones de monedas utilizadas. Para otras instancias del problema el algoritmo deja de ser óptimo y es necesario emplear otra técnica distinta que estudiaremos más avanzado el curso.

Para ilustrar este hecho supongamos que nuestra cadena de monedas es = [6, 4, 1] y se nos pide devolver un cambio de 8.

El algoritmo presentado en este capítulo nos daría el vuelto con una moneda de 6 y dos monedas de 1 (totalizando 3 monedas) cuando intuitivamente podemos apreciar que la manera más óptima sería devolver dos monedas de 4.

Fuentes:

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

Capítulo 17. Algoritmos Greedy (Parte II)

Presentaremos en este capítulo la forma general en formato pseudocódigo de los algoritmos Greedy.

GREEDY
Entrada: C -> conjunto de candidatos.
Salida:  S -> solución del problema.

     mientras C <> vacío y no esSolucion(S)
          x <- Seleccionar(C)
          C <- C\{x}          
          si esFactible(S U {x})
              S <- S U {x} 
          fin si
     fin mientras
     si esSolucion(S) 
         devolver S
     fin si
     sino 
         devolver No hay solución
     fin si
fin GREEDY

Al tratarse de operaciones entre conjuntos vale aclarar la notación:

• C\{x} quiere decir que al conjunto de candidatos C se le quita el elemento x (ya que 'x' había sido seleccionado en el paso anterior).
• S U {x} significa que al conjunto de solución se le agrega el elemento x.

En los siguientes capítulos nos dedicaremos a estudiar ejemplos de aplicación de esta técnica de diseño de algoritmos.

Capítulo 16. Algoritmos Greedy (Parte I)

Características de los Algoritmos Greedy

 

La técnica de diseño de algoritmos denominada Greedy (algoritmos voraces) es aquella que va construyendo la solución de un problema a partir de decisiones parciales tomadas en base a la información disponible en cada momento.

 

No mira hacia adelante, es decir, no ve los efectos de las decisiones tomadas a futuro y nunca reconsidera una decisión ya tomada.

 

Esta técnica es utilizada en general para resolver problemas de optimización. Suelen ser muy eficientes pero su eficacia debe ser validada, o sea, debe tenerse mucho cuidado con su correctitud. Esto quiere decir que se debe demostrar que la solución encontrada es óptima.

 

Se basa en un conjunto de candidatos a formar parte de la solución. En cada paso se toma uno de los candidatos, el más apropiado y se evalúa si sirve o no. Si sirve, el candidato es agregado a la solución, caso contrario es descartado. Para ello, es necesario saber en todo momento, dado un candidato, si el mismo está pendiente de ser evaluado, si ya fue evaluado y agregado a la solución o si fue descartado.

 

Para cumplir con esto deben conocerse cuatro funciones:

• La función selección que es la que selecciona el mejor candidato dentro de los pendientes.
• La función factibilidad que evalúa si un candidato seleccionado es factible de formar parte de la solución.
• La función solución que evalúa si un conjunto solución propuesto conforma la solución al problema.
• La función objetivo que es la que se debe maximizar o minimizar (optimizar).

 

En el próximo capítulo presentaremos el pseudocódigo de la forma general de los algoritmos Greedy. Tener en cuenta que, aunque las cuatro funciones mencionadas deben estar presentes en el diseño, no siempre es trivial la identificación de las mismas dentro del algoritmo.

Fuentes:

 

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

Capítulo 15. MergeSort dividiendo cadena en tres partes

Cuando aplicamos MergeSort en capítulos previos, siempre fuimos dividiendo la cadena de entrada en dos partes. ¿Qué pasaría si dividiéramos la cadena en tres o más partes? ¿Mejoraría la complejidad temporal? En este capítulo intentaremos dar respuesta a estas cuestiones.

Enunciado

Dada una cadena S de números enteros, ordenarla en forma creciente. Utilizar el método de ordenamiento Merge-Sort, pero dividiendo la cadena en 3 subcadenas y analizar el costo.

Pseudocódigo

Análisis de Complejidad Temporal

Considerando que el método UnirCadenasOrdenadas tiene un costo lineal O(n), podemos ver que la cantidad de llamadas recursivas es 3 al igual que la cantidad en que se divide la cadena. El resto de asignaciones y comparaciones tienen un costo constante.

Por lo tanto, tenemos que a = 3, b = 3 y k = 1

Siendo a = b^k ya que 3 = 3¹ el orden del algoritmo es O(n^k*log(n)) lo que finalmente se traduce en un costo de O(n*log(n))

 

Así acabamos de mostrar que el hecho de dividir la cadena en una mayor cantidad de partes no mejora la complejidad temporal de MergeSort. Podemos proceder análogamente en el caso que deseemos dividir la cadena de entrada en 4 o más partes y veremos que el resultado no se ve alterado.

Capítulo 14. Métodos de Ordenamiento: QuickSort (Parte II)

En el capítulo previo estudiamos el funcionamiento del método de ordenamiento QuickSort. Aquí presentaremos el pseudocódigo del algoritmo así como también realizaremos el análisis de complejidad temporal del mismo.

Pseudocódigo

QUICKSORT
Entrada: S -> secuencia de enteros.
Salida:  S -> la misma secuencia ordenada.

     si longitud(S) > 1
          p <- pivot(S)
          S1 <- crearVector(p - 1)
          S2 <- crearVector(longitud(S) - p)
          S1 <- S[1... p - 1]
          S2 <- S[p + 1... longitud(S)]
          S1 <- QuickSort(S1)
          S2 <- QuickSort(S2)
          S  <- S1 + S[p] + S2
     fin si
     devolver S
fin QUICKSORT

El pseudocódigo para el método pivot es el siguiente

PIVOT
Entrada: S -> secuencia de enteros.
Salida:  p -> posición del elemento utilizado para pivotear.

     p <- S[1]
     k <- 2
     t <- longitud(S)
     mientras S[k] <= p y k < longitud(S)
          k <- k + 1
     fin mientras
     mientras S[t] > p
          t <- t - 1
     fin mientras
     mientras k < t
          aux <- S[k]
          S[k] <- S[t]
          S[t] <- aux
          mientras S[k] <= p
               k <- k + 1
          fin mientras
          mientras S[t] > p
               t <- t - 1
          fin mientras
     fin mientras
     aux <- S[1]
     S[1] <- S[t]
     S[t] <- aux
     devolver t
fin PIVOT

Análisis de Complejidad Temporal

Analizando el método pivot en primera instancia podemos ver que su costo es de O(n) ya que los "mientras" anidados tienen como restricción el "mientras" principal. A su vez, el método QuickSort posee dos llamadas recursivas.

Dependiendo la ubicación del pivot (ya habíamos visto que cuanto más cerca del elemento mediano mayor eficiencia tendría el método), si el mismo cae cerca del centro de la cadena, el análisis de costos es el siguiente:

 

 

Se tiene que a = 2, b = 2 y k = 1 lo que finalmente da lugar a un costo O(n*log(n)) al igual que el método MergeSort.

Por el contrario, si el pivot cae cerca de alguno de los extremos (el peor caso), tenemos

 

 

 

Aquí a = 1, b = 1 y k = 1 (estamos en el Caso 1 de los métodos recursivos) dando una complejidad de O(n²).

En el peor de los casos, este algoritmo es menos eficiente que MergeSort. Cabe mencionar que en situaciones de la vida cotidiana, donde los datos tienen una distribución aleatoria (cualquiera de los ordenamientos es igualmente probable), se puede demostrar (está fuera de los alcances de este curso) que si bien el orden es igual para ambos algoritmos en el caso promedio, el tiempo de ejecución es menor para QuickSort.

 

 

 

Fuentes:

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

Capítulo 13. Métodos de ordenamiento: QuickSort (Parte I)

QuickSort

Pondremos nuestra atención en el funcionamiento de un nuevo método de ordenamiento que también utiliza la técnica de DyC, el QuickSort.

La idea principal del mismo consiste en elegir un elemento al azar, denominado pivot y, a partir de ese elemento, dividir la cadena en dos partes:

• A la izquierda del pivot todos los elementos menores
• A la derecha del pivot todos los elementos mayores.

Al hacer esto, el pivot queda ubicado en su posición definitiva dentro de la cadena, es decir, queda ordenado. Luego se aplica en forma recursiva el método a las dos partes restantes.

Existen distintas técnicas para la elección del pivot. Cabe destacar que una buena selección del elemento pivot significará una solución más eficiente. Cuanto más cercano al elemento mediano se encuentre el pivot, más parejas serán las dos partes de la cadena y mejor la solución. Por el contrario, cuanto más cercano a alguno de los extremos se encuentre el pivot, las partes serán más desparejas y la solución menos eficiente.

Al igual que con MergeSort veremos un ejemplo ilustrado que nos ayude a comprender la forma en que trabaja el método. Supondremos a continuación que nuestro algoritmo siempre selecciona como pivot el primer elemento de la cadena.

Señalamos a continuación el elemento pivot en negrita en las sucesivas llamadas recursivas.

Se puede observar que, a medida que el pivot es elegido, va quedando en la posición que le corresponde en la cadena ordenada. Verificar por ejemplo que el primer pivot, el número "15", queda sexto cuando es elegido y en la última cadena (la ordenada) también ocupa esa posición.

 

En el próximo capítulo presentaremos el pseudocódigo para el método de QuickSort así como también el análisis de complejidad temporal.

Fuentes:

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

Capítulo 12. Métodos de ordenamiento: MergeSort (Parte II)

En el capítulo anterior nos enfocamos en entender cómo funciona el método de ordenamiento denominado MergeSort. En esta oportunidad presentaremos el pseudocódigo y realizaremos el análisis de complejidad temporal para mostrar que esta técnica mejora las estudiadas previamente.

 

Pseudocódigo

 

 

Para mayor claridad se utiliza el método "Merge" que se encarga de combinar las subcadenas

 

 

 

Análisis de Complejidad Temporal

 

Podemos observar que en el algoritmo MergeSort se realizan 2 llamadas recursivas y la entrada va reduciéndose a la mitad en cada instancia. Por lo tanto nos encuadramos en el Caso 2 con un valor de a = 2.

 

Las operaciones no afectadas por la recursividad tienen una complejidad lineal, es decir, orden O(n) dando un valor de 1 para k. Como dijimos, al reducir la entrada por la mitad, el valor de b es 2.

 

Resumiendo, tenemos que a = b^k (ya que 2 = 2¹)  y entonces el costo del algoritmo es O(n*log n).

 

Esto representa una mejora a los algoritmos de inserción y selección que tenían una complejidad cuadrática. En el próximo capítulo veremos el método de ordenamiento QuickSort, también basado en la técnica de DyC.

 

Fuentes:

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

Capítulo 11. Métodos de ordenamiento: MergeSort (Parte I)

MergeSort

 

En este capítulo estudiaremos el método de ordenamiento conocido como MergeSort. Es un ejemplo de aplicación de la técnica de Divide y Conquista y, como veremos, el costo de su algoritmo es menor al de los métodos de selección e inserción vistos previamente.

 

La técnica consiste en dividir la cadena de entrada en dos mitades, ordenar cada una de las mitades y luego mezclar las mitades ordenadas en una nueva cadena ordenada.

 

Centraremos nuestra atención en un ejemplo simple que ayude a comprender el funcionamiento del algoritmo.

 

Se dispone de la siguiente cadena de enteros desordenada:

 

 

Lo que hacemos ahora es ir dividiéndola en mitades cada vez más pequeñas

 

 

En el algoritmo se verá que en cada iteración creamos 2 cadenas (una para la primera mitad y otra para la segunda mitad) y luego realizamos una llamada recursiva para cada una de ellas.

 

 

El caso base del algoritmo recursivo se producirá cuando la cadena de entrada tenga longitud igual a 1.

 

 

Una vez alcanzado el caso base, empezamos a combinar ordenadamente las subcadenas

 

 

 

Para obtener finalmente la cadena ordenada

 

 

 

 

En la próxima entrega veremos el pseudocódigo y analizaremos la complejidad temporal de MergeSort.

Capítulo 10. Métodos de ordenamiento: Inserción

El algoritmo para el método de ordenamiento por inserción consiste en ir ubicando cada elemento en su posición. Esto quiere decir que en cada iteración i se obtiene una secuencia ordenada de i - 1 elementos en la primera parte del arreglo y se inserta el elemento de la posición i para que ahora la secuencia de i elementos quede ordenada.

 

El pseudocódigo del algoritmo es el que sigue:

 

 

 

Al igual que en caso del ordenamiento por selección, las operaciones de asignación y comparación están incluidas dentro de dos bloques "para" lo que finalmente se traduce en una complejidad temporal de O(n²)

Fuentes:

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

Capítulo 9. Métodos de ordenamiento: Selección

Antes de  estudiar los métodos de ordenamiento que utilizan la técnica de Divide y Conquista, centraremos nuestra atención en los métodos de selección e inserción.

 

El objetivo es analizar la complejidad temporal de estos métodos más clásicos a fin de justificar la utilización de técnicas más eficientes.

 

El método de ordenamiento por selección consiste en ir buscando el menor de los elementos, colocarlo en la primera posición de una cadena, luego buscar el menor de los restantes, colocarlo en la segunda posición y así sucesivamente hasta que la cadena quede ordenada.

 

Presentamos el pseudocódigo de este método:

 

 

 

Sin hacer un análisis muy detallado podemos observar que las operaciones de asignación y comparación están embebidas en dos bloques "para", lo cual ocasiona que la complejidad temporal del método de selección sea O(n²)

 

Fuentes:

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

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 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.