Información detallada de curso |
Primer semestre 2017
Abr 19, 2024 |
|
 |
||
| Código y Nombre de la Asignatura: IST 4310 - ALGORITMOS Y COMPLEJIDAD |
|
División Académica:
División de Ingenierías
Departamento Académico: Dpto. Ingeniería de Sistemas IST 4031 Calificación mínima de 3.0 Número de créditos: Intensidad horaria (semanal para nivel pregrado y total para nivel postgrado): 2.000 Horas de Teoría 2.000 Horas de Laboratorio Niveles: Educación Continua, Educación Superior Pregrado Tipos de Horario: Teoría y Laboratorio Se inicia con una introducción a la noción de complejidad computacional (tiempo y espacio); se explica la complejidad temporal y espacial y su uso en el análisis de algoritmos. Luego se indica las diferentes estrategias para la solución de problemas mediante la construcción de algoritmos y por último se realiza un análisis general de las clases de complejidad P y NP. 3. JUSTIFICACIÓN La asignatura se justifica en términos de: - Familiarizar al estudiante con las técnicas formales para la obtención de algoritmos eficientes. -Introducir al estudiante en el análisis formal de problemas intratables determinísticamente. 4. OBJETIVO GENERAL Comprender y aplicar las diferentes técnicas empleadas para el análisis de algoritmos. 5. RESULTADOS DEL APRENDIZAJE Las salidas del curso (Course's Outcomes (CO's) o salidas de aprendizaje que el alumno debe adquirir son las siguientes: - Entender cómo caracterizar y clasificar los algoritmos, sus limitaciones y criterios de mejoramiento. - Comprender el análisis de complejidad y entender las diferencias de las notaciones O(n), Omega(n), Theta(n). - Comprender y aplicar las diferencias de los problemas tipo P, NP y NP Completos. - Aprender en su análisis, diseño y evaluación las técnicas: Algoritmos Recursivos, Dividir y Conquistar, Algoritmos Voraces, Programación Dinámica, Regreso hacia atrás y Teoría de Grafos. - Programar en un lenguaje de programación de alto nivel, tres casos involucrando algunas de la técnicas de: Dividir y Conquistar, Algoritmos Voraces, Programación Dinámica, Regreso hacia atrás, Teoría de grafos, o casos relacionados con los conceptos de problemas P, NP, y NP_Completos. 6. CONTENIDO 6.1 MODULO I COMPUTADORES, COMPLEJIDADES E INTRATABILIDAD 6.1.1 Introducción 6.1.2 Problemas, Algoritmos, y Complejidad 6.1.3 Análisis de Complejidad (Complexity Analysis) 6.1.3.1 Cantidad de trabajo realizado 6.1.3.2 Análisis asintótico (Asymptotic analysis) 6.1.3.3 Ordenes de complejidad (The timing of algorithms) 6.1.3.4 Análisis de eficiencia tiempo vs espacio en algoritmos. 6.1.3.5 Estudio de casos y ejercicios 6.1.4 Clases de Complejidad (Introducción) (Complexity Classes) 6.1.4.1 Clases de Complejidad P, NP, NP 6.1.4.2 Problemas tratables e intratables. 6.2 MODULO II TECNICAS DE ANALISIS DE ALGORITMOS 6.2.1 Eficiencia de los algoritmos 6.2.2 Análisis de programas recursivos 6.2.3 Resolución de ecuaciones de recurrencia 6.2.3.1 Ecuaciones de recurrencia lineales 6.2.3.2 Ecuaciones de recurrencia no lineales 6.2.4 Ejercicios 6.2.4.1 Análisis de algoritmos empleando ecuaciones de recurrencias 6.2.4.2 Comparación de algoritmos iterativos y algoritmos recursivos. 6.3 MODULO III ESTRATEGIA PARA LA SOLUCION DE PROBLEMAS 6.3.1 Dividir y Conquistar 6.3.2 Técnicas heurísticas 6.3.2.1 Técnicas voraces 6.3.2.2 Técnicas de acondicionamiento 6.3.3 Algoritmos de retroceso (Backtracking algoritmos) 6.3.4 Programación dinámica 6.4 MODULO IV EL PROBLEMA DE LA RUTA MAS CORTA 6.4.1 Algoritmo de Floyd y Warshall 6.4.2 Algoritmo de Dijsktra 6.4.3 Equivalencia de problemas 6.5 MODULO V BUSQUEDA EN TEORIA DE GRAFOS 6.5.1 Estrategias de búsquedas en grafos 6.5.2 Métodos de reintento 6.5.3 Métodos de grafo explícito 6.6 MODULO VI COTAS INFERIORES PARA ORDENES DE COMPLEJIDAD 6.6.1 Algoritmos basados en comparaciones 6.6.2 Cota inferior: Inserción en una lista ordenada 6.6.3 Máximo de un conjunto, Ordenamiento 6.7. EL PROBLEMA DE EQUIVALENCIA 6.7.1 El problema de equivalencia 6.7.2 El algoritmo de Kruskal 6.7.3 Complejidad computacional amortizada 6.8 INTRATABILIDAD 6.8.1 Introducción 6.8.2 Máquina de Turing 6.8.3 Teorema de Cook 6.8.4 Complejos pero 6.8.5 Una alternatica: No-Determinismo. 7. EVALUACION TIPO PORCENTAJE FECHA TEMA Primer Parcial (PAR1) 20% 4a Semana 1,2 Segundo Parcial (PAR2) 20% 8a Semana 3,4 Examen Final (EF) 20% Según Registro 1 al 8 Laboratorios (L) 20% 3a, 7ª, 9ª, 12a Semana I+D (10%) y Quices (10%) (Q) 20% 12a Semana 8. BIBLIOGRAFIA - AHO Alfred V. Ullman Jeffrey D. Foundations of Computer Science C Edition. Computer Science Press. An Imprint of W.H. Freeman and Company. New York. 1.996 - CORMEN Thomas H., LEISERSON Charles E., RIVEST Ronald L. Introduction to Algorithms. Electrical Engineering and Computer Science Departament at the Massachussetts Institute Technology (MIT). Twenty-first printing, 1998. - BECERRA S. César. Estructura de Datos en Java 1a. Edición Editorial Kimpres Ltda. Agosto 2000. - BAASE Van Gelder. Algoritmos Computacionales. Introducción al análisis y diseño. Pearson Education de México S. A. de C. V. (2002). - BRASSARD G, y BRATLEY p. Fundamentos de Algoritmia. Prentice Hall Inc., (1997) - CAPACHO, Rafael. Estrategias para la solución de problemas aplicando Teoría de Algoritmos. (Compilación - Notas de Clase). - http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/ - AMSBURY Wyne. Data atructures from arrays to priority queues.Wadsworth Publishing Company - BECKMAN, Fank. Mathematical Foundations of Programming. Addison-Wesley, 1980. - GAREY, Michael R. y JOHNSON, David S. Computers and Intractability: A guide to the theory of NP-Completeness. U.S.A: Bell Laboratories, 1979 . 340 p. - GREENE, Daniel. Matemathics for the Analysis of Algorithms. Binkhauser, 1982. - HARBRON, Thomas. File Systems Structures and Algorithms. Prentice Hall, - KNUTH, Donald. El arte de Programar Ordenadores. Reverte, 1987. - SEDGEWICK, Robert. Algorithms. U.S.A.: Addison - Wesley Publishng Company, 1995. 711 p. - WIRTH, Niklaus. Algoritmos y Estructuras de Datos. Prentice Hall - GALVE, Javier. GONZALEZ, Juan C. SANCHEZ, Angel y VELAZQUEZ, J. Angel. Algorítmica. Madrid, España: Addison - Wesley Iberoamericana, 1993. 496 p. - Base de datos: Computer Select. Direcciones Internet: - http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/ - http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/ - http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=IntroToAlgorithms http://books.google.com.co/books?id=4RTexhx0efEC&pg=PA153&lpg=PA153&dq=open+courses+algorithms+and+complexity&source=bl&ots=K0_B0abKHh&sig=T4jTgHcwHxxJ0MBhdJy5FeRoi24&hl=es&sa=X&ei=vDkXT8TWNovYtwfIxpjvAg&sqi=2&ved=0CE4Q6AEwBQ#v=onepage&q=open%20courses%20algorithms%20and%20complexity&f=false http://books.google.com.co/books?id=SNEmAAAAMAAJ&q=algorithms+and+complexity+Garey&dq=algorithms+and+complexity+Garey&hl=es&sa=X&ei=VjoXT4m8C8f3tgfoqszyAg&ved=0CDIQ6AEwA |
| Regresar a Anterior | Nueva búsqueda |
|