Tel. +58 274 240 2685 - 240 3325.
ibc@ula.ve
|
objetivos generales y programación semestral
|
|
Se inicia con una descripción detallada de las técnicas de diseño y de análisis de algoritmos, para seguir con los algoritmos de grafos y su conexión con los problemas de completitud computacional para soluciones polinómicas y no polinómicas. Se estudian diversos algoritmos matemáticos y se finaliza con los diferentes algoritmos utilizados hasta los momentos en geometría computacional.
Brassard, G y Bratley, P. Fundamentos de algoritmia. Prentice Hall, 1997.
O'Rourque, J. Computational Geometry. 2da. Ed. Cambridge University Press, 1998.
Besembel, I. TDSO. Publicaciones de la Facultad de Ingeniería-ULA.
Knuth, D. The Art of Computer Programming. Vol. 1 y 3.. Addison-Wesley. 1975.
Baldwin, D. Algoritms and Data Structures: The Science of Computing. Charles River Media. 2004.
McConnell, J. Analysis of Algoritms: An Active Learning Approach. Jones and Bartlett Pub. 2001.
Kingston, J. Algorithms and data structures: design, correctness, analysis. Addison-Wesley, 1990.
Berlioux, P. y Bizard, P. Algorithmique: construction, preuve et évaluation des programmes. Dunod, 1983.
Elsevier. Computational Geometry. Theory and Applications. Cuatrimestral.
|
Sesión |
CONTENIDOS |
OBJETIVOS |
ACTIVIDADES |
RECURSOS |
EVALUACIÓN |
| 1 |
1. Técnicas avanzadas de diseño
y análisis: Introducción y notación TDSO. Técnicas de diseño: algoritmos incrementales, recursivos, divide-y-vencerás, backtracking y programación dinámica. |
1. Desarrollar habilidades en el uso de la notación TDSO y las técnicas de diseño de algoritmos. | http://www.ing.ula.ve/~ibc/ayda. |
|
|
| 5 |
2. Análisis amortizado: Método agregado. Método del contador. Método del potencial. Ejemplos. |
2. Lograr un alto nivel operativo en el análisis amortizado de algoritmos y tipos abstractos de datos. |
|
|
|
| 7 |
3. Técnicas de pruebas y correctitud
de algoritmos: Pruebas de corrección parcial, pruebas de parada, pruebas de programas iterativos y recursivos, eliminación de la recursividad. |
2. Desarrollar habilidades en el uso de las técnicas de prueba y corrección de algoritmos. |
|
|
|
Volver al programa
|
Sesión |
CONTENIDOS |
OBJETIVOS |
ACTIVIDADES |
RECURSOS |
EVALUACIÓN |
| 9 |
1. Fundamentos: Definiciones, especificación, representaciones, relaciones, dígrafos, dígrafos acíclicos, búsqueda en amplitud, búsqueda en profundidad, ordenamiento topológico y conectividad. |
1. Desarrollar habilidades en el uso de algoritmos para grafos. | |
|
|
| 13 |
2. Árboles abarcadores mínimos:
Algoritmos voraces. TAD Conjuntos Disjuntos. Algoritmo de Kruskal. TAD Colas de Prioridad. TAD Montículos Binomiales. TAD Montículos de Fibonacci. Algoritmo de Prim. |
2. Lograr un alto nivel operativo en el cálculo de los árboles abarcadores mínimos. |
|
|
|
| 15 |
3. Digrafos etiquetados: Caminos más cortos y relajación, algoritmo de Dijkstra, algoritmo de Bellman-Ford, restricciones y caminos más cortos (programación lineal), algoritmo de Floyd-Warshall y algoritmo de Johnson. |
2. Desarrollar habilidades en el uso de los digrafos etiquetados. |
|
|
|
| 19 |
4. Flujo máximo: Redes de flujo y método de Ford-Fulkerson. |
2. Desarrollar habilidades en el uso de las técnicas de prueba y corrección de algoritmos. |
|
|
|
Volver al programa
|
Sesión |
CONTENIDOS |
OBJETIVOS |
ACTIVIDADES |
RECURSOS |
EVALUACIÓN |
| 20 |
1. Matrices: Operaciones sobre matrices: Representaciones especiales de matrices, algoritmo de Strassen, sistemas numéricos algebraicos y multiplicación de matrices, sistemas lineales de ecuaciones, inversión de matrices, matrices simétricas positivas y aproximación de mínimos cuadrados, programación dinámica y vuelta atrás. |
1. Desarrollar habilidades en el uso de los algoritmos para matrices. | |
|
|
| 23 |
2. Algoritmos Probabilistas y Transformada Rápida
de Fourier: Algoritmos probabilistas, Transformada discreta de Fourier y transformada rápida de Fourier. |
2. Lograr un alto nivel operativo en el uso de polinomios y transformada rápida de Fourier. |
|
|
|
| 25 |
3. Algoritmos de teoría de números:
Nociones de teoría de números, máximo común divisor, aritmética modular, sistemas lineales de ecuaciones modulares, teorema de resto chino, potencias de un entero y algoritmo RSA de criptografía. |
2. Desarrollar habilidades en el uso de los algoritmos de teoría de números. |
|
|
|
Volver al programa
|
Sesión |
CONTENIDOS |
OBJETIVOS |
ACTIVIDADES |
RECURSOS |
EVALUACIÓN |
| 27 |
1. Problemas NP-completos: Clases P y NP, reducciones polinomiales, problemas NP, algunas pruebas de completitud NP, algoritmos no determinísticos y problemas NP duros. |
1. Lograr una visión general sobre los problemas de completitud computacional. | |
|
|
| 28 |
2. Heurísticas y algoritmos de aproximación:
Algoritmos heurísticos, coloreo de grafos, el problema del vendedor viajero, el problema del morral y aproximaciones a problemas NP duros. |
2. Lograr una visión general sobre el uso de las heurísticas y los algoritmos de aproximación. |
|
|
|
Volver al programa
|
Sesión |
CONTENIDOS |
OBJETIVOS |
ACTIVIDADES |
RECURSOS |
EVALUACIÓN |
| 29 |
1. Algoritmos sobre polígonos: Teoremas de galería de arte, Teoría de triangulación, área de polígono, intersección de segmentos y algoritmos de triangulación. |
1. Desarrollar habilidades en el uso de algoritmos para polígonos. | |
|
|
| 30 |
2. Partición de polígonos:
Partición monótona, trapeciolización, partición en montañas monótonas, triangulación de tiempo lineal, partición convexa. |
2. Lograr una visión general sobre los métodos de partición de polígonos. |
|
|
|
Volver al programa
