English French German Spain Italian Dutch Russian Portuguese Japanese Korean Arabic Chinese Simplified

viernes, mayo 27, 2011

Reto matemático Semestre A 2011

Este semestre el reto matemático para mis estudiantes en la última semana del tercer corte consiste en: 
He hecho con las letras del abecedario tres conjuntos:
1º : {C, E, F, G, H, I, J, K, L, M, N, Ñ, S, T, U, W, X, Y, Z}           
2º : {A, D, O, P, Q, R}
3º : {B}



¿por qué los he ordenado asi? Es decir, encontrar la característica común de los elementos de cada uno de los conjuntos

Anímense a participar, reconocimiento especial para  quien comente de primero y de la manera más sencilla la respuesta a este problema abierto

Pueden consultar el reto del semestre pasado acá

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

martes, mayo 03, 2011

Aplicación de modelos matemáticos para buscar fugitivos y predecir ataques terroristas, propuesta de Colombiano candidato a Premio Nobel

La aplicación de modelos matemáticos en la prevención de ataques terroristas o en la búsqueda de fugitivos es posible a través de la denominada "Teoría de los juegos", explica el matemático Colombiano Guillermo Owen, quien asesora al Departamento de Defensa de Estados Unidos en estas materias.
 Owen, de 72 años y uno de los principales expertos mundiales en esta ciencia matemática, ha viajado a Barcelona (Mayo 2011) para impartir unas conferencias ante estudiantes de ingeniería de la Universidad Politécnica de Cataluña, con los títulos "Ataques terroristas patrocinados y represalias" y "Un modelo de búsqueda y captura del fugitivo".


En ambos casos se trata de dos de las numerosas aplicaciones prácticas de la "Teoria de los juegos", un área que estudia las interacciones y los procesos de decisión y estrategias entre dos o mas individuos, y que se ha usado también para efectuar análisis en el campo de la estrategia militar, la economía, la política, la biología o la informática.

Guillermo Owen, que se doctoró en Princeton (EEUU) y es profesor distinguido de Matemáticas Aplicadas en la Escuela Naval de Monterrey, en California, señala que en la búsqueda de un fugitivo se pueden aplicar el denominado "juego del escondite", por el que se estudia las características de los sitios donde se puede ocultar y las estrategias óptimas tanto del fugitivo como del buscador.

Owen se muestra reservado al ser preguntado sobre la efectividad de estos "juegos" matemáticos en casos reales de localización de personas y se limita a decir: "hemos estado ayudando en la búsqueda de algunas personas y hemos tenido algunos éxitos".

 "En cuanto a los actos de terrorismo, buscamos no tanto predecir los ataques terroristas sino que nos interesa la relación que pueda haber entre un grupo terrorista y un Estado que le pueda estar ayudando o 'Estado patrocinador', que es como lo llamamos", indica el matemático colombiano.
En este sentido, y en función de la relación entre estos dos 'jugadores', "vemos qué puede hacer el sujeto de los ataques o 'Estado víctima" contra el grupo terrorista y el Estado que lo está patrocinando", añade Owen.

Este experto en la "Teoría de los juegos", sobre la que ha escrito varias obras de referencia, efectúa junto a otros especialistas en la materia análisis para el Departamento de Defensa norteamericano, "unos estudios que son bastante abstractos, pero que les son útiles", asegura Guillermo Owen.
El matemático explica que en la "Teoría de los juegos" se distinguen dos grandes grupos, los "juegos cooperativos", donde se estudian las coaliciones y las negociaciones que pueden entablar jugadores del mismo grupo, y los "juegos no cooperativos", donde se busca qué puede hacer cada jugador para tener un rendimiento óptimo en función de las posibles estrategias de los otros jugadores.

En la vida diaria, las personas también toman decisiones basándose en unas estrategias, aunque estas decisiones no siempre son las mejores porque "no siempre nuestras acciones son totalmente racionales".

En este sentido, Owen advierte que "se puede recurrir a las matemáticas para analizar cuáles son las mejores decisiones, pero eso no quiere decir que la persona las vaya a tomar", mientras resalta que "a veces tomar una decisión errónea puede llevar a un éxito o un premio inesperado".

El matemático añade, a modo de explicación, que "el resultado de una decisión no sólo depende de nosotros, sino de otros factores que desconocemos o que considerábamos muy poco probables".
Así, Cristóbal Colón erró en su idea de encontrar una ruta más corta hacia la Indias navegando hacia Occidente porque "resultó que había algo, la naturaleza, que cambió sus planes, pero lo que hubiera sido un mal resultado, se convirtió en un gran resultado".

Del mismo modo, en el campo de la economía, donde se ha empleado la "Teoría de los juegos" para intentar prever los comportamientos de los agentes económicos "siempre hay imprevistos y la gente a veces puede moverse por el pánico, y con pánico la gente se comporta de manera muy irracional".
La "Teoría de los juegos" eclosionó en la década de los cuarenta del siglo pasado, en la época de la Segunda Guerra Mundial y la posterior "Guerra Fría", con las aportaciones de matemáticos como John von Neumann, Oskar Morgenstern o John Nash, quien recibió el Premio Nobel de Economía de 1994 y cuya vida se llevó al cine en la película "Una mente maravillosa". 

Redacción de Hèctor Mariñosa Barcelona, 30 abr (Agencia de Noticias EFE)