Tesis de Algoritmos para Caminos Mínimos , Universidad Nacional de Ingeniería (UNI) - johani Olivos Iparraguirre

Introducción
1. Preliminares 10
1.1. Teoría de Grafos  10
1.1.1. Adyacencia e Incidencia de vértices. 11
1.2. Representación de los grafos  12
1.3. Grado de un vértice13

1.4. Cadenas y Ciclos - Caminos y Circuitos .14
1.5. Grafos Etiquetados y Ponderados15
1.6. Tipos de Grafos 16
1.7. Isomorfismo de Grafos16
1.8. Subgrafos 17
1.9. Grafo Bipartitos17
1.10. Conexidad 18
1.11. ´ Arboles19
1.11.1. Arboles enraizados y ordenados . . . . . . . . . . . . . . . . . . . . . . . . 21
1.11.2. ´ Arboles binarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2. Complejidad de Algoritmos 23
2.1. Conceptos Básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2. Eficiencia y Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3. Análisis de Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1. Reglas generales para el calculo del numero de OE . . . . . . . . . . . . . 27
2.4. Cotas de Complejidad: Medidas Asintoticas . . . . . . . . . . . . . . . . . . . . . 28
2.4.1. Dominio Asintotico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.2. Cota Superior: Notación O . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.3. Cota inferior: Notación
 . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.4. Orden Exacto: Notacion . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5. Lenguaje Formal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.1. Alfabeto, cadena de caracteres . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.2. Operaciones con lenguajes . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.6. Problemas Matemáticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.6.1. Problemas de Decisión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.6.2. Problemas Tratables e Intratables . . . . . . . . . . . . . . . . . . . . . . 33
2.6.3. Algoritmos Determinısticos y No Determinısticos . . . . . . . . . . . . . . 33
2.6.4. Reductibilidad o Transformación Polinomica . . . . . . . . . . . . . . . . 37
2.7. Clases de Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.7.1. Complejidad de Clase P . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Español | Edición : Ultima | PDF  | Mb

ENLACES

| RapidShare | PutLocker |  4shared |