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 8. Divide y Conquista (Parte IV)

En este capítulo veremos un nuevo ejemplo de aplicación de la técnica de DyC.

 

Problema

Sea A[1...n], n >= 1, un vector de enteros diferentes y ordenados crecientemente, tal que algunos de los valores pueden ser negativos. Diseñar un algoritmo que devuelva un índice natural k, 1 <= k <= n, tal que A[k] = k, siempre que tal índice exista.

Pseudocódigo



 

La letra C significa que ese bloque tiene una complejidad temporal constante.

 

Análisis de complejidad Temporal

Vemos que el tamaño de la entrada se reduce a la mitad, por lo tanto nos encuadramos en el Caso 2

 

a = 1

b = 2

k = 0

 

Notar que 'a' es igual a 1 porque nunca se ejecutan ambos bloques (si uno se ejecuta, el otro no)

 

Reemplazando estos valores de los parámetros el costo del método queda en O(log n)

 

En este ejemplo, pusimos como pre condición, que el vector de enteros estuviera ordenado en forma creciente. En los próximos capítulos veremos métodos de ordenamiento que utilizan la técnica de Divide y Conquista para ordenar una cadena.