Programacion 2 - La Eficiencia De Los Algoritmos

La Eficiencia de los Algoritmos. Introducción Una historia casi real: Una pequeña empresa de ex-alumnos de Ingeniería Informática de la Uned ha desarrollado un sistema de visión artificial capaz de reconocer el rostro de una persona y determinar si coincide con alguno de los almacenados en una base datos. La máquina ha tenido muy buena aceptación como sistema de control de accesos (cerradura automática) y varias empresas lo han comprado. El algoritmo de comparación de caras se puede ejecutar, en principio, en un ordenador personal de gama baja. El tiempo que el sistema tarda en procesar una imagen depende del número de imágenes n almacenadas en la base de datos Tras haber vendido varios sistemas a pequeñas empresas, varias medianas empresas y un gran hospital se han interesado por él y lo han comprado. Sin embargo, al poco tiempo se reciben quejas de éstas empresas en relación con el excesivo tiempo que requiere el proceso de reconocimiento. Ante esas quejas, los desarrolladores realizan unas pruebas de velocidad de reconocimiento para distintos tamaños de base de datos, siempre ejecutando el programa de reconocimiento sobre el ordenador de gama baja mencionado. Los resultados son: Número de imágenes en la base de datos 10 50 100 200 Tiempo de reconocimiento (segundos) 1 25 100 400 Es indudable que el tiempo de reconocimiento para base de datos de 100 imágenes o más es inaceptable, para un sistema con 200 personas con acceso autorizado cada persona ha de pasar más de seis minutos ante la cámara. Se dedice probar a sustituir el ordenador por uno con procesador Pentium y más memoria en lugar del humilde 386 original. Las pruebas con el nuevo ordenador arrojan los siguientes resultados: Número de imágenes en la base de datos 10 50 100 200 Tiempo de reconocimiento (segundos) 0,2 5 20 80 El tiempo se ha reducido, sin embargo es de más de un minuto todavía para empresa de 200 personas, además si se prueba con una de 1000 el tiempo es de 2000 segundos (algo más de media hora), lo cual es claramente inaceptable. Puesto que se desea poder vender el sistema a grandes organismos y empresas, los nuevos empresarios deciden aplicar los conocimientos aprendidos en Programación II y Programación III y tratar de desarrollar un algoritmo de reconocimiento más eficiente. Las pruebas sobre el ordenador de bajas prestaciones dan ahora el resultado: Número de imágenes en la base de datos 10 50 100 200 Tiempo de reconocimiento (segundos) 0,3 2,82 6,64 15,3

Con este nuevo algoritmo el tiempo para 200 puede ser aceptable, todavía algo alto. Probando con el ordenador de gama alta se obtiene: Número de imágenes en la base de datos 10 50 100 200 Tiempo de reconocimiento (segundos) 0,07 0,56 1,33 3,06 Los tiempos son ahora muy buenos. Deciden adoptar el nuevo algoritmo e instalar los ordenadores más potentes. Instalan su máquina en grandes empresas, hospitales, ministerios, ...

Moralejas a) Ante un mal algoritmo el aumento de potencia del procesador no conduce a mejoras importantes, especialmente cuando el problema a tratar crece. El cambio de ordenador no consigue reducir el tiempo a un valor aceptable para n alto. b) Un algoritmo mejorado produce buenos resultados incluso para procesador poco potente. El segundo algoritmo del ejemplo ha logrado colocar el tiempo en valores casi aceptables incluso para ordenador de poca potencia c) Un algoritmo mejorado permite aprovechar mejor las ventajas de un procesador más potente de forma que es posible tratar en un tiempo de proceso inferior problemas más complejo. Supóngase que se limita el tiempo aceptable de reconocimiento en 3 segundos. Con el primer algoritmo, ordenador lento se tiene un n máximo aceptable de 17. Al pasar, con ese mismo algoritmo a ordenador rápido se tiene un n máximo de 39. Con el segundo algoritmo y ordenador lento n es 52 y pasa a valer 200 para ordenador rápido. Es decir, en el primer caso al cambiar de procesador se logra aumentar en un factor de poco más de dos el tamaño del problema tratable en un tiempo dado, en el segundo caso en un factor de casi cuatro. Y ahora las áridas ecuaciones El ingeniero usa las matemáticas fundamentalmente para comunicarse con los de su especie evitando largas parrafadas como las del apartado anterior. Lo explicado en el ejemplo puede traducirse a: El primer algoritmo es de orden cuadrático, es decir, si f(n) es la función que determina el tiempo de ejecución en función del tamaño n de la base de datos se tiene que: , en concreto 2 2 f(n)=0,01n para el primer ordenador. Para el segundo ordenador f(n)= 0,002n . El segundo algoritmo es de orden n.log n. En concreto para el primer ordenador la función de coste es f(n)=0,01.n.lg n, y para el segundo 0,002.n.lg n. Cuando se aprende el lenguaje matemático la economía de espacio para una explicación es evidente. Por todo ello se ha de realizar el esfuerzo mínimo necesario para comprender los conceptos matemáticos que permitan expresar ideas de forma simple y precisa. No se ha de caer en el extremo opuesto, es decir, usar las matemáticas de forma extensa, abusiva y aburrida sin que aporten nada especial a la comprensión básica del problema. ¿ Que és orden de complejidad de un algoritmo ?

El orden de complejidad de un algoritmo en cuanto a tiempo de ejecución es una expresión matemática que permite indicar cómo crece el tiempo de ejecución cuando crece el tamaño del problema que resuelve el algoritmo. Se ha de insistir en dos puntos en esta definición: •

Es una indicación del crecimiento del tiempo de ejecución cuando crece el tamaño del problema. ¿ Qué es "tamaño de problema " ?. Infinidad de algoritmos resuelven problemas en los que el tiempo de resolución varía cuando, sin variar la esencia del propio algoritmo, si varía uno o varios parámetros que determinan el tamaño de los datos de entrada. Por ejemplo, en un algoritmo de ordenación que ordene los registros de una base de datos, o los elementos de un vector etc. el tiempo de ejecución crece cuando crece el número de registros o elementos a ordenar.

•

Indica cómo crece el tiempo de ejecución. Cuando se habla de coste asintótico no se trata de expresar una medida absoluta del tiempo de ejecución del algoritmo. Se trata de expresar cómo varía el tiempo de ejecución cuando el tamaño del problema crece. Supóngase, por ejemplo, que un algoritmo de ordenación de vectores es de orden cuadrático. Es decir, que siendo f(n) el tiempo de ejecución necesario para ordenar n elementos del vector, se tiene .A partir de esta información no se puede determinar cuánto tiempo se tardará en ordenar un vector de tamaño dado. Pero sí se se puede decir que, cuando el tamaño n del vector a ordenar crece, el tiempo de ejecución crece cuadráticamente. Así si se nos dice que el tiempo necesario para ordenar un vector de 100 elementos es de 1 segundo se puede concluir que el tiempo necesario para ordenar uno de 1000 elementos será del orden de 100 segundos. Es decir, al multiplicar por 10 el tamaño del problema el tiempo se ejecución se multiplica por 102

Se han de tener en cuenta otros factores al analizar el coste de ejecución de un algoritmo. El contenido de los datos de entrada influye también en el tiempo de ejecución de muchos algoritmos. Así, por ejemplo, el tiempo de ejecución de un algoritmo de ordenación de vectores puede ser muy distinto según el vector contenga datos ya ordenados, o casi ordenados, o no. En general, cuando se hable de coste asintótico, se refiere al caso de contenido de datos más desfavorable, es decir el caso peor. En la asignatura se trata casi siempre el coste desde el punto de vista asintótico y para el caso peor. Esto no significa que, para problemas concretos, este tratamiento sea siempre el más adecuado y se ha de razonar con sentido común en casos como esos. Dos ejemplos ilustrarán esto: 1. Se dispone de dos algoritmos que tratan vectores de tamaño variable, determinado por un parámetro n, uno de coste f1(n)=0,001 n2 y otro de coste f2(n)=0,1n. Los algoritmos se van a utilizar para tratar vectores de tamaño 50 o menor ¿ Cúal es el más apropiado ?. Desde el punto de vista de coste asintótico es evidente que el mejor algoritmo es el segundo, de coste lineal. Sin embargo para vectores de tamaño 50 se tiene que el coste del primer algoritmo es 2,5 y el del segundo 5. Luego para tamaño 50 o menor es preferible el primer algoritmo aunque su coste asintótico sea peor. En la figura adjunta puede comprobarse que el primer algoritmo es en

realidad mejor para tamaño de problema menor de 100.

2. Un algoritmo de ordenación tiene coste cuadrático en el caso peor, sin embargo cuando se aplica sobre vectores ordenados el coste es lineal. Si al aplicarlo sobre un serie larga de vectores la probabilidad de que el vector sobre el que se aplica esté ya ordenado es muy alta, la función de coste asintótico para caso peor deja de ser útil. Es preferible utilizar una función de coste medio basada en la probabilidad de aplicación sobre vector ya ordenado. Este apartado sólo ha pretendido servir de introducción al estudio de costes de ejecución desde un punto de vista práctico sirviendo de complemento al apartado 1.1 de Peña. En este apartado se exponen las ideas básicas a tener en cuenta en el análisis de coste: •

• • •

El análisis detallado (tal y como el realizado en el texto para el algoritmo de ordenación por el método de selección), es demasiado tedioso y costoso en tiempo ( a su vez) como para ser de aplicación práctica normal. Por ello se utiliza el estudio de coste asintótico aproximado. Los factores que influyen en el tiempo de ejecución de un algoritmo son: tamaño de los datos, contenido de los datos e implementación concreta del algoritmo (máquina y compilador) Se estudia normalmente el coste para caso peor Dos implementaciones diferentes del mismo algoritmo sólo diferirán en cuanto a tiempo de ejecución en una constante multiplicativa. En el ejemplo del inicio de esta página las dos implementaciones (sobre dos máquinas distintas) de cada uno de los algoritmos se diferencian en un factor de 5, es decir una máquina es 5 veces más rápida que la otra. Sin embargo esto no cambia el tipo (en cuanto a coste asintótico) de cada uno de los algoritmos.

Medidas asintóticas y órdenes de complejidad Entre las personas que comienzan el estudio de PROGRAMACION II siguiendo el texto recomendado ("Diseño de Programas" de Ricardo Peña Marí), uno de los primeros traumas suele provocarlo la definición:

Este tipo de definiciones hace que muchas personas que habían decidido sacrificar su vida dedicándose a la ingeniería práctica, la que resuelve problemas, decidan que el esfuerzo no merece la pena. Espero que esta cita ayude a reintegrarlos al redil: "Si no fuera por las compulsiones de los ingenieros, la humanidad nunca hubiera llegado a conocer la rueda, y se habría conformado con el trapezoide porque algún neandertal especialista en marketing habría convencido a todo el mundo que tenía una mayor capacidad de frenada que la rueda". Scott Adams, "El principio de Dilbert" Consideremos pues, que a alguien le ha de tocar sacrificarse por el bien de la humanidad y volvamos a lo nuestro. Como ya se ha indicado anteriormente, las matemáticas son para el ingeniero un medio de comunicación rápida y precisa con los de su especie (ingenieros, físicos y demás gente del gremio). Para que esa comunicación sea efectiva se han de tener la capacidad de entender los conceptos prácticos que se esconden tras una definición abstracta o una ecuación. En este apartado se intentará "diseccionar" la definición anterior de forma que se traduzca a conceptos prácticos. En todo caso se ha de considerar que para abordar el estudio de Programación II es conveniente repasar, o abordar el estudio, de algunos conceptos matemáticos. Para el estudio de medidas asintóticas el concepto de límite matemático de funciones y sucesiones y los métodos de cálculo de límites son herramientas necesarias que pueden repasarse en cualquier texto de Análisis Matemático. Como ya se ha indicado en el apartado previo cuando se analiza el coste asintótico, en cuanto a tiempo de ejecución, lo que interesa es ver COMO CRECE el tiempo al crecer el tamaño del problema. Consideremos varios algoritmos (f1,f2, f3 ) cuyo tamaño de problema depende de un parámetro n y cuyo tiempo de ejecución se presenta, para distintos valores de n, en la siguiente tabla. En la misma tabla se representa la función f(n)=n2. n n2 f1 f2 f3

10 100 1.000 10.000 100 10.000 1.000.000 100.000.000 81 180 10.080 1.000.080 110 100.100 100.001.000 100.000.010.000 50 500 5000 50000

Si se observa cómo crece el coste para valores altos de n. En concreto cuando n se multiplica por 10 se tiene: • • •

f1 se multiplica por 100 (102) aproximadamente. f2 se multiplica por 1000 (103) aproximadamente. f3 se multiplica por 10 (101).

Luego f1 tiene un crecimiento de tipo cuadrático, f2 de tipo cúbico y f3 de tipo lineal. Si se considera, por ejemplo, la función f(n)=n2 se pueden definir tres conjuntos de funciones basados en f : •

El conjunto de las funciones que crecen asintóticamente de forma igual o menos rápida que n2,

•

este conjunto (infinito en este caso) de funciones se denota por El conjunto de las funciones que crecen asintóticamente de forma igual o más rápida que n2

•

este conjunto (infinito en este caso) de funciones se denota por El conjunto de las funciones que crecen asintóticamente de forma igual a n2 este conjunto (infinito en este caso) de funciones se denota por

Es evidente que tiene que f1 pertenece a pertenece sólo a

es la intersección de los conjuntos y también a

ya

y

. En el ejemplo de la tabla se

ya que crece de forma cuadrática. f2

ya que crece de forma cúbica, es decir más rápidamente que n2 . f3 pertenece

ya que crece de forma lineal. Es decir más lentamente que n2 .

sólo a

En general, se utilizará el orden de tipo , ya que se trata de buscar una cota superior al crecimiento del coste del algoritmo. También se utiliza frecuentemente el tipo que permite conocer el coste asintótico exacto del algoritmo. Sabiendo que, en realidad, las funciones f1, f2 y f3 están definidas por: f1=0,01n2+ 80 f2=0,1n3+n f3=5n, en la tabla siguiente se ha calculado el cociente entre los valores que toman las funciones f1,f2 y f3, respectivamente y el valor que toma n2 para distintos valores de n. n 10 100 1.000 10.000 100.000 2 f1/n 0,810 0,018 0,010 0,010 0,010 f2/n2 1,100 10,010 100,001 1.000,000 10.000,000 f3/n2 0,500 0,050 0,005 0,001 0,000 Puede observarse que, cuando n tiende a infinito: • • •

f1/n2 tiende a un valor constante (0,010). f2/n2 crece indefinidamente, es decir, tiende a infinito f3/n2 decrece indefinidamente, es decir, tiende a cero.

Se han presentado con un ejemplo las condiciones suficientes que permiten determinar cuando una función cualquiera g(n) es del orden (de los distintos tipos de orden) de otra dada f(n) (en el ejemplo f(n)=n2 ). Algunas de estas condiciones son: Propiedad 1

O sea, g(n) crece "más despacio" que f(n). Propiedad 2

O sea, g(n) crece "al mismo ritmo" que f(n) Propiedad 3

O sea g(n) crece "más deprisa" que f(n) Normalmente se trata de buscar una función sencilla f(n) que acote superiormente el crecimiento de otra g(n). Para ello es conveniente tener en cuenta una regla que se obtiene al combinar las propiedades 1 y 2 anteriores: Propiedad 4

Para el ejemplo tratado, si se trata de ver si las funciones f1, f2 y f3 son, respectivamente, de orden cuadrático, es decir si pertenecen a

se tendrá:

•

que f1 pertenece a , puesto que el límite cuando n tiende a infinito del cociente de f1 entre n2 es una constante (0,010)

•

que f2 no pertence a

, puesto que ahora el límite es infinito

•

que f3 si pertenece a

, puesto que ahora el límite es cero.

Si lo que se desea es conocer si alguna de las funciones es de orden cuadrático exacto, es decir, si pertenece a entonces el límite ha de ser una constante positiva no nula, y por tanto, la única función de orden cuadrático exacto es f1. Y ahora, una explicación que permita entender mejor la definición 1.1 expuesta al principio de esta página, decir que:

es equivalente a decir que

o lo que es lo mismo: Se puede encontrar un número real k no negativo y un número natural n0 , tales que para todo número natural n>n0 es g(n)<=k.f(n). Esto es lo que indica la definición 1.1, si bien de una forma más general ya que esta definición puede aplicarse incluso en casos en los que los límites no existen (el ejercicio 1.2 de Peña 1ª Ed expone un ejemplo):

Expresado en palabras: Dada una función de un parámetro n, natural y que toma valores no negativos, se puede definir un conjunto (normalmente infinito) de funciones, que se define como el conjunto de funciones del orden de dicha función. Este conjunto está formado por todas las funciones para las que es posible encontrar una constante real positiva c, y un número natural n0 tal que para todos los números naturales mayores que n0 se cumple que dicha función no supera en valor a c.f(n). La constante c y el número natural n0 deberá particularizarse, en general, para cada una de las funciones. Definiciones análogas se tienen (ver texto de Peña) para los otros tipos de orden.

Cálculo de coste en algoritmos iterativos Cuando se analiza la eficiencia, en tiempo de ejecución, de un algoritmo son posibles distintas aproximaciones : desde el cálculo detallado similar al realizado en Peña 1.1 ( que puede complicarse en muchos algoritmos si se realiza un análisis para distintos contenidos de los datos de entrada, casos más favorables, caso peor, hipótesis de distribución probabilística para los contenidos de los datos de entrada etc ) hasta el análisis asintótico simplificado aplicando reglas prácticas (ver Peña 1.4). En estos apuntes se seguirá el criterio de análisis asintótico simplificado, si bien nunca se ha de dejar de aplicar el sentido común. Como en todos los modelos simplificados se ha mantener la alerta para no establecer hipótesis simplificadoras que no se correspondan con la realidad. En lo que sigue se realizará una exposición basada en el criterio de exponer en un apartado inicial una serie de reglas y planteamientos básicos aplicables al análisis de eficiencia en algoritmos iterativos, en un segundo apartado se presenta una lista de ejemplos que permitan comprender algunas de las aproximaciones y técnicas expuestas.

Criterios 1) En general, el análisis se realizará sobre ejemplos expresados según el esquema básico de un algoritmo iterativo: Inicializar; mientras B hacer Restablecer; Avanzar; fmientras

Se ha de tener en cuenta que cada uno de los bloques básicos: ( Inicializar, Restablecer, Avanzar, incluso el cálculo de la expresión lógica B) pueden a su vez estar formados por una combinación de cada una de las estructuras fundamentales de un lenguaje imperativo: • • •

SECUENCIA: Composición secuencial de instrucciones: S1, S2, ..., Sn ALTERNATIVA: Instrucciones condicionales del tipo: si B entonces S1 si no S2 fsi, o del tipo más general: caso B1 → S1 caso B2→ S2....... caso Bn→ Sn fcaso ITERACION: Iteración, en sus varias formas: mientras B hacer S fmientras, repetir S hasta B, para i desde E1 hasta E2 hacer S fpara, ... Cualquiera de estas formas es transformable a una expresión del primer tipo (bucle "mientras").

( Es conveniente repasar la primera parte del capítulo 4 de Peña ).

2) Para análisis asintótico se aplicarán las reglas de la suma y del producto (Peña Cap 1). La regla de la suma:

dice que el orden suma de órdenes de varias funciones es igual al orden de la función suma e igual al orden de la función máximo de ambas. En la práctica si se tiene una secuencia de operaciones en un algoritmo: S1, S2, ..., Sn se ha de determinar primero el orden asintótico de cada una de estas operaciones. Entonces el orden de la secuencia es igual al orden de la suma o al orden del máximo. Supóngase, por ejemplo, que en un algoritmo se realizan tres operaciones secuenciales con un vector de tamaño n: •

Asignar un valor dado en el elemento de índice 1. Operación de coste constante o con función de coste de orden constante (

)

•

Sumar todos los elementos del vector. Operación de coste lineal (

•

Ordenar el vector con un algoritmo de tipo cuadrático (

)

)

La secuencia completa será de orden cuadrático puesto que:

Expresado con palabras: cuando el tamaño del problema (n) crece la operación que determina el coste asintótico es la más costosa, o sea la de mayor orden, en este caso la de orden cuadrático. El tiempo de ejecución de esta secuencia de operaciones se multiplicará por cuatro, aproximadamente, al doblar el

tamaño del problema. En este crecimiento del tiempo la operación que influye de una forma determinante es la de coste cuadrático. La regla del producto :

es de aplicación en procesos iterativos. El orden de la función de coste de un proceso iterativo es igual al producto del orden de la función que indica el número de iteraciones en función del tamaño del problema y del orden de la función de coste de la operación interna en el bucle. Este producto de órdenes es , a su vez, igual al orden del producto de la función que expresa el número de iteraciones y la de coste de las operaciones internas al bucle (no confundir "producto del orden" con "orden del producto"). Considérese un ejemplo: Un algoritmo ha de ordenar cada una de las filas de una matriz cuadrada de n x n elementos. El bucle iterativo es: para i:= 1 hasta n hacer ordenar fila i; fpara

o su equivalente en la forma básica "mientras": i:=1; mientras i<=n hacer ordenar fila i i:=i+1; fmientras

Es inmediato que el número de repeticiones de la operación interior es de coste lineal o sea la función de coste pertenece a , supóngase que para ordenar la fila se utiliza un algoritmo de tipo cuadrático. Entonces el coste asintótico de la operación será de tipo cúbico , ya que:

Es decir, el tiempo de ejecución se multiplicará aproximadamente por 8 cuando la matriz pase de n x n a 2n x 2n. Por último indicar, que para la ALTERNATIVA, la regla a aplicar será la de analizar el coste de cada una de las operaciones alternativas y tomar la de mayor coste asintótico como coste de la estructura total (análisis en el caso peor)

Ejemplos 1) Ordenación por selección Entre los métodos elementales de ordenación de vectores se encuentra el algoritmo de selección: para i desde 1 hasta n hacer imin:= índice del mínimo elemento del vector en v[i..n] intercambiar(v[imin],v[i]); fpara

Es decir, el método se basa en buscar en cada iteracción el mínimo elemento del subvector situado entre el índice i y el final del vector e intercambiarlo con el de índice i. Tomando la dimensión del vector n como tamaño del problema es inmediato que el bucle se repite n veces y por tanto la función que da el número de repeticiones es de tipo lineal ( vez como:

). La operación interior al bucle se puede desarrollar a su

imin:=i; para j desde i+1 hasta n hacer si v[j]
Se trata de una secuencia de tres operaciones, la segunda de las cuales es, a su vez, una iteración. La primera (asignación) y la tercera(intercambio) pueden considerarse de coste constante. La segunda es un bucle que internamente incluye una operación condicional que en el peor caso supone una operación de coste constante ( ) (en el peor caso y en el mejor, puesto que la comparación se ha de realizar siempre ) y el número de repeticiones de esa operación es de tipo lineal, ya que se realiza n-(i+1) veces, y por tanto, al crecer n, el número de veces crece proporcionalmente a n. Luego será de coste

.

= . Éste será entonces el coste de la secuencia completa (sucesión de dos operaciones de coste constante y una de coste lineal) El algoritmo total será entonces de orden

.

=

Es interesante observar que en este algoritmo el contenido de los datos de entrada , no influye en el coste del algoritmo. En efecto se puede comprobar (aplicar el algoritmo sobre varios vectores ejemplo), que se ejecutan de forma completa ambos bucles tanto para vector desordenado como para vector ordenado 2) Ordenación por inserción Otro de los métodos simples de ordenación de vectores es el de Inserción: para i desde 2 hasta n hacer x := v[i]; j : = i-1; mientras j>0 y v[j]> x hacer v[j+1]:=v[j]; j:=j-1; fmientras v[j+1]:=x; fpara

Es conveniente analizar cómo funciona este algoritmo: para cada índice i se guarda en la variable auxiliar x el elemento v[i] y se comienzan a desplazar todos los elementos de índice inferior que sean de valor mayor que el v[i] original (guardado en x), cuando se encuentra un elemento de valor menor o igual que x se guarda x en el hueco libre. La mejor forma de ver como funciona es aplicarlo a vectores sencillos. Un análisis similar al realizado en el ejercicio anterior permite concluir que el algoritmo es también de coste cuadrático en el caso peor.

Sin embargo este algoritmo es de coste lineal en el caso mejor. Es decir, cuando se aplica sobre vector ya ordenado. Puede comprobarse que, en este caso, las operaciones internas al bucle interno sólo se realizan una vez en cada iteración del bucle externo. Ello es debido a que la comparación v[j]>x dará resultado falso siempre a la primera. Es decir, si en un caso concreto se ha de optar por uno de los dos algoritmos, el segundo es ventajoso si se va a aplicar sobre vectores en los que la probabilidad de que ya estén ordenados o casi ordenados sea alta. Ésta es una conclusión que va más allá del análisis asintótico, desde ese punto de vista ambos algoritmos son de coste cuadrático. 3) Máximo común divisor Un algoritmo de cálculo del máximo común divisor de dos enteros n y m es el dado por: mientras n>0 y m>0 hacer si n>m entonces t:=n mod m; n:=m; m:=t; si no m:=m mod n; fsi fmientras si n=0 devolver m si no devolver n;

O expresado en forma más simple y simétrica si se utiliza la asignación múltiple (ver Peña Cap 4, asignación múltiple ): mientras n>0 y m>0 hacer si n>m entonces :=<m, n mod m>; si no :=; fsi fmientras si n=0 devolver m si no devolver n;

Es evidente que aquí las operaciones internas al bucle son de coste constante. El problema es determinar el orden de la función que da el número de repeticiones del bucle. El análisis no es directo, el bucle acaba cuando uno de los enteros acaba tomando el valor 0. En cada iteración el elemento de mayor valor pasa a tomar el valor del menor y el menor pasa a tomar el valor del resto de la división del mayor entre el menor. Conviene ver cómo funciona el algoritmo con algunos ejemplos concretos. En estos casos una alternativa es la de buscar una función simple que acote superiormente el número de repeticiones del bucle. Se puede observar que el bucle avanza en razón al decrecimiento del mínimo de ambos valores, cuando el mìnimo alcanza el valor cero el bucle finaliza. Se puede demostrar entonces que el mínimo de ambos valores toma un valor igual o menor a la mitad del valor previo en cada iteración: Dados dos enteros x e y tales que x>=y se tiene que es siempre x mod y <= x/2 . Es decir, el valor del resto de la división es siempre menor o igual que la mitad del dividendo. En efecto: si y> x/2 entonces es inmediato que x mod y= x-y <x- x/2 = x/2;

si y<= x/2 entonces x mod y< y <= x/2 (por la propiedad del resto). Puesto que el mínimo de ambos valores se reduce al menos a la mitad en cada pasada, se tendrá que el número de repeticiones no será mayor al logaritmo en base 2 del mayor de los dos enteros. Por tanto el algoritmo es de coste logarítmico (

(log n), ya que en este caso no se puede hablar de orden exacto).

Se ha presentado este ejemplo como ilustración de dos problemas que a veces no son simples, por una parte establecer un variable que determine el tamaño del problema, en este caso puede escogerse como tamaño de problema minimo(n,m). Por otra parte, determinar el número de iteraciones de un bucle. En este caso no se puede obtener una solución general exacta, pero es posible acotar superiormente el número de iteraciones por una función apropiada. Estos dos conceptos se asocian en la llamada función limitadora (ver Peña Cap 4), que en este caso podría ser : T(n,m)= minimo (n,m); Existe otra forma menos eficiente de algoritmo de máximo común divisor (algoritmo de Euclides), la dada por: mientras n distinto de m hacer si n>m entonces :=; si no :=; fsi fmientras devolver n;

Se deja al lector el análisis del coste de este algoritmo y la búsqueda de una función limitadora apropiada para él. 3) Serie de Fibonacci La sucesión de Fibonacci se define inductivamente como:

Esta sucesión aparece frecuentemente en matemáticas e informática. Un algoritmo para el cálculo del término de orden n de la sucesión puede ser: i:=1; j:=0; para k desde 1 hasta n hacer j:=i+j; i:=j-i; fpara devolver j;

En principio se puede deducir que es un algoritmo de coste lineal, teniendo en cuenta que el bucle se repite n veces y las operaciones internas son elementales, es decir de coste constante. ¿ Son

elementales ?. Si se ejecuta este algoritmo en un computador que utilice enteros de 32 bits, se comprobará que la suma i+j provocará desbordamiento para valores de n relativamente bajos (del orden de 50). Así el cálculo de un término n mayor que 50 de la serie de Fibonacci obliga a operar con enteros de más precisión. De hecho para calcular un término del orden de 10000 de la serie de Fibonacci sería necesario almacenar enteros de miles de dígitos. Por tanto la operación de suma deja de poder ser considerada una operación elemental para n no excesivamente grande y será una operación que dependerá del tamaño del problema. Este ejemplo se presenta simplemente como ilustracción de la necesidad de evaluar con cuidado cuándo una operación se puede considerar de coste constante. 4) Comentarios sobre el algoritmo "quicksort" Uno de los algoritmos avanzados para ordenamiento de vectores es el conocido como método rápido, de Hoare o "quicksort". Este método se presenta en el apartado 4.4 de Peña, 1ª Edición. También se pueden estudiar las versiones recursiva e iterativa y un análisis del coste en el texto de Niklaus Wirth (padre de Pascal y Modula 2): "Algoritmos + Estructuras de Datos=Programas", publicado por Ediciones del Castillo. Los algoritmos de ordenación de vectores se pueden clasificar en dos grupos: a) Los simples: Insercción, Selección, Intercambio o "burbuja"... De coste cuadrático, n.n b) Los avanzados: Shell, Montículo o "Heapsort", Rápido o "Quicksort"... De orden n.log n Si se realiza un análisis para caso peor del "Quicksort" se obtiene coste cuadrático. Sin embargo al aplicarlo sobre la mayoría de los vectores el coste es de orden n.log n . De hecho es uno de los algoritmos de ordenación más rápidos conocidos. La explicación radica en que en este caso no es apropiado estudiar coste para el caso peor, ya que un vector con contenido de datos que den lugar al caso peor será muy improbable si se elige el pivote de comparación del algoritmo de forma apropiada. Es, por tanto, más importante su comportamiento en el caso promedio. Este ejemplo se incluye como ilustración de un caso en el que el análisis de caso peor no es el más apropiado.

Cálculo de coste en algoritmos recursivos Introducción Retomando aquí el socorrido ejemplo del factorial, tratemos de analizar el coste de dicho algoritmo, en su versión iterativa, codificada en MODULA 2, se tiene: PROCEDURE Factorial(n : CARDINAL) : CARDINAL BEGIN VAR Resultado,i : CARDINAL ; Resultado :=1 ; FOR i :=1 TO n DO Resultado :=Resultado*i ; END ; RETURN Resultado END Factorial ;

Aplicando las técnicas de análisis de coste en algoritmos iterativos de forma rápida y mentalmente (es como se han de llegar a analizar algoritmos tan simples como éste), se tiene: hay una inicialización antes de bucle, de coste constante. El bucle se repite un número de veces n y en su interior se realiza una operación de coste constante. Por tanto el algoritmo es de coste lineal o expresado con algo más de detalle y rigor, si la función de coste del algoritmo se expresa por T(n), se tiene que T(n)

.

Una versión recursiva del mismo algoritmo, también codificada en MODULA-2, es: PROCEDURE Factorial(n: CARDINAL): CARDINAL; BEGIN IF n=0 THEN RETURN 1 ELSE RETURN n* Factorial(n-1) END END Factorial;

Al aplicar el análisis de coste aprendido para análisis de algoritmos iterativos se tiene: hay una instrucción de alternativa, en una de las alternativas simplemente se devuelve un valor (operación de coste constante). En la otra alternativa se realiza una operación de coste constante (multiplicación) con dos operandos. El primer operando se obtiene por una operación de coste constante (acceso a la variable n), el coste de la operación que permite obtener el segundo operando es ??? ... es ???... : -()... : -( .... ¡ es el coste que estamos calculando !, es decir es el coste de la propia función factorial (solo que para parámetro n-1). Es decir, para conocer el orden de la función de coste de este algoritmo ¿ debemos conocer previamente el orden de la función de coste de este algoritmo ?, entramos en una recurrencia . Y efectivamente, el asunto está en saber resolver recurrencias. Si T(n) es la función de coste de este algoritmo se puede decir que T(n) es igual a una operación de coste constante c cuando n vale 0 y a una operación de coste T(n-1) más una operación de coste constante (el acceso a n y la multiplicación) cuando n es mayor que 0, es decir:

Se trata entonces de encontrar soluciones a recurrencias como ésta. Entendiendo por solución una función simple f(n) tal que se pueda asegurar que T(n) es del orden de f(n). En este ejemplo puede comprobarse que T(n) es de orden lineal, es decir del orden de la función f(n)=n, ya que cualquier función lineal T(n)= a.n +b siendo a y b constantes, es solución de la recurrencia: T(0)= b , es decir una constante T(n)= a.n+b= an-a+ b+a= a(n-1)+b+a= T(n-1)+a , es decir el coste de T(n) es igual al de T(n-1) más una constante. Una buena noticia: el planteamiento y solución de recurrencias, abordándolo desde un punto de vista general, queda fuera del programa de PROGRAMACION II. Una menos buena: sí que forma parte del programa de PROGRAMACION III (el lector interesado puede empezar a estudiarlas en "Fundamentos de Algoritmia" de Brassard y Batley, texto básico de PROGRAMACION III ). Otra muy importante: en PROGRAMACION II han de conocerse y aplicarse dos recurrencias básicas que permiten analizar el coste de muchos algoritmos recursivos, y en concreto de todos los estudiados en esta asignatura.

Dos recurrencias básicas Para el análisis de coste de los algoritmos recursivos que se abordan en PROGRAMACION II va a ser necesario conocer dos tipos básicos de recurrencia, se ha de saber también aplicar la solución de estas recurrencias a problemas concretos y , es más, se han de saber interpretar los parámetros fundamentales que intervienen en ellas. Las primera de ellas es:

( Rec 1 ) Esta recurrencia es aplicable a cualquier algoritmo recursivo en el que: a) El cálculo del caso trivial es una operación de orden polinómico nk, es decir, para k=0 una operación de coste constante, para k=1 una operación de coste lineal, para k=2 una operación de coste cuadrático etc. b) El cálculo del caso no trivial se realiza por medio de a llamadas a la propia función recursiva con tamaño de problema reducido mediante resta en un factor b. Además se realiza una operación adicional que se supone del mismo tipo (en cuanto a coste asintótico) que la de caso trivial. Al apricarla a ejemplos se comprenderán mejor estos conceptos, pero no se ha de olvidar que: a) k determina el orden de la operación de caso trivial y de la adicional de caso no trivial b) a es el número de llamadas recursivas necesarias para realizar la operación de caso no trivial, a=1 en los casos de recursividad simple, que serán los habituales. c) b es el valor en que se disminuye, por substracción, el tamaño del problema en cada llamada. Una vez identificados los valores a,b y k de un problema concreto, la solución a esta recurrencia es que la función de coste T(n) será de un orden dado por:

( Sol 1 ) La segunda recurrencia es:

( Rec 2 ) y la única diferencia básica , respecto a la primera, es que la reducción del tamaño del problema se hace por división, siendo ahora b el divisor. La solución a esta segunda recurrencia es:

( Sol 2 ) Como ya se ha indicado, la mejor forma de comprender el sentido de estas recurrencias y sus soluciones es aplicarlas a ejemplos concretos. Después, se ha de ser capaz de sintetizar la información de cara a comprender cómo influyen los parámetros a, b y k, y el tipo de recursividad (con reducción de coste por resta o por división), en el coste final del algoritmo. Por lo tanto, manos a los ejemplos.

Ejemplos 1) Factorial El algoritmo recursivo de cálculo del factorial de un número natural n se realiza recursivamente: devolviendo directamente 1 si n=0 devolviendo el producto de n y el resultado de una llamada recursiva a la propia función para parámetro n-1 si n >0 en este caso, y puesto que se reduce el problema por resta, se tiene la primera recursividad (Rec 1) con: a=1 (una sola llamada recursiva en el caso trivial) b=1 (el valor en que se disminuye el tamaño de problema) k=0 (coste constante en operaciones adicionales y trivial) Aplicando la solución (Sol 1) se obtiene 2) Suma lineal de los elementos de un vector El siguiente algoritmo recursivo devuelve la suma de los elementos de un vector v definido como vect: vector [1..n] de enteros. En realidad es una función que calcula la suma de los elementos del vector de índices entre 1 e i, si se ejecuta con i=n suma todos los elementos del vector. Para obtener la suma de los elementos de índices entre 1 e i aplica el siguiente razonamiento recursivo: si i=0 devolver 0 (suma de los elementos de un vector vacío), sin i>0 ejecutar recursivamente la propia función para sumar los elementos de índices entre 1 e i-1, entonces sumarle a este resultado el valor de v[i]: fun suma(v: vect; i:entero) dev s: entero caso i=0 -> 0 . i>0 -> suma(v,i-1)+ v[i]; fcaso ffun

El tamaño de problema viene dado por n (número total de elementos del vector a sumar) La reducción del tamaño de problema es por resta (Rec 1) se tiene: a=1 (una sola llamada recursiva)

b=1 (el valor en que se disminuye el tamaño de problema k=0 (operaciones adicionales y trivial de coste constante) Luego de nuevo la solución (Sol 1) es 3) Búsqueda lineal El siguiente algoritmo (que se expresa en pseudocódigo simplificado, quien ya domine la notación de Peña no tendrá dificultades en traducirlo a dicha notación), búsqueda lineal, busca un elemento x en un vector v de índices 1..n. Para ello el algoritmo que en realidad busca el elemento entre los elementos de índices i a n , y se ha de ejecutar con parámetro de llamada inicial i=1. Devuelve dos elementos: un booleano que indica si la búsqueda ha tenido éxito, y el índice del lugar en el que se encuentra x (en caso de fracaso en la búsqueda este índice no es significativo). La búsqueda es lineal, el caso trivial se tiene cuando i=n+1 y por tanto se busca en un vector vacío. En este caso devuelve falso en el booleano. En el caso no trivial devuelve cierto si v[i] es el elemento buscado y si no es así ejecuta una llamada recursiva a la propia función para que busque en i+1 ...n. funcion Busqueda(v: vect; x,i:entero) dev (b: booleano, p:entero) si i>n entonces devolver sino si x=v[i] entonces devolver sino BusquedaLineal(v,x,i+1); fsi fsi ffun

El tamaño de problema aquí es la longitud del tamaño de búsqueda, dada por n-i, es decir la función de coste es t(n,i)=n-i, al realizar la llamada recursiva se hace con i+1 como segundo parámetro luego la función de coste vale t(n,i+1)=n-(i+1)=(n-i)-1=t(n,i)-1. Es decir, la reducción del tamaño de problema es por resta con b=1. Por tanto: a=1 (una sola llamada recursiva en el caso peor) b=1 (valor en que se disminuye el tamaño de problema)

k=0 (operación trivial y adicional de coste constante ) y de nuevo se tiene función de coste lineal. 4) Búsqueda dicotómica Cuando el vector está ordenado se puede realizar una búsqueda más eficiente que la lineal, expresado en forma simplificada para buscar el elemento en el intervalo de índices i a j del vector, se toma el valor medio m=(i+ j) div 2, si x está en esa posición se devuelve cierto y el índice m, si no es así se compara x con el elemento v[m], si x es menor que v[m] se ha de buscar en la mitad inferior del intervalo, si es mayor que v[m] se ha de buscar en la mitad superior. El caso trivial es aquel en el que se llega a intervalo nulo (i>j). El algoritmo, conocido como "búsqueda dicotómica" se puede encontrar en el capítulo 4 de Peña (figura 3.5 de la primera edición).

El tamaño de problema viene dado por la longitud del intervalo de búsqueda t(i,j)=j-i, cuando se realiza llamada recursiva el tamaño del intervalo de búsqueda se reduce a la mitad, aproximadamente, en efecto, y por ejemplo: t(i,m)= t(i, (i+j) div 2) = (i+j) div 2-i ≈ (j-i) div 2 =t(i,j) div 2 Luego se obtiene una recursividad del tipo Rec 2 en la que: a=1 (una sola llamada recursiva , obsérvese que sólo se ejecuta una de las dos posibles llamadas) b=2 (división por 2 del intervalo de búsqueda ) k=0 (operación trivial y adicional de coste constante) Aplicando la solución (Sol 2) se tiene:

Como puede observarse la posibilidad de reducción a la mitad del espacio de búsqueda en cada pasada hace que el algoritmo sea muy eficiente. Al doblar el espacio de búsqueda sólo se incrementa en una llamada recursiva más el proceso 5) Suma "dicotómica" Supóngase que se intenta un algoritmo de suma "dicotómico" en lugar del lineal del ejemplo 2). El algoritmo calcula la suma de los elementos del vector situados entre los índices i y j llamando recursivamente al propio algoritmo para sumar la mitad inferior del intervalo, volviendo a llamar para sumar la mitad superior y luego sumando ambos resultados. Se puede encontrar en el Capítulo 4 de Peña (pagina 52 de la primera edición). De forma similar al caso de la búsqueda dicotómica el tamaño del intervalo se disminuye por división por 2 en cada llamada. Sin embargo en este caso se han de realizar dos llamadas recursivas siempre. La recursividad es del tipo Rec 2 con: a=2 (dos llamadas recursivas cada vez) b=2 (división por 2 del intervalo de suma) k=0 (solución trivial y operación adicional de coste constante) La solución es (téngase en cuenta que a=2> bk =1en este caso):

Es decir, en este caso no se ha conseguido una suma más eficiente que la del algoritmo 2). Ello es debido a que, aunque el intervalo de suma se reduce a la mitad en cada llamada, se han de realizar dos llamadas recursivas, en lugar de una en el algoritmo lineal, siempre.

5) Torres de Hanoi El algoritmo que resolvía el problema de las torres de Hanoi es: Procedimiento Hanoi(n, i, j) Si n=1 entonces mover disco de i a j Si no entonces Hanoi(n-1,i,6-i-j) mover disco de i a j Hanoi(n-1,6-i-j,j) Fin Si Fin Hanoi

El caso trivial es una operación de coste constante (mover un disco). En el caso no trivial se realizan dos llamadas recursivas con tamaño de problema reducido por resta de 1 (mover n-1 discos) y una operación de coste constante (mover un disco). Luego se tiene recursividad de tipo Rec 1 con: a=2 (dos llamadas recursivas siempre) b=1 (se disminuye el tamaño de problema por resta de 1 disco) k=0 (operación trivial y adicional de coste constante) Aplicando la solución (Sol 1) se tiene:

Es decir, se trata de un algoritmo de coste exponencial. Estos algoritmos son los llamados "intratables" debido a su elevado coste asintótico. Téngase en cuenta que si un monje moviera un disco por segundo para resolver el problema de las torres para 10 discos tardaría del orden de 210 segundos, es decir 1024 segundos o 17 minutos. Para 11 discos el tiempo se doblaría, es decir sería de unos 34 minutos. Para 20 discos el tiempo ya sería de unos 12 días. Para mover los 64 discos tardaría 264 segundos, es decir 1,84. 1019 segundos o sea algo así como ¡ 600.000 millones de años !. Si en lugar de realizar movimiento manual de discos, se simula en un computador rápido a razón de un movimiento por microsegundo la solución para 64 discos se alcanzaría en unos 600.000 años. O sea que el potente ordenador no evita que estemos todos calvos cuando se acabe de solucionar el problema (según la leyenda el mundo se acaba cuando los monjes hayan conseguido mover los 64 discos).