Por fin salieron los resultados de mi TOEFL, así que los comparto. Básicamente fue así:

Por fin saqué una sección de lectura perfecta. Ya era hora; a estas alturas ya ni chingo. La parte de listening me da coraje, porque estoy seguro de haberme dado cuenta del error durante el examen (también estoy casi seguro de que me equivoqué sólo en una pregunta; son como doce, así que tiene sentido).

Mi parte baja fue el speaking… obviamente. Pero me da risa porque esa parte se dividió así:

O sea, que mi capacidad de hablar inglés es limitada cuando se trata de “temas familiares” (donde “familiar” es “común”, no de mi familia); y en cosas académicas y “del campus” es decente… cuando casi todas las veces que he hablado inglés en mi vida en general ha sido para hablar de cosas comunes y no académicas.

La verdad es que sencillamente no estaba preparado para la sección hablada; espero que no sea un problema si sí me voy. Aunque aparentemente “me doy a entender”, que (espero) es lo importante.

El que me impresionó fue el writing; antes había sido mi punto débil, y ahora lo tuve razonablemente bien. Ambos ensayos (“Writing based on reading and listening” y “Writing based on knowledge and experience”) sacaron “Good (4.0 – 5.0)”, que se traduce a:

You responded well to the task, relating the lecture to the reading. Weaknesses, if you have any, might have to do with

• slight imprecision in your summary of some of the main points and/or
• use of English that is occasionally ungrammatical or unclear.

Le apuesto a lo segundo, dado que la última vez que llevé un curso de inglés fue en secundaria. Y por tanto creo que es entendible.

Como sea, estoy contento: saqué más de 100 puntos (que era el mínimo que pide la universidad más exigente), y me fue razonablemente bien. Aunque realmente el inglés nunca ha sido el problema para que me acepten o no en una universidad.

Antes que nada, perdón por la negligencia respecto al blog. No he escrito entradas ni aprobado (o tan siquiera leído) nuevos comentarios desde hace días. Prometo comenzar a hacer eso mañana; ahorita estoy sencillamente molido.

Después de dos días de estar organizando, subiendo y etiquetando (además de ir al cine, a ver a mi amiga Claudia y perder un día en Toluca), por fin están las fotos de mi viaje a Guanajuato.

Taller de Investigación en Guanajuato

Están divididas por día básicamente; porque terminé tomando más de trescientas treinta fotos… aunque al final quedaron “sólo” trescientas dieciocho.

Enjoy.

El Primer Taller Iberoamericano en Geometría Combinatoria y Computacional llegó a su fin hoy a las dos de la tarde. No había escrito al respecto porque los últimos días fueron particularmente agitados (dentro y fuera del taller).

Estoy muy contento de haber venido; no sólo aprendí toneladas de cosas que no sabía; además conocí un chingo de gente increíblemente inteligente (además de agradable) y me la pasé bomba.

Aunque estuve pajareando en varios problemas, le entré realmente a dos. Uno de ellos está bastante bonito y probamos un resultado (con todo y algoritmo) que suena bastante interesante. El otro conseguimos un algoritmo que aún no sabemos si podemos bajarle la complejidad de O(n²), pero que genera un montón de problemas similares.

Si tengo suerte, uno de esos problemas será mi tema de tesis.

En un momento saldremos a la comida de despedida, y mañana nos iremos como al medio día. Las fotos se acumulan cada vez más, pero no creo subirlas hasta regresar a mi querida Ciudad de México.

El jueves nos levantamos tarde (hacía años que no me emborrachaba… y menos en miércoles y con doctores y estudiantes de maestría y doctorado), y al llegar al taller Urrutia nos regañó por llegar tarde. Y después me dio (por fin) mis cartas de recomendación.

A las doce me fui a DHL; tenía que enviar los paquetes antes de la una para que llegaran el viernes (15 de diciembre, último día para recibir solicitudes). El miércoles (antes de la reunión) pasé la tarde haciendo los paquetes, que siempre me ha dado una angustia enorme. Y sigue dándome, por cierto.

Al llegar a DHL, hice con la empleada lo necesario para dar las direcciones de las universidades (tres de ellas; me faltan dos), y al momento de pagar resultó que no tenía más que para pagar uno de ellos.

Mierda.

Se suponía el viernes antes de venir a Guanajuato me iban a dar $1,500.00 pesos, adelanto de mis viáticos. No pude pasar por ellos, pero pedí que me los depositaran y me habían dicho que eso harían.

Sólo nomás no lo hicieron.

Por suerte estoy con cuates, que me hicieron el favor de prestarme el dinero necesario; pero tuve que ir al CIMAT y regresar al DHL derrapándome por la carretera. Pero todo salió bien: a la una en punto mis paquetes iban en camino a las universidades.

Ahora (al menos con esas tres universidades) ya no está en mis manos.

En la mañana fuimos al taller y de nuevo avanzamos bastante padre en la chamba. Yo en particular propuse un algoritmo (para otro problema distinto al de ayer) que parece puede jalar… la única bronca es que se me olvidó que O(n²+n) es distinto a O(n³).

Saliendo fuimos a comer al centro en mi carro, y ya veníamos de regreso cuando me di cuenta de que había olvidado mi cámara. Lo peor era que ahí estaba el memory stick de un giga que Enrique me prestó.

Nos regresamos al restaurante, y por suerte y buena onda de la gente de ahí, mi cámara estaba esperándome. Se lo agradezco mucho a los del restaurante, porque me guardaron mi hermosa camarita.

Me puse un buen susto. Tengo que recordar el bailar La Macarena cada vez que salgo de un lugar, para comprobar qué gadgets traigo conmigo.

El primer día del taller fue algo pesado, pero bastante productivo. La gente con la que estuve trabajando fuimos capaces de dar una propuesta (algoritmo incluido) para un problema abierto (bastante nuevo), y los doctores están de acuerdo en que al menos estamos en camino para obtener una aproximación de la solución óptima. A mí y otro compañero nos suena que podemos encontrar la solución óptima si es posible realizar unas comprobaciones localmente en la gráfica; pero los doctores dicen (y tienen bastante más experiencia) que el problema tiene toda la cara de ser NP-duro.

Además, la idea inicial se me ocurrió a mí y utiliza la triangulación de Delaunay… si bien se me olvidó cómo se llamaba y nada más dije “la otra de la de Voronoi, que no tiene cosos dentro de los circulitos”.

Bastante divertido el día. Las fotos se acumulan, pero no tengo el tiempo (y paciencia) para subirlas y clasificarlas.

Hoy al medio día partí, junto con Marco y Armando, a Guanajuato a nuestro taller de investigación.

Tomamos todo periférico hasta alcanzar los letreros que decían “Querétaro”, y al llegar a ídem nos detuvimos a descansar y comer. Después seguimos los letreros que decían “San Miguel Allende”, donde tomamos fotos (no las voy a mostrar ahora; las dejaré al final del viaje), y depués seguimos los letreros que decían “Celaya”, hasta encontrar letreros que decían “Guanajuato”, los cuales seguimos hasta llegar a nuetro destino.

En total fueron seis horas de viaje en carretera, y una más de tráfico en la ciudad (y se quejan del D.F.) El hotel está simpático, tiene red wireless y mañana empezamos a trabajar.

No sé si nuestro método de viaje sea el más efectivo (en retrospectiva, el siquiera mirar un mapa tal vez hubiera estado chido), pero llegamos sin ningún problema y no manejé en carretera de noche, que era lo que quería evitar.

Mañana empezamos lo chido. Por ahora parece que aprovecharemos para pasear por la ciudad.

Antes que nada, perdón por no tener nada nuevo en varios días y por no haber aprobado o contestado comentarios. No fue por ninguna razón rara; sólo no estuve conectado todo este tiempo.

Acabo de pasar un fin de semana bastante sui generis, por decir lo menos. Resulta que tenía que hacer el TOEFL para mis solicitudes a las universidades donde quiero hacer el doctorado: ya estoy en eso… de nuevo.

El TOEFL que tenía expiró en febrero de este año, y me vine a enterar la semana pasada. Por suerte el GRE dura 5 años, si no también tendría que haberlo hecho; pero el TOEFL era imposible que no lo hiciera. Y para acabarla de amolar, ya no había lugares para hacerlo antes del 15 de diciembre (fecha límite para varias de mis solicitudes) en el DF.

Ni en Querétaro, ni Puebla, ni Guanajuato, ni Morelia, ni en ningún lado relativamente cercano. El único lugar donde todavía podía hacerlo, era Puerto Vallarta. Así que con todo el dolor de mi corazón, tuve que sacrificarme y pedirlo ahí.

Ahora, mucha gente que no me conoce probablemente crea que estoy siendo sarcástico cuando digo que me tuve que sacrificar. No lo estoy siendo; a mí no me gusta la playa. No me gusta el sol, no me gusta la arena, y menos me gusta el agua salada. La combinación me gusta aún menos.

Pero tenía que hacer el TOEFL, y además de Puerto Vallarta sólo había lugares como Mexicalli o Yucatán… Vallarta era la opción menos lejana.

Primero intenté solicitar el TOEFL en línea usando la página del ETS. Por supuesto, el sistema se murió cuando estaba enviando la información de la tarjeta de crédito… dos veces, así que al otro día (el miércoles) hablé por teléfono. Después de cinco minutos de dar mis datos en inglés y explicar que el sistema de la página me había fallado, la señorita que me contestó la llamada me preguntó si quería que continuáramos mejor hablando en español, lo cual yo agradecí infinitamente y terminé de solicitar el TOEFL sin broncas. El jueves fui por los boletos de camión y algunas cosas para el viaje, y el viernes me fui.

Sólo que con la banda habíamos quedado de reunirnos aprovechando que Edgar está en México, así que en mi camino a la terminal pasé a darle un abrazo a Edgar.

Óscar, Yo, Erick y Edgar

Después de un trago con los cuates, ahora sí fui a la Terminal del Norte, donde tomé el camión que hizo doce horas a Puerto Vallarta.

Dado que eran doce horas de ida, y doce de regreso, decidí que era idiota el regresarme el mismo sábado, así que renté una habitación de hotel para regresarme el domingo por la noche a la ciudad. Fue chistoso, en la agencia de viajes en la terminal de Puerto Vallarta les pedí la habitación más económica que tuvieran, y resultó que era una con vista al mar.

Vista de la habitación

Me bañé y descansé un poco del viaje de doce horas, y después fui a comer a un restaurante cerca de mi hotel, también con vista a la playa.

Vista del restaurante

Mi examen era a las 6:00 de la tarde, con órdenes de presentarme a las 5:30, así que estuve baboseando un rato por Puerto Vallarta, y después tomé un taxi al lugar del examen (la “American School of Puerto Vallarta”… o algo similar).

El examen fue mucho más largo de lo que recordaba. Y ahora además piden hablar, y lo graban a uno con un micrófono; esa parte fue nueva para mí, y me puse algo nervioso, pero creo que contesté todo de manera coherente y con una pronunciación entendible. El resto del examen creo que me fue bien; pero ya no le ponen a uno los resultados objetivos. Antes, al final del examen le ponían a uno en pantalla cuánto iba a sacar en las partes que la computadora puede calificar (el ensayo y la otra pregunta de redacción evidentemente no las puede revisar la computadora); pero ahora no. Pero de cualquier forma creo que me irá bien; aunque claro no puedo saberlo a ciencia cierta hasta que salgan los resultados.

Después me regresé al hotel y dormí bien por primera vez en muchas horas, y al otro día fui a pasear por el Malecón, que me lo habían recomendado ampliamente.

Yo en el Caballito de Mar

Aunque ciertamente está simpático, sí prefiero más el de Acapulco.

Dado que hacía años que no me remojaba en agua de mar, decidí que era medio absurdo que estando en Puerto Vallarta no lo hiciera, y procedí a meterme al mar.

Yo en la playa

Después de unas cuantas horas, refrendé mi posición de toda la vida: no me gusta el mar. La arena se mete por todos lados, la sal se me pega en los pelos del cuerpo (que tengo muchos), y el sol pega constantemente.

Pero estuvo divertido, y satisfice mis requerimientos de agua de mar de aquí a los próximos cinco años. Si puedo evitar la playa en todo ese tiempo, no voy a quejarme.

Me metí a la alberca del hotel para quitarme cualquier resto de sal que la regadera no hubiera eliminado, y me fui de nuevo al Malecón a buscar dónde comer. Comí en la Bodeguita del Medio, donde pude tomar algunas fotos bastante padres de la puesta de sol.

Puesta de sol desde la Bodeguita del Medio

Y donde comí un Camarón dos quesos que estaba delicioso, y me tomé un mojito igualmente rico.

Camarón dos quesos

Muy chido lugar; nunca había ido. Voy a ir a uno de los dos que están en la Ciudad de México, a ver si están tan padres.

Mi autobús salía a las nueve, así que recogí mis maletas del hotel, y me fui a la terminal de autobuses donde pude fotografiar a una chava bastante guapa. Lástima que por querer ser discreto le quité el flash, y entonces la foto no salió muy bien que digamos.

Guapa en la terminal

Y me regresé a la ciudad, haciendo de nuevo doce horas. Por supuesto cuando llegué y vi mi correo, resultaba que tenía que terminar un texto de forma inmediata, que fue lo que estuve haciendo ayer y por lo cual esta entrada la escribí hasta ahora.

En total estuve más o menos 60 horas fuera de la ciudad, 24 de ellas en un autobús viendo películas malas o tratando de dormir incómodamente. No lo recomiendo a nadie si pueden evitar algo del estilo.

Y bueno, esta semana tengo que seguir viendo lo de mis solicitudes (tres de ellas; otras dos las voy a enviar en enero o febrero), y preparar mi viaje a Guanajuato porque me voy ahí a un taller de investigación la próxima semana.

Acaban de enviar a la lista de correo de la maestría los costos de la foto de generación:

• Sólo la foto de 25×60cm: $150
• Fotoblock, sobre madera: $250
• Fotoframe: $350
• Fotoframe con placa $450

Saber que no hay forma de que puedan obligarme a ir: no tiene precio.

Ley de Murphy: el día que no duermo por terminar una tarea, el profesor decide no recogerla sino hasta el día siguiente.

El jueves expuse en mi seminario de tesis; creo que me fue bastante bien. Pero lo importante (además del hecho de que por ello había estado demasiado ocupado para publicar en el blog) es que en un momento tuve que hacer la gráfica de una Unit Disk Graph; una gráfica donde los nodos están en el plano euclidiano, y dos de ellos están conectados (comparten una arista) si su distancia es menor o igual a uno.

Es un modelo obvio para redes inalámbricas si consideramos que todas las antenas tienen la misma potencia y definimos “uno” como el rango de la señal.

Ahora, lo interesante de hacer un ejemplo de gráficas de disco unitario, es que ésta sea conexa; es decir, que todo nodo pueda mandarle un mensaje a cualquier otro siguiendo una ruta a través de las aristas. Si uno hace a pie un ejemplo de 5 nodos la cosa se pone ya de hueva, porque uno tiene que estar midiendo que cada nodo esté a distancia uno o menor de al menos otro nodo.

Por supuesto, entonces uno quiere automatizar el proceso (yo quería un ejemplo de 50 nodos). La bronca es que si uno no tiene cuidado, todos los nodos (o una gran parte) terminan amontonados en alguna parte del marco donde uno esté trabajando. Recuerden que yo uso PStricks para mis gráficas en , así que lo que hice fue un programita en Java que generara 50 puntos aleatorios siguiendo el siguiente algoritmo:

1. El primer punto es completamente al azar.
2. El punto i elige a un “hermano” j al azar entre los otros i-1 puntos.
3. Se toma un ángulo α entre 0 y 360 grados (o 0 y 2π radianes, como les guste verlo), y una distancia d al azar entre 0.9 y 1.0, y las coordenadas de i son las de j desplazadas la distancia d en la dirección α, a menos que el punto se salga del marco (pasa probabilísticamente pocas veces; en el peor de los casos hay un 25% de probabilidad de que el punto resultante esté en el marco)
4. El punto que se obtuvo arriba es agregado si y sólo si se encuentra a distancia 0.5 o mayor de todos los demás puntos. Por esta condición el algoritmo se tarda un poco; para cada punto i, debe comprobar que esté “lejos” de los otros i-1 puntos. Y si el punto está demasiado “cerca” de otro, se repite el paso anterior y este.

Siguiendo este algoritmo, se obtienen gráficas bastante simpáticas: esta fue la que puse en mi presentación:

Unit Disk Graph

Por supuesto la idea del programita no era sólo generar los puntos aleatorios; lo chido es que me generó básicamente todo el código para PStricks. Yo sé que Java no es la mejor elección para estas cosas, pero la entrada y salida de ML me dio demasiados dolores de cabeza y mi Python está demasiado oxidado. Pensé en hacerlo con Perl, pero lo que realmente quería era un intérprete interactivo, así que me pasé a Java porque sencillamente me siento ahí cómodo. Pero a la próxima uso un lenguaje interpretado, seguro.

Como sea estuvo chido; utilicé programitas que me generaran el código PStricks en todos los casos excepto los más sencillos. Creo que terminaré haciendo una biblioteca para ciertas cosas geométricas comunes; nada más tengo que elegir con cuidado en qué lenguaje la quiero.

Hace unos años, Grigory Perelman publicó en la red lo que hace unos días quedaría formalmente aceptado como la prueba de la conjetura de Poincaré. La conjetura tenía más de cien años de ser formulada, y era uno de los siete problemas del milenio (ahora son sólo seis).

La cosa es interesante no sólo porque se resolvió un problema ya viejo, sino por la circunstancias en las que se resolvió: no se publicó en una revista con arbitraje, no hay consenso acerca de qué tan completa era la prueba (unos dicen que la prueba era completa, otros dicen que le faltaban detalles, y otros más incluso dicen que sólo era una “descripción” de cómo debía ser la demostración, muy alejado de una prueba completa), y además el autor es un tipo interesante, por decir lo menos.

Y acaba de confirmar que no va a aceptar la medalla Fields. La medalla Fields es como los premios Nobel para matemáticas; sólo que se da cada cuatro años.

(No queda claro si va o no a aceptar el millón de dólares de recompensa que ofrece el Instituto Clay de Matemáticas por resolver alguno de los problemas del milenio).

El New Yorker acaba de publicar un artículo muy bonito describiendo la grilla detrás de todo eso, intercalado con una entrevista a Perelman y muchos otros matemáticos; lo recomiendo ampliamente, está bastante entretenido.

Hoy, sin mucha alharaca y algo (no mucha) de hueva, me inscribí a mi tercer semestre en el IIMAS. Voy a llevar mis últimas dos materias y mi seminario de tesis. Las materias son:

• Redes de Computadoras, con Jorge Urrutia.
• Criptografía, con Gerardo Vega.

Y mi seminario de tesis, con Urrutia también.

Si parecen pocas materias es porque lo son: el semestre pasado llevé una materia más de las que “debía”, y ahora sólo me faltan las dos que llevaré. Se ve un semestre mucho más sencillo que los anteriores, módulo la tesis, que planeo darle máxima prioridad: a finales de año mando mis solicitudes para el doctorado en Canadá, o a ver qué otro lado se me ocurre.

Mi segundo semestre en el IIMAS estuvo más cargado de trabajo que el anterior, por la materia extra más que nada, pero fue mucho más sencillo que el primero. Las materias las elegí yo, y en general me gustaron bastante.

Eso se reflejó en mis calificaciones: saqué 10 en todo. Que es la primera vez en mi vida que saco 10 en todo en un ciclo escolar: ni en la Facultad, ni en el CCH, ni (mucho menos) en la secundaria, ni en la primaria había sacado la máxima calificación en todas mis materias. Bueno, en la primaria no hay materias, pero tampoco saqué 10 de cualquier forma. Nunca.

Yo no empecé a ser “buen estudiante” hasta que entré al CCH. En la primaria no me fue mal, pero tampoco terriblemente bien: jamás fui de la escolta, ni del cuadro de honor, ni de nada parecido, y ni de chiste estuve cerca de ello. Bailé disfrazado de pollito, eso sí, pero lo hicimos todos los de mi grupo.

En secundaria menos. No por algo la hice en cuatro años; de hecho en mis “primeros” tres años, siempre terminé en extraordinario en alguna materia. Matemáticas, por cierto, por desconcertante que ahora parezca. E inglés.

Buen Dios, detesté la secundaria. Todo lo relacionado con ella, incluyendo mi primer beso.

Y ya, después me “compuse” y ahora resulta que me va cada vez mejor en cada nivel educativo. Me está yendo mejor en el IIMAS que en la Facultad, me fue mejor en la Facultad que en el CCH, y si sigo así voy a terminar mi doctorado summa cum laude.

Que no creo que sea muy significativo: después de mi traumática experiencia en la secundaria, he llegado a la conclusión de que arriba de seis es presunción.

Como sea, terminó oficialmente la primera mitad de mi maestría. Ahora sólo tengo que hacer mi tesis en un año (o menos) y conseguir que me acepten en un doctorado de mi agrado.

Hoy expuse en mi clase de Geometría Computacional (aquí está la presentación, por si alguien le interesa).

Y con eso, para motivos prácticos, terminé mi segundo semestre en la maestría.

Este semestre llevé cinco materias; cuatro regulares y además el seminario de investigación. En muchos sentidos fue más pesado el semestre; pero en muchos otros fue mucho más sencillo. Pero por mucho.

La carga de trabajo intelectual fue más pesada que el semestre anterior. Y por eso se me hizo más sencillo; pensar no es una de mis debilidades. La carga de trabajo idiota (como andar haciendo microprocesadores, que me perdonen los inges) fue básicamente mínima.

No tengo aún calificaciones excepto de una materia; haré una entrada comentando cómo fue en cada una de ellas cuando las sepa.

Este semestre me ha dominado una hueva inmensa. No me termina de quedar claro porqué, ya que las materias están bastante interesantes.

Lógica Matemática con Francisco Hernández Quiroz está muy chida; sobre todo para alguien como yo que nunca he sido fan de la lógica. No tengo problema con esa materia, pero tampoco me emociona en exceso.

Sistemas Distribuidos con Sergio Rajsbaum está interesante, pero el tema está muy árido. Ahorita Sergio se fue y nos está dando clase Manuel, con quien hacía años que no tomaba clase. El tema es sincronización de relojes, y está chido; pero tampoco me emociona en extremo. Tampoco tengo bronca con esta materia.

Geometría Computacional también está padre, pero Urrutia ha faltado mucho por andar en congresos, y de aquí tengo que sacar mi tema de tesis. Eso me angustia; pero la materia no.

Teoría de la Complejidad (con Sergio también) es una materia preciosa… pero ya he visto casi todos estos temas como siete veces. En este preciso momento Sergio no está y estamos viendo algoritmos con DNA. El tema es nuevo para mí e interesante (y el tipo que nos da la clase es cagadísimo), pero tampoco me emociona en exceso. Ytampoco me preocupa.

(Tan poco me emociona que estoy escribiendo esto durante la clase.)

Y lo que más me preocupa es mi Seminario de Tesis, porque le he dedicado muy poco tiempo, básicamente leyendo artículos de mi materia de Geometría Computacional.

Pero sí ando muy desganado con la escuela. Le dedico más tiempo al blog, de hecho. Y más vale que se me quite, porque ya viene el fin de semestre.

Unicode es la neta. Lástima que no se vea tan bonito como ; si no, lo usaría para este tipo de cosas:

CLIQUE es NP-completo

Primero, CLIQUE ∈ NP. Sencillamente verificamos que la adivinanza que nos de el oráculo sean k nodos, y además comprobar que cada nodo esté conectado a todos los demás. Verificarlo nos toma O(n²).

Segundo, vemos que SAT α CLIQUE. Dada una instancia de SAT (una fórmula lógica φ), la queremos reducir polinomialmente a una instancia de CLIQUE (una gráfica G y un entero k), de tal forma que φ sea satisfacible si y sólo si G tiene una subgráfica completa de k vértices.

Si φ tiene k cláusulas, por cada cláusula c_i de m literales, añadimos m vértices a G, y los nombramos v_i,1,…,v_i,m. Y añadimos aristas para cada par de vértices v_i,l, v_j,m excepto cuando i=j, y cuando v_i,l=¬v_j,m.

Ejemplo: dada la fórmula

obtenemos la gráfica G

Ejemplo CLIQUE

Donde

v_1,1 en G es v₁ en φ, v_2,1 es v₂, v_3,1 es v₁, etc.

Entonces sólo falta demostrar que φ (donde φ tiene k cláusulas) es satisfacible si y sólo si G tiene una subgráfica completa de k vértices.

• ⇒ φ (con k cláusulas) es satisfacible. Entonces para toda cláusula c_i al menos una de sus literales es verdadera. Sea V’ el conjunto de vértices correspondientes a esas literales (aunque es posible que haya más de una literal verdadera por cláusula, tomamos sólo una). Sean v_i y v_j cualesquiera dos vértices distintos en V’: v_i y v_j están en cláusulas distintas, porque tomamos sólo una literal por cláusula, y como todas las literales de V’ son verdaderas, no es posible que v_i=¬v_j. Por lo tanto, por construcción, v_i está conectado a v_j. Como esto ocurre para cualquier par de vértices en V’, entonces todos los vértices de V’ están conectados entre sí.

  Por lo tanto, G tiene una subgráfica completa con k vértices.

• ⇐ G tiene una subgráfica completa de k vértices. Para cada uno de los vértices, le asignamos un valor de verdad a la literal correspondiente en φ. Como los vértices están conectados, por construcción están en cláusulas distintas de φ (y no hay v_i=¬v_j); entonces cada una de esas cláusulas se evalúa a verdadero. Pero como eran k vértices, esto ocurre con k cláusulas: o sea con todas las cláusulas de φ, y por lo tanto encontramos una asignación de variables tal que φ se evalúa a verdadero.

  Por lo tanto, φ es satisfacible.

Pero es que es mucho más bonito con (por no mencionar lo rápido):

CLIQUE es NP-completo

Primero, CLIQUE NP. Sencillamente verificamos que la adivinanza que nos de el oráculo sean nodos, y además comprobar que cada nodo esté conectado a todos los demás. Verificarlo nos toma .

Segundo, vemos que SAT CLIQUE. Dada una instancia de SAT (una fórmula lógica ), la queremos reducir polinomialmente a una instancia de CLIQUE (una gráfica y un entero ), de tal forma que sea satisfacible si y sólo si tiene una subgráfica completa de vértices.

Si tiene cláusulas, por cada cláusula de literales, añadimos vértices a , y los nombramos . Y añadimos aristas para cada par de vértices , excepto cuando , y cuando .

Ejemplo: dada la fórmula

obtenemos la gráfica

Ejemplo CLIQUE

Donde en es en , es , es , etc.

Entonces sólo falta demostrar que (donde tiene cláusulas) es satisfacible si y sólo si tiene una subgráfica completa de vértices.

• (con cláusulas) es satisfacible. Entonces para toda cláusula al menos una de sus literales es verdadera. Sea el conjunto de vértices correspondientes a esas literales (aunque es posible que haya más de una literal verdadera por cláusula, tomamos sólo una). Sean y cualesquiera dos vértices distintos en : y están en cláusulas distintas, porque tomamos sólo una literal por cláusula, y como todas las literales de son verdaderas, no es posible que . Por lo tanto, por construcción, está conectado a . Como esto ocurre para cualquier par de vértices en , entonces todos los vértices de están conectados entre sí.

  Por lo tanto, tiene una subgráfica completa con vértices.

• tiene una subgráfica completa de vértices. Para cada uno de los vértices, le asignamos un valor de verdad a la literal correspondiente en . Como los vértices están conectados, por construcción están en cláusulas distintas de (y no hay ); entonces cada una de esas cláusulas se evalúa a verdadero. Pero como eran vértices, esto ocurre con cláusulas: o sea con todas las cláusulas de , y por lo tanto encontramos una asignación de variables tal que se evalúa a verdadero.

  Por lo tanto, es satisfacible.

En Lógica Matemática con Francisco Hernández Quiroz nos dio Göedel para niños (©).

Sea una teoría matemática (un subconjunto del cálculo de predicados con una interpretación y un universo U), con como axiomas. Entonces

1. Existe tal que pero (para todo sistema de demostración como los vistos en clase). En pocas palabras, existen fórmulas tales que y .
2. Si agregamos un axioma adicional tal que o , entonces con son inconsistentes.

(Antes de que mis amigos matemáticos me salten encima para decir que cualquier cosa de arriba esté mal: tengan en cuenta de que es la versión para niños).

Después de decirnos eso, se dio el siguiente diálogo:

Francisco: Y bueno, después de que Göedel demostró esto, mandó a la lógica a…
Yo: ¿A la fregada?

Hoy, sin mucha alharaca pero sí hueva, me inscribí para mi segundo semestre en el IIMAS. Voy a llevar cuatro materias y mi seminario de tesis. Las materias son

• Lógica Matemática, con Francisco Hernández Quiroz.
• Sistemas Distribuidos y Verificación, con Sergio Rajsbaum.
• Geometría Computacional, con Jorge Urrutia (mi director de tesis).
• Teoría de la Complejidad, con Sergio Rajsbaum.

Y mi seminario, que es con Urrutia también. Dado que los tres profes me gustan, creo que será un semestre menos angustiante que el anterior.

Mi primer semestre en el IIMAS fue traumático por varias cosas. Yo no quería estar ahí, y además tuve una materia que en mi vida yo hubiera elegido por voluntad propia para llevar, y otra en la que el profesor era un retrasado mental, además de insoportable, así que sí era medio pesado para mí en algunos momentos.

La materia que más me gustó en el semestre, sin duda alguna, fue Estructuras de Datos y Algoritmos, con Jorge Urrutia. Tanto que me metí con él para hacer la tesis, y espero que eso salga bien.

Exceptuando un examen en el que saqué seis (combinación de exceso de confianza y un examen excesivamente talachudo y con casi nada de teoría), tuve 10 en absolutamente todo. Pero lo chido de esa materia fue nuestra tercera tarea.

Urrutia se fue a China (creo) unas semanas, y entonces se le ocurrió la genial idea de dejarnos 27 ejercicios de tarea. Y no eran ejercicios del tipo “¿cuánto es 2+4?”; algunos estaban bastante pesados.

Cuando Urrutia regresó, la mayoría llevaba un puñado de ejercicios resueltos; yo llevaba la mitad. Conforme se acercaba el día de entrega, yo avanzaba cada vez más, hasta que una semana justo antes de entregarla, el grupo hizo presión sobre Urrutia para que sólo hubiera que entregar la mitad de los ejercicios, y la otra mitad regresando de las vacaciones de diciembre.

Urrutia se dobló como un mapa.

Me dio un coraje. Porque le había dedicado a esa maldita tarea básicamente todo mi tiempo libre, y de verdad la estaba resolviendo (un montón de las respuestas estaban en la red, con una búsqueda no muy compleja). Y además por supuesto tampoco era justo con mis compañeros el que yo pidiera que la fecha de entrega original se mantuviera.

Entonces tomé la decisión de que, como forma de protesta, iba a entregar la tarea completa para el día en que se había dejado originalmente. Me costó un huevo, y dormirme a las cuatro de la mañana del día de entrega. Pero acabé.

Porque además no sólo resolví la tarea; la hice en , con diagramas, algoritmos, demostraciones y toda la cosa. Además de revisar la correctez de mis respuestas, revisé hasta la locura la redacción, ortografía y presentación de esa tarea. No hacía algo así con un texto desde mi tesis de licenciatura.

Cuando le di la tarea a Urrutia (32 cuartillas, engargoladas bien bonito), le dije que me reservaba el derecho de entregar correcciones. Lo cual fue muy inteligente; Omar me ayudó a detectar algunos errorcillos (dos de ellos graves) que había con mi tarea. Entregué la versión final cuando terminaron las vacaciones; pero creo que el ayudante la ignoró, porque ya me había puesto 10.

Aquí está la versión final, por si quieren echarle un ojo. De especial orgullo son mis diagramas para redes de flujo; quedaron bien bonitos.

Al momento de hacer el último examen, no tuve ningún problema: estaba basado en la tarea. Y por supuesto, terminé sacando 10.

La segunda mejor materia, me pesa admitir, fue Arquitectura de Computadoras. Esa materia sería fabulosa… si no fuera obligatoria. Tiene todos los elementos por los cuales no elegí Ingeniería en Computadoras como mi carrera.

De esa materia ya platiqué el climático final que tuvimos mis compañeros y yo, así que aquí no me extenderé más en ello.

Savage me puso 9 al final. Es una calificación excesivamente noble para conmigo; estrictamente yo no merecía más de ocho. Pero como de verdad nos matamos en ese proyecto final, y mis contribuciones al mismo fueron para nada despreciables, no creo que sea injusta. Es noble, pero no injusta.

En tercer lugar está Lenguajes de Programación. Esto (sigo diciendo, y lo sostengo) no es culpa de la materia; es que Algoritmos y Arquitectura sí fueron muy buenas. Francisco tenía dos grandes desventajas: era coordinador de la carrera en Ciencias, lo cual evidentemente consumía mucho de su tiempo, pero además tenía el ayudante más estúpido de la historia. No, esperen; esa sería la X-fig.

Pero el tipo le hacía competencia.

Claro, yo no soy monedita de oro y me gané a pulso el odio del tipo. Eso no es raro; no es el primer ayudante que me odia. Sólo que es apenas el segundo que lo muestra a la hora de calificar.

(La otra sería la X-fig).

Como sea, con un muy buen último examen, última tarea, y una reposición pude sacar el 10.

De la última materia, todavía me enojo. Autómatas y Lenguajes Formales me dio desconfianza el Dr. Luis Pineda como profesor desde el principio. El tipo era pedante, repetitivo, queriéndose hacer el gracioso sin conseguirlo, y cómo dio el curso era patético.

Yo estoy maleado; tomé un excelente curso de Autómatas con Elisa Viso en Ciencias. Pero de cualquier forma; es inaceptable perder tres meses viendo autómatas y lenguajes regulares, ver sólo un mes gramáticas libres de contexto, y ver una clase de Máquinas de Turing.

Además, Pineda se robó los acetatos de otro curso; un cuate encontró los originales. Eso no tiene nada de raro; todos los profes toman de otro lado cuando así conviene hacerlo. Pero dan crédito. Pineda sólo los tradujo (mal; en todos lados hay “and” y “but” en sus acetatos… además de que están hechos en PowerPoint), y les puso su nombre. Y cada vez que alguien tenía una duda no trivial, el tipo tenía grandes problemas para contestarla, además de que se ponía altanero y como que comenzaba a enojarse.

Eso me hacía angustiarme bastante con esa materia. Como sea, sencillamente dejé de ir como a la mitad del semestre, y me cuidé de sólo entregar bien las tareas y hacer bien los exámentes. Exceptuando un par de tareas donde en una saqué 7 y en otra 8.5, tenía 10 en todo lo demás.

En la tarea que saqué 7 fue exceso de confianza (de nuevo; debo cuidar eso); pero en la tarea donde saqué 8.5 fui a reclamarle, porque mi tarea estaba bien. El tipo, descubrí con asombro, era incapaz de entender una demostración si no era como él las hacía. No me extrañó descubrir después que es del Tec. Así que dejé mi 8.5 en paz; realmente casi no afectaba mi calificación final.

El examen final contaba 40% de la calificación; y yo necesitaba 9 para tener 10 en la calificación final. Saqué 8, porque el tipo me puso mal una demostración porque la hice distinto a como él las hace. Traté de explicarle que estaba bien, pero de verdad es incapaz de entender una demostración ligeramente abstracta. Me dio hueva y dejé así las cosas.

En parte el enojo que tengo es conmigo; si ya había visto que el tipo es un idiota, debí haber respondido como a él le gustaba y evitarme problemas. Pero es que sencillamente así no funciono yo. Y además, es un mugre punto, y yo sé que manejo el tema probablemente mejor que como lo maneja él, así que me quedé con mi 9.

Como sea, sí me molesta, porque idiotas como él no deberían dar clases. Yo sí le recomiendo a quien sea que esté tomando clases, que se evite tomarlas con Luis Pineda. Pero claro, es mi opinión personal, y habrá quien difiera.

Pero en mi opinión, el tipo es un tarado.

Y ya; esa fue básicamente la única mancha en mi primer semestre. Acabé con promedio de 9.5, que es el mismo con el que acabé la licenciatura, así que al menos no estoy empeorando. Y dado que el semestre que entra voy a tener puras materias que sí me interesan, con profesores que sí me gustan y que ya he tomado clase con ellos, espero que sea menos angustiante que este primer semestre que acabé en el IIMAS.

Ayer tuve mi último examen de Análisis de Algoritmos, el correspondiente a la tarea 3 de Análisis de Algoritmos (en negritas, porque tengo que escribir acerca de ella, del examen y de la materia en general).

Al terminar le hablé a Alejandro, que estaba recluido en su casa (creo que sin bañarse) desde el viernes, y él me dijo que prefería estar en su casa chambeando. Dado que él fue el head developer por defecto del proyecto, presumí que nuestro deber era ir a apoyar; así que agarré a Alexander y fuimos a casa de Alejandro, llamándole a Iván y diciéndole que su misión si decidía aceptarla era ir también.

Lo que siguió fueron las veinte horas más pesadas que he tenido en el IIMAS, y ciertamente están en el top five de mi vida.

Estuvimos en casa de Alejandro con la firme idea de no salir hasta que saliera el proyecto o hasta que tuviéramos que ir al IIMAS a entregarlo, lo que ocurriese primero.

Varios obstáculos se interpusieron en el camino: primero, la chingadera no cabía. La Xilinx Spartan-3E que teníamos era el modelo más chafa (bueno, el segundo más chafa) de esa compañía, y nuestro proyecto era muy complejo: entonces las compuertas no alcanzaban. Los inges (principalmente Alejandro) estuvieron haciendo maromas con el código VHDL para optimizar todo lo optimizable, y viendo qué podían quitar.

Después, la FPU ya estaba, jalaba en el ModelSim, pero no servía cuando la quemábamos en la tarjeta. Tenía que ver con la frecuencia a la que jalaba la tarjeta, que era como el doble de lo que aguantaba el FPU… o algo así.

Y por último, cada quemada de todo el CPU nos tomaba cerca de 20 minutos… lo cual nos mataba el ritmo, porque no podíamos hacer nada mientras estaba compilando y quemando el CPU a la tarjeta.

Cerca de las 3 de la mañana, un gran pesimismo comenzó a apoderarse de nosotros: la cosa no quería quedar, y comenzamos a pensar en un plan B. En el peor de los casos, teníamos smiley para presentar.

Y entonces, a las 7:30 de la mañana, cada quién haciendo lo que podía con su parte (yo estaba terminando la documentación), todos madreados y ya sin muchas esperanzas, Alejandro de repente nos dijo “¡miren!”.

Y miramos.

Mandelbrot

Haciendo uso de todos los trucos del universo, y optimizando todo lo optimizable, el CPU cupo y funcionó en la tarjeta. Literalmente ocupamos todo el espacio de la tarjeta: incluso usamos una opción que tiene el XST de Xilins para utilizar los Block RAMs no utilizados en el proyecto como compuertas lógicas extras.

Uso de la tarjeta

Ya de ahí todo fue de bajada; terminamos todo lo que había que terminar, y nos tomamos la foto del triunfo:

El triunfo

Lo chido de esa foto, es que de verdad estábamos eufóricos: el pinche procesador nos había costado un huevo y la mitad del otro, y ya casi habíamos perdido la esperanza cuando por fin funcionó.

Terminamos todo el procesador. Sólo excluimos las instrucciones lógicas (and, or, xor, shl y shr), porque no cabían. Era trivial implementarlas (las operaciones están soportadas a nivel de VHDL, y Xilinx para variar sí implementó esa parte del estándar VHDL); pero no teníamos ya compuertas. Nos quedaban como dos ORs. Y un AND.

Después fue preparar la presentación (que ya fue sencillo teniendo todo), nos fuimos al IIMAS, y fuimos el primer equipo en presentar su proyecto. Fue una presentación muy padre: fuimos el único equipo que hizo ensamblador y simulador, y pudimos enseñarle a Savage dos fractales y nuestro smiley. Además, de verdad estábamos emocionados con nuestro micro, porque nos había costado un chingo. Savage incluso nos felicitó; yo ni podía creerlo.

Ya después, cada quién fue a dormir a su casa.

No sé qué calificación vaya a tener al final en esta materia; en los exámenes me fue mal. Pero creo que no importa; a este proyecto le echamos todas las ganas del universo, y la verdad nos quedó muy padre.

Aunque yo le pondría 10 a mi equipo.