viernes, febrero 10, 2012

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

17 comentarios:

  1. Este comentario ha sido eliminado por un administrador del blog.

    ResponderEliminar
  2. Un troll al dia10/2/12 8:48 a. m.

    Y si se mira el código fuente de passwords.cgi se ve en claro el password de los usuarios para la validación javascript:

    pwdAdmin = 'password';
    pwdSupport = 'ovislink';
    pwdUser = 'dj5800';

    ResponderEliminar
  3. lo estan usando para fraude y telefonica pasa del cliente

    ResponderEliminar
  4. Me he sentido muy identificado porque estudié más o menos las mismas cosas que tú con intereses muy parecidos, aunque mi experiencia en programación no era tan extensa.
    En mi opinión pasar por la universidad te da algo que no se obtiene aprendiendo de forma autodidacta, que es la obsesión por hacer las cosas bien, eficientes, elegantes, mantenibles... tengo compañeros que programan y estudiaron otra cosa (física y matemáticas sobre todo) y se les nota mucho que lo que hacen, con tal que funcione vale todo. Y luego pasa lo que pasa, que cuando crecen los datos o se le busca alguna vulnerabilidad, pues se nota la diferencia...

    ResponderEliminar
  5. Una de las cosas que más me llamó la atención en programación orientada a objetos es que después de estudiarnos un montón de métodos de ordenación como los que comentas (quicksort, burbuja, etc) nos preguntaron:

    "Según los métodos empleados en POO (programación orientada a objetos) ¿como se realiza la ordenación de los elementos de un objeto?"

    Solución:

    Objeto.Sort()

    Era un examen de 10 preguntas (1 punto por cada pregunta). La respuesta fué 1 punto :D

    Evidentemente había cosas mucho más complejas :D

    Gracias por hacerme recordar mis andanzas por las clases de programación :D

    ResponderEliminar
  6. Lisp, ADA, esos de por sí, me parecen un locurón y no tengo ni idea, solo ví unas clases del MIT, del año la polca. Madre mia, Chema, tienes todos mis respetos. Seguiremos en la trayectoria indicada.

    PD: Dejo un link, donde hay algunos cursos (y muy interesantes, sobre todo el primero de todos, introducción a la programación en Python) sobre "ciencia de la computación", en inglés:
    http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/

    ResponderEliminar
  7. Jias jias
    Si le kitas la parte final, donde tu te decantaste por una rama distinta, casi te podria calcar la historia, aunque supongo k como taaantos otros k hicimos la carrera. Yo elegí al final decantarme por cryptografía (tb contiene estadistica a porrones k odiaba) y el bloke final de Internet y Seguridad... Para acabar trabajando de programador para una empresa en Barna (Visual Studio, C#, .NET, JavaScript, ASP.NET, etc...) jejejejejeje
    Lo k kiero decir, es que al final, uno elije y encamina, segun las oportunidades que se le presentan, pero como dicen en el anuncio de la tele, la suerte no existe, HAY QUE ESTAR AHI, para que se te presente!
    "Que la inspiración te pille trabajando"

    Me gustó leer que en el fondo no estamos tan distantes unos de otros, solo elegimos un camino u otro...

    P.D. Chema, no se si leeras esto o no, pero SIEMPRE (100% de las veces) que le doy a PUBLICAR COMENTARIO con la cuenta de Google para ident. me da error del Capcha, identifica la cuenta y tengo k meter uno nuevo... Error de la web?

    ResponderEliminar
  8. No podría estar más de acuerdo Chema.

    ResponderEliminar
  9. Gracias maligno, me hiciste reflexionar sobre la universidad.

    ResponderEliminar
  10. Chema este año me toca Estadisticas... al modo que lo pintas me asustas... no obstante tienen razon en los comentarios, para que algo sea eficiente debe ser bien analizado a fin de que cuando crezcan las bases no haya problemas...

    ResponderEliminar
  11. Pues a mi estadistica me parecio mega tirada(de hecho saque un 10) :P

    ResponderEliminar
  12. Chema segun informan hackearon telefonica y sacaron doc secretos de seguridad

    HACKEAMOS TELEFONICA Y OBTENEMOS INFORMES SECRETOS #Anonymous #Opdoblefilo CONFIDENCIAL BBVA http://bit.ly/wVprKe #OpSpain #AnonWorld.Info


    http://uploaded.to/file/r29wwztj

    ResponderEliminar
  13. Sólo tienes un par de años más que yo y me ha sorprendido lo de Cobol.

    Bueno, ya sé que aun se usa, pero yo no hubiese tenido curiosidad, hubiese invertido en otros "más comunes", de hecho C, C++ Pascal fueron mis eleciones primerizas.

    En la universidad dimos uno funcional, Caml, que ni aparece en la lista de Tiobe. Sólo sirvió para introducir los funcionales.

    Por cierto, nosotros teníamos estadística repartida por todos los cursos y todas huesos, pero había una asignatura en 2º, que fue la que más estudié y me tuve que presentar 4 veces. Fui a tutorías con el profe para la 4º convocatoria (muy majo y amable) varias veces porque ya no sabía que más estudiar ni cómo.

    Puedo decir que aprendí estadística y probabilidad y me salen las variables aleatorias y las series de Markov por las orejas :)

    ResponderEliminar
  14. Muy buen artículo, Yo hice un FP de grado superior en desarrollo de aplicaciones y me he metido a estudiar la carrera, la verdad es que es totalmente diferente y estoy aprendiendo muchísimo.

    Un saludo

    ResponderEliminar
  15. Yo tuve la mala idea de meterme en la carrera para luego intentar llegar a ser semi-maligno. A ver como termina la cosa.

    ResponderEliminar
  16. :) Ahora que estoy a falta del proyecto, te leo y es prácticamente como si lo hubiese escrito yo, cambiando la estadística por seguridad, que curiosamente es de las
    que más me han gustado :P.

    Gran post Chema, has hecho que mire ya casi con penica el final, cuídate!

    ResponderEliminar
  17. Hola, el enlace del pdf no funciona, podrias repararlo por favor, Gracias por todo el tiempo empleado en esta entrada y muchas otra

    ResponderEliminar