martes, 15 de julio de 2008

"Hello World!" en una máquina de Turing


Hello World as a Turing machine.
Extraído desde aquí.
Algo básico: Cómo una máquina de Turing escribiría la típica frasecita: "Hello World!"
Un ejemplo Kokito para empezar a entender lo que es Máquinas de Turing

Turing-Machine


State   Read      Write     Step    Next state
------------------------------------------------
1 empty H > 2
2 empty e > 3
3 empty l > 4
4 empty l > 5
5 empty o > 6
6 empty blank > 7
7 empty W > 8
8 empty o > 9
9 empty r > 10
10 empty l > 11
11 empty d > 12
12 empty ! > STOP

Y para alivianar un poco las cosas... el "Hello World!" en Java :)
Hello World! en Java

class HelloWorld{
public static void main( String args[] ){
System.out.println( "Hello World!" );
}
}

// Todo siempre desde aquí: "Hello World!" en 366+ Lenguajes de programación.

lunes, 14 de julio de 2008

TSP en procesamiento paralelo


TSP es el típico problema en grafos: Travel salesman problem, o el problema del agente viajero.
En un computador tradicional:
La típica solución exhaustiva, es, probar todos los nodos contra todos los nodos (ciudades).
Si se tienen N ciudades, se tienen N*(N-1)*...4*3*2 probabilidades de rutas, de las cuales, en la exhaustiva, se encuentra la respuesta óptima.
La típica solución usando algoritmos genéticos, es hacer que el fenotipo contenga una ruta, y la función fitness sea la menor distancia posible... ahí, aplicar mutación y cruzamiento, etc...

En un computador paralelo, si no me equivoco, podríamos hacer esto:
Hacer que cada nodo-procesador represente una ciudad;
A continuación, cada uno calcule la distancia al resto de ciudades [O(n) para cada procesador]
Cada uno calcule la menor distancia a otra ciudad (Como el pár más próximo, pero con una sola ciudad)
Mandar esa solución al nodo-procesador principal;
Ahí verifica las mejores puntuaciones, las repetidas las almacena; las otras, las manda a corregir.
Y así así, hasta que acabe...
Complejidad total: O(n*log(n) )

Parece sencillo, no?
Corríjanme si me equivoco :)

domingo, 13 de julio de 2008

LaTeX para Web/Blogger


Este blog está hecho para publicar algoritmos, investigaciones, y proyectos que desarrollé en la universidad, o que actualmente hago...
Pero es un poco difícil manejar el lenguaje matemático en la web...
Navegando por internet, encontré que en servalx plantean 2 soluciones (desde aquí):

Opción 1: Un editor on-line de LaTeX, aquí en rogercortesi.
La fórmula te la da en formato de imagen (pero no conviene al usar muchas fórmulas = muchas imágenes)
Opción 2: Acoplar LaTeX en el editor de Blogger (La explicación completa en inglés, está aquí)
Para esto, según voy entendiendo va así:
2.1. Necesitas tener Firefox instalado.
2.2. Necesitas tener instalado el greasemonkey (un script para editar HTML de la página cargada desde firefox)
2.3. Debes ejecutar éste script (se carga automáticamente)
2.4. Debes modificar el CSS de tu blog para que las ecuaciones no tengan bordes/marco.
Añade éste código:
img.latex_eq {
padding: 0;
margin: 0;
border: 0;
}

Justo antes de la línea ]]>
Eso es todo... Necesitas conocer LaTeX y escribir tu fórmula con $$ al inicio y también con $$ al final, y escribir sobre fondo blanco (por estética para la fórmula).
Un ejemplo: escribe ésta fórmula:

$$\pi = \int_{0}^{1} \frac{4}{1+x^{2}}$$

Y luego dale clic al botón en la barra de edición de blogger.
Y obtendrás:

Un breve y muy buen manual de LaTeX aquí.

sábado, 12 de julio de 2008

Algoritmo de un AFD genérico


Este algoritmo fue desarrollado para un curso de tercer ciclo: Teoría de la Computación.
Consiste en, hacer un algoritmo que reciba como entradas un autómata, y una palabra;
y que devuelva como resultado, si la palabra es reconocida o no por el autómata.
Es decir:

Algoritmo:
Autómata finito determinista general para reconocer palabras

Entrada:
- AFD como 5-tupla: donde:
  • es el Conjunto de Estados/Variables
  • es el Alfabeto
  • es la función de transición
  • es el estado inicial
  • es el Conjunto de estados finales
- palabra a evaluar.

Salida:
- Valor booleano que determina si la palabra evaluada pertenece al AFD.

Proceso:
1. Hacer la lectura del AFD
  • Leer : estado inicial // representado por un número
  • Leer : Conjunto de estados // representado por un arreglo de números
  • Leer : vocabulario // representado por un arreglo de caracteres
    que pertenecen a
  • Dados los tamaños de y de ,
    crear una matriz de tamaño
    para representar/almacenar las transiciones
    rellenando con en donde no hay transición
  • Leer : Conjunto de estados finales
2. Leer palabra a evaluar.

3. Analizar la palabra:
Tenemos el estado actual/temporal (el cual evalúa según momento)
Tenemos el valor booleano
Para cada caracter , mientras no termine la palabra:

si y

sino
error: palabra no reconocida


Comentarios adicionales:
1. En aquella época no sabía manejar GUIs, por eso la precariedad del programa.
Ahora se vería más bonito e interesante con un creador gráfico de estados y transiciones:


2. Me quedaba la duda de: siempre S0 será el estado inicial? (Y así, omitir el paso 1.1. del algoritmo)
3. Imágenes, cortesía de Wikipedia