La computación no es era prioritaria

miércoles, 26 de noviembre de 2008
Nota: Estuve un poco bocón en este post, vean la aclaración que agregué abajo. Por suerte no soy una institución periodística respetable.

En el marco del (un tanto hipócrita, es innegable) Año de la Enseñanza de las Ciencias, el Ministerio de Educación promueve el programa de becas Bicentenario, que consta de 30.000 cupos de ayuda financiera que oscilan entre los $415 y los $1000 al mes, dependiendo del grado de avance en la carrera, para las carreras científico-técnicas que se denominan prioritarias (según una lista que aparece en el propio sitio web).

Es curioso que, a pesar del formidable auge del sector informático, no haya ninguna carrera del área de computación en el listado citado más arriba (una extensa lista, que incluye cosas como Ingeniero de recursos naturales renovables para zonas áridas o Diseñador industrial). Al parecer se tomaron muy a pecho las palabras de Miguel Calello, presidente de CESSI (Cámara de Empresas de Software y Servicios Informáticos):
Podemos tener productividad y calidad pero no si no tenemos los profesionales, vamos a tener límites para el crecimiento (...) Necesitamos carreras más cortas y enfocadas a la industria y sus necesidades.

De modo que para nosotros, técnicos y cientificones de segunda no-prioritarios, nos pusieron (junto con CESSI, Sun, IBM, Microsoft, Oracle y Cisco) las super becas Ctrl+F, con las que podés acceder a la formación de tus sueños:
  • Microsoft Administrador de Bases de Datos SQL Server 2005 (1 mes)
  • Administración SOLARIS Nivel Inicial (2 meses)
  • Cisco System IT Essentials I (1 mes)
  • Y muchos más!

Personalmente me parece triste ver semejante falta de perspectiva en estos programas. La informática es un área con un crecimiento formidable en la Argentina, y es una de las pocas industrias en las que el factor humano hace toda la diferencia (y con él, la educación). Además En lugar de enfocar energías en un sector estratégico como este, se plantean becas para cursos de esclavo corporativo (útil sólo con la tecnología de la empresa que dicta los cursos).

Editado: Existen unas (de momento mucho menos publicitadas) becas para el área de sistemas. La página web no tiene dominio propio, ni hubo más publicidad que un mail que recibí de la directora del Departamento de Computación en la lista de alumnos del mismo. Me comenta Jorge Aliaga (el decano lee mi blog! :P) en un mail que se va a comenzar a difundir en breve.

Hacela corta

lunes, 24 de noviembre de 2008
Lo bueno, si breve, dos veces bueno

El intervalo de atención (o attention span) de una persona varía entre los 3 a 5 minutos para los niños hasta aproximadamente 20 minutos en adultos.

Siempre que se intenta comunicar algo, es una buena idea intentar ir al grano. Muchas veces una explicación larga puede resultar más clara que una corta, pero de poco sirve si la mayoría de las personas no van a tomarse el trabajo de leerla o escucharla.

El uso de vocabulario técnico tiene que ver con esta limitación. Tener un lenguaje preciso para cosas complejas permite ser más breve. Esta brevedad no solo permite comunicar más rápido, sino también de modo más efectivo, ya que hace que ideas complejas quepan dentro del intervalo de atención de los receptores. Sin embargo, el uso de vocabulario técnico restringe el alcance de lo que intentamos comunicar: solo aquellos que lo manejen van a entender lo que decimos.

Un ejemplo

Estos tres planteos son equivalentes:
  • "Supongamos que tomo un triángulo en el cual uno de sus ángulos es recto. Si tomo las longitudes de los dos lados más cortos del triángulo, las multiplico por sí mismas y las sumo, obtengo el mismo resultado que si multiplico por sí misma la longitud del lado más largo" (50 palabras)
  • "En un triángulo rectángulo, la suma de los catetos al cuadrado es igual al cuadrado de la hipotenusa" (18 palabras)
  • "Vale el teorema de Pitágoras" (5 palabras)

El efecto que describo es bastante aparente: la primera versión es muy larga para leerla (da fiaca), la segunda requiere de vocabulario técnico, y la tercera requiere conocer de qué se está hablando de antemano. Todavía se puede mejorar aún más, y decir lo mismo sin ninguna palabra.

El minimalismo

La cuestión de la brevedad está estrechamente relacionada con el minimalismo. Como lo puso el genial Antoine de Saint-Exupéry, autor de El Principito, "parecería que la perfección se alcanza no cuando ya se ha agregado todo, sino cuando no queda más nada para quitar".

Pero sin duda, la mejor cita sobre el minimalismo, aquella que resume su espíritu así como también su forma, es la que uso para terminar este post.
Menos es más

Contrastes

jueves, 13 de noviembre de 2008
Todo es relativo, nada es absoluto.
La mente humana es adepta al contraste. Es difícil observar y calificar algo si no es por comparación con otra cosa. Sentimos frío al salir de una ducha caliente, la Coca-Cola parece desabrida después de un chocolate, es un placer pararse después de mucho tiempo sentado, así como lo es sentarse después de mucho tiempo parado.

Contrastes y fotografía

En fotografía es una preocupación usual el problema de separación: tenemos un objeto que queremos fotografiar, pero el fondo "queda feo" y nos arruina la imagen. Un estudio fotográfico es lo último en separación: nos permite elegir el fondo sobre el que aparecerá el sujeto. Sin embargo, hay muchos tipos de fotografía en los que el uso de un estudio no es viable. Objetos como árboles y montañas son difíciles de convencer, y la gente en la calle suele desconfiar cuando un extraño les pide que "los acompañe a un lugar".

¿Qué herramientas tenemos para separar?

La separación se produce por contraste de algún tipo. Existen muchos tipos de contraste, pero en particular nos interesa el contraste visual, que es aquel que afecta a la imagen como imagen, y más allá del significado que tenga.

Contamos con 3 herramientas primordiales para obtener contraste visual:
  • La profundidad de campo
  • El color
  • El valor o brillo


El contraste visual no es la única forma de contraste efectiva. La observación del contraste no-visual (el que podríamos llamar contraste de significado o contraste semántico) le valió a Spencer Platt el galardón World Press Photo of the Year de 2006.

Estrellas Mágicas

miércoles, 5 de noviembre de 2008
En PC++ hay personajes curiosos. Uno de ellos es DjGera, que hace unos días propuso este problema:

Ubicar los números del 1 al 16 de forma que todas las columnas, filas y diagonales sumen 34.

Como buen ser humano mi primer instinto es mirar el problema fijo a ver si se me ocurre una solución. Pasados 10 minutos me empieza a dar hambre y recuerdo que para algo estudio Lic. en Computación.

Rápidamente, hay 16! = 2.1e13 formas de poner los números en el dibujo. Si obviamos las rotaciones y reflexiones de una misma solución, quedan apenas 653 837 184 000 formas posibles (seiscientos mil millones aproximadamente). Si bien las computadoras de hoy son rápidas, los problemas con números de esta magnitud todavía no son razonables para tratarlos "a lo bruto".

Solución con Programación Lineal

Al mirar el problema uno piensa bastante rápido (o no) en esas clases de álgebra lineal y empieza a imaginar matrices ralas y triangulaciones. Las restricciones del tipo "esta variable y esta otra deben sumar tanto" son efectivamente lineales y por lo tanto pueden representarse de forma matricial. Sin embargo, el problema como está planteado no es un sistema lineal convencional, por dos razones:
  • Las variables son enteras, no reales
  • Las variables deben ser todas distintas

Con estos añadidos, el problema se sale de la programación lineal y entra en la programación entera, un área que es computacionalmente mucho más difícil. Estos temas son objeto de la materia Investigación Operativa que es una de las gemas del Departamento de Computación de la UBA. Desgraciadamente, todavía no tuve oportunidad de cursar esa materia. Pensándolo un poco llegué a la conclusión de que probablemente esta no fuera la ruta más sabia, pero Martín, un poco más piola y sobre todo mucho más optimista, me mostró que estaba equivocado.

La técnica para resolver el problema usando programación entera es esencialmente:
  1. Plantear la matriz asociada a las restricciones lineales
  2. Triangularla con el método de eliminación gaussiana
  3. Tras este paso, queda una matriz singular de rango 8
  4. Fijar 8 de las 16 variables en valores enteros de 1 a 16
  5. Resolver las 8 variables restantes; si sus valores son enteros, están entre 1 y 16 y son diferentes a los 8 valores elegidos en el punto anterior, encontramos una solución.
  6. Volver al paso 4 para cada valuación distinta de las 8 variables a fijar

El algoritmo es entonces una combinación de programación lineal con fuerza bruta, pero programado en Mathematica tarda unas 10 horas en hallar todas las soluciones posibles, lo cual es muy respetable.

Solución con Algoritmo Genético

Con el rabo entre las piernas frente a la completitud y elegancia de la solución propuesta por Martín, implementé un algoritmo genético para resolver el problema. Sin demasiado trabajo el algoritmo encuentra una solución muy rápido (en unos 5 segundos con Psyco). Este tipo de algoritmos no deja de sorprenderme, puesto que si se observa el código las heurísticas de mutación y apareamiento son totalmente primitivas, y sin embargo el rendimiento del mismo es excelente.

#!/usr/bin/python
# estrella.py
# Resuelve la estrella magica de 16 puntas con un algoritmo genetico.

import random
import sys

tam_poblacion = 400
natalidad = 0.15
mutacion = 0.5
max_generacion = 500

# restricciones lineales
m = [[0,1,3,4],
     [4,5,7,8],
     [8,9,11,12],
     [12,13,15,0],
     [14,15,1,2],
     [2,3,5,6],
     [6,7,9,10],
     [10,11,13,14]]

# funcion de aptitud
def fitness(cand):
    fit = 0
    for eq in m:
        fit_local = -34
        for j in eq:
            fit_local += cand[j]
        fit += abs(fit_local)
    
    # esto fuerza que el primer numero sea el 16
    # y filtra las rotaciones de la misma solucion
    if cand[0] != 16:
        fit += 1000

    return fit

# funcion de apareamiento
def cruzar(c1, c2):
    l = [c1,c2]
    random.shuffle(l)
    c1, c2 = l
    c = c1[:8]
    for each in c2:
        if not each in c:
            c.append(each)
    return c

# funcion de mutacion
def mutar(cand):
    # "ejercito" al generador pseudoaleatorio
    # esto mejora bastante la velocidad de convergencia!
    i1 = random.randint(0,15)
    i2 = random.randint(0,15)
    
    i1 = random.randint(0,15)
    i2 = random.randint(0,15)
    
    i1 = random.randint(0,15)
    i2 = random.randint(0,15)

    c = cand[:]
    c[i1], c[i2] = c[i2], c[i1]
    
    return c

def avanzar_gen(pob):
    nacen = int(tam_poblacion * natalidad)
    mutan = int(tam_poblacion * mutacion)

    # unos se aparean
    for i in range(nacen):
        papa, mama = random.sample(poblacion, 2)
        poblacion.append(cruzar(papa, mama))

    # nacen unos mutados
    for i in range(mutan):
        deforme = random.sample(poblacion, 1)[0]
        poblacion.append(mutar(deforme))

    # ordeno por fitness
    poblacion.sort(lambda x,y: cmp(fitness(x), fitness(y)))
    
    # mato a los menos aptos
    while(len(poblacion) > tam_poblacion):
        poblacion.pop()
    

numeros = range(1,17)

# inicializador de poblacion
def init_pob():
    poblacion = []
    for i in range(tam_poblacion):
        cand = numeros[:]
        random.shuffle(cand)
        poblacion.append(cand)
    return poblacion


if __name__ == '__main__':
    while True:
        print
        print "Comenzando simulacion..."
        gen = 0
        poblacion = init_pob()
        min_fit = 1000
        while min_fit !=0:
            avanzar_gen(poblacion)
            gen += 1
            f = fitness(poblacion[0])
            
            if f < min_fit:
                print "Fitness: %s (gen %s)" % (f, gen)
            min_fit = f
            
            if min_fit == 0:
                print "Eureka!"
                print poblacion[0]
                sys.exit(0)
            if poblacion[0] == poblacion[len(poblacion)-1] or gen >= max_generacion:
                break
La ejecución se ve aproximadamente así (con un poco de suerte!):

gomo@ciabatta:~$ time python estrella.py

Comenzando simulacion...
Fitness: 30 (gen 1)
Fitness: 18 (gen 4)
Fitness: 16 (gen 10)
Fitness: 10 (gen 15)
Fitness: 8 (gen 30)
Fitness: 6 (gen 44)
Fitness: 4 (gen 47)
Fitness: 2 (gen 99)
Fitness: 0 (gen 237)
Eureka!
[16, 3, 11, 2, 13, 7, 14, 9, 5, 10, 1, 15, 4, 6, 12, 8]

real 0m2.449s
user 0m2.420s
sys 0m0.028s
Por su naturaleza, el tiempo que insume el algoritmo genético es muy variable y no encuentra siempre la misma solución. Por esta razón el programa hace varios intentos en lugar de perseverar con la misma simulación si observa que está tardando mucho en encontrar una solución.

Agregado el 10/12/2008
Solución con Backtracking

Tras discutir en un foro, considero que es mejor aclarar lo siguiente: los algoritmos propuestos arriba no son ni de cerca los más eficientes que se conocen para este problema. Un simple algoritmo de backtracking encuentra una solución de forma certera y bastante más veloz que lo que propongo arriba.

El interés del post era mostrar dos técnicas interesantes para resolver el problema, sin ánimos de indicar que eran particularmente aptas o buenas para la tarea. A modo de ilustración, adjunto el código del algoritmo de backtracking.

def buscarSolucion(actual, restantes):
    if restantes == []:
        return actual
    else:
        for r in restantes:
            nuevo_act = actual + [r]
            nuevo_rest = restantes[:]
            nuevo_rest.remove(r)
            
            s = None
            if esValidoParcial(nuevo_act):
                s = buscarSolucion(nuevo_act, nuevo_rest)
                
            if not s is None:
                return s
            

def esValidoParcial(perm):
    l = [[0,1,3,4],
         [4,5,7,8],
         [8,9,11,12],
         [12,13,15,0],
         [14,15,1,2],
         [2,3,5,6],
         [6,7,9,10],
         [10,11,13,14]]

   
    for rest in l:
        s = 0
        c = 0
        for k in rest:
            if len(perm) > k:
                s += perm[k]
                c += 1
        
        if c == 4 and s != 34:
            return False
        elif c < 4 and s >= 34:
            return False
    
    return True

if __name__ == "__main__":
    numeros = range(1,17)
    print buscarSolucion([], numeros)

Flashback: Plasma!

lunes, 3 de noviembre de 2008
En mi colegio secundario para la prueba de bachillerato (francés) con orientación científica existe lo que se conoce como TPE (Travaux Personnels Encadrés o Trabajos personales guiados) que es esencialmente un proyecto de investigación que debe desarrollarse en grupos de 2 o 3 personas sobre algún tema de interés.

En 2003 yo estaba muy entusiasmado con el fusor de Farnsworth-Hirsch. Había estado mirando páginas de Internet en varias tardes de ocio y me parecía super interesante. Fue entonces que vi en el TPE la oportunidad de profundizar un poco más.

¿Qué es el fusor de Farnsworth-Hirsch?

Esencialmente, se trata de un tipo de reactor de fusión nuclear. La fusión nuclear es la reacción nuclear opuesta a la que se utiliza en las plantas nucleares actuales (la fisión). En lugar de partir grandes átomos en otros más pequeños, se unen átomos pequeños para formar otros más grandes. Las reacciones de fusión son las que hacen que brille el sol y las demás estrellas, y tienen numerosas ventajas sobre las de fisión. En particular, el combustible para la fusión (así como los productos de la reacción) son comparativamente muy limpios. Lejos de ello están cosas como el uranio, el plutonio y otros elementos radioactivos de una planta nuclear convencional.

¡Qué bueno! Pero hay un problema: a los humanos no nos sale la fusión. Si bien la bomba de hidrógeno funciona gracias a la fusión, resulta difícil lograr una reacción en un entorno controlado que pueda ser usada para la generación de electricidad. Si bien puede lograrse fusión en un reactor, llegar a este punto insume más energía de la que el reactor genera.

El fusor es una variante de reactor de fusión que hoy por hoy se considera no viable: su diseño es inherentemente incapaz de producir una reacción de fusión autosostenida. Sin embargo, el fusor si puede hacer otras cosas, en particular:
  • Producir reacciones de fusión (no autosostenidas), y sobre todo
  • Ser construído por un adolescente!


El cacharro

Nuestro aparato constaba de 3 partes esenciales, de izquierda a derecha en la foto:
  • Una bomba de vacío
  • Una cámara de vacío con el "reactor" dentro
  • Un generador de alto voltaje (hasta 5000V)




Fue así como pusimos manos a la obra con nuestro modelo. Pronto fue aparente que dados los elementos que teníamos, lograr la fusión de átomos en nuestro aparato era imposible. Sin embargo, contábamos con lograr un muy fotogénico plasma (estado de gas luminoso que adquiere la materia de camino al punto de fusión).



Trabajamos bastante armando el dispositivo pero después de varias pruebas todo parecía derrumbarse: no se vislumbraba absolutamente nada adentro del reactor. Sabíamos que la bomba de vacío no tenía la potencia suficiente, y que el generador no producía la tensión suficiente para lograr fusión, pero contábamos con que apareciera el bendito plasma luminoso para consolarnos. Desgraciadamente no se veía absolutamente nada.

Un viernes las cosas cambiaron. Cito mi antiguo post:
Bombeamos entonces la cámara, como ya era costumbre, aunque sin esperanzas. La bomba de vacío, cuando está encendida, hace un ruido característico que disminuye y se apaga cuando se obtiene un cierto nivel de vacío. Pasado este nivel, comienza un nuevo ruido, no tan fuerte como el primero, y más metálico y liviano. Normalmente nos quedábamos en este punto. Hoy, tras bombear unos 5 minutos, la bomba nuevamente dejó de hacer ruido: fue entonces que pensé que tal vez ahora sí habíamos obtenido un vacío decente. Supongo que la grasa permitió un sellado perfecto de las juntas permitiéndonos alcanzar estos niveles. A todo esto, y durante la preparación, la profesora de física, que estaba evaluando los otros proyectos, nos advirtió que la llamáramos antes de encender nada, cosa que era un poco superflua dado que las últimas veces habíamos trabajado bastante sin supervisión, aunque también sin resultados. Cuando encendí la fuente y ví que aparecían las primeras chispas en el electrodo interno, supongo que entendí a Arquímedes cuando gritó ¡Eureka! :)




En el aula se suscitó una pequeña conmoción, con compañeros y otros profesores que vinieron a ver lo que ocurría. Si bien el logro científico era de bajo calibre, el impacto visual del plasma, sumado a la adrenalina (ya que lo único que sabíamos con certeza era que estábamos usando 5000V y vidrio presurizado, ambas cosas con amplia capacidad de matarnos en caso de una eventualidad) hizo que fuera un momento muy especial.

3 implementaciones de Fibonacci

sábado, 1 de noviembre de 2008
En la charla sobre técnicas algorítmicas usé el algoritmo para calcular números de Fibonacci para mostrar como se podía mejorar la eficiencia de un programa utilizando la técnica de programación dinámica. El algoritmo trivial de Fibonacci utiliza recursión múltiple. Esto produce una cantidad exponencial de llamadas, lo que resulta en un algoritmo de complejidad O(2n).
def fibo1(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibo1(n-1) + fibo1(n-2)
La técnica de Programación Dinámica consiste en resolver primero subproblemas que están contenidos dentro del problema total, y luego servirse de las soluciones a los subproblemas para resolver el problema total.

Un ejemplo sencillo es el problema de obtener un camino mínimo entre dos puntos. El popular algoritmo de Dijkstra para caminos mínimos utiliza la técnica de programación dinámica.

Para el caso de Fibonacci, los subproblemas son los números de Fibonacci más pequeños que el que queremos calcular. En la implementación anterior, estos números se obtienen con llamadas recursivas. Sin embargo, si comenzamos calculando desde los números de Fibonacci más pequeños y con ellos vamos construyendo los más grandes, se puede realizar el cálculo en O(n).
def fibo2(n):
  if n == 0 or n == 1:
      return 1
  else:
      nm1 = 1
      nm2 = 1
      i = 1
      while i < n:
          nm1, nm2 = nm2, nm1 + nm2
          i = i+1
      return nm2
Un tiempo después Fede me comentaba sobre un algoritmo de Divide & Conquer que permite calcular aún más rápido los números de Fibonacci.

El algoritmo se basa en la siguiente identidad (donde Fn es el enésimo término de la sucesión o secuencia de Fibonacci):



Como existe un algoritmo de Divide & Conquer para elevar un número (o en este caso, una matriz) a una cierta potencia, nos podemos servir de él. Este algoritmo de potenciación es la función aLaN() en el código que sigue. Gracias al mismo, podemos calcular números de Fibonacci en tiempo O(log n).
def fibo3(n):
    # esta funcion multiplica 2 matrices de 2x2
    def multiplicar(m, n):
        return [m[0]*n[0]+m[1]*n[2],
                m[0]*n[1]+m[1]*n[3],
                m[2]*n[0]+m[3]*n[2],
                m[2]*n[1]+m[3]*n[3]]
    # esta funcion eleva una matriz de 2x2 a la k
    # usando el algoritmo de D&C
    def aLaN(m, k):
        if k == 0:
            return [1,0,0,1]
        elif k == 1:
            return m
        else:
            if k % 2 == 0:
                return aLaN(multiplicar(m,m),k/2)
            else:
                return multiplicar(aLaN(multiplicar(m,m),k/2),m)
    
    inicial = [1,1,1,0]
    return aLaN(inicial, n)[0]
Esto permite ver que el correcto uso de técnicas algorítmicas puede mejorar sustancialmente el rendimiento de los algoritmos. Si bien el programa presentado es de juguete, el conocimiento de estas técnicas puede abrir nuevas posibilidades a la hora de desarrollar software.