MATERIA:Análisis de Algoritmos I

CLAVE:COMP-420

SEMESTRE DE UBICACION:Cuarto.

AREA:Ciencias de la Computación

OBJETIVOS: Este curso da un tratamiento profundo de análisis de complejidad. Ayudan a motivar y desarrollar el tema varios algorítmos de búsqueda y ordenamientos, así como métodos de espacios de búsqueda de¡ área de Inteligencia Artificial y estructuras de archivos utilizados en sistemas de bases de datos. Se discuten clases de complejidad, así como la naturaleza de la NP completez e intratabilidad. Esto lleva a una discusión de computabilidad y de la máquina universal de Turing. Se discuten algunos problemas asociados con algoritmos paralelos.

TEMARIO:

1. Introducción y conceptos básicos. (Se establecen los conceptos principales con los cuales se mide un algoritmo y se presentan los distintos modelos de computabilidad que se utilizan para evaluar la calidad de un algoritmo)
   • Problemas y algoritmos

   • Complejidad

   • Modelos de cómputo

   • Modelo Universal de la Máquina de Turing

   • Problemas de complejidad polinomial

2. Complejidad en ordenamientos (Se regresa a los algoritmos de ordenamientos ya vistos y se examinan detenidamente las medidas de complejidad de los mismos. Se introducen nuevos tipos de algoritmos que, a pesar de no garantizar la correctez de la solución, presentan medidas de "eficiencia" que en su comportamiento promedio resultan ser mejores que aquéllos cuyas cotas máximas, de ser cumplidas, resultan ser poco eficientes.)
   • 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".

3. Problemas que involucran sistemas complejos: Gráficas (Se presentan métodos para representar y realizar búsquedas en gráficas. Los algoritmos de gráficas, generalmente de una complejidad considerable, ponen al descubierto mucha información respecto a la estructura de la gráfica. Estos algoritmos son importantes en cuanto a que se muestran estrategias de optimización que logran abatir la complejidad natural de los algoritmos típicos.)
   • Estructuras

   • Colas y particiones

   • Ordenamientos parciales

   • Exploración de gráficas

   • Transmisión de la información

   • Distribución de flujo.

4. Problemas que involucran números (Con este tipo de problemas se introduce al estudiante a la necesidad de manejar aritmética de precisión y magnitud arbitrarias en software a través de una representación fija de unos cuantos dígitos en el hardware. Esto apunta en dos direcciones: primero, las operaciones aritméticas básicas de suma, resta, multiplicación y división se vuelven "caras" y su costo se incremento en razón del número de dígitos en sus argumentos. En segundo lugar, se debe cambiar el modelo para medir la complejidad midiendo el tamaño de los datos en términos del número de dígitos necesario para representarlos. A este modelo se le conoce como el modelo de costeo en bits.)
   • Números exponenciales.

   • Números comunes

   • Números Primos

   • Números secretos

   • Números auténticos

   • Números al azar

   • Transformando números

5. Algoritmos Paralelos(Introducción al desarrollo de algoritmos para arquitecturas paralelas y distribuidas, ilustrando como el paralelismo puede proporcionar un aceleramiento substancial en comparación con ejecución secuencial)
   • Paralelismo, la PRAM y otros modelos

     • Algunos algoritmos PRAM y el manejo de conflictos en la escritura

     • Mezclas y ordenamientos

     • Un algoritmo con componentes a paralelos conectados

     • Cotas mínimas

6. La clase NP y su relación con la clase P (Se regresa al concepto de algoritmos a través de la luz de los algoritmos ya presentados. Se distingue entre las teorías de Computabilidad y Complejidad. La primera de ellas se pregunta ¿Cuándo hay las condiciones para que esto se compute? ¿Se puede computar? mientras que la segunda se pregunta ¿Qué tan barato puede calcularse esto?¿ Qué tan dificil es calcularlo?)
   • Nacimiento del concepto de NP-Completez

   • Determinar las jerarquías de complejidad

   • ¿Qué es un algoritmo?

   • ¿Qué es una prueba?

7. La Teoría de la NP-Completez (Se da una introducción a la teoría de la NP-Completez, de tal manera que se puedan identificar aquellos problemas que pertenecen a esta clase, para optar por algoritmos aproximados para resolver problemas de este tipo. Introduce también la noción de reducibilidad para algunos problemas NP-Completos a problemas polinomiales. Finalmente da una perspectiva de la teoría de Computabilidad.)
   • 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

BIBLIOGRAFIA:

• Connen, T. H.; Leierson, C. E.; Rivest, R. L., Introduction To Algolithms, McGraw-Hill Book Company, 1990

• Rawlins, G. J. E., compared to what?, an introduction to the analysis of algorithms,Computer Science Press, 1992

BIBLIOGRAFIA COMPLEMENTARIA:

• Aho, A. V.; Hopkroft, J. E.; Uliman, J. D., Estructuras De Datos y Algoritmos, Addison Wesley Publishing Company, 1988

• Garey, J., Computers And Intractability: A Guide To The Theory Of NP-Completeness, Freeman, New York, 1979

• Aoe, J. I. edited by , Computer Algoyithms: Key Search Strategies, IEEE Computer Society Press, 1991

• Cragon, H. G., Branch Strategy Taxonomy and Performance Models, IEEE Computer Society Press-, 1992