Introducción al diseño y análisis de los algoritmos (página 3)

b)    Si C2€(0,Ñ)  entonces  W (T1(n)) = W (T2(n))  

c)     Si C2=0  entonces  T1= W (T2(n))  –>  W (T1(n)) < W (T2(n))  

Definición 5: Sean T1 y T2 funciones de N–>R+. Escribimos  T1(n) = Q(T2(n)), y diremos que T1(n) esta acotado superior e inferiormente por T2(n), excepto para un número finito de excepciones, C2 T2(n) ú T1(n)  ú C1 T2(n).

 Propiedades de Q:

1. T1= Q (T1(n))
2. T1= Q (T2(n))  –>  Q (T1(n)) =  Q (T2(n))  
3. Q (T1(n)) = Q (T2(n))   <–> T1= Q (T2(n))  y T2= Q (T1(n)) 
4. Si T1(n) = Q (T2(n))   y  T2(n) = Q (T3(n))   –>  T1(n) = Q (T3(n))
5. Si T1(n) = Q (T2(n))  y  T3(n) = Q (T4(n)) –> T1(n) +T3(n)= Q (max(T2(n), T4(n))).
6. Si T1(n) = Q (T2(n))   y  T3(n) = Q (T4(n))   –>  T1(n) T3(n)= Q (T2(n) T4(n)).
7. Si  $  , dependiendo de los valores de que tome C tenemos:

d)    Si C€(0,Ñ)  entonces  Q (T1(n)) = Q (T2(n))  

b)    Si C =0  entonces  los ordenes de T1(n) y T2(n) son distintos.

Ejemplo 20: Retomemos el ejemplo 18, T(n)=26n-19  podemos obtener las cotas  inferior y superior nú  26n -19 ú 26n, T(n)= O(n), para C1 = 26, T(n)= W (n), para C2 = 1 y  por la definición 3 tenemos que T(n)= Q (n).

Para un algoritmo podemos obtener funciones que permiten medir su tiempo de ejecución, estas corresponden a sus casos mejor, medio y peor, y las denotaremos como Tm(n), T1/2(n) y Tp(n). Para cada una de ellas podemos dar 3 cotas asintóticas de crecimiento, por lo que se puede obtener un total de 9 cotas para el algoritmo.

Diremos que un algoritmo es de orden de complejidad O(T(n)) si su tiempo de ejecución para el peor caso es de orden O de T, es decir  Tp(n)=O(T(n)). De forma análoga diremos que su orden de complejidad para el mejor caso es W(T(n)), si Tm(n)= W(T(n)). Un algoritmo es de orden exacto Q(T(n)), si

T1/2(n)= Q(T(n)).

Un problema que tiene un algoritmo con tiempo de ejecución polinomial en el peor de los casos se considera un algoritmo bueno, la interpretación de la anterior significa que el algoritmo resuelve de forma eficiente el problema. Un problema que no tiene un algoritmo polinomial en el peor de los casos se entiende como intratable. El tiempo de ejecución de un algoritmo, si existe para un problema intratable es muy largo, incluso para tamaños de entradas pequeños.

Ciertos problemas son tan difíciles que no disponen de algoritmo alguno. Un problema para el cual no existe algoritmo se dice que es irresoluble. Uno de los primeros problemas de esta clase es el problema de terminación: Dado un algoritmo arbitrario y un conjunto de entradas,¿concluirá la ejecución en algún momento?

Un conjunto de problemas hasta ahora tienen un estado indeterminado, se supone que son intratables, esto aun no se ha demostrado, son los problemas de clase NP, como ejemplos de estos problemas se pueden mencionar: el problema de ciclo de Hamilton; dada una colección M de conjuntos finitos y un entero positivo m ú½M½(½M½= al número de elementos de M), ¿contiene M al menos m conjuntos mutuamente ajenos? (conjuntos de M tomados por pares, tales que, su intersección es el vacío).

P es la clase de todos los problemas cuya solución se obtiene mediante un algoritmo deterministico (aquellos en que la solución del problema se obtiene al ejecutar paso a paso una secuencia de instrucciones predeterminada, si se conoce la entrada entonces el resultado es totalmente predecible, tiene como base la lógica bivalente)  en  tiempo polinomial. 

NP es la clase de todos los problemas que pueden resolverse en tiempo polinomial con un algoritmo no deterministico (aquellos que la solución del problema se obtiene mediante una selección aleatoria de los pasos a ejecutar, estos no permiten a priori saber cual será el resultado para una entrada inicial, tiene como base la lógica difusa). 

Claro P Í NP ya que  los algoritmos deterministicos son un caso especial de los algoritmos no deterministicos, dónde  la estructura de selección es interminable. La pregunta si P es un subconjunto propio de NP (P c NP), es decir, si el algoritmo no  deterministico  es más eficaz  que uno deterministico, este es uno de los mayores problemas  en la teoría de complejidad. La naturaleza matemática de esta clase de problemas puede llevar a la errónea idea que su estudio solamente tiene valor teórico, en cambio muchos problemas de esta clase tienen una gran relevancia para la solución de aplicaciones prácticas, lo que justifica en interés de su estudio por la teoría de la complejidad.

II.3   Algoritmos correctos.

Otra elemento de gran de importancia para el análisis de un algoritmo es su correctitud.

Definición 6: Un algoritmo es correcto si satisface las siguientes exigencias:

a.     Luego de un número finito de operaciones elementales convierte cualquier dato de entrada w€LM en dato de salida (resultado) w*.

b.    El resultado w* es estable para pequeñas perturbaciones de los datos de entrada w.

c.     El resultado w* posee estabilidad computacional.

Si alguna de estas tres condiciones no es satisfecha decimos que el algoritmo no es correcto.

La necesidad de la condición 1 es evidente. Si para obtener un resultado el agente de cómputo necesita realizar infinitas operaciones o se requieren operaciones no realizables por agente de cómputo, entonces el algoritmo no es considerado como correcto.

Ejemplo 21: El algoritmo de división de dos  números enteros, en general no es correcto, pues el puede prolongarse infinitamente, si no se considera un criterio de parada en los cálculos.

Ejemplo 22: El algoritmo de cálculo de las raíces de   a x2+ b x + c = 0 a través de la formula  x1,2 = (-b ±(b2-4ac)1/2)/2a, no es correcto en general pues es necesario que el  agente de computo sea capaz de realizar la operación de cálculo de la raíz cuadrada.

La segunda condición significa que el resultado debe depender continuamente de los datos de entrada bajo la condición de ausencia de errores de cálculo. Note que junto al dato w€LM, en esta definición toman parte todas las entradas wE cercanos a w.

Ejemplo 23: Sea el problema del ejemplo 19, supongamos que el agente de cómputo es capaz de realizar el cálculo de la raíz cuadrada. Si el algoritmo esta diseñado para trabajar sólo cuando b2-4ac ³ 0, entonces este algoritmo no es estable respecto a los datos de entrada, además si en el algoritmo no contempla que a ¹ 0, entonces el tampoco será estable respecto a los datos de entrada.

Debido a los errores de redondeo al suministrarle los datos al agente de cómputo y a las operaciones que el agente de cómputo ejecuta, inevitablemente surgen errores. Para un determinado algoritmo el valor de este error esta determinado por la exactitud Dac del agente de cómputo. En el caso de las operaciones aritméticas este valor depende de la cantidad de dígitos t destinados a la mantisa,

            m = ±(b1 2-1 + b2 2-2+…+b t 2-t),  b = 1,  bi €{0, 1},    i = 2, 3, … , t

y del método de redondeo (truncamiento Dac = 21-t;  redondeo Dac = 2-t).

Definición 7: Un algoritmo es estable computacionalmente si los errores de cálculo del resultado tienden a cero cuando Dac® 0.

Definición 8: Un algoritmo es estable, si es estable computacionalmente y respecto a los datos de entrada, en caso contrario, el algoritmo no es estable.

Ejemplo 24: Supongamos que es necesario realizar una tabla de los valores de, 

para n =1,2,…,10, en un agente de cómputo que admite 6 cifras decimales en la mantisa y  Dac = 5 10-7.

Integrando por partes tenemos ½

Por tanto, es válida la fórmula de recurrencia

Además

Utilizando la formula de recurrencia encontramos sucesivamente:

Es evidente que los valores de la integralson positivos, pues el integrando   para todo  x€[0; 1], es  siempre positiva. Sin embargo, los valores determinados para  n = 9 y n = 10, son negativos. ¿Dónde esta la causa de este error?. El error fue cometido al redondear el valor de a seis cifras significativas, es decir, . Sin embargo,  al calcular   este error se conservo, al hallar  se multiplico por 2!, así sucesivamente hasta obtener  donde se multiplico por 10!. De esta forma llegamos a que  , por ejemplo, .

Por tanto, este algoritmo es inestable computacionalmente, pues el error crece proporcionalmente a n!, y evidentemente esta situación no mejora si se aumenta la cantidad de cifras de la mantisa.

Para obtener un algoritmo estable escribimos la formula de recurrencia en la forma

y realizamos los cálculos en orden inverso, por ejemplo, para n = 54, tenemos . Debido a que , entonces .

Sin embargo, al calcular el error disminuye 54 veces, así se mantiene el proceso de cálculo, como resultado los valores de serán calculados con 6 cifras significativas verídicas, y el error decrece en cada paso.

La inestabilidad de un algoritmo puede ser deducida del análisis de la estabilidad según los datos de  entrada, pues la inestabilidad respecto a pequeños errores de redondeo de los datos automáticamente conlleva a la inestabilidad computacional

Sin embargo, al calcular el error disminuye 54 veces, así se mantiene el proceso de cálculo, como resultado los valores de serán calculados con 6 cifras significativas verídicas, y el error decrece en cada paso.

La inestabilidad de un algoritmo puede ser deducida del análisis de la estabilidad según los datos de  entrada, pues la inestabilidad respecto a pequeños errores de redondeo de los datos automáticamente conlleva a la inestabilidad computacional.

Ejemplo 25: Supongamos que yn, n=1, 2, 2…, se calcula por la formula de recurrencia

Yn = an yn-1 +  bn,   y0 es un valor conocido,  an una constante no negativa.

Sea y* un a valor aproximado de y0, entonces (si los cálculos se realizan correctamente), los valores obtenidos mediante la formula de recurrencia contienen errores, dados por

Si an ú 1, entonces el algoritmo es estable respecto a los datos de entrada, pues  Si, al contrario  an ³ q > 1, entonces el error crece indefinidamente cuando n ® Ñ. En este caso el algoritmo no es estable.

En realidad debemos notar que el algoritmo fue caracterizado como inestable cuando an ³ q > 1 si se cumplen dos condiciones, a las que no se le prestó la debida atención. La primera, la continuación ilimitada de la ejecución,  este carácter inestable nos informa sobre la tendencia a un crecimiento ilimitado del error cuando la ejecución se prolonga indefinidamente. La segunda esta relacionada con la medida del error (hasta el momento no habíamos hecho ninguna diferenciación al respecto, realmente habíamos tratado el error absoluto, el cual no siempre es una medida adecuada, por lo que se emplea el error relativo) seleccionada.

Ejemplo 26: Supongamos que en la formula de recurrencia del ejemplo 23, tenemos an ¹ 0 y bn = 0, n. Entonces 

Luego  y bajo esta condición, el algoritmo es relativamente estable para los datos de entrada.

II.4  Sensibilidad de los algoritmos.

La ejecución de cálculos en un agente de cómputo está ligada sin lugar a dudas a la aparición de errores de cálculo, originados fundamentalmente por el carácter finito de la representación de los números, lo cual impone la necesidad de realizar aproximaciones de redondear o truncar el resultado de cada operación aritmética. Inclusive cuando la cantidad de cifras para almacenar la mantisa es grande, existe un peligro real de que luego de realizar un gran número de operaciones, ocurra una acumulación del error capaz de distorsionar parcial o totalmente el resultado calculado. A veces, al realizar una cantidad no significativa de operaciones, el resultado puede ser incorrecto si el algoritmo es bien sensible a los errores.

Cuando es necesario resolver problemas complejos (o sea, cuando el número de operaciones aritméticas supera los millones, los cálculos requieren muchos recursos, el resultado debe obtenerse con una exactitud garantizada y es necesario tener una determinada responsabilidad ante la solución obtenida se impone tomar una posición seria respecto a los errores de cálculo.

II.4.1 Orden de ejecución de las operaciones.

La solución de los más variados problemas en un agente de cómputo se reduce inevitablemente a la realización de simples operaciones aritméticas y lógicas. Sin embargo, en muchas situaciones una misma expresión matemática admite varias posibilidades para su cálculo, que difieren solamente en el orden de ejecución de las operaciones. Ahora bien, los resultados de los cálculos en un agente de cómputo dependen del orden de realización de las operaciones y la diferencia en los errores puede ser altamente significativo.

Analicemos un ejemplo simple, pero ilustrativo, del cálculo en un agente de cómputo de la suma . Supongamos que  son números reales positivos que pueden ser representados en la máquina. ¿En qué orden debemos sumarlos de forma que, en lo posible, sea mínimo el error de cálculo?

Sea  una suma parcial, y  su valor aproximado, calculado según la fórmula  [1]. El error del valor  está compuesto por el error del valor  y por el error en la ejecución de la operación . Por consiguiente, , siendo   una cota superior del error absoluto en el cálculo de . Esto significa que

  =

               .

Debido a que el factor que acompaña a  en la fórmula del acotamiento del error decrece con el aumento de , en general el error será mínimo si se suman los números en el orden creciente a sus valores, comenzando con el menor.

A veces una selección inapropiada del orden de las operaciones conlleva a una pérdida total de la exactitud, o provoca la detención de la ejecución por desbordamiento, imposibilitando la obtención de los resultados.

Ejemplo 27: Supongamos que en un agente de cómputo con diapasón de números representables dado por , es necesario hallar el producto , donde . Si realizamos los cálculos en el orden natural entonces ya  nos da una parada brusca por desbordamiento. Por otro lado, la ejecución de los productos en orden inverso conlleva a la pérdida del orden, pues ; de esta forma, , por lo que luego de realizar todas las multiplicaciones obtenemos el valor . Para este caso, una posibilidad de organizar el orden de las operaciones es: .

II.4.2  Pérdida "catastrófica" de la exactitud

En muchas ocasiones, una sucesión corta de cálculos a partir de datos conocidos con buena exactitud, conduce a un resultado que contiene muy pocas cifras significativas correctas (por cifras significativas de un valor aproximado, se entiende toda cifra distinta de cero y el cero si este se encuentra entre cifras significativas, por ejemplo 0,002080, en este número los tres primeros ceros no son cifras significativas pues ellos solamente determinan el orden decimal de las restantes cifras, los restantes dos ceros representan  cifras significativas, por cifras significativas correctas entenderemos aquellas cifras significativas del valor aproximado cuya posición en el error absoluto es igual a cero), inclusive ninguna en ciertos casos. Esto es lo que se conoce como pérdida "catastrófica" de la exactitud. En el ejemplo 27 ya nos encontramos con esta situación, cuando un determinado orden en el cálculo de los productos condujo al resultado erróneo  igual a cero. Veamos otros ejemplos.

Ejemplo 28. Es conocido que la función  puede ser representada en forma de la siguiente serie de potencias convergente:

De aquí que parece razonable la posibilidad de calcular valores de la función  mediante la suma directa de la serie. Supongamos que para los cálculos usamos un agente de cómputo de 6 cifras decimales. Sea  y vamos a calcular los valores de las sumas parciales hasta tanto la adición del próximo sumando cambie el valor de la suma:

 Ө  Ө  Ө     Ө Ө .

En la suma entraron 37 miembros, y el valor del siguiente (el 38vo) ya no cambió el resultado. ¿Puede ser considerado el resultado aceptable? La comparación con el valor obtenido al evaluar la función  muestra que el valor hallado no contiene ni una cifra significativa correcta .

¿Dónde radica la causa de la pérdida catastrófica de la exactitud? Resulta que los sumandos calculados de la serie necesariamente contienen errores, de manera que para algunos (del 5to al 13º) la magnitud del error supera el valor del resultado buscado. Vemos así un defecto evidente del algoritmo.

En este caso, el paso a los cálculos con doble precisión (doble longitud de la mantisa) permite obtener   con 6 cifras verdaderas. Sin embargo, para  el problema analizado antes aparece de nuevo. Procedamos de otro modo. Utilizando el desarrollo en la serie para x = 8.1,  calculamos:

,

y entonces, . Este cambio en el algoritmo ha permitido obtener el valor con 6 cifras significativas correctas.

II. 4.3  Condicionamiento de un algoritmo de cálculo

La noción de condicionamiento de un algoritmo de cálculo, la sensibilidad del resultado de la ejecución de un algoritmo a pequeños, pero inevitables, errores de redondeo.

Definición 9.  Un algoritmo computacionalmente estable es bien condicionado si pequeños errores relativos de redondeo (caracterizados por el número ) conlleva a pequeños errores relativos de cálculo   del resultado , y lo llamaremos mal condicionado si los errores del cálculo pueden ser arbitrariamente grandes.

Si  y  están relacionados por la desigualdad , entonces al número  se le suele llamar número de condicionamiento de un algoritmo de cálculo. Para los algoritmo computacionalmente mal condicionados tenemos que . Cuando el número  adquiere un valor muy grande, el algoritmo es prácticamente inestable.

Si usamos el primer algoritmo propuesto en el ejemplo 24 para el cálculo de una serie finita de  integrales , entonces el coeficiente de crecimiento del error es finito: , o sea, al calcular una serie finita de integrales el algoritmo formalmente es estable. No obstante, para valores no muy grandes de  el algoritmo es tan mal condicionado que en el plano práctico puede considerarse como instable.

Algo no deseable sucede si para la solución de un problema bien condicionado empleamos un algoritmo mal condicionado. Precisamente este es el caso de los algoritmos propuestos al inicio en los ejemplos 24 y 27.

Retomemos el ejemplo 28. ¿Es posible prever la pérdida catastrófica de exactitud al calcular valores por medio de la suma directa de la serie? Analicemos el problema de la suma de la serie  con sumandos . Cada uno de estos miembros se calcula con un error relativo . Entonces, para , la fórmula (Ref. 5, pág 53)

considerando el desarrollo de la serie nos da el valor . El crecimiento del módulo de  proporciona un  empeoramiento drástico del condicionamiento de los cálculos. Para , . Por esta razón es que ocurre una pérdida de la exactitud al realizar los cálculos en un agente de cómputo con 6 cifras decimales.

Si por acaso un algoritmo destinado a la solución de un problema bien condicionado, es mal condicionado, entonces éste debe ser modificado y realizar esfuerzos para la construcción de un algoritmo cualitativamente mejor.

"Si el problema es mal condicionado, entonces ningún esfuerzo que se intente en organizar los cálculos de otra forma va a llevarnos a respuestas ciertas, excepto por AZAR".

Ejercicios para el trabajo independiente:

1. Para los ejemplos del 1 al 14 determine una función para una entrada n T(n) y una cota inferior y superior para esta función.

2. Para los ejemplos del 1 al 14 analice  si los algoritmos son correctos.

Bibliografía Básica    

-        Amosov A. A., Dubinskii,Y. A., Konpchenova N. V.: Métodos de calculo para la solución de problemas de ingeniería., Editorial MEI, 1991.

-       Fabricio L. y Otros: Matematics of Computing, CISM, UNESCO Project., 2002

-       Frolov G. Y, Kuztnetsov E.: Elementos de Informática,  1991.

-       Garbatov. V.A: Fundamentos de la Matemática Discreta. Editorial Mir Moscú, 1988.

-       Johnsonbaugh R.: Matemáticas Discretas, Vol. 1, Cap. 3 y 5, 2004.

-       Libro en formato electrónico (Internet). Universidad de Málaga,  1999

Autores: Dr.C. Antonio Manuel Otero Dieguez

Dr.C. Luis Orlando Castellano Pérez

Profesores:

Facultad de Informática Departamento de Matemáticas Universidad De Holguín, Cuba.

Graduados en la antigua URSS, en licenciatura en Física-Matemática.

2008

[1] Aquí y en lo sucesivo, los símbolos Ө, , etc., indican las operaciones aritméticas realizadas por el agente de cómputo.

Partes: 1, 2, >