 |
| Lord Kelvin |
A lo largo de la historia de la
ciencia ha habido muchas demostraciones de que algo es imposible.
Estas demostraciones suelen ser ciertas en matemáticas, como la que afirma que es imposible generar el número π
con regla y compás. A pesar de lo cual, muchos aficionados
siguen empeñándose en que lo han conseguido. Yo mismo he tenido que enfrentarme
con alguna de esas “demostraciones”.
Otro caso parecido es la demostración, esta vez relacionada con la ciencia física, de que es imposible construir máquinas con movimiento perpetuo, porque se oponen al primero o al segundo principio de la termodinámica. También en este caso muchos aficionados se empeñan en afirmar que lo han conseguido. En estos casos, uno no debe perder el tiempo buscando el error, porque se sabe que existe.
Otras veces, especialmente en el
campo de la tecnología, la demostración de imposibilidad no es definitiva, sino
que depende de unas condiciones que no siempre se
cumplen. A veces esto ha detenido durante algún tiempo el avance
de la ciencia, hasta que alguien se dio cuenta de esas condiciones (que no
siempre están claras) y se saltó las limitaciones impuestas. Veamos tres
ejemplos:
- La controversia decimonónica sobre si es posible el vuelo de vehículos
más pesados que el aire. Lord Kelvin rechazó así la invitación a formar
parte de la Aeronautical Society: Yo no
tengo fe en ninguna forma de navegación aérea que no sea mediante globos. Y
en 1903, el astrónomo canadiense Simon Newcomb dijo esto:
Es muy probable que el siglo XX esté
destinado a ver las fuerzas naturales que nos permitirán volar de un continente
a otro a una velocidad muy superior a la de un pájaro. Pero cuando preguntamos
si el vuelo aéreo es posible en el estado actual de nuestro conocimiento; si
con los materiales que poseemos se puede fabricar una combinación de acero,
tela y alambre que, movida por el poder de la electricidad o el vapor, forme una
máquina voladora que funcione con éxito, el panorama puede ser completamente
diferente.
El
primer vuelo de los hermanos Wright tuvo lugar ese mismo año (1903).
- En 1969, Marvin Minsky y Seymour Papert publicaron un
libro (Perceptrons: An Introduction to Computational
Geometry) en el que demostraron que las redes neuronales
artificiales de entonces (los perceptrones con dos capas de
neuronas) no podían representar la función lógica binaria o-exclusivo, cuyo resultado es 0 si las
dos entradas son iguales, y 1 si son distintas. Se dice (aunque no todo el
mundo está de acuerdo) que esta demostración detuvo la investigación en
redes neuronales durante diez años. La introducción de una tercera capa en
la red neuronal permitió representar la función o-exclusivo y otras muchas
más.
- Uno de los problemas más importantes que se planteó a los ordenadores
fue ordenar una serie de números
de menor a mayor, o al revés. El primer algoritmo que lo consiguió era
sencillo, pero lento si la serie de números a ordenar era larga, pues el
tiempo de su ejecución es proporcional al cuadrado del tamaño de la
serie. O sea: si para ordenar 10 números ese algoritmo tardaba
(digamos) 10 unidades de tiempo, para ordenar 100 números tardaría 1000;
para ordenar 1000 números tardaría 100.000; y así sucesivamente. El resto
de este artículo se dedica a este caso.
Pronto se diseñaron algoritmos de
ordenación más rápidos, con tiempo de ejecución proporcional
al producto del tamaño de la serie por su logaritmo. Si para ordenar 10 números se tardaba 10 unidades de
tiempo, para ordenar 100 números se tardaría 200; para ordenar 1000 números,
3000; y así sucesivamente. Se ve que el tiempo, en función del número de
elementos a ordenar, crece mucho más despacio que con el primer algoritmo.
Algunos informáticos intentaron
encontrar algoritmos aún más rápidos que los anteriores. Sin embargo, alguien
demostró un teorema que afirmaba que es imposible
ordenar n números en un tiempo menor que n.log(n). Ese teorema
detuvo la investigación en este campo durante unos diez años, hasta que otra
persona diseñó el siguiente algoritmo, que ordena n números en un tiempo
proporcional a n, lo que significa que, si para ordenar 10 números se tarda 10
unidades de tiempo, para ordenar 100 se tardaría 100; para ordenar 1000 se tardaría
1000; etcétera. Veamos el algoritmo:
Para ordenar n números, cortamos n
espaguetis en longitudes proporcionales a los números a ordenar y los colocamos
verticalmente sobre una superficie plana. Hacemos descender hacia ellos otra
superficie plana impregnada de pegamento. En cuanto encuentra la menor
resistencia, la placa que desciende se para y vuelve a subir, llevándose pegado
el espagueti más largo. Sacamos ese espagueti y repetimos la misma operación.
Al final tenemos ordenados los espaguetis (y por tanto los números) de mayor a
menor, y el tiempo ha sido proporcional al número de espaguetis (o de números).
Aunque este algoritmo no es fácil
de implementar en un ordenador, demuestra que es
posible ordenar n números en un tiempo proporcional a n. ¿Qué
pasaba entonces con la demostración de que era imposible hacerlo más deprisa
que n.log(n)? ¿Dónde está el error?
No lo había. La demostración es
correcta, si se aplica a una serie de números reales. Pero no todos los números
reales son iguales. Algunos (los que se pueden expresar en forma de quebrado
a/b) son racionales. Hay infinitos números reales para los que esto no es
posible, como π, e, y muchos más. Pero todos los números reales que se
pueden representar en un ordenador son racionales, porque tienen un número
finito de cifras (usualmente más de 50, en código binario). Cuando sólo hay números
racionales, el teorema no se aplica.
En cuanto se supo que era posible
resolver el problema, se buscaron y encontraron algoritmos que podían hacer lo
mismo en un ordenador. Yo utilicé uno de ellos en mi implementación de
intérpretes del lenguaje APL para el ordenador personal de IBM. En cambio, en
intérpretes anteriores de este lenguaje se habían usado
algoritmos del tipo n.log(n), que para valores grandes de n eran más lentos.
Hilo Temático sobre Matemáticas y Estadística: Anterior Siguiente
Manuel Alfonseca
Hace muchos años leí "Cómo trisecar un ángulo", probablemente era un capítulo de algún libro de Martin Gardner (acabo de comprobar que es Carnaval Matemático, Alianza Editorial, 1984). Allí se decía que la imposibilidad de resolver algebráicamente determinadas ecuaciones era equivalente a la imposibilidad de trisecar un ángulo con regla y compás. Sin embargo, era posible construir un artefacto mecánico que puede trisecar un ángulo sin mayor problema. Creo que aquello es análogo al ingenioso procedimiento de los espaguetis que cuentas aquí.
ResponderEliminarLo que no acabo de ver es qué relación hay entre la posibilidad de resolver mecánicamente el problema de la ordenación de números, y el hecho de que estos números tengan un número finito o infinito de cifras diferentes.
El teorema que demuestra que no es posible ordenar N números reales en menos de O(N.log N) se aplica cuando al menos uno de los N números no es racional. No se aplica si los N números son racionales.
EliminarTodo número decimal P que se puede expresar en base B con un número finito K de cifras, es P=(P.B^K)/B^K donde el numerador y el denominador son enteros. Por lo tanto, es racional.
El algoritmo de los espagueti también se puede aplicar sólo a números racionales, puesto que un espagueti sólo se puede cortar entre dos átomos, y por tanto su longitud es siempre un número racional.
Una versión del teorema que dice que no se puede ordenar en tiempo menor que nlog(n) se lo demuestro yo a mis estudiantes. La idea del teorema es que no se pueden ordenar n elementos en tiempo menor que n log n si la ordenación se realiza por comparación de claves, es decir, si se compara una clave (no necesariamente un número) de la tabla contra otra clave de la tabla y en función de si una clave es mayor o menor que la otra se realiza una operación sobre la tabla y esta operación se repite hasta que la tabla está ordenada. Es por ejemplo lo que hacen algoritmos como quicksort, mergesort o heapsort.
ResponderEliminarPara saltarse lo anterior, el truco es no realizar comparaciones de claves, sino comparar trozos de claves. Es lo que hace, por ejemplo, el algoritmo Radixsort, que se puede implementar muy facilmente en un ordenador, el algoritmo hace algo parecido a una ordenación alfabética para cada uno de los carácteres de la cadena. Por tanto, si tengo N cadenas, y cada cadena tiene k caracteres tomados de un alfabeto de h carácteres, necesitaré k*N iteraciones y h colas. Si k << N, entonces se puede considerar que el algoritmo es O(N).
Sobre los reales, no entiendo muy bien el teorema, un ordenador no puede representar de forma exacta prácticamente ningún numero real. Solo fraccionarios, y no todos, por ejemplo, el sistema que usamos para representar números en un ordenador, ni siquiera permite representar de forma exacta el número 0,1.
En efecto, los números reales no racionales, que tienen infinitas cifras sin periodicidad, no pueden representarse en un ordenador. Y de los fraccionarios, los que tienen infinitas cifras con periodicidad en base 2, tampoco.
EliminarPor matizar un poco lo anterior, en un ordenador no hay problema en representar números con infinitas cifras con periodicidad en base 2, lo que lo impide realmente es el formato de representación IEEE754 de números en coma flotante, que obviamente casi siempre el elegido porque tiene muchas ventajas, una de ellas es que representa los números en base 2, que es la misma a la que trabaja el hardware. Pero nada impide que se pueda implementar otro estándar de numero en coma flotante sobre el hardware actual en el cual el 0,1 se puede representar de forma exacta, por ejemplo un estándar de representación en el cual cada grupo de cuatro bits representa un numero del 0 al 9, permitirá sin problema representar el 0.1 de forma exacta, a pesar de ser un numero periódico cuando se representa en base 2 ya que en realidad nuestro estándar lo que hace es trabajar en base 10 en lugar de en base 2.
EliminarLo que si es cierto es que, se elija el formato que se elija de representación, siempre va a haber números fraccionarios incluso pequeños, que no se van a poder representar de forma exacta en alguna base de numeración. Los números que no se puedan representar dependerán del estándar de representación.
Lo otro que es cierto también, es que en la inmensa mayoría de ordenadores que tenemos, el formato IEEE754 viene ya implementado en el procesador, y si queremos usar las funciones matemáticas, tenemos que representar los números en ese formato. Pero nada quita que, si así lo consideramos oportuno, pasemos de la capacidades del procesador para la coma flotante, y nos montemos nuestro propio formato y nuestras propias funciones matemáticas.
Un fuerte abrazo.
El lenguaje LOGO representa los números como cadenas de caracteres, con longitud arbitraria, e implementa las operaciones matemáticas sobre números escritos en ese formato. Siendo así, cualquier número racional no periódico puede representarse exactamente en LOGO.
EliminarOtro modo de representación que permitiría trabajar de forma exacta con todos los números racionales, sean periódicos o no, sería representarlos como pares de números de la forma "a/b".
En cualquier caso, los números reales con infinitas cifras decimales no periódicas no pueden representarse exactamente en un ordenador.
Ya, y de hecho, la inmensa mayoría de los racionales (enteros incluidos), tampoco, solo los "pequeños" (como soy matematico, me puedo dar el lujo de llamar "pequeño" a cualquier numero que se pueda representar en la memoria de un ordenador, que obviamente, es finita).
EliminarPor lo que dice, no termino de ver la idea de la demostración del teorema que enunció en su post y relativo a que la complejidad algoritmica tiene que ver con si los numeros a comparar son reales o no. Como dije, la versión que yo conozco para enunciar una cota inferior de la complejidad en algoritmos de ordenacion tiene que ver con como funciona el algoritmo (si compara claves, o si funciona de otra manera), no con el formato o tipo de las claves que se comparan (da igual si el algoritmo compara números, cadenas o cualquier otra cosa, lo que importa es como las compara y que hace al compararlas).
¿Tiene una referencia del teorema tal como lo ha enunciado?
Por cierto, el algoritmo de los espaguetis lo que hace es usar el paralelísmo físico. Al bajar la superficie estoy comparando la altura de todos los espaguetis a la vez (en una misma iteración), lo cual en un procesador monohilo, eso es, en general, imposible. Es decir, si el proceso se hiciese en una máquina de un solo procesador, el algoritmo sería N^2 (solo puedo comparar la altura de un espagueti en cada iteración) y por tanto, para buscar el más alto, necesito N-1 iteraciones, y esencialmente tendría el algoritmo SelectSort
EliminarPor cierto, como bien dice un buen amigo común a quien usted mencionó el otro día (Jordi Porta). El algoritmo Quicksort (que es NlogN ya que funciona por comparación de claves y es optimo en caso medio), en realidad es un algoritmo logN,, !En una máquina con N procesadores!
Un fuerte abrazo.
Hace 40 años tenía referencias, pero hace mucho que las perdí. En este artículo hablo de memoria. En cuanto al algoritmo de los espaguetis, se me quedó grabado porque lo utilicé en mis clases de Complejidad de Algoritmos hace muchos años.
EliminarEn efecto, con N procesadores y un algoritmo QuickSort se puede ordenar N números en O(logN). Pero si tienes que ordenar un millón de números, necesitas un millón de procesadores. No parece práctico.
Por cierto, como dato curioso, Radixsort es un algoritmo del año 1887 (Holleritz), mientras que Quicksort es de 1960 (Hoare).
ResponderEliminar