Enseñando a una computadora a usar paint

Hace un mes, me enfrenté a un problema computacional muy interesante, que fue consecuencia de asumir que si algo lo podemos hacer fácilmente, entonces las computadoras también deberían de hacerlo con la misma dificultad. Les explico.

Un grupo de personas querían desarrollar una página que pusiera marcadores en secciones de un mapa(concretamente hablando, querían marcadores circulares lo más grande posibles en municipios de un mapa de michoacán). Imagino que fue idea de un empleado de oficina que tiene una fuerte afición a los tableros con tachuelas y a jugar en paint, porque de hecho para plantear la propuesta de este portal a los clientes mostraron una imagen de un mapa de Michoacán con puntos pintados en paint.

Alguien podría argumentar: "Pero poner puntos(o tachuelas) en un mapa es re-fácil, ¡sólo lo pones adentro del municipio y ya!". Estoy de acuerdo que para nosotros es fácil. También imagino que no le resultó difícil al que pintó el mapa en paint. Pero, ¿es fácil para una computadora?

Notemos que nosotros podemos hacer esto gracias a nuestra vista. ¿Cómo le podríamos enseñar a un ciego a dibujar puntos que caigan adentro del municipio deseado? Además, tenemos desarrollados conceptos como "adentro", o "afuera", lo entendemos sin siquiera pensar en lo que formalmente significa.

Parece que empezamos a entender por qué una computadora no sabe "poner puntitos en paint". Pero, para que quede más claro, primero tratemos de formalizar lo que significa "adentro" y "afuera".

Imaginemos que vamos en una camioneta destruyendo todo en nuestro camino, y que enfrente hay un terreno muy irregular. Supondremos que venimos de afuera del terreno. La primera vez que tiremos parte de la cerca, diremos que hemos entrado al terreno, pero cuando volvemos a tirar otra parte de la cerca, es porque salimos de él, y volvemos a empezar. Siguiendo este método podemos saber si estamos adentro o afuera del terreno con la paridad de la cantidad de veces que tiramos parte de la cerca.

¿Bonita idea no? Pues esa forma de saber si algo está adentro o afuera se le llama "Ray casting algorithm", y se puede implementar. Dejaré un link al final por si a alguien le interesa.

¡Bravo!. Ya podemos enseñarle a una computadora lo que significa "adentro" y "afuera". Pero veamos que esta idea sólo sirve para saber si algo que ya está se encuentra adentro o afuera. Alguien podría decir: "Bueno, pero pues fíjate cuándo entras y sales, mide la distancia entre esos dos puntos y listo". Y es una idea muy buena, que de hecho sí sirve, pero tiene una gran desventaja. El algoritmo es unidimensional, así que podría pasar que pases muy cerca de un borde y no te des cuenta, y si pones un marcador por ahí puede que se desborde de la orilla, o si evitas que se desborde puede que te quede muy chiquito, y nosotros buscamos poner marcadores que se puedan ver sin tanta dificultad.

Parece que ahora entendemos por qué es que las computadoras no saben usar paint. Ellas necesitan saber específicamente en dónde quieres el punto, y adentro de un municipio hay incontables puntos que puedes considerar que están adentro. Y tampoco podemos tomar puntos aleatorios, porque en primer lugar, es muy grande el conjunto de puntos posibles, y además, queremos lugares estratégicos en donde se pueda poner un marcador grandote. Además, existe otra dificultad. La computadora debería de ser capaz de poner VARIOS marcadores dentro de un mismo municipio.

¿Suena complicado no? Pensemos en el caso más simple...

Supongamos que nuestro polígono es un triángulo. Es claro que el punto ideal para poner un marcador es el incentro, con el inradio como radio. Y tenemos fórmulas que ubican exáctamente a este punto. Además, no importa qué tan irregular sea nuestro polígono(mientras sea también una curva cerrada simple), siempre podemos triangularlo. Entonces nuestro problema se reduce a buscar una "buena" triangulación.

¿Qué es una "buena" triangulación? Una que tenga triángulos con inradios grandotes. Si tenemos una triangulación con triángulos flaquitos, nuestros marcadores no se van a ver. Pues, precísamente existe una triangulación que maximiza la gordura de nuestros triángulos, llamada "Triangulación de Delaunay", ¡y es programable!(dejaré la referencia al final del artículo), sólo que hay un pequeño problema, la triangulación de Delaunay no ve aristas, sólo puntos. Es decir, puede ocurrir el siguiente caso:

Imaginemos que nuestro polígono está delimitado por la frontera roja, y la triangulación está indicada por las líneas azules. Esta no es una triangulación de nuestro polígono, ya que hay triángulos que estan tanto afuera como adentro del polígono. Pero se soluciona fácil.

Le puedes decir dónde está tu arista si pones muchos puntos muy cercanos entre sí que estén contenidos en la arista. Como es un algoritmo que evita triángulos flacos, ignorará las posibilidades que nos causan ruido de esta manera.

Por otra parte, por la misma razón de que Delaunay no ve aristas, se van a generar triángulos que están afuera de nuestro polígono irregular, pero basta con tomar los incentros de los triángulos para saber cuáles descartaremos, ya que ya tenemos un algoritmo que evalúa si un punto está adentro o está afuera.

Ahora, si los triángulos son muy poquitos, siempre podemos partir un triángulo grande en 4 triángulos chiquitos con las mismas proporciones, y podemos repetir el proceso cuantas veces se necesite para satisfacer la demanda de marcadores.

¡Bingo!, terminamos el problema. Y para cerrar con broche de oro, les dejo algunas imágenes del agoritmo corriendo en la práctica:

Aquí vemos al municipio de San Lucas con su triangulación de Delaunay. Son ignorados los puntos de los triángulos que caen fuera del municipio.

Y por último les dejo a Michoacán con todos los marcadores generados por cada municipio con la triangulación de Delaunay.

Referencias:

Ray Casting Algorithm: https://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

Triangulación de Delaunay: https://es.wikipedia.org/wiki/Triangulaci%C3%B3n_de_Delaunay

Live demos:

Ray Casting Algorithm: http://bl.ocks.org/bycoffe/5575904

Triangulación de Delaunay: http://bl.ocks.org/mbostock/4341156

Más que infinito

Recuerdo que cuando era un niño sin pista alguna de la vida, de vez en cuando tenía confrontamientos con mi hermana en la que uno decía: "Yo tengo un X", el otro contestaba: "Pues yo tengo 2", y el otro contestaba: "pues yo tengo 3", hasta que eventualmente uno decía: "Pues yo tengo infinitos" y la pelea más o menos terminaba porque nadie sabía como superar eso (entendíamos que infinito más uno no era mejor que infinito).

Como experencia personal en mi desarrollo académico como matemático considero un punto relevante el punto en el que uno consigue entender que dos cosas infinitas no necesariamente tienen el mismo "tamaño". Cuando les comento esto a mis amigos que no son matemáticos su primera reacción es de sorpresa, después de todo ¿Infinito es infinito o no? ¿Cómo es que existen infinitos más grandes que otros? Por ello he decidido compartir una demostración de que existen más números reales que números naturales y voy a intentar hacerlo de manera amena y procurando no causar muchos dolores de cabeza.

Conjuntos

Como siempre en matemáticas primero tendremos que definir algunas cosas, como este post es de divulgación haré definiciones poco rigurosas. Primero, el conjunto de números naturales son aquellos que se utilizan para contar \((1, 2, 3, 4, \ldots)\) i.e. los números no negativos sin partes fraccionarias. El conjunto de números reales son "todos los números" o los que se utilizan para medir distancias \((1, 5, 3.9, π, \ldots)\).

Tamaños

Ahora que tenemos dos conjuntos, queremos ver cuál de ellos es más grande. Pero, ¿qué significa esto matemáticamente? No es como que pongamos a los conjuntos junto al refrigerador y veamos cual llega más alto. Los matemáticos utilizamos una idea de tamaño parecida a la que usaría un coréografo o director de baile, si tienes un montón de hombres y mujeres y cuando formas parejas te sobran hombres, entonces tienes más hombres que mujeres, si te sobran mujeres entonces tienes más mujeres que hombres, si nadie sobra, entonces hay tantas mujeres como hombres (los matemáticos a esta idea le llamamos correspondencia biyectiva).

Cuando los conjuntos infinitos entran al juego, las reglas cambian un poco.  Imaginen que tenemos dos copias del conjunto de números naturales, llamémosle \(P\) y \(S\) (de primero y segundo), para hacer el ejemplo más legible al número \(1\) que vive en \(P\) le llamaremos \(1_P\), al número \(2\) le llamaremos \(2_P\), al 2 le llamaremos \(3_P\) y así sucesivamente. De manera equivalente los elementos de \(S\)  serán representados como \(1_S\), \(2_S\), \(3_S\), etc.

Hagamos la siguiente asignación de \(P\) a \(S\):

a \(1_P\) le asignamos \(2_S\),

a \(2_P\) le asignamos \(3_S\),

a \(3_P\) le asignamos \(4_S\),

...

a \(nP\) le asignamos \((n+1)_S\).

De esta manera a todos los elementos de \(P\) les asignamos a alguien de \(S\), pero no a todos los elementos de \(S\) les fue asignado un elemento de \(P\) pues el \(1_S\) se quedó sin pareja. Esto no significa que \(S\) sea más grande que \(P\), recuerden que después de todo ambos son copias del conjunto de los números naturales y por lo tanto tienen exáctamente los mismos elementos. Si aceptaramos esto como demostracíon de que \(S\) es más grande que \(P\) entonces bien podríamons invertir el papel de \(S\) y \(P\) en la asignación  y de la misma manera podríamos decir que \(P\) es más grande, lo cual intuitivamente es una contradicción. ¿Qué está pasando? Lo que es distinto en los conjuntos finitos es que si les quitas un elemento su tamaño es distinto, los conjuntos infinitos contienen subconjuntos que también son infinitos. Por ejemplo, en el caso del conjunto de los números naturales, si le quitas un elemento sigue siendo infinito, si le quitas la mitad de sus elementos, sigue siendo infinito, si de cada millón de elementos le quitas \(999999\), sigue siendo infinito. Por esta razón la asignación del ejemplo no es suficiente para probar que un conjunto es más grande que el otro, pero sí es suficiente para probar que \(P\) no es más grande que \(S\), pues usando todos los elementos de \(P\) no pudimos cubrir a todos los de \(S\). También es cierto que \(S\) no es más grande que \(P\) (basta invertir los papeles de \(P\) y \(S\) en la asignación para tener una demostración de ello). Si \(P\) no es más grande que \(S\) y \(S\) no es más grande que \(P\), la intuición nos dice que entonces deben ser del mismo tamaño (aunque ya lo sabíamos pues \(P\) y \(S\) eran copias del mismo conjunto), pero rigurosamente hablando, no podemos decir que son del mismo tamaño a menos que tengamos una correspondencia biyectiva y el teorema de Schröder-Bernstein nos dice que esto es suficiente.

Todo esto es para convencerlos de que un conjunto infinito puede tener un subcojunto que es tan grande como él. Y no solo eso, un conjunto infinito puede partirse en muchos conjuntos infinitos de tal manera que cada uno de ellos sea tan grande como el conjunto mismo. Por ejemplo, veamos que existen tantos números naturales impares como números naturales pares, para esto pensemos en la asignación que a cada número par \(2_n\) le asigna el número impar \(2n+1\). Esto es una correspondencia biyectiva, a cada número par le asignamos un número impar y cada número impar fue asignado a alǵun número par (o en otras palabras, a cada quien le tocó exáctamente una pareja), y por lo tanto hay tantos números naturales pares como impares. Ahora, veamos que existen tantos números naturales pares como números naturales. Para esto sólo pensemos en la asignación que a cada número natural \(n\) le asigna el número par \(2n\). Esto es otra correspondencia biyectiva y por lo tanto hay tantos naturales como números naturales pares. Pero también teníamos que hay tantos números naturales impares como números naturales pares, por lo tanto también hay tantos números naturales impares como números naturales. Ahora, si juntamos los números naturales pares con los números naturales impares, lo que tenemos es el conjunto de números naturales, entonces, el conjunto de números naturales se puede partir en dos conjuntos que son tan grandes como él mismo. Y esto no lo es todo, con argumentos similares podríamos partirlo en cualquier cantidad de conjuntos de tal manera que cada uno sea tan grande como los naturales, incluso lo podríamos partir en una infinidad de conjuntos de tal manera que cada uno sea tan grande como los naturales (véase la siguiente imagen)

En cada nivel horizontal hay tantos números como números naturales.

De manera parecida les pediré que me crean que en los números reales hay tantos números entre el 0 y el 1 como en el conjunto de todos los reales (Para los escépticos, vean que la función tangente toma todos los valores reales cuando la evalúan en \((-π/2, π/2)\), definan una relación con esta función, y luego vean que hay tantos números reales en \((0, 1)\) como en \((-π/2, π/2)\).

No hay tantos números naturales como números reales en (0, 1)

Por un momento supongamos que esto no es cierto. Es decir, que existe una correspondencia biyectiva entre los números naturales y los números reales entre el 0 y el 1. Eso quiere decir el natural 1 tiene asignado un número real \(r_1\) y supongamos que dicho número se ve así:

$$r_1 = 0.d_1^1d_2^1d_3^1d_4^1d_5^1d_6^1d_7^1d_8^1\ldots$$

donde \(d_n^1\) es el enésimo dígito. Muchos de estos dígitos pueden ser ceros si es que la expanción decimal del número es finita (i. e. es lo mismo 0.2 que 0.2000000000\ldots).

De manera similar, al número natural 2 tiene asignado otro número real y supongamos que dicho número se ve así:

$$r_2 = 0.d_1^2d_2^2d_3^2d_4^2d_5^2d_6^2d_7^2d_8^2\ldots$$

(noten que los superíndices ahora son 2 en vez de 1). Generalizando, el número natural \(n\) va a tener un real asignado que se va a ver como:

$$r_n = 0.d_1^nd_2^nd_3^nd_4^nd_5^nd_6^nd_7^nd_8^n\ldots$$

Ahora, construyamos un número real \(r = 0.d_1d_2d_3d_4d_5d_6d_7d_8\ldots\) de la manera siguiente:

• \(d_1\), el primer dígito de \(r\) va a ser cualquier dígito que sea distinto de 9 y que sea distinto de \(d_1^1\) (el primer dígito de \(r_1\). 
• \(d_2\), su segundo dígito, va a ser cualquier dígito que sea distinto de 9 y que sea distinto de \(d_2^2\) (el segundo dígito de \(r_2\)). 
• \(d_3\), su tercer dígito, va a ser cualquier dígito que sea distinto de 9 y que sea distinto de \(d_3^3\) (el tercer dígito de \(r_3\)). 
• \(\ldots\)
• \(d_n\), su \(n\)-ésimo dígito, va a ser distinto de 9 y distinto de \(d_n^n\) (el \(n\)-ésimo dígito de \(r_n\)).
• \(\ldots\)

Esto siempre se puede hacer, siempre tendremons al menos 8 dígitos de donde elegir. (Los nueves no nos gustan, pero no les voy a decir por qué en este post)

Veamos que \(r\) se quedó sin pareja en la asignación:

• \(r\) no puede estar asignado al número 1, pues su primer dígito es distinto que el del número que se le asignó al 1. 
• Tampoco puede estar asignado al número 2, pues su segundo dígito es distinto que el segundo dígito del número que se le asignó al 2. 
• Tampoco puede ser el tercer, pues su tercer dígito es distinto que el tercer dígito del número que se le asignó al 3. 
• \(\ldots\)
• Tampoco puede estar asignado al número \(n\), pues su \(n\)-ésimo dígito es distinto del enésimo dígito del número que se le asignó a \(n\).
• \(\ldots\) 

En otras palabras, a ningún número natural se le asignó \(n\), pero esto no es posible si la asignación era biyectiva, contradiciendo que existe una asignación biyectiva entre el conjunto de los números naturales y los números reales entre 0 y 1.

Con esto terminamos, tanto los números reales como los números naturales son infinitos. Pero el infinito de los números reales es más "grande" que el de los números naturales. Y no sólo eso, el infinito de los números reales no tiene por que ser el más grande, dado cualquier infinito, siempre podemos construir un conjunto que sea más grande (pero eso es material para otro post). Si mi hermana y yo hubieramos entendido que sí existe manera de superar "infinito" cuando éramos niños posiblemente seguiríamos peleando.

Tips de negocios para la academia

Nuestro amigo Shildkröte nos habló sobre cómo alguien con formación académica (física y matemáticas), puede desarrollarse en la industria, en particular en la ingeniería de software (artículo). Yo, por otra parte, pretendo hablarles de cómo algunas caracteristicas que usualmente se buscan más en el sector privado, nos pueden ayudar para tener un mejor futuro en la academia.

Un primer consejo es: Conoce un poco de todo, pero vuélvete experto en algo.

Empezaré con la parte de "Conoce un poco de todo":

Siglos atrás, no era raro que quien fuera estudioso de un área de la ciencia, en realidad perteneciera a varias. Es común leer en biografías de gente de los siglos XV a XIX: "TalPersona - Matemático, Físico, Astrónomo...". Como ejemplos, tenemos a Newton y Gauss, por mencionar algunos. 

A finales del siglo XIX y principios del XX, cuando nos aventuramos a estudiar el átomo, la división entre profesiones aún no era tan clara. Incluso, durante el renacimiento y la ilustración, había quien se metía también al arte (Da Vinci, por ejemplo).

Es durante tales épocas, que lograr la polimatía (ser experto en muchas cosas), era algo que a menudo se buscaba. Hoy en día, ser todólogo es una tarea bastante difícil, pero no es imposible conocer un poco de todo; más cuando ésta es una cualidad que te da muchas ventajas en la industria y el sector privado, y que, como espero convencerlos, también en la academia. 

Un ejemplo: Si eres programador, te tratarán mejor si también sabes de redes y eres un experto en linux. Pregúntenle a Soffer.

Conocer de muchas cosas es algo que también es útil en la academia; dos ejemplos me vienen a la mente: En matemáticas, si entiendes aunque sea un poco de varias ramas, puedes leer, hablar con gente, entrar a charlas de muchas áreas y entonces podrás hacer uso de distintas herramientas para atacar tu problema. En física, si además de tu área sabes, por ejemplo, programar bien y algo de análisis o geometría diferencial, ya te ganaste el corazón de varios.

En mi experiencia como físico, puedo decir que gente muy buena en la parte teórica se queda fuera de las discusiones cuando se empieza a hablar de los métodos numéricos; y, que gente muy buena en la talacha, se queda fuera cuando se habla de cosas más formales. Así que más vale conocer de todo, aunque sea un poco, para no quedarse fuera.

Otro punto importante en pro de conocer varias áreas, es que hoy en día, los posgrados y los trabajos están muy peleados. Vivimos en una época difícil, pues cada vez es más fácil tener un posgrado (irónicamente, ésto nos perjudica). Buscando becas y lugares donde te den dinero para subsistir, uno nunca sabe si al empezar estudiando teoría de juegos, se terminará haciendo machine learning (true story). Haber conocido varias cosas desde un principio, te facilitará la transición entre áreas, e incluso te abrirá más posibles ramas.

Ahora, ¿a qué me refiero con "vuélvete experto en algo"?

Al ser experto en algo, es posible volverse un líder en la ejecución de ciertas tareas y resolución de ciertos problemas; eventualmente, te vuelves una referencia obligada cuando alguien se pregunte cómo hacer eso en lo que tú eres "el experto".

En la industria lo podemos ver como: "Tal persona es el gurú de Linux", "Tal persona es quien sabe hablar con la gente", "Tal persona es quien entiende de finanzas", etc. Gente que por saber algo, se volvió una referencia. Ésto también lo vemos en la academia: "es el que hace forcing", "es el que hace gráficas", "es el que hace geometría"; al escuchar esas cosas, uno automáticamente asume que la persona en cuestión es buenísima en su área.

De primera vista, uno pudiera pensar que esto contradice mi punto anterior, pero no es así. Conocer algo no es lo mismo que ser experto en algo. Conocer cosas me brinda opciones y me permite no quedarme fuera de muchas partes del proceso de investigación; ser experto me vuelve indispensable.

El doctorado es la mejor época para volverse experto en algo. Antes del doctorado no sabes muchas cosas; después del doctorado estarás más preocupado por impartir clases, asesorar tesistas, publicar artículos y, tristemente (en especial si te quedas en México), por burocracia.

Mi segundo consejo tiene que ver con algo que le llaman Networking, que consiste, básicamente, en socializar.

En los negocios, networking es construir relaciones para compartir información/conocimiento y obtener un beneficio mutuo; es dar a conocer tu producto y darte a conocer a tí. Ésto último, sirve para buscar subir en el escalafón profesional y ganarte esa posición clave en la empresa. Para nosotros la posición clave es, según nuestro grado, un doctorado, un posdoc o una plaza de investigador.

Aunque el concepto es algo que está pensado para los negocios, no es algo que debe ser ajeno a la academia. Ser talentoso y/o trabajador podría no ser suficiente siempre. Por muy bueno que seas, por el simple hecho que habemos tantos investigando tantas cosas, es muy difícil que trasciendas si la gente no te conoce.

Por feo que suene, conozco a mucha gente buena en su área, que se ha quedado atrás sólo porque es callada y no conoce a muchas personas fuera de su núcleo más cercano de colaboradores. A su vez, se de más de un caso en que gente ha conseguido posgrado en el extranjero o posición de posdoc, sólamente por haber socializado con la gente adecuada (una disculpa si alguien se ofendió).

La plataforma ideal para networking, en nuestro caso, son los congresos. En los congresos, como Clave de Fa nos platicó en su artículo, uno puede hacer promoción a nuestra propia investigación al dar plática o presentar póster. Pero no se limita a estas actividades: los coffee breaks y los eventos sociales (como la cena de gala, si hay) son también una buena plataforma.

La física y las matemáticas son un área muy bonita, en el sentido de que los profesores e investigadores motivan a los alumnos a acercarse a ellos; a diferencia de lo que llega a pasar en otras áreas (sobre todo en las sociales), donde el profesor marca su raya y se sube a su pedestal. Nosotros podemos presumir de poder ir a comer/chelear con los profes, por lo que debemos sacarle provecho a eso.

Por ello, aunque aún no tengamos un tema de investigación, hacer preguntas es también una buena forma de darte a conocer. Incluso si otros estudiantes o profesores jóvenes te miran feo, siempre habrá algún profesor viejito, que por más impertinente que otros consideren tu pregunta, te verá como un joven entusiasta y te tendrá bien identificado (las preguntas verdadéramente tontas, déjalas para la cena, cuando se estén echando unas copitas).

En estos eventos, además de promocionar tu investigación y hacer que la gente te conozca, muchas veces salen alianzas y proyectos nuevos. Por otro lado, conoces doctorantes/posdocs con quienes puedes discutir las cosas más básicas y hacer las preguntas que te dan pena (o contestarles preguntas a ellos); además, muchas veces otros estudiantes le comparten tu investigación a su asesor. También lograrás identificar que profesor no se lleva con quién y eventualmente sacar provecho de ello (muahaha).

Así que platica con la gente, aprovecha coffee breaks y eventos sociales; si tienes charla/póster, da la mejor impresión que puedas (consejos).

Recomendaciones al saludar en los coffee breaks:

• Antes de saludar: Identifica qué hace la persona y piensa en una pregunta pequeña, no importa si es muy ingenua (pero de ninguna manera llegues diciendo: "tengo una pregunta ingenua/tonta..."). También, piensa que después de responderte, te preguntará qué haces o qué te interesa. Ten preparada una buena respuesta.
• Cuando saludes: Di tu grado actual (doctorado, posdoc) y con quién trabajas. Hazle la pregunta y espera a que te pregunten algo. No le quites mucho tiempo, 2 minutos y te vas a saludar a la siguiente persona. No te pongas nervioso.
• Por tonto que suene, usa tu badge (la cosa con tu nombre) todo el tiempo. Si todo fue bien en los 2 minutos, va a intentar acordarse de tu nombre, aún más si es extranjero. En éste último caso, si no habla español, muy probablemente querrá saber la pronunciación y entonces definitívamente se acordará de tí.
• Una vez más: no le quites mucho tiempo. Si tu duda es muy profunda, busca a su estudiante o sólo pídele una referencia. Ésto demuestra interés, pero también autonomía.

En resumen:

• Aunque no seas un experto en cada una de ellas, conoce un poco de muchas áreas: tendrás más herramientas a tu alcance y opciones de investigación; en las colaboraciones, no te quedarás fuera de las discusiones.
• Ser experto en algo te ayudará a volverte indispensable. La mejor época para volverse experto es el doctorado, conoces lo suficiente y nunca volverás a tener tanto tiempo.
• Platica con la gente, establece relaciones y da a conocer tu investigación lo más que puedas. Para este fin, aprovecha los congresos.

La industria de la Ingeniería de Software para físicos y matemáticos

Las computadoras han venido a facilitar la resolución de problemas. Desde tomar notas, enviar documentos a destinos a miles de kilómetros, hacer tus pagos, hasta un sistema de recomendaciones, métodos de identificación de personas por comportamiento, ¡Autos que se manejan solos!.

Las computadoras no resuelven ningún problema por sí solas. Es necesario que alguien les enseñe a resolverlos y para esto, primero hay que saber resolver el problema. Es ahí donde los físicos y matemáticos tienen una buena oportunidad, porque lo que hacen es resolver problemas. Durante su formación estarán resolviendo problemas por 4 ó 5 años (sin cotas estrictas) prácticamente todos los días.

El trabajo de un programador es enseñarle a una computadora como resolver un problema por medio de algoritmos. Y un algoritmo no es nada desconocido para los físicos y matemáticos. ¿Qué es una demostración sino un algoritmo? tienen un número finito de afirmaciones que te llevan de una hipótesis (input) a un resultado (output).

Obviamente, hay mejores maneras de resolver un problema que otras. Si les pido buscar "ONOMATOPEYA" en un diccionario no van a empezar a buscar palabra por palabra empezando por "A", "ABA", "ABAD", "ABAN". De la misma manera ocurre con los programas, hay mejores maneras de implementar un programa que de otras.

Un ejemplo clásico es búsqueda binaria. Imaginen que les doy un diccionario con un millón de palabras y la habilidad de llegar a la n-ésima palabra de manera instantanea. Si les pregunto por una palabra ¿Cuantas palabras tienen que consultar para llegar a la palabra que les pregunté? (podría ser que les pregunte por una palabra que no está en el diccionario).

Una solución es ir buscando palabra por palabra hasta llegar al lugar donde debería estar la palabra que están buscando. En el peor de los casos tendrían que revisar un millón de palabras sólo para darse cuenta de que no está la palabra que les pedí.

Una mejor solución, es preguntar por la palabra de en medio (la 500,000), ver si esa palabra está antes o después de la que estoy buscando y repetir esto con la primera mitad (si la palabra está antes) o la segunda mitad (si la palabra está después). De esta manera en el peor de los casos, sólo se necesitan 20 (función techo de logaritmo base dos de un millón) consultas para encontrar o dar por no existente la palabra por la que les di a buscar. (Esta solución es conocida como búsqueda binaria).

Los problemas de programación requieren diseñar estrategias eficientes, fuerza bruta siempre es una solución, pero pocas veces es una buena solución. Imaginen que cada lectura a disco duro les toma 0.1 segundos. En el caso anterior ¡Fuerza bruta utilizaría 100,000 segundos para encontrar una palabra en el peor caso (eso es más de un día)! Búsqueda binaria utlizaría 2 segundos. (Una lectura a disco duro en realidad toma mucho menos que 0.1 segundos, la intención de la exageración es que puedan comparar la eficiencia de dos distintas soluciones).

La ingeniería de software está repleta de este tipo de retos. Lamentablemente muchas escuelas
en México no le dan importancia a que los futuros desarrolladores de software aprendan a
resolver los problemas por su propia cuenta y generalmente están atenidos a que alguien
más los resuelva, empaque la solución en una librería y lo publique, lo cual consume tiempo, el recurso más valioso en una industria que evoluciona a pasos agigantados. También cabe mencionar que aquellos programadores que saben manejar un gran número de herramientas son muy valiosos (tal vez conocer la herramienta correcta te ahorre un par de días de desarrollo), pero esto requiere invertir bastante tiempo. Jugar en ambos lados, crear soluciones y conocer soluciones, es lo más conveniente.

Esta es la parte que diferencía a un programador de una persona que sabe utlizar lo que un programador hizo.

Sobre la industria del software:

• Al igual que en cualquier otra industria siempre tendrá mejores oportunidades quien pueda resolver los problemas de la mejor manera posible en el menor tiempo posible.
• Es una industria que evoluciona a pasos muy agigantados, siempre es bueno experimentar con nuevas tecnologías y mantenerse al día.
• En México generalmente las buenas oportunidades siempre implican moverse de ciudad. (Morelia tiene una industria de software en crecimiento, sin embargo aún es pequeña. Las empresas más importantes están en Guadalajara, Monterrey y el Distrito Federal). 
• El desarrollo de software mexicano es principalmente consumido por Estados Unidos y México mismo. México ha ganado un buen lugar en el mercado estadounidense frente a la India por dos razones: la zona geográfica favorece la comunicación con Estados Unidos, y México ha demostrado tener mejores desarolladores que la India (en promedio). 
• Existen muchos trabajos de freelancer, los cuales son bien pagados y uno tiene libertad de trabajar desde casa, pero sólo garantizan trabajo por temporadas cortas y requieren de mucha experiencia. Estos trabajos no son fáciles de encontrar para un principiante, hay que armar un buen portafolio para facilitar estas ofertas.
• Debido a que la mayor parte del trabajo implica estar sentado, existen varios riesgos de salud en esta industria. No es nada que no pueda contrarrestarse con un poco de ejercicio, pero hay que estar conscientes de ello.
• Una vez que uno consigue demostrar su valía es fácil encontrar buenas oportunidades o mejorar las actuales.

Sus proyectos escolares sirven como código que puede presentarse en una entrevista de trabajo, no se deshagan de él, y si es posible, súbanlo a un lugar visible (github o bitbucket por ejemplo).

Materias que les recomiendo tomar:

• Computaciones 1 y 2. (Pongan mucha atención en estructuras de datos).
• Todos los cursos de Matemáticas Discretas que puedan, en particular aquellas que incluyan Teoría de Gráficas.
• Si pueden conseguir un curso en optimización combinatoria sería muy bueno.
• Lenguajes de Programación. 
• Lenguajes Formales.
• Teoría de la Complejidad Computacional.
• Inteligencia artificial.
• Diseño y análisis de algoritmos.
• Bases de datos.
• Probabilidad.
• Teoría de números.

Sé que es una lista larga, no esperaría que los tomaran todos, pero considero que todos estos cursos contribuyen con aportaciones importantes.

Programen mucho, programar se aprende programando, es muy complicado enseñar a programar.
Se pueden dar consejos, pero la única manera en que en realidad aprenderán es cuando intenten
resolver sus propios problemas.

El inglés es fundamental y les dará ventaja en el mercado mexicano. No se diga en el extranjero.

Cosas que podrían ir aprendiendo desde ahora:

• Programación Orientada a Objetos. (bien aprendido)

1. Herencia.
2. Diferenciar miembros de instancia y estáticos. 
3. Diferenciar public, protected, private, en caso de C#, internal también. (access modfiers).
4. Diferenciar una clase de una interfaz.

• Manejar Linux propiamente, en Linux es más fácil resolver algunas tareas que en Windows, una vez que lo aprenden a hacer en Linux, encontrar la analogía en Windows será más sencillo. Siempre es mejor ser hábiles en ambos. (Recomendación personal, Ubuntu para principiantes, y Arch Linux para cuando ya no sean principiantes).
• Busquen muchos problemas y resuélvanlos.
• Aprendan a utilizar al menos unos 5 lenguajes distintos (HTML no es un lenguaje de programación, CSS tampoco).   Mi recomendación personal es: Java, C#, Javascript, Python, Ruby.
• Aprendan cosas básicas de HTML y CSS. Después de que hayan estudiado, un buen ejercicio es tomar una página no demasiado sencilla e intentar recrearla.
• Aprendan a sacar ventaja de la programación funcional, eso es algo que a los físicos y matemáticos se nos da de manera natural.

Recursos:

1. Guía de Linux para novatos, brutos y extremadamente torpes. http://www.sistemasverschae.cl/acceso/sitio/manual%20openoffice/paratorpes.pdf No se ofendan, yo no elegí el título. Es un excelente curso, lamentablemente la versión web desapareció.
2. http://www.coderbyte.com/ aquí hay muchos problemas sencillos.
3. http://www.topcoder.com aquí encontrarán muchos problemas no tan sencillos.
4. https://projecteuler.net/ aquí hay un montón de muy buenos problemas de programación para matemáticos.
5. Libro: Programming Challenges de Steven S Skiena y Miguel A. Revilla.
6. Libro: Cracking the Coding Interview de Gayle Laakmann McDowell. Este libro tiene muchos problemas de todos los niveles.

Existen muchos otros recursos interesantes, pero por el momento creo que no serviría de mucho apabullarles  con una lista aún más grande.

A la audiencia de fismat: Malú y Karina podrían darles algunos de los cursos enlistados o al menos recomendarles quien podría dárselos.

Pláticas Cortas de Matemáticas

Estimados lectores, he de contarles que tiene mucho tiempo que quiero escribir una entrada, sin embargo no venía a mi cabeza una buena idea. Sin embargo, hace unos días tuve el placer/disgusto de preparar una presentación en equipo y me di cuenta de que cada uno tiene sus propias costumbres al hablar en público.

Por otro lado, hace unos días algunos de mis más estimados cuates recibieron la noticia de que hablarán en algún congreso lo cuál me hizo pensar de nuevo en este asunto de las presentaciones. Después de meditarlo un rato decidí hacer una entrada al blog respecto a éstas.

Una primer pregunta interesantes es ¿Para qué dar charlas de matemáticas?. En mi opinión, dar una charla te hace crecer como matemático. Hace unos días un compañero me dijo que uno no entiende algo si no es capaz de explicarselo a alguien que no hace matemáticas. Yo estoy de acuerdo con él y dar pláticas de nuestro trabajo es un entrenamiento en este sentido. Por otro lado, dar una plática es lo más cercano a tener publicidad en lo que hacemos, es la manera de que te conozcan (para bien o para mal) y conocer gente. Sin el afán de ofender, diré que si eres de lo que piensa que dar pláticas sólo es para inflar tu currículo, puedes cerrar el blog y te agradezco tu visita.

Antes que nada he de decir que no me considero un experto dando charlas ni mucho menos. Además, estoy seguro de que mucho (en densidad) de los que lean esta entrada serán (o son) mejores expositores que yo. Sin embargo, sí puedo decir que tengo un poquito de experiencia dando charlas pero sobre todo, escuchando malas charlas. En este sentido, lo que escribo en esta entrada no es un montón de reglas, sino de consejos y costumbres que yo he encontrado útiles y deben ser tomados como tales, es decir, entenderé si alguno o muchos de ustedes no están de acuerdo en lo que escribo, pero si a sólo uno le sirve uno de mis consejos, me sentiré infinitamente bien. En pocas palabras, espero que algo de eso les sirva para evitar que su audiencia hable mal de ustedes al terminar su presentación.

He de decir que en esta entrada me enfocaré exclusivamente en charlas cortas, es decir de unos 20 o 30 minutos cuando mucho. Es probable que algunas de las cosas que escribo sean útiles en general, pero estoy seguro que yo mismo no estoy de acuerdo con algunos de los puntos cuando se habla de una charla de una hora (o cercano) o incluso un mini-curso de más de una sesión. También es importante mencionar que estoy pensando en charlas en congresos a los que asisten personas con formación matemática sin que necesariamente sean especialistas en un tema (el Congreso Nacional de la SMM es buen ejemplo). NO estoy pensando en clases de un curso frente a un grupo que estudia determinada materia ni nada de ese estilo, aunque de nuevo, es probable que algunos de estos puntos sean aplicables, pero también es probable que esté en contra de muchos de ellos cuando se está en la situación mencionada anteriormente.


Dividiré mis consejos en dos partes. Antes de la plática y durante la plática. 

Antes de la plática.

• Prepara la plática. Es probable que muchos matemáticos crean que es cool preparar la plática la noche anterior a la presentación.  Es importante que tengas una idea varios días (incluso semanas) antes del congreso, sobre todo, si éste es fuera de tu ciudad de origen, pues los últimos días seguramente estarás atareado con el viaje y cosas así. También conozco algunos que el último día se están esforzando por demostrar ese super teoremononón para incluirlo en la presentación. Ya hablaré del contenido más adelante, pero por ahora sólo diré que estoy en contra de eso. Normalmente escribo en papel (de hecho, tengo un cuaderno dedicado para eso) el contenido de la plática que pretendo dar mucho antes de siquiera comenzar con la presentación.
• Practica. Una vez que preparaste tu plática, practicala. Conozco matemáticos que pasan la mañana de su presentación dando su plática solos, en su cuarto de hotel. Estoy de acuerdo en que puedes parecer chiflado, pero en mi caso me da mucha seguridad además de que me sirve para medir el tiempo en el que hablaré. Si puedes, haz que tu asesor, o algún profesor al que le tengas confianza, te escuche antes de la presentación (días antes), pues ellos tienen mucha más experiencia que tú y te podrán orientar. Otra buena forma de practicar es reunirte con tus cuates (sobre todo si ellos también hablarán) y presentarse las pláticas que darán entre ustedes, a manera de ensayo general (sin mencionar que éste también es un buen pretexto para echarte unas chelitas con tus estimados).
• Descansa antes de tu plática. Esto tiene que ver con preparar con tiempo y practicar de manera adecuada, pero lo que quiero decir es que no gastes la noche anterior tratando de mejorar tu presentación. Difícilmente obtendrás una mejora sustancial y en cambio presentarse dormido puede afectar la calidad de tu presentación.
• Relájate antes de tu plática. Este punto es casi lo mismo que el anterior, pero tiene que ver con los nervios. Ve una película, una serie o incluso tómate por unas chelas la tarde (no la noche o al menos no tan noche) anterior a tu charla. Lo que sea para calmar los nervios.
• Usa Beamer, PowerPoint, Prezi o tu slide-maker favorito. Estamos en la era de las computadoras y a pesar de que una plática en pizzarrón puede ser muy amigable, es muy difícil dar de verdad una buena presentación así. Podría hacer toda una entrada acerca de las presentaciones en pizzaron contra los slides, pero por ahora sólo diré que no considero apropiado dar una platica (recuerda que estoy hablando de charlas cortas) en pizzarrón.
• No sobrecargues los slides. Ya que toqué el tema de los slides, debes recordar no poner muchas letras en ellos, es una plática: HABLA!. No tienes que escribir todo el contenido en letras, agrega mejor contenido gráfico o visual, aunque sin olvidar escribir algunas cosas que consideres importantes. Es importante también mencionar que aunque unos dibujos, unos colores y quizá una que otra animación puede parecer nais, sobrecargar de estas (animaciones sobre todo) puede hacer que la audiencia pierda el interés en el contenido de tu plática y comience a fijarse en tu presentación. Recuerdo también una presentación donde el contenido brincaba de la pantalla con cada cambio de slide pero el expositor iba y regresaba constantemente en la presentación que hizo que tanto brinco me mareara, ten cuidado con eso. En mi opinión, no hay nada más elegante que Beamer para dar una charla de matemáticas.
• Menos es mejor. No hagas demasiadas diapositivas, las mejores charlas que he visto tenían unas 10 diapositivas, cuando mucho. Recuerda usar \pause, si estás en Beamer, después de las definiciones y cosas importantes.
• No des muchas definiciones. Aquí estoy pensando en definiciones que se salgan de la cultura general, estoy seguro que casi todo mundo te va a entender si hablas de "la bola abierta de radio 1". Si das demasiadas definiciones va a llegar un momento (muy rápido) en el que sólo los expertos del área (que ya están familiarizados con las definiciones nuevas) te van a entender. Nadie quiere eso. Tampoco uses mucha notación poco estándar, recuerda que va a desaparecer con el slide de la definición; recuerda recordar (aunque sea brevemente) la definición de la notación cada que vuelva a aparecer, considera que tu audiencia, a diferencia de ti, no ha trabajado con ella por meses o semanas. También es importante simplificar la notación, no tiene que aparecer como en tu artículo (tesis); nadie va a recordar qué es $A*(G,h,_; \epsilon)_{v}$ después de dos minutos.
• Ejemplo > Teorema. Da ejemplos, de hecho, muchas veces es mejor hablar de un ejemplo que de un resultado general. Por ejemplo, si tienes un resultado para todos los grupos simples no abelianos que no es trivial para $A_5$, muchas veces es mejor hablar del resultado para $A_5$ y decir "es posible generalizar".
• No incluyas pruebas, NUNCA! Tienes poco tiempo y siempre es mejor dar un buen ejemplo que una prueba complicada. Esto es un error muy común, sobre todo si tienes una prueba que te costó mucho trabajo y quieres que todo el mundo la vea. La mitad de tu audiencia comenzará a ignorarte en el momento que digas "y la prueba va más o menos así"; quien de verdad esté interesado te puede preguntar al final de la charla.
• Evita muchos detalles técnicos. Nadie quiere ver una presentación llena de cuentas, créelo, nadie, por más que tus cuentas sean muy brillantes y haya ideas muy interesantes de fondo. Evita también las hipótesis técnicas que comúnmente son parte de la prueba y no del resultado (recuerda, no queremos ver pruebas). Es mucho mejor decir "El siguiente teorema se vale para los grupos bien portados o bonitos ..." sin específicas qué quiere decir "bonitos" o "bien portados" que dar una lista de hipótesis técnicas.
• Modifica el contenido para hacerlo más accesible. De nuevo, no tienes que dar la definición tal y como aparece en el artículo/tesis. Hazla lo más amigable posible, si alguien de verdad quiere conocer los detalles, se puede acercar a ti después.
• No tienes que hablar de trabajo propio. Esto también es un error común, sobre todo en los estudiantes (como yo) que apenas tenemos trabajos propios y queremos presumirlos a todo mundo. Tampoco tienes que hablar siempre de cosas innovadoras y de investigación profunda, la mejor plática que he visto hablaba de juguetes hechos con papel.
• Deja a la audiencia picada. Siempre es bueno mencionar un par de problemas abiertos en el área o algo del estilo, igual y consigues buenos colaboradores.

Estoy seguro que puede haber muchos más consejos y probablemente ya se les ocurrieron varios mientras leían esto, pero por ahora dejaré la lista de antes de la plática hasta ahí.

Durante la plática

• Deja que te presenten. Muchas veces, ya sea por los nervios o por que nuestra plática resultó más larga de lo que esperábamos (ver arriba) queremos empezar de inmediato. Es importante dejar que el coordinador (chairman) te presente y tomar una posición secundaria mientras lo hace, a un lado del salón o algo así y no frente a la presentación. Tu momento llegará.
• Sé educado. Organizar congresos y sesiones no es algo fácil, así que tómate tu tiempo para agradecer a los organizadores y a la audiencia por asistir.
• No te dejes intimidar por la audiencia. No importa que J. Conway esté presente en tu charla, no se la des a él. Esto te hará ver inseguro y probablemente causará que hables rápido y cometas errores. Además, si crees que es "demasiado fácil", resultará en que sólo Conway y los otros dos expertos en la sesión te entenderán y harás sentir al resto de la audiencia "poco importantes", esto puede causar un grave efecto en los estudiantes, sobre todo.
• Tampoco la intimides. Es igual de desagradable alguien que pasa la diapositiva de las definiciones diciendo "bueno, como todo esto ya lo saben". Incluso los expertos te agradecerán que revises el "material conocido".
• Motiva a la audiencia. Haz que te crean que tu trabajo es interesante, pero sin mostrar vanidad. No es una tarea fácil, pero tampoco es imposible. Por otro lado, recuerda que no siempre tienes que hablar de cosas innovadoras.
• No hagas un índice de tu plática. Estoy seguro que el 90% de las pláticas de matemáticas tienen su índice contenido en Antecedentes Históricos -> Definiciones ->Ejemplos ->Resultados->Aplicaciones (if any) -> Problemas abiertos. De modo que mencionarlo sólo te quitará tiempo y aportará muy poco a la plática.
• No leas las fórmulas. Es mucho mejor decir "esta es una cota superior para bla bla bla" que decir "el cuadrado de la varianza del número pseudo para compacto del la tía de batman..." Además, nadie te va a entender. Quien de verdad esté interesado en tanto detalle te puede preguntar después.
• Da periodos estratégicos de silencio. Si hiciste las cosas con calma, debes de tener tiempo de hacer esto. Dar periodos de silencio después de las partes importantes de tu plática hace que la audiencia se de cuenta de que es importante y le permiten digerir lo que acabas de decir/mostrar. Estos periodos no tienen que ser muy largos (5 segundos, 10 por máximo).
• Lee las caras de tu público.  No olvides que les estás hablando a un montón de personas y no a la pared o a los dos expertos del área. Leer las caras no es algo fácil pero sirve mucho para medir si estás hablando rápido, si la gente se está aburriendo, etc... esto te permite manejar mejor el ritmo de tu charla.
• Termina a tiempo. No es para nada lo mismo terminar 3 minutos antes que 3 minutos después. El siguiente expositor te lo agradecerá y así te queda tiempo para preguntas o para que la gente te de un minuto de aplausos después de tu espectacular presentación.

Sorprendentemente la entrada se hizo muy larga, así que no escribiré más. Terminaré dejando un par de enlaces interesantes:

• El blog de Terry Tao, donde habla acerca de las platicas de matemáticas.
• Un link que no recuerdo de dónde saqué, pero trata acerca de cómo hablar de material técnico en público.

Finalmente, un comic de PhD Comics:

El Método Probabilístico

Todo aquel que se haya enfrentado a problemas matemáticos más allá de los problemas de preparatoria habrá visto problemas de existencia. Es decir, se enuncia una propiedad bajo algún conjunto axiomático y se cuestiona la existencia de algún elemento con dicha propiedad.

Un ejemplo muy básico con la aritmética que todos conocemos y algunos aman es si dado un entero "x", existe otro entero "y" tal que y > x. La respuesta en este caso es que sí existe y basta con decir sea: "y = x + 1".

Estos problemas de existencia por lo regular son resueltos por construcción. Es decir, se exhibe un elemento que cumpla dicha condición (como en el ejemplo anterior, donde a partir de x, se construye y = x + 1).

En otras palabras, si se quiere demostrar que existen los unicornios rosas, siguiendo este estilo de demostraciones se debería mostrar al menos un uniocornio rosa.

Dicho esto, la pregunta que surge naturalmente es si siempre es necesario construir o mostrar un elemento que cumpla con las hipótesis que se piden para completar la demostración.

La respuesta es que no siempre es necesario. Un ejemplo también muy básico es el que da el principio del palomar (también conocido como el principio de Dirichlet). El principio dice que si se tienen n palomares, m palomas y hay más palomas que palomares (es decir m > n), entonces, si todas las palomas están en uno de estos palomares, en algún palomar hay más de una paloma.

En este ejemplo, jamás se exhibió el palomar que tiene más de una paloma para demostrar su existencia.

El método probabilístico es una generalización del principo del palomar. Lo que dice es que si algo tiene probabilidad positiva de existir, entonces existe.

Recuerdese que la probabilidad de que un evento ocurra (en el caso finito), es la cantidad de casos en el que el evento ocurre entre el número total de casos. Por ejemplo, imagine a un mono escribiendo letras al azar con una máquina de escribir. La probabilidad de que el mono escriba una "a" o una "b" es 2/26 (esta máquina de escribir no tiene "ñ"), puesto que los casos favorables son que escriba una "a" o una "b" y la cantidad total de casos son 26.

Para asentar la analogía entre el método probabilístico y el principio de Dirichlet, suponga que P representa la probabilidad de que algún palomar contenga más de una paloma. Ahora sea P1 la probabilidad de que el palomar 1 tenga más de una paloma, P2 la probabilidad de que el palomar 2 tenga más de una paloma, .. , Pn la probabilidad de que el palomar n tenga más de una paloma. Es natural que P1 + P2 + ... + Pn = P (La probabilidad de que algún palomar tenga más de una paloma es la suma de las probabilidades de que el palomar 1 tenga más de una paloma y que el palomar 2 tenga más de una paloma, etc.). Si P = 0, entonces P1 + P2 + ... + Pn = P = 0 y por lo tanto Pi = 0  para todo 1 ≤ i ≤ n  (recuérdese que las probabilidades viven en los números reales entre 0 y 1, incluyendo el 0 y el 1, donde 0 significa que el evento "nunca" ocurre y el 1 que el evento "siempre" ocurre, las comillas están ahí a propósito) Pero si P > 0, entonces P1 + P2 + ... + Pn > 0 y entonces algún Pi > 0. Entonces, dado dicho Pi, debe existir al menos una configuración de palomas en los palomares, en la que el palomar i-ésimo tiene más de una paloma.

En realidad, el problema de construir un objeto conveniente sigue presente (se construye un palomar suficientemente pequeño que contenga suficientes palomas), pero en muchas ocasiones, esto es suficiente para facilitar las demostraciones, que es lo que se busca.

A continuación, un par de ejmplos sobre para qué han sido útiles los métodos probabilísticos.

Un ejemplo entendible es, dado un conjunto finito C de enteros distintos de cero ¿Es posible encontrar un subconjunto A tal que si se suman cualesquiera dos elementos de A el resultado está afuera de A?

La respuesta es obvia y es sí. Tómese el subconjunto A que únicamente contenga a un elemento cualquiera de C y con eso es suficiente. La pregunta verdaderamente interesante es ¿Qué tan grande puede ser este subconjunto?

Utilizando el método probabilístico, Erdös demostró que siempre existe un subconjunto A con dicha propiedad que tiene estrictamente más elementos que la tercera parte de C.

Otro resultado interesante y muy importante tiene que ver con teoría de gráficas (véase este post anterior donde se habla sobre teoría de gráficas).

En teoría de gráficas se define una buena coloración como una manera de colorear los vértices de una gráfica tal que ningún par de vértices adyacentes tengan el mismo color. El número cromático de una gráfica es el número de colores más chiquito con el que se puede conseguir una buena coloración. De alguna manera, si el número cromático es grande, esto nos dice que la gráfica está muy "enredada", o que existen muchas conexiones entre los vértices que no permiten utilizar menos colores.

También se define el cuello de una gráfica como el tamaño del ciclo más chiquito que contiene. Un cuello grande, de alguna manera nos dice que la gráfica no está tan "enredada", es decir, se pueden encontrar conjuntos de vértices grandes donde ninguno está conectado con otro.

La conjetura obvia es que si el cuello de una gráfica es grande, entonces su número cromático estaba condenado a no ser muy grande (es decir, si la gráfica no está tan "enredada", entonces se necesitan relativamente pocos colores para "bien colorearla"). Lo que Erdös logró demostrar utilizando el método probabilístico es que esta conjetura es falsa y que dados dos números cualesquiera n y m, se podía encontrar una gráfica con cuello más grande que n y número cromático más grande que m.

Si alguien quiere aprender más sobre el método probabilístico, le recomiendo buscar el libro de
Noga Alon y Joel H. Spencer  titulado "The Probabilistic Method".

Y para aquellos que están estudiando en fismat, tal vez consigan que Malú les dé un curso al respecto.

Inteligencia Artificial

Las computadoras en estos días son capaces de resolver problemas cotidianos que hace tiempo requería mucho esfuerzo para las personas.

Hace mucho tiempo, la única manera de comunicar personas a larga distancia era por medio del correo,
era tardado, no era del todo confiable y movilizaba a un montón de personas para poder enviar un único mensaje, lo cuál, lo volvía muy caro.

Hoy en día, enviar un mensaje es cuestión de segundos, muchas veces más barato y las personas necesarias son una minoría comparado con las épocas de antaño.

Hacer tablas de logaritmos, polinomios, funciones particularmente importantes (cómo distribuciones normales, o transformadas de Furier que aparecen en todos lados), integrales, etc. Era tedioso, sin arte y costoso (a los que han llevado cursos en probabilidad seguramente les han hablado sobre tablitas para aproximar resultados, algunas aún las pueden encontrar al final de sus libros de estadística o cálculo). Actualmente, eso es cosa del pasado, te basta descargar una calculadora, pedirle lo que necesitas y el resto lo hacen una o varias computadoras.

Que la vida se vuelva inmensamente más sencilla gracias a las computadoras sugiere preguntarse qué alcance podría llegar a tener esto. Es obvio que un pequeño conjunto de menos de 10 computadoras, puede realizar más eficientemente el trabajo que antes realizaban centenas de personas. ¿Podría una o más computadoras reemplazar a una persona?

Pensemos en que somos no más que un conjunto de átomos interactuando con cierto "orden". Nuestro sistema nervioso no es más que una red de neuronas transmitiendo y reaccionando a un flujo de electrones. Una computadora no está lejos de simular algo así.

¿Alguien opina que existe algo que no pueda hacer una computadora? Ya pueden vender cosas, intercambiar acciones, identificar personas, manejar automóviles, comunicarse. Posiblemente google o facebook saben más de tí que tú mismo.

La respuesta cotidiana es que una computadora no puede amar. Pero eso se arregla fácil

function Amor()
{
    return true;
}

Listo. ¿Alguien tiene alguna queja?

Para más de una persona las computadoras se han vuelto una parte indispensable de nuestras vidas. Muchos estudiamos, trabajamos y nos entretenemos con computadoras.

El término "artificial" es difícil de describir, pero supongamos que es contrario al termino "dado naturalmente", donde "dado naturalmente" significa que no necesitó un humano para aparecer (esta es la parte complicada, al parecer, sólo los humanos pueden hacer cosas artificiales). 

El término "inteligencia" es igual de complicado, pero si no les molesta, diré que "inteligencia" es la capacidad de reconocer patrones. Hay quienes dicen que "inteligencia" es la capacidad de resolver problemas, pero como matemático puedo decir que me he encontrado con cosas que necesitan de mucha "inteligencia" y realmente a nadie le han resuelto un problema. Hay problemas que no se sabe como resolver, pero han involucrado mucha gente para poder decir que ese problema ya existía desde antes pero con distintas palabras (es decir, reconocer el patrón). Así que concidero que mi definición de "inteligencia" me tiene mejor satisfecho y espero que también a ustedes.

Con esto dicho, "inteligencia artificial" significaría algo como "crear la capacidad de reconocer patrones" donde "crear" debe entenderse como "por un humano".

Supongamos que queremos una computadora invencible en gato (tres en linea o tic tac toe). Para empezar, el número de juegos posibles (patrones) que hay que recordar es muy chiquito para una computadora, es menor que 9! = 362880. Y la computadora, sabiendo todos los juegos posibles, puede elegir uno por el cuál no pierda, todo el tiempo (no existe estrategia estrictamente ganadora en tic tac toe, pero sí estrategia de empate). No existirá humano capaz de derrotar a este algoritmo. Y por lo tanto, esta computadora será al menos tan inteligente como una persona a la hora de jugar gato.

El problema es que existen una infinidad (una infinidad bastante grande) de patrones. Una computadora de hoy en día podría reconocer tan solo una cantidad finita de patrones (pues sus memorias son finitas), y si es capaz de reproducirse, a lo mucho una cantidad numerable de patrones. Para quien no entienda el término numerable, numerable significa tan infinito como los números enteros (para quien no entienda el por qué de la comparación, la razón es que existen infinitos más "grandes" y del que estamos hablando aquí es del infinito más "pequeñito"). Pero eso no tiene por qué desalentarnos, la cantidad de personas que existirán son finitas, cada una con tiempo finito de vida y a lo más reconocerán una cantidad finita de patrones.

Hasta ahora, se han creado "inteligencias artificiales" capaces de resolver problemas muy particulares, como manejar autos, jugar ajedrez, no dejarte ganar (o al menos no fácil) en los videojuegos, adivinar si una película te gustará o no antes de verla (imdb), mostrarte lo que posiblemente quieres ver (google), decirte quienes son muy posiblemente tus amigos de la infancia de los que ni siquiera te acuerdas o quien podría ser un buen amigo tuyo (facebook). Cabe destacar que muchas de estas tareas, las computadoras lo resuelven mucho mejor de lo que lo haría una persona (donde el "mucho mejor" ha sido dicho según los estándares de algunas personas).

Crear una máquina capaz de hacer todo lo que un humano implicaría que esta máquina también debería poder crear máquinas capaces de hacer todo lo que un humano. En caso de que así suceda, no podríamos refutar la teoría de que nosotros mismos somos una "inteligencia artificial" creada por alguien más.

Para aquellos que quieran entender más a fondo los problemas de la inteligencia artificial, les recomiendo
los cursos "Machine Learning" con Andrew Ng y "Artificial Intelligence" con Sebastian Thrun y Peter Norvig (el primer curso de coursera, el segundo de udacity). La inteligencia artificial que encontrarán utiliza mucho sobre Cálculo en Varias Variables, Probabilidad, Estadística y necesitarán de saber programar un poco si quieren entender mejor.

Para aquellos a quien sólo les fascina soñar con inteligencia artificial les recomiendo los siguientes libros:
-"The last answer" de Isaac Asimov (les toma una o dos horas leerlo y lo encuentran en internet fácilmente).
-"The robot series" (son varios libros que afortunadamente duran más de una hora leer) de Isaac Asimov también.
-"The foundation series" (también son varios libros) de Isaac Asimov también.
-"Do androids dream of electric sheep?" de Philip Kindred Dick.