English French German Spain Italian Dutch Russian Portuguese Japanese Korean Arabic Chinese Simplified
Mostrando entradas con la etiqueta Matemáticas y Computación. Mostrar todas las entradas
Mostrando entradas con la etiqueta Matemáticas y Computación. Mostrar todas las entradas

jueves, noviembre 10, 2011

De las Series de Fourier a la Nanotecnología


Las series de funciones seno y coseno fueron utilizadas por Leonard Euler y otros en el siglo 18 para estudiar la dinámica de las vibraciones de cuerdas y para estudiar los movimientos de los cuerpos en mecánica celeste. Joseph Fourier, a principios del siglo 19, reconoció la gran utilidad práctica de estas series para estudiar la conducción del calor y comenzó a desarrollar una teoría general de las mismas. A partir de entonces, las series de Fourier se utilizan por doquier, desde la acústica o la óptica, hasta los circuitos eléctricos. 

Las series de fourier consisten en la descomposición de una onda periódica en una serie infinita de sumas de ondas sinusoidales, esto para el análisis matemático de dicha onda periódica.

En la actualidad, los métodos de Fourier están en la base de gran parte de la ciencia y de la ingeniería moderna, en especial de las técnicas computacionales.  Sin embargo, las matemáticas de principios del siglo 19 eran inadecuadas para el desarrollo riguroso de las ideas de Fourier y aparecieron gran número de problemas de carácter técnico que desafiaron a muchas de las grandes mentes de la época. Costó mucho desarrollar nuevas técnicas matemáticas para poder resolver estas dificultades. En la década de 1830, Gustav Lejeune Dirichlet obtuvo la primera definición clara y útil del concepto de función. 

Bernhard Riemann en la década de 1850 y Henri Lebesgue en la década de 1900 obtuvieron nociones rigurosas de la integración de funciones. La convergencia de series infinitas resultó muy  resbaladiza al principio, pero se logró dominar gracias a Augustin-Louis Cauchy y a Karl Weierstrass, que trabajaron en la décadas de 1820 y 1850, respectivamente. En la década de 1870, los primeros pasos de Georg Cantor hacia una teoría abstracta de los conjuntos se iniciaron con el análisis de las diferencias entre funciones que no son iguales pero cuyas series de Fourier son idénticas.


En la primera década del siglo 20, el concepto de espacio de Hilbert fue clave para entender las propiedades de las series de Fourier. El matemático alemán David Hilbert y sus colegas definieron estos espacios de forma axiomática, algo que parecía muy alejado de las aplicaciones prácticas. Sin embargo, en la década de 1920, Hermann Weyl, Paul Dirac y John von Neumann reconocieron que este concepto era la piedra angular de la mecánica cuántica, ya que los estados posibles de un sistema cuántico son elementos de cierta clase de espacios de Hilbert. 

La mecánica cuántica es la teoría científica más exitosa de todos los tiempos. Sin ella, gran parte de nuestra tecnología moderna (el láser, los ordenadores, los televisores de pantalla plana, la energía nuclear, etc.) no existiría. Quien podía imaginar que problemas matemáticos abstractos relacionados con las propiedades matemáticas de las series de Fourier acabarían revolucionando la ciencia y la ingeniería del siglo 20, y acabarían conduciendo a la energía nuclear.

miércoles, noviembre 09, 2011

De las naranjas a los módems


En 1998, de repente, las matemáticas fueron noticia en todos los medios. Thomas Hales actualmente Andrew Mellon (Universidad de Pittsburgh, Pennsylvania) había demostrado la conjetura de Kepler, que afirma que la mejor forma de apilar naranjas en una caja es la utilizada en todas las fruterías (el empaquetamiento de esferas más eficiente posible). 

Un problema que había estado abierto desde 1611, cuando lo propuso Johannes Kepler. En algunos medios de prensa y TV se llegó a decir “creo que es una pérdida de tiempo y dinero de los contribuyentes.” Hoy en día, las matemáticas del empaquetamiento de esferas se utilizan en ingeniería de comunicaciones y teoría de la información y de la codificación para planificar canales de comunicación y para desarrollar códigos correctores de errores. El problema de Kepler fue mucho más difícil de demostrar de lo que Kepler nunca pudo imaginar. De hecho, el problema más sencillo sobre la mejor forma de empaquetar círculos planos fue demostrado en 1940 por László Fejes Tóth.



Otro problema sencillo cuya solución costó muchos años fue el problema de las esferas que se besan, planteado en el siglo XVII por Isaac Newton y David Gregory: Dada una esfera, ¿cuántas esferas iguales que ésta pueden colocarse con la condición de que toquen a la inicial? En dos dimensiones es fácil demostrar que la respuesta es 6. Newton pensaba que 12 era el número máximo en 3 dimensiones. Lo es, pero la demostración tuvo que esperar al trabajo de Kurt Schütte y Bartel van der Waerden en 1953. Oleg Musin demostró en 2003 que el número de besos en 4 dimensiones es 24. En cinco dimensiones sólo se sabe que se encuentra entre 40 y 44. Sabemos la respuesta en ocho dimensiones, que es 240, como demostró Andrew Odlyzko en 1979. Más aún, en 24 dimensiones la respuesta es 196.560. Estas demostraciones son más sencillas que la del resultado en tres dimensiones y utilizan empaquetamiento de esferas mucho más complicados e increíblemente densos, la red E8 en 8 dimensiones y la red de Leech en 24 dimensiones.

Todo esto es muy bonito, pero ¿sirve para algo? En la década de 1960, un ingeniero llamado Gordon Lang diseñó los sistemas de comunicación por módem utilizando estos empaquetamientos de esferas multidimensionales. 

El problema de la comunicación analógica en una línea telefónica es el ruido. En una conversación entre dos personas el lenguaje natural es tan redundante que el ruido importa poco, pero para enviar datos es necesario introducir ciertas redundancias y utilizar técnicas correctoras de error, lo que reduce el ancho de banda del canal (la cantidad de información que se puede transmitir por segundo). Lang utilizó los empaquetamientos de esferas para lidiar con el ruido y aumentar al máximo el ancho de banda. Para ello utilizó una codificación basada en el empaquetamiento E8 (más tarde también se utilizó el de Leech). 

En la década de los 70, el trabajo de Lang fue clave para el desarrollo temprano de la internet. Donald Coxeter, matemático que ayudó a Lang en su trabajo, dijo que estaba “horrorizado de que sus bellas teorías hubieran sido manchadas de esta manera por las aplicaciones.”

martes, noviembre 08, 2011

Cuaterniones de Hamilton: Origen y utilidad en videojuegos



La historia de cómo descubrió los cuaterniones el matemático irlandés William Rowan Hamilton (1805–1865).
Se dice que esto ocurrió el 16 de octubre 1843 mientras estaba caminando sobre el Puente de “Broome” en Dublín y tras más de dos décadas echándole cabeza a la multiplicación de tripletas, pues  había estado buscando una manera de extender el sistema de números complejos a tres dimensiones de tal forma que permitiera describir las rotaciones tridimensionales respecto a un eje arbitrario como los números complejos describen las rotaciones bidimensionales. 
Su idea feliz ahora nos resulta casi obvia, no era posible hacerlo con ternas de números, las rotaciones tridimensionales requieren un sistema de números con cuatro componentes imaginarias. Si los números complejos son de la forma a + i b, donde a y b son números reales, e i es la raíz cuadrada de –1, entonces los cuaterniones deben tener la forma
a + bi + cj + dk , donde las unidades imaginarias cumplen que  i2 = j2 = k2 = ijk= –1.


Hamilton pasó el resto de su vida tratando de convencer a toda la comunidad de matemáticos de que los cuaterniones eran una solución elegante a múltiples problemas en geometría, mecánica y óptica. Tras su muerte, pasó el testigo a Peter Guthrie Tait (1831–1901), profesor de la Universidad de Edimburgo. William Thomson (Lord Kelvin) quien pasó más de 38 años discutiendo con Tait sobre la utilidad real de los cuaterniones. Kelvin prefería el cálculo vectorial, que a finales del siglo 19 eclipsó a los Cuaterniones.  Los matemáticos del siglo 20, en general, consideran los cuaterniones como una hermosa construcción matemática sin ninguna utilidad práctica. Así fue hasta que por sorpresa, en 1985, el informático Ken Shoemake presentó la idea de interpolar rotaciones usando cuaterniones en el congreso de gráficos por computador más importante del mundo (el ACM SIGGRAPH). Interpolar matrices preservando la ortogonalidad de las matrices de rotación es muy engorroso y utilizar los ángulos de Euler ayuda poco. 

Las técnicas convencionales de interpolación para númeos reales se extienden de forma natural a los números complejos y a los cuaterniones. Interpolaciones suaves y rápidas de calcular que desde entonces se utilizan en todos los juegos por ordenador que presentan gráficos tridimensionales. 

En la actualidad, los cuaterniones son imprescindibles en robótica y en visión por ordenador, además en gráficos por ordenador. Al final del siglo 20, la guerra entre Kelvin y Tait fue ganada por este último. Hamilton vio cumplido su sueño en la industria de los videojuegos, 150 después de su descubrimiento, una industria que mueve más dinero en el mundo que la industria del cine (más de 100 mil millones de dólares en 2010).
Sociedad Británica para la Historia de las Matemáticas

miércoles, junio 29, 2011

Crean un 'software' que analiza y simula el comportamiento de las corrientes de agua

El grupo de investigación 'Modelado Matemático y Simulación de Sistemas Medioambientales' del Departamento de Ecuaciones Diferenciales y Análisis Numérico de la Universidad de Sevilla (US) han desarrollado un 'software' de simulación matemática que predice el comportamiento de los flujos ambientales, especialmente de corrientes de agua, caudal de los ríos, inundaciones, deslizamientos de tierra o el transporte y dispersión de contaminantes en la atmósfera en el entorno andaluz. 


El estudio se desarrolla a través de la aplicación 'FreeFem++3D', ecuación tridimensional que "modela" diversos problemas existentes en áreas como la física, la ingeniería, las ciencias de la salud o la economía. "Es un sistema que permite programar, mediante operaciones matemáticas, cualquier tipo de simulación, como las presentes en interacciones de los flujos de aire y sangre o la interacción aire-atmósfera", matiza el experto. 



En concreto, el proyecto 'Freefem++3D: Aplicaciones a la simulación de flujos ambientales' ya se ha aplicado en el estudio del Embalse del Gergal y en el Estrecho de Gibraltar. En el primero, el calor del verano y el frío del invierno provocan un fenómeno ambiental llamado ciclo estacional de estratificación-desestratificación, que permite a los expertos realizar diversos análisis ecológicos para de optimizar los recursos naturales que ofrece la balsa sevillana, según señala. "En ocasiones, pueden darse inversiones de agua entre el fondo y la superficie, es decir, intercambios en el embalse producidos por el viento, que hacen que las sustancias potencialmente contaminantes del fondo ocupen la superficie y puedan ser explotados", apunta el investigador principal, Tomás Chacón Rebollo. En el caso del Estrecho de Gibraltar, este modelo informático ayuda a entender la compleja dinámica que existe entre el Océano Atlántico y el Mar Mediterráneo. 

"Nuestro simulador ayuda a comprender la ecología de la zona, así como el clima. En este sentido, el flujo del Estrecho está generado por dos mareas de diferente densidad que provocan una compleja interacción entre ambas", sostiene Chacón. De esta forma, Esta herramienta ayuda a entender el clima o la flora y fauna de la zona al reproducir el movimiento del agua, además de su velocidad, presión y salinidad. Así, explica que se analizará cómo el Océano Atlántico, de menor densidad, "rellena el Mar Mediterráneo en la superficie; mientras que éste rellena el anterior en el fondo". "La entrada de agua mediterránea en el Atlántico se puede visualizar como una gran cascada", añade. 

Este modelo, caracterizado por ser "preciso y riguroso en sus cálculos", se utiliza para analizar las diversas corrientes de aguas naturales o inducidas por el hombre y es capaz de simular, por ejemplo, el caudal de los ríos, inundaciones, deslizamientos de tierra o el transporte y la dispersión de contaminantes en la atmósfera. Esta aplicación, que se podrá descargar de forma gratuita desde la red, permite determinar, de una manera predictiva, cuál puede ser el alcance de una inundación provocada, por ejemplo, por un río. 

"Con esta aplicación impedimos que se levanten zonas residenciales en entornos peligrosos para la sociedad. Es decir, diagnosticamos, desde un punto de vista del riesgo, la distancia óptima a la que construir las infraestructuras, siempre en función de la reproducción matemática de un desbordamiento virtual", explica el investigador. 

Tomado de www.europapress.es

martes, junio 14, 2011

Hormigas Optimizadoras

Laberinto utilizado con  caminos de  hormigas.

Las colonias de hormigas son capaces de resolver dinámicamente, y de manera óptima, problemas como encontrar el camino más corto entre dos puntos dentro de un laberinto. 


Muchas de las ideas que encontramos en ciencias de la computación han sido inspiradas por la Naturaleza. Así por ejemplo existen los algoritmos genéticos, que se basan en cierta idea de darwinismo para encontrar soluciones a ciertos problemas, sobre todo cuando queremos encontrar el mínimo de energía absoluto en un sistema en el que otros métodos caen en mínimos de energía locales de los que no salen. Existe también el método del enjambre (inspirado en la inteligencia colectiva de un enjambre de abejas) e incluso se pueden encontrar soluciones satisfactorias (aunque no necesariamente la mejor solución posible) al problema del viajante si nos inspiramos en las hormigas. De hecho hay un algoritmo denominado Ant Colony Optimisation (ACO) que se basa en el comportamiento de estos pequeños animales.

La pregunta es si se puede usar directamente a los animales sociales para resolver este tipo de problemas sin pasar por un ordenador y ver así las diferencias. Según han demostrado unos investigadores de la Universidad de Sydney eso mismo no sólo es posible, sino que han podido comprobar que las hormigas logran resolver un equivalente al problema de la torre de Hanoi sin demasiadas dificultades incluso cuando cambian las condiciones a mitad de juego.

La torre de Hanoi, en su versión más simple, consiste en tres barras verticales y tres discos agujereados por el centro de distintos tamaños. Se comienza con los tres discos apilados de mayor a menor (de abajo a arriba) en una de las barras y hay que moverlos a otra barra bajo ciertas restricciones en el menor número de movimientos posibles. Las reglas son que hay que mover los discos de uno en uno y que en ningún momento un disco esté sobre otro de menor tamaño.

Obviamente las hormigas no pueden mover discos de una barra a otra, así que los investigadores implicados crearon un laberinto (ver foto) de tal modo que encontrar el camino más corto entre dos puntos era equivalente a mover los discos en el menor número de movimientos posibles en el problema de la torre de Hanoi.

Este tipo de problemas de tratar de encontrar caminos más cortos en un grafo son típicos problemas de la matemática computacional. Para algunos de esos problemas tenemos algoritmos (Kruskal, Prim, Fleury, Dijkstra…) que nos dan la solución óptima en tiempo polinómico. Para otros problemas, como el problema del viajante o el de la mochila, al tratarse de problemas NP, no tenemos algoritmos que nos den eso mismo, sino algoritmos que nos dan una buena (o mala) aproximación en un tiempo polinómico. En estos últimos casos, si queremos tener seguro la solución óptima, no nos queda más remedio que enumerar por fuerza bruta todos los casos posibles y escoger el mejor, algo que tiene un coste computacional exponencial.

Encontrar el camino más eficiente a través de una red saturada es un desafío común en conductores, ingenieros y compañías telefónicas. Todos estos problemas se encuadran en lo que podemos denominar problemas de optimización y no hace falta decir que estos problemas tienen grandes implicaciones económicas. La optimización permite a una empresa de transportes ahorrar mucho dinero en combustible y una factoría puede producir más si los procesos de montaje están optimizados. Hay muchos problemas logísticos en el que se tiene que maximizar la eficiencia.

Por tanto, si encontramos pistas sobre cómo solucionar un problema de este tipo en la Naturaleza, aunque ya esté solucionado algorítmicamente, quizás lo podamos aplicar a otros casos que son especialmente duros computacionalmente.

Se sabe muy bien cómo solucionar el problema de la torre de Hanoi. Saber cómo se hace algorítmicamente forma parte del programa de estudios de las escuelas de ingeniería informática. Pero las hormigas quizás nos inspiren nuevos métodos algorítmicos para resolver otros problemas.

Quizás pensando en esto último, o simplemente en la diversión, Chris Reid, Madeleine Beekman y David Sumpter (éste de la Universidad de Upsala) pusieron a una colonia de hormigas argentinas (Linepithema humile) a resolver un problema de optimización dinámica de encontrar la ruta mejor en un laberinto.

Las hormigas son capaces de solucionar el problema aunque son sean seres muy simples. La “inteligencia colectiva” que emerge de ellas es suficiente para resolver el problema, aunque cada una de ellas, individualmente, sea incapaz de hacerlo. Recordemos que las hormigas crean caminos a través de unas señales de feromonas que van dejando en el suelo, reforzándose o debilitándose según el tráfico que haya, entre otros factores.

Aunque los algoritmos inspirados en la Naturaleza de los que hemos hablado antes funcionan satisfactoriamente, no necesariamente representan el mundo real de, por ejemplo, las hormigas. En general estos algoritmos son estáticos y están diseñados para resolver un tipo de problema en concreto. Los autores del estudio se plantearon cómo las hormigas reales podrían resolver un problema de optimización y cómo responderían a los cambios. Se preguntaban si sólo podían proporcionar una solución única fija o si se adaptarían a los cambios introducidos a mitad del juego.

En el laberinto equivalente al problema de la torre de Hanoi, las hormigas tenían que encontrar en camino más corto, de los 32768 caminos posibles entre un punto de entrada y otro en el que se colocaba una comida tentadora. Básicamente era un problema tipo Dijkstra en el que el peso de las aristas del grafo eran las longitudes de los segmentos del laberinto.

Al cabo de una hora las hormigas encontraron los dos caminos más cortos que representaban las dos posibles soluciones óptimas al problema. Estas soluciones eran las que más tráfico de hormigas contenían. Entonces los investigadores bloquearon algunos caminos y abrieron nuevas áreas del laberinto a las hormigas para ver si tenían la capacidad de resolver dinámicamente el problema.

Como hemos dicho, al cabo de una hora las hormigas encontraban el camino más corto, que en un caso bordeaba el borde del laberinto. Al bloquearlo las hormigas respondieron mediante una modificación del camino original, solución que no era óptima. Sin embargo, al cabo de otra hora ya habían encontrado la ruta óptima a través del centro del laberinto.

Los investigadores descubrieron que si se permitía a las hormigas exploradoras recorrer el laberinto sin comida durante una hora antes del experimento entonces el resto cometía menos errores y eran más rápidas que cuando se enfrentaban al problema por primera vez sin exploración previa. Esto, según sugieren los investigadores, sería debido a que la feromona dejada por las exploradoras era clave para ayudar a la resolución del problema cuando cambiaban las condiciones.

Contrariamente a lo que se creía, el uso de las feromonas no afianza o consolida a las hormigas en un camino en particular sin poder adaptase a las nuevas circunstancia. Según los investigadores tener al menos dos feromonas separadas les da a las hormigas mayor flexibilidad y les ayuda a encontrar buenas soluciones incluso si las condiciones ambientales cambian.

Añaden que descubrir cómo las hormigas son capaces de resolver dinámicamente problemas puede proporcionar inspiración para nuevos algoritmos de optimización, y que éstos pueden permitir la creación de software que resuelva mejor problemas de optimización en la industria.



lunes, mayo 23, 2011

Criptografía

La criptografía, la ciencia que estudia cómo hacer un mensaje que resulte indescifrable para terceros, parece cosa de novelas de espionaje o tesoros enterrados. Sin embargo, todos nosotros recurrimos a la criptografía cuando hacemos una compra por Internet o enviamos un mensaje por telefonía celular. Y es, probablemente, la rama de las matemáticas que más provecho ha dado en los últimos años.




Una clave muy sencilla consiste en reemplazar cada letra del mensaje por otro símbolo: a igual letra, igual símbolo. Es el método que, en la imaginación de Edgar Allan Poe, usa el pirata Kidd en “El escarabajo de oro”. El protagonista, un hombre llamado Legrand, encuentra en la playa un pergamino con lo que parece ser una secuencia aleatoria de números y símbolos. Legrand sospecha que el pergamino puede contener las instrucciones para encontrar un tesoro y logra descifrar el mensaje.
Poe era muy aficionado a este tipo de claves y solía publicar desafíos de este tipo para los lectores del Alexander’s Weekly Messenger, una revista de Filadelfia. El relato en “El escarabajo de oro” es casi un manual de instrucciones para resolver claves de sustitución. Legrand comienza por contar cuántas veces aparece cada símbolo y asociar el símbolo que más se repite (el número ocho) a la letra más frecuente en el idioma inglés (la e). Confirma esta suposición por el hecho de que el par 88 aparece cinco veces el mensaje y, efectivamente, la letra “e” se duplica muchas veces en inglés (como en feed, speed, agree, etc.). Luego analiza la distribución de los símbolos, localiza la palabra the (la más frecuente en inglés) y, paso a paso, termina por descifrar todo el mensaje.

Sherlock Holmes emplea el mismo método para resolver una clave similar en “La aventura de los bailarines”. Aquí cada letra se reemplaza por la figura de un hombrecito bailando y a cada letra le corresponde una posición diferente. Como Legrand, Holmes asocia la letra “e” a la figura más repetida. Curiosamente, para Poe, el orden de las letras en inglés, según su frecuencia, es E, A, O, I, D, H, N, R, S, T... mientras que para Holmes es E, T, A, O, I, N, S, H, R, D y L.
Mucho más sencilla es la clave que el profesor Lidenbrock (en realidad, su sobrino) descifra en Viaje al centro de la Tierra: el autor del mensaje simplemente lo escribe al revés.

CLAVES DE DESPLAZAMIENTO

Otro tipo de clave consiste en reemplazar cada letra del mensaje por la que le sigue en el abecedario, una cantidad determinada de posiciones. Por ejemplo, reemplazando cada letra por la que está dos posiciones más allá. Entonces, la palabra PAGINA se convertiría en RCIKOC (la R está dos lugares después de la P; la C, dos lugares después de la A y así sucesivamente). Este sistema de encriptación se llama también “clave cesárea”, porque fue usada por Julio César.
Estas claves “de desplazamiento” son muy fáciles de descifrar: una vez identificada una letra, quedan determinadas todas las demás. Además, para un alfabeto de veintisiete letras hay sólo veintiséis desplazamientos posibles y una computadora podría analizarlas a todas en segundos.

El método de desplazamiento se puede perfeccionar recurriendo a un número. Por ejemplo, 4239. Este número indica que la primera letra del mensaje se reemplaza por la que está cuatro lugares más allá en el abecedario. La segunda, por la que está dos lugares más allá. La tercera, por la que está tres lugares más allá y la cuarta, por la que está nueve lugares más allá. El ciclo se repite a partir de la quinta letra. Este sistema es más seguro porque una misma letra se reemplaza por una distinta según su posición en el texto y no sirve el análisis de frecuencia empleado por el personaje de Poe o por Sherlock Holmes. Lewis Carroll, el autor de Alicia en el País de las Maravillas, publicó una vez una tabla de doble entrada para aplicar rápidamente la clave de desplazamiento.

Durante la Segunda Guerra Mundial, el ejército alemán desarrolló una máquina encriptadora llamada Enigma, de gran complejidad y que producía mensajes secretos casi imposibles de descifrar. Para mayor seguridad, las claves se cambiaban varias veces al día. Un tipo de mensajes que preocupaba especialmente a los aliados eran los que informaban la posición de los submarinos alemanes que hundían los barcos que llevaban suministros a través del Atlántico. Fue gracias a los trabajos de Alan Turing que los ingleses lograron descubrir cómo funcionaba la máquina Enigma y descifrar los mensajes enemigos. Los alemanes estaban tan seguros de la inviolabilidad de sus mensajes que atribuyeron esto a la labor de espías.
El ejército de Estados Unidos, mientras tanto, desarrolló un lenguaje secreto basado en el idioma de los indios navajos. El idioma navajo no tenía forma escrita, por lo que había pocos registros de su estructura, fuera de Estados Unidos. El código usaba algunas palabras traducidas directamente del navajo, otras veces empleaba metáforas (por ejemplo, nombres de pájaros para aviones o de peces para barcos) y también incluía palabras armadas mediante fonética. Por ejemplo, el verbo belong (pertenecer) se armaba con las palabras navajas para bee (abeja) y long (largo).
Esta clave no empleaba sustitución de letras, no se basaba en un algoritmo matemático, ni necesitaba máquinas complejas para encriptar y descifrar. Cada regimiento, cada batallón, incluía un indio navajo responsable de las comunicaciones que traducía casi instantáneamente los mensajes transmitidos.

El código fue vital para el avance de las tropas norteamericanas en el Pacífico. La historia del código navajo fue llevada al cine en 2002 en la película Código de guerra (Windtalkers), con Nicolas Cage en el papel del oficial que debía acompañar al indio. Su misión era protegerlo pero, también, matarlo ante el riesgo de caer prisionero: el código era más valioso que la vida de un soldado. También se menciona el código navajo en “Anasazi”, uno de los episodios de los Expedientes X.

EL METODO RSA

Normalmente, la clave usada para encriptar un mensaje es la misma que se usa para desencriptarlo. Por lo tanto, los participantes de la comunicación deben acordarla previamente. En las novelas de espionaje vemos cómo se intercambian libros de claves en encuentros personales o se anuncian solapadamente en la radio o en avisos clasificados. En cualquier caso, que la clave tenga que “circular” en algún momento pone en riesgo la seguridad de la comunicación.
Pero, en 1975, los matemáticos Ronald Rivest, Adi Shamir y Leonard Adleman crearon un sistema de encriptación completamente nuevo que asegura la confidencialidad gracias al uso de claves distintas para encriptar y desencriptar. El sistema se conoce como RSA por las iniciales de sus creadores.

Por ejemplo, supongamos que un banco necesita que sus clientes se comuniquen con una sucursal. Por supuesto, los clientes quieren que sus mensajes sean confidenciales, que nadie que no sea el banco pueda leerlos. Para eso, el banco dispone de dos claves. Una es pública, la conoce todo el mundo. El banco la puede anunciar en su publicidad, en su página web o comunicarla a sus clientes en el momento de abrir la cuenta. Esta clave la usan los clientes para encriptar sus mensajes. La otra es privada, sólo la conoce el banco y la usa para desencriptar los mensajes. Como las claves son distintas, eso asegura la confidencialidad. Aunque un mensaje sea interceptado por un tercero, que conoce la clave usada para encriptar (porque es pública), éste no podrá desencriptarlo porque no tiene la clave privada, que sólo la conoce el banco. A diferencia de los sistemas tradicionales, los participantes de la comunicación no necesitan acordar secretamente las claves. El sistema se compara a veces con un buzón en el que cualquiera puede meter un mensaje, pero sólo el que tiene la llave puede abrirlo y leer los mensajes que contiene.
Esta asimetría (claves distintas para encriptar y para desencriptar) es lo que garantiza el secreto. Sin embargo, el sistema es simétrico en otro sentido: un mensaje encriptado con la clave pública debe ser desencriptado con la clave privada. Y, viceversa, un mensaje encriptado con la clave privada debe ser desencriptado con la clave pública. Y esto tiene otra ventaja: si el cliente recibe un mensaje que, para leerlo, debe ser desencriptado con la clave pública, eso indica que fue encriptado con la clave privada. El mensaje no es secreto porque todos conocen la clave pública. Pero como la clave privada sólo la conoce el banco, eso garantiza el origen del mensaje. Si se desea garantizar el origen del mensaje y, además, su privacidad, se puede usar una doble encriptación.

El método RSA comienza transformando el mensaje en un número muy largo. Por ejemplo, se reemplaza la letra A por el número 01, la B por el 02 y así sucesivamente. Luego se hace la encriptación propiamente dicha mediante un par de operaciones matemáticas. Estas operaciones no son complejas en sí mismas pero, como involucran cientos de dígitos, son imposibles de realizar sin computadora.

Aunque la clave pública y la privada son distintas, eso no significa que sean cualesquiera. En realidad, las dos claves están directamente relacionadas y, conociendo la clave pública, es teóricamente posible calcular la privada. Teóricamente. En la práctica llevaría millones de millones de años completar el cálculo. Esto se debe a que ambas claves se relacionan a través de números primos. Las dos se calculan a partir de un número muy grande (de centenares de dígitos) que es el producto de sólo dos números primos.

Si tenemos los números primos 47 y 59 es fácil calcular su producto: 2773. Pero, si nos dan el número 2773 y queremos saber qué dos números lo dan como producto, tenemos que probar con todos los números primos desde el dos hasta la raíz cuadrada de 2773. Son dieciséis divisiones en total. Si el número inicial tiene cuarenta dígitos, obtener los primos que lo forman a razón de un millón de divisiones por segundo podría tardar más de 60 mil años. Con números de cien o más dígitos, el tiempo necesario superaría largamente la edad del Universo.

Durante muchos años, la investigación sobre números primos se consideró la rama más pura de las matemáticas, algo que no tendría ninguna utilidad práctica. Pero todo llega y ahora vemos cómo la confidencialidad de nuestras comunicaciones y hasta la seguridad nacional descansan en los números primos.
Tomado de Diario Página 12 en http://www.pagina12.com.ar/diario/ultimas/index.html

lunes, marzo 21, 2011

Pasos matemáticos cruciales para el ensayo de cirugías con copias virtuales de cada paciente

Accidentalmente, un cirujano mata a un paciente, deshace el error y comienza de nuevo. ¿Pueden los matemáticos hacer realidad esa idea de la ciencia-ficción? Se aproxima con rapidez el día en que un cirujano pueda practicar sobre el "doble digital" de su paciente (una copia virtual del cuerpo de éste) antes de realizar la operación quirúrgica real, según el matemático Joseph Teran Ph.D.  en 2005 en Stanford University. y actualmente docente investigador de la UCLA: University of California de Los Angeles  está ayudando a hacer viable una tecnología para la cirugía virtual.  


Las ventajas de esta nueva tecnología salvarán vidas. "El cirujano puede permitirse cometer errores sin consecuencias cuando utiliza un simulador, y aprender de sus errores", explica Teran. "Si comete errores, puede deshacerlos como lo hace cualquiera que se equivoca al teclear una palabra en un documento usando un procesador de textos. Volver a empezar es un gran beneficio de la simulación. La simulación quirúrgica está llegando, no hay ninguna duda sobre esto. Es una alternativa más barata frente a los cadáveres y una alternativa más segura para los pacientes". Los pacientes pueden ser escaneados y entonces es posible generar un doble digital tridimensional. Es una copia virtual del cuerpo del paciente, incluyendo sus órganos internos. El cirujano hace primero la operación quirúrgica en el paciente virtual. Con un simulador, un cirujano puede practicar un procedimiento decenas o cientos de veces. Cuando está clara la mejor forma de realizar la cirugía, entonces el paciente acudirá al hospital para ser operado. Ahora, ya puede hacerse un doble corporal tridimensional digital de cualquier persona, pero actualmente eso requiere la labor de 20 especialistas entre seis y nueve meses. En un futuro cercano, un único técnico podrá hacerlo en cuestión de minutos. La disponibilidad fácil de esta tecnología permitirá a los cirujanos cometer menos errores sobre los pacientes reales. El único factor limitante es la complejidad de la geometría involucrada, pero Teran y sus colaboradores están trabajando en eso. La tecnología será especialmente útil para nuevos tipos de cirugías, que por su carácter novedoso no hayan podido ser ensayadas tanto como sería deseable. 

Joseph M. Terán  Docente UCLA
Hacer realidad la cirugía virtual requerirá resolver ecuaciones matemáticas, operaciones de cálculo multivariado, así como progresar en la geometría computacional y en la informática. Siendo un experto en matemáticas aplicadas, Teran trabaja en estos campos; él desarrolla algoritmos para resolver las ecuaciones. Los adelantos hechos por Teran y otros científicos en la geometría computacional, ecuaciones  y la computación a gran escala están acelerando la viabilidad práctica de la cirugía virtual.

domingo, enero 23, 2011

El matemático Donald E. Knuth gana el premio FBBVA por convertir la programación informática en ciencia

La Fundación BBVA ha concedido el premio Fronteras del Conocimiento en la categoría de Tecnologías de la Información y la Comunicación al matemático estadounidense Donald E. Knuth. Según el jurado, el galardonado “sistematizó el diseño del software y estableció los cimientos sobre los que se construyen los programas informáticos actuales”.

 Donald E. Knuth recibe este premio por “hacer de la programación informática una ciencia introduciendo técnicas matemáticas para el análisis riguroso de los algoritmos”, en palabras del jurado.
Knuth sentó las bases de los ‘modernos compiladores’, es decir, los programas que traducen el lenguaje de alto nivel de los programadores al lenguaje binario de los ordenadores.


Donald Knuth. Foto: FBBVA.


Además, es considerado el ‘padre’ del análisis de algoritmos - conjunto de instrucciones que se da a un ordenador para ejecutar una tarea- . “Los algoritmos se encuentran en el centro del mundo digital actual, y subyacen en todo lo que hacemos con un ordenador”, afirman los expertos que conceden el premio.
El libro de Knuth El Arte de Programar Ordenadores está considerado “el trabajo más relevante de la ingeniería informática en su sentido más amplio, abarcando los algoritmos y métodos que se encuentran en el núcleo de la inmensa mayoría de los sistemas informáticos con una claridad y profundidad poco común”.
El premiado es también el creador de los programas tipográficos más usados hoy en día en la edición de textos científicos, TeX y METAFONT, distribuidos en código libre. Son dos lenguajes que “incorporan la estética tipográfica permitiendo a los autores confeccionar documentos con diseño de imprenta”, explica el jurado.
“Todo lo que tiene que ver con los ordenadores hoy me sigue fascinando, y no hay una sola cosa de lo que ha ocurrido que yo hubiera podido predecir hace treinta años”, comentó Knuth.
Entre otros reconocimientos, Knuth ha recibido la Medalla Nacional de la ciencia en EEUU, el Turing Award y el Kyoto Prize. En las dos ediciones anteriores los galardonados en esta categoría fueron el israelí Jacob Ziv y el ingeniero y matemático estadounidense de origen indio Thomas Kailath.
---------------------------------------------
Donald Knuth (1938, Wisconsin) es desde 1993 profesor emérito de la Universidad de Stanford (EEUU), a la que se incorporó como catedrático a los treinta años. En la actualidad con la condición de “profesor emérito”, dedica su tiempo a completar El arte de programar ordenadores, una serie de volúmenes en la que empezó a trabajar en 1962 y de la que se han publicado hasta ahora los tres–en 1968, 1969 y 1973-. Precisamente el volumen 4 A acaba de finalizar su de impresión.
Los Premios Fundación BBVA Fronteras del Conocimiento, creados en 2008 y dotados con 3,2 millones de euros distribuidos en ocho categorías, reconocen la investigación y la creación de excelencia. Sus ocho categorías reflejan los principales retos científicos, tecnológicos, sociales y económicos del presente.
Fuente: SINC (Servicio de Informacion y Noticias Científicas)

miércoles, noviembre 17, 2010

Grafos Hamiltonianos y bacterias

Utilizan una computadora bacteriana para saber si un grafo es o no hamiltoniano. Esto sería una demostración para un nuevo tipo de computación.

Grafo hamiltoniano con uno de los posibles ciclos hamiltonianos marcado. Quizás algunos de los temas más interesantes en la ciencia son los asuntos interdisciplinares, cuestiones que unen más de una rama del saber. Si a usted, amigo lector, se le dice que las Matemáticas pueden aplicarse a la Biología o a la Genética seguro que no se sorprenderá demasiado, al fin y al cabo las Matemáticas son el lenguaje de la ciencia. Pero, ¿y si es al revés?, ¿y si es la Genética la que ayuda a resolver problemas matemáticos?

Todo aquel que realmente esté interesado en la Informática (es decir, más allá de jugar con el ordenador y bajarse material de la red) sabe de la importancia de la Matemática Discreta. Esta rama de las Matemáticas permite estudiar la naturaleza de los números y, por tanto, desarrollar sistemas de cifrado, como el RSA que le permite conectarse de manera segura con su banco. Nos dice también la manera de encontrar una solución óptima a un problema, como la ruta más corta entre dos puntos. Los lógicos que han trabajado en problemas computacionales nos dicen que hay problemas muy duros de computar, de tipo NP o NP completos, que básicamente no pueden ser resueltos de manera óptima en un tiempo razonable. La única manera que tenemos (o la única posible que existe) para resolverlos de manera segura es enumerar todas las configuraciones posibles y escoger la mejor. Es decir, aplicando fuerza bruta. Pero los ordenadores tienen sus limitaciones a la hora de resolver los problemas a base de fuerza bruta si el sistema a resolver es lo suficientemente grande, pues el tiempo de resolución crece exponencialmente, aunque sea un hipotético ordenador cuántico.

Es aquí donde la Biología puede ayudar. Podemos tener un cultivo de miles de millones de bacterias que genéticamente computen lo que nosotros queramos. O, al menos, esa es la idea. Recientemente unos investigadores norteamericanos han creado una “computadora bacteriana” capaz de resolver un problema matemático sofisticado (aunque pequeño), demostrando así que es posible realizar computación en células vivas y abriendo la puerta a diversas aplicaciones. Esta segunda generación de computadoras bacterianas ilustra además la capacidad de este método para resolver de manera real problemas matemáticos complicados. El equipo de investigadores, pertenecientes a diversas instituciones científicas, usaron ingeniería genética para modificar bacterias E. coli que fueron capaces de resolver el problema conocido como problema del ciclo hamiltoniano. Este resultado es una extensión de sus trabajos previos con este tipo de computación, y con el que anteriormente resolvieron el “problema de la tortitas quemadas”, resultado que ya cubrimos en NeoFronteras. El problema del ciclo hamiltoniano pregunta sobre si en un grafo, formado por diversos vértices unidos por aristas, hay una ruta que empezando por un vértice se vuelva al mismo pasando una sola vez por cada uno de los otros vértices, aunque se queden aristas sin visitar. Es decir, si así es el grafo será hamiltoniano y si no es así no será hamiltoniano. Aunque hay algún criterio (como el de Dirac) que permite decir en algunos casos si un grafo es hamiltoniano, no hay, en general, un criterio universal que nos lo asegure, a diferencia del caso de decir si un grafo es o no Euleriano (si tiene o no un camino que partiendo de un vértice visite todas las aristas una sola vez). La ausencia de tal criterio frustra a muchos estudiantes de informática que estudian Matemática Discreta como parte de su formación, pues, pese al parecido, los conceptos de grafo euleriano y hamiltoniano son muy distintos. La mayoría de las veces la única manera de decir si un grafo es hamiltoniano es encontrar un ciclo* hamiltoniano en él. Estos investigadores modificaron el circuito genético de las bacterias E. coli para que fuesen capaces de encontrar un ciclo hamiltoniano en grafos de tres vértices (por pequeño un problema ridículamente simple por otra parte).

Las bacterias que resolvieron satisfactoriamente el problema informaban por fluorescencia roja y verde simultánea, produciéndose colonias amarillas. Aunque el problema es en este caso simple, lo importante de este resultado es que nos dice que es posible resolver este tipo de problemas. Su extensión a grafos mayores sería factible. La Biología Sintética es el uso de las técnicas de Biología Molecular, Ingeniería Genética y modelización matemática para diseñar y construir circuitos genéticos que permitan a las células vivas realizar nuevas funciones. Según uno de los autores este resultado es un ejemplo más de lo poderosa y dinámica puede ser la Biología Sintética. En este caso se ha usado para resolver un problema matemático, pero se puede aplicar a Medicina o a investigación sobre fuentes de energía, Medio Ambiente, etc.

Fuentes y referencias: Nota de prensa. Jordan Baumgardner, Karen Acker, Oyinade Adefuye, Samuel THOMAS Crowley, Will DeLoache, James O Dickson, Lane Heard, Andrew T Martens, Nickolaus Morton, Michelle Ritter, Amber Shoecraft, Jessica Treece, Matthew Unzicker, Amanda Valencia, Mike Waters, A. M. Campbell, Laurie J. Heyer, Jeffrey L. Poet and Todd T. Eckdahl. Solving a Hamiltonian Path Problem with a bacterial computer. Journal of Biological Engineering.

miércoles, octubre 06, 2010

Matemáticas.zip


Cuantos de nosotros hemos comprimido o recibido archivos del estilo ***.ZIP, o trabajamos a diario con formatos PDF, MP3, GIF, JPG, … y hasta hablamos de DVD. Pero, ¿todos saben que detrás de ello está la matemática?
Pues hace pocos meses, más precisamente el 18 de junio, la Fundación BBVA Fronteras del Conocimiento ha hecho una entrega de premios en Madrid y ha distinguido a Jacob Ziv, Doctor en Ingeniería Eléctrica por el Instituto de Tecnología de Massachussets, a quien se debe el desarrollo junto con Abraham Lempel del algoritmo LZ77, clave para la compresión de archivos. 
Es muy interesante leer la entrevista que le realizó Judith De Jorge en abc.com, donde se vislumbra su gran humildad.
Expresa: “Estoy en contra de cualquier reglamentación en internet.” En la nota podremos leer sus ideas respecto a Derechos de Autor, y cómo se plantea una nueva forma de trabajar gracias a las nuevas herramientas disponibles en Internet. Además, podremos conocer algunos comentarios acerca del algoritmo.
Una buena manera de reconocer el uso de la matemática en lo que utilizamos a diario.
Pueden leer la entrevista completa en: www.abc.com

lunes, agosto 09, 2010

Matemáticas y seguridad informática

Tomado de: www.matematicas.net

El secreto de Google

Tomado de: www.matematicas.net