MMAANNUUAALL DDEE AANNÁÁLLIISSIISS YY DDIISSEEÑÑOO
DDEE AALLGGOORRIITTMMOOSS
VVeerrssiióónn 11..00
DDiirreecccciióónn ddee ÁÁrreeaa IInnffoorrmmááttiiccaa
ww wwww .. ii nnffoorrmmaattii ccaa..ii nnaa ccaapp.. ccll
Colaboraron en el presente manual:
Víctor Valenzuela Ruz
[email protected]
Docente
Ingeniería en Gestión Informática
INACAP Copiapó
Página 1
Co pyrigh t
© 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.
Página 2
PPrr ee ffaa cc iioo
"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 Algoritm os” 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 20 0 3
Página 3
ÍÍnn dd iicc ee GGee nn ee rr aa ll
Página
Pre s e n tació n
7
1. In tro du cció n
1.1. Motivación y Objetivos
1.2. Algunas Notas sobre la Historia de los Algoritmos
1.3. Fundamentos Matemáticos
2. Algo ritm o s y Pro ble m as
2.1. Definición de Algoritmo
2.2. Formulación y Resolución de Problemas
2.3. Razones par a Estudiar los Algoritmos
2.4. Formas de Representación de Algoritmos
2.5. La Máquina de Turing
3. Eficie n cia d e Algo ritm o s
3.1. Introducción
3.2. Concepto de Eficiencia
3.3. Medidas de Eficiencia
3.4. Análisis A Priori y Pr ueba 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 ális is d e Algo ritm o s
4.1. Introducción
4.2. Tiempos de Ejecución
4.3. Concepto de Com plejidad
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 W
4.5.5. Propiedades y Cotas más Usuales
y Q
4.6. Ecuaciones de Recurrencias
4.6.1. Introducción
4.6.2. Resolución de Recurrecias
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
45
45
Página 4
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. Es trate gias d e D is e ñ o d e Algo ritm o s
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 Bran ch an d Boun d
6. Algo ritm o s d e Ord e n am ie n to
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 Or denamiento
6.7.1. Ordenamiento por Incrementos Decrecientes
6.7.2. Ordenamiento por Mezclas Sucesivas
7. Algo ritm o s de Bú s qu e da
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. Te o ría d e Grafo s
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
8.3.2. Recorridos en Profundidad
8.4. Grafos con Pesos
8.5. Árboles
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
10 3
10 4
10 6
10 8
10 8
Página 5
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
9. Co m ple jid ad Co m pu tacio n al
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
Biblio grafía
10 9
111
113
114
115
118
118
118
121
123
124
126
Página 6
Pre s e n tació n
la madurez y
tanto una gran variedad de
El curso de Análisis y Diseño de Algoritm os (ADA) tiene como propósito
fundamental proporcio nar 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.
los
El curso está diseñado para propor cionar al alumno
conocimientos necesarios para enfrentar,
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 solu ciones. 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
softw are 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 J ava.
Página 7
Capítu lo 1
In tro du cció n
1.1 Mo tivació n y Obje tivo s
La representación de información es fundamental para las Ciencias de la
Computación.
La Ciencia de la Computación (Com puter Scien ce) , es mucho más que el
estudio de cómo usar o programar
Comentarios de: Manual de análisis y diseño de algoritmos (0)
No hay comentarios