Notas de Clase- 2002

EL PODER DEL ALGORITMO Una de los sucesos m´as sorprendentes en la ciencia y las matem´aticas del siglo XX es el surgimiento del mundo computacional, informativo y visual asociado al ordenador. En este evento matem´aticos, f´ısicos e ingenieros tuvieron partes diferenciadas y complementarias. Las figuras legendarias de Alan Turing y John von Neumann son bien conocidas del gran p´ ublico, aunque es menos sabido que otros gigantes de la matem´atica pura estaban en la fotograf´ıa original, como David Hilbert y Kurt G¨odel, y yendo m´as atr´as en el tiempo los mism´ısimos Blaise Pascal y Gottfried Leibniz grandes matem´aticos del siglo XVII, y Charles Babbage gran inventor de m´aquinas calculadoras en el XIX. El resultado de la aventura que se inici´o en los a˜ nos 30 del siglo XX es una las maravillas del mundo actual, una tecnolog´ıa poderosa, democr´atica y limpia. Hoy vamos a ocuparnos del geniecillo matem´atico escondido entre los bits, el algoritmo, y vamos a dar una idea de sus propiedades, sus man´ıas y algo de su gran poder. Definici´ on. “Un algoritmo es un procedimiento efectivo y sistem´atico para resolver un problema, usualmente matem´atico”. Un Procedimiento es una serie de reglas dise˜ nadas para alcanzar un objetivo; aqu´ı se trata de resolver un problema matem´atico. Por Procedimiento Efectivo entienden los expertos algo muy concreto que nos servir´a para la definici´on detallada de algoritmo: - es un n´ umero finito de reglas o instrucciones bien definidas, - que actuando sobre datos de una clase dada, - producen en un n´ umero finito de pasos perfectamente prescritos, - la soluci´on correcta a un problema matem´atico - en todos los casos a considerar. Esta u ´ltima propiedad refleja el calificativo de sistem´atico en la definici´on. Analicemos con m´as detalle estas frases. El lector versado en programaci´on para ordenadores puede comparar los detalles con su experiencia personal. (i) El procedimiento efectivo consiste en un n´ umero finito de instrucciones precisas tomadas de un ”conjunto de instrucciones (admisibles)”, I, (ii) Las instrucciones se aplican a un conjunto finito de datos tomado de un conjunto bien definido de “datos admisibles”, D (input), (iii) Estas instrucciones o reglas se ejecutan de forma autom´atica o mec´anica sin dar lugar a fallos, dudas o interpretaciones en su ejecuci´on, (iv) Y producen tras “un n´ umero finito de pasos”, 1

(v) Un “resultado”concreto en cada caso (output), (vi) Que da una soluci´on correcta al problema propuesto en todos los casos. Resumimos las 3 propiedades principales del algoritmo como procedimiento efectivo que figuran en los textos de Algoritmia: * Sistem´atico o Universal: resuelve todos los casos de un problema. * Prescriptivo: es determinado y finito; no deja lugar a fallos, dudas o interpretaciones sobre la marcha; por ello es mecanizable. * Consistente: resuelve correctamente el problema en cuesti´on. Comentarios. Hemos de se˜ nalar que un algoritmo ha de resolver todos los casos posibles para los datos admisibles; se trata en general de un conjunto potencialmente infinito, por ejemplo, los n´ umeros enteros. Si es s´olo aplicable a un subconjunto peque˜ no de datos, el algoritmo no ser´a muy u ´til. Todo ello es cuesti´on opinable: las personas algo versadas en matem´aticas no buscar´an un algoritmo que calcule la ra´ız cuadrada de un n´ umero negativo (salvo que realmente les interesen los n´ umeros complejos, hay clientes para todo y algoritmos a su medida). Tambi´en el concepto de soluci´on correcta puede ser opinable. En particular, muchos algoritmos han de computar soluciones aproximadas. En esos casos la denominaci´on de soluci´on correcta se traduce m´as bien por soluci´on satisfactoria. Analizar estas cuestiones suele ser la labor del matem´atico, ver m´as abajo la discusi´on. En un lenguaje m´as coloquial, lo que caracteriza al algoritmo es que es realizable de forma mec´anica y en tiempo finito para obtener un resultado concreto y correcto en cada caso propuesto. La palabra finito es crucial en todo lo anterior y es un aspecto nada trivial, las famosas obras matem´aticas K. G¨odel [G] y A. Turing [T] giran precisamente en torno a la finitud. Otras formulaciones que se hallan en la literatura y convienen al algoritmo son las de procedimiento detallado, concreto, preciso, mec´anico, pr´actico y tambi´en el de m´etodo operativo. An´ alisis de un algoritmo. Se observan las siguientes partes constituyentes: - Datos o Input. - Instrucciones de C´alculo. - Instrucci´on de Parada. - Expresi´on del resultado o Output. Usualmente los algoritmos - son num´ericos, D es el conjunto de los n´ umeros, naturales, enteros o reales (a veces complejos). Los programas de ordenador piden usualmente que declaremos el tipo de variable que usamos. - Las instrucciones se escriben en un alfabeto simb´olico dado. En muchos casos se trata de lenguajes de ordenador, y los algoritmos se conocen como programas de c´alculo o, mejor 2

dicho, son parte de esos programas. Pero un algoritmo es en s´ı un ente matem´atico y no necesita a priori ser implementado en un programa.

3

Algoritmos iterativos: Es un tipo frecuente en los procesos de c´alculo num´erico en que la instrucci´on b´asica, o bloque de instrucciones b´asico, produce un resultado que sirve de dato de entrada (input) a un segundo c´alculo cuyo resultado sirve de dato a ..., y as´ı sucesivamente. Esto se llama ”bucle”(loop). La utilizaci´on de bucles es una t´ecnica b´asica del c´alculo num´erico, pues permite resumir en unas pocas instrucciones un proceso que se traduce en cuantiosos c´alculos repetitivos, que afortunadamente dejamos al cuidado del ordenador. Todos los lenguajes de programaci´on (como PASCAL o MATLAB) tienen prevista una c´omoda escritura y sintaxis para los bucles. En los algoritmos iterativos es preciso cuidar de (1) como se accede al bucle, usualmente mediante un ”paso de inicializaci´on”, (2) cu´antas iteraciones del bucle deben realizarse, bien indic´andolo expl´ıcitamente, bien indicando un criterio efectivo cuya satisfacci´on termina la repetici´on. Problemas usuales de un algoritmo: - “el chisme se atasca”: existen datos para los que no est´a definida una de las instrucciones. Por ejemplo, se pide que divida por x y x vale en este caso cero. Tambi´en puede haber errores de sintaxis, lo que es usual en los programas autom´aticos. Los lenguajes de programaci´on de ordenador tienen previsto como avisar al artista de cual es el problema. Este es un error del usuario. - “a´ un peor, se cuelga”(es decir, el bucle infinito): en los algoritmos iterativos puede que se produzca un bucle en que las instrucciones y c´alculos intermedios se repiten c´ıclicamente. Ya se imagina el lector que no hay forma de que termine en este caso, y ello puede suceder aunque el n´ umero de instrucciones sea muy peque˜ no (sugerencia para iniciados: ponga usted mismo un ejemplo). Tambi´en puede darse el problema en forma de la ”huida infinita”: pongamos que para realizar un paso se precisa previamente calcular dos cantidades; pero la primera de ellas exige a su vez dos c´alculos previos; y el primero de ´estos exige a su vez ... etc etc., no hay forma de que termine el primer c´alculo. Este es un error esencial, si no se resuelve el proceso no es computable. La teor´ıa y la practica. Algoritmos y soluciones aproximadas En numerosos problemas matem´aticos los datos que se manipulan son n´ umeros reales (como los problemas de la f´ısica y la geometr´ıa) o bien producen soluciones reales a partir de n´ umeros enteros (como la extracci´on de ra´ıces). Dado que el ordenador es (esencialmente) finito, trata en general los n´ umeros reales mediante sus aproximaciones decimales m´as o menos largas. Ello provoca un problema de enorme importancia filos´ofica y pr´actica: qu´e significado tienen las soluciones con un n´ umero finito de cifras decimales producidas por estos m´etodos y en que sentido aproximan la soluci´on exacta pensada por los te´oricos. En resumen, calcular la soluci´on exacta no es, contra lo que pudiera pensarse, el objetivo de muchos algoritmos, pues es un trabajo inabordable en forma efectiva o meramente 4

no pr´actico. Definir en esos casos la soluci´on que nosotros prudentemente hemos llamado correcta o satisfactoria es parte importante del arte algor´ıtmico y en ella se junta el inter´es del cliente (por ejemplo, un cient´ıfico que usar´a los resultados) y los conocimientos del experto (matem´atico o inform´atico). Reflejando esta problem´atica se dice entonces que la soluci´on hallada es v´alida. As´ı, una ra´ız cuadrada se calcula con tantas cifras decimales como desee el cliente, pero no con infinita exactitud. Determinismo y azar Uno estar´ıa tentado de a˜ nadir en la descripci´on del algoritmo la frase ”dados los mismos datos se produce el mismo resultado”. De hecho, as´ı se caracterizan los algoritmos deterministas, que son los cl´asicos. Sin embargo el mundo progresa sin cesar. Son hoy d´ıa de gran uso en la matem´atica, la ciencia, la econom´ıa y la ingenier´ıa los algoritmos estoc´asticos (o probabilistas), en los que se introduce en alguno de los pasos una llamada al azar, por ejemplo en la forma de un n´ umero aleatorio como dato. Ello se visualiza por ejemplo diciendo que en un determinado momento tomamos una decisi´on tirando una moneda (virtual). La ley de los grandes n´ umeros y su extra˜ na magia nos garantizan que en gran cantidad de supuestos ello nos conduce a algoritmos rapid´ısimos que ofrecen soluciones que son asint´oticamente correctas”. Uno se pregunta que significa esta u ´ltima frase pero ese es otro fascinante tema de estudio. Algoritmia Es la ciencia de los algoritmos. En ella se estudia como construir buenos algoritmos, e incluso algoritmos ´optimos. Se define la eficiencia de un algoritmo midiendo su coste de c´alculo. Aunque el c´alculo del coste depende de las caracter´ısticas de los agentes calculadores (es decir, los ordenadores) y se mide en funci´on del tiempo consumido (tiempo de CPU por ejemplo), se trata de una disciplina muy matem´atica y hermosa en forma de Teor´ıa de la Complejidad. El An´alisis Matem´atico se encarga de demostrar que los algoritmos son realmente consistentes con su problema, y de evaluar la velocidad de convergencia de los algoritmos iterativos. El gran maestro, Isaac Newton, ya pas´o por estos pagos dejando su profunda huella (como el m´etodo de Newton de c´alculo de ra´ıces de funciones). Con todo el atractivo de la teor´ıa, no debemos olvidar por un momento que la merecida gloria de los algoritmos en nuestra sociedad informatizada se basa en la capacidad pr´actica para calcular r´apida y mec´anicamente y dar as´ı respuesta num´erica a toda clase de problemas. Un poder que ni se so˜ naba hace s´olo 60 a˜ nos y que uno imagina que encantar´ıa a Newton, inventor de algoritmos y calculador a mano. En resumen, los algoritmos son importantes porque funcionan y calculan (casi) todo lo imaginable. Una referencia sobre Algoritmia para los estudiosos: [BB]

5

10 familias de algoritmos famosos Presentamos aqu´ı una lista de algoritmos cl´asicos de las matem´aticas, organizados en 10 familias. 1 - Los algoritmos de las operaciones aritm´eticas en base 10. El algoritmo de la ra´ız. 2- El algoritmo de Euclides para hallar el m´aximo com´ un divisor de dos n´ umeros enteros. Idem de polinomios. 3- La criba de Erat´ostenes para obtener la lista de n´ umeros primos (inferiores a un entero dado). 4- Fracciones continuas. La fracci´on continua que halla la ra´ız de 2. 5- El algoritmo de cambio de base num´erica (por ejemplo de base 10 a base 2). Los algoritmos de las operaciones aritm´eticas en base 2. 6- El m´etodo de Newton para hallar ra´ıces de funciones (resoluci´on de ecuaciones). Se trata de uno de los algoritmos m´as bellos por la combinaci´on de sencillez, alcance y rapidez de convergencia. 7- La tabla de n´ umeros combinatorios (coeficientes bin´omicos) de Cardano-Tartaglia. 8- El algoritmo de Gauss para resolver sistemas de ecuaciones lineales. 9- La integraci´on de funciones (por ejemplo algebraicas) por m´etodos num´ericos (como el del rect´angulo o del trapecio). 10- El m´etodo de Euler para integrar ecuaciones diferenciales ordinarias. Las familias de m´etodos Runge-Kutta y multipaso. Grandes algoritmos del Siglo XX - El algoritmo del Simplex. El N´ umero Uno de los algoritmos aplicados en el siglo XX. Inventado por George Dantzig en 1947, figura en una enorme cantidad de m´etodos de programaci´on lineal y optimizaci´on. - La Fast Fourier Transform o Transformada de Fourier r´apida. Otra herramienta computacional de incre´ıble poder. Para aprender todo sobre ella visitar http://www.fftw.org/links.html - Los algoritmos basados en el m´etodo de Monte Carlo (probabilistas). - Los algoritmos de grafos. - Los algoritmos gen´eticos. - Los algoritmos de la inteligencia artificial. Historia: El nombre procede del gran matem´atico ´arabe (musulm´an) del siglo IX Moh´amed ben Musa al Juarizmi (Abu Ja’far Muhammad ibn Musa Al-Khwarizmi, en la versi´on inglesa). El final del nombre puede deberse a su regi´on de origen en la actual rep´ ublica de Uzbekist´an, el Joresm, no lejos de la m´ıtica Samarcanda, pero no es seguro. S´ı lo es que trabaj´o en la famosa Casa de la Sabidur´ıa que erigi´o el califa Harun al-Rashid en 6

Baghdad. ´ Al Juarizmi es famoso por su tratado de Algebra, “Hisab al-jabr w’al-muqabala”, que es el origen de la palabra ´algebra. El nombre algoritmo deriva en concreto de la traducci´on al lat´ın de su obra de aritm´etica, “Algoritmi de numero Indorum”, sobre el c´alculo a la manera india, o sea sobre la aritm´etica con notaci´on posicional que hoy usamos (pero no se conoce el original de esta obra). Referencia para la Historia de las Matem´aticas en la red: http://www-history.mcs.st-andrews.ac.uk/history/

NOTAS AVANZADAS Computabilidad. El Problema de la Parada (Halting Problem) es uno de los problemas estrella de la computabilidad e hizo la fama de Alan Turing. Se pregunt´o el buen ingl´es si no existir´ıa un algoritmo universal que permitiera descubrir si un algoritmo dado (cualquiera) va a pararse en tiempo finito (o al contrario si va a seguir con su tema eternamente). La respuesta es negativa, tal cosa no puede existir por una cuesti´on l´ogica, y ello pone un l´ımite inevitable a la capacidad de la matem´atica te´orica y pr´actica. Es uno de los resultados matem´aticos m´as justamente famosos del siglo XX. Una de los grandes logros de la computabilidad como ciencia es el haber establecido la equivalencia de los diversos modelos de “m´aquina de c´alculo”que se han ido proponiendo y que responden del funcionamiento de los ordenadores que usamos, empezando con la m´aquina de Turing (1936). Este resultado proporciona una profunda unidad filos´ofica a todo el arte computacional actual y con ello una base s´olida a la Sociedad de la Informaci´on. La lista de instrucciones b´asicas con las que todo algoritmo num´erico puede implementarse en estas m´aquinas es sorprendemente muy corta. As´ı, en el modelo de m´aquina universal de c´alculo URM (Universal Register Machine) muy utilizada a efectos docentes la lista es: I = Z(n), S(n), T (m, n), J(m, n, p), consistente en poner un cero en el registro n, poner el n´ umero siguiente, trasponer dos registros y hacer una sustituci´on (que permite programar iteraciones). Esta equivalencia de todos los conceptos de computabilidad es la famosa Tesis de Church. Ver para m´as detalles ver el texto de Curtland [Ca]. Todos estos conceptos de computabilidad son te´oricos pero es importante recordar que los algoritmos se corren en computadoras de capacidad finita y existen restricciones adicionales de tipo pr´actico o f´ısico que se van suavizando con el progreso pero est´an siempre presentes. En la pr´actica los ”lenguajes de alto nivel”, como BASIC, PASCAL, C++ o MATHEMATICA, utilizan muchas instrucciones que imitan las frases del idioma natural (ingl´es) para m´as comodidad del escritor, pero todas ellas son reducibles a los m´ınimos esquemas 7

b´asicos de los ”lenguajes de m´aquina”. El algoritmo y el infinito Hemos dicho que la finitud es una de las caracter´ısticas esenciales de la definici´on y funcionamiento del algoritmo. Sin embargo, el infinito, ese viejo amigo, no deja de aparecer por detr´as del escenario; una suerte, pues el infinito es la sal de las matem´aticas. Veamos c´omo. Si bien ha de ser finito el n´ umero de c´alculos que se realizan en cada experimento de utilizaci´on de un algoritmo, por ejemplo, el de Euclides, el n´ umero de posibles experimentos distintos es infinito. Lo mismo se puede decir de las operaciones elementales. Se trata del famoso ”infinito potencial”, ya estudiado por Arist´oteles, que habita confortablemente en nuestras mentes (por lo menos) y nos permite imaginar y escribir las teor´ıas. Otro ejemplo: la criba de Erat´ostenes calcula algor´ıtmicamente todos los n´ umeros primos menores que un entero dado, y termina esta labor sistem´aticamente en un tiempo finito. Pero, dado que el conjunto de los n´ umeros enteros naturales y de los primos es infinito, el conjunto de primos que podemos calcular con la criba es infinito, y el algoritmo no se detendr´a si no le damos la oportuna orden de parada. Por cierto que parece claro que la Humanidad nunca ha calculado m´as de una cierta cantidad de primos; volvemos as´ı al mundo de lo finito. Lo que nos lleva como divertimento a la curiosa pregunta de cual es el mayor n´ umero primo jam´as calculado, o jam´as impreso y publicado, o cu´al es el mayor jam´as pensado, y que quieren decir las expresiones anteriores de modo efectivo (sugerencia: d´ese un minuto para reflexionar sobre estas filosof´ıas). :-) Article in Encyclopaedia Britannica ALGORITHM. Systematic procedure that produces in a finite number of steps the answer to a question or the solution of a problem. The name derives from the Latin translation, Algoritmi de numero Indorum, of the 9th-century Muslim mathematician al-Khwarizmi’s arithmetic treatise Al-Khwarizmi Concerning the Hindu Art of Reckoning. Art´ıculo en DRAE ALGORITMO. Del ´ar. al-Jwarizmi, sobrenombre del c´elebre matem´atico Moh´amed ben Musa. 1. m. Conjunto ordenado y finito de operaciones que permite hallar la soluci´on de un problema. 2. M´etodo y notaci´on en las distintas formas del c´alculo.

8

Referencias [B] D. Berlinski, “The advent of the algorithm”, Harcourt, San Diego, 2000. [BB] Gilles Brassard, Paul Bratley, “Fundamentos de Algoritmia”, Prentice Hall, Madrid, 1997. Traducci´on de Rafael Garc´ıa-Bermejo; revisi´on t´ecnica de Ricardo Pe˜ na, Narciso Mart´ı, Luis Joyanes Aguilar, 1999. [Ca] J. Casti, “Five Golden Rules”, John Wiley, New York, 1996. [Ca] N.J. Curtland, “Computability, An Introduction to recursive function theory”, Cambridge Univ. Press, 1980. [D] George B. Dantzig, “Linear Programming and Extensions”, Princeton University Press. [G] K. G¨ odel, “Ueber formal unentscheidbare Saetze der Principia Mathematica und verwandter Systeme”, (“On formally undecidable propositions of Principia Mathematica and other related systems”), 1931. [P] R. Penrose, “The Emperor’s New Mind”, Penguin, London, 1989. [T] A. Turing, “On Computable Numbers, with an application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society. 1937. Juan Luis V´azquez Texto de 30 de enero de 2002. Corregido por u ´ltima vez 28-10-2002

9