ESCUELA DE INGENIERÍA DE SISTEMAS

DEPARTAMENTO DE COMPUTACIÓN

Diseño y Análisis de Algoritmos

Prof. Isabel M. Besembel C.

Piso 3. Ala Sur. Oficina: 3S07. Edif. B. Facultad de Ingeniería. La Hechicera. Mérida, 5101 - Venezuela.

Tel. +58 274 240 2685.

TABLA DE CONTENIDO

Descripción del curso

Prerrequisitos,

objetivos generales y

programación semestral

Evaluación

Bibliografía

1. Técnicas avanzadas de diseño y análisis

2. Algoritmos para grafos (no incluído)

3. Algoritmos matemáticos (no incluído)

4. Completitud NP (no incluído)

5. Geometría computacional

Descripción del curso:

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.

Tipo: Obligatoria

Prelación: Programación 3 y Matemáticas Discretas

Código: ISFDAA

TPLU: 4 0 0 4

Ubicación: Sexto semestre

Ciclo: Formativo

Tabla de contenidos

Prerrequisitos:

Programación y estructuras de datos
Matemáticas discretas

Objetivos generales:

Consolidar un alto nivel en el diseño y uso de algoritmos y estructuras de datos.
Lograr un alto nivel operativo en el uso de algoritmos para grafos, matemáticos y de geometría computacional.
Comprender la importancia de la completitud computacional y la división de los problemas en aquellos de solución polinómica y los de solución no-polinómica.
Desarrollar habilidades en el análisis, diseño y construcción de algoritmos, que permitan resolver problemas presentados en orden de complejidad creciente

Programación del mini-semestre:

El mini-semestre tiene una duración de 8 semanas con una dedicación de 144 horas/mini-semestre, aproximadamente 16 horas/semana.
Horas de clase teórico-prácticas: 8 horas/semanales.
Horario del semestre B-2012: de lunes a jueves de 10-12 m. salón: 1O-04 el miércoles y el resto en el 1E-07.
Inscritos y notas

Tabla de contenidos

Evaluación:

Evaluaciones parciales: cuatro (4) pruebas escritas con un peso de 25%, 25%, 10% y 20%, para un total de 80% de la mitad de la nota definitiva.
Ejercicio práctico para la casa con un peso total de 20% de la mitad de la nota definitiva.

Tabla de contenidos

Textos:

León, L. Tejiendo algoritmos. Abstracción, crítica, secuencias y árboles. Consejo de Publicaciones, Universidad de Los Andes, 2012.

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.

Textos de consulta:

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.

Revistas de consulta:

Elsevier. Computational Geometry. Theory and Applications. Cuatrimestral.

Tabla de contenidos

Contenidos específicos:

UNIDAD 1.- Técnicas avanzadas de diseño y análisis

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.	Lecturas: guía TDSO Besembel, cap. 4 Kingston, cap. 2 Brassard y sec. 3.1 y 3.2 León. Ejercicio 1: sobre técnicas de diseño en las clases 2, 3 y 4.	Clase: clase 1, clase 2, clase 3 y clase 4. Textos Lista del curso	Corrección de la prueba escrita 1.
2	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.	Lecturas: cap. 1, 3 y 4 Brassard. Cap. 2 y 3 Kingston. sec. 3.3 León. Ejercicio 2: sobre análisis amortizado en la clase 5.	Clases: clase 5 y clase 6 Ejercicio 2 Textos Lista
2	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.	Lecturas: cap. 1-6 Berlioux y Bizard. Cap. 1 Kingston. sec. 3.4 y 3.5 León.	Clases: clase 7 y clase 8 Textos Lista	Corrección de la prueba escrita 2.

Volver al programa

UNIDAD 5.- Geometría computacional

Sesión	CONTENIDOS	OBJETIVOS	ACTIVIDADES	RECURSOS	EVALUACIÓN
3	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.	Lecturas: cap. 1 O'Rourque.	Clase: clase 9 y clase 10. Textos Lista del curso	Corrección de la prueba escrita 3.
4	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.	Lecturas: cap. 2 O'Rourque.	Clases: clase 11. Textos Lista	Corrección de la prueba escrita 4.

Volver al programa