Análisis de Algoritmos Para Ingenieria de Sistemas y Comput

8/16/2019 Análisis de Algoritmos Para Ingenieria de Sistemas y Comput

1/258

1

Análisis de Algoritmospara Ingeniería de

Sistemas y Computación

Sergio Augusto Cardona Torres Adscrito al

Programa de Ingeniería de Sistemas y ComputaciónFacultad de Ingeniería

Universidad del Quindío

Sonia Jaramillo Valbuena Adscrita al

Programa de Ingeniería de Sistemas y ComputaciónFacultad de Ingeniería

Universidad del Quindío

Jorge Iván Triviño Arbeláez Adscrito al

Programa de Ingeniería de Sistemas y ComputaciónFacultad de IngenieríaUniversidad del Quindío


2/258

2

Análisis de Algoritmospara Ingeniería deSistemas y Computación

No está permitida importar, vender, difundir, distribuir y exportar total o parcialmenteesta obra, ni su tratamiento o transmisión por cualquier método sin autorización escritadel 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.Swww.elizcom.com

[email protected]

NIT 90004331-7Armenia, Quindío – Colombia

Tel. 7493244Cel: 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

http://www.elizcom.com/http://www.elizcom.com/


3/258

3

ANÁLISIS DE ALGORITMOS PARA INGENIERÍA DE SISTEMAS YCOMPUTACIÓN

1 ANÁLISIS DE ALGORI TMOS .............................................................................. 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


4/258

4

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


5/258

5

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 OPTIM IZACIÓN, PRUEBAS Y LÍM ITES 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 BIBL IOGRAFÍA ................................................................................................. 257


6/258

6

PRESENTACIÓN

El Análisis de Algoritmos se considera como una temática fundamental dentro del proceso deformació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 decomputadores, las estructuras de datos, las Matemáticas Discretas y la teoría de grafos entreotras.

Las orientaciones sociológicas y pedagógicas que permitieron la elaboración de este libro y suviabilidad en el campo profesional y teórico, están orientadas a fortalecer el objetivo o propósitogeneral de formación del Ingeniero de Sistemas y Computación. Desde la perspectivasociológica, quienes comparten los conceptos del análisis de algoritmos, son capaces deemplearlo para: comprender, explicar, demostrar, solucionar problemas, crear o hacerrepresentaciones, orientados a compartir su significado con otras personas. Desde laperspectiva pedagógica, se pretenden establecer estrategias de enseñanza que faciliten a losestudiantes los aprendizajes requeridos en esta disciplina tanto en lo científico como en loformal, cotidiano y viceversa.

El presente libro pretende con su estrategia de enseñanza, la resolución de problemas usandoel análisis de algoritmos. En éste, se agregan actividades que contribuyen a la mejorcomprensión de los conceptos plasmados a lo largo de los capítulos. Al poseer una estructuracoherente, el estudiante podrá trabajar a través de cada uno de ellos, convirtiéndose en unverdadero actor del proceso de aprendizaje, esto conlleva a que el rol del docente sufra unaprofunda transformación, se ha migrado hacia la idea de un consultor. Teniendo en cuenta queel análisis de algoritmos comprende una amplia variedad de temas, consideramos que esfundamental que los estudiantes identifiquen la importancia de esta disciplina dentro de suproceso de formación.

Por un lado el libro recoge nuestra experiencia en la enseñanza de las asignaturasrelacionadas 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 losproblemas de una forma simple, coherente y estructurada. Por otro lado este libro es unaversión que retoma los conceptos fundamentales de los libros de análisis de algoritmos en javay Técnicas de Diseño de Algoritmos en java, en el cual, continua siendo un objetivo de losautores proporcionar una introducción comprensible y sólida de los elementos fundamentalesdel análisis de algoritmos. Teniendo en cuenta las observaciones y las oportunidades demejora propuestas tanto por estudiantes como profesores que usaron estos libros, serealizaron cambios para este libro, con el objetivo de aportar al proceso de formación de losprofesores. El libro se adaptó teniendo en cuenta el micro currículo vigente del curso análisisde algoritmos I.

El texto fue escrito pensando principalmente en aquellos estudiantes de Ingeniería de Sistemasy afines que tienen los conocimientos fundamentales de las Matemáticas Discretas y Lógica deProgramación y que deseen aprender los conceptos básicos a tener en cuenta en el análisis dealgoritmos. Este libro se utilizará como referencia para la asignatura Análisis del Algoritmos Idel 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 losestudiantes. Se presentan conceptos básicos fundamentales e intermedios, los cuales sepueden aplicar en la práctica, así como también realizar un análisis riguroso de los conceptosteóricos que se imparten. El texto está orientado al estudiante, y hemos puesto el mayorempeño para explicar cada tema tan claramente como sea posible.


7/258

7

INTRODUCCIÓN

El objetivo de este libro de texto consiste en mostrar los elementos fundamentales del análisisde algoritmos, estrategias de programación, el análisis de algoritmos aplicados a estructuras dedatos, análisis de grafos y técnicas de optimización de código, los cuales son temas que tienenuna serie de aplicaciones en diferentes áreas de las ciencias computacionales. Se pretendeestablecer una relación de aplicación entre los conceptos teóricos y su aplicación específica enel 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 queaporta al proceso de formación de los estudiantes e ingeniería de sistemas ycomputació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 conceptosmatemá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 complejidadcomputacional y la eficiencia en términos de tiempo de ejecución en algoritmos dediferente 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 seencuentran desarrollados en java, dado que es un lenguaje de programación deaceptació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 computacionalescomplejos, considerados fundamentales en la formación del ingeniero de sistemas ycomputación.

Es de suponer que los lectores de este libro tienen los conocimientos básicos de algoritmia yestá familiarizado con algún lenguaje de programación. Los ejemplos serán implementados ensu totalidad en el lenguaje de programación java y se dará importancia únicamente a losaspectos más esenciales, sin sobrecargar al lector en temas que pueden ser objeto de estudioen otros libros relacionados con la programación y la algoritmia.

El libro está estructurado en 5 capítulos los cuales pretenden de forma progresiva mostrar

diferentes temas que son abordados de forma simple y estructurada, a continuación, semuestra un breve resumen de los temas que se presentan en el mismo.

En el primer capítulo denominado análisis de algoritmos, se analiza el tiempo de ejecución delos algoritmos y presentamos su forma de calcularlo. Se muestra una amplia variedad deejemplos los cuales permitirán al estudiante conocer y entender los diferentes tiempos deejecución que se pueden obtener de los algoritmos. Adicionalmente se trabajarán temas comoel tiempo de ejecución de los algoritmos iterativos, la complejidad computacional y notacionesasintóticas, el análisis de algoritmos recursivos, de los métodos de ordenamiento y losalgoritmos de búsqueda.

En el segundo capítulo llamado estrategias de programación, se trabajará con algoritmos quese emplean en problemas de optimización en los cuales se pretende maximizar o minimizar

algún valor. Se mostrarán casos considerados típicos como el problema de la mochila, el


8/258

8

problema de la devuelta; en los cuales es posible el uso de algoritmos divide y vencerás,algoritmos devoradores o ávidos y algoritmos que aplican programación dinámica.

El capítulo tercero denominado algoritmos aplicados a grafos y árboles, se muestra el análisisde los algoritmos más comunes aplicados a las estructuras de datos no lineales. Se analizan

los órdenes de complejidad de los métodos de implementación de grafos y arboles másimportantes. Se explicarán las operaciones fundamentales aplicadas a los árboles y finalmentese analizan conceptos de árbol n-ário, árbol AVL y la técnica de backtraking.

El capítulo cuarto muestra los algoritmos aplicados a estructuras de datos, se analiza laimplementación de las estructuras de datos lineales con su respectivo análisis de orden decomplejidad. Se explicarán los órdenes de complejidad de los métodos más importantes paralas listas, pilas y colas. Adicionalmente se muestra un caso de estudio que usa estructuraspredefinidas del lenguaje de programación conocidas como ArrayList.

En el último capítulo del libro se muestra la optimización y pruebas de algoritmos, se analizanalgunas técnicas que se pueden aplicar para la optimización de código. Algunas de las técnicasque se trataran son el desenvolvimiento de ciclos, la fusión de ciclos, la eliminación de

expresiones redundantes, entre otras. También se muestra algunas herramientasproporcionadas por el lenguaje de programación que permiten la realización de pruebas decorrección las cuales buscan una mejor calidad en el código de programación y en sufuncionalidad. Adicionalmente, se muestran los conceptos asociados a los límites de la lógica yde la complejidad computacional, se muestra el planteamiento de problemas asociados aalgoritmos que conforman la clase P, así mismo se muestran casos en los cuales seconsideran problemas intratables denominados clases NP.


9/258


10/258

10

Existen diferentes tipos de algoritmos, entre los cuales tenemos:

Algoritmos Determinísticos: Es un algoritmo en el cual, cada uno de sus pasos estánclaramente definidos, y para cada conjunto de entrada es posible predecir una salidaexacta.

Algoritmos No Determinísticos: Es un algoritmo en el cual, para un mismo conjuntode datos de entrada, se pueden obtener diferentes salidas. No se puede previa a laejecución de estos algoritmos, afirmar cuál será su resultado.

Algoritmos Adaptativos: Son algoritmos con alguna capacidad de aprendizaje. Porejemplo, los sistemas basados en conocimientos, las redes neuronales entre otras.

En la literatura asociada al tema se encuentra una cantidad muy amplia de tipos de algoritmosentre los cuales adicionalmente se pueden citar los algoritmos paralelos, probabilísticos,voraces, divide y vencerás, dinámicos. Estos tres últimos se tratarán en capítulos posterioresdel libro.

La implementación de un algoritmo debe ser en todos los casos:

Correcta: Si para toda instancia del conjunto de entrada se obtiene la salida esperada,es decir, que cumpla con el objetivo para el cual está pensado.

Eficiente: Debe ser rápido y usar la menor cantidad de recursos. Es una relación entrelos recursos consumidos, fundamentalmente tiempo y memoria versus los productosobtenidos.

Por lo tanto, un algoritmo se considera bueno si considera los siguientes elementos.

Si los anteriores elementos resueltos de forma positiva dan noción de lo que es un buenalgoritmo. Por lo tanto se pueden generar las siguientes frases que se convertirán en preguntascuando estemos analizando cada uno de nuestros programas.

Que cumpla con el objetivo para el cual está pensado. Que resuelva el problema en el menor tiempo posible. Que haga uso adecuado de los recursos. Que permita identificar posibles errores. Que sea fácil de modificar para añadir funcionalidad

Para aproximar mejor los elementos anteriores, observemos el siguiente ejemplo: se deseadeterminar si un número entero positivo predeterminado es primo o no lo es. El conjunto de losnúmeros primos es un subconjunto de los números naturales que contiene aquellos que sondivisibles por sí mismos y por la unidad.Son entre otros números primos: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43. Acontinuación se muestra una implementación del método que resuelve el problema en

mención.


11/258

11

Implementacióndel Método

public boolean esPrimo(int numero){

int resultado = 0;int i = 2;

while( i < numero ){if ( numero % i == 0 ){

resultado = 1;}i = i + 1;

}if ( resultado == 0 ){

return true;}else{

return false;}

}

Considerando los anteriores interrogantes, es posible responder para este caso:

¿Cumple el algoritmo el objetivo para el cual está pensado? Solo en el caso en cual seingresa un número entero positivo, el algoritmo genera una salida correcta y cumpliríacon su objetivo.

¿El algoritmo resuelve el problema en el menor tiempo posible? No es posible resolverel interrogante, para poder responder, se debe comparar con la eficiencia de otrosalgoritmos que resuelven el mismo problema.

¿El algoritmo hace uso adecuado de los recursos? Si, dado que se usan las variablesestrictamente necesarias para la solución y se utiliza un tipo de dato con rango devalores moderado.

¿Permite el algoritmo identificar posibles errores? No, dado que el programa no manejaexcepciones que controlen posibles errores.

¿El algoritmo es fácil de modificar para añadir funcionalidad? Si, dada la sencillez delproblema y de la solución propuesta.

Una segunda solución para determinar si el número es primo, se muestra a continuación:


public boolean esPrimo(int numero){

int i;for ( i = 2 ; i numero / 2 ){

return true;

}


12/258

12

else{

return false;}

}

Para esta implementación es posible dar respuesta a los siguientes interrogantes:

¿Cumple el algoritmo el objetivo para el cual está pensado? Solo, en el caso en el quese ingrese un número entero positivo, el algoritmo genera una salida correcta.

¿Resuelve el algoritmo el problema en el menor tiempo posible? Si se compara con elalgoritmo anterior, este algoritmo es mejor dado que una vez que encuentra un númerodivisible, termina la ejecución y muestra el mensaje al usuario, teniendo en cuenta lacondición if.

¿Hace el algoritmo uso adecuado de los recursos? Si, pues para algunos casos noitera toda la cantidad de veces permitida por el ciclo.

¿El algoritmo permite identificar posibles errores? No, dado que el programa no manejaexcepciones que controlen posibles errores.

¿El algoritmo es fácil de modificar para añadir funcionalidad? Si, dada la sencillez delproblema y de la solución propuesta.

ACTIVIDAD

A continuación se muestra la implementación de un método el cual lee un número enteropositivo y retorna la cantidad de dígitos que este tiene.


public int calcularCifras (int num){

int aux = 0, con = 0;if(num==0){

return 1;}for(int i=10;num!=0;i+=10){

con = con + 1;num = num/i;i = i-10;

}if(con!=0){

aux = con;}return aux;

}

Para la anterior implementación, resuelva los siguientes interrogantes:

Pregunta Respuesta¿Cumple el algoritmo el objetivopara el cual está pensado?


13/258

13

¿Resuelve el algoritmo el problemaen el menor tiempo posible?¿Hace el algoritmo uso adecuadode los recursos?¿El algoritmo permite identificar

posibles errores?¿El algoritmo es fácil de modificarpara añadir funcionalidad?

A continuación se muestra otra implementación de un método el cual lee un número enteropositivo y retorna la cantidad de dígitos que este tiene.


public int calcularCifras (int numero){

int acum = 0;if(numero=10 && numero10; i-=10){

numero= numero/10;acum++;if(numero == 0){

break;}

}return acum;

}}


Pregunta Respuesta¿Cumple el algoritmo el objetivopara el cual está pensado?¿Resuelve el algoritmo el problema

en el menor tiempo posible?¿Hace el algoritmo uso adecuadode los recursos?¿El algoritmo permite identificarposibles errores?¿El algoritmo es fácil de modificarpara añadir funcionalidad?

ACTIVIDAD

Entre las varias sucesiones interesantes de números que existen en las matemáticas discretasy combinatorias, están los números armónicos, los cuales tienen la forma:


14/258

14

H 1 + H 2 + H 3 +… donde:

Y en general,

para cualquier (Grimaldi, 1998)

La sucesión de los números armónicos se puede definir como:


public int armonico (int numero){

}

Con bases en la implementación propuesta, responda los siguientes interrogantes.

Pregunta Respuesta¿Cumple el algoritmo el objetivopara el cual está pensado?¿Resuelve el algoritmo el problemaen el menor tiempo posible?¿El algoritmo permite identificarposibles errores?

Realice una comparación entre el método que usted implementó, con el siguiente método yposteriormente responda la pregunta:


public int armonico(int numero){

double aux, result = 1;for(int i=2; i


15/258

15

1.3 Características de los Algoritmos

Cuando que se desarrolla una solución a un problema desde la perspectiva algorítmica, sedebe procurar en la medida de lo posible que los algoritmos cumplan las siguientescaracterísticas:

Preciso: Un algoritmo preciso, posee un orden específico en cada uno de los pasosque este ejecuta. Por esta razón cuando se ejecuta un paso del algoritmo, se conocecon certeza cuál es el paso siguiente a ejecutar.

Finito: El algoritmo debe finalizar tras una secuencia o número finito de pasos. Efectivo: La eficiencia hace alusión al logro de la solución a un problema de la mejor

manera posible (en términos de tiempo). En el ambiente computacional, lo son el buenuso de los recursos de hardware.

Determine si la siguiente implementación del método, cumple con las características de losalgoritmos definidas anteriormente.


public int calcularCifras (int numero){

int acum = 0;if(numero=10 && numero10; i-=10){

numero= numero/10;acum++;if(numero == 0){

break;}

}return acum;

}}


Pregunta RespuestaEs preciso el método?Es finito el método?Es efectivo el método?

Para finalizar esta sección cabe mencionar que dentro de la Ingeniería de software, también secontemplan factores fundamentales en la calidad del software, entre los cuales tenemos:

Eficiencia: Atributo que determina el buen aprovechamiento de los recursos queutiliza.

Facilidad de uso: Facilidad para que el usuario interactué con el programa.


16/258

16

Compatibilidad: Facilidad para que un programa pueda usarse en unión con otrosprogramas.

Extensibilidad: Es la capacidad que tiene un programa de ampliar la funcionalidad deacuerdo a nuevas necesidades o requerimientos.

Verificabilidad: Es la capacidad que tiene un programa para soportar casos de prueba

y para identificar posibles errores. Exactitud: Es el atributo que determina el nivel de precisión de los resultados

obtenidos por un programa.

1.4 Buenos hábitos de diseño de Algoritmos

Al diseñar un algoritmo y posteriormente implementarlo en un lenguaje de programación, sedeben tener en cuenta buenos hábitos y técnicas de diseño. A continuación se especificanalgunos aspectos a considerar por los equipos de desarrollo de software y por losdesarrolladores de software al momento de diseñar e implementar algoritmos (Ramirez, 2003).

Analizar el problema: La correcta resolución de un problema viene determinada engran medida por el planteamiento inicial. Un planteamiento correcto evitará perdertiempo en la implementación de los algoritmos.

Evaluar posibles soluciones: Es necesario conocer los recursos algorítmicosdisponibles y las distintas metodologías de diseño para plantear la solución adecuada.Una vez hecho esto, deberá optar por la mejor de ellas para su posteriorimplementación.

Diseñar la solución: Esta actividad se refiere a un modelamiento de lo que será lasolución definitiva. Bajo el paradigma orientado a objetos, es posible especificar la jerarquía de clases con una descripción completa del diagrama de clases. También serecomienda al diseñar la solución, modelar diagramas de secuencia, los cuales

permiten visualizar la interacción de los objetos por medio del envío de mensajes.

Documentar el código: Con frecuencia los algoritmos adolecen de documentación yen algunos casos esta es inexistente. Este tipo de situaciones perjudican elmantenimiento y reutilización de los mismos, y dificultan su entendimiento. Loscomentarios propiamente dichos son pequeños fragmentos de tipo explicativo,aclaratorio o de advertencia que se intercalan entre las instrucciones del programa.

Cada programador debe aprender a escribir la especificación de su programa (o sea, ladocumentación), antes de escribir el programa (Di Mare, 1998). Documentar permiteentender el programa a medida que crece y también, identificar posibles fuentes deerror. Javadoc es una herramienta creada para tal fin. Está pensado para lograr que laarquitectura de la solución sea mucho más comprensible, es decir, su formato comúnhace que los comentarios escritos sean más comprensibles por otro programador.

Una adecuada documentación requiere agregar comentarios a todas las clases ymétodos que componen el programa. Un comentario debe contener la informaciónsuficiente para que otras personas puedan entender lo que se ha realizado y el porquéde lo que se ha realizado.

Manejo de versiones: Es necesario el uso de herramientas que permitan el control deversiones. Teniendo en cuenta el carácter evolutivo y progresivo de los proyectos dedesarrollo de software.

Estándar de programación: Es recomendable establecer un lineamiento particular enla forma en la cual se construyen los programas. Se deben estandarizar por ejemplo


17/258

17

los nombres de variables, de las clases y de los métodos, todos estos deben estaracordes a las tareas que realizan.

Existen estándares para usar convenciones de programación. Las convenciones decódigo son importantes para los programadores por un gran número de razones

(Molpeceres, 2001) :

o El 80% del coste del código de un programa va a su mantenimiento.o Casi ningún software lo mantiene toda su vida el auto original.o Las convenciones de código mejoran la lectura del software, permitiendo

entender código nuevo mucho más rápidamente y más a fondo.o Si distribuyes tu código fuente como un producto, necesitas asegurarte de que

está bien hecho y presentado como cualquier otro producto.

Para conocer las convenciones de código definidas por el proveedor oficial de java serecomienda visitar el site (octubre de 2011), el cual contiene los elementos bases parael uso de estándares: http://www.oracle.com/technetwork/java/codeconv-138413.html

1.5 Fases de desarrollo de un programa

Dentro del entorno de la informática no siempre los problemas – necesidades de las personaso las organizaciones, se encuentran claramente definidas, es necesario en muchas ocasionesrealizar una clara formulación del problema. Solo partiendo de una correcta formulación deeste, será posible especificar una metodología para su solución.

Según (Cardona, Jaramillo, & Carmona, Análisis de Algoritmos en Java, 2007), una buenaplanificación de las tareas a realizar para desarrollar un programa favorece el éxito en laimplementación. La planificación debe estar basada en el establecimiento de fases. Las fases,tanto para realizar programas sencillos como para llevar a cabo proyectos de envergadura deconstrucción de aplicaciones informáticas se pueden ver en la figura.

La etapa de definición del problema, se enfoca en el entendimiento del espacio delproblema, se identifican las posibles necesidades y restricciones sobre la solución delproblema. Al culminar esta actividad, se debe tener un completo entendimiento del

problema a solucionar.

Una vez definido el problema, se realiza la especificación del problema, por medio delos que se conoce como diseño detallado o algorítmico, en donde se definen ydocumentan los detalles y algoritmos de cada una de las funciones

Con base en el diseño, se construyen los algoritmos necesarios para la solución delproblema, para posteriormente estos se implementados en un lenguaje deprogramación. Cada algoritmo implementado, debe ser verificado para comprobar lasoperaciones para las cuales fue construido, estos se deben someter a un conjunto depruebas.

Finalmente se tiene una aplicación de software, que debe dar la solución esperada de

acuerdo a los requerimientos planteados inicialmente.


18/258

18

1.6 Tiempo de Ejecución de los Algoritmos

Cuando se aborda la solución de un problema computacional se tiene la disyuntiva deseleccionar entre varios algoritmos y la cual se realiza basándose fundamentalmente en lossiguientes aspectos: el algoritmo fácil de entender, codificar, depurar versus el algoritmo que se

ejecute con la mayor rapidez posible, siempre con el objetivo de hacer un uso eficiente de losrecursos de la máquina. Lograr uno de estos objetivos generalmente implica entrar encontradicción con el cumplimiento del otro, por ello se debe valorar los casos en que se debepriorizar, el uno o el otro.

Para calcular el tiempo de ejecución, se deben apropiar dos conceptos que fundamentan elanálisis de algoritmos, estos conceptos algorítmicos se conocen como el mejor y el peor caso.

El peor caso se considera como la situación en la cual el algoritmo consume mayorcantidad de tiempo o mayor cantidad de instrucciones para resolver un problema.

El mejor caso está relacionado con la situación en la cual el algoritmo consume menorcantidad de tiempo o menor cantidad de instrucciones para resolver un problema.

Para este libro, tendremos en cuenta el análisis para el peor de los casos.

Tradicionalmente se usan estrategias para la estimación de los tiempos de ejecución, elsiguiente mapa conceptual nos muestra los elementos fundamentales:

Más formalmente las siguientes técnicas se utilizan para estimar el tiempo de ejecución de unprograma (Aho & Ullman, 1995):

La técnica de benchmarking consiste en comparar dos o más algoritmos con un mismoconjunto de datos de entrada, se establece cual es el que resuelve el problema deforma más eficiente; es decir, cual consumió menos tiempo al ejecutarse. Es necesarioque el hardware sobre el cual se realiza la prueba a los algoritmos tenga las mismascaracterísticas.

La técnica de Profiling consiste en asociar a cada instrucción de un programa unnúmero que representa la fracción del tiempo total tomada para ejecutar esainstrucción particular. Una de las técnicas más conocidas (e informal) es la Regla 90-10, que afirma que el 90 % del tiempo de ejecución, se invierte en el 10 % del código


19/258

19

(Valenzuela, 2003). De acuerdo a lo anterior, un programa pasa la mayor parte deltiempo de la ejecución en un trozo de código pequeño. Este 90 % del código sueleestar constituido por ciclos.

La técnica de análisis considera aspectos más rigurosos para la estimación del tiempo

de ejecución. Su objetivo es analizar de forma matemática y detallada cada uno de lospasos que ejecuta el algoritmo. Consiste en asignar a cada una de las instrucciones uncosto en consumo de tiempo, sumar cada uno de estos y establecer la función deconsumo de tiempo. Esta técnica utiliza una función T(n), la cual representa el númerode unidades de tiempo que consume el algoritmo para cualquier entrada de tamaño n.Por lo anterior, T(n) es el tiempo de ejecución del algoritmo. El tiempo de ejecución enla función T(n) no se le está asignando ninguna unidad de medida del tiempo, lo que seestá haciendo es calculando el monto de instrucciones que el algoritmo ejecutará, dadoel tamaño del conjunto de datos de entrada

1.6.1 Análisis de Algoritmos Iterativos

Después de realizar un estudio sobre las diversas técnicas para el análisis de algoritmos, seutilizará la técnica de análisis. Esta técnica permitirá que la estimación, se realizará en funcióndel número de operaciones elementales que realiza dicho algoritmo para un tamaño de entradadado.

Entendiendo por operaciones elementales como aquellas operaciones cuyo tiempo deejecución se puede acotar superiormente por una constante (Guerequeta & Vallecillo, 2000). Así, se consideran como operaciones elementales:

Nombre Operadores o instruccionesOperaciones aritméticas básicas +,-,*,/,% Asignaciones a variables =

Comparaciones lógicas o relacionales &&,||,


20/258

20

EjemploObjetivo: Comprender la estimación del tiempo de ejecución paramétodos que tienen operaciones elementales.

Método

public int metodo1( int n ){

int x,y,z;x = 2;y = x++;z = y + x;return z;

}

Análisis deltiempo deejecución

El tiempo de ejecución de una secuencia consecutiva deinstrucciones se calcula sumando cada línea de código que poseeel método, independiente de la cantidad de operaciones que seejecuten en la línea. Adicinalmente se debe considerar el parámetroque llega al método el cual se cuenta como una instrucción.

int n, se ejecuta 1 vez

x = 2, se ejecuta 1 vezy = x++, se ejecuta 1 vezz = y + x, se ejecuta 1 vezreturn z, se ejecuta 1 vez

T(n) T(n) = 5

ACTIVIDAD

Estime y argumente el cálculo del tiempo de ejecución para el siguiente método:

Ejercicio Objetivo: Estimar el tiempo de ejecución del método.

Método

public int ejercicio( int x, int y, int z ){

int r;r = 0;x += 2;y = x + 3;z = x + 2;r = x + y + z;return r

} Explicación del

tiempo deejecución

T(n)

1.6.3 Tiempo de ejecución para ciclos simples

Muchos de los problemas que se resuelven a nivel de programación, están relacionados con eluso de ciclos. A continuación, se muestran una serie de ejemplos que permitirán establecer eltiempo de ejecución para métodos que poseen ciclos en su implementación. Para cada uno de

los métodos se considerará el peor caso.


21/258

21

EjemploObjetivo: Crear habilidad para calcular el tiempo de ejecución deun método cuando este tiene ciclos.

Método

public void metodo ( int n)

{int i, x, y;i = 0;while ( i < n ){

x = i + 3;y = x + 1;i++;

}}

Análisis delTiempo deejecución

int n Se ejecuta 1 vezi = 0 Se ejecuta 1 vezwhile ( i < n ) Se ejecuta n + 1 vecesx = i + 3 Se ejecuta n vecesy = x + 1 Se ejecuta n vecesi = i + 1 Se ejecuta n veces

La instrucción while(i < n) se repite n+1 veces, esto teniendoen cuenta la última comparación del ciclo. Las instrucciones quehay dentro del ciclo, se repiten n veces.

T(n) T(n) = 4n+3.

A continuación se muestra otro ejemplo en el cual se estima el tiempo de ejecución del método.El método recibe tres parámetros por valor, lo que implica que cada uno de esos valores se

ejecuta una vez.

EjemploObjetivo: Crear habilidad para calcular el tiempo de ejecución delmétodo.

Método

public void metodo ( int x, int y, int n ){

for ( int i = 3 ; i


22/258

22

EjemploObjetivo: Crear habilidad para calcular el tiempo de ejecución delmétodo cuando se utilizan condicionales.

Método

public void metodo( int n, int arreglo[] ){

int temp;for ( int i = 0 ; i


23/258

23


El else tiene en su bloque más cantidad de líneas de código. Porlo tanto el peor de los casos, es que la condición if al momento desu evaluación sea falsa y el flujo del programa continué en el else.

T(n) T(n)= 6n-7, para n>1.

ACTIVIDAD

Estime y argumente el cálculo del tiempo de ejecución para los siguientes métodos:

Ejercicio Objetivo: Estimar el tiempo de ejecución del método.

Método

public void metodo( int n, int a[] ){

int temp, x, i;

i = 0;while(i


24/258

24


T(n)

Estimar el tiempo de ejecución del siguiente método, analizando el caso en el cual elcondicional if (w % i == 1) es verdadero en la última iteración.

EjercicioObjetivo: Conocer cómo se calcula el tiempo de ejecución cuandoun ciclo tiene una instrucción de salto.

Método

public void ejercicio ( int n, int a[], int x ){

int j = 0;for ( int i = 0 ; i < n ; i++ ){

if ( x % i == 0){

a[i] = i * 2;j++;break;

}a[i] = 5;a[j] = i * 2;x--;}

} Análisis delTiempo deejecución

T(n)

1.6.4 Tiempo de ejecución para ciclos anidados

El uso de los ciclos anidados es una práctica muy frecuente y necesaria para laimplementación de diferentes tipos de algoritmos. A continuación vamos a estimar el tiempo deejecución del método que posee dos ciclos anidados.

Es común cuando se tienen dos ciclos anidados que inician en un valor entero positivo e iteranhasta n (siendo n un entero positivo muy grande) o viceversa, encontramos que la función T(n)tiene un orden cuadrático. Para verificar el correcto cálculo del tiempo de ejecución, serecomienda asignar algún valor entero a la variable n y realizar un conteo de las instrucciones.

EjemploObjetivo: Crear habilidad para calcular el tiempo de ejecución delmétodo cuando se utilizan ciclos anidados.

Método

public void metodo ( int n, int a1[], int a2[] ){

for ( int i = 0 ; i < n; i++ ){

for ( int j = 0 ; j < n ; j++ ){

a1[ j ] = a2[ i ];}

}

}


25/258

25


Para la estimación del tiempo de ejecución, se comenzará con elanálisis del ciclo más interno, para nuestro caso lo llamaremosT1(n). T1(n) = 3n +2

El ciclo externo se ejecuta n veces por lo tanto multiplicaremos n

por el T1(n) y adicionaremos el tiempo de ejecución del cicloexterno. Utilizaremos un T(n) para indicar el tiempo de ejecucióntotal del algoritmo.

T(n)T(n) = ( ( 3n + 2 ) * n ) + 2n + 2 + 3T(n) = 3n2 + 4n +5

El método tiene tres ciclos anidados, cada uno de los cuales se analizará por separado paraposteriormente estimar el tiempo de ejecución total. Cada uno de los ciclos itera desde un valorpequeño hasta n, por lo que el orden de la función de tiempo de ejecución debería ser cúbico.

Ejemplo

Objetivo: Crear habilidad para calcular el tiempo de ejecución de

un método cuando este utiliza ciclos anidados.

Método

public void metodo( int n ){

int x = 0;for ( int i = 0 ; i < n ; i++ ){

for ( int j = 0 ; j < n; j++ ){

for ( int k = 0 ; k < n ; k++ ){

x++;}

}}

}

Tiempo deejecución

Se analiza el ciclo más interno, a éste lo llamaremos T1(n). T1(n)= 3n + 2

A continuación, se analiza ciclo del medio, lo llamaremos T2(n). T2(n) = 2n+2

Se calcula el tiempo de ejecución de los dos ciclos más internos, alcual llamaremos T3(n).

T3(n)= ((3n+2)*n) + 2n+2= 3n2+4n+2

T(n)Finalmente me estima el tiempo de ejecución total del método

T(n) = ((3n2+4n+2)*n) + 2n+2+2= 3n3+4n2+4n+4

ACTIVIDAD

Estime y argumente el cálculo del tiempo de ejecución para el siguiente método:


26/258

26

EjercicioObjetivo: Crear habilidad en el cálculo de tiempo de ejecución paramétodos.

Método

public void ejercicio ( int n ){

int x, y, i, j;

i = 1;while ( i 0 ; j-- ){

temp = 4;resultado = 1;

}}

} Análisis delTiempo de

ejecución

T(n)

El siguiente cuadro, facilitará la forma para estimar la cantidad de veces que se repite un ciclo.En ella se puede observar cual es la cantidad de iteraciones, teniendo claramente establecido:

Límite inferior o superior del ciclo. Tope máximo o mínimo del ciclo. Incrementos o decrementos de la variable que controla las iteraciones.


27/258

27

Estructura del ciclo Cantidad de iteracionesfor (i=0; i < n; i++)for (i=0; i 0; i--)

for (i=n; i >=0; i--)for (i=n; i > k; i--)for (i=0; i < n; i+=k)for (i=j; i < n; i+=k)for (i=1; i < n; i*=2)for (i=n; i > 0; i/=2)

nn+1n-kn

n+1n-kn/k

(n-j)/klog2 (n)

log2 (n) + 1

A continuación se muestra un ejemplo que usa una estructura similar a la del ciclo for (i=n;i > 0; i/=2). Para el análisis de este algoritmo, debemos tener en cuenta el valor asignadoinicialmente a la variable i = 32, esta variable dentro del ciclo se va dividiendo cada vez por 2.Se puede afirmar entonces la cantidad de veces que itera el ciclo es: log2(n) + 1.

Ejemplo Objetivo: Crear habilidad en el cálculo de tiempo de ejecución paramétodos con tiempo de complejidad logarítmica.

Método

public void metodo ( ){

int temp = 0, x = 0, y = 1, i;i = 32;while( i > 0 ){

x++;temp++;y = y * 1;i = i / 2;

}}


temp = 0 Se ejecuta 1 vezx = 0 Se ejecuta 1 vezy = 1 Se ejecuta 1 vezi = 32 Se ejecuta 1 vezwhile(i > 0) Se ejecuta log2(i) + 2 vecesx++ Se ejecuta log2(i) + 1 vecestemp++ Se ejecuta log2(i) + 1 vecesy = y * 1 Se ejecuta log2(i) + 1 vecesi = i/2 Se ejecuta log2(i) + 1 veces

Se realizan 6 comparaciones en el ciclo while(i > 0) más laúltima comparación, basándose en la forma como cambia eltamaño de i . En este caso encontramos una relación entre elnúmero de comparaciones del ciclo, (6 comparaciones) y el valor dei = 32. Se puede determinar que 25 = 32, (5 es logaritmo en base 2de 32), entonces las veces que se repite el ciclo es log2(i )+1.

T(n) T (n) = 5(log2(i ) + 1) + 5

A continuación se muestra un ejemplo que usa una estructura similar a la del ciclo for (i=1;i < n; i*=2).


28/258

28

EjemploObjetivo: Crear habilidad en el cálculo de tiempo de ejecución paramétodos con tiempo de complejidad logarítmica.

Método

public void metodo ( int n){

int x = 0, i;i = 1;while( i < n ){

x++;i= i * 2;

}}


int n Se ejecuta 1 vezx = 0 Se ejecuta 1 vezi = 1 Se ejecuta 1 vezwhile(j < n) Se ejecuta log2 (n) +1 vecesx + + Se ejecuta log2 (n) vecesi = i * 2 Se ejecuta log2 (n) veces

T(n) T(n) = 3(log2(n)) + 4

ACTIVIDAD

Calcular el tiempo de ejecución para el siguiente algoritmo iterativo.

EjercicioObjetivo: Crear habilidad en el cálculo de tiempo de ejecución para

métodos.

Método

public void ejercicio ( ){

int x = 0, y = 1, w = 0, i;i = 128;while( i > 0 ){

x++;y = y * 1;i = i / 2;

}for ( i = n ; i > 0 ; i-- )

{ w++;y++;

}}


T(n)

Calcular el tiempo de ejecución para el siguiente algoritmo iterativo.


29/258

29

EjercicioObjetivo: Crear habilidad en el cálculo de tiempo de ejecución paramétodos.

Método

public void ejercicio ( int n ){

int t = 0, i, j=256;while( j > 1 ){

t++;j = j / 2;

}for (i = 2; i = 0; j--){

t--;}

}

} Análisis delTiempo deejecución

T(n)

Explique detenidamente el funcionamiento del siguiente algoritmo y calcule su tiempo deejecución. Deduzca el problema que resuelve y compare el mismo con otras implementaciones.

Método

public boolean misterio(int numero){

int raiz;int valor = 0;

if (numero==1 || numero==2 || numero==3){return true;

}else{

raiz = (int)Math.sqrt(numero);for(int i=2; i


30/258

30


T(n)

1.6.5 Tiempo de ejecución con llamada a métodos

Muchos de los problemas que se resuelven a nivel de programación están relacionados con losllamados a los métodos de las clases. A continuación, se mostrarán ejemplos en los cuales secalcula el tiempo de ejecución para algoritmos que realizan este tipo de llamado.

Para la estimación del tiempo de ejecución realizando llamadas a métodos, es necesarioanalizar el tiempo de cada uno de los métodos, y de esta forma establecer cuál es el peor caso,siempre considerando valores enteros grandes.

Ejemplo Objetivo: Crear habilidad en el cálculo de tiempo de ejecución parallamados a métodos con un tiempo de ejecución predefinido.

Método

public void metodo( int n, int x, int y){

int i;for ( i = 0; i < n; i++ ){

if(x == y){

metodo1();}else{

metodo2()}

}}

metodo1() — > T (n) = 3n + 10 metodo2() — > T (n) = 2n + 500


Dado que el metodo1 es mayor que el metodo2 (para valoresgrandes), se establece entonces el tiempo de ejecución con elmetodo1. Se procede de la misma forma en la cual se estabacalculando el tiempo de ejecución.

El tiempo de ejecución es: T(n)= ((3n + 10) * n) + (3n + 2)+ 3T(n) T(n)= 3n2+13n+5

Es frecuente cuando se usan métodos el uso de instrucciones condicionales, a continuación semuestra un ejemplo que utiliza la instrucción switch.

La estructura de selección múltiple switch permite elegir una ruta de entre varias rutasposibles, usando para ello una variable denominada selector. El selector se compara con unalista de constantes C1, C2, ..., Cn para cada una de las cuales hay una acción A1, A2, ..., An y:Si el selector coincide con una constante de la lista, se ejecuta la acción correspondiente adicha constante. Si el selector no coincide con ninguna constante de la lista, se ejecuta laacción default correspondiente al de lo contrario, si es que existe.


31/258

31

Las acciones A1, A2, A3, ..., An pueden ser acciones simples (una sola acción) o accionescompuestas (un conjunto de acciones).

El tipo de la variable que se utiliza para controlar el switch es llamada selector. Cada uno delos valores presentes en los casos (C1....Cn) debe ser de tipo compatible con el del selector.

Cada uno de estos valores debe ser único, es decir, no se aceptan rangos.

El default (por defecto) se utiliza cuando ninguno de los casos coincide con el selector. Sinembargo, la sentencia default es opcional. Si ningún case coincide y no hay sentenciadefault, no se hace nada.

El break se utiliza en sentencias switch para terminar una secuencia de acciones. Cuandose encuentra un break, la ejecución salta a la primera línea de código que sigue a la sentenciaswitch completa. Esto tiene el efecto de saltar fuera del switch.

EjemploObjetivo: Crear habilidad en el cálculo de tiempo de ejecución para

llamados a métodos en que tengan la instrucción switch.

Método

public void metodo( ){

switch (0){

case 0 : metodo1();case 1 : metodo2();case 2 : metodo3();

}if(m==x+2){

metodo4();}

} metodo1() — > T(n) = n + 3 metodo2() — > T(n) = n2 + 5 metodo3() — > T(n) = 4n2 metodo4() — > T(n) = 4n3 + 8


Dado que el valor del parámetro del switch es cero, se evalúantodos los case y por lo tanto el tiempo de ejecución es la sumatoriade cada uno de los tiempos de ejecución.

T(n) T(n) = 4n + 5n + n + 18

ACTIVIDAD

Calcular el tiempo de ejecución para el siguiente método.

EjercicioObjetivo: Crear habilidad en el cálculo de tiempo de ejecución parallamados a métodos.


32/258

32

Método

public void ejercicio( int n, int a, int b){

if (n>a && b>= d){

for (int i=0 ; ic){

metodo1();metodo2();

}}

}else{

metodo3();}

} metodo1() — > T(n) = n4 metodo2() — > T(n) = n2 metodo3() — > T(n) = n5 + 5


T(n)


EjercicioObjetivo: Crear habilidad en el cálculo de tiempo de ejecución parallamados a métodos en los cuales se encuentre la instrucciónswitch.

Método

public void ejercicio( ){

switch (2){

case 0 : metodo1();case 1 : metodo2();case 2 : metodo3();

}metodo4();

}

metodo1() — > T(n) = 2n + 30 metodo2() — > T(n) = 10n2 + 5 metodo3() — > T(n) = n2 + n + 3 metodo4() — > T(n) = n3 + 5


T(n)



33/258

33

EjercicioObjetivo: Crear habilidad en el cálculo de tiempo de ejecución parallamados a métodos. Verificar que el tiempo de ejecución es el queaparece al final del ejercicio.

Método

public void ejercicio ( int n, int b, int c){

if (n>b){

if (n>c){

for ( int i=1; i T(n)= 3n + 120 metodo3() ---> T(n)= 2n2 + 10


T(n)


EjercicioObjetivo: Crear habilidad en el cálculo de tiempo de ejecución parallamados a métodos en los cuales se encuentre la instrucciónswitch.

Método

public void ejercicio( ){

switch (0){

case 0 : metodo1();case 1 : metodo2();

break;case 2 : metodo3();case 3 : metodo4();

}}


T(n)


34/258

34

1.7 Caso de estudio: Biblioteca

A continuación se muestra un caso de estudio aplicado, en el cual se aplican actividades de unproceso de desarrollo de software. El objetivo del caso es implementar los métodos másimportantes y su posterior análisis de tiempo de ejecución. A continuación se describe el caso

de estudio.

Se desea crear una Aplicación para manejar la información de una Biblioteca o librería. En ellahay libros. Cada libro tiene un código isbn, un valor y una editorial. Cada editorial tiene uncódigo y un nombre asignado. Se debe permitir agregar un nuevo libro, mostrar cuántos librosse tienen de cada editorial (Solamente se tendrán 3 editoriales), listar los libros adquiridos ymostrar el valor total de los libros que hay en la biblioteca.

Inicialmente se realiza una descripción de los requerimientos funcionales para la aplicación.

a) Requerimientos funcionales

NOMBRE R1 – Agregar libro al listado general de libros.RESUMEN Permite agregar un nuevo libro.

ENTRADAS

Isbn, valor, codigo Editorial, nombre Editorial.

RESULTADOS

Un nuevo libro ha sido agregado.

NOMBRE R2 - Contar cantidad de libros por cada editorial.RESUMEN Permite contar la cantidad la cantidad de libros que tiene cada editorial.

ENTRADAS

RESULTADOS

Un mensaje con la cantidad de libros por editorial.

NOMBRE R3- Mostrar el listado de todos los libros.RESUMEN Genera un listado con todos los libros. ENTRADAS

RESULTADOS

Listado con todos los libros


35/258

35

NOMBRE R4 - Mostrar el valor total de los libros que hay en la biblioteca.RESUMEN Muestra el valor total de los libros que hay en la biblioteca. ENTRADAS

RESULTADOS

El valor total de los libros.

b) Identificación de las clases

Las clases principales para el caso de estudio se identifican y se describen a continuación:

CLASE DESCRIPCIÓNBiblioteca Es la clase principal del mundo

Libro Permite manejar la información de un docente

Editorial Contiene la información de la Editorial

c) Modelo de clases

Para este caso de estudio se muestran las clases del principales del dominio, estas clasescontienen todos los métodos que cumplen con los requerimientos funcionales especificados enel problema.

Se continúa con la implementación de los métodos de las clases.


36/258

36

d) Implementación de métodos

Se mostraran los métodos más relevantes para la clase Biblioteca. Se debe calcular eltiempo de ejecución para cada uno de los métodos.

Implementación de los métodos

public Biblioteca(){

contador1=contador2=contador3=0;mLibro=new ArrayList();

}

T(n) =

void setMLibro(ArrayList mLibro) /*** Permite fijar el array de libros

* @param mLibro se obtiene del archivo*/

public void setMLibro(ArrayList mLibro){

this.mLibro=mLibro;}

T(n) =

ArrayList getMLibro()

/*** Devuelve el valor del array que contiene los libros* @return ArrayList */

public ArrayList getMLibro(){

return mLibro;}

T(n) =

agregarLibro( String codEditorial, String isbn, double valor)

/*** Permite agregar un libro*/

public void agregarLibro(String codEditorial,String isbn,double valor){

Libro unLibro = new Libro(codEditorial);

if(codEditorial.equals("001")){

contador1++;}else{

if(codEditorial.equals("002")){

contador2++;

}


37/258

37

else{

contador3++;}

}

unLibro.setIsbn(isbn);unLibro.setValor(valor);mLibro.add(unLibro);

}T(n) =

obtenerCantidaFabricantes()

/*** Permite obtener la cantidad de fabricantes* @return String Contiene la cantidad de artículos por fabricante*/

public String obtenerCantidaFabricantes(){

return "Addison Wesley: "+contador1+" Mc Graw Hill: "+contador2+"Prentice Hall: "+contador3;

}T(n) =

determinarValorMercancia()

/*** determina el valor total de la mercancía que hay en la biblioteca.* @return double valor de los libros en la biblioteca*/

public double determinarValorMercancia(){

double valor=0;

for(int i=0; i


38/258

38

Nuestro proceso no ha finalizado aquí puesto que debemos pasar del diseño a laimplementación. Esta fase se inicia con la evaluación (en términos de complejidad dealgoritmos y de espacio ocupado, de dificultad y de grado de desacoplamiento) de los diseñosque fueron propuestos, los cuales deberán refinarse hasta que sea posible argumentar por quéese diseño es el mejor, siendo importante llevar a cabo las comparaciones pertinentes respecto

a los diseños obtenidos, fruto de la cual se seleccionará uno de ellos.

ACTIVIDAD

Escriba los métodos para la clase Biblioteca que resuelven los problemas que se describena continuación.

EjercicioObjetivo: Generar habilidad en la construcción de métodos paraposteriormente calcular su tiempo de ejecución.

Escriba unmétodo queretorne laposición en lacual seencuentra ellibro con elmayor valor.

public int mayorPosicion(){

}


T(n)


Escriba unmétodo quemuestre el isbnde los libros quese encuentranlas posicionesimpares delArrayList.

public String mostrarIsbnPosicionesImpares(){

}


T(n)


39/258

39


Escriba unmétodo quemuestre lasposiciones delos libros cuyocódigo isbntermina en elcarácter 5.

public String mostrarPosicionesIsbn()

{

}

Análisis del

Tiempo deejecución

T(n)

EjercicioObjetivo: Generar habilidad en la construcción de métodos yposteriormente calcular su tiempo de ejecución.

Escriba unmétodo quepermita

determinar elvalor total de lamercancía delos elementosque seencuentran enlas posicionespares delArrayList.

public String sumarElementosPares(){

}

Análisis delTiempo de

ejecución

T(n)

1.8 Comparación de tiempos de ejecución

La comparación de los algoritmos proporciona una medida concreta de cuando un algoritmo esmás eficiente que otro de acuerdo a un conjunto de datos de entrada. El siguiente cuadropermite establecer una comparación del crecimiento de algunas funciones, en las cuales semuestra su comportamiento y diferencias con otras funciones de acuerdo a un valor nparticular.


40/258

40

Cuando en una aplicación se van a procesar pocos datos de entrada, es poco importanteanalizar un algoritmo independiente del crecimiento de la función. Por ejemplo, si se deseaprocesar 50 datos, es casi indistinto que se utilice un algoritmo con tiempo de ejecución n o nlog(n), pero si se desea procesar 2000000 datos, el algoritmo con n log(n) crececonsiderablemente con relación a n. Es por ello necesario entrar a realizar un estudio sobre el

crecimiento y comportamiento asintótico de los tiempos de ejecución de los algoritmos.

Función nombreLog2(n) (Logarítmico)

n (Lineal)n log(n) n log(n)

n2 Cuadráticon Cúbico2n Exponencial

A continuación se muestra una tabla con el crecimiento de algunas funciones polinómicas y lascuales son las más frecuentemente usadas en el análisis de algoritmos.

Los siguientes ejemplos permiten comparaciones de los tiempos de ejecución. Considerandosu crecimiento, se recomendara alguno de ellos considerando que en cada caso se resuelve elmismo problema,

Se tienen dos algoritmos los cuales tienen un tiempo de ejecución dado respectivamente por2n+10 y n log(n), para el mismo problema, cuál de ellos recomendar y por qué?. En la siguientefigura se observa que a partir del valor 15, la función n log(n) está por encima de la función 2n+ 10, por lo que se recomienda que a partir del valor 15, se debe recomendar el algoritmo contiempo de ejecución 2n + 10.


41/258

41

En la siguiente figura se ve el comportamiento de dos algoritmos que tienen tiempos deejecución 2n2 + n + 5 y log(n). Según su comportamiento, se observa que en todo caso lafunción logarítmica log(n) siempre está por debajo de la cuadrática, por ello se recomienda elalgoritmo que tiene la función log(n).

Como se pudo observar, es fundamental estimar y entender el comportamiento de losalgoritmos de acuerdo a su crecimiento. Una vez que se tenga claro cuál es la cantidad dedatos a procesar, es necesario tomar la decisión de cual algoritmo recomendar.

ACTIVIDAD

Dadas la siguiente grafica con sus correspondientes funciones, realice un análisis delcomportamiento de las mismas e indique cuando la una es más eficiente que la otra. Lasfunciones a comparar son 2n2 y log(n).

Para una implementación completa que permita comparar dos algoritmos, se desea determinarel máximo común denominador de dos números enteros positivos. El máximo común divisor(MCD) se define de la forma más simple como el número más grande posible, que permitedividir a esos números.

A continuación se muestran dos implementaciones diferentes del mismo problema.


42/258

42

Método 1Máximo común

Divisor

public int mcd(int a,int b){

int valora, valorb;valora = a;valorb = b;

while (valora!=valorb){

if(valora 0; i--){

if(a%i==0 && b%i==0){

resultado = i;break;

}

}return resultado;

}

Se comparan ambos algoritmos asumiendo que los valores que se envían por parámetro almétodo son: a = 30 y b = 18. En el siguiente cuadro se observan las instrucciones necesariaspara la deducción del MCD del segundo algoritmo.

A b resultado i i>0 If(a%i==0 b%i==0)30 18 1 18 18>0 30%18==0 && 18%18==0

17 17>0 30%17==0 && 18%17==0

16 16>0 30%16==0 && 18%16==015 15>0 30%15==0 && 18%15==0

14 14>0 30&14==0 && 18%14==0.. .. … .. .. ……………

7 7>0 30%7==0 && 18%7==0

6 6>0 30%6==0 && 18%6==06

En el siguiente cuadro se observan las instrucciones que son necesarias para la deducción delMCD del primer algoritmo.

Valora Valorb While(valora!=valorb) If(valora


43/258

43

Considerando los cuadros anteriores, se puede deducir por los valores ingresados, que elprimer algoritmo es más eficiente que el segundo. Esto dada la cantidad de instrucciones quese ejecutan. Pero es posible afirmar lo mismo si los valores que se ingresan sonrespectivamente: a = 38 y b = 4.

En el siguiente cuadro se observan las instrucciones necesarias para la deducción del MCD delsegundo algoritmo.

a B resultado i i>0 If(a%i==0 b%i==0)38 4 1 4 4>0 38%4==0 && 4%4==0

3 3>0 38%3==0 && 4%3==0

2 2 2>0 38%2==0 && 4%2==0

En el siguiente cuadro se observan las instrucciones que son necesarias para la deducción delMCD del primer algoritmo, con los valores anteriormente dados.

Valora Valorb While(valora != valorb) If(valora < valorb)38 4 38 != 4 38


44/258

44

a) Requerimientos funcionales

NOMBRE R1- Agregar Persona

RESUMENENTRADAS

RESULTADOS

NOMBRE R2- Eliminar Persona

RESUMEN

ENTRADAS

RESULTADOS

NOMBRE R3- Mostrar el listado de todas las personas

RESUMEN

ENTRADAS

RESULTADOS

NOMBRE R4- Buscar una persona por nombreRESUMEN

ENTRADAS

RESULTADOS

NOMBRER5- generar un listado de personas que están cumpliendo años el

día de hoyRESUMEN

ENTRADAS

RESULTADOS

b. Identificar las entidades o clases.

ENTIDAD DEL MUNDO DESCRIPCIÓNAgendaTelefonica

Persona

Fecha


45/258

45

c. Especificar las relaciones entre las clases ( AgendaTelefonica, Pesona, Fecha).

d. Construcción de la aplicación

Para las siguientes clases escriba en java las los métodos e instrucciones necesarias para elcorrecto funcionamiento de la aplicación. Como estrategia se dejan parcialmente planteadosmétodos de implementación y los cuales deben ser completados.

En la clase AgendaTelefonica puedes observar que se ha hecho uso de ArrayList. UnArrayList es una estructura contenedora dinámica que crece o disminuye dinámicamente.

import java.io.Serializable;import java.util.ArrayList;import java.util.Calendar;import java.util.GregorianCalendar;

public class AgendaTelefonica implements Serializable{

ArrayList listaPersona ;

int contadorContactos, contadorTotal, contadorCumpleaños;

/*** Constructor de la clase AgendaTelefonica*/public AgendaTelefonica(){

contadorContactos = ___________;contadorTotal = ___________;contadorCumpleaños = ___________;listaPersona = new _____________;

}

/*** Permite inicializar el atributo listaPersona* @param listaPersona contiene la información de los contactos*/public void setListaPersona( ArrayList listaPersona ){

this.listaPersona = ___________________;

}


46/258

46

/*** @return ArrayList devuelve la información de las* personas contenidas en la agenda.*/public ArrayList getListaPersona()

{__________________________;

}

/**Constructor de la AgendendaTelefonica* @param listaPersona */

public AgendaTelefonica( ArrayList listaPersona ){

this.listaPersona = ____________________;}

public void agregarPersona( String cedula, String nombre,

String direccion, int dia, int mes,int anio, ArrayList telefono )

{miPersona.____________________ ( cedula );miPersona.____________________ ( nombre );miPersona.setDireccion ( ___________________ );miPersona.setMiFechaNacimiento ( ________________ );miPersona._____________________( teléfono );listaPersona.add(_________________);

}

/*** @return String[] devuelve la información de los contactos

*/public String[] obtenerContactos(){

int i;contadorTotal = 0;String[] contactos;Contactos = new String[ listaPersona.size() + 1 ];contadorTotal = listaPersona.size();

for( i=0 ; i < listaPersona.size() ; i++ ){

String infoT = listaPersona.get(i).getTelefono().toString();

String info = listaPersona.get( i ).getCedula() + "" +__________________________________+ infoT;contactos[ i ] = info;

}

contactos[ i ] = "En total: " + contadorTotal + " contactos";return contactos;

}

/*** Permite obtener un contacto que contenga a nombre.* @return String[] información del contacto que coincide con el* nombre especificado.*/


47/258

47

public String[] obtenerContatosNombre( String nombre ){

int i = 0;contadorContactos = 0;String[] contactos;

ArrayList contactosNombre = new ArrayList();

}

/** Devuelve el contador de contactos */public int getContadorContactos(){

________________________

}

/** Devuelve el contadorTotal */public int getContadorTotal(){

__________________________

}

/** Contador de personas que están cumpliendo años */public int getContadorCumpleaños()

{ _________________________

}

/** Devuelve la información de las personas que están cumpliendo* años */

public String[] obtenerContatosCumpleaños(){

String[] contactos;int i;GregorianCalendar go = new GregorianCalendar();

//sacamos los valores del dia, mes y añoint dia = go.get ( Calendar.DAY_OF_MONTH );int mes = go.get ( Calendar.MONTH ) + 1;contadorCumpleaños = 0;

ArrayList contactosNombre = new ArrayList ();

}


48/258

48

/** Permite eliminar una persona especificando la cédula */public void eliminarPersona(String cedula){

}}

ACTIVIDAD

Una vez escritos los métodos para la clase AgendaTelefonica, se debe calcular el tiempo deejecución de cada uno de ellos.

MétodoTiempo de Ejecución

T(n)String[] obtenerContactos()

String[] buscarContatosNombre(String nombre)

int getContadorContactos()

int getContadorTotal()

String[] obtenerContatosCumpleaños()

void eliminarPersona(String cedula)

1.10 Complejidad Computacional

En la sección anterior se ha trabajado el concepto de tiempo de ejecución de formaexperimental sobre cada uno de los algoritmos expuestos. Este análisis resulta particularmente

interesante y útil cuando debemos decidir cuál algoritmo escoger bajo unos criterios razonablesy sustentables.

Los órdenes polinómicos más comunes de los tiempos de ejecución de los algoritmos son lossiguientes:

Log2(n) (Logarítmico). Los algoritmos con este tiempo de ejecución son consideradoscomo muy eficientes.

n (Lineal). Es común en aplicaciones que utilizan ciclos sencillos. n log(n). Común encontrarla en algoritmos de ordenamiento eficientes. n2 (Cuadrático). Habitual cuando se usan 2 ciclos anidados. n3 (Cúbico). Habitual cuando se usan 3 ciclos anidados. 2n (Exponencial). No suelen ser muy útiles en la práctica por el elevado tiempo de

ejecución.


49/258

49

La elección de un buen algoritmo está orientada hacia la disminución del costo que implica lasolución del problema; considerando este enfoque es posible orientar esta elección en doscriterios (Iparraguirre, 2009):

Criterios orientados a minimizar el costo de desarrollo: claridad, sencillez y facilidad de

implantación, depuración y mantenimiento. Criterios orientados a disminuir el costo de ejecución: tiempo de procesador y cantidad

de memoria utilizados.

Cuando se resuelve un problema, normalmente hay necesidad de elegir entre variosalgoritmos, típicamente existen dos objetivos que suelen contradecirse (Aho, Ullman, &Hopcrof, The Design and Analysis of Computer, 1994):

Que el algoritmo sea fácil de entender y codificar Que el algoritmo use eficientemente los recursos, y en especial, que se ejecute con la

mayor rapidez posible.

Debemos tener claro que los aspectos interesantes a reducir son el tiempo y el espacio en

memoria. En cuanto al tiempo nos hemos centrado en la función T(n), la cual determina lacantidad de operaciones que efectúa un algoritmo. De acuerdo a la forma como se calcula elT(n) es importante hacer dos precisiones:

El tiempo de ejecución T(n), suele ser difícil de calcular exactamente. Si cada operación necesita una fracción de tiempo muy pequeña de tiempo para

ejecutarse, no se precisa una exactitud en el cálculo de T(n).

Estas dos precisiones nos permiten dar una aproximación al concepto de complejidadcomputacional de un algoritmo, como un concepto que recoge la naturaleza asintótica de lafunción T(n) y no su valor exacto. Dicha naturaleza debe dar información de cómo crece lafunción cuando aumenta el tamaño de n. Normalmente, el análisis de la complejidad de losalgoritmos está relacionado con conceptos matemáticos que son necesarios precisar.

1.10.1 Notación Asintótica

Debido a que la eficiencia de un algoritmo no se expresa en alguna unidad de tiempodeterminada debido a que se escoge una medida arbitraria T(n), se ha introducido una notaciónespecial llamada notación asintótica, porque tiene que ver con el comportamiento de dichasfunciones en el límite, o sea, para valores suficientemente grandes en sus parámetros.

1.10.2 Notación Big Oh O.

En 1892, Paul Gustav Heinrich Bachmann inventó una notación para caracterizar elcomportamiento asintótico de funciones. Esta invención se conoce como notación O grande. Elautor define una función que mide el tiempo de ejecución de un algoritmo, y que debe cumplirlas siguientes condiciones:

El argumento n es estrictamente positivo. La evaluación de la función T(n) nunca es negativa, para cualquier argumento n.

Si f(n) es alguna función definida sobre los enteros no negativos n, se dice entonces que T(n)es O(f(n)) (McConnell, 2007).


50/258

50

Comparación de O(f(n)) con relación a T(n)

T(n) es O(f(n)) si existe un entero n0 y una constante c > 0, tal que para todos los enterosn >= n0 , tenemos que T(n)


51/258

51

Regla de la Suma

Suponga que un algoritmo está formado por dos secciones, una de ellas con O(n2) y la otracon O(n3). Entonces es posible sumar estos dos órdenes de complejidad para obtener lacomplejidad total del algoritmo. La regla es la siguiente:

Suponga que para T1(n) se sabe que es O(f1(n)) y T2(n) es O(f2(n)) y suponga, además,que f1 crece más rápido que f2. Esto se traduce en que f2(n) es O(f1(n)). En consecuenciase puede concluir que T1(n) + T2(n) es O(f1(n)).

1.10.3 Notación Omega Ω

Dada una función f , queremos estudiar aquellas funciones g que a lo sumo crecen tanlentamente como f . Al conjunto de tales funciones se le llama cota inferior de f y lodenominamos f . Conociendo la cota inferior de un algoritmo podemos asegurar que, en ningúncaso, el tiempo empleado será de un orden inferior al de la cota.

Decir que T (n) es Ω (f (n)) se lee “omega grande de f (n)”, significa que existe una constantepositiva c y tal que para los n, no se cumple que T (n) ≥ cf (n), (f (n) es una cota inferior paraT (n)).

1.10.4 Notación

Dada una función g de los enteros no negativos a los números reales positivos. Entonces(g )=O(g ) Ω (g ), es decir, el conjunto de funciones que están tanto en O(g ) como en Ω (g ).Comunmente la forma de leer es “f a (g )”, es decir , “f es del orden de g”.

La función f a (g) si , para alguna constante c tal que 0 < c < .

Asociada a las anteriores notaciones es posible el uso de otros conceptos matemáticos entrelas cuales encontramos las denominadas funciones de piso y techo. La función piso y techopuede ser utilizada para cualquier número flotante o entero y.

La expresión denotada como y se conoce como la función piso de y corresponde al enteromás grande que es menor o igual que x. 2.1 = 2, 4.5 = 4 y 6.9 = 6.

La expresión denotada como y se conoce como la función tech

Documents

Análisis de Algoritmos Para Ingenieria de Sistemas y Comput