Análisis de la Velocidad de Algoritmos

En el momento de seleccionar un algoritmo para resolver un problema, debemos por supuesto considerar su velocidad (o desempeño) en conjunto con su estabilidad hacia atrás (si los resultados son estables para pequeños cambios en los datos de entrada al algoritmo).

Existen muchas maneras de estimar la velocidad de un algoritmo:

Si contamos con una instancia de un problema en particular, una implementación en particular de un algoritmo, y una computadora para correrlo, podemos por supuesto simplemente correr el programa y medir el tiempo requerido para obtener el resultado. Sin embargo, esto puede ser difícil y costoso en tiempo, por lo que en ocasiones requerimos estimaciones previas.

Una forma tradicional de medir el tiempo que toma un algoritmo para ejecutar es contar los flops, que son el número de operaciones en punto flotante que realiza. Hacer este estimado es recomendable para cualquier algoritmo que se busque implementar en hardware. Sin embargo, esta estimación puede generar algunas confusiones en los tiempos requeridos en las arquitecturas de computadoras modernas, debido a que puede tomar mucho más tiempo mover los datos en el interior de la computadora hacia las unidades funcionales que se encargan de realizar la operación. De aquí la necesidad de realizar una buena programación y de contar con compiladores que generen código optimizado que aproveche al máximo el hardware disponible.

En el caso de algoritmos iterativos que no se detienen hasta alcanzar un valor de convergencia, debemos estudiar cuantos pasos se requieren para alcanzar un valor tolerable de error. Para hacer esto, debemos decidir si la convergencia es lineal, esto es, si el error disminuye en un factor constante en cada paso: o más rápido.

Teoría de la Perturbación y los Números de Condicionamiento

Las respuestas producidas por los algoritmos numéricos en raras ocasiones son exactamente correctas.

Podemos considerar dos fuentes de error:

• Pueden existir errores en los datos que entran al algoritmo, causados por posiblemente por errores previos de cálculo o simplemente por deficiencias en la medición.
• Además, tenemos los errores imputables al propio algoritmo, que normalmente se deben a aproximaciones hechas en el mismo algoritmo.

Para poder entender en que medida existen errores en los resultados del algoritmo provenientes de estas dos fuentes de error, necesitamos entender que tanto cambia la solución de un problema si los datos de entrada son en alguna forma modificados o perturbados.

Sea una función real continua de una variable real . Queremos calcular , pero no conocemos el valor exacto de . Supongamos que en su lugar tenemos a . Lo mejor que podemos hacer (sin más información disponible) es calcular el valor de y tratar de limitar el error absoluto . Podemos usar una aproximación linear hacia para tener limitado al error en .

Llamamos al término el número absoluto de condicionamiento de la función en . Si es lo suficientemente grande, entonces el error puede ser grande aunque la distancia sea pequeña. En estos casos decimos que la función esta mal condicionada en .

El número de condicionamiento es todo lo que necesitamos para entender como un error en la entrada puede afectar la respuesta calculada.

El universo no lineal

Recuerdo hace unos meses cuando el gobierno (o más bien desgobierno) calderonista mexicano pretendía subir los precios de la gasolina para recaudar más impuestos (idea que no encuentro muy lógica en tiempos de crisis, pero bueno eso es otro problema) que un amigo disminuía el impacto que esto tendría en los precios de los productos.

Su razonamiento era el siguiente:

Si la gasolina subía sólo unos cuantos centavos, supongamos un incremento de 1%. Entonces el costo del transporte se incrementaría en un porcentaje todavía menor, debido a que la gasolina no es el único factor que interviene en esta industria. Por lo que el incremento en los precios de los productos no podría ser mayor a 1% y probablemente sería mucho menor.

Además de pensar:  ¿pues que este hombre no tiene memoria?  o ¿en que año nació? Titubíe en el momento de pensar los motivos por los que podía estar equivocado su razonamiento.

De súbito vino a mi mente que el fenómeno de la inflación probablemente no era un fenómeno lineal. Esto es, el resultado esperado no debe calcularse simplemente como la suma de las partes.

¿Porqué pasa esto en los precios de los productos?

Sin creer tener toda la razón en el asunto, seguramente un economista tendrá una mejor explicación. Creo que es porque cada producto esta formado por otros productos intermedios en una cadena que llega hasta las materias primas. Si debido al transporte suben los precios de las materias primas, entonces también subirán los precios de los productos intermedios, los cuales también vuelven a transportarse (provocando un incremento adicional parecido al que tenemos con una realimentación positiva) y así hasta llegar al producto final.

Además debemos considerar otros aspectos caóticos como el comportamiento humano y su respuesta no facilmente estimable pero monotonamente alzista por el incremento de las gasolinas.

Todo esto lo digo para poner un ejemplo de un fenómeno no lineal, me imagino que en la economía debe de haber muchos más y desgraciadamente los expertos que tenemos (sobretodo en México) dudo que tomen en cuenta la existencia de este tipo de realimentaciones y comportamientos. Y es que en realidad los expertos que se dedican a estudiar fenómenos no lineales y encontrar novedosas explicaciones a muchos problemas (demostrando una vez más que nuestros conocimientos científicos apenas sirven para plantear preguntas un poco más complejas) son todavía muy pocos y este paradigma sigue siendo muy reciente. Quizás estemos ante una nueva revolución del conocimiento, similar a la que ocurrió cuando se cuestionó el sistema geocéntrico.

Probablemente con métodos no lineales podamos en un futuro encontrar una teoría que unifique las diferentes leyes físicas y explique preguntas relacionadas con el origen de la vida.

Para los que les interesa este tipo de cuestiones recomiendo el siguiente libro:

Ojalá lo disfruten como yo lo estoy haciendo.