Hoy os voy a descubrir una pequeña maravilla del arte independiente.
Una serie cojonuda (y no es porque en ella participen mi padre y sobre todo, mi primo Jorge).
Como la vida misma, http://www.averlasvenir.es/
32 minutos de metraje, que me han pasado realitavamente cómo 5.
Un ejemplo de cómo con pocos medios y menos actores, puede hacerse una serie mucho mejor que las “profesionales”.
P.D.: ¡QUIERO UN PAPEL! xD Yo tambien tengo mi historia…
He modificado la imagen que en wikipedia ilustra Mergesort (de dominio público) para mostrar como funciona mi Optimal Comparison Sort.Recuerdo que para mezclar tres vectores, se usa el Merge3.
Aprovecho para comentar que es el equivalente a un árbol balanceado.Las comparaciones en este caso son 10 para mi Optimal Comparison Sort , 14 para Mergesort y 15 para Quicksort eligiendo como pivote el elemento central. Espero un comportamiento proporcional para vectores aleatorios más grandes. (more…)
Sabemos la forma óptima de mezclar tres vectores ordenados, la de mezclar cuatro no será tan sencilla. (more…)
Lo que decía sobre la cota de los algoritmos de ordenación, explicado aquí con una bonita demostración.
The worst case running time of any comparison sort algorithm is Ω(nlgn)
![X[1\dots n]](http://upload.wikimedia.org/math/9/7/e/97e625b7973e975c107e32cc966f1075.png)
. So T is complete and the label of each vertex v of the tree are of the form xi:xj and v is source of two edges labeled 
and < . The comparisons made by a sorting algorithm running over X corresponds to a path from the root of T to a leaf. One should note that for each possible permutation P of the elements in X there is such a path. So T has at least n! leaves. We know that T is a binary tree, so it has a maximum of 2h leaves, where h is it’s height. We have 
and.
Summarizing, h = Ω(nlgn)
Cada vez que pienso en ordenación y se me ocurre algo pienso que como lo hacía tan complicado, y que cómo lo complican tanto si es “tan fácil”.
Ordenar un vector de n elementos con k vectores ordenados en su interior, de forma óptima, viene a ser hallar en el mínimo tiempo posible la sorting network que caracteriza la ordenación de ese vector (por eso da igúal el tiempo de inserción suplementario a la búsqueda binaria, sólo ordenamos una vez que sabemos todas las relaciones entre elementos).
Ordenar un vector de n elementos con k vectores ordenados en su interior, el más largo de ellos de c elementos, es equivalente a ordenar los centros de de los k vectores (invocación recursiva al mismo algoritmo) y ordenar el elemento central a la izquierda del primer elemento ordenado con el central a la derecha del segundo ordenado etc… (búsqueda binaría de los centros de los k vectores en los demás de forma simultanea).
Mediante una búsqueda binaría simultanea masiva, de los elementos centrales de los k vectores, el coste sería:
ordenar(n)=(n-1)+ordenar(k)*log2(c)
En el peor caso (donde halla menos orden que aprovechar, vectores de 2 elementos)
ordenar(n)=(n-1)+ordenar( n/2)*log2(2)
P.D.: redondeando al entero superior log2(2)=1+1=2.
La idea básica la tuve este verano, pensando en dimensiones, vectores y dimensiones; ¿Si tomamos un vector como una dimensión, habría media dimensión si por ejemplo sólo coges terminos positivos? Y chorradas así.
Pero lo que de verdad importa es la siguiente idea, para ordenar N vectores ordenados, los podemos ver como N dimensiones. Por lo tanto si juntamos esos vectores en un plano N-dimensional, pudiera ser que fuera muy fácil hacer la fusión (merge) -Violeta, si algún momento lees esto, en eso es en lo que estaba pensando este verano :P-.
Para muestra un botón (uso 3 vectores, por no saber representar más de 3 dimensiones en el plano, vectores de 3 elementos para facilitar la búsqueda binaria, y son sin repetición para evitarme más problemas de momento) :
Así un algoritmo casi óptimo, adaptativo, de ordenación por comparación sería así:
Para que fuera óptimo de verdad la única variación sería comparar siempre los elementos centrales de los vectores (busqueda binaría). Siempre hacia el vector central. Sería equivalente a mi idea de un algoritmo óptimo recursivamente adaptativo.
Como se puede ver es una forma mucho más sencilla de representar y trabajar con la ordenación de vectores.
Creo que aplicando esta estructura como TAD (tipo abstracto de datos) adecuado, se pueden conseguir el numero mínimo de comparaciones para la ordenación. El TAD creo que sería un gráfo dirigido con algún añadido para localizar los centros de los vectores (también puede que sea más fácil de dibujar que n dimensiones).
Es increíble lo importante que es la busqueda binaria para desarrollar estas ideas. al fin y al cabo está en todos lados… y sino…¿Tú como cortaría el queso si quieres hacer dados con el mínimo de cortes? Por la mitad y otra vez por la mitad, hasta que los pedazos sean suficientemente pequeños.
P.D.: Le estoy dando vueltas a que puede que sea imposible hacer un algoritmo superadaptativo (recursivamente adaptativo) que a la vez sea óptimo, me da la impresión de que si comparas primero todos los centros de todos los vectores estás haciendo comparaciones que no son imprescindibles.
El algoritmo óptimo por lo tanto sería: inserción binaria del elemento central de los vectores colindantes, en el vector central, e inserción binaria recursiva de los elementos centrales de sus dos mitades, luego repetimos la operación para el resto de los vectores. Tal vez si primero ordenamos los centros de todos los vectores, nos ahorremos comparaciones, o tal vez no, y sólo fueran operaciones prescindibles, si lo implemento después de examenes, probaré las dos posibilidades.
Microsoft (a.k.a el diablo para algúnos :P), ha sacado un entorno de desarrollo rápido de videojuegos tanto para Windows (XP, directX9) como para XBOX360. Entre otras cosas promete liberar al programador de muchas cosas feas (e innecesarias), como por ejemplo tener que escribir en cada fichero las referencias a las librerías básicas que siempre usamos (a ver si se apuntan un tanto en ADA y les copia algún IDE la idea :P).
Adiós a alguna tediosa tarea ;). Bienvenido sea, la burocracia no es buena.
Si es que, ¡todo debería de ser para torpes!
Yo pienso probarlo.
Se llama XNA Game Studio y el enlace está AQUÍ.
P.D.: A ver si otros grandes fabricantes de consolas, se ponen las pilas y empiezan a soltar SDK’s gratuitos… que es una pena que para programar algo para PSP o DS, haya que ir haciendo ingeniería inversa de todo.
Hoy quiero hablar de una de las más importantes tecnologías de la informática actual, la emulación.
Todo el mundo la usa a diario al menos por partida doble, y es que cualquier procesador (x86) actual, “emula” la arquitectura x86 sobre un conjunto de instrucciones más propios de una arquitectura RISC. La gran mayoría de estos mismos usuarios de PC también usan día a día java, que emula un procesador con su propio juego de instrucciones, el denominado “bytecode”.
La emulación nunca es perfecta, nada en informática lo es, a día de hoy, pero suele ofrecer muy buenos resultados.
Una característica interesante es por ejemplo, que el código emulado puede ser automodificable, independientemente de si la arquitectura que hay debajo lo soporta. Esto podría servir en el caso de que se requiera programar código automodificable en muchas de las arquitecturas modernas, que por motivos de rendimiento separan cachés de código y datos, y no permiten la escritura en la primera.
Pasando a una visión más divertida del asunto le recomiendo a todo el mundo con un teléfono con java (j2me, o jme que es como lo llamán ahora) , que pruebe el meBoy.
Tiene algúnos errores y otras cosas resultan incomodas, pero es lo más espectacular que he visto hasta ahora en el mundo de los emuladores. Emula juegos de gameboy, incluso gameboy color, a velocidad real, sobre cualquier movil de clase media actual (mi nokia 5200, por ejemplo). Es decir, sobre un emulador (la máquina virtual de java) corre otro (meboy) … y todo ello en un gadget del tamaño de una game boy micro. Es increible lo que pueden dar de si los ARM que llevan estos bichos.
Especificación y derivación de algoritmos de forma automática, algo tiene que ver con mis ideas sobre como debería de ser el programar, si lo he entendido bien, leyendo por encima.
¿Alguien sabe de estudios de derivación automática de especificaciones a código? Me interesaría muchísimo, lo veo como un gran paso de abstracción en el camino a seguir. Aunque fuera semi-automatica apoyandose en una base de datos.
EDITO: Para añadir un documento que parece aún más interesante AQUÍ.
A la hora de añadir un elemento a un vector ordenado, es evidente que el coste óptimo es log(n) -mediante busqueda binaria-.
El error que se comete es creer que hacer esto mismo con varios elementos nos lleva necesariamente a algo proporcional.
Para añadir n elementos a un vector ordenado (o lo que es lo mismo, ordenar n elementos), parece que el coste vaya a ser n log n en el peor caso. Sin embargo esto tan sólo es cierto si no tenemos en cuenta las realciones entre los elementos. Por lo tanto n log n sólo es cota para el peor caso de un algoritmo de ordenación óptimo.
Para ilustrar esto comparemos la búsqueda binaria con los algoritmos anteriores.
BusquedaBinaria(estable)
4 6 0 0 0 5 6 0 7 0 7 8 2 7 8 0
4<=6 comps=1
0<=4<=6 comps=2
0<=0<=4<=6 comps=4
0<=0<=0<=4<=6 comps=6
0<=0<=0<=4<=5<=6 comps=9
0<=0<=0<=4<=5<=6<=6 comps=12
0<=0<=0<=0<=4<=5<=6<=6 comps=15
0<=0<=0<=0<=4<=5<=6<=6<=7 comps=19
0<=0<=0<=0<=0<=4<=5<=6<=6<=7 comps=23
0<=0<=0<=0<=0<=4<=5<=6<=6<=7<=7 comps=27
0<=0<=0<=0<=0<=4<=5<=6<=6<=7<=7<=8 comps=31
0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=8 comps=35
0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=7<=8 comps=39
0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=7<=8<=8 comps=43
0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=7<=8<=8 comps=47