miércoles, 1 de marzo de 2017

Modificando la Dreamcast (I): Introducción

Las últimas consolas de Sega no le fueron muy bien, la Saturn era muy buena, con el doble sistema de CD y Cartucho, pero no gustó. La Dreamcast fue su intento de competir con la Playstation, pero llegó tarde, poco después salió la PS2, la Dreamcast fracasó en ventas e hizo que Sega se retirara del mercado de las consolas. Es una consola de sexta generación que se produjo entre 1998 y 2001, compitiendo con PS2, GameCube y XBox, todas usando ya un DVD, mientras que Sega apostó por el GD-ROM, con capacidad de 1'2 Gb y mejor velocidad. El procesador principal era el Super H-4 de Hitachi, un procesador RISC de 32 bits, una FPU vectorial de 128 bits de Hitachi, y un chip gráfico de NEC potente y con gran capacidad de cálculo de polígonos, luces y sombreados. El sonido disponía de dos procesadores en un chip de Yamaha con 4 canales, la memoria principal era de 16Mb, la memoria gráfica de 8Mb, y la de sonido era de 2 Mb, todas pudiendo trabajar de forma independiente conectadas a cada procesador, lo que permitía mejorar la velocidad interna del aparato.

Como particularidades incluía un módem para conectar con los servidores de Sega y poder jugar on-line (no se incluyó en algunos países asiáticos), y el mando incluía la posibilidad de añadir una unidad de memoria con un display, lo que permitía en los juegos un comportamiento personalizado de los caracteres, o disponer de información adicional. Esto que hoy día es lo habitual entonces no lo era.

También disponía en la ROM de unas rutinas desarrolladas por Microsoft compatibles con las que se usaban en los móviles del momento, el Windows CE, en un intento de hacer que el desarrollo de programas para la máquina fuera mas compatible con esos sistemas, pero aunque Sega amplio y mejoró muchas rutinas, no llegó a ser lo que prometían.

Unidad japonesa/asiática (logotipo naranja) y mando USA/Europa (logo azul), la unidad no dispone del modem en el lateral, por lo que se sabe fue vendida en Asia. (Fuente Wikipedia)

Esta consola tiene la ventaja de que es muy cómoda y  agradecida para desarrollar juegos para ella (al contrario que la PS2 con sus múltiples procesadores que requiere programación muy especial para optimizarla), por lo que hay una gran comunidad de programadores que la mantienen activa.

En esta serie de entradas voy a modificar una máquina, ya que también es de las mejores consolas para modear, permite muchas modificaciones que se han ido actualizando, algunas se han simplificado al incluirse en otras, no son excesivamente complicadas y el resultado es muy bueno. Podemos agruparlas en tres grandes grupos:

Salidas de vídeo

La consola dispone de un conector trasero, usando el cable apropiado se puede conectar por AV, S-Video, Euroconector o VGA (ver esta entrada). Hoy día es difícil encontrar los cables hechos, o localizar el conector para hacerse el cable, por lo que se recurre a poner las salidas en la carcasa directamente. En esta máquina es muy sencillo añadir una salida VGA mas sonido. Se puede hacer con un interruptor que fuerce la salida, aunque realmente no es necesario pues se puede hacer que el propio conector VGA lo haga de forma automática. Disponiendo de VGA no tiene sentido hacer una salida Scart, que abulta mas y no aporta mejor calidad.

BIOS Multi-Región

Esta modificación realmente no es necesaria, cargando un programa desde un CD se puede hacer lo mismo, pero no cabe duda de que disponer de un BIOS con soporte ampliado desde el arranque es mucho mas cómodo. Esta modificación originalmente se hacía para el cambio de región, había que realizar un cableado en la placa que dejaba la Flash BIOS en modo que era grabable, pero si no te acordabas de protegerla al terminal acababas con la BIOS corrupta. Luego se ha desarrollado la doble BIOS, de forma que se puede disponer de la original o la ampliada solo cambiando un interruptor y reiniciando la máquina. La BIOS ampliada mediante DreamShell incluye no solo region-free, sino soporte para unidades de datos mejoradas.

Almacenamiento


La consola incluye solo el lector de GC-ROM, pero usando DreamShell se pueden manejar unidades SD a través del puerto serie que incluye la máquina,  pero esto ha quedado superado hoy día, se puede conectar un disco duro directamente lo que la hace mucho mas cómodo y rápido.

En las próximas entradas iré desarrollando estas modificaciones en las Dreamcast, vereis que no es complicado hacerlas, aunque los puntos de soldadura de la máquina no son muy grandes, por lo que hay que tener un poco de mano soldando, y en la de doble BIOS hay que tener un poco de cuidado al manipularla.

jueves, 23 de febrero de 2017

Programación del Sinclair QL (XXI): Estructura de datos. Arbol binario de Búsqueda balanceado



Como dije en la entrada anterior, el problema de los árboles binarios de búsqueda (ABB) es que si no están bien balanceados pierden mucha efectividad, el caso extremo es introducir los datos en orden, ya que estamos generando una lista pero con la ocupación y la mayor complejidad de un árbol.

Balancear el árbol significa que en cada nodo los elementos que cuelguen por su izquierda sean los mismos que los que cuelgan por su derecha, esta circunstancia ideal es compleja, por lo que se mira que la profundidad de las dos ramas sea la misma, un sistema un poco mas sencillo de conseguir y que sigue manteniendo el balanceo. Si una rama tiene elementos de mas profundidad que la otra, el árbol se balancea para compensarlo mediante lo que se denomina una rotación.

Aunque existen varias formas de montar los ABB balanceados, las formas mas utilizadas en general son los siguientes (aunque en general se usan solo los tres primeros):

  • Los árboles AVL son los ABB auto-balanceados mas antiguos y los que consiguen mantener el mejor balanceo.
  • Los montículos son ABB balanceados almacenados en forma de arreglo, mas adelante los usaremos en el conocido algoritmo de ordenación Heapsort.
  • Los árboles rojo-negro son menos estrictos en el balanceo, permitiendo ligeras descompensaciones, por lo que son un poco mas ágiles en inserciones.
  • Los árboles AA son una variación de los rojo-negro que simplifica mas las inserciones.
  • Los árboles biselados son ABB balanceados cuyos nodos recientemente visitados se rotan para que aparezcan lo antes posible en las búsquedas.
  • Los árboles de Fibonacci son una variante de los AVL.
Voy a modificar el árbol para que se comporte como un árbol AVL, llamado así por el nombre de sus creadores, los matemáticos rusos Gueorgui Adelsón-Velski y Yevgueni Landis, que lo definieron en un artículos publicado en 1962.

En una árbol AVL hay que conocer la profuncidad de cada rama del árbol, para poder mantenerlo siempre balanceado. Si la profundidad de la rama izquierda difiere en más de una unidad de la profundidad de la rama derecha, el árbol está desbalanceado y se procede a efectuar una rotación para equilibrarlo, se retrocede al padre de ese nodo y se repite la operación, subiendo hacia la raíz hasta que no se requieran mas balanceos. Para poder ir subiendo por las ramas del árbol debemos guardar el camino recorrido, lo que se consigue de forma sencilla usando recursividad en lugar de iteración, por eso cambiaremos el algoritmo de inserción para convertirlo en recursivo.

Para equilibrar un árbol hay que mover nodos, en lo que se denominan rotaciones, se basan en ver la diferencia de profundidad de un nodo entre sus ramas izquierda y derecha, y si la diferencia es mayor de 1 realizar una rotación en el nodo, intercambiándolo con su hijo. Depende del hijo que usemos para rotar se denominará rotación a la izquierda o rotación a la derecha, pero ambas son equivalentes. También dependiendo del nodo ocupado del elemento hijo se usará una rotación simple o una doble. Pongo un ejemplo sencillo de rotación simple a la derecha y otro de rotación doble izquierda-derecha:


Vemos que en primer caso el nodo 1 es el que usamos para rotar, ya que tiene cero hijos por su izquierda y dos por su derecha necesita una rotación derecha. Colgamos el nodo (1) a la izquierda de su nodo hijo (2), y luego colgamos el nodo hijo (2) en lugar del nodo seleccionado. Podemos imaginar que estiramos hacia arriba del nodo (2).

Si el nodo izquierdo está ocupado, no es posible poner allí el nodo seleccionado, por lo que necesitamos dos pasos, primero colgamos el nodo hijo (3) a la derecha de su sub-nodo izquierdo (2), y luego colgamos el sub-nodo izquierdo del nodo seleccionado (1). Ahora tenemos ya el caso anterior y usando el mismo sistema equilibramos el árbol.

Entendiendo bien esto es muy sencillo equilibrar los árboles en las altas y bajas, solo hay que ir subiendo por el árbol a partir del nodo seleccionado, ver las profundidades de ambos nodos, y actuar en consecuencia. Hay varios sistemas para mantener las alturas en el árbol, lo mas sencillo es guardar la altura de las sub-ramas izquierda y derecha pero necesitamos dos valores en cada nodo, la otra forma es mantener solo la diferencia de alturas y así usamos un solo valor en cada nodo.

lunes, 19 de diciembre de 2016

Traducciones en la Wikipedia

Estas son mis últimas traducciones:

  • La gama de computadores UNIVAC, separado del UNIVAC I a donde redirigía
  • Códigos de caracteres de 6 bits, que fueron muy usados en los UNIVAC y en los DEC por ejemplo, igual que en muchos de los primeros ordenadores.
  • Entrada sobre ordenadores decimales, en general los primeros ordenadores fueron casi todos decimales (con la excepción de los Zuse, el sistema mecánico que empleó en la Z1 para almacenar datos binarios fue una gran idea, y la fuente de sus principales problemas, luego pasó a los relés y se solucionaron) hasta que se impuso el binario.
  • Entrada sobre la empresa Remington Rand
  • Entrada sobre Herman Lukoff y entrada sobre John Grist Brainerd, pioneros poco conocidos de la informática.

viernes, 16 de diciembre de 2016

Programación del Sinclair QL (XX): Estructuras de datos. Presentar el árbol



La presentación de los datos que hacía del árbol no eran muy adecuadas, en las listas se ve mejor pero el árbol cuesta mas de ver presentando en forma lineal los valores de datos y enlaces, por lo que he desarrollado un proceso para ver de manera mas gráfica los árboles, en modo texto, pero queda bastante visible. Hay dos procesos, uno que presenta el árbol que es nuevo, y el que retorna la lista de elementos del árbol en una cadena que he simplificado la visualización.

4890 REMark --------------------------------------------------------------
4900 REMark -- ARBOL_VER_GR -- Presenta en pantalla un arbol            --
4910 REMark --------------------------------------------------------------
4920 DEFine PROCedure ARBOL_VER_GR
4930   LOCal lin,col,a$
4940   :
4950   lin = ARBOL_NIVELES - 1
4960   col = 1 : FOR i=2 TO lin+2 : col = (2 * col)
4970   OPEN#5,con : WINDOW#5, 448,200,32,16
4980   CLS#5 : BORDER#5, 2,2
4990   PRINT#5, "N:";!ARBOL_NIVELES;!"L:";lin;!"C:";col-2,
5000   PRINT #5,ARBOL_ELEMENTOS$
5010   montar 0,col/2-1,col/4,A_RAIZ
5020   INPUT a$
5030   CLOSE#5
5040 END DEFine 
5050 :
5060 DEFine PROCedure montar(l,c,s,nodo)
5070   LOCal i,t
5080   :
5090   IF nodo <> P_NULO THEN 
5100     imprime l+1,c+1, ArrArbol(nodo)
5110     IF ArrDer(nodo) <> P_NULO THEN 
5120       t = c+s+1
5130       FOR i=c+2 TO t-1 : imprime l+1,i,"-"
5140       imprime l+1, t, "\"
5150       imprime l+2, t, "|"
5160     END IF 
5170     IF ArrIzq(nodo) <> P_NULO THEN 
5180       t = c-s+1
5190       FOR i=c TO t+1 STEP -1 : imprime l+1,i,"-"
5200       imprime l+1, t, "/"
5210       imprime l+2, t, "|"
5220     END IF 
5230     montar l+2,c-s,s/2,ArrIzq(nodo)
5240     montar l+2,c+s,s/2,ArrDer(nodo)
5250   END IF 
5260 END DEFine 
5270 :
5280 DEFine PROCedure imprime(l,c,dato$)
5290   IF (l > 0) AND (l < 19) AND (c > 0) AND (c < 73) THEN 
5300     AT#5,l,c : PRINT#5, dato$
5310   END IF 
5320 END DEFine 
5330 :
5340 REMark --------------------------------------------------------------
5350 REMark -- v$ = ARBOL_ELEMENTOS$ -- Muestra la lista de elementos   --
5360 REMark -- RETORNA: Lista ordenada de elementos del arbol           --
5370 REMark --------------------------------------------------------------
5380 DEFine FuNction ARBOL_ELEMENTOS$
5390   LOCal lista$
5400   :
5410   lista$=""
5420   inorden lista$,A_RAIZ
5430   RETurn lista$
5440 END DEFine 
5450 :
5460 DEFine PROCedure inorden(cadena$,nodo)
5470   IF nodo <> P_NULO THEN 
5480     inorden cadena$, ArrIzq(nodo)
5490     IF LEN(cadena$) <> 0 THEN cadena$ = cadena$ & ","
5500     cadena$ = cadena$ & ArrArbol(nodo)
5510     inorden cadena$, ArrDer(nodo)
5520   END IF 
5530 END DEFine<0 hay="" libres="" no="">
 
El resultado es el siguiente, no es espectacular pero creo que se ve bien la estructura del árbol, y cuando entremos en los árboles AVL y las rotaciones se verá de forma mas clara como se van moviendo los datos.


Aquí los fuentes de todo lo desarrollado sobre estructuras de datos hasta el momento, la parte de ordenación no ha variado.

martes, 13 de diciembre de 2016

Programación del Sinclair QL (XIX): Estructura de datos. Arbol binario de Búsqueda



Los arboles son las estructuras mas usadas para almacenar datos, ya que permiten un muy rápido acceso a ellos. La estructura en sencilla, un registro se divide en dos partes, una con los datos que se necesitan guardar y otro con enlaces a los elementos hijos, que será un número mayor o igual a dos.

Ejemplo de arbol (Fuente: Monografias.com)


Si el número máximo de hijos es dos se denominan árboles binarios, y son los mas usados en programación en general, reservando los árboles de mas ramas para uso en ficheros indexados habitualmente. No voy a explicar mucho mas, hay suficiente información en la Web sobre arboles y su manejo.

Existe un tipo especial de árbol binario, en el que en cada nodo de cada rama, los valores de los elementos que cuelgan del nodo izquierdo son todos menores al valor del propio nodo, y los elementos que cuelgan del nodo derecho son todos valores mayores al del propio nodo, de forma que si recorremos el árbol primero la rama izquierda, luego el nodo, y luego la rama derecha, obtenemos una lista de elementos ordenados en orden creciente. Si la recorremos primero la rama derecha, luego el nodo y después la rama izquierda obtenemos la lista ordenada en forma decreciente. Este tipo de árboles se llaman "Árbol Binario de Búsqueda", y es lo que voy a implementar, ya que estamos hablando de algoritmos de ordenación. 

Voy a usar tres arreglos para almacenar los datos, en uno me guardo los datos del registro (en este caso será una lista de números, pero puede ser cambiado de manera sencilla a una lista de cadenas por ejemplo), otro arreglo numérico con los enlaces a los punteros de la rama izquierda, y un tercer arreglo con los enlaces a la rama derecha. Estos dos arreglos podrían ser uno solo, pero creo que así está un poco mas claro.

Usaré el arreglo de enlaces a nodos izquierdos para almacenar la lista de elementos libres, pero por que sea mas visual haré lo mismo con los derechos. Esto lo cambiaré mas adelante por algo un poco mejor, ya lo veremos. El manejo de los árboles requiere muchos procedimientos recursivos, aunque usaré iterativos cuando sea posible para que se vean varias técnicas de manejo.

Uso una variable para almacenar el nivel máximo de profundidad del árbol, no tiene uso mas que para enseñarlo en pantalla, pero me permite que se vea algo que deseo demostrar luego. No me voy a complicar mucho cuando compacto el árbol, ya que esta parte la voy a cambiar luego, solo lo pongo de momento para que se vea.

2000 REMark --------------------------------------------------------------
2010 REMark -- ESTRUCTURAS DE DATOS                                     --
2020 REMark --   Modulo....: Arbol binario                              --
2030 REMark --   Objetivo..: Arbol binario usando un arreglo de valores --
2040 REMark --               numericos y dos para los punteros          --
2050 REMark --   Autor.....: javu61, 12/2016                            --
2060 REMark --   Procesos..:                                            --
2070 REMark --     ARBOL_CREAR      -- Crear el arbol                   --
2080 REMark --     ARBOL_NUEVO(tam) -- Crea el arbol con un tama‰o      --
2090 REMark --     b=ARBOL_LEN      -- Nro de elementos del arbol       --
2100 REMark --     b=ARBOL_NIVELES  -- Nro de niveles del arbol         --
2110 REMark --     b=ARBOL_BUSCAR(n)-- Busca un elemento en el arbol    --
2120 REMark --     ARBOL_ADD(dato)  -- Introduce un dato en el arbol    --
2130 REMark --     ARBOL_DELETE(n)  -- Borra el elemento n del arbol    --
2140 REMark --     v$=ARBOL_VER$    -- Muestra los elementos del arbol  --
2150 REMark --     ARBOL_CAMBIA(tam)-- Cambia el tama‰o del arbol       --
2160 REMark --   Procesos de uso interno:                               --
2170 REMark --     ARBOL_INIT       -- Inicializa una arbol             --
2180 REMark --     b=ARBOL_EL_LIBRE -- Retorna elemento libre           --
2190 REMark --     n=ARBOL_NIVELES  -- Retorna nro de niveles del arbol --
2200 REMark --   Elementos.: Se usan los siguientes elementos globales  --
2210 REMark --     A_TAM           -- Tama‰o del arreglo                --
2220 REMark --     A_FACTOR        -- Factor de crecimiento             --
2230 REMark --     ArrArbol(tam)   -- Elementos del arbol               --
2240 REMark --     ArrIzq(tam)     -- Puntero al elemento izquierdo     --
2250 REMark --     ArrDer(tam)     -- Puntero al elemento derecho       --
2260 REMark --     P_NULO          -- Puntero nulo                      --
2270 REMark --     P_VACIO         -- Puntero vacio                     --
2280 REMark --     A_RAIZ          -- Puntero al nodo raiz              --
2290 REMark --     A_NRO           -- Nro de elementos del arbol        --
2300 REMark --     A_NIVELES       -- Nro de niveles del arbol          --
2310 REMark --------------------------------------------------------------
2320 :
2330 :
2340 REMark --------------------------------------------------------------
2350 REMark -- ARBOL_CREAR -- Crea el arbol                             --
2360 REMark --------------------------------------------------------------
2370 DEFine PROCedure ARBOL_CREAR
2380   REMark Espacio para 10 elementos, crece minimo 5
2390   ARBOL_NUEVO 9,5
2400 END DEFine 
2410 :
2420 REMark --------------------------------------------------------------
2430 REMark -- ARBOL_NUEVO(tam,fac) -- Crea el arbol con un tama‰o y un --
2440 REMark --                         factor de crecimiento            --
2450 REMark --------------------------------------------------------------
2460 DEFine PROCedure ARBOL_NUEVO(tam,fac)
2470   LOCal i
2480   :
2490   LET P_NULO   = -1        : REMark Puntero nulo
2500   LET P_VACIO  = -2        : REMark Puntero vacio
2510   LET A_RAIZ   = P_NULO    : REMark Puntero al nodo raiz
2520   LET A_NIVELES= 0         : REMark Nro de niveles del arbol
2530   LET A_NRO    = 0         : REMark Nro de elementos del arbol
2540   LET A_TAM    = tam       : REMark Tama‰o del arreglo
2550   LET A_FACTOR = fac       : REMark Factor de crecimiento
2560   DIM ArrIzq(tam)          : REMark Punteros al elemento izquierdo
2570   DIM ArrDer(tam)          : REMark Punteros al elemento derecho
2580   DIM ArrArbol(tam)        : REMark Elementos del arbol
2590   :
2600   REMark Inicializa arbol de elementos libres
2610   FOR i=0 TO A_TAM : ArrIzq(i) = P_VACIO : ArrDer(i) = P_VACIO
2620 END DEFine 
2630 :
2640 REMark --------------------------------------------------------------
2650 REMark -- b = ARBOL_LEN -- Retorna el nro de elementos del arbol --
2660 REMark -- RETORNA: 0 si vacio, >0 = nro de elementos               --
2670 REMark --------------------------------------------------------------
2680 DEFine FuNction ARBOL_LEN
2690   RETurn A_NRO
2700 END DEFine 
2710 :
2720 REMark --------------------------------------------------------------
2730 REMark -- b = ARBOL_NIVELES -- Retorna el nro de niveles del arbol --
2740 REMark -- RETORNA: 0 si vacio, >0 = nro de elementos               --
2750 REMark --------------------------------------------------------------
2760 DEFine FuNction ARBOL_NIVELES
2770   RETurn A_NIVELES
2780 END DEFine 
2790 :
2800 REMark --------------------------------------------------------------
2810 REMark -- b = ARBOL_EL_LIBRE -- Retorna elemento libre del arbol   --
2820 REMark -- RETORNA:  <0 hay="" libres="" no="">=0 nro del elemento         --
2830 REMark --------------------------------------------------------------
2840 DEFine FuNction ARBOL_EL_LIBRE
2850   LOCal i
2860   :
2870   FOR i=0 TO A_TAM
2880     IF ArrIzq(i) = P_VACIO THEN RETurn i
2890   END FOR i
2900   RETurn P_NULO
2910 END DEFine 
2920 :
2930 REMark --------------------------------------------------------------
2940 REMark -- b = ARBOL_BUSCAR(valor) -- Busca un elemento en el arbol --
2950 REMark -- RETORNA:  nro del elemento o NULO si no encontrado       --
2960 REMark --------------------------------------------------------------
2970 DEFine FuNction ARBOL_BUSCAR(valor)
2980   LOCal nro,repetir
2990   :
3000   nro = A_RAIZ
3010   REPeat repetir
3020     IF nro = P_NULO THEN EXIT repetir
3030     IF ArrArbol(nro) = valor THEN EXIT repetir
3040     IF ArrArbol(nro) < valor THEN 
3050       nro = ArrDer(nro)
3060     ELSE 
3070       nro = ArrDer(nro)
3080     END IF 
3090   END REPeat repetir
3100   RETurn nro
3110 END DEFine 
3120 :
3130 :
3140 REMark --------------------------------------------------------------
3150 REMark -- ARBOL_ADD(dato) -- Introduce un dato en el arbol, si     --
3160 REMark --                    esta llena crece al doble             --
3170 REMark --------------------------------------------------------------
3180 DEFine PROCedure ARBOL_ADD(dato)
3190   LOCal repetir,nro,pos,nivel
3200   :
3210   REMark Busco nodo libre, crece si hace falta y ubico el elemento
3220   REPeat repetir
3230     nro = ARBOL_EL_LIBRE
3240     IF nro <> P_NULO THEN EXIT repetir
3250     ARBOL_CAMBIA(A_TAM*2)
3260   END REPeat repetir
3270   ArrArbol(nro) = dato
3280   ArrIzq(nro) = P_NULO
3290   ArrDer(nro) = P_NULO
3300   nivel = 1
3310   :
3320   REMark Si es el primer nodo, lo ubico en la raiz
3330   IF A_RAIZ = P_NULO THEN 
3340     A_RAIZ = nro
3350   ELSE 
3360     REMark Si no es el primero, buscamos su posicion recorriendo
3370     pos = A_RAIZ
3380     REPeat repetir
3390       nivel = nivel + 1
3400       REMark Si es menor o igual pasamos a la izquierda
3410       IF (ArrArbol(pos) > dato) THEN 
3420         IF (ArrIzq(pos)=P_NULO) THEN 
3430           ArrIzq(pos) = nro
3440           EXIT repetir
3450         END IF 
3460         pos = ArrIzq(pos)
3470       ELSE 
3480         :
3490         REMark Si es mayor pasamos a la derecha
3500         IF (ArrDer(pos)=P_NULO) THEN 
3510           ArrDer(pos) = nro
3520           EXIT repetir
3530         END IF 
3540         pos = ArrDer(pos)
3550       END IF 
3560     END REPeat repetir
3570   END IF 
3580   :
3590   REMark Sumo un elemento al arbol y miro el nivel
3600   A_NRO = A_NRO + 1
3610   IF nivel > A_NIVELES THEN A_NIVELES = nivel
3620   :
3630 END DEFine 
3640 :
3650 REMark --------------------------------------------------------------
3660 REMark -- v$ = ARBOL_VER$ -- Muestra el arbol                      --
3670 REMark -- RETORNA: Lista de elementos del arbol                    --
3680 REMark --------------------------------------------------------------
3690 DEFine FuNction ARBOL_VER$(hastanivel)
3700   LOCal lista$
3710   :
3720   IF ARBOL_LEN = 0 THEN 
3730     PRINT "Error: Arbol vacio"
3740     STOP
3750   END IF 
3760   :
3770   lista$=""
3780   inorden A_RAIZ,hastanivel,lista$,1
3790   RETurn lista$
3800 END DEFine 
3810 :
3820 DEFine PROCedure inorden(nodo,nivel,cadena$,actual)
3830   IF nodo <> P_NULO THEN 
3840     inorden ArrIzq(nodo),nivel,cadena$,actual+1
3850     IF (nivel < 1) OR (nivel = actual) THEN 
3860       IF LEN(cadena$) <> 0 THEN cadena$ = cadena$ & ","
3870       cadena$ = cadena$ & "[" & actual & "]" & ArrArbol(nodo)
3880     END IF 
3890     inorden ArrDer(nodo),nivel,cadena$,actual+1
3900   END IF 
3910 END DEFine 
3920 :
3930 REMark --------------------------------------------------------------
3940 REMark -- ARBOL_DELETE(valor) -- Borra un elemento del arbol       --
3950 REMark --------------------------------------------------------------
3960 DEFine PROCedure ARBOL_DELETE(valor)
3970   LOCal nodo,padre,repetir
3980   :
3990   nodo = A_RAIZ
4000   padre = P_NULO
4010   REPeat repetir
4020     IF nodo = P_NULO THEN EXIT repetir
4030     IF ArrArbol(nodo) = valor THEN EXIT repetir
4040     padre = nodo
4050     IF ArrArbol(nodo) < valor THEN nodo = ArrDer(nodo)
4060     IF ArrArbol(nodo) > valor THEN nodo = ArrDer(nodo)
4070   END REPeat repetir
4080   :
4090   IF (nodo = P_NULO) THEN 
4100     PRINT "ERROR: Intenta eliminar un elemento que no existe"
4110     STOP
4120   END IF 
4130   :
4140   ARBOL_BORRAR_NODO nodo,padre : REMark Borrar el nodo
4150   A_NRO = A_NRO - 1            : REMark reducir elementos del arbol
4160   A_NIVELES = ARBOL_MAX_NIVEL  : REMark Recalcula niveles
4170 END DEFine 
4180 :
4190 REMark --------------------------------------------------------------
4200 :
4210 DEFine PROCedure ARBOL_BORRAR_NODO(nodo,padre)
4220   LOCal nuevo
4230   :
4240   :: ArrArbol(nodo) = 0
4250   :
4260   REMark Este elemento sera el que reemplace en el padre
4270   nuevo = P_NULO
4280   :
4290   REMark Si no tiene hijos, se desapunta el padre
4300   IF (ArrIzq(nodo)=P_NULO)  AND (ArrDer(nodo)=P_NULO) THEN 
4310     nuevo = P_NULO
4320   END IF 
4330   :
4340   REMark Solo tiene un hijo, se pasa al padre
4350   IF (ArrIzq(nodo)=P_NULO)  AND (ArrDer(nodo)<>P_NULO) THEN 
4360     nuevo = ArrDer(nodo)
4370   END IF 
4380   IF (ArrIzq(nodo)<>P_NULO) AND (ArrDer(nodo)=P_NULO)  THEN 
4390     nuevo =  ArrIzq(nodo)
4400   END IF 
4410   :
4420   REMark Tiene dos hijos, pasa al padre el derecho y lo borro
4430   IF (ArrIzq(nodo)<>P_NULO) AND (ArrDer(nodo)<>P_NULO) THEN 
4440     nuevo = ArrDer(nodo)
4450     ARBOL_BORRAR_NODO ArrDer(nodo),nodo
4460   END IF 
4470   :
4480   REMark Ahora apunto el padre de forma adecuada
4490   IF padre = P_NULO THEN 
4500     A_RAIZ = nuevo
4510   ELSE 
4520     IF ArrIzq(padre) = nodo THEN ArrIzq(padre) = nuevo
4530     IF ArrDer(padre) = nodo THEN ArrDer(padre) = nuevo
4540   END IF 
4550   ArrIzq(nodo) = P_VACIO
4560   ArrDer(nodo) = P_VACIO
4570 END DEFine 
4580 :
4590 REMark --------------------------------------------------------------
4600 REMark -- ARBOL_CAMBIA -- Cambia el tama‰o del arbol             --
4610 REMark --------------------------------------------------------------
4620 DEFine PROCedure ARBOL_CAMBIA(tam)
4630   LOCal tEle(A_TAM),tIzq(A_TAM),tDer(A_TAM),tTam,tRaiz,tNro,m1,m2,i
4640   :
4650   REMark Guardo el arbol en el auxiliar de forma compacta
4660   tRaiz = A_RAIZ
4670   tNro  = A_NRO
4680   tTam  = A_TAM
4690   m1    = 0      : REMark Ultimo elemento libre de la lista
4700   FOR i=A_TAM TO 0 STEP -1
4710     IF (m1 = 0) AND (tEle(i) <> P_VACIO) THEN 
4720       m1 = i + 1
4730     END IF 
4740     tEle(i)=ArrArbol(i)
4750     tIzq(i)=ArrIzq(i)
4760     tDer(i)=ArrDer(i)
4770   END FOR i
4780   :
4790   REMark calculo tama‰os m“nimos
4800   m2 = A_NRO + A_FACTOR
4810   IF tam < m2       THEN tam = m2
4820   IF tam < A_FACTOR THEN tam = tam + A_FACTOR
4830   IF tam < m1       THEN tam = m1 + A_FACTOR
4840   :
4850   REMark Creo el nuevo arbol y lo relleno
4860   ARBOL_NUEVO tam,A_FACTOR
4870   :
4880   A_RAIZ = tRaiz
4890   A_NRO  = tNro
4900   FOR i=0 TO m1-1
4910     ArrArbol(i) = tEle(i)
4920     ArrIzq(i)   = tIzq(i)
4930     ArrDer(i)   = tDer(i)
4940   END FOR i
4950 END DEFine 
4960 :
4970 :
4980 REMark --------------------------------------------------------------
4990 REMark -- n = ARBOL_NIVELES -- Retorna el nro de niveles del arbol --
5000 REMark -- RETORNA: Nivel maximo del arbol                          --
5010 REMark --------------------------------------------------------------
5020 DEFine FuNction ARBOL_MAX_NIVEL
5030   RETurn nivel_inorden(A_RAIZ, 0)
5040 END DEFine 
5050 :
5060 DEFine FuNction nivel_inorden(nodo,actual)
5070   LOCal n1,n2
5080   :
5090   IF nodo = P_NULO THEN 
5100     RETurn actual
5110   ELSE 
5120     n1 = nivel_inorden(ArrIzq(nodo),actual+1)
5130     n2 = nivel_inorden(ArrDer(nodo),actual+1)
5140     IF (n1 > n2) THEN RETurn n1 : ELSE RETurn n2
5150   END IF 
5160 END DEFine
 


Para poder verificar que el árbol funciona uso un pequeño programa de pruebas, en el se ve siempre el árbol y sus enlaces izquierdo y derecho, los punteros nulos, los elementos libres, etc. Tras cada prueba se presenta el árbol y la lista de elementos ordenados que se obtiene del mismo.

100 REMark ----------------------------------------
110 REMark -- Carga                              --
120 REMark ----------------------------------------
130 MODE 4: PAPER 0 : CLS
140 INPUT "Cual prefiere (1)=Simple",t$
150 IF t$<>"1" THEN GO TO 200
160 n$="mdv1_ed_arbol_arreglo" & t$
170 PRINT "Cargando ";n$
180 MERGE n$
190 REMark ----------------------------------------
200 REMark -- Rutinas de pruebas                 --
210 REMark ----------------------------------------
220 MODE 4: PAPER 0 : CLS : LET No=0 : LET Si=1
230 p2$=""
240 t1=DATE
250 :
260 PRINT "Creacion del arbol"
270 crear : ver : PRINT
280 :
290 PRINT "PRUEBA 1: Introduce elementos en orden, inversos y aleatorios"
300 crear : FOR i=1 TO 5         : mete(i)          : END FOR i : verarbol
310 crear : FOR i=5 TO 1 STEP -1 : mete(i)          : END FOR i : verarbol
320 crear : FOR i=1 TO 10        : mete(RND(1 TO 9)): END FOR i : verarbol
330 :
340 PRINT "PRUEBA 2: Introduce 9, elimina 5, introduce 3, elimina 4"
350 crear
360 FOR i=1 TO 9   : mete(i)
370 FOR i=1 TO 5   : borra(i)
380 FOR i=10 TO 12 : mete(i)
390 FOR i=9 TO 11   : borra(i)
400 verarbol
410 :
420 PRINT "PRUEBA 3: Introduce 9, Extrae 2, introduce 10 y reduce"
430 crear
440 FOR i=1 TO 9   : mete(i)
450 FOR i=1 TO 2   : borra(i)
460 FOR i=10 TO 19 : mete(i)
470 verarbol
480 PRINT "CM "; : ARBOL_CAMBIA 0 : ver : verarbol
490 :
500 PRINT "PRUEBA 4: Buscar algunos elementos"
510 crear
520 FOR i=1 TO 9   : mete(i)
530 FOR i= 0 TO 13 STEP 3
540   PRINT "BUSCO ";i;" = ";ARBOL_BUSCAR(i)
550 END FOR i
560 PRINT
570 :
580 PRINT "PRUEBA 5: Extrae elementos hasta error por vacia"
590 FOR i=1 TO ARBOL_LEN : borra(i)
600 t2 = DATE : PRINT "Tarda ";t2-t1;" segundos"
610 borra(0)
620 STOP
630 :
640 :
650 DEFine PROCedure crear
660   ARBOL_CREAR
670 END DEFine 
680 :
690 DEFine PROCedure mete(a)
700   PRINT "EN ";a;":";
710   ARBOL_ADD(a)
720   ver
730 END DEFine 
740 :
750 DEFine PROCedure borra(a)
760   PRINT "BO ";!a;"(";ARBOL_BUSCAR(a);"):";
770   ARBOL_DELETE(a) : ver
780 END DEFine 
790 :
800 DEFine PROCedure verarbol
810   PRINT "ARBOL: ";ARBOL_VER$(0) : PRINT
820 END DEFine 
830 :
840 DEFine PROCedure ver
850   LOCal xx
860   :
870   PRINT "[";ARBOL_LEN;"x";ARBOL_NIVELES;"]";
880   IF A_RAIZ=P_NULO THEN PRINT "*"; : ELSE PRINT A_RAIZ;":";
890   FOR xx=0 TO A_TAM
900     PRINT !"(";xx;")";ArrArbol(xx);
910     IF ArrIzq(xx)=-1 THEN PRINT "*";
920     IF ArrIzq(xx)=-2 THEN PRINT "v";
930     IF ArrIzq(xx)>0  THEN PRINT ArrIzq(xx);
940     IF ArrDer(xx)=-1 THEN PRINT "*";
950     IF ArrDer(xx)=-2 THEN PRINT "v";
960     IF ArrDer(xx)>0  THEN PRINT ArrDer(xx);
970   END FOR xx
980   PRINT
990 END DEFine 

Cuando ejecutéis las pruebas os daréis cuenta de que si introduzco los elementos de forma ordenada todos van a parar siempre a la rama derecha, quedando la izquierda vacía, por lo que tenemos una lista en lugar de un árbol. Cuando los introduzco de forma aleatoria se van llenando las ramas izquierda y derecha mas o menos a la par. Esto nos indica que un árbol binario de búsqueda solo será eficiente si los elemento se introducen al azar y producen un árbol en el que las ramas sean todas mas o menos del mismo tamaño, pues sin ese equilibrio pierde mucha efectividad en altas y bajas, peor lo que es peor, hace mas lentas las búsquedas, siendo nuestro objetivo que estas sean lo mas eficientes posibles. En la siguiente entrada montaremos arboles binarios de búsqueda equilibrados mediante las técnicas de rotación simple y doble, produciendo árboles AVR.

Como siempre aquí todo lo desarrollado sobre estructuras de datos hasta el momento, la parte de ordenación no ha variado.

lunes, 12 de diciembre de 2016

Variante del cable RGB de la SNES

Ha surgido una variante del cable RGB para las SNES, que no se si servirá para las Nintendo-64 con salida RGB o no. En esta entrada expliqué los cables de video existentes para las variedades de maquinas de nintendo con el mismo conector de salida, SNES/SNES 2/AV Famicom/N64/Game Cube, en ella explicaba que los cables deben no usar condensador para las SNES y si para las N64 y Cube, aunque esto hay que probarlo siempre ya que depende de la maquina y el televisor mas que de otra cosa.

Ahora ha surgido una variante del cable RGB para la SNES. Sabemos que la salida del euroconector o scart necesita cuatro señales para el manejo de vídeo, rojo, verde, azul y el sincronismo compuesto. Esta última señal se saca de la señal de vídeo compuesto habitualmente, pero se ha descubierto que es mejor obtener de la señal de luminancia, que también los incluye, y por las pruebas que he visto da un resultado mucho mejor (aunque no lo he podido probar todavía, pero las imágenes que se ven por Internet del cable que se ha denomiado Chekerboar dejan claro que la señal es mucho mejor. El cambio es muy sencillo, solo hay que sacar la señal  que va al pin 20 del SCART a través del pin 7 de la Nintendo, en lugar de a través del pin 5. Hay que mantener la resistencia entre el pin 7 y masa, que yo en mi imagen pongo entre los pines 18 y 20 del euroconector, pero que normalmente en los cables está en el conector de Nintendo.


No tengo constancia de si esta modificación serviría igualmente para las N64 (las que llevan soporte RGB que no son todas) y las Game Cube.

viernes, 9 de diciembre de 2016

Mas traducciones en la Wikipedia

He realizado algunas traducciones mas para la wikipedia, ya que considero que es un buen lugar para almacenar información que sea útil a todo el mundo, además siempre aprendo cosas nuevas.

  • Micromation fue una empresa americana de micro ordenadores, que fabricaba ordenadores multi usurio a base de montar un aplaca con un procesador para cada uno. Que yo sepa no llegaron a España, eran caros pero de lo mejor del momento.
  • Como me gusta mucho DEC y sus PDP (aunque no he tenido la suerte de usar nunca uno), he traducido la página sobre los DECmate, los microordenadores compatibles con los PDP-8.
  • Relacionado con lo anterior, el microprocesador Intersil 6100 era el corazón de los DECmate, una CPU de un PDP-8 en un solo chip, aunque mucho mas lento.
  • Relacionado con los PDP, las páginas para 12 bits y para 18 bits no estaban en español. También he añadido una plantilla para que enlace con todos los anchos de bits y la he ubicado en todas las páginas relacionadas.
Seguiré con otras traducciones que faltan muchas cosas de empresas y ordenadores antiguos que tanto me gustan.