Stanford MOOC Automata W1

Automata Theory At CourseraCuando comencé a explorar los diferentes cursos que Coursera ofrece, me topé con la existencia de un curso sobre teoría de autómatas impartido por el mismísimo  Jeffrey Ullman. Para los que hemos estudiado las formalidades de las ciencias de la computación, en particular lenguajes formales, diseño de compiladores, lenguajes de programación y teoría de la computación, el nombre de Jeffrey Ullman tienen una connotación y equivalencia al del padre del campo de la aplicación de la teoría de autómatas a la computación.

En aquel entonces no había más fechas abiertas para este curso, por lo que lo puse en mi “watchlist” y me concentré en otras cosas. Un par de semanas antes se su inicio, mientras andaba con mis cursos de cloud computing y de modelos de regresión, recibí el aviso de la apertura de una nueva fecha, en la segunda semana de septiembre. Una sorpresa y alegría.

He terminado de ver la primer ronda de video lecturas de este curso. Cuatro videos que no me han tomado más de dos horas verlos (a diferencia de otros de los MOOC de Coursera que he tomado en los que llegan a 18 o 20 videos). Algunos de los videos se atoraban (aunque el audio continuaba sin problema). Esta primera semana se han revisado los conceptos de alfabetos, símbolos, cadenas, lenguaje, la representación gráfica de un autómata, el modelo formal de un autómata, el automata finito determinístco (DFA), el autómata finito no determinístco (NFA), el autómata finito determinístico con ε-transiciones (ε-NFA), las equivalencias entre éstos tres y algunos comentarios a su alrededor.

Interesante dos ejemplos prácticos del uso de la teoría de autómatas. El primero es sobre el modelado de los posibles resultados en el desarrollo de un juego de tenis

Tennis scores

y el segundo sobre lo que sería el más simple protocolo de comunicaciones

Simplest communications protocol

He también concluido el primer “quiz“, que en este curso llaman “tareas” (homeworks), que resultó interesante. Ejercicios como el determinar cuál de las cadenas “10001”, “0010110”, “100011” o “010011” son aceptadas por el DFA:

ullman_dfa1

puedo hacerlos sin tener que escribir mucho. Sin embargo, me he topado con ejercicios que me recuerdan lo complicado que estas cosas pueden turnarse (no por nada Stephen Wolfram dice que por aquí hay todo un nuevo tipo de ciencia). Por ejemplo, sobre el mismo DFA, se pide determinar el número de cadenas que puede aceptar cuando su cardinalidad es 11, 12, 13 ó 14 (preguntas variables). A simple vista puede verse que cadenas de longitud 1 no son aceptadas, sólo hay dos de longitud 2, entres ninguna, en cuatro hay 2 pero a partir de 5 hay cierta recurrencia por los estados A y B (alcanzados desde D) que complican tremendamente el asunto.

Finalmente, mientras escribía esto, me he topado con algo curioso. El libro de Ullman, “Introduction to Automata Theory, Languages, and Computation” (sobre el que el mismo Ullman pide respetar los derechos de autor y no hacer descargas ilegales de la obra) fue inicialmente catalogado bajo el esquema DDC con el call number 629.8/312, que corresponde a ingeniería de automatización y control. Si bien lo que trata el libro es mucho de lo fundamental del conocimiento científico que un ingeniero en control y automatización debe saber, lo cierto es que el libro no tiene nada que ver con el asunto. Otras obras sobre teoría de autómatas han sido o son catalogadas bajo los números número 511, la decena 620 o bajo el 005. Me parece que las últimas ediciones de la DDC consideran  el tema bajo el 005.4 (por donde debe estar el tema de los compiladores)*. Si bien no está del todo errado, a mi parecer, este material (cuando es de naturaleza enteramente abstracta como es la obra de Ullman) debe ser catalogada bajo el rubro 004.0151, correspondiente a los principios matemáticos de las ciencias de la computación. El porqué estas obras han sido catalogadas bajo los números 511 (matemáticas) o 629, debe ser porque los bibliotecarios consideraron el tema como “matemático” (guiados quizás por el contenido) o relacionado con los robots (guiados por el título).

Respetando el encolamiento de otros posts, esto no será publicado hasta el día 30 de septiembre.

*La suposición se debe a que como la DDC ostenta un copyright, la organización que lo posee cobra por dar a conocer su conocimiento. Muchos de los servicios a los que recurría para poder clasificar mi blog están ya bajo accesos por los que hay que pagar y tengo aún huecos en mi conocimiento de este esquema.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s