Más charlas interesantes

martes, 30 de diciembre de 2008
Siguiendo (y terminando) con la línea del post anterior, les comento sobre otras tres muy buenas presentaciones que ví en los últimos días. Varias de ellas son en las Ted Talks, unas conferencias sobre temas diversos que se organizan anualmente bajo el motto "Ideas que vale la pena compartir" (Ideas Worth Spreading). TED cuenta entre sus expositores a personajes como Bono, Richard Branson, Bill Clinton, Frank Gehry, Lawrence Lessig (Creative Commons) y Steven Levitt (Freakonomics).

Jill Bolte Taylor, especialista en neurociencias, despertó una mañana sintiéndose extraña. No le tomó demasiado tiempo reconocer sus síntomas y darse cuenta de que estaba sufriendo un ataque cerebral. Así pudo observar desde adentro mientras todas las funciones de su cerebro iban dejando de funcionar, desde la destreza motora hasta la conciencia de sí misma. Tras los 8 años que le tomó recuperarse completamente de la apoplejía, Jill cuenta paso a paso su experiencia y como cambió su forma de entender el cerebro humano.

Sir Ken Robinson es especialista en creatividad, innovación y recursos humanos. En su charla ¿Las escuelas matan la creatividad? discute el modelo educativo actual y como éste probablemente no esté adaptado para las necesidades del futuro, ya que fue construído a imagen de las necesidades del mundo industrial. Postula con mucho carisma que las escuelas y universidades del futuro deberían incentivar la creatividad por sobre las aptitudes convencionalmente "escolares" como la habilidad de memorizar datos o ejecutar tareas sin errores.

Dan Pinks es el autor del libro "Una mente totalmente nueva" (A Whole New Mind), en el que plantea una idea compatible con la conferencia de Sir Ken Robinson. El subtítulo del libro pregona que las personas predominantemente diestras de cerebro (es decir, aquellas que realizan tareas relacionadas con el hemisferio derecho del cerebro, usualmente tareas creativas) van a ser mucho más valoradas en el futuro, en razón de varios cambios en la dinámica mundial que se están suscitando en este momento. Pinks escribió durante varios años los discursos del candidato presidencial americano Al Gore, así que tampoco le falta cancha para entretener a una audiencia, y discute las ideas generales del libro en una breve conferencia.

Hay un largo listado de de charlas de TED así como de Pop!Tech, suficientes como para perder un verano frente a la pantalla.

Espiral descendente vs. Mundo de posibilidades

lunes, 29 de diciembre de 2008
Hay una historia sobre dos vendedores de zapatos que son enviados a África a evaluar las posibilidades de desarrollo para el mercado de zapatos en el continente negro. El primer vendedor envía el siguiente telegrama: Situación irreparable STOP No usan zapatos. El segundo vendedor en cambio escribió lo siguiente: Magnífica oportunidad STOP Nadie tiene zapatos todavía. Esos mensajes no son descripciones de las circunstancias, sino expresiones de la actitud de los viajeros.
Con esa anécdota comienza Benjamin Zander su charla en Pop!Tech 2008. Zander es director de orquesta en la filarmónica de Boston y profesor de música, así como coach de liderazgo.

A lo largo de la charla, Zander hace subir al escenario a un joven de 15 años con su violonchelo, y mientras le explica en vivo como mejorar su interpretación, hace gala de un carisma y una soltura formidables para expresar su idea central: liderar es esencialmente mostrarle a los demás las posibilidades que están frente a ellos.

Es mi opinión que siempre es un placer ver a una persona hacer algo muy bien, no importa qué sea lo que está haciendo. Benjamin Zander es un maestro de las presentaciones, y como tal, es un placer destinarle media hora a ver una charla que inspira admiración. Su habilidad llega al punto de que Garr Reynolds lo llama el Maestro Zen de las presentaciones. Si lo prefieren, pueden descargar el video (M4V, 335 MB) para verlo en otro momento.

El video está en perfecto y claro inglés.

Python 3: es excepcional

sábado, 27 de diciembre de 2008
El manejo de excepciones en Python 3 recibió también un cambio menor, pero que tiene por objeto evitar una fuente muy común de bugs en el código producidos por el descuido del programador.

Lanzando

En Python 2.x, la sintaxis para lanzar una excepción era usualmente la siguiente:
raise ValueError, "Error de valor!" # o bien
raise ValueError("Error de valor!")
Sin embargo, existe una cantidad de casos diferentes y poco conocidos que se detallan en un largo párrafo del manual de referencia. Está claro que esto es poco deseable, puesto que introduce complicaciones en el lenguaje con el objeto de facilitar usos poco comunes.

Volviendo al caso "usual" citado antes, si bien ambos casos eran equivalentes, se decidió eliminar el primero puesto que la sintaxis resulta un poco confusa. Al leer, no se entiende fácilmente que en realidad el argumento que viene después de la coma en el raise se pasa al constructor de la excepción. Por lo tanto, de ahora en más habrá que restringirse a la segunda opción:
raise ValueError("Error de valor!")
Atajando

Del mismo modo, para atrapar una excepción, se utilizaba el siguiente bloque:
try:
    ... # codigo que lanza una excepción
except ValueError:
    ... # codigo que maneja la excepción
Ahora, si se desea observar el contenido de la excepción para manipularlo de alguna manera, se utiliza el siguiente bloque except:
except ValueError, e:
    print e # "e" referencia la excepción
La dificultad en este caso proviene del uso de la variable e, que puede fácilmente confundirse en el contexto siguiente:
try:
    ... # codigo que lanza una excepción
except (ValueError, TypeError):
    print e
Como se observa, la idea del código es atrapar una excepción de cualquiera de los dos tipos especificados. Sin embargo, muchas veces en las que se desea hacer esto, se termina escribiendo:
except ValueError, TypeError:
    ... # TypeError es ahora una ref. a la excepción!
Está claro que el comportamiento no es el esperado: el bloque citado no atrapa las excepciones de tipo TypeError, sino que únicamente presta atención a los ValueError.

Para evitar esta situación, se introduce a partir de Python 3 una nueva sintaxis que reutiliza el keyword as, ya utilizado antes con las inclusiones de módulos externos para establecer un nombre diferente al módulo importado. La nueva sintaxis se ve así:
except (ValueError, TypeError) as e:
    ... # "e" es lo que uno espera
Gracias a estos cambios se eliminan varias ambiguedades y semánticas complicadas en pos de la simplicidad. Con cambios como estos se hace que el código sea más legible para quienes son nuevos con el lenguaje, y se evitan bugs difíciles de detectar en el manejo de excepciones.

Computer Networks: A systems approach

miércoles, 17 de diciembre de 2008
Este cuatrimestre cursé la materia Teoría de las Comunicaciones ("redes" para los amigos). Dado que acabo de dar el final esta tarde, me parece un buen momento para dejar una breve reseña sobre el libro que sirve de bibliografía principal de la materia. El libro fue escrito por Larry Peterson (profesor de Princeton) y Bruce Davie (fellow de Cisco), y su cuarta y última edición, que es la que tengo entre mis manos, es de 2007.

El otro libro popular de esta asignatura es el de Andrew Tanenbaum, un reconocido autor del área de sistemas del que ya tuve que utilizar varios libros (Sistemas Operativos Modernos, Sistemas Operativos: Diseño e Implementación, y Redes de Computadoras).

El libro de Peterson-Davie es una bocanada de aire fresco después de los de Tanenbaum porque está, lisa y llanamente, muy bien estructurado y muy bien ajustado al espíritu de la carrera de Ciencias de la Computación.

Bien estructurado

El libro está escrito en perfecto inglés técnico. Mis dotes de inglés no son particularmente fantásticas y jamás me tuve que detener a interpretar una expresión u alguna otra. Como es común en los libros de este tema, los capítulos se organizan siguiendo de forma más o menos ajustada las capas del modelo OSI. de abajo hacia arriba.

Sin embargo, lo que hace que este libro sea muy bueno es como construye de forma ascendente todos los tópicos a cubrir, pero de todas maneras se hace posible leerlo por capítulos independientes sin necesidad de volver hacia atrás constantemente. Es difícil explicar el origen de esta cualidad, fuera de un muy buen trabajo de planeamiento y redacción. Sin dudas este libro no solo sirve como introducción a los temas y explicación de los mismos, sino también como material de consulta.

Bien ajustado a Cs. de la Computación

El enfoque sistémico (systems approach) se basa en que el libro contiene una enumeración concisa de como funcionan las cosas, y una discusión tanto o más larga sobre por qué funcionan de esa manera, y cuales son las demás opciones que no tuvieron éxito.

Jamás aparece entre las páginas del libro un bloque interminable de código fuente lleno de punteros que pretende "explicar" como funciona algo. En las únicas oportunidades en que aparece código es para especificar detalles de implementación, y siempre acompañado de un extenso comentario sobre su contenido.

Gracias a esto, el libro da una perspectiva muy útil del funcionamiento de las redes de datos, puesto que explica de forma profunda las particularidades de diseño de algunos protocolos centrales (como TCP), pero además pinta un panorama amplio sobre el resto del abanico. No se trata de un libro que va a quedar obsoleto con la próxima versión de IP.

Lo malo

Sin embargo, hay algunos "defectos" (si pueden llamarlo así) en el libro. Comparado con el Tanenbaum, este libro carece de algo muy interesante: notas de color. Tanenbaum no escatima chistes, reflexiones graciosas y anécdotas con curiosidades sobre los temas abordados. Si bien esto puede parecer decorativo, yo lo encuentro muy interesante y sobre todo, opino que facilita la lectura haciendo más amenos los tramos largos.

El libro de Peterson tiene la cantidad de dos toques creativos:
  • Las citas al principio de cada capítulo, que son excelentes y muy atinadas, a pesar de provenir de ámbitos totalmente disociados con la informática o las redes. Por ejemplo, el capítulo sobre Internet y redes IP comienza con la siguiente cita de Mason Cooley:
    Every seeming equality conceals a hierarchy.
  • Un único chiste en el que, al hacer referencia a que Internet tiene muchos backbones (columnas vertebrales), una nota al pie indica que los autores no conocen ningún otro animal que comparta esta característica.
Sin embargo, el Peterson-Davie tiene muchos recuadros con notas al margen que son muy útiles. Aquí se incluyen discusiones sobre cosas como la utilización de prefijos decimales o binarios para las unidades, o un recuadro especial "Where are they now?", nuevo en la cuarta edición, donde se discute la utilización real del tema que se está discutiendo.

En resumen, una pieza de bibliografía muy recomendada para quiénes como yo, van a estar mayormente usando redes de computadoras, y no diseñándolas o construyéndolas.

Más ingresantes a Ciencias de la Computación

sábado, 13 de diciembre de 2008
Desde 2005 sigo la carrera de Ciencias de la Computación en la Facultad de Ciencias Exactas y Naturales de la Universidad de Buenos Aires (FCEyN - UBA). Si bien la carrera es popular dentro de la facultad, en la medida que fui avanzando en la carrera fui observando como las materias van teniendo una cantidad de alumnos más reducida. Con cierta frecuencia escucho historias de clases con 150 alumnos en materias como Algoritmos 2, que yo calculo habré terminado con unas 50 personas más.

En el Departamento de Computación (departamento responsable de la carrera), la baja en la cantidad de estudiantes empezó a preocupar a varias personas. Esta situación es por demás curiosa dada la buena salida laboral que tiene la carrera, así como la excelente capacitación que da. Durante el último año se lanzó un nuevo sitio web para futuros alumnos. Incluso varios de mis compañeros salen en las fotos de la página :)

Hoy leo en un artículo del diario La Nación que Ciencias de la Computación encabeza la lista de carreras con mayor aumento en la cantidad de inscriptos:
Entre las carreras que más crecieron en candidatos figuran ciencias de la computación (58%), ingeniería civil (47%), ingeniería mecánica (37%) (...)
Sin duda un casi 60% más de inscriptos es una cifra importante.

Python 3: es de colección

miércoles, 10 de diciembre de 2008
Otro de los sets de cambios incluídos en la nueva versión de Python afecta a las colecciones. Entran en esta categoría los diccionarios, conjuntos y secuencias.

Sets y Frozensets son ahora builtin

En Python 3, set es un builtin (ya no es necesario importarlo del módulo sets). Set es una estructura de datos que representa un conjunto de elementos sin un orden específico. La implementación utiliza una tabla de hash, al igual que los diccionarios.

El tipo set es mutable (una misma instancia puede recibir modificaciones), al igual que las listas. Como la listas en Python tienen un equivalente inmutable (las tuplas), los conjuntos lo tienen también en el tipo frozenset. Cabe aclarar que estos tipos ya existían en Python 2.x, pero en Python 3 fueron promovidos a la librería estándar y ya no es necesario importar ningún módulo para utilizarlos.
>>> s = set()          # creo un set vacío
>>> for i in [1,2,3]:
...     s.add(i)
...
>>> 3 in s
True
>>> 4 in s
False
>>> s.remove(2)
>>> s
{1, 3}
>>> fs = frozenset()   # creo un frozenset vacío
>>> fs2 = fs.union(s)  # lo uno con el set {1, 3}
>>> fs2
frozenset({1, 3})      # obtengo un nuevo frozenset
>>> fs
frozenset()            # fs se mantiene intacto
Hay más información en la documentación oficial de set y frozenset.

Nuevos literales y expresiones por comprensión

Set viene acompañado de un literal para su creación: no es necesario construirlo agregando tediosamente elementos a un set vacío como hice arriba. Sin embargo, como la sintaxis es similar a la del literal de diccionarios, hay que tener cuidado al crear uno vacío! El constructor de set vacío es set(), ya que {} está reservado para los diccionarios.
>>> s = {1, 2, 3, 4}           # creo un conjunto
>>> d = {1: 'uno', 2: 'dos'}   # creo un diccionario
>>> s = {}                     # ojo! crea un diccionario
>>> type(s).__name__
'dict'
>>> s = set()
Pero todavía hay más! Python 3 finalmente incorpora diccionarios por comprensión, y ya que estamos en la volada, conjuntos por comprensión. La sintaxis es exactamente la que uno esperaría, muy similar a la de listas por comprensión. Es curioso mencionar que la propuesta de diccionarios por comprensión proviene del PEP 274 (de 2001!). En 2008, Python 3 incorpora esta deseable funcionalidad: se terminaron los días de usar una lista porque es más cómodo!
>>> numeros = [1,2,3,4,5,6,7,8,9,10]
>>> def esPar(x):
...     return x % 2 == 0
...
>>> pares = {x for x in numeros if esPar(x)}
>>> pares
{8, 2, 4, 10, 6}
>>> cuad_impares = {x: x*x for x in numeros if not esPar(x)}
>>> cuad_impares
{1: 1, 3: 9, 9: 81, 5: 25, 7: 49}

Novedades en diccionarios

En primer lugar hay que notar que el método has_key() de diccionarios fue eliminado. Este método era redundante; estas dos expresiones eran equivalentes en Python 2.x, introduciendo una ambigüedad innecesaria:
>>> dicc.has_key('clave')
True
>>> 'clave' in dicc
True
En Python 2.x los métodos keys(), values() y items() de un diccionario devolvían listas contiendo los datos del diccionario (sus claves, sus valores, y los pares clave-valor respectivamente). Asimismo, existían funciones análogas iterkeys, iteritems y itervalues. Estas últimas devolvían iteradores sobre las mismas secuencias que las anteriores.

Python 3 introduce el concepto de vista. Una vista es un objeto intermedio entre el diccionario y los elementos devueltos por los métodos descritos en el párrafo anterior. Los mismos objetos que usábamos en Python 2.x pueden obtenerse ahora a partir de la vista en lugar del diccionario propiamente dicho. Veamos como:
>>> d = {1:'uno', 2:'dos', 3:'tres'}    # armo un diccionario

# Python 2.x
>>> it = d.iterkeys()  # obtengo un iterador sobre las claves
>>> keys = d.keys()    # obtengo una lista de claves
>>> keys
[1, 2, 3]

# Python 3
>>> v = d.keys()    # obtengo la "vista" del diccionario d
>>> type(v).__name__
'dict_keys'
>>> it = iter(v)    # construyo un iterador a partir de la vista (no del dict!)
>>> keys = list(v)  # construyo una lista a partir de la vista
La utilidad de la vista no es aparente aún: sin embargo, la vista introduce una nueva posibilidad. Es claro que la lista obtenida a partir de keys() en Python 2.x está desconectada del diccionario: toda modificación al diccionario posterior a la creación de la lista no se ve reflejada en la misma. Los iteradores se comportan de forma similar: si se modifica el diccionario durante la iteración, se produce una excepción.
>>> d = {1:'uno', 2:'dos', 3:'tres'}
>>> it = d.iterkeys()
>>> del(d[2])
>>> for key in it:
...     print key
... 
Traceback (most recent call last):
RuntimeError: dictionary changed size during iteration
Lo curioso de la vista es que ella también es iterable! (además del iterador que devuelve al aplicarle iter()). Y esta iteración si soporta modificaciones durante su ejecución. De modo que en Python 3, podríamos hacer esto:
>>> v = d.keys()
>>> del(d[2])
>>> for key in v:
...     print(key)
...
1
3
Si obtenemos a partir de la vista el iterador "tipo Python 2.x", tendremos el mismo comportamiento que antes (se emite una excepción al modificar el tamaño del diccionario sobre el que se está iterando).

En resumen, Python 3 incorpora el tipo set a la librería estándar, y notaciones literales y por comprensión tanto para conjuntos como para diccionarios. Estas facilidades hacen más ameno el uso de los tipos de datos correctos para cada tarea, en casos en los que muchas veces se utilizaba una lista por comodidad de notación. Por último, las vistas introducen funcionalidad adicional a los diccionarios, permitiendo modificarlos mientras se los recorre además de mantener las operaciones existentes.

Python 3: diferencias de orden

domingo, 7 de diciembre de 2008
Otro de los cambios introducidos en Python 3 es la abolición del argumento cmp en la operación de ordenamiento de secuencias. Este argumento permitía especificar una función de comparación para utilizar como criterio de ordenamiento, lo cual era bastante cómodo en muchas situaciones. La función debía seguir el modelo de cmp (la builtin).
>>> cmp(1,2)
-1
>>> cmp(2,1)
1
>>> cmp(1,1)
0
Esto se usa mucho para ordenar según el valor de alguna clave particular en el caso de objetos personalizados.
>>> def cmp_edad(p1, p2):
...     return cmp(p1.edad, p2.edad)
... 
>>> class Persona:
...     def __init__(self, nombre, edad):
...             self.nombre = nombre
...             self.edad = edad
...     def __repr__(self):
...             return "%s (%s años)" % (self.nombre, self.edad)
... 
>>> personas = [Persona('Juan', 15), Persona('Lautaro', 3), Persona('Ifigenio', 73)]
>>> personas
[Juan (15 años), Lautaro (3 años), Ifigenio (73 años)]
>>> personas.sort(cmp=cmp_edad)
>>> personas
[Lautaro (3 años), Juan (15 años), Ifigenio (73 años)]
Python 3 elimina esta posibilidad para forzar en cambio la utilización del argumento key. La diferencia es sutil: el valor de key es una función de un único argumento que devuelve una clave que luego se utilizar para ordenar. Esta técnica se llama DSU (por Decorate, Sort, Undecorate) o transformación de Schwartz. Es realmente meritorio lo de este tipo Schwartz, porque logró ponerle su nombre a algo muy simple en 1994, uniéndose a otros personajes avivados similares (como Bolzano!).

La ventaja está en que la implementación con cmp realiza O(n log n) llamadas a la función de comparación, mientras que usando DSU la clave se evalúa una única vez para cada elemento de la secuencia, lo cual es O(n). Si la función de cálculo de la clave es costosa, esto puede hacer una diferencia apreciable en el rendimiento del algoritmo.

Veamos como quedaría el código anterior:
>>> def key_edad(p):
...     return p.edad
... 
>>> personas.sort(key=key_edad)
>>> personas
[Lautaro (3 años), Juan (15 años), Ifigenio (73 años)]
Hay una cuestión más sutil respecto de porqué se decidió eliminar cmp. No solo la función se ejecuta más veces, sino que además el uso corriente utiliza una función anónima (lambda) para hacerlo. Algo del estilo de:
>>> personas.sort(cmp=lambda x,y: cmp(x.edad, y.edad))
Esto tiene el problema añadido de que, si bien la rutina de sorting está implementada en C, la función de comparación no. Esto implica que cada vez que hace falta comparar dos elementos, hay además que hacer un cambio de contexto a Python con el costo adicional que esto representa. El idiom que utiliza key viene con un aditamento: el módulo operator incluye, a partir de 2.4, las funciones attrgetter y itemgetter. Estas funciones, al estar implementadas en C, son mucho más rápidas que sus contrapartidas en Python. Veamos como quedaría lo anterior utilizando la "forma Python 3":
>>> personas.sort(key=operator.attrgetter('edad'))
De esta forma, todo el ciclo de ordenamiento se ejecuta en C y no se repiten cálculos innecesarios, logrando así ordenar de forma muy eficiente. Hay mucha más información sobre ordenamiento de secuencias en Python (pre-3.0) en el wiki oficial.

En resumen, lo que se hizo fue eliminar una forma popular de ordenar secuencias. Las razones son técnicas además de filosóficas: la variante cmp no solo introduce una decisión a la hora de ordenar (¿qué uso? ¿cmp o key?), sino que una de las opciones produce código naturalmente menos eficiente que la otra.

Benchmark

A pedido del público, una comparación entre la alternativa típica de Python 2 usando cmp con lambda contra la versión de Python 3. En el código de prueba ordeno una larga secuencia de objetos en base al valor de su atributo (entero) i. El código que resulta es el siguiente:
class Pepe:
    def __init__(self, i):
        self.i = i

nums = range(1000000)
random.shuffle(nums)
pepos = map(Pepe, nums)

p1 = pepos[:]
p2 = pepos[:]

t = Timer()

# Version cmp
t.start()
p1.sort(lambda x,y: cmp(x.i, y.i))
print "Version lambda: ",
t.stop()

# Version key
t.start()
p2.sort(key=operator.attrgetter('i'))
print "Version key:    ",
t.stop()
La diferencia es abrumadora, no hay más que ver la salida del programa para una secuencia de 1 millón de elementos:
Version lambda:  21.29 segundos
Version key:     3.78 segundos
La versión key es unas 6 veces más rápida. Solo porque es divertido, les dejo un gráfico que compara la performance de los dos métodos (tiempo en segundos vs. cantidad de objetos a ordenar).

Python 3: pequeños cambios misceláneos

sábado, 6 de diciembre de 2008
El operador <>
No existe más, debería usarse != en su lugar (más de una manera de hacer lo mismo!)

El operador !=
Por defecto devolverá lo opuesto de ==, a menos que este último lance NotImplementedError. Este comportamiento es esperable y por tanto su ausencia era una fuente de bugs. En su momento reporté un bug en el ORM de Django por esta precisa razón.

print es una función
Anteriormente, print era un statement: una palabra reservada del lenguaje con tratamiento especial (como es el caso de if o class). En Python 3 print pasa a ser una función convencional. Esto es consistente con el hecho de que no hay ninguna razón para que no lo sea! Si bien va a ser necesario agregar paréntesis que antes no hacían falta, también va a ser posible utilizar print como antes era imposible.
# Python 2.x
print "hola mundo"    # imprime y va a la línea
print "hola mundo",   # imprime y no va a la línea
map(print, [1,2,3,4]) # error!

# Python 3.x
print("hola mundo")
print("hola mundo", end="")
map(print, [1,2,3,4]) # ok!
La mayoría de la sintaxis especial (y muchas veces extraña) de print ahora se reemplaza con keywords para la función. Hay más información en la página de cambios en Python 3 y en la documentación.

La división anda bien
El histórico problema de que la división de enteros da entero en Python se eliminó de una buena vez. Esto era un problema clásico al comenzar a programar, y forzaba a castear a float en muchas ocasiones para asegurarse de que al menos uno de los dos argumentos de la división sea float (en ese caso la división puede devolver float).
uno = 1
dos = 2

# Python 2.x
a = uno / dos
b = uno // dos
c = float(uno) / 2
print a # imprime 1
print b # imprime 1
print c # imprime 0.5

# Python 3.x
a = uno / dos
b = uno // dos
c = float(uno) / 2
print(a) # imprime 0.5 :D
print(b) # imprime 1
print(c) # imprime 0.5
Unificación de Int y Long
En Python 2 existían las dos clases de enteros, y si bien interoperaban entre ellas perfectamente, al imprimir un entero largo por pantalla se imprimía una curiosa L al final.
>>> import sys
>>> sys.maxint
2147483647
>>> sys.maxint + 1
2147483648L # <- "L" al final
>>> type(sys.maxint).__name__
'int'
>>> type(sys.maxint+1).__name__
'long'
Como la constante sys.maxint quedó por lo tanto sin uso, fue eliminada también.

reduce() no es más builtin
En Python 1.0 (allá por 1994) se agregaron varias primitivas de programación funcional: map, filter, reduce. Estas primitivas permiten, usando una única llamada, reescribir varios bucles simples que se suelen utilizar al programar.

Si bien map y filter quedan casi sin cambios en Python 3, reduce se eliminó porque produce código difícil de leer y por lo tanto es más conveniente utilizar un ciclo en lugar de la función. Para los que deseen seguirla utilizando, reduce ahora vive en el módulo functools.

Hace un tiempo expliqué map, filter y reduce en el foro de PC++.

Volaron muchos otros builtins
Todos los siguientes builtins volaron. Los idioms que los reemplazan están disponibles en la documentación sobre cambios en Python 3.
  • apply
  • callable
  • coerce
  • reload
  • file
  • y varios más!

Python 3 está entre nosotros

El 3 de diciembre salió Python 3 (anteriormente llamado Python 3000). Por primera vez en la historia, Python rompe la compatibilidad hacia atrás para mejorar (y en cierta manera, purificar) el lenguaje.
There should be one —and preferably only one— obvious way to do it
"Debería haber una (y preferentemente solo una) manera obvia de hacerlo". Esa cita proviene del Zen de Python, una suerte de poema-chiste-documento que contiene las filosofías detrás del diseño del lenguaje de programación. La que cito arriba, en particular, se contrapone fuertemente con el slogan de Perl: "Hay más de una manera de hacerlo". Los programas en Perl se caracterizan por su muy pobre legibilidad - al punto que a veces se dice que Perl es un lenguaje de solo escritura (una vez que está escrito, nadie podrá leerlo!).

Esa cita es una parte esencial de las modificaciones que sufrió Python en su versión 3. Con el paso de los años, Python fue creciendo y acumulando librerías y funcionalidades. En muchos casos, existían varias maneras de hacer lo mismo sin que quedara claro cual era la mejor. Por esta razón, se eliminaron muchas formas redundantes de hacer cosas, y se aprovechó para corregir algunos detalles que vinieron mal de fábrica. Por supuesto, también hay nuevas funcionalidades.

En el sitio web oficial hay una página detallando todos los cambios en Python 3.

En los próximos días voy a estar comentando algunos de los cambios que se hicieron en Python 3, sus razones de ser, y sus implicaciones en el uso del lenguaje. Python es más simple, consistente (y lindo!) que nunca.

El caso Konabot

martes, 2 de diciembre de 2008
El Konabot es un robot para manipulación de explosivos que se desarrolló en el laboratorio de robótica de la Facultad de Ciencias Exactas y Naturales de la Universidad de Buenos Aires, en un proyecto a cargo del Dr. Juan Santos. Se trata de un proyecto técnicamente avanzado que se hizo a pedido de la brigada de explosivos de los bomberos de la Policía Federal. El robot recibió en 2007 el Premio Innovar en Investigación Aplicada.

Está disponible en YouTube un video explicativo sobre el Konabot.

La polémica

A principios de septiembre de este año se difundió en los pasillos de la facultad que la misma había hecho efectiva la cesión de los derechos de desarrollo del Konabot a la empresa Robots del Sur, creada para tal fin por el inversor Tobías Schmukler (fundador de ITS, una empresa local de servicios informáticos). La transferencia de desarrollos realizados en la universidad pública al sector privado es considerada por muchos parte de la colaboración de la universidad con la sociedad que la sustenta. Sin embargo, los términos de la cesión resultaban curiosos, y más aún las palabras de Schmukler en una entrevista donde comentó las intenciones de su actual empresa Innova Tekné:
La ganancia se da a partir del desarrollo puntual del proyecto y de la venta posterior de esa empresa
A muchos nos chocaron estas ideas, puesto que pareciera que lo se iba a hacer era regalar a Schmukler un desarrollo nacional para que luego un consorcio extranjero lo compre, dejando así al Konabot fuera del alcance de los compradores nacionales y enriqueciendo al inversor.

Desde ya que las opiniones sobre este tema resultaron divididas, pero se armó un gran revuelo en la facultad por esta cuestión. Hay información mucho más completa en el post de PC++ donde comenté esto por primera vez.

Cómo terminó la historia

Hace unos días, llegó de Jorge Aliaga (decano de la facultad) el siguiente mail a la lista de alumnos:
Cuando se informó acerca del convenio, recibimos críticas de diversos sectores, donde se nos acusó de destruir la robótica en el país y las carreras científicas de los miembros en formación del grupo, de regalar las tecnologías generadas con fondos públicos, etcétera. También se atacó públicamente al inversor, tanto dentro como fuera de la Facultad.

Como consecuencia de todos los inconvenientes generados, Robots del Sur ha desistido de sus intenciones de iniciar sus actividades.

Quién esté interesado puede mirar el texto completo del mail, donde el propio decano hace un balance de la situación.

Una reflexión sobre lo ocurrido

¿Fue bueno o malo que el proyecto se echara atrás? ¿Se evitó una estafa a la universidad pública y a los investigadores que trabajaron con esfuerzo, o se evitó el desarrollo de una empresa nacional de tecnología? Sin lugar a dudas esto no está claro, y probablemente nunca se sabrá.

Lo que resulta evidente, al ver los resultados, es que la facultad, desde la incubadora de empresas, manejó muy mal la comunicación con la comunidad universitaria. Desde un punto de vista político operaron pésimamente: de forma casi repentina, varios de los investigadores se desayunaron que su trabajo estaba siendo regalado a un inversor privado, y se produjo una reacción violenta por parte de la comunidad estudiantil, pidiendo explicaciones a los responsables.

¿Qué fue lo que pasó? Yo entiendo que hay tres posibilidades:
  • El proyecto era realmente el manejo extraño que intentaron promover algunas agrupaciones de estudiantes.
  • El proyecto era honesto y bienintencionado, con la mala suerte de que se manejó muy mal la comunicación y el debate sobre la cesión de desarrollos públicos al sector privado, provocando una reacción desfavorable.
  • El proyecto era honesto y bienintencionado, pero se intentó promover por lo bajo, evitando llamar la atención de la comunidad con el objetivo de escapar a una inevitable reacción desfavorable.
Detengámonos sobre la última opción. Es sabido que en la universidad pública, un proyecto de privatización del desarrollo realizado en la facultad será recibido con el ceño fruncido. Es sabido que habrá quien intente sacar partido político oponiéndose a él. Es sabido que boicotear un proyecto polémico, con o sin razón, otorga rédito político a quién impulsa el boicot.

Es en función de esto que resultaría muy comprensible que las autoridades hayan tratado de evitar esta situación para lograr llevar a cabo el proyecto. Hay ahora quienes proclaman el éxito en ponerle freno a las políticas privatistas. Ahora bien, como comunidad, ¿ganamos algo? ¿Si logro martillarme la cabeza, lo puedo considerar un triunfo?

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.

Charla sobre Técnicas Algorítmicas

viernes, 31 de octubre de 2008
Cada tanto la gente de PC++ organiza una reunión donde algunos de los miembros del foro tienen la oportunidad de dar una charla o curso breve de algún tema en el que trabajan o estudian.

La última edición fue el 26 de Julio pasado y me tocó dar una charla sobre técnicas algorítmicas, donde conté varios de los temas que en mi carrera corresponden a las materias Algoritmos y Estructuras de Datos II y III.

Además de la presentación de PowerPoint, también preparé un muy rápido resumen sobre complejidad algorítmica que sirve de introducción al tema, y un apunte sobre los temas de la charla para los que no pudieron asistir.

Downloads

Mis fotos



Yo y mi Olympus OM2


Hace ya varios años que me gusta la fotografía y le dedico buena parte de mi tiempo libre. Revolviendo los backups de mi antiguo blog encontré, allá por el 2003, estas palabras:
Me está gustando la fotografía. Tiene un nosequé de plasmar lo intrascendente... (...) es interesante mirar todas esas pequeñas cosas desde otro punto de vista.
Todavía estaba lejos de Septiembre de 2005, momento en que compraría mi primera cámara propia, pero por lo visto ya me lo sentía venir. Todo mi trayecto fotográfico está a la vista en mi Flickr, donde fui subiendo fotos desde aquellos días.

Este año armé un segundo sitio web, donde subí solo una selección de mis fotos favoritas, como para que cualquiera pueda ver las que considero mis mejores fotos sin las distracciones típicas de un sitio comunitario como es Flickr.


"Dormidos" (c) Gonzalo Sainz-Trápaga


Probando

jueves, 30 de octubre de 2008
*toc* *toc*
Hola! Sssí!
Uno, dos, tres, probando...

Hace unos años tuve un blog. En él había bastante contenido piola. Como con muchas cosas, el paso del tiempo (y el avance del comment spam) hizo que mantenerlo se hiciera cada vez más cuesta arriba. Un buen día, la pequeña Pentium 166 donde se alojaba el blog exhaló su último soplo durante una tormenta eléctrica. El sitio nunca volvió a la vida, aunque todavía conservo los backups.

Algunas de las ideas de este nuevo blog son:
  • Volver a poner online parte del contenido del antiguo blog,
  • Centralizar contenido nuevo que generalmente posteo en otros sitios, y
  • Tener un espacio propio donde alojar contenidos que no "encajan" en otra parte.
Nos estamos leyendo.