/algoritmos de sorting II

Hubo un algoritmos de sorting en este blog, a diferencia del anterior, estos applets de xSortLab va de dos modos (hay una tercera, pero no es la mas relevante), uno visual, que muestra paso a paso el ordenamiento de 16 elementos, y una comparativa de sus tiempos de ejecución.
En la primera aparece debajo una línea detallando la 'instantánea' del momento.
Es bastante didáctico porque las diferencias entre los diferentes métodos son evidentes.
Los métodos que se muestran son: el método de la burbuja, ordenación por selección, por inserción, por intercalación (MergeSort) y ordenamiento rápido (QuickSort).

/fox pro en dos monousuario -> red

Es lo que hay valor, eso me tocó en el trabajo. No estoy acostumbrada a trabajar con tablas .dbf, estoy acostumbrada a manejar la concurrencia mediante transacciones. Pero a lo hecho pecho.

Primera estrategia, usar una tabla 'candando', que se llama 'candado.dbf', su única misión es actuar de semáforo para gestionar los accesos concurrentes las tablas. No se bloquean las tablas a acceder, sino el 'candado'.
Ventajas: no atosigar tanto las otras tablas, dar velocidad de consulta.
Desventajas: puede hacerse por fuera de la aplicación, pero las probabilidades que suceda son bajas.

Importante, poner SET EXCLUSIVE OFF en el config.fp o en un archivo del proyecto.
Estos fueron los mayores cambios:
1.- Ruta de Archivos (Prg Bases de Datos y tablas)
--- Set Default to
--- Set Path to
2.- Quitar la Exclusividad de la Base de Datos
--- Set Exclusive Off

PROCEDURE CANDADO_ON
    UNLOCK ALL                &&    Por seguridad
    IF  !USED("CANDADO")
        USE CANDADO IN 0
    ENDIF

    PRIVATE XSR
    XSR=SET("REPROCESS")
    SET REPROCESS TO 1
    DO WHILE !FLOCK("CANDADO")
        DO CINFORME WITH "Los archivos est n en uso...\n\n"+;
            "Toque ENTER para reintentar ya, o espere a que esta "+;
            "ventana se vaya y reintente sola.",2
    ENDDO
    SET REPROCESS TO (XSR)


PROCEDURE CANDADO_OFF
    UNLOCK ALL

Uso:
=candado_on() && en realidad bloque la tabla 'candado.dbf'
insert/append
= candado_off()

No puede usarse con el comando ZAP (vaciar tabla) ya que exige abrir la misma en modo exclusivo, y la tabla queda para ser accedida en forma exclusiva y no pueda compartirse, aun cuando SET EXLUSIVE = OFF. Por lo tanto no libera al usuario de ese recurso, y si algun usuario intenta acceder a la tabla 'zapeada', sale el siguiente mensaje: "File access denied"

Generalmente estas tablas eran usadas para información de reportes, por lo cual opté por crear tablas locales a cada terminal para ahorrarme este problema.
Estas tablas se cargan mediante el resultado de una sentencia SQL (hay un borrado implícito: el resultado de la consula, evitamos usar ZAP).

Hasta la versión 7 de FoxPro no salieron los cursores READWRITE los cuales me hubieran evitado usar tablas, que no son temporales, pero sí locales.
En teoría para FoxPro 2.5 DOS los cursores pueden escribirse/borrarse/indexarse, de hecho lo usé, y me anduvo en modo monousuario pero no se porqué tuve problemas al hacerlo en concurrencia. Concretamente al indexar, mensaje de error: "a read-only file"

No tengo tiempo de investigar el motivo, ni mucho menos me motiva hacerlo en FoxPro, decidí cambiarlo por tablas y se solucionó.

De momento ni siquiera la ORT ha montado la red para probar lo que estoy haciendo, ergo, la forma de testearlo es llamando la aplicación dos veces. Y para probar el ruteo de los archivos (hacia el supuesto servidor) ubiqué los ejecutables en diferentes carpetas.
Los ejecutables son los mismos para cada terminal (servidor y cliente), lo que varía es el archivo de configuración Config.fp en cada máquina.
Al menos algunos problemas de concurrencia han salido a la luz probándolo de esta forma, pero está lejos de lo óptimo como testeo.
Aqui el resultado de la misma aplicación llamada desde diferentes lados:

/language is a virus - anymails

Anymails es el proyecto de tesis de Carolin Horn (diseño & concepto) y Florian Jenett (código) realizado en Flash/Processing, para el Dynamic Media Intitute Boston (2007). El mismo traza una metáfora visual del contenido de los emails recibidos con un ecosistema de organismos (que se mueven como si nadaran, forman grupos, cambian de tamaño, de color, formas, etc).
El objetivo es ver el mundo de nuestros emails desde otra experiencia.

Los emails individuales se representan por un microbio, las edades (su antiguedad) por el tamaño y opacidad (los mas nuevos grandes y opacos, los mas viejos chicos y transparentes). Así mismo podemos ver colonias de microbios, agrupados por 'familia', 'propaganda', etc. Los diferentes mails se categorizan por colores y tamaños.

Hay una barra horizontal que representa el tiempo, podemos navegar a través del tiempo para ver los diferentes tipos de mails, es interesante la posibilidad de encontrar patrones de comportamiento en diferentes momentos.

Tanto la tesis como el código pueden descargarse desde el propio sito.

Hay mas imagenes y videos (muy buenos) aqui pueden ver uno, es necesario QuickTime.


Mi envío de mails se ha restringido, el spam y las cadenas me resultan tediosos, los mails sin copia oculta también, todo suma y hace que cada vez más limite mis mails , o al menos a dar mi email fácilmente. Este proyecto plasma, sin ser su propósito quizás, algo tangencial, el (sobre)abuso de info y de 'vínculos' que nos exceden más de lo que probablemente podemos digerir. En la idea de este proyecto sobrevuela, al menos creo yo, un replanteo de su uso.

vía notcot

/leyendo (recursivamente) con fscanf

El 29/08 escribía este post sobre mis problemas para entender fscanf. No es que haya sacado mucho mas en limpio, pero a ensayo y error y leyendo algun que otro man, pude entender al menos lo necesario para resolver el problema.
En general la información o es mas bien críptica o demasiado trivial, por eso dejo un ejemplo concreto, otro más.

La solución fue recursiva nomás. La única restricción es que debía ser llamada dentro de otra función a la cual hay que respetarle el cabezal o su firma.

Para recordar, el formato del archivo a leer es de este tipo:
(Ar 3 (C 2 (d 5) (F 6))(juan 4 )(Ale 5 (Ana 3)))
Entre dos paréntesis consecutivos )) puede haber cualquier cosa, la cual debe ser filtrada.

Arbol* leer(char const* ruta)// firma a respetar.
{
   FILE *fp;
     
   fp = fopen(ruta,"r");
   Arbol* arbol = NULL;  
           
   if (fp)  
   {       
    arbol = getArbol(fp,arbol);        
    fclose(fp);       
   }

   return arbol;
}

Arbol* getArbol(FILE *f, Arbol* a)
{
  
   char c;
   char nom[largoNombre];
   char lin[512];   
   int nro; 
      
   Arbol* arbol = NULL;
   Arbol* subArbol = NULL;
      
   if (!feof(f))
   {       
    fscanf(f,"%[^()]",lin); // leo lo que haya ANTES de ( ó )
        
    fscanf(f,"%c",&c);  // lee los paréntesis    
    if (c == '(')  // hay un nodo del arbol
        {        
            
            fscanf(f," %s %d ",nom,&nro);                
            arbol = arbolCrear(nom,nro);
              
            subArbol = getArbol(f,arbol); //llamo c/hijos           
            subArbol = getArbol(f,a); //llamo con padre a leer hnos
                                    
            if ((a != NULL) && (arbol != NULL))            
                arbolCambiarPadre(arbol,a); //agrega al arbol                          
        }    
   }  
   return arbol;
}   

Notas:

• no es necesario pasar por referencia el puntero a arbol porque la raíz no cambia.
• fscanf(f,"%[^()]",lin) puede sustituirse por fscanf(f,"*[^()]"), el * indica que lo leído no se almacene en ninguna variable. Como desconocía las consecuencias de leer asi, sin almacenar, decidí optar por la primera. El símbolo ^ saltea blancos, tabuladores, nueva línea y espacios.
• Otra forma de leer lo mismo hubiera sido fscanf(f," ( %s %d ",nom,&nro)los espacios en blanco son para contemplar el caso que el string o entero inmediato se encuentren después de una nueva línea (algo que puede darse), salvo esa restricción, no vi necesario el espacio entre %s y %d.
  
• fscanf(f," %s %d ",nom,&nro). El espacio en blanco saltea nueva línea, tabuladores, los espacios que haya, no importa cuantos, basta poner uno saltea los que haya hasta que encuentre una coincidencia que se ajuste al parámetro de lectura.
• El carácter "(" es la condición de parada de la recursividad, se terminaron de leer los hijos del nodo actual, se pasa a leer los hermanos del mismo.
  

Dada la recursividad de la estructura, la función escritura también fue recursiva.

void arbolEscribir(Arbol* arbol,FILE* f)
{
    
    char* nombre = new char[largoNombre];    
    nombre[19] = '\0';
    Arbol* hijo;
    int cant_hijos,k;    
    
    if (arbol != NULL)
    {
        fputs("(",f);
                    
        arbolNombre(arbol,nombre);                
        
        fprintf(f,"%s ",nombre);
        fprintf(f,"%d",arbolNumero(arbol));
        
        cant_hijos = arbolCantHijos(arbol);        
        
        for (k = 0; (k <>
        {
            hijo = arbolHijo(arbol,k);            
            arbolEscribir(hijo,f);            
        }            
        fputs(")",f);
    }    
}
      
// Guarda arbol en formato de s-expresión en el archivo ruta.
void escribir(Arbol* arbol, char const* ruta)
{   
   FILE *fp;
   
   if (arbol == NULL)
   {
      printf("El arbol esta vacio, no hay arbol para guardar\n");
      return;
   }      
      
   if( NULL == (fp = fopen(ruta, "w")) )
   {
      printf( "ERROR: No se pudo crear el fichero, %s\n",ruta);
      return;
   }      
   
   arbolEscribir(arbol,fp);
   fclose(fp);         
}

/otro buscador de código (C++)

Se trata de codecogs está en fase beta, de registro gratuito que permite compartir código C++ orientado a la estadística, matemática, ciencas exactas y finanzas. La idea es crear una base de datos con código Open Source. Aunque hay de varias licencias. El sitio está catalogado segun las diferentes áreas, tiene un foro, un buscador, y cualquier usuario registrado puede subir código. Digamos que por ahora es una especie de foro algo mas especializado, ideal para la enseñanza de ciertos algoritmos, vale la pena seguirlo creo.

/Sudoku en Delphi

mis rollos con Delphi
Como saben me gusta Delphi, es fuertemente tipeado, prolijo, su Object Pascal no es lo mejor (aunque en versiones posteriores a la 7 se ha mejorado), no es fuertmente OO, el motivo básicamente es que se descansa en su RAD, precisamente porque tiene una paleta de componentes muy amplia, y muchas de ellas gratuitas y con licencias muy abiertas, ejemplo de esto son los componentes Jedi, Indy, Zeos o GLScene por mencionar algunos. Es orientado a eventos, a los de sus propios componentes, que si, son clases, pero hace que la mayoría de sus aplicaciones no se base en el paradigma de la OOP estrictamente.

Sin embargo creo que para Win32 Delphi 7 es una excelente opción para desarrollar, claro, perdemos transportabilidad a otros lenguajes que basan su desarrollo en una OOP mas estricta, como suele ser Java o C#, o bien C++.

Actualmente existe Lazarus, un Object Pascal 'basado' en Delphi que corre tanto bajo Windows como Linux, quienes lo han probado dicen que el traslado de un código desde Delphi a Lazarus prácticamente ni se siente, sin embargo admiten que el producto aun no es lo suficientemente maduro.

en tema: sudoku
En el blog de Seoane encontré una implementación de Sudoku, su algoritmo me pareció mejor que los anteriores que mencioné aqui y aqui, esto sin analizar demasiado, por lo que puedo equivocarme, pero intenta no aplicar backtracking donde puede, evitando el gran consumo de recursos que conlleva esta técnica.

(Su lógica es muy clara y su sintaxis similar a muchas otras de otros lenguajes, lo que hace de este algoritmo fácilmente extrapolable a otros lenguajes)

Voy a implementarlos a los 3 y ya comentaré.


vía Seoane

/análisis de algoritmos - libro

Este libro en formato digital (pdf) y en español andaba circulando cuando cursé P3. Fue escrito por catedráticos de la universidad de Málaga, aunque desconozco a sus autores.
Aborda de manera bastante clara, y sin perder rigurosidad los siguientes temas:

• las diversas técnicas de algoritmos (programación dinámica, backtracking, divide&vencerás, algoritmos voraces)
• técnicas de ordenación
• estudio sobre cáclulo de ordenes de los algoritmos (complejidad y eficiencia)

Abunda en ejemplos, y algunos problemas tipo como el problema de la mochila, o el de dar cambio son resueltos aplicando las diversas técnicas para resaltar las diferencias entre ellas.
Los ejemplos están escritos en Modula-2 (muy similar a Pascal), ergo, son fácilmente extrapolables a otros lenguajes.

A propósito, encontré este sitio que trata de manera algo básica esos temas, pero sirve como lectura introductoria algoritmia.net

(El libro también está en sección 'Estantería')

Este libro es complementario de otros que recomiendo:

• Estructura de datos y algoritmos - Alfred Aho, Jonh Hopcroft y Jeffrey Ullman
• Fundamentos de Algoritmia - G. Brassard y P.Brantley

No todo es software de gestión, aplicaciones variadas como video juegos, o donde sea necesario optimizar alguna función objetivo hacen uso de estas técnicas.


Box.net

/bits + software = arte

(Actualizado)
Las piezas de arte que nacen como consecuencia de conjugar variables que 'parecen' tan disímiles como tecnología, algoritmos, modelado de datos y la estética, tienen para mi un poderoso atractivo semántico. Por un lado, nos advierte de la potencialidad de la tecnología, como reinterpeta lo circundante, como puede codificarlo torpemente para 'entenderlo', ya sea por un sensor que capta un movimiento, una luz, o bien cómo los datos se transforma en imágenes, etc. Y por otro, como el dominio de la misma hace posible traducir ese mundo binario en un concepto que llega visualmente limpio al receptor humano.
Tecnología mediante es posible interactuar con muchas de estas obras, estableciendo así un vínculo entre el receptor y la obra, que hace al primero formar parte de la misma. Retroalimentación desde lo emocional y sensorial, un concepto mas amigable-humano para interactuar con la tecnología, no sustituye, sino que amalgama. Aleja el fetichismo que la tecnología a veces pareciera tener para algunos, interesante.

Aqui una breve muestra de algunos de estos artistas que mediante una combinación de software, circuitos, cámaras de video, computadoras, logran efectos interesantes.
(Algunas de los obras tienen el link donde se muestra la interacción, QuickTime necesario)

(Nota: Hay restricciones para acceder directamente al link por artista como puse originalmente, dejo el enlace a los artistas)

Daniel Rozin, círculos laminados, cámara de video, motores, computadora, software (obra interactiva, hay demo)



Objetos desechados, vídeo, software, computadora, electrónica, chapeado (obra interactiva, hay demo).




Manferd Mohr uno de los pioneros en usar la computadora para generar piezas de arte, comenzó en 1968. (obra interactiva, hay demo).
Nunca pensé que me gustaría la combinación casi minimalista del verde y el negro que hace Mohr.

vía bitforms

/diseño de patrones

Aqui hay un link a varios patrones conocidos implementados en C++ y Java, incluye los diagramas UML de los mismos, y están catalogados de acuerdo a los efectos de su aplicación en el modelo de clases (estructurales, creacionales, comportamiento,etc).
Particularmente interesante también, para notar las diferencias de los lenguajes y su manejo de punteros. (En el caso de Java la referencia a los mismos es explícita)

Pronto subiré mi implementación de Colecciones en C++ usando el patrón Iterator.

/fancy física

Working Model, ni idea del costo, leí por ahí unos USD80.000, no se si es correcto.
Este programa permite armar modelos y demostrar su funcionamiento. Prácticamente un laboratorio virtual de física, y flexible como para ejemplificar bastante cada situación, según se modifique el modelo y sus interacciones.
El programa responde a estímulos: la presión sobre la pizarra (cuando se dibuja), y a cómo se superponen las formas sobre la misma, para autocompletar lo dibujado, pero hace más, pone en funcionamiento los modelos diseñados (aquí es donde está el poder didáctico de esta aplicación).

Una explicación grotesca, es que el dispositivo tiene un mecanismo de sensores, uno en el marcador, otro en la pizarra, ambos conectados a una computadora, al igual que el proyector que apunta a la pizarra, entonces cada vez que se presiona sobre la pizarra, el proyector 'dibujará' donde se encuentra el marcador.






vía metacafe

/algoritmos de sorting

Aqui se muestra una comparativa visual sobre como funcionan diferentes técnicas de algoritmos de sorting (ordenamiento). Basta hacer click para ver cómo va modificandose la estructura.
Podemos elegir varios a comparar: QuickSort, Bubble sort (método de la burbuja), Insertion sort (sort por inserción), etc.
El código fuente de todos los algoritmos fue hecho en Java y está disponible.

Si bien QuickSort parece ser el mas óptimo, con un orden proporcional a nlogn (aplicando técnica divide y vencerás), siempre debe haber un balance eficiencia-cantidad de recursos, y según la probablilidad de uso de cada algoritmo.


vía StumbleUpon

/cifrando mensajes

Francamente desconocía Enigma hasta que apareció en elAbra, Frank Spieß crea un simulador en Flash de la máquina Enigma de tres rotores (dependientes).
Enigma es la máquina que usaron los alemanes durante la 2da Guerra Mundial para cifrar mensajes (sistema que fue roto por los aliados).

Permite configurar las claves, elegir 3 rotores de 5, sus posiciones iniciales y teclear texto que es automáticamente cifrado (o descifrado) mostrando de forma visual qué camino recorre cada letra. También incluye opciones para enviar el texto cifrado a alguien por correo (me matan!).

Este un sistema es de encriptación simétrica: al encriptar "A" tenemos "B", entonces a la hora de encriptar (bajo los mismos parámetros) "B" nos da "A".

enc(A) = B entonces A = enc(B)
Suponiendo que enc(A) es la función de encriptación

Mezcla interesante de conceptos, máquinas de estado (ya que los rotores son dependientes) y encriptación.

input: "HOLAMUNDO" output: RXZRSRGZR con los rotores I,II,III y H,D,X sin streckers.

/sudoku en C++ (otra vez)

Ya había hablado de Sudoku, y hay muchos sitios para resolver Sudoku en C++ usando la técnica de backtracking, pero este sitio me gustó porque explica un poco más en detalle en lo que consiste ese tipo de algoritmos: una búsqueda en profundidad en el árbol de soluciones posibles (estados del juego), y así analizádolas va desarrollando la solución definitiva.
Si bien lo ataca vagamente, vale como una unión de conceptos interesantes.