Algoritmos probabilistas

Las últimas prácticas de Análisis de algoritmos ( :'( ), esta vez es otro tipo de algoritmos, aquellos que emplean en azar para resolver el problema que se les asignó. A estos se les llama probabilistas y según la Wikipedia en español, hay de tres tipos; mismos tipos que nos tocó ejemplificar mediante algunos algoritmos conocidos empleando POO (lo cual es un poco difícil para ejemplos tan sencillos), son los siguientes:
Integración de Monte Carlo
Apelando al hecho de que una integral es la sumatoria de la infinidad de resultados de evaluar una función en un intervalo dado, se toman puntos de evaluación aleatorios dentro de ese intervalo dado, se evalúan y se van acumulando para luego realizarles un ajuste matemático, les diría que lo buscaran en Wikipedia, pero este documento me resultó especialmente revelador.

Para el caso de la implementación de POO lo que se consideró fue la creación de dos clases Random y Funcion, la primera para generar números aleatorios y la segunda para evaluar la función.

Aproximación a π
Para este caso se toma un cuarto de círculo de radio = 1, y se lanzan n dardos hacia él de esos n dardos supongamos que m aciertan en él entonces mediante matemágia, podemos encontrar que  π ≈ 4 * m / n

Para (mal) aplicar la POO, existe una clase que hace uso de Random, la clase definida en el ejericio anterior y de otra, llamada Aproximación en la cual se realiza la simulación de los dardos

Comprobación de primalidad (Algoritmo Monte Carlo)
Existe un test de primalidad, inventado por Fermat que nos dice que si tomamos la siguiente frómula a^(n-1) % n para cualquier número a ∈ [1,n-1] y si el resultado de eso es distinto de 1 entonces sabemos que n no es primo. Tomando una gran cantidad de números con valores aleatorios para a ∈ [1,n-1] podríamos asegurar con cierta probabilidad si un número n es primo. Si el test falla, es decir el resultado para cualquiera a es distinto de 1 podemos asegurar que n no es primo.

Resolución del problema de las N reinas (Algoritmo Las Vegas)
El ya conocidísimo problema delas N reinas también se puede resolver mediante probabilidad, es decir, tomamos la columna 1 y colocamos la primera reina, después para la segunda columna tratamos de colocar la siguiente reina en una posición elegida aleatoriamente, si se logró, continuamos con la siguiente columna, y así hasta colocar las N reinas o no poder colocar una, en ese caso falla.
Bastante simple.
Las primeras dos corresponden a la práctica 5, implementada en C++, y la segundas están implementadas en C#, con interfaz gráfica para Windows Phone 8 en XAML. El código, en analizando-algo.

¡Saludos!
@fferegrino :)

Todos pueden aprender ciencias computacionales

Hace mucho me surgió el deseo de ser maestro de esta área que tanto me agrada, enseñar lo que sé sobre programación, algoritmos, estructuras de datos y demás. Sé que voy por el camino correcto puesto que entre mis planes está el hacer una maestría y buscar regresar a alguna de esas escuelas que me formaron  pero esta vez como maestro, pero por mientras quisiera comenzar haciendo algo que, aunque sencillo y pequeño, ayude a acercar a más niños (y también no tan niños) a las ciencias computacionales.

Buscando en internet encontré varios proyectos interesantes que tratan precisamente de eso, acercar el conocimiento a la mayor cantidad de gente posible, entre ellos está el proyecto de Code.org (http://code.org/), la Computer Science Education Week (http://csedweek.org/) y el último, que me parece el más interesante para lo que quiero hacer: Computer Science Unplugged (http://csunplugged.org/).

Este útlimo es programa de enseñanza diseñado específicamente para nivel primaria, de tal manera que el aprendizaje se lleve a cabo mediante juegos y actividades que resulten entretenidas para los niños, sin embargo creo que también se podría usar para cualquier persona que no esté involucrada para nada en el ambiente de la computación.

Por lo pronto veré la posibilidad de usar como guía el programa de Computer Science Unplugged para impartir un curso cerca de donde vivo, espero que se pueda hacer y contarles cómo me fue.

Enseñando también se aprende.

¡Saludos!
@fferegrino :)

Codificación voraz de Huffman

La codificación Huffman es un algoritmo usado para la compresión de datos. Dicho algoritmo hace uso de una tabla de códigos para escribir un determinado símbolo, donde la tabla ha sido rellenada basándose en la probabilidad estimada de aparición de cada símbolo. A cada símbolo le corresponde un código (secuencia de 1 y 0) de longitud variable, puesto que los símbolos cuya aparición es menos frecuente reciben códigos más largos, mientras que los que aparecen más reciben códigos más cortos.

Para la ESCOM, el trabajo fue hacer la implementación voraz de dicho algoritmo, la cual tiene como variante que la comstrucción de la tabla de códigos es distinta para cada archivo, tomando solo en cuenta los símbolos contenidos en él y la cantidad de veces que aparecen.

He de decir que es de las prácticas más pesadas que he tenido en todo lo que llevo en la escuela, dentro del programa se hace uso de recursividad, operaciones a nivel de bits y estructuras de datos a más no poder:
  • Se usa una lista para para ir almacenando las frecuencias de cada caracter
  • Se usa un arreglo de árboles para generar el árbol único de códificación
  • Se usa una cola para obtener el código asignado a cada símbolo

El código, que se encuentra en el proyecto analizando-algo en GitHub, está muy comentado tratando de hacerlo lo más entendible posible. 

¡Saludos!
@fferegrino :)