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:
- T1= Q (T1(n))
- T1= Q (T2(n)) –> Q
(T1(n)) = Q
(T2(n)) - Q (T1(n)) = Q (T2(n))
<–> T1= Q (T2(n)) y
T2= Q (T1(n)) - Si T1(n) = Q (T2(n))
y T2(n) = Q (T3(n))
–> T1(n) = Q (T3(n)) - Si T1(n) = Q (T2(n)) y
T3(n) = Q (T4(n)) –> T1(n)
+T3(n)= Q (max(T2(n),
T4(n))). - Si T1(n) = Q (T2(n))
y T3(n) = Q (T4(n))
–> T1(n) T3(n)= Q
(T2(n) T4(n)). - 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
integral
son 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.
 Página anterior | Volver al principio del trabajo | Página siguiente  |