Resumen de Algoritmos y estructura de datos 1 PDF

Preview

Summary

MÓDULO 1AlgoritmosLlamamos algoritmo al conjunto finito y ordenado de acciones con las que podemos resolver un determinado problema. Llamamos problema a una situación que se nos presenta y que, mediante la aplicación de un algoritmo, pretendemos resolver.Cuando se tienen algoritmos distintos que res...

Description

ALGORITMOS Y ESTRUCTURAS DE DATOS I

MÓDULO 1 Algoritmos Llamamos algoritmo al conjunto finito y ordenado de acciones con las que podemos resolver un determinado problema. Llamamos problema a una situación que se nos presenta y que, mediante la aplicación de un algoritmo, pretendemos resolver. Cuando se tienen algoritmos distintos que resuelven un mismo problema de maneras diferentes, se dice que dichos algoritmos son equivalentes.

Diseño de algoritmos Para poder diseñar correctamente un algoritmo, es necesario conocer su contexto, de manera que se tenga claro su alcance, sus datos de entrada y sus salidas. Algunos autores definen a los algoritmos como procedimientos computacionales que se encargan de tomar las entradas, de procesarlas y generar una o varias salidas. Para diseñar los algoritmos, también, se cuenta con tres recursos, que son: la memoria, las operaciones aritméticas y las operaciones lógicas.

Análisis de algoritmos A la hora de elegir un algoritmo para programar la funcionalidad de una aplicación, se deberán tener en cuenta los parámetros, como el hardware sobre el que se ejecutará dicha aplicación, la cantidad de datos que procesará y los tiempos de ejecución esperados por el tipo de usuario al que está destinada. Si se sacan otros factores (como la velocidad, la cantidad de procesadores, la calidad del compilador y la cantidad y la velocidad de la memoria), el tiempo de ejecución de un algoritmo es una función de la cantidad de los datos de entrada que debe procesar. A mayor cantidad de datos, mayor será el tiempo de ejecución, por lo que se utilizan funciones matemáticas para caracterizar la eficiencia de los algoritmos. Un algoritmo lineal es aquel que tiene un tiempo de ejecución que responde a una función lineal. Es el más eficiente. Sin embargo, existen algoritmos no lineales con tiempos de ejecución mucho más elevados. Las funciones más comúnmente encontradas en el análisis de algoritmos son las siguientes, ordenadas de mayor a menor eficiencia: 

Lineal: El tiempo de ejecución se incrementa a la misma velocidad en que se aumenta la cantidad de datos de entrada. O sea, son directamente proporcionales a la cantidad de datos de entrada a los que se someten. Es por esto que es el tipo de algoritmo más eficiente. 1

ALGORITMOS Y ESTRUCTURAS DE DATOS I



N*log(N): El logaritmo es una función que crece lentamente. Aunque crece más rápido que la función lineal, es más lenta que la cuadrática y la cúbica. El tiempo de ejecución, en estos algoritmos, es N veces el logaritmo de N, siendo N el tamaño de la entrada.



Cuadrática: El tiempo de ejecución está definido por una función cuadrática (por ejemplo, 3N2+2N+3) siendo N el tamaño de la entrada. Los algoritmos de este tipo son menos eficientes que los del tipo N*Log(N).



Cúbica: El tiempo de ejecución está definido por una función cúbica (por ejemplo, 4N3+3N2+2N+3) siendo N el tamaño de la entrada. Están entre los menos eficientes, ya que, ante pequeños incrementos en el tamaño de los datos, el tiempo de ejecución del algoritmo crece rápidamente.

Pueden darse casos en que, por las constantes implicadas, una función N*Log(N) sea más eficiente que una lineal. Sin embargo, ante una misma complejidad, las lineales son más eficientes. Distinto es el caso de los algoritmos cuadráticos, que tienen altos tiempos de ejecución, a partir de un tamaño de entrada de unos pocos miles. Peor aún, es el caso de los algoritmos cúbicos que tienen tiempos de ejecución lentos, a partir de un tamaño de entrada de unos pocos cientos. Al observar estos gráficos, se puede evidenciar que, ante las entradas pequeñas, las diferencias en el tiempo de ejecución de cada función no son muy grandes. Sin embargo, cuando se tienen entradas grandes, las diferencias en el tiempo de ejecución de cada función se vuelven grandes. A medida que se aumenta el tamaño de la entrada, se hace notable la diferencia de la eficiencia. Es en las grandes cantidades de entradas donde preocupa más la eficiencia del algoritmo. Cabe aclarar que, cuando se está ante la presencia de entradas pequeñas, la tasa de crecimiento puede no llegar a ser del todo importante. Incluso, puede suceder que una función con una tasa de crecimiento mayor que otra función sea más eficiente. De todas maneras, se podrá usar una u otra función sin notar mucha diferencia entre ellas. Pero, esto no es lo que suele suceder. Por ello, es necesario abocarse a analizar los tiempos de ejecución ante las entradas grandes. Es por esto que la optimización del algoritmo es la tarea principal, a la hora de hacer que un código se ejecute en forma eficiente, es decir, diseñar un buen algoritmo desde el principio. No importa qué tanto se optimice el código. La optimización debe realizarse, primeramente, sobre el algoritmo, porque es el que define la eficiencia en la ejecución.

Notación O 2

ALGORITMOS Y ESTRUCTURAS DE DATOS I

El impacto se profundiza a medida que crecemos en el problema a resolver, por lo cual, consideraremos a N tendiendo a infinito En ese caso, estaremos considerando su comportamiento asintótico. Al momento de identificar diferentes relaciones entre funciones y recursos, podemos agrupar los comportamientos resultantes en familias de funciones, dependiendo de su comportamiento asintótico, y les asignaremos un orden de complejidad O. La notación O-grande no toma en cuenta los factores constantes, es decir, ignora si se hace una mejor o peor implementación del algoritmo, además de independizarlo de los datos de entrada del algoritmo. Como utilidad de aplicar este concepto es encontrar un límite superior del tiempo de ejecución, es decir, el peor caso.

Cota superior asintótica Cota superior asintótica es otra manera de nombrar a la notación O. Se ha notado que los algoritmos, ante entradas pequeñas, pueden mostrar una diferencia de eficiencia mínima. En esos casos, no parece lógico realizar un gran esfuerzo por optimizar un algoritmo, ya que el tiempo de ejecución mejorará muy poco con respecto a otro algoritmo más sencillo. Sin embargo, también se mencionó que esas situaciones no son tan comunes y que, en realidad, se necesitan algoritmos que funcionen eficientemente ante las grandes entradas. Allí, las diferencias en el tiempo de ejecución, entre los algoritmos equivalentes, se hacen mayores. Además, en estos casos, sí se requiere realizar un esfuerzo para optimizar los algoritmos. Lo que se busca es garantizar que el tiempo de ejecución de un algoritmo siempre sea menor a una cota o límite superior. Con esto, se sabe que, en el peor de los casos, este algoritmo tendrá un tiempo de ejecución que será proporcional a la función lineal N. Lo importante en este tipo de análisis es poder encontrar una función que acote el crecimiento que, en el peor de los casos, tendrá la complejidad del algoritmo. Al conjunto de funciones que acotan dicho crecimiento lo llamamos O(g(x)) donde x representa la cantidad de elementos que se van a procesar y g(x) es cualquier cota superior de la función de complejidad del algoritmo. Más formalmente, lo planteamos de la siguiente manera: sea f(x) la función que expresa la complejidad de un algoritmo, entonces la expresión f(x) pertenece a O(g(x)), significa que f(x) crece, a lo sumo, tan rápido como cualquiera de las funciones g del conjunto O.

3

ALGORITMOS Y ESTRUCTURAS DE DATOS I

Por lo tanto, ahora se usará la O mayúscula para denotar aquella función que indique el límite superior de crecimiento de una función. Esto es conocido como notación O mayúscula o big O. Es evidente notar que el orden será definido por el término más importante de la función. Esto significa que, ante distintas funciones, se hará énfasis en el término que le da el grado a la función analizada. Este término es el más dominante y representa la tasa de crecimiento que interesa analizar. Por ejemplo, si se tiene una función cuadrática del tipo: aN 2 + bN + c, se dirá que es del orden cuadrático O(N2) y que se prescinde de los demás términos que, como ya se mencionó, son despreciables. Como conclusión, podemos decir que los algoritmos polinomiales son “buenos” algoritmos y los algoritmos exponenciales son “malos” algoritmos.

Cota inferior asintótica y cota ajustada asintótica Si bien es de utilidad analizar el peor de los casos y conocer el límite superior (el cual no será superado), también es útil, a veces, conocer el límite inferior, es decir, el mejor de los casos. Asimismo, se puede querer expresar que una función tiene la misma tasa de crecimiento que otra. Entonces, se encuentra la notación O(g(x)) para denotar una cota inferior asintótica, donde se indica que una función g(x) crecerá más lento o, a lo sumo, tan rápido como f(x). Esto quiere decir que el algoritmo analizado no se comportará mejor que una función. En otras palabras, el tiempo de ejecución será siempre mayor o, a lo sumo, igual que el de esa función.

4

ALGORITMOS Y ESTRUCTURAS DE DATOS I

También, se encuentra la notación T(g(x)), para denotar una cota ajustada asintótica. Por esto, si se dice que una función f(x) es T(g(x)), significa que la función f(x) tendrá la misma tasa de crecimiento que g(x). A modo de conclusión, el análisis de los algoritmos es de vital importancia para poder decidir, cuando se tienen varios algoritmos, cuál es el que más conviene, cuál es el mejor y cuál se adecua mejor a las distintas necesidades. Asimismo, el análisis de los algoritmos permite anticiparse y saber cuál será el comportamiento de un algoritmo en el peor de los casos.

Conceptos para tener en cuenta  Un programa que se va a ejecutar muy pocas veces hace que nuestro foco deba estar en la codificación y la depuración del algoritmo, donde la complejidad no es el factor crítico a considerar.  Un programa que se utilizará por mucho tiempo, seguramente, será mantenido por varias personas en el curso de su vida útil. Esto hace que los factores que debemos considerar sean los que se relacionan con su legibilidad; incluso, si la mejora de ella impacta en la complejidad de los algoritmos empleados.  En un programa que únicamente va a trabajar con datos pequeños (valores bajos de N), el orden de complejidad del algoritmo que se use suele ser irrelevante.  Un programa de baja complejidad, en cuanto a tiempo de ejecución, suele demandar un alto consumo de memoria y viceversa. Esto es una situación que debemos evaluar para entender cómo impactan ambos factores.  Un programa orientado al cálculo numérico hace que debamos tener en cuenta más factores que su complejidad o, incluso, su tiempo de ejecución. En estos casos, debemos considerar la precisión del cálculo, el máximo error introducido en cálculos intermedios, la estabilidad del algoritmo, etcétera.

El problema de la búsqueda estática Sznajdleder define el problema de la búsqueda estática: Dado un entero X y una matriz A, devolver la posición de X en A o una indicación de que no está presente. Si X aparece más de una vez, devolver cualquiera de las apariciones. La matriz A nunca es modificada. Esto implica, también, que no se presentarán inserciones con nuevos elementos o eliminaciones. Por esto, no será necesario tener en cuenta el tiempo insumido en ordenar la estructura posterior a la inserción o eliminación. 5

ALGORITMOS Y ESTRUCTURAS DE DATOS I

Tipos de búsqueda 

Interna: Cuando los elementos entre los que buscamos están almacenados en la memoria.



Externa: Cuando los datos entre los que buscamos están almacenados en un dispositivo externo; en este caso, la búsqueda se realiza a partir de un determinado campo denominado campo clave.

En cualquier caso, buscar un determinado elemento, en un array o en un archivo, es encontrar la posición del array o del archivo en que se encuentra almacenado ese elemento, o bien, detectar que dicho elemento no pertenece al array o al archivo en el que se busca.

Métodos Algoritmo de búsqueda secuencial Es un método que consiste en comparar cada elemento de una estructura con el elemento que se quiere encontrar. Esto supone que no es necesario tener una estructura ordenada. Es evidente que, al tener que transitar por todos los elementos, es poco eficiente. Además, este algoritmo puede terminar en dos estados: con éxito (se encontró el elemento buscado) o sin éxito (no se localizó el elemento buscado). De todas maneras, la mayoría de los algoritmos de búsqueda se basan en él. En el peor de los casos, se tendrá que transitar por todos los elementos hasta llegar al último. Por lo tanto, es de orden lineal O(n). Esto sucede tanto en un caso exitoso (cuando el elemento buscado se encuentra y está en la última posición), como en un caso sin éxito (cuando no se logra encontrar al elemento buscado y se tuvo que recorrer toda la estructura). El mejor de los casos corresponde a encontrar el elemento buscado en la primera posición. En promedio, se podrá obtener un caso con éxito recorriendo la mitad de la estructura, es decir, n/2, por lo que este algoritmo es de orden lineal O(n).

Algoritmo de búsqueda binaria Este algoritmo parte de una estructura que está ordenada. Es un algoritmo mucho más eficiente, debido a que va subdividiendo la estructura en mitades hasta encontrar el elemento buscado o evidenciar que dicho elemento no se encuentra. Este método está basado en la técnica divide y vencerás. El procedimiento del algoritmo es bastante sencillo 6

ALGORITMOS Y ESTRUCTURAS DE DATOS I

y consta de los siguientes pasos, si asumimos que la estructura está ordenada de menor a mayor: 1) se comienza el proceso en el elemento central de la estructura (en caso de que la cantidad de elementos sea impar) o casi central (en caso de que la cantidad de elementos sea par). Es decir, se divide a la estructura en dos mitades; 2) se verifica si el elemento buscado corresponde al elemento central, en cuyo caso, finaliza el proceso. En caso contrario, se corrobora si el elemento buscado es mayor o menor a dicho elemento central. Si el elemento que se intenta hallar es de mayor valor que el elemento central, se descarta la primera mitad. Si el elemento que se busca es de menor valor que el elemento central, se descarta la segunda mitad; y, por último, 3) con la mitad no descartada, se comienza el proceso de nuevo, desde 3 el primer paso. Se repite este mecanismo de manera sucesiva hasta encontrar al elemento buscado o hasta que no se pueda subdividir más la estructura, en cuyo caso se concluye que el elemento no se encuentra. Programáticamente, este algoritmo se resuelve, inicialmente, teniendo referencias a los extremos y el centro de la estructura. En el mejor de los casos, al iniciar el proceso, el elemento en la posición central corresponde al elemento buscado. Pero es muy poco probable que esto ocurra. En el peor de los casos, se tienen dos situaciones: 1. se podrá conseguir un estado de éxito y encontrar al elemento buscado en la última iteración. Se hará, por consiguiente, una cantidad de iteraciones igual a Log(n). La última iteración corresponderá a un rango de un solo elemento; y 2. se podrá conseguir un estado sin éxito, es decir, realizar todas las iteraciones y detectar que no coinciden con el elemento buscado. Se harán, por consiguiente, una cantidad de iteraciones igual a Log(n)+1. La última iteración corresponderá a un rango nulo, es decir, no contendrá ningún elemento. En promedio, se obtendrá al elemento buscado con una iteración menos que el peor caso.

Búsqueda por interpolación En la mayoría de los casos, la búsqueda binaria es la primera opción implementada para la búsqueda de un elemento. Son muy pocos los casos donde se opta por elegir otro método. 7

ALGORITMOS Y ESTRUCTURAS DE DATOS I

La búsqueda por interpolación es una alternativa cuando se presentan ciertas situaciones particulares y ofrece, en promedio, un tiempo de ejecución mejor. Sin embargo, en el peor de los casos, ofrecen un tiempo de ejecución bastante peor que el de la búsqueda binaria. Por lo tanto, es importante detectar cuándo es realmente ventajoso aplicar este método. Se recomienda aplicar este algoritmo: 

cuando acceder al elemento buscado es muy costoso: el acceso a un elemento que se encuentra en la memoria es algo muy rápido. Pero, cuando se debe acceder a un elemento que está almacenado en un disco, el acceso se vuelve una tarea costosa, que demanda tiempo y recursos; y



cuando los elementos están ordenados según una distribución uniforme.

Este método se basa en analizar el problema para realizar una estimación que permita, desde un principio, determinar dónde está localizado el elemento que se quiere encontrar. En el método de búsqueda binaria, en cada iteración, se toma el valor central, mientras que, en la búsqueda por interpolación, se toma como referencia un valor que corresponde a la valuación de una fórmula mucho más compleja. Si bien el cálculo de este valor complejiza el proceso y enlentece cada iteración, ocurre que, en muchos casos, es insignificante comparado con el costo de tener que acceder a un elemento. En el peor de los casos, cuando los elementos de la estructura no responden a una distribución uniforme, este método puede tener un tiempo de ejecución lineal. Pero, si se tiene una estructura con distribución uniforme o, al menos, bastante uniforme, se puede obtener un promedio de comparaciones de O(n*Log(Log(n))). Esta expresión contiene la operación de logaritmo dos veces, una vez más que en la búsqueda binaria, lo cual permite una reducción considerable de las iteraciones.

Limitación del análisis O El análisis O mayúscula es una herramienta muy efectiva, pero también tiene sus limitaciones. Como ya hemos mencionado, su uso no es apropiado para entradas de pequeño tamaño. Para este tipo de entradas, siempre es conveniente utilizar el algoritmo más simple. Asimismo, para un algoritmo concreto, la constante implicada en el análisis O mayúscula puede ser demasiado grande como para resultar práctica. Las constantes de gran tamaño pueden entrar en acción cuando un algoritmo es excesivamente complejo. También influyen, porque nuestro análisis no tiene en cuenta las constantes y no puede, por lo tanto, diferenciar entre cosas como los accesos a memoria (que son baratos) y los accesos a discos (que normalmente son varios miles de veces más caros). Nuestro análisis asume que tenemos una memoria infinita, pero para las aplicaciones que implican grandes conjuntos de datos, la falta de memoria suficiente puede ser un grave problema. 8

ALGORITMOS Y ESTRUCTURAS DE DATOS I

Otro elemento que produce un impacto es, en aquellos algoritmos complejos, la influencia de las constantes que, en nuestros casos, no son consideradas.

Complejidad computacional de problemas y el análisis y diseño de algoritmos A través de llamados al sistema operativo se puede conocer el valor del reloj de tiempo real. Invocando al reloj, antes y después de realizar el algoritmo se tendrá una medida de la duración del tiempo de ejecución. Sin embargo, esta medida es muy dependiente del hardware (memoria, reloj, procesador), del sistema operativo (multitarea, multiusuario) y puede variar significativamente dependiendo del computador, del compilador, y de la carga del sistema. Al disponer de sistemas con multiprocesadores o que la ejecución sea distribuida también afecta medir el tiempo con cronómetro. Por la razón anterior como una medida del tiempo de ejecución, se considera contar las instrucciones del lenguaje de alto nivel que son necesarias realizar.

Eficiencia algorítmica La eficiencia de un algoritmo es determinada por el menor consumo de recursos, como el tiempo y la memoria que se necesitan para que sea ejecutado. Esta eficiencia se puede cuantificar con las siguientes medidas de complejidad: 

Complejidad temporal o tiempo de ejecución: “Se define el coste o complejidad temporal de un algoritmo como el tiempo empleado por éste para ejecutarse y proporcionar un resultado a partir de los da...