ene 11 2010

MANUAL DE ANÁLISIS Y DISEÑO DE ALGORITMOS

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 en Gestió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 que estos 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 cierta
frecuencia, lo que probablemente desembocará en sucesivas versiones, y para
ello nadie mejor que los propios lectores para plantear dudas, buscar errores y
sugerir mejoras.

Contenido del Libro:

Presentación 7

1. Introducción
1.1. Motivación y Objetivos 8
1.2. Algunas Notas sobre la Historia de los Algoritmos 10
1.3. Fundamentos Matemáticos 11

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

3. Eficiencia de Algoritmos
3.1. Introducción 25
3.2. Concepto de Eficiencia 25
3.3. Medidas de Eficiencia 26
3.4. Análisis A Priori y Prueba A Posteriori 27
3.5. Concepto de Instancia 27
3.6. Tamaño de los Datos 28
3.7. Cálculo de Costos de Algoritmos
3.7.1. Cálculo de eficiencia en análisis iterativo 29
3.7.2. Cálculo de eficiencia en análisis recursivo 29
3.8. Principio de Invarianza 31
3.9. Análisis Peor Caso, Mejor Caso y Caso Promedio 31

4. Análisis de Algoritmos
4.1. Introducción 34
4.2. Tiempos de Ejecución 34
4.3. Concepto de Complejidad 36
4.4. Órdenes de Complejidad 37
4.5. Notación Asintótica
4.5.1. La O Mayúscula 39
4.5.2. La o Minúscula 39
4.5.3. Diferencias entre O y o 42
4.5.4. Las Notaciones W y Q 42
4.5.5. Propiedades y Cotas más Usuales 42
4.6. Ecuaciones de Recurrencias
4.6.1. Introducción 45
4.6.2. Resolución de Recurrecias 45
4.6.3. Método del Teorema Maestro 45
4.6.4. Método de la Ecuación Característica 46
4.6.5. Cambio de Variable 48
4.7. Ejemplos y Ejercicios 49

5. Estrategias de Diseño de Algoritmos
5.1. Introducción 51
5.2. Recursión 51
5.3. Dividir para Conquistar 55
5.4. Programación Dinámica 57
5.5. Algoritmos Ávidos 58
5.6. Método de Retroceso (backtracking) 60
5.7. Método Branch and Bound 61

6. Algoritmos de Ordenamiento
6.1. Concepto de Ordenamiento 63
6.2. Ordenamiento por Inserción 63
6.3. Ordenamiento por Selección 64
6.4. Ordenamiento de la Burbuja (Bublesort) 65
6.5. Ordenamiento Rápido (Quicksort) 65
6.6. Ordenamiento por Montículo (Heapsort) 68
6.7. Otros Métodos de Ordenamiento
6.7.1. Ordenamiento por Incrementos Decrecientes 74
6.7.2. Ordenamiento por Mezclas Sucesivas 75

7. Algoritmos de Búsqueda
7.1. Introducción 78
7.2. Búsqueda Lineal 78
7.3. Búsqueda Binaria 80
7.4. Árboles de Búsqueda 81
7.5. Búsqueda por Transformación de Claves (Hashing) 81
7.6. Búsqueda en Textos
7.6.1. Algoritmo de Fuerza Bruta 88
7.6.2. Algoritmo de Knuth-Morris-Pratt 88
7.6.3. Algoritmo de Boyer-Moore 92

8. Teoría de Grafos
8.1. Definiciones Básicas 97
8.2. Representaciones de Grafos
8.2.1. Matriz y Lista de Adyacencia 101
8.2.2. Matriz y Lista de Incidencia 103
8.3. Recorridos de Grafos
8.3.1. Recorridos en Amplitud 104
8.3.2. Recorridos en Profundidad 106
8.4. Grafos con Pesos 108
8.5. Árboles 108
8.6. Árbol Cobertor Mínimo
8.6.1. Algoritmo de Kruskal 109
8.6.2. Algoritmo de Prim 111
8.7. Distancias Mínimas en un Grafo Dirigido
8.7.1. Algoritmo de Dijkstra 113
8.7.2. Algoritmo de Ford 114
8.7.3. Algoritmo de Floyd-Warshall 115

9. Complejidad Computacional
9.1. Introducción 118
9.2. Algoritmos y Complejidad 118
9.3. Problemas NP Completos 118
9.4. Problemas Intratables 121
9.5. Problemas de Decisión 123
9.6. Algoritmos No Determinísticos 124

Bibliografía

Descarga: http://www.megaupload.com/?d=RV1JUGHU

¡¡ Comentar es Agradecer !!


Mensaje Privado
24482 Visitas


FavoriteLoadingAñadir a favoritos


Categoria: Tutoriales y Ayuda

RSS Seguir Feed RSS Comentarios | Temas de fnava91

Comentarios

Deja tu comentario

Debes iniciar sesion para poder enviar un comentario.

Terminos y Condiciones - Politica de Privacidad - Report Abuse - DMCA