PDF de programación - Manual de análisis y diseño de algoritmos

MMAANNUUAALL DDEE AANNÁÁLLIISSIISS YY DDIISSEEÑÑOO

DDEE AALLGGOORRIITTMMOOSS

VVeerrssiióónn 11..00



DDiirreecccciióónn ddee ÁÁrreeaa IInnffoorrmmááttiiccaa

ww wwww ..iinnffoorrmmaattiiccaa..iinnaa ccaapp..ccll





Víctor Valenzuela Ruz
[email protected]

Docente

Ingeniería en Gestión Informática

INACAP Copiapó

Colaboraron en el presente manual:

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.

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



Página 3





ÍÍnnddiiccee GGeenneerraall



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

45
45

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



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 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





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

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
103

104
106
108
108

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. 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



109
111

113
114
115

118
118
118
121
123
124



126

Página 6



Presentación



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 propor cionar al alumno la madurez y 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.


Página 7




Capítulo 1

Introducción


1.1 Motivación y Objetivos


La representación de información es fundamental para las Ciencias de la
Computación.

La Ciencia de la Computación (Computer Science), es mucho más que el
estudio de cómo usar o programar las computadoras. Se ocupa de
algoritmos, métodos de calcular resultados y máquinas autómatas.

Antes de las computadoras, existía la computación, que se refiere al uso de
métodos sistemáticos para encontrar solucio