Alpha's Manifesto

A black and white figure's thought-hive

Udacity

Otra iniciativa más de enseñanza online

Me encontré como noticia en ALT 1040 que Sebastian Thrun dejó Stanford para comenzar su propia iniciativa de enseñanza online, llamada Udacity. En este preciso momento se están enseñando sólo dos cursos: Cómo construir un auto que se maneja solo y Cómo construir un motor de búsqueda. Ambos están dados por Thrun y el del motor de búsqueda está también asociado con David Evans.

Se vienen nuevos cursos durante este año, que también parecen ser muy interesantes, como Sistemas Operativos, Sistemas Distribuidos, Redes, Seguridad, Algoritmos y estructura de datos, Prácticas de Ingeniería de Software, Construir aplicaciones web, etc. Nombré los cursos que están nombrados en la página al día de hoy, pero quién sabe qué traerá el futuro. Parece que por hoy está teniendo mucho éxito.

Soy un zorrinito estudioso.

Link del día: Damn Cool Algorithms

Hoy mismo me crucé con un post de la serie de Damn Cool Algorithms, una serie de posts del blog de Nick Johnsonz, en donde explica determinados algoritmos de forma relativamente simple. Hace falta conocimiento técnico, pero aún así los simplifica lo suficiente como para que sean entendibles. Y son realmente útiles, son de mucha utilidad y además, en cierta forma, bonitos.

Soy un zorrinito algorítmico.

Link del día: Interrelacionando datos

Para quienes es sólo una palabra difícil, interpolación significa en el ámbito de funciones matemáticas, calcular valores aproximados de datos que no tenemos realmente. Esto se lleva al punto en donde para interpolar, podemos calcular una fórmula que rige los valores con los que estamos trabajando. Cuando estas funciones realmente predicen los datos con los que estamos trabajando, logramos obtener la “regla” por la que estos valores se guían.

Y esto es interesante cuando tenemos un conjunto de valores y luego tenemos que predecir su comportamiento en el futuro. Más que nada, en casos de la vida cotidiana. ¿A qué hora estará peor el tránsito? ¿Cuántas llamadas voy a recibir en cada momento del día?

Eureqa es un software que nos permite hacer este trabajo. Tomando un conjunto de datos y permitiéndonos cierto margen de error (muchos algoritmos de interpolación los permiten) nos permite identificar con cierta exactitud una fórmula que describa el comportamiento de nuestros datos. Se hace generando distintos bloques de operaciones aritméticas que den lugar a un resultado más o menos cercano a nuestro conjunto de datos. Personalmente no reconozco si este es un algoritmo de interpolación en particular, o sólo se trata de un algoritmo de búsqueda (en pocas palabras: prueba y error).

Muy relacionado, quiero dejar un link a Google Correlate, uno de los productos de Google que ahora se encuentran en sus laboratorios, que básicamente nos devuelve cuáles son las búsquedas más íntimamente relacionadas en cuanto a números con una búsqueda que a nosotros nos interese. Como extra, nos permite loggearnos y relacionar nuestro propio conjunto de datos con los que ellos tienen de sus búsqueda. O mejor aún, podemos dibujar nuestro propio gráfico y saber qué búsquedas tuvieron esa característica de interés (por ejemplo, una curva creciente y luego decreciente, algo que a la gente ya le aburrió).

Soy un zorrinito de datos relacionados.

Link del día: Visualizar las estructuras

Los trabajadores de la informática tienen muy asimilados estos conceptos: pilas, colas, árboles, el camino más corto, ordenamiento, algoritmo, grafo, etc. Todos estos conceptos los hemos ido aprendiendo de una forma u otra, pero al momento de aplicarlos es cuando realmente se prueba nuestro aprendizaje. Personalmente creo que ningún aprendizaje está completo sin una buena visualización de la materia, y es aquí en donde, para las estructuras de datos, hay que inventar algo.

Seguramente lo mismo pensó David Galles, quién desarrolló  un software en Java que nos permite visualizar el funcionamiento de estas estructuras. Data Structure Visualizations es el nombre que le otorgó, pero la historia no se queda ahí, sino que HTML5 hizo su entrada y ahora también tenemos la versión web. Denle una mirada, no sólo es interesante, sino entretenido.

Recuerdan La Belleza de Los Algoritmos? Creo que este link calificaba totalmente para estar en ese listado.

Soy un zorrinito estructurado.

Link del día: El algoritmo del Kinect

Si es que han visto demos, publicidades, o han jugado personalmente con el Kinect, probablemente se habrán dado cuenta que tiene mucho trabajo volcado en ese producto, y mucha tecnología novedosa sobre la forma en la que se pueden reconocer los cuerpos, las caras y los movimientos. Simplemente, una forma que resultó ser viable de utilizar el reconocimiento de gestos de una forma muy amplia.

Hace no mucho tiempo Microsoft reveló públicamente el algoritmo que utiliza Kinect para hacer estos reconocimientos. Toda esa información está presente en un paper publicado bajo el nombre de Real-Time Human Pose Recognition in Parts from Single Depth Images. El paper es bastante conciso y no muy largo, pero claro, hay que tener ciertos conocimientos de probabilidad, grafos y procesamiento de imágenes para poder apreciarlo en su totalidad.

Siendo esto público ahora, ¿quién de nosotros será el próximo en armar su aplicación Kinect-like?

Soy un zorrinito en movimiento.

Link del día: La belleza de los algoritmos

Sí, ya sé que suena demasiado geek, pero cualquiera que pueda abtraerse un poco del algoritmo en sí, de qué haga o cómo lo haga verá que de alguna forma su “orden” logra un algo extra que puede ser realmente hermoso.

Demostraciones tenemos miles, y la primera que encontré fue una comparación hecha sobre algoritmos de ordenamiento si es que generaran sonido. Su visualización gráfica también es atractiva. Pueden visitarlos en Sorting Algorithms: quite boring until you add sound effects, pero aquí tenemos otra bonita demostración gráfica del heapsort, quicksort, y radio del dígito más significativo.

Pero no todos son algoritmos de ordenamiento. También tenemos fractales, como la serpiente de Serpinski, un tetris-fractal. O por qué no, algoritmos genéticos, o usados para hacer arte, que es de todos modos muy hermoso.

Los dejo con el mejor de los ejemplos para mi gusto, que es la demostración de utilizar un algoritmo procedural para la creación de un paisaje nocturno. Vale la pena ver todo el video con toda la evolución del proceso: Pixel City.

Soy un zorrinito algorítmico.

Link del día: El castor ocupado

Para quién no lo sabe, una Máquina de Turing es una máquina conceptual que consta de una “cabeza” sobre una “cinta” que puede moverse a izquierda o derecha, y leer o escribir. Se supone que con esas cuatro operaciones básicas, la máquina conceptual de Turing es capaz de realizar cualquier algoritmo computable existente. Sí, desde sumar dos números hasta calcular los dígitos de π. Desde revertir una cadena de texto hasta ser un servidor web (aunque lo veo como poco eficiente para eso). Para diagramar los algoritmos que ejecutan, se utilizan estados sobre los pasos que están ejecutando, y lo que se puede leer o escribir trata de un alfabeto en particular (es decir, algún conjunto de símbolos que se le llama alfabeto de esa máquina).

Lejos de ser una metáfora a la publicidades de pasta dental, el Castor Ocupado es un algoritmo para máquinas de Turing que, dada una cantidad de estados y una cantidad de elementos de alfabeto, debe correr tanto tiempo como sea posible para luego detenerse. ¿Qué significa esto en términos de computabilidad? Significa que debe de ser, bajo una cantidad limitada de condiciones, el algoritmo más largo no-infinito, lo cual, de alguna forma es un desafío para encontrar aquello que tome más tiempo de computación y no sea interminable.

¿La razón? No es pura búsqueda por el buscar como muchos pueden suponer (y como muchos lo buscan, por simple diversión), sino que detrás de esto existe la teoría de la computación, en cuanto a qué algoritmos son computables (por ejemplo, parece que los que se encuentran sí, pero el algoritmo para encontrarlos no), qué orden de computación tienen, y seguramente también se relaciona con el tipo de problemas que son computables y no computables, pero dejaré eso para el futuro.

Hubo alguien más, Peteris Krumins, que le encontró una veta artística. Por un lado, hay un video en Youtube de una máquina de Turing (construida) corriendo el castor ocupado, y por otro lado, Peteris mismo hizo un programita que va dejando un archivo con el estado de la cinta a medida que la máquina va ejecutando, y de ahí, generar una imagen en donde se vea gráficamente. En su blog, en el artículo del Problema del Castor Ocupado,  habla de los algoritmos y los resultados que obtuvo ejecutándolos. Curiosas las imágenes, e impresionante la imagen de 5 estados y2 símbolos, para verla completa hace falta una bueeeeeeeena pantalla.

Soy un zorrinito ocupado.