Un ligero update sobre lo que me ha tenido ocupado estos últimos días.
Primero, desde la semana anterior empezó oficialmente el semestre en la universidad lo que lo que implica muchos más estudiantes, frenesí por toda la ciudad, gente nueva por doquier, más fiestas y relajo por las noches y, también, más trabajo para mí. Y es que como estoy trabajando de medio tiempo dando servicio técnico en las redes de dormitorios, ésta es justo la temporada donde llegan todos los estudiantes nuevos queriendo conectarse e implorando por que les arreglemos el internet en su cuarto. Pero bueno, quizá esto es lo más cerca que voy a estar en mi vida de poder llenar mi agenda con citas que tienen nombres como Alessandra, Carolyn, Rebecca, Denisse y Maryam. Que triste, jaja.
Otra de las cosas que me ha mantenido ocupado es el cambio de cuarto que, como habrán visto en un post anterior, no fue mucho de mi agrado. Pero también ya me voy acostumbrando y después de todo pues parece que no está tan mal. Después de una reorganización de muebles y tratar de embellecer un poco el lugar, pues ya no se ve tan mal. Mis nuevos compañeros de dormitorio también se ven muy buena onda todos, son 3 chinos y 3 musulmanes. Prometo más detalles, fotos y comentarios pronto en otro post.
En la uni ahí voy también en el ciclo de nueva idea → implementar idea → probar idea → idea no sirve → nueva idea → ... Y por otro lado cazando a mi supervisor que después de haber andado un año de sabático todavía no puedo hablar bien con él para definir lo que será el curso de mi investigación en lo que será (esperemos) el último año del doctorado.
Ya para terminar sólo comento también que en los pocos minutos libres que he tenido me la he pasado generando la lista de mis 100 películas favoritas de todos los tiempos. Ambas la lista y cómo generé la lista son historias interesantes, de las que prometo dar detalles pronto. La lista, de hecho, ya la tengo (¿alguien puede adivinar las 3 primeras?). Pero los dejo unos días en suspenso, prometo subirla aquí también pronto en otro post.
Promesas, promesas.
martes, 26 de septiembre de 2006
martes, 19 de septiembre de 2006
Fotografiando a nuestro planeta
Un grupo de estudiantes de licenciatura en Cambridge, lograron mandar una cámara hasta la estratosfera de la Tierra para tomarle fotografías.Los estudiantes subieron el equipo fotográfico en un globo que ascendió hasta los 30 km de la superficie terrestre. A esa altura el globo se quemó y la cámara regresó a la tierra a salvo en un paracaídas. Durante el trayecto que duró tres horas, la cámara tomó unas 800 fotografías de nuestro hermoso planeta azul.
Este es el primer paso en la investigación de estos jóvenes científicos que quieren, de hecho, mostrar que es posible enviar pequeños cohetes al espacio con un presupuesto de menos de £1,000.
Cómo se ve que con creatividad y un tantito de ingenio se pueden hacer muchísimas cosas increíbles. Que chido por estos chavos, me da gusto saber que hay personas para quienes ni siquiera el cielo es el límite.
Fuentes: [1] [2], Más fotos: [3].
Etiquetas:
informativo
sábado, 16 de septiembre de 2006
De paradojas y cosas no computables
Recientemente me encontré con el trabajo de un grupo de científicos que descubrieron algunas relaciones entre la compresión de texto (generar archivos comprimidos como los .zip), la interpretación de lenguaje natural (que las máquinas hablen y entiendan nuestro lenguaje) y problemas de inteligencia artificial en general.
La primera vez que escuché esto me pareció un completo disparate pero, después de estarlo leyendo con un poco más de calma, he visto que la idea es realmente muy interesante y parece tener bastante sentido. Incluso, además de tener unos tintes medio filosóficos geniales, todo está fundamentado en resultados matemáticos formales. También me he dado cuenta de que las ideas, aunque no son nada triviales, tampoco parecen imposibles de entender para nosotros los simples mortales.
Éste es entonces el primero de una serie de posts donde trataré de ir explicando varios de los componentes involucrados en esta teoría. El tema de este post es la llamada complejidad de Kolmogorov que, si no dejamos que nos espante mucho el nombre y leyendo con un poquito de atención, veremos que finalmente no es algo tan complejo como aparenta. ;-)
Empezamos con una simple cadena de texto. La dichosa complejidad es un numerito que trata de medir que tan ‘complicado’ es generar esa cadena con un programa en la computadora. Por ejemplo, la cadena de texto
Pero no todas las cadenas de texto son tan simples como repetir “hola” un montón de veces. Por ejemplo, para la cadena de 40 caracteres
Entonces, la complejidad de una cadena de texto, como la definió este señor Kolmogorov, es el tamaño (en no. de caracteres) del programa más pequeño que escriba dicha cadena en la pantalla.
En el último de los ejemplos vimos cómo, para cualquier cadena de texto, es muy fácil conseguir un programa que la escriba; basta con agregarle unos 10 caracteres extras: “escribe "..."”. Esto quiere decir que la complejidad de una cadena no puede ser mucho más grande que el tamaño de la cadena misma. En el peor de los casos el programa tendrá 10 caracteres extra pero, en muchos otros casos, es posible encontrar programas más pequeños.
Imagínate en mi primer ejemplo que la cadena dice “hola ” pero, en lugar de 8, unas 5000 veces. La cadena de texto tendría ahora unos 25000 caracteres, mientras que el programa para escribirla en pantalla sigue siendo pequeñito
Espero que hasta aquí vaya todo más o menos claro, porque vamos a comenzar ahora con cosas más divertidas. Y es que vamos a mostrar que calcular la complejidad de una cadena es una tarea, digamos, muy difícil.
Supongamos que un amigo muy inteligente nos ha hecho el favor de escribir un programita al que le damos una cadena de texto y nos regresa la complejidad de esa cadena. El programa se vería más o menos así:
Y el funcionamiento de este programita tampoco es nada complicado. Lo único que hace es ir generando una por una todas las posibles cadenas de texto (esto es lo que indica el ‘por cada Cadena’) y llamando a la rutina Complejidad para ver si hemos encontrado o no una cadena con complejidad mayor a N. En cuanto encontremos la primera cadena con complejidad mayor a N el programa termina y regresa como resultado esa cadena.
Recapitulando, este es el código que llevamos escrito hasta ahora.
Podemos agregar entonces el siguiente pedacito de código al final de nuestro programa.
¿Puedes ver algún problema? Veámoslo de nuevo. Hemos construido un programa que, en total, ocupa unos 5030 caracteres e imprime una cadena de complejidad mayor a 8000. ¿Recuerdas la definición de complejidad? Es el tamaño del programa más pequeño que escribe la cadena. Según el código súper inteligente de nuestro amigo, el programa más pequeño necesita unos 8000 caracteres, pero nosotros hemos logrado escribir esa cadena ¡con sólo 5030!
¿Qué significa todo esto? Pues lo primero es que nuestro amigo súper inteligente nos mintió y el código que nos dio para calcular la complejidad de una cadena no funciona. De hecho no funciona porque, no se puede escribir ningún programa para calcularla. Lo que hemos demostrado es que, no importa qué tan inteligente sea nuestro amigo, nunca podrá escribir el dichoso programita porque eso genera contradicciones. En otras palabras hemos probado que la complejidad de Kolmogorov no es computable.
¿Y, qué significa eso? En palabras más sencillas, una de las implicaciones de este resultado es que nunca podremos programar el compresor de archivos perfecto. Y ojo que eso no quiere decir que no podamos comprimir archivos, eso sí que lo podemos hacer y es lo que hacemos cuando generamos archivos .zip. Lo que no podemos tener es la garantía de haber podido comprimir los archivos lo más posible.
Ya para terminar sólo quiero mencionar que, para hacer la explicación más sencilla, tuve que sacrificar un poco la formalidad de la demostración. Pero espero que me puedan creer que esto se puede hacer formalmente sin ninguna ambigüedad, usando por ejemplo un lenguaje de programación real apropiado. En particular el ‘por cada Cadena’ se puede implementar fácilmente generando las cadenas en orden, primero las más chicas y luego las más grandes; y las del mismo tamaño ordenadas alfabéticamente.
También para los curiosos, o si alguien se perdió entre tanta explicación y cosa rara, una versión más informal del mismo argumento es la Paradoja de Berry.
La primera vez que escuché esto me pareció un completo disparate pero, después de estarlo leyendo con un poco más de calma, he visto que la idea es realmente muy interesante y parece tener bastante sentido. Incluso, además de tener unos tintes medio filosóficos geniales, todo está fundamentado en resultados matemáticos formales. También me he dado cuenta de que las ideas, aunque no son nada triviales, tampoco parecen imposibles de entender para nosotros los simples mortales.
Éste es entonces el primero de una serie de posts donde trataré de ir explicando varios de los componentes involucrados en esta teoría. El tema de este post es la llamada complejidad de Kolmogorov que, si no dejamos que nos espante mucho el nombre y leyendo con un poquito de atención, veremos que finalmente no es algo tan complejo como aparenta. ;-)
Empezamos con una simple cadena de texto. La dichosa complejidad es un numerito que trata de medir que tan ‘complicado’ es generar esa cadena con un programa en la computadora. Por ejemplo, la cadena de texto
“hola hola hola hola hola hola hola hola ”la podríamos escribir en la pantalla usando el siguiente programita repite 8 veces escribe "hola "Algo interesante es que este programa se puede ver, además, como una cadena de texto “repite 8 veces escribe "hola "”que, en este caso, está formada por 30 caracteres (contando todas las letras, símbolos y espacios). Observa como la cadena original, la de muchos hola’s, tenía 40 caracteres y la hemos podido generar con un programa que ocupa sólo 30.Pero no todas las cadenas de texto son tan simples como repetir “hola” un montón de veces. Por ejemplo, para la cadena de 40 caracteres
“u8agup2pPy3J087z4m9krF6c9gE00Uo6AOLox56m”quizá el programa más corto que la escriba en pantalla esescribe "u8agup2pPy3J087z4m9krF6c9gE00Uo6AOLox56m"que ocupa en total 50 caracteres.
Entonces, la complejidad de una cadena de texto, como la definió este señor Kolmogorov, es el tamaño (en no. de caracteres) del programa más pequeño que escriba dicha cadena en la pantalla.
En el último de los ejemplos vimos cómo, para cualquier cadena de texto, es muy fácil conseguir un programa que la escriba; basta con agregarle unos 10 caracteres extras: “escribe "..."”. Esto quiere decir que la complejidad de una cadena no puede ser mucho más grande que el tamaño de la cadena misma. En el peor de los casos el programa tendrá 10 caracteres extra pero, en muchos otros casos, es posible encontrar programas más pequeños.
Imagínate en mi primer ejemplo que la cadena dice “hola ” pero, en lugar de 8, unas 5000 veces. La cadena de texto tendría ahora unos 25000 caracteres, mientras que el programa para escribirla en pantalla sigue siendo pequeñito
repite 5000 veces escribe "hola "y ocupa, después de cambiar el “8” por “5000”, ¡tan sólo 33 caracteres! Observa como aquí comienzan a aparecer algunas relaciones con compresión, una cadena de 25000 caracteres la pudimos comprimir en una de 33.Espero que hasta aquí vaya todo más o menos claro, porque vamos a comenzar ahora con cosas más divertidas. Y es que vamos a mostrar que calcular la complejidad de una cadena es una tarea, digamos, muy difícil.
Supongamos que un amigo muy inteligente nos ha hecho el favor de escribir un programita al que le damos una cadena de texto y nos regresa la complejidad de esa cadena. El programa se vería más o menos así:
Complejidad(Cadena S) regresa NúmeroYa que tenemos este programa, vamos a escribir nosotros este otro
inicio
/* Un código súper inteligente va aquí */
fin
EncuentraCadena(Número N) regresa Cadena¡No se espanten! Voy a explicar ahora de qué se trata todo esto. Nuestro nuevo programa recibe de entrada un número, N, y va a dar como salida una cadena de texto. La cadena que obtenemos en la salida tiene la única peculiaridad de que su complejidad es más grande que N, el número que le demos de entrada.
inicio
por cada Cadena S
si Complejidad(S) > N entonces regresa S
fin
Y el funcionamiento de este programita tampoco es nada complicado. Lo único que hace es ir generando una por una todas las posibles cadenas de texto (esto es lo que indica el ‘por cada Cadena’) y llamando a la rutina Complejidad para ver si hemos encontrado o no una cadena con complejidad mayor a N. En cuanto encontremos la primera cadena con complejidad mayor a N el programa termina y regresa como resultado esa cadena.
Recapitulando, este es el código que llevamos escrito hasta ahora.
Complejidad(Cadena S) regresa NúmeroRecordemos que la linea donde dice ‘Un código súper inteligente va aquí’, efectivamente, tenemos reemplazarla por el código que nos haya dado nuestro amigo. Ya que hayamos escrito ese código podemos entonces contar el total de caracteres que ahora ocupa todo el programa completo hasta este punto. Digamos que los contamos y resulta que en total hay unos 5000 caracteres.
inicio
/* Un código súper inteligente va aquí */
fin
EncuentraCadena(Número N) regresa Cadena
inicio
por cada Cadena S
si Complejidad(S) > N entonces regresa S
fin
Podemos agregar entonces el siguiente pedacito de código al final de nuestro programa.
escribe EncuentraCadena(8000)Veamos que es lo que hace este programa. En realidad es muy sencillo, simplemente busca una cadena que tenga complejidad mayor a 8000 y la escribe en pantalla.
¿Puedes ver algún problema? Veámoslo de nuevo. Hemos construido un programa que, en total, ocupa unos 5030 caracteres e imprime una cadena de complejidad mayor a 8000. ¿Recuerdas la definición de complejidad? Es el tamaño del programa más pequeño que escribe la cadena. Según el código súper inteligente de nuestro amigo, el programa más pequeño necesita unos 8000 caracteres, pero nosotros hemos logrado escribir esa cadena ¡con sólo 5030!
¿Qué significa todo esto? Pues lo primero es que nuestro amigo súper inteligente nos mintió y el código que nos dio para calcular la complejidad de una cadena no funciona. De hecho no funciona porque, no se puede escribir ningún programa para calcularla. Lo que hemos demostrado es que, no importa qué tan inteligente sea nuestro amigo, nunca podrá escribir el dichoso programita porque eso genera contradicciones. En otras palabras hemos probado que la complejidad de Kolmogorov no es computable.
¿Y, qué significa eso? En palabras más sencillas, una de las implicaciones de este resultado es que nunca podremos programar el compresor de archivos perfecto. Y ojo que eso no quiere decir que no podamos comprimir archivos, eso sí que lo podemos hacer y es lo que hacemos cuando generamos archivos .zip. Lo que no podemos tener es la garantía de haber podido comprimir los archivos lo más posible.
Ya para terminar sólo quiero mencionar que, para hacer la explicación más sencilla, tuve que sacrificar un poco la formalidad de la demostración. Pero espero que me puedan creer que esto se puede hacer formalmente sin ninguna ambigüedad, usando por ejemplo un lenguaje de programación real apropiado. En particular el ‘por cada Cadena’ se puede implementar fácilmente generando las cadenas en orden, primero las más chicas y luego las más grandes; y las del mismo tamaño ordenadas alfabéticamente.
También para los curiosos, o si alguien se perdió entre tanta explicación y cosa rara, una versión más informal del mismo argumento es la Paradoja de Berry.
Etiquetas:
compsci,
interesante
jueves, 14 de septiembre de 2006
miércoles, 13 de septiembre de 2006
Segundo año terminado
Finalmente después de algunas semanas tratando de controlarme para no entrar en pánico y esconder los nervios por todo el trámite en el doctorado para este fin de año, hoy se terminó ya oficialmente para mi el segundo año.
El tramite involucraba entregar un reporte corto hace una semana, y hoy una entrevista para que mi supervisor, asesora y dos examinadores internos evaluaran mi desempeño en este segundo año. Y pues, después de haber pasado un año sin supervisor porque andaba de sabático, si estaba yo medio preocupado de que tan relevante era el trabajo que había estado haciendo.
Pero bueno, en contra de todas expectativas, parece que me fue bien. A los examinadores les gustó mi presentación (yo tampoco le entiendo) y parece que quedaron contentos. El otro lado de la historia se los podré contar el próximo viernes (o lunes) después de platicar bien con mi supervisor y decidir el rumbo de mi investigación para (esperemos) mi último año del doctorado.
Así que, ahí vamos a la siguiente etapa.
Thank you Mario! But our princess is in another castle!
El tramite involucraba entregar un reporte corto hace una semana, y hoy una entrevista para que mi supervisor, asesora y dos examinadores internos evaluaran mi desempeño en este segundo año. Y pues, después de haber pasado un año sin supervisor porque andaba de sabático, si estaba yo medio preocupado de que tan relevante era el trabajo que había estado haciendo.
Pero bueno, en contra de todas expectativas, parece que me fue bien. A los examinadores les gustó mi presentación (yo tampoco le entiendo) y parece que quedaron contentos. El otro lado de la historia se los podré contar el próximo viernes (o lunes) después de platicar bien con mi supervisor y decidir el rumbo de mi investigación para (esperemos) mi último año del doctorado.
Así que, ahí vamos a la siguiente etapa.
Thank you Mario! But our princess is in another castle!
Suscribirse a:
Entradas (Atom)