Módulo 1 - Lectura 1 - Apuntes 1 PDF

Preview

Summary

tp resumen modulo1 algoritmo y estructura de datos 1 resumen modulo1 algoritmo y estructura de datos 1...

Description

Algoritmos y tiempos de ejecución

Los problemas surgen cotidianamente y, muchas veces, se debe encontrar una manera para resolverlos. Se pueden hallar diferentes algoritmos que ayuden a resolver un mismo problema y estos, si están escritos en un lenguaje adecuado (un lenguaje de programación), pueden ser ejecutados por computadoras, de manera que se automaticen. Así, se evitan los errores humanos en el proceso de resolución, además, se agilizan y se obtienen los resultados en un período de tiempo que sea realmente útil.  A su vez, como se pueden distinguir distintos algoritmos para resolver un mismo problema, es necesario contar con algún método que permita comparar algoritmos, para poder elegir aquel que se ajuste mejor a las diferentes necesidades. Como estos algoritmos van a ser ejecutados en computadoras, debe tenerse en cuenta que estas cuentan con una memoria y con las capacidades para resolver problemas lógicos y matemático-aritméticos. Los recursos con los que cuenta una computadora son finitos, por lo que se debe considerar este aspecto a la hora de diseñar un buen algoritmo.

Algoritmos

Referencias

LECCIÓN 1 de 2

Algoritmos

Definición. Ejemplos Se comenzará por lo primero, ¿qué es un algoritmo?

“Llamamos algoritmo al conjunto finito y ordenado de acciones con las que podemos resolver un determinado problema. Llamamos problema a una situación que se nos presenta y que, mediante la aplicación de un algoritmo, pretendemos resolver” (Sznajdleder, 2012).

Cuando se tienen algoritmos distintos que resuelven un mismo problema de maneras diferentes, se dice que dichos algoritmos son equivalentes.

En realidad, se aplican algoritmos todos los días, al realizar las distintas actividades. Se tomará, por ejemplo, la receta para preparar un pan casero. El algoritmo tendría los siguientes pasos:

1

agregar la harina (agregarHarina);

2

agregar el agua (agregarAgua);

3

agregar sal (agregarSal);

4

amasar la masa (amasar);

5

dejar reposar la masa durante veinte minutos (reposarMasa); y

6

hornear durante cuarenta minutos (hornear).

A su vez, cada paso puede descomponerse en subpasos o módulos. Por ejemplo, la acción agregarHarina puede descomponerse en:

1

medir la harina (medirHarina);

2

tamizar la harina (tamizarHarina); y

3

colocar la harina en el bol (colocarHarina).

El módulo hornear quedaría:

1

precalentar el horno (precalentarHorno);

2

colocar la placa con la masa en el horno (colocarPlaca);

3

ajustar el horno a doscientos grados (ajustarHorno); y

4

quitar la placa del horno a los cuarenta minutos (quitarPlaca).

Así, se puede descomponer tanto como se desee. Por ejemplo, se puede profundizar, aún más, descomponiendo la acción quitarPlaca en:

1

tomar las agarraderas;

2

abrir el horno;

3

tomar la placa con las agarraderas;

4

sacar la placa del horno; y

5

colocar la placa sobre una tabla.

En el ámbito informático, cuando se habla de algoritmos, se está haciendo referencia al conjunto de acciones que debe seguir una computadora para resolver un problema. Se mencionó que un problema es una situación que se pretende resolver con un algoritmo. Dentro del ámbito informático, en el cual está enmarcada esta materia, se tienen distintos problemas comunes que surgen para ser resueltos con distintos algoritmos, tales como el de la recursión, el del ordenamiento de los elementos dentro de una estructura y el problema de encontrar un elemento dentro de una estructura. Existe una infinidad de problemas que pueden ser resueltos algorítmicamente.

En el video 1 se puede observar, de manera simple, en qué consiste un algoritmo.

Video 1: ¿Qué es un algoritmo?

¿Qué es un algoritmo?

Fuente: Magic Markers (21 de julio de 2015). [Video de YouTube] Recuperado de: https://www.youtube.com/watch?v=U3CGMyjzlvM

Diseño de algoritmos Para poder diseñar correctamente un algoritmo, es necesario conocer su contexto, de manera que se tenga claro su alcance, sus datos de entrada y sus salidas. Esto es de gran importancia. De hecho, algunos autores definen a los algoritmos como procedimientos computacionales que se encargan de tomar las entradas, de procesarlas y generar una o varias salidas.

En este ejemplo, el alcance específico que el algoritmo incluye va desde el armado de la masa hasta la obtención del pan sacado del horno. Las

entradas podrían ser la cantidad de panes a hornear, el tipo de harina que se va a usar, la marca de la sal, el tipo de horno, etcétera. Las salidas podrían ser la cantidad de panes obtenidos con falta de cocción, los panes bien cocidos, los quemados, etcétera.

Para diseñar los algoritmos, también, se cuenta con tres recursos, que son: la memoria, las operaciones aritméticas y las operaciones lógicas.

En el ejemplo, se necesita tener en la memoria que se debe quitar la placa del horno a los cuarenta minutos. Se llamará a la variable de la hora transcurrida horaActual y a la del límite de cuarenta minutos, tiempoLimite.

Un algoritmo es una serie de pasos definidos para resolver un problema.

Verdadero

Falso

SUBMIT

Análisis de algoritmos

Dado un problema para resolver, se sabe que, muchas veces, se lo puede solucionar de más de una forma y que algunas de estas serán más eficientes que otras. Es decir, ya sea en el tiempo de ejecución, en el uso de los recursos como la memoria, el disco, la red e, incluso, el tiempo que le lleva a un desarrollador escribir el algoritmo.

A la hora de elegir un algoritmo para programar la funcionalidad de una aplicación, se tendrán que tener en cuenta los parámetros, como el hardware sobre el que se ejecutará dicha aplicación, la cantidad de datos que procesará y los tiempos de ejecución esperados por el tipo de usuario al que está destinada.

Por ejemplo, si se está desarrollando una aplicación que se espera que pueda ser ejecutada en las computadoras hogareñas típicas; tendrás que tener en cuenta que los algoritmos que implementes cumplan con los tiempos que un usuario doméstico puede soportar en la respuesta de una aplicación y que el poder de procesamiento será el de una computadora doméstica.

Entonces, se vuelve indispensable encontrar formas de analizar los algoritmos para poder determinar su eficiencia. Para ello, se analiza el comportamiento de los algoritmos en forma matemática.

Si se sacan otros factores (como la velocidad, la cantidad de procesadores, la calidad del compilador y la cantidad y la velocidad de la memoria), el tiempo de ejecución de un algoritmo es una función de la cantidad de los datos de

entrada que debe procesar. A mayor cantidad de datos, mayor será el tiempo de ejecución, por lo que se utilizan funciones matemáticas para caracterizar la eficiencia de los algoritmos.

Se formula, por ejemplo, la función que define el tiempo de ejecución para el despliegue de la tabla en un reporte de ventas por vendedor. En este caso, se supone que lleva 0,0014 segundos contar la cantidad de registros y dibujar la tabla con sus encabezados. Luego, toma 0,012 segundos, obtener y colocar en la tabla el registro de venta de cada vendedor.

La función del tiempo de ejecución resultante sería:

Tiempo de ejecución: 𝑡𝑒 = 0,0014+𝑁∗0,12 N es la cantidad de registros de venta del sistema.

Como se puede observar, se llega a una función lineal (N elevado al exponente 1), donde, tal como sucede en cualquier función lineal, la tasa de crecimiento de la función (en este caso, el tiempo de ejecución te) es igual a la tasa de crecimiento de la variable (en este caso, el tamaño de la entrada N). Se muestra una relación de proporcionalidad: el tiempo de ejecución es directamente proporcional al tamaño de la entrada.

Un algoritmo lineal es aquel que tiene un tiempo de ejecución que responde a una función lineal. Es el más eficiente. Sin embargo, existen algoritmos no lineales con tiempos de ejecución mucho más elevados. Las funciones más

comúnmente encontradas en el análisis de algoritmos son las siguientes, ordenadas de mayor a menor eficiencia:

Lineal

–

El tiempo de ejecución se incrementa a la misma velocidad en que se aumenta la cantidad de datos de entrada. O sea, son directamente proporcionales a la cantidad de datos de entrada a los que se someten. Es por esto que es el tipo de algoritmo más eficiente.

N*log(N)

–

El logaritmo es una función que crece lentamente. Aunque crece más rápido que la función lineal, es más lenta que la cuadrática y la cúbica. El tiempo de ejecución, en estos algoritmos, es N veces el logaritmo de N, siendo N el tamaño de la entrada.

Cuadrática

–

El tiempo de ejecución está definido por una función cuadrática (por ejemplo, 3N2+2N +3) siendo N el tamaño de la entrada. Los algoritmos de este tipo son menos eficientes que los del tipo N*Log(N).

Cúbica

–

El tiempo de ejecución está definido por una función cúbica (por ejemplo, 4N3+3N2+2N +3) siendo N el tamaño de la entrada. Están entre los menos eficientes, ya que, ante pequeños incrementos en el tamaño de los datos, el tiempo de ejecución del algoritmo crece rápidamente.

Pueden darse casos en que, por las constantes implicadas, una función N*Log(N) sea más eficiente que una lineal. Sin embargo, ante una misma complejidad, las lineales son más eficientes.

Distinto es el caso de los algoritmos cuadráticos, que tienen altos tiempos de ejecución, a partir de un tamaño de entrada de unos pocos miles. Peor aún, es el caso de los algoritmos cúbicos que tienen tiempos de ejecución lentos, a partir de un tamaño de entrada de unos pocos cientos.

En la figura 1, se observa el gráfico comparativo de las diferentes funciones de análisis de algoritmos y los tiempos de ejecución para entradas de pequeño tamaño.

Fuente: Weiss, 2013, p. 187.

Figura 1: Tiempos de ejecución para entradas de pequeño tamaño En la imagen se observa el gráfico comparativo de las diferentes funciones de análisis de algoritmos y los tiempos de ejecución para entradas de tamaño moderado.

Fuente: Weiss, 2013, p. 187.

Figura 2: Tiempos de ejecución para entradas de tamaño moderado Al observar estos gráficos, se puede evidenciar que, ante las entradas pequeñas, las diferencias en el tiempo de ejecución de cada función no son muy grandes. Sin embargo, cuando se tienen entradas grandes, las diferencias en el tiempo de ejecución de cada función se vuelven grandes. A

medida que se aumenta el tamaño de la entrada, se hace notable la diferencia de la eficiencia. Normalmente, el tiempo de ejecución se ve afectado cuando el tamaño de la entrada es grande. Por esto, es en las grandes cantidades de entradas donde preocupa más la eficiencia del algoritmo.

Cabe aclarar que, cuando se está ante la presencia de entradas pequeñas, la tasa de crecimiento puede no llegar a ser del todo importante. Incluso, puede suceder que una función con una tasa de crecimiento mayor que otra función sea más eficiente. De todas maneras, se podrá usar una u otra función sin notar mucha diferencia entre ellas. Pero, esto no es lo que suele suceder. Por ello, es necesario abocarse a analizar los tiempos de ejecución ante las entradas grandes.

Es por esto que la optimización del algoritmo es la tarea principal, a la hora de hacer que un código se ejecute en forma eficiente, es decir, diseñar un buen algoritmo desde el principio. No importa qué tanto se optimice el código. La optimización debe realizarse, primeramente, sobre el algoritmo, porque es el que define la eficiencia en la ejecución.

Ejemplos de tiempos de ejecución de los algoritmos Se examinarán tres problemas para resolver, con el fin de ejemplificar los tipos de funciones que se aplican a algunos algoritmos utilizados normalmente:

hallar el elemento mínimo de una matriz;

hallar los puntos más próximos en un plano (x; y); y

hallar todos los grupos de tres puntos colineales en un plano (x; y).

Hallar el elemento mínimo de una matriz El objetivo de este algoritmo es encontrar aquel elemento con menor valor dentro de una estructura de datos que, en este caso, es una matriz.

Consta de los siguientes pasos:

1

guardar, en una variable, el primer elemento de la matriz; y

2

comparar el elemento de la variable con cada elemento de la matriz y, en los casos en que el elemento de la matriz sea menor, guardarlo en la variable.

Una vez que se hayan recorrido todos los elementos de la matriz, la variable contendrá el valor mínimo de esta. Este es el caso de un algoritmo lineal, ya que se deben recorrer los elementos de toda la matriz y se posee un tiempo de ejecución fijo para cada elemento.

Hallar los puntos más próximos en un plano

Se tiene un plano con una cantidadN de puntos y el objetivo es encontrar, entre todos esos puntos, al par donde la distancia entre ellos sea menor, en comparación con la distancia entre cualquier otro par de puntos.

Se puede realizar de la siguiente forma:

1

encontrar todos los pares de puntos existentes en el plano;

2

calcular la distancia entre cada par de puntos; y

3

hallar el de menor distancia.

La cantidad de pares de puntos existentes en cualquier plano de N puntos es igual a:

Figura 3: Fórmula para calcular la cantidad de pares de puntos existentes

Fuente: Elaboración propia.

Si se expande la expresión anterior, queda una función cuadrática:

Figura 4: Función cuadrática

Fuente: Elaboración propia.

Si se utilizan algunos artilugios, se puede evitar calcular la distancia entre todos los pares de puntos del plano. Dicha técnica responde a una función N*log(N) e, incluso, existe una forma que responde a una función lineal.

Hallar todos los grupos de tres puntos colineales en un plano Es un problema que se da mucho en el ámbito del tratamiento de los gráficos. Se puede realizar siguiendo estos pasos:

1

encontrar todos los grupos de tres puntos existentes en el plano; y

2

verificar cuáles se encuentran alineados.

La cantidad de grupos de tres puntos en un plano de N puntos es igual a:

Figura 5: Fórmula para calcular los grupos de tres

Fuente: Elaboración propia.

Figura 6: Función cúbica

Fuente: Elaboración propia.

Al igual que en el caso anterior, existe una forma de resolver este problema de una manera más eficiente, mediante el uso de un algoritmo cuadrático. Sin embargo, esto excede el alcance de esta materia.

Al analizar cada problema, mostramos una solución y el tiempo de ejecución para ese algoritmo. Sin embargo, mencionamos que existen otras maneras de mejorarlos. De esta forma, podemos ver cómo un mismo problema se puede resolver con distintos algoritmos que, según la tasa de crecimiento de la función matemática a la que responden, son más o menos eficientes.

Existen diferentes algoritmos, lineales y no lineales, que poseen diferentes tiempos de ejecución. De las funciones más comúnmente utilizadas en el análisis de algoritmos y ante una misma complejidad, ¿cuál es la más eficiente?

La función lineal.

La función logarítmica.

La función cuadrática.

La función cúbica.

SUBMIT

C O NT I NU A R

LECCIÓN 2 de 2

Referencias

Magic Markers (21 de julio de 2015). ¿Qué es un algoritmo? [Video de Youtube]. Recuperado de: https://www.youtube.com/watch?v=U3CGMyjzlvM

Sznajdleder, P. A. (2012). Complejidad algorítmica. En D. Fernández, Algoritmos a fondo con implementación en C y JAVA (pp. 522-523). Buenos Aires: Alfaomega.

Weiss, M. A. (2013). Análisis de algoritmos. En Martín-Romo, M. Estructuras de datos en Java (pp. 185-190). Madrid: Pearson.

C O NT I NU A R...