Manual algoritmos
Páginas: 54 (13299 palabras)
Publicado: 7 de septiembre de 2010
MANU AL DE ANÁLISIS Y DISEÑO DE ALGORITMOS
Versión 1 .0
Dirección de Áre a I nform ática
w ww . i nform ati ca.i na cap. cl
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
Copyright
© 2003 de Instituto Nacional de Capacitación. Todos los derechos reservados. Copiapó, Chile. Estedocumento 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
Prefacio
"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 laasignatura 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énpara 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 revisadoexhaustivamente. 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
Índice Gener al
Página Presentación 1. Introducción 1.1. Motivación y Objetivos 1.2. Algunas Notassobre 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 yPrueba 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 Ω y Θ 4.5.5. Propiedades y Cotas más Usuales 4.6. Ecuaciones de Recurrencias 4.6.1. Introducción 4.6.2. Resolución de Recurrecias 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
4.6.3. Método del TeoremaMaestro 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....
Versión 1 .0
Dirección de Áre a I nform ática
w ww . i nform ati ca.i na cap. cl
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
Copyright
© 2003 de Instituto Nacional de Capacitación. Todos los derechos reservados. Copiapó, Chile. Estedocumento 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
Prefacio
"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 laasignatura 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énpara 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 revisadoexhaustivamente. 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
Índice Gener al
Página Presentación 1. Introducción 1.1. Motivación y Objetivos 1.2. Algunas Notassobre 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 yPrueba 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 Ω y Θ 4.5.5. Propiedades y Cotas más Usuales 4.6. Ecuaciones de Recurrencias 4.6.1. Introducción 4.6.2. Resolución de Recurrecias 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
4.6.3. Método del TeoremaMaestro 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....
Leer documento completo
Regístrate para leer el documento completo.