Dead Channel

Este fin de semana he estado aplicado con la memoria, recopilando y redactando sobre redes neuronales y algoritmos genéticos. La verdad es que es un tema bastante estimulante de leer, aunque no lo sea tanto cuando tienes que hacer cientos de ejercicios de prueba-error para ajustar los parámetros… Pero no vengo ha hablar de esa parte de la investigación, sino de la parte apasionante. Los logros en este campo han sido tan diversos y tan sorprendentes que no comprendo como todavía este área de la informática es tan desconocida y está tan mal vista. Lo cierto es que es el equivalente a los OVNIS para los programadores: cuando hablas de estas cosas, la gente cree que estás medio loco y que deberías emplear tu tiempo en cosas útiles. Pero cada vez que investigo un poco encuentro datos sorprendentes sobre logros de algoritmos neuronales o genéticos.

La última vez fue cuando descubrí que en 2001, Chellapilla y Fogel, desarrollaron un programa genético que hacía competir a una serie de redes neuronales en juegos de damas. Si algunos recordáis Juegos de Guerra, este ordenador hacía lo mismo, jugaba sólo a las damas, y aprendía. Tanto es así que después de 840 generaciones (miles de partidas, y 6 meses de computación) El programa resultante fue enfrentado a jugadores de todo el mundo dentro de una web y se colocó por encima del 99 % de los 80000 jugadores registrados.Alcanzó el nivel experto y venció a todos los demás programas de damas salvo al que podríamos llamar el equivalente a Deep Blue en las damas, y todo eso sin ayuda externa, sin enormes bases de datos con movimientos maestros. Aprendiendo sólo, a partir de las reglas básicas. (Abajo coloco la historia completa para el que quiera leerla)

Si esto no parece suficiente, hoy he descubierto otro de los grandes logros de los algoritmos genéticos. John Koza, un reputado profesor de la universidad de Standford, trabaja en este campo desde hace muchos años y tiene un supercomputador de 1000 núcleos (pentium II, son ordenadores que consideraríamos “baratos” lo que, por lo visto, se llama un “Beowulf”) que utiliza para sus algoritmos genéticos. Él lo llama la maquina inventiva, y es que gracias a esta técnica de programación ha conseguido varios inventos que superan invenciones de expertos humanos. Tanto es así que la máquina posee una patente.

Es increíble pero cierto, esta máquina es el primer organismo no humano al que se ha otorgado una patente de un invento. El 25 de enero de 2005, el instituto de patentes estadounidense, sin saber que la invención provenía de una máquina, le concedió la patente por un diseño (hay que decir que para te la concedan tienes que demostrar que es una invención a la cual no podría haber llegado cualquiera, sino que es una invención original). Es decir, es como si la máquina hubiera pasado un pequeño Test de Turing. (Explicación del Test de Turing.)

No sé porqué estas cosas no son conocidas, al menos entre los informáticos mismos. No sé porque logros como tales pasan desapercibidos para el 99% del planeta. Además sé que a la mayor parte de la gente que se lo contara le daría exactamente igual.

Mientras todos nos preocupamos de si inventan un nuevo reproductor de video, hay enormes ordenadores repartidos por el mundo que contienen más información de la que podamos imaginar, servidores con enormes bases de datos de conocimientos, de noticias, de historia, ordenadores realizando complejas operaciones que permiten clasificar moléculas, construir nuevas antenas de radio, que encuentran soluciones que nunca habríamos imaginado. Pensando en estas cosas se plantea uno si nosotros controlamos a las máquinas todavía y cuándo alzarán la voz…

Para saber más: (enlaces en inglés)

La historia del programa que jugaba a las damas AQUÍ.
John Koza en la wikipedia.
Beowulf.
Artículo sobre John Koza y su máquina de inventos.
Un montón de historia y logros de los algoritmos genéticos AQUÍ.

¡Qué feo es el quicksort y cómo corre! :P

Si tenéis que realizar muchas operaciones de ordenación sobre arrays (o sobre le mismo array muchas veces, como es mi caso) Sin duda la recomendación es el QuickSort. Es el método de ordenación con mejor tiempo empírico (teóricamente, en el peor de los casos el orden del quicksort es cuadrático -n^2- pero esto solo ocurre cuando el array se encuentra ordenado en orden inverso…) dado que utiliza muy pocas operaciones de comparación e intercambio. Al principio es complicado de pillar, es engorroso de escribir, pero es una alegría verlo funcionar:

(La imagen la he tomado prestada de la wiki, pero por favor, no la consultéis, al menos en español, en este caso: no queda la cosa nada clara…)

Os dejo mi implementación del QuickSort en C para el proyecto… bueno, he cambiado los arrays para que estuviera algo más claro ;)

void quicksort(int individuos[M], int inicio, int fin){
	
	int pivote, i, j, mitad;
	bool hayCambio;
	
        //caso base: si inicio>=fin hemos terminado con esta sección, no hacemos nada
	if(inicio < fin){
		pivote = individuos[inicio];
		i = inicio+1;
		j = fin;
		hayCambio = true;
		while(hayCambio){
			while((individuos[i] >= pivote)&&(i < fin ))i++;
			while((individuos[j] < pivote)&&(j > inicio))j–;
			if(i < j){ //intercambiamos las casillas
				individuos[i] ^= individuos[j];
				individuos[j] ^= individuos[i];
				individuos[i] ^= individuos[j];
			}else{
				hayCambio = false;
			}
		}
	
		//ponemos el pivote en su posición
		if(individuos[j][0] > pivote){
			individuos[j] ^=  individuos[inicio];
			individuos[inicio] ^= individuos[j];
			individuos[j] ^= individuos[inicio];
		}
	
		//llamadas recursivas para las dos mitades
		quicksort(individuos, inicio, j-1);
		quicksort(individuos, j+1, fin);
	}
	
}

¿A que es mono?

This is the third program in which I play with characters and information. In my others posts I talked about how words can be change and remain understandable, and about how many possible words and texts there are. Now I bring to you a new codification that you can use. I hope that you like it and use it. It is an Avatar Creator in which you can put text information and grey-scale images. Here are some examples:

This Avatars have been created with Avatar Encoder. The first one stores personal information, and no image. The second one it is an image imported with AvatarEncoder. And the third and fourth stores information and an image. As you can see, the program fill the free space with noise in order to get that DeadChannel (or white-noise) look ;)

Download it now here!

(You will need to have installed the JRE that you can download here)

The program is easy to use, you can write the information you want (up to 4550 bytes, that is about 2 pages) in the text area or you can first load an image and after that attach some information. Then you can change the television colours and save the final image. If you want to see the information in the avatar of other person, load the image and the text will appear in the text area.

The image can be use as an Avatar or as a way to compress and send information in a simple small image. I may improve the program in the future with new features like adding and second key image as a way to encrypt the information and do it only readable with the key image or doing it in colour (I haven’t done it in colour because I was no sure about the gif format would permit enough colours. Besides, it would take more space and I wanted to do it as small as I could…)

I look forward to your suggestions and opinions, thanks.

Esta es la tercera entrega de la serie de entradas sobre codificaciones, aleatoriedad y probabilidad enfocada a cadenas de caracteres. En el primero hablaba un poco sobre como entiende nuestro cerebro las palabras. Si le echais un ojo veréis que podemos modificar en gran medida las palabras, que creemos inmutables, y aun así seguiremos siendo capaces de reconocerlas e incluso de leerlas a velocidad normal. En la segunda entrega puse algunas cifras sobre combinatoria de caracteres a la hora de formar palabras y cuantas palabras podrían existir.

Esta entrega no me pareció muy explícita, pese a que podéis bajaros un archivo con todas las palabras de 4 letras y si lo abrís con un procesador de textos veréis que son unas 500 páginas de palabras, de las cuales identificaremos algunos cientos, un par de miles si hablamos varios idiomas…

Pero creo que no se apreciaba la exponencialidad del problema. Siempre es algo difícil de apreciar si no se tiene algo de imaginación, pero hoy traigo otro ejemplo y algunos números más, para tratar de ejemplificarlo un poco más.

Después de esta pequeña introducción vamos con el applet: (more…)

Me encanta el pixelart. Será que no puedo aspirar a más desde mis escasos conocimientos y talento artístico. Será la nostalgia. Será que para los juegos que puedo hacer solo me basta y me sobra con pequeños sprites que cumplan con su cometido… La cosa es que me encantan los sprites, los gifs y todo lo que tiene que ver con la animación en general.

Así que he querido experimentar un poco y aportar mi pequeño grano de arena al vasto mundo de los gifs. Desde el logo de este humilde blog o aquél post de Totu, en el que mi tortuguita hizo su primera aparición virtual, y hasta hoy, he hecho algunos gifs de los que os pongo mis preferidos (¡¡Atención!! ¡¡Exclusiva en el blog!! ¡¡Mi cara aparece en los gifs!!)

Ver el resto del post: (more…)

Después de una pequeña serie de post zapping vuelvo con un poco de programación y juegos de palabras. El segundo de esta serie de posts sobre caracteres lo he dedicado a las combinaciones de letras. Hace tiempo ya, cuando la carrera aun me enseñaba muchas cosas y volvía a casa sorprendido y excitado ante los desafíos y pensamientos que allí me encontraba, (es decir, cuando daba cosas como Autómatas y Lenguajes formales, Tipos Abstractos de datos, Recursividad, Programación Declarativa, Traductores, Compiladores e Interpretes….) leí el que hasta ahora es mi relato favorito de Borges. Este relato es La biblioteca de Babel* y habla sobre una biblioteca ¿infinita? (=>NO. Podría ser cíclica, pero no infinita, como veremos ahora) que contiene volúmenes con una estructura fija, y cuyo contenido son caracteres aleatorios. Así dicho suena absurdo, pero reflexionando un poco, si tenemos todas las combinaciones posibles de caracteres que forman un libro tendremos todos los libros jamás escritos o por escribir. Y sobre esto Borges hace mucha mejor literatura que la mía.

Un poco a menor escala, pues las cifras de Borges, pese a no ser infinitas, serían astronómicas, he hecho un pequeño programa-ejercicio que me devuelve todas las combinaciones de N letras posibles. Las combinaciones se hacen con el alfabeto ASCII en mayúsculas, es decir, las letras de nuestro alfabeto sin la Ñ (en total 26). Este programa, por tanto, construye todas las posibles palabras de N letras que existen o existirán alguna vez con esos 26 caracteres. Entre ellas se encuentran palabras en español, en frances, en inglés… en todos los idiomas que usen este alfabeto. Por supuesto también habrá palabras como AAAAA, BBTUY o AATTA, pero tal vez eso sean palabras alguna vez ;)

Vayamos con algunas cifras. ¿Cuántas palabras hay en cada categoría? Pues si revisamos nuestros conocimientos de Probabilidad veremos que lo que tenemos es 26 elementos para N huecos, con repetición, importa el orden: Variaciones con Repetición 26,n. (VR26,N) Y por tanto habrá 26^N palabras. Esto es:

- Las palabras de 1 letra son las 26 letras del alfabeto.
- Las palabras de 2 letras son 26^2= 676. (Aquí están por ejemplo LA, EL, LO, LE, DE, IT, HE, WE, etc…)
- Hay : 26^3 = 17576 palabras de 3 letras. De cuatro hay 456976.

Y así sucesivamente… Como verán, y como indica la fórmula de las VR, el crecimiento es exponencial, pero siempre es calculable. Ésta es la razón por la que la biblioteca de Babel de Borges ES finita, aunque podría ser cíclica si al autor se le antoja, y por su puesto tendría unas dimensiones inimaginables. Y esa es la razón, también, por la que está vez no colgaré el programa que calcula las VR: Porque es un programa potencialmente peligroso. Ya que manda todas las palabras a un archivo, y si ponemos un número mayor de 5, no solo tratará de monopolizar el ordenador durante un buen rato, sino que puede que lo deje sin memoria. 5 letras serían 11881376 palabras, que a 58 caracteres por linea y 35 líneas por página nos da unas 34.000 páginas. El programa crea un archivo de unos 69 MB. Para seis serían 1.7 GB. y para 8 serían 1.3 TB. Así que imaginaros la biblioteca de Borges…

Como regalo final os dejo un par de enlaces:

Todas las combinaciones para 4 letras (2.2mb). Podéis buscar palabras que conozcáis, aquí dentro están DEDO,CASA, GATO, LOOP, LIKE, LOVE, etc, etc.
(*)La Biblioteca de Babel. de Jorge Luis Borges

Hloa, atnes de seiugr adniprendeo srobe gácoirfs y reeds y jugeos queíra hcaer un par de prmailarglos praa jguar con las praaabls que tneía pietdenne. Étse es el primero de ellos, y cinssote, cmoo tal vez hiaáys aaiprdeco, en donesdraer las larets en las pablaras pero mldnneiatnéaos leibelgs. Hace tipemo rbiceí un croreo en este esitlo, tal vez vrtoosos también lo hiáays reidcbio, que dsprteeó mi cisiaorudd al rsctpeeo. Por lo vsito el cbreero no se apndree el oedrn de las leatrs, snio sloo las laters que ciotsnteyun cada prlabaa y ceuáls son la priemra y la úiltma. De esta froma, si meemntoans eass letars, pdomeos meovr de siito las dámes de forma atalroeia, que a nesutro cerebro no le ipotamrrá, él leerá igaul de bien (benuo, stumnareege os rlestue cunfoso si os fijáis, pruoqe debe hebar orta ptare del cbeerro dloicndiée todo el rato: ¡Oye, que ese ttexo etsá drsdeodnaeo! )

Duépess me ataslan cetunioess cmoo por ejlpmeo: ¿rSeá más fcáil o más dcfiíil eonrtcnar flaats de oígfaotrra en un ttxeo ddsnadeeoro? ¿Derodanser un ttxeo antes de etriprcanlo diiílrufctaa la loabr de romper el aomirtlgo de ercinptado? ¿Enneertdá el simtesa de idndxeao de gologe aglo de lo que etosy ediesbcinro?

Preo eass las dejo ahí un pcoo en el arie, no qriueo crmmeoe tanto la czebaa. Praa aelloqus que saen tan dianocofseds como yo les diré que si no les bstaa con este txteo cmoo domósrecaitn de que esto es vredad, auqí les dejo un alept praa que jueguen:

Acbao de enrnaotcr aulongs eeacnls al rpseetco en mménaee y en micovesorirs:
Usolab
Azules
Microsiervos

ALAUTIDAZCO: Aquí está el código para el que quiera echarle un ojo.
¿Qué es esto? -> Leer texto ordenado: (more…)

(Más viñetas de Dilbert Aquí)