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

Imágen de pdf Manual de análisis y diseño de algoritmos

Manual de análisis y diseño de algoritmosgráfica de visualizaciones

Publicado el 11 de Febrero del 2019
437 visualizaciones desde el 11 de Febrero del 2019
842,9 KB
127 paginas
Creado hace 16a (31/12/2002)
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
v_valenzuela@inacap.cl

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
  • Links de descarga
http://lwp-l.com/pdf15165  

Comentarios de: Manual de análisis y diseño de algoritmos (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad

Revisar política de publicidad