Manual Analisis de algoritmo

MANUAL
ANÁLISIS DE ALGORITMOS

Versión 1.0




Área Informática & Telecomunicaciones
Página 2

Prefacio
"Lo que debemos aprender a hacer lo aprendemos haciéndolo".
Aristóteles, Ethica Nicomachea II (325 A.C.)

El presente documento ha sido elaborado originalmente como apoyo a la
asignatura de “Análisis y Diseño de Algoritmos” del séptimo semestre de la
carrera de Ingeniería enGestión Informática, del Instituto Nacional de
Capacitación (INACAP). Este documento engloba la mayor parte de la materia
de este curso troncal e incluye ejemplos resueltos y algunos ejercicios que serán
desarrollados en clases.
El manual ha sido concebido para ser leído en forma secuencial, pero también
para ser de fácil consulta para verificar algún tema específico.
No se pretende queestos apuntes sustituyan a la bibliografía de la asignatura ni
a las clases teóricas, sino que sirvan más bien como complemento a las notas
que el alumno debe tomar en clases. Asimismo, no debe considerarse un
documento definitivo y exento de errores, si bien ha sido elaborado con
detenimiento y revisado exhaustivamente.
El autor pretende que sea mejorado, actualizado y ampliado con ciertafrecuencia, lo que probablemente desembocará en sucesivas versiones, y para
ello nadie mejor que los propios lectores para plantear dudas, buscar errores y
sugerir mejoras.
El Autor.

Copiapó, Enero 2003

Área Informática & Telecomunicaciones
Página 3

Índice General
Página
Presentación

7

1. Introducción
1.1. Motivación y Objetivos
1.2. Algunas Notas sobre la Historia de losAlgoritmos
1.3. Fundamentos Matemáticos

8
10
11

2. Algoritmos y Problemas
2.1. Definición de Algoritmo
2.2. Formulación y Resolución de Problemas
2.3. Razones para Estudiar los Algoritmos
2.4. Formas de Representación de Algoritmos
2.5. La Máquina de Turing

18
19
22
23
24

3. Eficiencia de Algoritmos
3.1. Introducción
3.2. Concepto de Eficiencia
3.3. Medidas de Eficiencia
3.4.Análisis A Priori y Prueba A Posteriori
3.5. Concepto de Instancia
3.6. Tamaño de los Datos
3.7. Cálculo de Costos de Algoritmos
3.7.1. Cálculo de eficiencia en análisis iterativo
3.7.2. Cálculo de eficiencia en análisis recursivo
3.8. Principio de Invarianza
3.9. Análisis Peor Caso, Mejor Caso y Caso Promedio
4. Análisis de Algoritmos
4.1. Introducción
4.2. Tiempos de Ejecución
4.3.Concepto de Complejidad
4.4. Órdenes de Complejidad
4.5. Notación Asintótica
4.5.1. La O Mayúscula
4.5.2. La o Minúscula
4.5.3. Diferencias entre O y o
4.5.4. Las Notaciones Ω y Θ
4.5.5. Propiedades y Cotas más Usuales
4.6. Ecuaciones de Recurrencias

25
25
26
27
27
28
29
29
31
31

34
34
36
37
39
39
42
42
42

Área Informática & Telecomunicaciones
Página 4

4.6.1.Introducción
4.6.2. Resolución de Recurrecias
4.6.3. Método del Teorema Maestro
4.6.4. Método de la Ecuación Característica
4.6.5. Cambio de Variable
4.7. Ejemplos y Ejercicios
5. Estrategias de Diseño de Algoritmos
5.1. Introducción
5.2. Recursión
5.3. Dividir para Conquistar
5.4. Programación Dinámica
5.5. Algoritmos Ávidos
5.6. Método de Retroceso (backtracking)
5.7. Método Branchand Bound
6. Algoritmos de Ordenamiento
6.1. Concepto de Ordenamiento
6.2. Ordenamiento por Inserción
6.3. Ordenamiento por Selección
6.4. Ordenamiento de la Burbuja (Bublesort)
6.5. Ordenamiento Rápido (Quicksort)
6.6. Ordenamiento por Montículo (Heapsort)
6.7. Otros Métodos de Ordenamiento
6.7.1. Ordenamiento por Incrementos Decrecientes
6.7.2. Ordenamiento por Mezclas Sucesivas
7.Algoritmos de Búsqueda
7.1. Introducción
7.2. Búsqueda Lineal
7.3. Búsqueda Binaria
7.4. Árboles de Búsqueda
7.5. Búsqueda por Transformación de Claves (Hashing)
7.6. Búsqueda en Textos
7.6.1. Algoritmo de Fuerza Bruta
7.6.2. Algoritmo de Knuth-Morris-Pratt
7.6.3. Algoritmo de Boyer-Moore
8. Teoría de Grafos
8.1. Definiciones Básicas
8.2. Representaciones de Grafos
8.2.1. Matriz y...