Análisis de algoritmos

Universidad Rafael Landívar
Ingeniería en Informática y Sistemas
Análisis de Algoritmos

Trabajo de investigación final

Guatemala, 21 de noviembre 2007

Índice

Índice 2

Introducción 3

Objetivos 3

Tema 1: Tipos de datos abstractos fundamentales 4

TDA lista 4
TDA pila 5
TDA cola 5
Eliminación de recursividad utilizando Pilas 7
Correspondencia 9

Tema 2: Modelos declasificación interna 9

Clasificación rápida (quicksort) 9
Ejemplo QuickSort 10
Clasificación por “montículos”(heapsort) 11
Ejemplo Heapsort 11
Clasificación por “urnas”(binsort) 14
Ejemplo binsort 15
Clasificación por comparaciones 16

Tema 3: Técnicas de Análisis de Algoritmos 16

Eficiencia de los algoritmos 16
Comparación de la eficiencia de algoritmos: flops y etime 17
Análisis deprogramas recursivos 17
Ejemplo. 18
Ecuaciones de recurrencia 18

Tema 4: Técnicas de Diseño de Algoritmos 19

Algoritmo Divide y vencer 19
Ejemplo práctico 20
Algoritmo Ávido 20
Método de Retroceso (Backtracking): 21
Algoritmo retroceso generalizado 21
Algoritmo de Búsqueda local 22

Bibliografía 23

Introducción

El análisis de algoritmos es una parte importante de la Teoría decomplejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.
A la hora de realizar un análisis teórico de algoritmos es corriente calcular su complejidad en un sentido asintótico, es decir, para un tamañode entrada suficientemente grande. La cota superior asintótica, y las notaciones omega y theta se usan con esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(log(n)), coloquialmente "en tiempo logarítmico". Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo notienen porque tener la misma eficiencia. No obstante la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas por una constante multiplicativa llamada constante oculta.
La medida exacta (no asintótica) de la eficiencia a veces puede ser computada pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo,llamada modelo de computación. Un modelo de computación puede definirse en términos de una ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos una búsqueda binaria tiene n elementos, y podemos garantizar que una única búsqueda binaria puede realizarse en un tiempo unitario,entonces se requieren como mucho log2 N + 1 unidades de tiempo para devolver una respuesta.
Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usan algoritmos, porque tienen más precisión y así les permite saber cuanto tiempo pueden suponer que tomará la ejecución. Para algunas personas, como los desarrolladores de videojuegos, una constante oculta puedesignificar la diferencia entre éxito y fracaso.
Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido, debemos garantizar que el tiempo requerido para realizar un paso esté acotado superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuestopuede no estar garantizado en ciertos contextos. Si por ejemplo los números involucrados en la computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la adición requiere un tiempo constante (usando papel y lápiz, compara el tiempo que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlo con enteros de 1000 dígitos).

Tema 1: Tipos de datos...