• Descripción



    En "The Art of computing programming", D. Knuth propuso evaluar como se desempeñan los algoritmos suponiendo que sus entradas son aleatorias. Esta idea dio lugar a lo que  hoy se conoce como análisis probabilístico de algoritmos. Este análisis es más realista que el de el peor caso que solamente considera las entradas en las que el algoritmo tiene un mal desempeño y que en muchos casos son poco probables y por lo tanto, infrecuentes en la práctica.   

    En este curso se presentarán los fundamentos del análisis probabilístico que permiten analizar el desempeño de de algoritmos  de ordenamiento datos (quicksort, mergesort, etc.), algoritmos de procesamiento texto y algoritmos y muchos otros.

    Las herramientas y fundamentos teóricos para realizar este análisis se basan en la combinatoria analítica, disciplina que asocia problemas de conteo con series de potencias llamadas series generatrices. El problema combinatorio original se traduce en un problema clásico del análisis matemático como, por ejemplo, determinar el dominio de convergencia de la serie, determinar singularidades, etc. Un tratamiento unificado de esta teoría así como la mayoría de sus fundamentos metodológicos fueron propuestos por Philippe Flajolet y están descriptos en los libros [Sedgewick&Flajolet] y [Flajolet&Sedgewick].

    En el curso se presentarán algunos problemas de investigación. 
      

    Objetivos

    Pesentar los principios del análisis probabilístico de algoritmos junto con algunas herramientas propias de la combinatoria analítica.   Presentar el análisis probabilístico del desempeño de algunos algoritmos clásicos para ordenamiento de datos (sorting algorithms), algoritmos de procesamiento de texto y el comportamiento de ciertas clases de árboles (tries, BST, etc.)