Análisis de Algoritmos I

HRS./SEM.: 4

Objetivo: Calcular la complejidad de problemas algoritmicos. Conocer las técnicas principales de analisis de secuencias, las clases de problemas de complejidad y los problemas insolubles.

  • Introducción y conceptos básicos. Problemas y algoritmos. Complejidad. Modelos de cómputo. Modelo Universal de la Máquina de Turing. Problemas de complejidad polinomial
  • Complejidad en ordenamientos. Distintos tipos de ordenamientos (intercambio, inserción, selección, mezcla, por particiones). Cotas mínimas en ordenamientos. Cotas óptimas. Conceptos de algoritmos relajados, de aproximación, probabilísticos y heurísticos para la obtención de soluciones "adecuadas".
  • Problemas que involucran sistemas complejos. Estructuras. Colas y particiones. Ordenamientos parciales. Exploración de gráficas. Transmisión de la información. Distribución de flujo.
  • Problemas que involucran números. Números exponenciales. Números comunes. Números Primos. Números secretos. Números auténticos. Números al azar. Transformando números.
  • Algoritmos Paralelos. Paralelismo, la PRAM y otros modelos. Algunos algoritmos PRAM y el manejo de conflictos en la escritura. Mezclas y ordenamientos. Un algoritmo con componentesa paralelos conectados. Cotas mínimas.
  • La clase NP y su relación con la clase P. Nacimiento del concepto de NP-Completez. Determinar las jerarquías de complejidad. ¿Qué es un algoritmo?. ¿Qué es una prueba?.
  • La Teoría de la NP. Transformaciones polinomiales. Probando resultados NP-completos: 3-SAT y reducciones; problemas básicos NP-completos. Problemas no decidibles. Solución de problemas difíciles. Computabilidad: Máquinas de Turing y Universales.

Bibliografía.

[1]. Cormen, T. H.; Leierson, C. E.; Rivest, R. L., Introduction To Algorithms, McGraw-Hill Book Company, 1990.
[2].Rawlins, G. J.E., compared to what?, an introduction to the analysis of algorithms, Computer Science Press, 1992
[3]. Aho, A. V.; Hopkroft, J. E.; Ullman, J. D., Estructuras De Datos Y Algoritmos, Addison-Wesley Publishing Company, 1988
[4]. Garey, J., Computers And Intractability: A Guide To The Theory Of NP-Completeness, Freeman, New York, 1979
[5]. Aoe, J.I.; edited by , Computer Algorithms: Key Search Strategies, IEEE Computer Society Press, 1991
[6].Cragon, H. G., Branch Strategy Taxonomy and Performance Models, IEEE Computer Society Press, 1992