Objetivos Generales.
Se estudian los conceptos de complejidad, justificación, análisis y diseño de algoritmos.
Para desarrollar estos temas se revisan: algoritmos de búsqueda, ordenamiento y aquellos que involucran gráficas.
Se discuten clases de complejidad, revisando con detalle la Clase de los Problemas NP-Completos.
Al final se presenta algún tópico avanzado.
Requisitos:
Tener aprobado el curso de Estructuras de Datos
SE DARA PRIORIDAD A LOS ORDINARIOS, EXTRAORDINARIOS-LARGOS SÓLO SI HAY LUGAR
Habrá un grupo Especial para Extraordinarios Largos (8 semanas)
Lunes a Viernes de 5-7pm, Taller de Sistemas Operativos
Profesora: Luz Gasca Soto
T E M A R I O
I. Conceptos Básicos
II. Justificación de Algoritmos
1. Algoritmos Iterativos.
2. Algoritmos Recursivos
III. Diseño de Algoritmos usandoInducción Matemática
IV. Secuencias
1. Búsquedas (Binaria, Exponencial, por Interpolación)
2. Ordenamientos (MergeSort, QuickSort, HeapSort... )
V. Algoritmos que Involucran Gráficas
1. Recorrido en árboles (BFS,DFS, TopologicalSort)
2. Árboles Generadores de peso mínimo
3. Ruta más Corta
4.Teoría de Redes *
VI. Problemas NP-Completos
1. Introducción
2. Algoritmos Deterministicos y No-Deterministicos
3. Teoría de los Problemas NP-Completos
4. Técnicas para determinar problemas NP-Completos
5. Algoritmos de Aproximación
VII. Tópicos Avanzados
1. Tiempo Amortizado
2. Geometría Computacional
3. Algoritmos que involucran números
Calificación
50% Tareas-Examen
20% Examenes
30% Programas
-10% No Asistencia
Bibliografía
Chartran, G. And Oellermann, O.R. Applied and Algorithmic Graph Theory. Mc Graw Hill. USA, 1993.
Collins, W.J. Data Structures. An Object Oriented Approach, Addison Wesley, USA, 1992.
Cormen, T.H; L.C.E. & R.R.L. Introduction to Algorithms,Addison Wesley, USA, 2nd Edition, Third priting, 2002
Kingston, J. Algorithms and Data Structures: Design, Correctness, and Analysis. Addison Wesley, USA,1990.
Manber, U. Introduction to Algorithms. A Creative Approach, Addison Wesley, USA,1989.
Neapolitan, R. and Naimipour, K. Foundations of Algorithms. D.C. Heath and Company, USA, 1996.
Rawlins, G.J.E. Compared to what? An Introduction to the Analysis of Algorithms, Computer Science Press, USA, 1991.
M. A. Weiss, Data Structures and Algorithms Analysis in Java, Addison Wesley, 3rd. edition, 2011.