El algoritmo de Melkman, la marcha de Jarvis y Estadística

Si hubo una asignatura que me tuvo loco fue Estadística. Esa materia, como a muchos de mis compañeros, me traía loco. Sin embargo, hubo otras que me enamoraban y me mantenían enganchado, eran todas las que tenían que ver con programar. Yo había comenzado a aprender a programar en BASIC cuando tenía 12 años y cuando llegué a la Universidad ya me había pegado con Cobol, Pascal y C. Con 18 años penaba que era un buen programador.

Sin embargo, cuando llegué a las salas de más de 100 alumnos, me encontré con contenidos que me sonaron totalmente nuevos. Las estructuras de datos, los algoritmos recursivos, los tipos estructurados de datos, etcétera, y en todos había que entender cómo iba moviéndose el flujo del programa, lo que lo hacía más divertido. Ese fue el momento en que conocí las listas, las pilas, las colas y los árboles, para disfrute de mis programas y, por supuesto, de la resolución de problemas como los de las mega-famosas Torres Hanói, que hube de resolver de veinte maneras diferentes.

Figura 1: Resolución del problema de las Torres Hanoi

En segundo de carrera llegaría la algorítmica, con sus resoluciones de backtracking, sus análisis de complejidad, los algoritmos de búsqueda, de ordenación, de recorrido de grafos en los que había que aplicar estructuras de datos y algoritmos óptimos para generar los auténticos programas. También en ese curso llegarían las estructuras de datos avanzadas, con sus árboles AVL, los árboles hilvanados por listas, y los árboles AVL doblemente hilvanados, los árboles B, y los B*, organizados pensando en el tamaño óptimo de lectura de los discos.

También en ese curso llegaron los paradigmas de programación, aprendiendo no sólo la archi-famosa programación estructurada, sino que tocó lidiar con el paradigma de orientación a objetos, el polimorfismo, la sobrecarga, la herencia y el diseño UML de aplicaciones, eso sí, con lenguajes tan curiosos como Smalltalk o C+- (sí, más menos...). Por otro lado la programación concurrente, que yo “sufrí” con ADA, OCCAM y otro que ahora os cuento, me obligaba a pensar en semáforos, regiones críticas, zonas de exclusión mutua e inter-bloqueos que podían generar entornos de inanición. Resolver problemas como el de los filósofos glotones que luchaban por los tenedores para comer spaguetti eran el día a día en esas clases de – wait for it – Pascal Concurrente. Como es lógico, también hubo que pegarse con programación funcional y resolver problemas imposibles con el LISP.

A toda la parte que tenía que ver con la programación más pura y dura se sumaban otras disciplinas que también me vendrían de maravilla en el futuro, como fueron UNIX, Ensamblador, Diseño de Bases de datos y el lenguaje SQL, o Compiladores e Interpretes donde como todos los que hemos pasado por la Universidad toco diseñarse los autómatas de turno, el lenguaje formal y programar el analizador léxico, sintáctico y semántico de un lenguaje.

Yo, como soy un enfermo, y en primero me encantó la Matemática Discreta y los algoritmos con los grafos, decidí proseguir con ellos hasta el final de la carrera, donde los algoritmos de cierres convexos, los algoritmos de triangulación o los de resolución de problemas con rectas de barrido me llevaron a terminar haciendo el PFC sobre esas cosas. Al final Melkman o Jarvis y su famosa marcha, me hacían pensar en algorítmica día tras día.

Figura 2: La ejecución del marcha de Jarvis para hacer el cierre convexo de una nube de puntos

La optimización del algoritmo y hacer uso de buenas estructuras de datos era el reto en todas las aproximaciones. Elegir la recta de barrido, el divide y vencerás, un recorrido en profundidad de un grafo para hacer un backtracking eficiente, implementar bien el QuickSort, o cómo pintar los triángulos de una lista de polígonos desordenados en el espacio era como resolver sudokus día a día.

La programación era para mí una ciencia que se convertía en arte cuando descubría que para saber si dos rectas se cruzan en el espacio no debía calcular nunca el punto de corte porque no es eficiente y tenía que crear un algoritmo más eficiente para un límite infinito de rectas. Algo que cuando se añaden restricciones de espacio, memoria o tiempo, hacían que fuera aún mejor.

Es por eso que, a todos los jóvenes que me habéis preguntado si es necesario hacer la carrera de informática para ser un buen informático os he dicho que no, pero que yo os recomiendo a todos que paséis por la Universidad, aunque tengáis que sufrir Cálculo Infinitesimal, Física, Lógica … o la famosa Estadística.

Saludos Malignos!

PD: Por si te gusta la algorítmica y la programación, aquí so dejo un PDF de un libro que cubre gran parte de estos temas: How to think about algorithms