Archivo categoría Academia

Aristas de la prioridad académica

El día de hoy, jueves 3 de septiembre de 2009, Noga Alon dio una charla titulada Probabilistic Reasoning en la Facultad de Matemáticas de la Universidad Católica, donde estudio. El profesor Alon es uno de los matemáticos más prominentes de la actualidad, con más de 400 artículos publicados y una posición como investigador visitante en el Instituto para Estudios Avanzados de Princeton un trimestre cada año.

Pese a lo excepcional de la ocasión, el total de alumnos de la facultad que asistieron a la charla pueden contarse con una mano. Para mí, como organizador del evento, el hecho resultó ser tan vergonzoso, que me provocó fuertes deseos de salir rápida y disimuladamente de la sala, para así no tener que dar explicaciones al invitado. A él, por cierto, le había hablado de nuestro establecido coloquio de estudiantes, dándole a entender que su charla sería en este contexto. Lo que me mantuvo quieto, además de una cuota de orgullo personal, fue la tranquilidad de que se juntó un buen grupo, compuesto por profesores de matemáticas y ciencia de la computación de las universidades de Chile y Católica, además de un pequeño grupo de entusiastas alumnos de postgrado de Beaucheff, quienes incluso tomaron fotografías. Esto me emocionó sobremanera.

Tras la charla los asistentes tuvieron la oportunidad de conversar con el expositor, lo cual para mí era uno de los objetivos más importantes. Como asistente al 3er Congreso Latinoamericano de Matemáticos yo ya había tenido la suerte de conocerlo y hablar, y realmente fue un privilegio. Por ejemplo, se dio el trabajo de aconsejarme temas de estudio de mi interés y darme la correspondiente literatura relacionada. Literatura que, dicho sea de paso, conoce extremadamente bien. Además, la sencillez de su persona presenta un impresionante contraste con la profundidad de sus ideas, aunque algunos encontrarán que esto es natural entre tales genios.

Recapitulando las últimas horas, mientras caminábamos con Noga hacia la salida del campus, pensaba yo en qué motivos podrían tener los alumnos de matemáticas para ausentarse de manera tan organizada. Tengo algunas hipótesis, la más importante de las cuales es la desinformación. Si bien tengo una confirmación de palabra de que el correo electrónico de aviso fue enviado a todos los estudiantes de la facultad, un muestreo aleatorio entre mis compañeros me hace dudar de la capacidad de los servidores. Me dicen, simplemente, que no les llegó correo alguno al respecto.

Si descartamos la teoría anterior y suponemos que los alumnos sí sabían (al menos sé de varios que sabían y no fueron), todavía hay explicaciones que me descolocan. «Es que tengo prueba,» me dijo uno, mientras otro me recordaba que tiene clases. Si bien ambos motivos parecen naturales, creo que no pueden contarse como válidos. Vamos, que todos tenemos pruebas, y probablemente son unas tres o cuatro al mes. Para qué decir las clases. ¿Que no pueden dejar de estudiar durante 90 minutos? Algunos lo harán el sábado para ver un partido de fútbol, aunque tengan prueba el lunes. Otros lo hacen, estando en la universidad, para jugar ping pong frente a la oficina del Centro de Alumnos. También hay quienes juegan a las cartas, al yo-yo, a armar un cubo de Rubik a velocidad vertiginosa, o simplemente se sientan o echan sobre el soleado césped a conversar. Todo esto se realiza, en ocasiones, de manera excepcional a la hora de clases. Pero no, no pueden hacer también una excepción para ir a una charla.

Una segunda excusa, que a mi parecer es más natural que la primera, es la del idioma. El que una charla sea en inglés impone una barrera difícil de sortear. Hay inexperiencia en muchos, y en otros hay timidez ante la posibilidad de tener que hablar en inglés. Esto es un tema no menor para quienes tuvimos una formación escolar paupérrima en lo que a idiomas se refiere, pues con algo de suerte los programas incluían practicar el idioma, y quienes tenían esa suerte debían tener otro tanto para que efectivamente se realizara. Recuerdo a Renato Lewin entrando a la sala un día en nuestro primer año, mientras nos enseñaba el curso de Cálculo II. Sin saludar, y muy en su estilo apresurado, preguntó «¿saben inglés?» ante lo cual quedamos en silencio. «Bueno, si no saben inglés, tienen que aprender. Ésta es una carrera que se hace en inglés, y los libros más adelante están sólo en inglés.» Me pregunto cuántos habrán notado, en ese momento o después, que la palabra carrera en ese contexto se refiere a todo lo que suele suceder después de la universidad hasta la jubilación, lo que uno llamaría el trabajo y otros traducirían literalmente de currículum vítae: carrera de la vida. Me pregunto, también, cuántos habrán tomado en serio el consejo. Cuando fui a Arequipa a participar en mi primer workshop tuve la oportunidad de darme cuenta de varias cosas a este respecto. La primera de ellas es que la gente en la comunidad científica es feliz con su acento, por lo que el temor adolescente que puede resumirse en la frase «es que hablo mal» pasa a segundo plano. De hecho, a medida que aumenta la cantidad de países involucrados podemos encontrar una verdadera jungla de acentos, entonaciones, modulaciones y otras variantes. En definitiva, nada que no pueda superarse con una conversación y fuerza de voluntad.

Podemos también pensar que el tema de la charla no parecía mayormente atractivo. Un punto bastante justo, aunque sus partidarios evitan —voluntaria o involuntariamente— darse cuenta de que, si fuera sólo por el tema, mejor pondríamos un computador que presentara diapositivas y las leyera de manera automática. Puedo entender, hasta cierto punto, que los alumnos de pregrado consideren el tema como un factor a la hora de decidir, pero no logro entenderlo de los de postgrado. En el primer caso cabe destacar que los alumnos de pregrado —en especial los más nuevos— son los que conocen menos temas, por lo que la mayoría de las veces será algo nuevo para ellos, lo cual me lleva a pensar que los estanca el temor a lo nuevo o la conformidad con lo conocido, en ambos casos dejando entrever mediocridad o tal vez demasiada inocencia. En el segundo caso, no siendo un alumno de postgrado, es posible que no cuente con una visión clara de su realidad. Ya puedo imaginar a algunos diciendo «si supieras todo lo que tenemos que hacer,» lo cual podría llevarnos a una discusión sobre las condiciones humanitarias de los estudiantes o, en un tono de confrontación, sobre darles a entender que no son los únicos que hacen cosas. Por otra parte, tal respuesta puede interpretarse como una estrechez de mente que a la larga les impide obtener provecho de la experiencia de otros. Se me viene a la mente la imagen de flores que, seguras de que el agua es suficiente para sobrevivir, rehúsan abrazar al sol matutino.

En estas teorías —y en otras que no compartí acá— se asoma naturalmente una pregunta: ¿cuáles son las prioridades de los estudiantes de la facultad? Terminar la carrera es una de ellas, eso es seguro. Sin embargo, parece ser que en muchos casos la prioridad se acaba ahí, con el cartón en la mano en letra bonita, sin nada más allá.

Quiero pensar que el correo no se envió. Quiero pensar que si la gente hubiera sabido de la oportunidad que tendrían, la hubieran aprovechado, y que efectivamente no supieron. Sin embargo, me quedo con el gusto amargo de no haber visto a muchos que ya me habían confirmado, y que en el camino recordaron, de una manera u otra, que tenían cosas más importantes que hacer.

2 Comentarios

Tiempo exponencial y el problema del millón

Aviso: este artículo es una pequeña motivación al tema de la “eficiencia” de los algoritmos. Requiere ciertos conocimientos técnicos. Lo dejo en el blog para mantener registro de él (lo tenía escrito en un papel que encontré). ¡Comentarios bienvenidos!

Matías es un alumno de Introducción a la Programación. Para su primera tarea tiene que desarrollar un programa que escriba un número 1 en la consola. Con dos semanas de plazo para entregar, Matías —un alumno brillante— se relaja y decide aventurarse por una estrategia original. Probará todas las posibles secuencias de caracteres de largo 1, luego de largo 2, y así sucesivamente, hasta que una de ellas haga lo que pide el enunciado. De esta manera, él entregará el programa más corto posible que resuelve el problema (lo cual es motivo de orgullo).

Para conseguirlo cuenta con P computadores, cada uno con la capacidad de verificar O posibles programas por segundo (no me pregunten de dónde los sacó, sólo sabemos que los tiene). Llamemos t(n) al tiempo que tardarán todos estos computadores en verificar todos los programas de largo n (es decir, que tienen n caracteres en total). Suponiendo que Matías puede usar 256 caracteres para programar, tiene en total 256^n posibles programas de largo n. Así, el tiempo que tardará en verificarlos está dado por

t(n)=(256^n)/(P*O)

Supongamos ahora que en cada electrón del universo tenemos un supercomputador que realiza 10^50 de estas verificaciones por segundo. La cantidad estimada de electrones del universo es 10^130, por lo que

t(n)>=(256^n)/(10^50*10^130)

Ahora bien, el siguiente programa en Java escribe el número 1 en la consola. Tiene 96 caracteres.

public class Principal
{
  public static void main(String[] args) {
    System.out.println(1);
  }
}

Si eliminamos los saltos de línea innecesarios lo podemos dejar en 86 caracteres. Asumamos que éste es el programa de menor largo que es solución al enunciado.

public class Principal{public static void main(String[] args){System.out.println(1);}}

Para llegar a verificar los programas de largo 86, Matías debe verificar primero todos los de largo 85 (y darse cuenta de que ninguno le servía). En total hay 256^85 programas que verificar (es decir, exponencial respecto del largo del programa). Así, para n=85 tenemos que

Como 2^10=1024>1000=10^3, entonces

La edad estimada del universo es de 13.600 millones de años, y eso es 10^18. Esto significa que para verificar todos los programas de largo 85, Matías tardará t(85)>10^24>10^18 segundos, ¡más que la edad del universo!

¿Se van imaginando cuánto tiempo tardaría —con todo ese poder computacional— si el programa más corto que le sirve tuviera unas 200 líneas de código (que es algo más razonable que 85)?

Este simple ejemplo justifica un poco la elección del apodo “ineficiente” para los algoritmos de tiempo exponencial. Se sabe que los problemas de la clase NP pueden ser resueltos de manera determinista en tiempo a lo más exponencial (como el problema de Matías). Lo que no se sabe es si cada uno de ellos además se puede resolver en tiempo polinomial de manera determinista (P).

El problema de P y NP es uno de los más importantes en computación teórica, y ciertamente el más importante en el área de Complejidad Computacional. Tan importante es (y tan difícil), que es uno de los siete problemas por cuya solución el Instituto de Matemáticas Clay ofrece un millón de dólares.

Habrá que ponerse a estudiar.

No hay Comentarios

La Ciudad Blanca

A las 06:25 de ayer comencé el día viajando hacia el aeropuerto (SCL) en un transfer de Tur-Bus. Hice hora, luego el check-in y finalmente me tomé un desayuno buffet del Gatsby, mi primer alimento del día. Lo acompañé elegantemente con tres pastillas.

Un rato después me fui a la puerta donde debía embarcar. Ahí me encontré con Renzo, que vendría en el mismo vuelo que yo. A las 09:20 comenzaba a moverse el Boeing 737 de Sky y se alejaba de la puerta 26.

Durante la primera parte del vuelo (Santiago-Iquique) nos sirvieron un buen segundo desayuno (Renzo se había castigado en el Starbucks del aeropuerto). Después de todo lo que había comido en el Gatsby, finalmente fui derrotado por una simple combinación de café, jugo, pan, homelet, y un pastelito.

Conversamos con Renzo sobre RDF y SPARQL, y me ayudó a aclarar varias cosas que tenía pendientes desde que comenzó todo el cuento de la operación.

Cuando el avión comenzó a descender me di cuenta de la peor manera que había olvidado comprar chicle y traer algo para taparme los oídos. Recordé las primeras veces que había tenido problemas con los cambios de presión, en la Piscina Municipal de Maipú, donde hacíamos competencias de buceo con los salvavidas llevando bloques de cemento a 5.4 metros de profundidad, para luego volver a sacarlos. Le pregunté a una azafata si tenía algo para el dolor, pero sólo me pudo conseguir un poco de algodón. No es la mejor solución, pero es una solución parche (debería tirarme a político). En el paso por el aeropuerto de Arica compré un par de chicles antes de pasar por Policía Internacional y embarcar finalmente hacia Arequipa, la ciudad blanca (no Minas Tirith).

Almorcé en casa de Renzo. Un caldo blanco para empezar (caldo, arroz, carne de vacuno y dos o tres variedades de papas) y luego arroz con más carne y más papas. Nuevamente tuve que hacer una tregua con la comida. Además comenzaba a darme sueño, facilitado por el analgésico de las 16:00.

Salimos en el Datsun del 77 en familia y me acompañaron a buscar hotel. Yo tenía uno visto, pero estaba demasiado lejos del hotel la conferencia. Por suerte encontramos el Hotel Benavides, que por un precio similar al que tenía presupuestado me ofreció una cómoda habitación con vista al parque, sol en la mañana, y a tres minutos a pie de la conferencia.

Luego vinimos a Libertador, donde encontramos a Marcelo, Pablo y Claudio. Renzo se quedó trabajando con Claudio mientras se nos unía Leonid Libkin en el pisco sour de cortesía que les daba el hotel (Marcelo pagó el mío). Peter Wood y señora ya estaban en eso. Conversamos con ellos un rato.

El pisco fue continuado con una cerveza y luego fuimos a comer una exquisita alpaca mechada (qué weá más sana) en compañía esta vez de Leo Bertossi y Andrea Cali. Volvimos con Leonid a nuestros respectivos hoteles mientras los demás se fueron a un bar. Empecé a escribir esto pero me quedé dormido haciéndolo. A mitad de noche me desperté cuando se me cayó el notebook, pero todavía vive.

Por cierto, todos los agradecimientos a Yahoo! Research por el financiamiento. Espero a la noche contarles sobre hoy.

2 Comentarios