Análisis y Diseño de Algoritmos (AyDA)

Unidades crédito: 4004

Programación semestral: Semestre de 16 semanas con 160 horas/semestre y 10 horas/semana.

Prof. Isabel M. Besembel Carrera.

Núcleo Pedro Rincón Gutiérrez. La Hechicera. Edificio B. Facultad de Ingeniería. Escuela de Sistemas. Ala Sur. Piso 3. Cubículo 3S07. Mérida 5101-Venezuela.

Tel. +58 274 240 2685 - 240 2811.

TABLA DE CONTENIDO

Descripción del curso,
Conocimiento previo,
Objetivos generales y
Programación semestral

Evaluación y
Bibliografía

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

2. Estructuras de datos avanzadas

3. Algoritmos para grafos y matemáticos

4. Geometría computacional

5. Complejidad 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 aplicadas a los principales métodos de ordenamiento y búsqueda tanto internos como externos, para seguir con las estructuras avanzadas de datos haciendo énfasis en los árboles, se continua con los algoritmos de grafos y los algoritmos matemáticos incluyendo también los algoritmos multihilos. Luego se estudian diversos algoritmos utilizados hasta los momentos en geometría computacional, para finalizar con los problemas de complejidad computacional polinómica y no polinómica.
Durante el curso se utilizarán estrategias de aprendizaje donde se desarrolle investigación documental con su respectiva presentación y defensa de los resultados obtenidos ante el curso.

Conocimiento previo:

Programación digital y manejo de archivos en algún lenguaje de programación, se recomienda el lenguaje java o C++.
Técnicas de acceso asociativo a memoria: hashing e índices
Estructuras de datos: arreglos, registros, cadenas, listas, árboles binarios y montículos.
Técnicas de Ingeniería de Software orientada por objetos.

Objetivos generales:

Consolidar el conocimiento previo en análisis, diseño y uso de algoritmos y estructuras de datos.
Consolidar habilidades de investigación y exposición de resultados sobre temas incluidos en el contenido programático del curso.
Lograr un alto nivel operativo en el uso de algoritmos para estructuras de datos avanzadas, grafos, multihilos, matemáticos, concordancia de patrones y de geometría computacional.
Comprender la importancia de la complejidad 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 como ejercicios prácticos, en orden de complejidad creciente.

Programación semestral:

El semestre tiene una duración de 16 semanas con una dedicación de 160 horas/semestre, aproximadamente 10 horas/semana.
Horas de clase teórico-prácticas: 4 horas/semanales.
Plan

Tabla de contenidos

Evaluación:

Prueba diagnóstico para evaluar los conocimientos previos del curso.
Ejercicios teóricos-prácticos de programación en C++ o java sobre algún tema específico de cada unidad. Cada ejercicio tendrá el peso siguiente:
- Ejercicio 1, 2, 3 y 4: 2% c/u
- Ejercicio 5, 6, 7 y 8: 3% c/u
- Ejercicio 9, 10 y 11: 4% c/u
- Ejercicio 12 y 13: 5% c/u
- Ejercicio 14: 8%
para un total de 50% de la nota final.
Consultas y discusiones semanales.
Evaluación final presencial con un 50% de la nota final.

Bibliografía

Texto:

T. Cormen, C. Leiserson, R. Rivest y C. Stein. Introduction to algorithms. MIT Press and McGraw-Hill. 2009.

Textos de consulta:

Knuth, D. The Art of Computer Programming. Vol. 1 y 3.. Addison-Wesley. 1975.
Brassard, G y Bratley, P. Fundamentos de algoritmia. Prentice Hall, 1997.
O'Rourque, J. Computational Geometry. 2da. Ed. Cambridge University Press, 1998.
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.
M. Garey y D. Jhonson. Computers and inractability: A guide to the theory of NP-Completeness. Freeman, 1979.

Revistas de consulta:

Elsevier. Computational Geometry. Theory and Applications. Cuatrimestral.
ACM Transaction on Database Systems (TODS), SIGMOD, Computing Surveys, Communications, etc.

Tabla de contenidos

Contenidos específicos:

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

SESIÓN	CONTENIDOS	OBJETIVOS	ACTIVIDADES	RECURSOS	EVALUACIÓN
1 2 3	1. Análisis de algoritmos: Tipos abstractos de datos (TAD), notación TDSO, notaciones estándares, funciones comunes, análisis probabilístico y análisis amortizado: Método agregado, método del contador, método del potencial y tablas dinámicas.	1. Lograr una visión general sobre el análisis de algoritmos y los tipos abstractos de datos (TAD).	Lecturas: cap. 1-5 y 17 Cormen y col. Ejercicio 1: sobre TAD.	Clase: clase 1, clase 2 y clase 3 . Ejercicio 1 Textos Lista del curso	Corrección del ejercicio 1.
4 5 6	2. Técnicas de diseño: Introducción a las técnicas de diseño: algoritmos incrementales, recursivos, divide-y-vencerás, backtracking y programación dinámica.	2. Obtener un panorama genérico sobre las técnicas de diseño de algoritmos.	Lecturas: guía TDSO Besembel, cap. 2, 4, 15 y 16 Cormen y col. Ejercicio 2: sobre técnicas de diseño.	Clases: Clase 4, clase 5 y clase 6 Ejercicio 2 Textos Lista	Corrección del ejercicio 1 (2%).
7 8	3. Técnicas de pruebas y corrección 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. Ejercicio 3: sobre pruebas de corrección de algoritmos.	Clases: clase 7 y clase 8 Ejercicio 3 Textos Lista	Corrección del ejercicio 2 (2%).

Tabla de contenidos

UNIDAD 2.- Estructuras de datos avanzadas

SESIÓN	CONTENIDOS	OBJETIVOS	ACTIVIDADES	RECURSOS	EVALUACIÓN
9 10 11	1. Fundamentos: Estructuras lineales de datos: Pilas, Colas y Listas. Hashing perfecto. Colas por prioridad. Aumento de estructuras de datos y árboles de intervalos. Montículos binarios y de Fibonacci: estructura y operaciones. Conjuntos disjuntos: operaciones, bosques y análisis de la unión por rango con caminos de compresión.	1. Desarrollar habilidades en el uso de estructuras de datos complejas.	Lecturas: Cap. 6, 10-14, 19 y 21 Cormen y col. Ejercicio 4: sobre conjuntos disjuntos.	Clase: clase 9 , clase 10 y clase 11. Ejercicio 4 Textos Lista del curso	Corrección del ejercicio 3 (2%).
12 13	2. Árboles monocriterio: Introducción. Árbol binarios de búqueda y rojinegros. Familia de árboles_B. Htree.	2. Lograr una visión general sobre las estructuras de datos para el manejo de índices construidos por una clave.	Lecturas: Cap. 12-13, 18 y 20 Cormen y col. Ejercicio 5: sobre árboles_B+.	Clase: clase 12 y clase 13 clase 13a. Ejercicio 5 Textos y artículo árbol H Lista del curso	Corrección del ejercicio 4 (2%).
14 15	3. Árboles multicriterio: Introducción. Árbol k-d. Quadtree. Octree. Árbol_R.	3. Lograr una visión general sobre las estructuras de datos para el manejo de índices construidos por dos o más claves.	Lecturas: Artículos sobre cada estructura de datos. Ejercicio 6: sobre árboles_R.	Clase: clase 14 y clase 15. Ejercicio 6 Textos y artículo árbol_R Lista del curso	Corrección del ejercicio 5 (3%).

Tabla de contenidos

UNIDAD 3.- Algoritmos para grafos y algoritmos matemáticos

SESIÓN	CONTENIDOS	OBJETIVOS	ACTIVIDADES	RECURSOS	EVALUACIÓN
16 17	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. Árboles de expansión mínima: algoritmos de Kruskal y Prim.	1. Lograr una visión general sobre los algoritmos para grafos.	Lecturas: Cap. 22 y 23 Cormen y col. Ejercicio 7: sobre grafos.	Clase: clase 16 y clase 17. Ejercicio 7 Textos Lista del curso	Corrección del ejercicio 6 (3%).
18 19 20	2. 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. Flujo máximo: Redes de flujo y método de Ford-Fulkerson.	2. Desarrollar habilidades en el uso de los digrafos etiquetados.	Lecturas: Cap. 24-26 Cormen y col. Ejercicio 8: sobre digrafos etiquetados.	Clases: clase 18, clase 19 y clase 20. Ejercicio 8 Textos Lista	Corrección del ejercicio 7 (2%).
21	3. 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.	3. Desarrollar habilidades en el uso de los algoritmos para matrices.	Lecturas: Cap. 28 de Cormen y col. Ejercicio 9: sobre matrices.	Clase: clase 21. Ejercicio 9 Textos Lista del curso	Corrección del ejercicio 8 (3%).
22 23	4. Algoritmos Probabilistas y Transformada Rápida de Fourier: Algoritmos multihilos y Programación lineal, Transformada discreta de Fourier y transformada rápida de Fourier.	4. Lograr un alto nivel operativo en el uso de polinomios y transformada rápida de Fourier.	Lecturas: Cap. 27 y 29-30 de Cormen y col. Ejercicio 10: sobre polinomios, la transformada rápida de Fourier y teoría de números.	Clases: clase 22 y clase 23. Ejercicio 10 Textos Lista	Corrección del ejercicio 9 (4%).
24 25	5. 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.	5. Desarrollar habilidades en el uso de los algoritmos de teoría de números.	Lecturas: Cap. 31 de Cormen y col. Ejercicio 11: sobre algoritmos numéricos.	Clases: clase 24 y clase 25 Ejercicio 11 Textos Lista	Corrección del ejercicio 10 (4%).

Tabla de contenidos

UNIDAD 4.- Geometría computacional

SESIÓN	CONTENIDOS	OBJETIVOS	ACTIVIDADES	RECURSOS	EVALUACIÓN
26 27	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. 33 de Cormen y col. Cap. 1 O'Rourque. Ejercicio 12: sobre polígonos.	Clase: clase 26 y clase 27. Ejercicio 12 Textos Lista del curso	Corrección del ejercicio 11 (4%).
28	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. Ejercicio 13: sobre polígonos.	Clases: clase 28. Ejercicio 13 Textos Lista	Corrección del ejercicio 12 (5%).

Tabla de contenidos

UNIDAD 5.- Complejidad Computacional

SESIÓN	CONTENIDOS	OBJETIVOS	ACTIVIDADES	RECURSOS	EVALUACIÓN
29	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.	Lecturas: cap. 34 Cormen y col. Ejercicio 14: sobre pruebas de completitud NP y heurísticas.	Clase: clase 29 . Ejercicio 14 Textos Lista del curso	Corrección del ejercicio 13 (5%).
30	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.	Lecturas: Cap. 35 de Cormen y col.	Clase: clase 30. Textos Lista	Corrección del ejercicio 14 (8%). Prueba escrita presencial. (50%).

Tabla de contenidos