Análisis de Algoritmos para Ingeniería de Sistemas y Computación PDF

Preview

Summary

Análisis de Algoritmos para Ingeniería de Sistemas y Computación Sergio Augusto Cardona Torres Adscrito al Programa de Ingeniería de Sistemas y Computación Facultad de Ingeniería Universidad del Quindío Sonia Jaramillo Valbuena Adscrita al Programa de Ingeniería de Sistemas y Computación Facultad de...

Description

Accelerat ing t he world's research.

Análisis de Algoritmos para Ingeniería de Sistemas y Computación Miguel Cañas

Related papers Est ruct ura de dat os en java Joyanes 1ed David Miguel Cruz Garcia Est ruct ura de dat os en java Kaneki Sanchez Compart ido por Dey Ort igoza

Download a PDF Pack of t he best relat ed papers 

Análisis de Algoritmos para Ingeniería de Sistemas y Computación

Sergio Augusto Cardona Torres

Adscrito al Programa de Ingeniería de Sistemas y Computación Facultad de Ingeniería Universidad del Quindío

Sonia Jaramillo Valbuena

Adscrita al Programa de Ingeniería de Sistemas y Computación Facultad de Ingeniería Universidad del Quindío

Jorge Iván Triviño Arbeláez

Adscrito al Programa de Ingeniería de Sistemas y Computación Facultad de Ingeniería Universidad del Quindío

1

Análisis de Algoritmos para Ingeniería de Sistemas y Computación

No está permitida importar, vender, difundir, distribuir y exportar total o parcialmente esta obra, ni su tratamiento o transmisión por cualquier método sin autorización escrita del editor. El contenido de la presente obra es exclusivo de los autores

Derechos reservados Diciembre de 2011 ISBN: 978-958-99930-2-6

ELIZCOM S.A.S www.elizcom.com [email protected] NIT 90004331-7 Armenia, Quindío – Colombia Tel. 7493244 Cel: 57+3113349748 Java™ y todas las marcas y logos basados en Java™ son marcas comerciales o marcas registradas de ORACLE Sun, La marca de Eclipse y sus logotipos aparecen de acuerdo con las condiciones legales de Eclipse, expuestas en http://www.eclipse.org/legal/main.html Microsoft Office y su logotipo es una marca registrada por Microsoft Corporation. CMAP – Tools son marca registrada por ihmc - Florida institute for Human & Machine Cognition

2

ANÁLISIS DE ALGORITMOS PARA INGENIERÍA DE SISTEMAS Y COMPUTACIÓN 1

ANÁLISIS DE ALGORITMOS .............................................................................. 9 1.1 Introducción .................................................................................................... 9 1.2 Definición de Algoritmo ................................................................................. 9 1.3 Características de los Algoritmos ................................................................ 15 1.4 Buenos hábitos de diseño de Algoritmos .................................................... 16 1.5 Fases de desarrollo de un programa ........................................................... 17 1.6 Tiempo de Ejecución de los Algoritmos ..................................................... 18 1.6.1 Análisis de Algoritmos Iterativos ............................................................... 19 1.6.2 Tiempo de ejecución para instrucciones simples ....................................... 19 1.6.3 Tiempo de ejecución para ciclos simples ................................................... 20 1.6.4 Tiempo de ejecución para ciclos anidados ................................................. 24 1.6.5 Tiempo de ejecución con llamada a métodos ............................................. 30 1.7 Caso de estudio: Biblioteca .......................................................................... 34 1.8 Comparación de tiempos de ejecución ....................................................... 39 1.9 Actividad Independiente: Agenda Telefónica ............................................ 43 1.10 Complejidad Computacional ....................................................................... 48 1.10.1 Notación Asintótica ................................................................................ 49 1.10.2 Notación Big Oh O. ................................................................................ 49 1.10.3 Notación Omega Ω ................................................................................. 51 1.10.4 Notación .............................................................................................. 51 1.10.5 Regla del Límite ..................................................................................... 52 1.10.6 Ordenes de Complejidad ........................................................................ 54 1.11 Actividad Independiente: Concurso Docente ............................................ 62 1.12 Análisis de Algoritmos Recursivos .............................................................. 68 1.12.1 Algoritmos Recursivos ........................................................................... 69 1.12.2 Tiempo de ejecución de algoritmos recursivos ...................................... 73 1.12.3 Resolución de Recurrencias por inducción ............................................ 78 1.12.4 Resolución de Recurrencias por sustitución ........................................... 82 1.13 Análisis de Métodos de Ordenamiento ....................................................... 85 1.13.1 Método de Ordenamiento ShakerSort .................................................... 86 1.13.2 Método de Ordenamiento Burbuja ......................................................... 87 1.13.3 Método de Ordenamiento por Selección ................................................ 87 1.13.4 Método de Ordenamiento Inserción ....................................................... 88 1.13.5 Método de Ordenamiento QuickSort. ..................................................... 89 1.13.6 Método de Ordenamiento ShellSort. ...................................................... 91 1.13.7 Método de Ordenamiento StoogeSort .................................................... 93 1.14 Métodos de Búsqueda................................................................................... 93 1.14.1 Búsqueda Lineal Iterativa ....................................................................... 94 1.14.2 Búsqueda Lineal Limitada ...................................................................... 95 1.14.3 Búsqueda Lineal Iterativa con extremos ................................................ 96 1.14.4 Búsqueda Binaria.................................................................................... 97 1.15 Caso de Estudio: Registro de notas ............................................................. 98

2

ESTRATEGIAS DE PROGRAMACIÓN ........................................................... 107 2.1 Introducción ................................................................................................ 107

3

2.2 Algoritmos Divide y Vencerás ................................................................... 107 2.2.1 Búsqueda Binaria...................................................................................... 107 2.2.2 Ordenamiento por el método MergeSort .................................................. 108 2.2.3 Multiplicación de Números Grandes ........................................................ 110 2.3 Algoritmos Devoradores ............................................................................ 114 2.3.1 El Problema de la mochila ........................................................................ 115 2.3.2 Elementos de los Algoritmos Voraces...................................................... 120 2.3.3 El problema de la Devuelta. ..................................................................... 121 2.4 Actividad Independiente: El problema de la Devuelta ........................... 123 2.5 Programación Dinámica ............................................................................ 126 2.5.1 Serie de Fibonacci .................................................................................... 126 2.5.2 Problema de la Mochila ............................................................................ 130 2.5.3 Problema de la Devuelta ........................................................................... 132 2.5.4 Algoritmo de Dijkstra ............................................................................... 134 2.5.5 Hoja de trabajo: Lotería ............................................................................ 135 3

ALGORITMOS APLICADOS A GRAFOS Y ARBOLES ................................. 141 3.1 Introducción ................................................................................................ 141 3.2 Arboles Binarios ......................................................................................... 141 3.2.1 Árboles Binarios de Expresión ................................................................. 143 3.2.2 Implementación de Arboles Binarios ....................................................... 146 3.2.3 Recorridos en Arboles Binarios ................................................................ 153 3.3 Caso de estudio: Agenda Telefónica ......................................................... 155 3.4 Hoja de trabajo: Graficador de árboles ................................................... 158 3.5 Grafos .......................................................................................................... 166 3.5.1 Conceptos fundamentales de los Grafos ................................................... 166 3.5.2 Grafos Dirigidos ....................................................................................... 166 3.5.3 Grafos No Dirigidos ................................................................................. 167 3.6 Arboles de Recubrimiento Mínimo ........................................................... 168 3.6.1 Algoritmo de Prim .................................................................................... 168 3.6.2 Algoritmo de Kruskal ............................................................................... 169 3.6.3 Algoritmo de Dijkstra ............................................................................... 170 3.7 Arboles n-arios ............................................................................................ 174 3.8 Actividad Independiente: Organigrama de empresa .............................. 177 3.9 Arboles AVL ............................................................................................... 178 3.9.1 Elementos de los Árboles AVL ................................................................ 178 3.9.2 Operaciones de los Árboles AVL ............................................................. 179 3.10 Caso de estudio Grupo de estudiantes ...................................................... 184 3.11 Backtracking ............................................................................................... 193 3.12 Caso de estudio: Reinas.............................................................................. 194 3.13 Actividad Independiente: Laberinto......................................................... 197

4

ANÁLISIS DE ESTRUCTURAS DE DATOS ................................................... 201 4.1 Introducción ................................................................................................ 201 4.2 Estructura de Datos Lista .......................................................................... 201 4.2.1 Lista Sencillamente Enlazada – Implementación 1. ................................. 201 4.2.2 Lista Sencillamente Enlazada – Implementación 2. ................................. 204 4.2.3 Lista Sencilla Circular .............................................................................. 209 4.2.4 Lista Doblemente Enlazada ...................................................................... 213

4

4.2.5 Lista Circular Doblemente Enlazada ........................................................ 217 4.3 Actividad Independiente: Ciudades .......................................................... 221 4.4 Estructura de Datos Pila ............................................................................ 224 4.4.1 Implementación Basada en un arreglo ..................................................... 224 4.4.2 Implementación utilizando Listas ............................................................. 227 4.5 Estructura de Datos Cola ........................................................................... 228 4.5.1 Implementación Basada en un arreglo ..................................................... 229 4.5.2 Implementación utilizando Listas ............................................................. 232 4.6 Estructura ArrayList ................................................................................. 233 4.7 Caso de estudio – Universidad................................................................... 234 5

OPTIMIZACIÓN, PRUEBAS Y LÍMITES DE LA LÓGICA ........................... 241 5.1 Introducción ................................................................................................ 241 5.2 Técnicas de Optimización .......................................................................... 241 5.2.1 Desenvolvimiento de ciclos ...................................................................... 241 5.2.2 Reducción de Esfuerzo ............................................................................. 243 5.2.3 Tipos de Variables .................................................................................... 244 5.2.4 Fusión de ciclos ........................................................................................ 245 5.2.5 Expresiones redundantes .......................................................................... 246 5.2.6 Folding ...................................................................................................... 247 5.3 El diseño por contrato ................................................................................ 249 5.4 Pruebas con JUnit ....................................................................................... 252 5.5 Límites de la Lógica .................................................................................... 256 5.5.1 Clase P ...................................................................................................... 256 5.5.2 Clase NP ................................................................................................... 256

6

BIBLIOGRAFÍA ................................................................................................. 257

5

PRESENTACIÓN El Análisis de Algoritmos se considera como una temática fundamental dentro del proceso de formación de los estudiantes de Ingeniería de Sistemas y Computación, pues posee una estrecha relación con otras áreas de formación del ingeniero, como lo son la programación de computadores, las estructuras de datos, las Matemáticas Discretas y la teoría de grafos entre otras. Las orientaciones sociológicas y pedagógicas que permitieron la elaboración de este libro y su viabilidad en el campo profesional y teórico, están orientadas a fortalecer el objetivo o propósito general de formación del Ingeniero de Sistemas y Computación. Desde la perspectiva sociológica, quienes comparten los conceptos del análisis de algoritmos, son capaces de emplearlo para: comprender, explicar, demostrar, solucionar problemas, crear o hacer representaciones, orientados a compartir su significado con otras personas. Desde la perspectiva pedagógica, se pretenden establecer estrategias de enseñanza que faciliten a los estudiantes los aprendizajes requeridos en esta disciplina tanto en lo científico como en lo formal, cotidiano y viceversa. El presente libro pretende con su estrategia de enseñanza, la resolución de problemas usando el análisis de algoritmos. En éste, se agregan actividades que contribuyen a la mejor comprensión de los conceptos plasmados a lo largo de los capítulos. Al poseer una estructura coherente, el estudiante podrá trabajar a través de cada uno de ellos, convirtiéndose en un verdadero actor del proceso de aprendizaje, esto conlleva a que el rol del docente sufra una profunda transformación, se ha migrado hacia la idea de un consultor. Teniendo en cuenta que el análisis de algoritmos comprende una amplia variedad de temas, consideramos que es fundamental que los estudiantes identifiquen la importancia de esta disciplina dentro de su proceso de formación. Por un lado el libro recoge nuestra experiencia en la enseñanza de las asignaturas relacionadas con la algoritmia y la programación, y nos ha permitido ver la importancia que tiene el disponer de una metodología de trabajo que permita abordar la resolución de los problemas de una forma simple, coherente y estructurada. Por otro lado este libro es una versión que retoma los conceptos fundamentales de los libros de análisis de algoritmos en java y Técnicas de Diseño de Algoritmos en java, en el cual, continua siendo un objetivo de los autores proporcionar una introducción comprensible y sólida de los elementos fundamentales del análisis de algoritmos. Teniendo en cuenta las observaciones y las oportunidades de mejora propuestas tanto por estudiantes como profesores que usaron estos libros, se realizaron cambios para este libro, con el objetivo de aportar al proceso de formación de los profesores. El libro se adaptó teniendo en cuenta el micro currículo vigente del curso análisis de algoritmos I. El texto fue escrito pensando principalmente en aquellos estudiantes de Ingeniería de Sistemas y afines que tienen los conocimientos fundamentales de las Matemáticas Discretas y Lógica de Programación y que deseen aprender los conceptos básicos a tener en cuenta en el análisis de algoritmos. Este libro se utilizará como referencia para la asignatura Análisis del Algoritmos I del programa de Ingeniería de Sistemas y Computación de la Universidad del Quindío. Este libro pretende ser flexible en la forma como puede impartirse a las personas interesadas. La comprensión de los temas, depende fundamentalmente de la preparación de los estudiantes. Se presentan conceptos básicos fundamentales e intermedios, los cuales se pueden aplicar en la práctica, así como también realizar un análisis riguroso de los conceptos teóricos que se imparten. El texto está orientado al estudiante, y hemos puesto el mayor empeño para explicar cada tema tan claramente como sea posible.

6

INTRODUCCIÓN El objetivo de este libro de texto consiste en mostrar los elementos fundamentales del análisis de algoritmos, estrategias de programación, el análisis de algoritmos aplicados a estructuras de datos, análisis de grafos y técnicas de optimización de código, los cuales son temas que tienen una serie de aplicaciones en diferentes áreas de las ciencias computacionales. Se pretende establecer una relación de aplicación entre los conceptos teóricos y su aplicación específica en el campo de la Ingeniería de Sistemas y Computación. El libro tiene los siguientes objetivos:   

  

Mostrar la importancia del análisis de algoritmos como área de fundamentación que aporta al proceso de formación de los estudiantes e ingeniería de sistemas y computación. Presentar a los estudiantes de ingeniería de sistemas y computación, los temas fundamentales de algoritmia y mostrar la relación existente entre los conceptos matemáticos con su aplicación en el contexto de las ciencias de la computación. Mostrar al estudiante las técnicas básicas utilizadas para establecer la complejidad computacional y la eficiencia en términos de tiempo de ejecución en algoritmos de diferente naturaleza, y en paralelo, formalizar la idea de “mayor eficiencia”, estableciendo el concepto de complejidad desde el punto de vista computacional. Presentar casos de estudio y hojas de trabajo. En este aspecto, todos los ejemplos se encuentran desarrollados en java, dado que es un lenguaje de programación de aceptación mundial tanto en ámbito industrial como en el ámbito académico. Desarrollar en el estudiante habilidades para la construcción de algoritmos recursivos correctos, algoritmos ordenamiento y algoritmos de búsqueda entre otros. Aplicar a casos de estudio, técnicas de solución de problemas computacionales complejos, considerados fundamentales en la formación del ingeniero de sistemas y computación.

Es de suponer que los lectores de este libro tienen los conocimientos básicos de algoritmia y está familiarizado con algún lenguaje de programación....