Archive for the 'Cosas que nos enseñan en el doctorado' Category

Saturación postvacacional

Published
by
Borja Sotomayor
on 10/10/2005
in Cosas que nos enseñan en el doctorado and Life in Chicago
. 5 Comments

Volver de las vacaciones al trabajo nunca es fácil… recuerdo que los primeros días de septiembre en Deusto casi todo el mundo respondía a la pregunta “¿Qué tal?” con “Ya sabes… aterrizando…”. Y el primer día, por supuesto, es un día en el que se sucede café tras café mientras cuentas una y otra vez cómo han sido tus vacaciones. Pero eso era entonces, y esto es ahora… y aquí en Chicago, cuando las vacaciones terminan, terminan de verdad. El día 26 empezaron las clases, y ya empezamos a recibir los primeros deberes, a lo que hay que añadir las mil movidas de investigación en las que hay que trabajar aparte de las clases. La verdad es que, después de tres semanas holgazaneando, pues cuesta un poco retomar una rutina de trabajo diario. Eso sí, por lo menos este trimestre no nos van a meter tanta caña como el trimestre de Invierno 2005 (Algoritmos y Sistemas Operativos).

Pero bueno, empecemos por las fascinantes asignaturas que tengo este trimestre. Son dos asignaturas, sin ninguna relación con mi area de investigación, y tengo que aprobarlas para cumplir los requisitos del doctorado. Eso sí, podemos escoger entre varias asignaturas y escogí las dos que más me podían interesar:

  • Teoría de la Complejidad: En la asignatura de Algoritmos nos metieron una caña espectacular con los fundamentos más matemáticos de la algoritmia, pero sólo tocamos muy brevemente el tema de la complejidad computacional, el área de la informática teórica que se centra en descubrir cómo podemos realizar eficientemente una tarea computacional. A este área pertenece, por ejemplo, el eterno problema de ¿P=NP?. Puesto que la informática teórica me interesa (sin llegar a ser algo en lo que trabajaría), pues me apunté a la asignatura. La verdad es que, de momento, no me está defraudando. Estamos viendo mogollón de cosas interesantes (incluyendo demostraciones que el profesor de Algoritmos no explicó porque “son muy complicadas”) y estoy descubriendo que P y NP no son más que dos clases de problemas dentro de un oceano de clases de complejidad: L, NL, P, NP, NPC, E, NE, EXP, NEXP, DTIME, NTIME, DSPACE, NSPACE, PSPACE, P/Poly, AL, AP, …

    Para que os hagais una idea de lo que tenemos que hacer en clase, aquí va nuestro primer homework resuelto. Que conste que no pude resolver todos los problemas y que, al igual que en Algoritmos, eso es lo más habitual. Por cierto, el profesor de la asignatura tiene un blog titulado Computational Complexity.

  • Lenguajes de Programación: Que no os engañe el nombre… en esta asignatura vemos de todo, menos programación :-D Es una asignatura en la que se ven los fundamentos teoricos de los lenguajes de programación pero, curiosamente, sin ver lo que habitualmente se ve en una asignatura de Compiladores. La asignatura tiene un temario un tanto peculiar, y vamos a ver todo tipo de movidas raras relacionadas con la descripción formal de lenguajes de programación, “type checking”, “type safety”, y otros temas relacionados con lenguajes funcionales. En particular, vamos a ver un lenguaje llamado SML que, por lo menos en este departamento, es bastante popular.

En lo que se refiere a movidas grid, aparte de tener el libro a punto de caramelo, ahora estoy metiendome en movidas de máquinas virtuales + grid cómo posible tema para la tesina que tengo que presentar el próximo verano. Resulta que varios investigadores de Globus están investigando cómo utilizar tecnologías de paravirtualización (sobre todo, Xen) para crear aplicaciones Grid más potentes y versátiles. Parece un tema bastante interesante…

Pero, por supuesto, no todo tiene que ser trabajo. Hace tiempo ya nos adelantaron que el segundo año de doctorado iba a ser bastante más relajado que el primero, y la verdad es que lo estoy notando. Cuando llega el fin de semana, no me quedan tareas pendientes y puedo disfrutarlo sin ningún tipo de impedimento. Incluso tengo casi todas las tardes libres (no olvideis que aquí se sale de trabajar a las 17:00 o 18:00). Además, las primeras semanas del año académico siempre están llenas de eventos: recepciones para los alumnos de postgrado, comidas/cenas gratis, etc. Y también hay cosas que hacer fuera de la Uni… sin ir más lejos, el jueves fuimos Mike, otro amigo, y yo a ver a Gilbert Gottfried en vivo y en directo en el club Zanies. Una hora entera riendonos sin parar… fue una auténtica gozada.

En fin, resumiendo, que la vuelta al trabajo está resultando un pelín dura, pero también muy agradable por diversas razones. Y en cuanto al blog (llevaba casi dos semanas sin escribir), seguro que este trimestre caen varios artículos interesantes, sobre todo ahora que el libro sale en menos de dos meses. Pero, lo mismo que en otras ocasiones que he andado muy liado, que nadie se extrañe si me tiro largas temporadas sin escribir :-)

Dude, I don’t have to outrun the bear…

Published
by
Borja Sotomayor
on 17/3/2005
in Cosas que nos enseñan en el doctorado
. 2 Comments

Estos días estamos quedando los compis de doctorado para repasar obsesivamente todo el temario de Algoritmos. Cuando tienes que hacer un repaso de todo, una buena estrategia es poner por escrito un esquema del temario. Así que nos pusimos a escribir el nombre de todos los temas en la pizarra de nuestro despacho (sí, nuestro despacho tiene pizarra y todo…). El resultado nos dejo un poco acojonados, en parte por todo lo que tenemos que meter a presión en nuestras cabecitas para este viernes, y en parte por que no nos creiamos que todo eso lo hemos aprendido en las 10 semanas que dura el trimestre. En fin, como me daba pena borrar la pizarra, hice unas cuantas fotos de recuerdo. El resultado es este bonito collage. Os recomiendo que veais la versión de alta resolución, pues así podreis ver exactamente cual es nuestro temario. Otra cosa que intentaré hacer una vez termiando el trimestre es colgar una selección de homeworks que he entregado durante el trimestre, para que veais a qué tenía que dedicar casi todos mis fines de semanas (y mis lunes, y mis martes, y mis… ).

En fin, visto el panorama, por lo menos nos sigue consolando el hecho de que aquí la calificación es mediante campanazo de Gauss. Basta con que haya un puñado de patanes (3 o 4, en nuestro caso) para que el resto de nosotros aprobemos. Cuando hemos comentado eso, uno de mis compañeros ha dicho “Dude, at least you don’t have to outrun the bear!”. A lo que yo he respondido “¿Lo cualo?” (en correctisimo ingles: “The which-o?”). Y me ha contado este simpatico ‘chiste’:

Dos amigos se encuentran de acampada cuando, de repente, aparece un oso enorme. Los dos salen corriendo, pero el oso les persigue a una velocidad considerable.
- ¡Nunca conseguiremos ir más rapidos que el oso! ¡Es demasiado veloz!
-¡Tío, yo no tengo que ir más rápido que el oso, sólo tengo que ir más rápido que tú!

Está claro… nuestro profesor de Algoritmos es el oso y en su asignatura lo que hay que hacer no es trabajar lo suficiente como para llegar hasta una meta objetiva de ‘aprobado’, sino que tienes que asegurarte de que trabajas mejor que el 50% de tus compañeros (bueno, por estos lares solo suelen pencar al 25-30% inferior de la clase). Afortunadamente, a pesar de que esto podría derivar en ‘competiciones’ entre los compañeros, entre nosotros hay buen rollito, y nos ayudamos mutuamente. Habrá que ver que piensa Gauss de todo esto…

Problemas abiertos (o “Hay que ver los cerebrines que estudian aquí”)

Published
by
Borja Sotomayor
on 16/3/2005
in Cosas que nos enseñan en el doctorado
. 7 Comments

En las matemáticas existen lo que se llaman problemas abiertos. Son problemas para los que se sabe que hay una solución, aunque nadie haya dado con ella todavía. Quizás el problema abierto (hasta hace poco) más conocido para el público general es el Último Teorema de Fermat:

No hay numeros enteros positivos x, y, z tales que xn + yn=zn, donde n es un número entero mayor que 2.

Desde que Pierre de Fermat enunció este teorema en 1637, nadie fue capaz de demostrarlo hasta 1994, y durante mucho tiempo fue uno de los problemas abiertos más conocidos del mundo de las matemáticas. Curiosamente, el Último Teorema de Fermat es de escaso interes teorico (en el sentido de que tanto si es cierto como si no, el teorema no tiene importantes repercusiones prácticas). Una de las cosas que he aprendido este año es que los matemáticos adoran a Pierre de Fermat no por su último teorema, sino por el Pequeño Teorema de Fermat, un teorema de gran utilidad (por ejemplo, es una de las bases del algoritmo criptográfico RSA).

Pues bien, en informática también hay muchos de estos problemas abiertos. Eso sí, a mi siempre me ha fascinado más el hecho de que hay problemas para los que se ha demostrado que nunca se podrá encontrar una solución. Por ejemplo, está demostrado que es imposible elaborar un algoritmo que, dado cualquier programa P, decida si P entrará en un bucle infinito en algún momento de su ejecución (si crees que te estoy engañando, ya estás leyendote el anexo del artículo Si Turing levantara la cabeza…).

Pero bueno, me desvío del tema: los problemas abiertos. Todo esto lo comento porque nuestro profesor de Algoritmos plantea como desafio a los alumnos la resolución de ciertos problemas abiertos. Lo siento mucho, pero eso es algo por lo que ya no paso. Bastante me atormenta la asignatura de Algoritmos como para además ponerme la capa de Super-Algoritmo-Man para luchar contra problemas en los que durante años han fracasado algunas de las mentes más brillantes de las matemáticas. Eso sí, en nuestra clase hay bastantes cerebrines que sí están por la labor… y resulta que durante la asignatura, dos alumnos han resuelto un problema abierto cada uno. Cagate lorito.

Sin entrar en demasiados detalles, uno de los alumnos ha descubierto la cota inferior de la complejidad de un problema clásico de algoritmia (relacionado con la detección de monedas falsas entre monedas genuinas). Descubrir la ‘cota inferior de la complejidad’ de un problema es un logro acojonante, porque quiere decir que has descubierto que un problema nunca podrá resolverme de manera más eficiente que la dada por la cota inferior. Para que nos enteremos: si un problema tiene como entrada n elementos (p.ej. n números) y la cota inferior es de n3, eso significa que ese problema nunca podrá resolverse en menos de n3 pasos (esta explicación omite muchos detalles, pero es para que me entendais todos… los más entendidos ya sabrán que me estoy refiriendo a la notación Big-Oh).

Otro de los alumnos ha cogido un problema cuyo mejor algoritmo conocido requiere n2 pasos, y ha encontrado un algoritmo que requiere sólo n pasos. También un logro interesante, aunque desde un punto de vista teorico no es tan acojonante como encontrar una cota inferior.

Pues ya veis el tipo de gente que deambula por esta universidad…

Por cierto, si esto de los problemas abiertos ha despertado vuestra curiosidad, os interesará saber cual es (con diferencia) el mayor problema abierto de la informática teorica: ¿P=NP? Esta sencilla formula trae de cabeza a buena parte de la comunidad de la informática teorica. Teneis más detalles aquí.

Mi kernel (y 2)

Published
by
Borja Sotomayor
on 15/3/2005
in Cosas que nos enseñan en el doctorado
. 1 Comment

El viernes entregamos el segundo kernel que había que hacer para la asignatura de Sistemas Operativos. En este caso nos dieron un kernel ya programado (por el profesor), y nosotros teníamos que añadirle toda la funcionalidad de I/O. Leed el artículo sobre el primer kernel para más información sobre la arquitectura simplificada para la que está programada el kernel. En el caso de la capa de I/O, el sistema unicamente tiene cuatro dispositivos: un puerto serie, un lapiz optico, una pantalla, y un chip de memoria flash de 8 MB. Por simplificar, la memoria flash no tiene sistema de ficheros y el kernel presenta el dispositivo como si fuese un único fichero de 8MB.

Nuevamente, para disfrute y deleite de los lectores más frikis, aquí teneis el kernel en cuestión. Os recomiendo que empeceis por el README, pues ahí están listados lo módulos que hemos añadido nosotros. Eso sí, resultan especialmente interesantes los ficheros io_pipe.c (la implementacion de las pipes) y sema.c (la implementación de los semáforos).

¡Ah! Y no olvideis que el fichero está protegido con contraseña fácilmente descrifrable por alumnos/as de ESIDE:

Nombre de usuario: borjanet
Contraseña: “Número del aula de programación” (3 dígitos) + “Nombre de cierta profesora de programación con risa muy contagiosa” (en minúsculas) + “Piso de los profesores” (un dígito)

Nuevamente, si no has estudiado en ESIDE, pideme la contraseña por mail.

Por cierto, hoy he entregado mi proyecto para la asignatura de Grid Computing (impartida por el mismisimo Ian Foster). Ahora ya sólo queda el examen de Algoritmos este viernes. Y por fin habré terminadoooooooo :-D

Mi kernel

Published
by
Borja Sotomayor
on 10/3/2005
in Cosas que nos enseñan en el doctorado and Informatica
. 7 Comments

Bueno, para los más frikis, aquí lo teneis para vuestro disfrute y deleite: el kernel que he programado como parte de la asignatura de Sistemas Operativos aquí en la Universidad de Chicago. ¡Ojo! Como el kernel podría ser de gran utilidad para alumnos que hagan la asignatura el año que viene, hace falta nombre de usuario y contraseña para acceder a la URL donde está colgado el kernel. Como me imagino que principalmente interesará a los frikis de ESIDE, la contraseña la podrá deducir facilmente cualquier persona que haya estudiado en ESIDE. Si no has estudiado en ESIDE, mandame un mail y te mando la contraseña.

Nombre de usuario: borjanet
Contraseña: “Número del aula de programación” (3 dígitos) + “Nombre de cierta profesora de programación con risa muy contagiosa” (en minúsculas) + “Piso de los profesores” (un dígito)

En cuanto al kernel, lo primero que tengo que decir es que no lo he programado yo solito, sino en colaboración con Mike Rainey, estimado compañero y excepcional friki. Luego, en vez de cascar un rollo macabeo sobre el kernel, me parece que lo mejor es dar un pequeño resumen y si alguien se pone a mirar el codigo fuente y no entiende algo, que lo plantee en los comentarios.

El kernel está escrito para una arquitectura simplificada llamada Yalnix. Hace falta un emulador para ejecutar el kernel, y por mucho que busco y rebusco, no lo encuentro por ningún lado en la web. Podría pasaros el binario que hemos utilizado nosotros, pero sólo funciona bajo Solaris… En fin, la arquitectura Yalnix es parecida a la que podriamos encontrarnos en un dispositivo movil tipo PDA (de hecho, el emulador de Yalnix te muestra una pantalla tipo PDA e incluye un dispositivo “lapiz” como el que tienen los PDAs). Por lo tanto, implementar un kernel resulta bastante más sencillo que en una arquitectura i386, aunque no por ello deja de ser complicado. A saber, nuestro kernel implementa la siguiente funcionalidad:

  • Gestión de la memoria física (utilizando un algoritmo First-Fit).
  • Gestión de memoria virtual (First-Fit) pero sin swapping al disco. El malloc interno del kernel utiliza un Buddy algorithm (que resulta que es un algoritmo pesimo para reservas de bloques pequeños de memoria, pero que es bastante rapido, y por lo tanto adecuado para una PDA)
  • Gestión de procesos (exec, fork, wait, getpid, delay, yield, …). El scheduler utiliza un algoritmo round robin.

Debo enfatizar que todo esto funciona. Es decir, cuando ejecutamos el kernel en el emulador podemos cargar programas, crear nuevos procesos, y ver como interactuan y se pelean por la CPU. No os podeis imaginar la cara de felicidad que se me puso cuando conseguí que el “Proceso A” y el “Proceso B” conmutasen sin problemas… Trabajar en este proyecto ha sido sinceramente muy revelador. Una cosa es estudiar el funcionamiento de (por ejemplo) la memoria virtual sobre el papel, y otra cosa muy distinta es pelearte tu mismo con la implementación desde cero de un gestor de memoria virtual donde el más mínimo fallo provoca un kernel panic.

En la segunda parte del proyecto (la que entregamos este viernes), tenemos que añadir lo siguiente al kernel:

  • Gestión de E/S a bajo nivel (llamadas del sistema para interactuar directamente con los dispositivos fisicos). Esto supone escribir código bastante obfuscado para gestionar (entre otras cosas) un puerto serie.
  • Gestión de E/S a alto nivel, tipo UNIX. Es decir, interactuar con los dispositivos de bajo nivel a través de ficheros como “/dev/serial”, “/dev/display”, etc. y con las llamadas típicas de UNIX (open, close, read, write, pipe, etc.)
  • Exclusión mutua mediante semáforos.

La segunda parte ya la tenemos 99.9% terminada (hemos llegado al punto en que nuestra principal preocupación es conseguir que los comentarios queden bonitos…). De la segunda parte me ha encantado implementar todo el sistema de pipes. Escribir el caracter de la barra vertical en la shell nunca volverá a ser lo mismo…

En fin, ahi lo teneis. Si os sentís especialmente frikis hoy, bajaros el kernel y echadle un vistazo (os sugiero que empeceis por kernel.c). Si teneis preguntas, planteadlas en los comentarios. ¡Ah! E intentaré colgar el segundo kernel la semana que viene.

P.D.- El kernel incluye varios comentarios en plan de cachondeo. A ver si podeis encontrarlos todos…