MMAANNUUAALL
AANNÁÁLLIISSIISS DDEE AALLGGOORRIITTMMOOSS
VVeerrssiióónn 11..00
Colaboraron en el presente manual:
Docente
Ingeniería en Informática
INACAP Copiapó
Víctor Valenzuela Ruz
[email protected]
ÁÁrreeaa IInnffoorrmmááttiiccaa && TTeelleeccoommuunniiccaacciioonneess
Página 1
Copyright
© 2003 de Instituto Nacional de Capacitación. Todos los derechos reservados. Copiapó, Chile.
Este documento puede ser distribuido libre y gratuitamente bajo cualquier soporte siempre y
cuando se respete su integridad.
Queda prohibida su venta y reproducción sin permiso expreso del autor.
ÁÁrreeaa IInnffoorrmmááttiiccaa && TTeelleeccoommuunniiccaacciioonneess
Página 2
PPrreeffaacciioo
"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 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.
El Autor.
Copiapó, Enero 2003
ÁÁrreeaa IInnffoorrmmááttiiccaa && TTeelleeccoommuunniiccaacciioonneess
Página 3
ÍÍnnddiiccee GGeenneerraall
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
ÁÁrreeaa IInnffoorrmmááttiiccaa && TTeelleeccoommuunniiccaacciioonneess
Página 4
Presentación
1. Introducción
1.1. Motivación y Objetivos
1.2. Algunas Notas sobre la Historia de los Algoritmos
1.3. Fundamentos Matemáticos
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
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
Página
7
8
10
11
18
19
22
23
24
25
25
26
27
27
28
29
29
31
31
34
34
36
37
39
39
42
42
42
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 Branch and 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 Lista de Adyacencia
8.2.2. Matriz y Lista de Incidencia
8.3. Recorridos de Grafos
8.3.1. Recorridos en Amplitud
ÁÁrreeaa IInnffoorrmmááttiiccaa && TTeelleeccoommuunniiccaacciioonneess
45
45
45
46
48
49
51
51
55
57
58
60
61
63
63
64
65
65
68
74
75
78
78
80
81
81
88
88
92
97
101
103
104
Página 5
8.3.2. Recorridos en Profundidad
8.4. Grafos con Pesos
8.5. Árboles
8.6. Árbol Cobertor Mínimo
8.6.1. Algoritmo de Kruskal
8.6.2. Algoritmo de Prim
8.7. Distancias Mínimas en un Grafo Dirigido
8.7.1. Algoritmo de Dijkstra
8.7.2. Algoritmo de Ford
8.7.3. Algoritmo de Floyd-Warshall
106
108
108
109
111
113
114
115
118
118
118
121
123
124
9. Complejidad Computacional
9.1. Introducción
9.2. Algoritmos y Complejidad
9.3. Problemas NP Completos
9.4. Problemas Intratables
9.5. Problemas de Decisión
9.6. Algoritmos No Determinísticos
Bibliografía
126
ÁÁrreeaa IInnffoorrmmááttiiccaa && TTeelleeccoommuunniiccaacciioonneess
Página 6
Presentación
la madurez y
El curso de Análisis y Diseño de Algoritmos (ADA) tiene como propósito
fundamental proporcionar al estudiante las estructuras y técnicas de manejo de
datos más usuales y los criterios que le permitan decidir, ante un problema
determinado, cuál es la estructura y los algoritmos óptimos para manipular los
datos.
El curso está diseñado para proporcionar al alumno
los
conocimientos necesarios para enfrentar, tanto una gran variedad de los
problemas que se le presentarán en su vida profesional futura, como aquellos que
se le presentarán en los cursos más avanzados.
El temario gira en torno a dos temas principales: estructuras de datos y análisis de
algoritmos. Haciendo énfasis en la abstracción, se presentan las estructuras de
datos más usuales (tanto en el sentido de útiles como en el de comunes), sus
definiciones, sus especificaciones como tipos de datos abstractos (TDA's), su
implantación, análisis de su complejidad en tiempo y espacio y finalmente algunas
de sus aplicaciones. Se presentan también algunos algoritmos de ordenación, de
búsqueda, de recorridos en gráficas y para resolver problemas mediante recursión
y retroceso mínimo analizando también su complejidad, lo que constituye una
primera experiencia del alumno con el análisis de algoritmos y le proporcionará
herramientas y madurez que le serán útiles el resto de su carrera.
Hay que enfatizar que el curso no es un curso de programación avanzada, su
objetivo es preparar al estudiante brindándole una visión amplia de las
herramientas y métodos más usuales para la solución de problemas y el análisis de
la eficiencia de dichas soluciones. Al terminar el curso el alumno poseerá un
nutrido "arsenal" de conocimientos de los que puede echar mano cuando lo
requiera en su futura vida académica y profesional. Sin embargo, dadas estas
características del curso, marca generalmente la frontera entre un programador
principiante y uno maduro, capaz de analizar, entender y programar sistemas de
software más o menos complejos.
Para realizar las implantaciones de las distintas estructuras de datos y de los
algoritmos que se presentan en el curso se hará uso del lenguaje de programación
MODULA-2, C++ y Java.
ÁÁrreeaa IInnffoorrmmááttiiccaa && TTeelleeccoommuunniiccaacciioonneess
Página 7
Capítulo 1
Introducción
1.1 Motivación y Objetivos
La representación de información es fundamental
Comentarios de: MANUAL ANÁLISIS DE ALGORITMOS (0)
No hay comentarios