Módulo 1 y 2 algoritmos y estructuras de datos I primer parcial PDF

Preview

Summary

Download Módulo 1 y 2 algoritmos y estructuras de datos I primer parcial PDF

Description

Módulos miércoles, 13 de octubre de 2021

14:19

M Ó DULO 1 Aná Unidad 1 . An álisis de algoritmos 1.1. Introducción ¿Qué es un a lgoritmo? “Llamamos a l go goritmo ritmo al conjunto finito y ordenado de acciones con las que podemos resolver un determinado problema. Llamamos p ro blema a una situación que se nos presenta y que, mediante la aplicación de un algoritmo, pretendemos r e solv olver er” (Sznajdleder, 2012).

Cuando se tienen algoritmos distintos que resuelven un mismo problema de maneras diferentes, se dice que dichos algoritmos son eq equu i valentes.

Di señ o d e al goritm os seño algoritm goritmos Para poder diseñar correctamente un algoritmo, es necesario conocer su co ntexto, de manera que se tenga claro su al alccan ance ce, sus dat datoos de e ntr ada y sus s al alii das das. Esto es de gran importancia. De hecho, algunos autores definen a los algoritmos como pr proocedimi cedimien en entos tos comp omputacionales utacionales q u e s e e nc ncaarg rgaan de toma marr l as e ntr ntradas, adas, de p r oce ocesa sa sarlas rlas y ge gene ne nerr ar un unaa o v ar arias ias s al alida ida idas.s. Para diseñar los algoritmos, también, se cuenta con tres recursos, que son: l a m e m oria oria,, l as o p erac eraciones iones a r itmétic itméticas as y la lass o p era eraciones ciones ló lógi gi gicas cas cas.

Aná náli lisi sis li si s de a lgoritmos Dado un problema para resolver, se sabe que, muchas veces, se lo puede solucionar de m ás de un unaa ffoo r ma y que algunas de estas serán m ás e fi cientes q ue o tra trass. 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 l o s pa parr ámetros ámetros, como el h ar ardw dw dware are sobre el que se ejecutará dicha aplicación, la c ant antidad idad de dat datos os que procesará y los t ie iempos mpos de e je cuc cución ión esperados por el tipo de usuario al que está destinada. 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 un unaa f un unci ci ción ón de la ccan an antt idad de l o s dat datos os de en entt r ada q ue de b e pr proce oce ocesar sar sar. A mayor cantidad de datos, mayor será el tiempo de ejecución, por lo que se utilizan fu ncio nciones nes m a t emá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. Un al algo go goritmo ritmo l in ineal eal es aquel que t i en enee u n t i em empo po de e je cu cución ción q ue r e sponde a u na fu n c ión liline ne neaal. E s e l m á s e fic ficiente. iente. iente.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: Li Linn e al 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* N*ll o g(N g(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.

C uad uadrr á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 úb úbii ca 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. E s tán en entr tr tree l os m e nos e f icientes icientes, ya que, ant antee pe peqq ueñ ueños os i nc ncre re remen men mentos tos en e l tam amaa ño de lo loss dat datos, os, el t i emp empoo de e je cución de dell al algg oritmo cr ece r ápi ápiddamente.

F i g ura 1 : T i empos de e je cución p ar araa e ntr ntradas adas de pe peqq ue ueño ño t ama amaño ño

Fi Figu gu gurr a 2 : T i em empos pos de e je jecc ución p ar araa e nt ntradas radas d e t am amañ añ añoo m o dera derado do

Ante las e nt ntrr adas p e queña queñass, las diferencias en el t i e mpo de ej ejee cución de cada función n o s o n m u y g ra randes ndes ndes. Sin embargo, cuando se tienen e nt ntra ra radas das g r andes ndes, las diferencias en el tiempo de ejecución de cada función s e v u e lvlven en g ran randes des des. A medida que se aumenta el tamaño de la entrada, se hace notable la di diff ere erenci nci nciaa de la ef efii ciencia ciencia.

Es por esto que la op ti mizació mizaciónn de dell al algg orit oritmo mo e s l a tar area ea pr principal incipal incipal, a la hora de hacer que un código se ejecute en forma eficiente, es decir, di diss e ñar u n b ue uenn al algor gor goritmo itmo de dess de e l p r incipio incipio. No importa qué tanto se optimice el código. La optimización debe realizarse, primeramente, sobre el algoritmo, porque es el que define la ef efii ciencia e n la e jec ecución ución ución.

1.2. Ejemplos de tiempo de ejecución de algoritmos • hal alll ar e l el elee me mento nto m í nimo de u na m at atriz; riz; 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:

2B 2021 Page 1

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.

alll ar lo loss pu punt nt ntos os m á s p r óximos en u n p l ano ( x; y ); • hal 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: ○ encontrar todos los pares de puntos existentes en el plano; ○ calcular la distancia entre cada par de puntos; y ○ 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

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

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. • hal alll ar t o dos l o s gr grupos upos de t r es pu puntos ntos c o lineales e n u n pl plan an anoo ( x ; y ) . Es un problema que se da mucho en el ámbito del tratamiento de los gráficos. Se puede realizar siguiendo estos pasos: ▪ encontrar todos los grupos de tres puntos existentes en el plano; y ▪ verificar cuáles se encuentran alineados. La cantidad de grupos de tres puntos en un plano de N puntos es igual a: Fi g ura 5 : F órmula p ar araa cal alcul cul culaar l os gr grup up upos os de tr es

F i g ura 6 : F unción c ú bica

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.

1.3. Análisis asintótico 1.4. Notación O El impacto se profundiza a medida que crecemos en el problema a resolver, por lo cual, consideraremos a N tendiendo a infinito.

En ese caso, estaremos considerando su co m portamiento as asii ntótic ntóticoo. Al momento de identificar diferentes relaciones entre funciones y recursos, podemos agrupar los comportamientos resultantes en fa m i lias de f un unciones ciones ciones, dependiendo de su comportamiento asintótico, y les asignaremos un or den de c omplejidad O. La notación O-grande no toma en cuenta los factores constantes, es decir, i gn gnor or oraa s i s e ha ce u na m e jor o p e or i m plement plementaación de dell al algg orit oritmo mo mo, además de i nd ndee pe pendizarlo ndizarlo de l o s dat datos os de en entt r ada de dell al algo go goritmo ritmo ritmo.. Como utilidad de aplicar este concepto es en encc o ntr ntraar un l í m ite s up uperior erior de dell t i empo de e je cución cución, es decir, el pe peoo r c a so so. (Tovar, 2012).

Co ta s uperior a sintótica Cota superior asintótica es otra manera de nombrar a la notación O. Lo que se busca es g ar arant ant antiza iza izarr qu quee e l t iemp iempoo de e je cución de u n a lg lgoo r itmo s i empre s e a m enor a u na co cota ta o l í m ite s u perior perior. Con esto, se sabe que, en el peor de los casos, este algoritmo tendrá un tiempo de ejecución que será proporcional a la función lineal N. Lo importante en este tipo de análisis es poder encontrar una función que acote el crecimiento que, en el peor de los casos, tendrá la complejidad del algoritmo.

Al conjunto de funciones que acotan dicho crecimiento lo llamamos O( g (x)) donde x representa la can anttidad de e l emen ementos tos q u e s e v an a pr proocesar y g(x) es c ual ualqq uier cot otaa s u perior de la fu nción de com plejid plejidad ad de dell al algg or oritmo. itmo. Más formalmente, lo planteamos de la siguiente manera: sea f(x) la función que expresa la complejidad de un algoritmo, entonces la expresión f(x) pertenece a O(g(x)), significa que f(x) crece, a lo sumo, tan rápido como cualquiera de las funciones g del conjunto O. (Sznajdleder, 2012, p. 523). Om may ay ayúú scu scula la para denotar aquella función que indique el límite superior de crecimiento de una función. Es evidente notar que el orden será definido por el término más importante de la función. Esto significa que, ante distintas funciones, se hará énfasis en el término que le da el grado a la función analizada. Este término es el más do dom m in inante ante y representa la t as asaa de c r ecimie ecimiento nto q ue in inter ter teresa esa an anal al alizar. izar.

Como co nclusión, podemos decir que los algoritmos polinomiales son “buenos” algoritmos y los algoritmos exponenciales son “malos” algoritmos.

2B 2021 Page 2

justada sintótica Co ta i nferior asintótica y co ta ajus tada a sin tótica Si bien es de utilidad analizar el peor de los casos y conocer el límite superior (el cual no será superado), también es útil, a veces, conocer el límite inferior, es decir, el m e jor de l os casos asos. Asimismo, se puede querer expresar que una función tiene la misma tasa de crecimiento que otra. Entonces, se encuentra la notación Ω ( g ( x)) para denotar una co ta i nferior as asii ntótica ntótica, donde se indica que una función g(x) crecerá más lento o, a lo sumo, tan rápido como f(x). Esto quiere decir que el algoritmo analizado no se comportará mejor que una función. En otras palabras, el tiempo de ejecución será siempre mayor o, a lo sumo, igual que el de esa función. También, se encuentra la notación Θ(( g( g(x)) x)), para denotar una cota aj ajust ust ustaada a s i ntótica ntótica. Por esto, si se dice que u na f un uncción f (x) e s Θ(( g(x)) g(x)), significa que la función f(x) tendrá la misma tasa de crecimiento que g(x). A modo de conclusión, el análisis de los algoritmos es de vital importancia para poder decidir, cuando se tienen varios algoritmos, cuál es el que más conviene, cuál es el m e jor y cuál se a de decc úa mejor a las distintas necesidades. Asimismo, el análisis de los algoritmos permite ant antic ic iciparse iparse y saber cu ál s e rá e l comp omportamiento ortamiento de u n alg algoor itmo en el peor de los casos.

Co nc eptos para tener en cu enta nceptos • Un programa que se va a ejecutar m u y p o cas v ec eces es hace que nuestro foco deba estar en la codificación y la depuración del algoritmo, donde la complejidad no es el factor crítico a considerar. empo, seguramente, será m a nt ntenido enido p or v a rias pe perr sonas en el curso de su vida útil. Esto hace que los factores que debemos considerar sean los que se • Un programa que se utilizará por m u c ho t i empo leg i bilidad bilidad; incluso, si la mejora de ella impacta en la complejidad de los algoritmos empleados. relacionan con su leg • En un programa que únicamente va a trabajar con dat datoo s p eq eque ue ueños ños (valores bajos de N), el orden de complejidad del algoritmo que se use suele ser irrelevante. • Un programa de b aj ajaa c omplejidad mplejidad, en cuanto a tiempo de ejecución, suele demandar un alto consumo de memoria y viceversa. Esto es una situación que debemos evaluar para entender cómo impactan ambos factores. lculo ulo numér umérico ico hace que debamos tener en cuenta más factores que su complejidad o, incluso, su tiempo de ejecución. En estos casos, debemos considerar la precisión • Un programa o r i entado al cá lc del cálculo, el máximo error introducido en cálculos intermedios, la estabilidad del algoritmo, etcétera.

1.5. Problema de búsqueda estática Sznajdleder define: Problema de la búsqueda estática. Dado un entero X y una matriz A, devolver la posición de X en A o una indicación de que no está presente. Si X aparece más de una vez, devolver cualquiera de las apariciones. La matriz A nunca es modificada.

Esto implica, también, que no s e p r es esentar entar entaráán i nsercion serciones es c on nue uevo vo voss e l ementos o e lilimin min minaaciones ciones. Por esto, no será necesario tener en cuenta el tiempo insumido en ordenar la estructura posterior a la inserción o eliminación.

Tipos d e b úsqueda nterna: erna: Cuando los elementos entre los que buscamos están almacenados en la memoria (array). • Int erna:: Cuando los datos entre los que buscamos están almacenados en un dispositivo externo; en este caso, la búsqueda se realiza a partir de un determinado campo denominado c am ampp o c la lave ve ve. • E x t erna En cualquier caso, bu buss car u n det determinado erminado e l emento emento, en un array o en un archivo, es encontrar la posición del array o del archivo en que se encuentra almacenado ese elemento, o bien, detectar que dicho elemento no pertenece al array o al archivo en el que se busca.

Mét odos étodos A l g or oritmo itmo de b ús úsqueda queda s e cuencial Es un método que consiste en comparar cada elemento de una estructura con el elemento que se quiere encontrar. Esto supone que no e s ne necc e sari sarioo t ener u n a e s t ructura o rdena rdenada da da. Es evidente que, al tener que transitar por todos los elementos, e s p o c o e f iciente iciente. Además, este algoritmo puede terminar en dos estados: con éxito (se encontró el elemento buscado) o sin éxito (no se localizó el elemento buscado). De todas maneras, la mayoría de los algoritmos de búsqueda se basan en él.

En el peor de los casos, se tendrá que transitar por todos los elementos hasta llegar al último. Por lo tanto, es de orden lineal O( O(nn) . Esto sucede tanto en un caso exitoso (cuando el elemento buscado se encuentra y está en la última posición), como en un caso sin éxito (cuando no se logra encontrar al elemento buscado y se tuvo que recorrer toda la estructura). El mejor de los casos corresponde a encontrar el elemento buscado en la primera posición. En promedio, se podrá obtener un caso con éxito recorriendo la mitad de la estructura, es decir, n/2, por lo que este algoritmo es de or den l i neal O ( n). A l g or oritmo itmo de b ús úsqueda queda b i naria o di c ot otómica ómica Este algoritmo parte de una estructura que está ordenada. Es un algoritmo mucho más eficiente, debido a que va subdividiendo la estructura en mitades hasta encontrar el elemento buscado o evidenciar que dicho elemento no se encuentra. Este método está basado en la técnica di divv i de y v e ncer nceráás.

El procedimiento del algoritmo es bastante sencillo y consta de los siguientes pasos, si asumimos que la estructura está ordenada de menor a mayor: 1- se comienza el proceso en el elemento central de la estructura (en caso de que la cantidad de elementos sea impar) o casi central (en caso de que la cantidad de elementos sea par). Es decir, se divide a la estructura en dos mitades; 2- se verifica s i e l el elee m e nto b u sc scado ado c orr orresponde esponde al e l e me mento nto c e ntral ntral, en cuyo caso, fi na naliza liza e l pr proce oce oceso so so. En caso contrario, se corrobora si el elemento buscado es mayor o menor a dicho elemento central. Si el elemento que se intenta hallar es de may mayoo r v alor que el elemento central, se descarta la primera mitad. Si el elemento que se busca es de m e n or v alor que el elemento central, se descarta la segunda mitad; y, por último, 3- con la mitad no descartada, se comienza el proceso de nuevo, desde el primer paso. S

t

t

d

h t 2B 2021 Page 3

t

l l

t b

d

h t

d

bd d

l

t t

l

l l

Se r e p ite e ste m ecanismo de m an anee ra s u cesiva hast astaa e nc ncontrar ontrar al e l e me mento nto b u sca scaddo o has asta ta q u e n o s e pu puee da s ubd ubdividir ividir m ás l a e s truct ructura ura ura, en cuyo caso se concluye que el elemento no se encuentra. Programáticamente, este algoritmo se resuelve, inicialmente, teniendo referencias a los extremos y el centro de la estructura. Como muestra la figura 1, si el elemento que se busca está en el centro de la estructura, se concluye entregando el valor almacenado en la posición central de esta.

Si el elemento que se busca es mayor que el elemento central, se descarta la primera mitad y se refrescan las referencias: • MAX continúa como estaba;

• MIN = MED + 1; • se calcula el nuevo centro MED = (MAX - MIN) / 2.

Fi g ura 1 : R e ferencia ferenciass us usaadas e n l a b ú s q ueda b i naria e n u n v e cto torr

En la figura 2, se observa que, si el elemento que se busca es menor que el elemento central, se descarta la segunda mitad y se refrescan las referencias: • MIN continúa como estaba; • MAX = MED – 1; • Se calcula el nuevo centro MED = (MAX - MIN) / 2.

Fi g ura 2 : V e ct ctor or f inal, cuando el e l emento a bbus us usca ca carr es m ayor al el elee me mento nto ce ntral

En el mejor de los casos, al iniciar el proceso, el elemento en la posición central corresponde al elemento buscado. Pero es muy poco probable que esto ocurra. En el peor de los casos, se tienen dos situaciones:

• se podrá conseguir un estado de éxito y encontrar al elemento buscado en la última iteración. Se hará, por consiguiente, una cantidad de iteraciones igual a Log(n). La última iteración corresponderá a un rango de un solo elemento; y • se podrá conseguir un estado sin éxito, es decir, realizar todas las iteraciones y detectar que no coinciden con el elemento buscado. Se harán, por consiguiente, una cantidad de iteraciones igual a Log(n)+1. La última iteración corresponderá a un rango nulo, es decir, no contendrá ning...