Encabezado Facultad de Ciencias
Presentación

Ciencias de la Computación (plan 2013) 2015-2

Quinto Semestre, Análisis de Algoritmos

Grupo 7302, 45 lugares. 36 alumnos.
Profesor Carlos Zerón Martínez lu mi 17 a 18:30 P102
Ayudante Erika Berenice Hernández Angulo ma ju 16 a 17 P102
Ayud. Lab.

 
Sitio del curso

Este es el sitio donde los alumnos inscritos podrán consultar más información sobre el curso

https://sites.google.com/a/ciencias.unam.mx/analisis-de-algoritmos-fciencias/?pli=1
Los alumnos que vayan a inscribirse, deberán ingresar el sitio y el correo que registren
se usará para el acceso tanto al sitio como a la lista distribución que se usará en el curso.
Introducción
En este curso se estudian los conceptos de complejidad, justi cación y diseño de
algoritmos. Para el desarrollo de estos temas se revisan diversas técnicas y tipos
de algoritmos, entre los cuales se incluyen algoritmos que involucran el uso de
búsquedas, ordenamientos y gráficas. Asimismo, se presenta una introducción
a ciertos algoritmos que tienen un propósito específi co y a los problemas NP Completos.
Contenido del curso


1. Fundamentos


a) Problemas, Ejemplares, Algoritmos y Soluciones.
b) Características de los Algoritmos.
c) Clasificación de Problemas
2. Análisis de Complejidad de Algoritmos

a) Modelos de Cómputo.
b) Modelo RAM y Tiempo de Ejecución.
c) Notacion Asintótica y Propiedades.
d) Categorías de Complejidad.

3. Justificación de Algoritmos
a) Algoritmos Recursivos.
b) Algoritmos Iterativos.

4. Diseño de Algoritmos

a) Divide y Vencerás. (Divide and Conquer)
b) Programación Dinámica. (Dynamic Programming)
c) Paradigma Greedy. (Greedy Algorithms)

5. Algoritmos de Búsqueda

a) Diccionarios y Mapas (Hashing).
b) Búsqueda Binaria y Variantes.
c) Búsqueda por Interpolación.

6. Algoritmos de Ordenamiento

a) Ordenamientos por Comparaciones.
b) Cota Mínima de Ordenamiento.
c) Ordenamientos para Casos Especiales.

7. Algoritmos Elementales en Gráficas

a) Recorridos.
b) Ordenamiento Topológico.

8. Algoritmos en Gráficas Pesadas

a) Problema del Arbol Generador de Costo Mínimo.
b) Problema de la Ruta más Corta.

9. Temas Selectos

a) Reducciones de Problemas.
b) Algoritmos No Determinísticos.
c) Introducción a Problemas NP-Completos y Algoritmos de Aproximación.

Evaluación
  • 9 Tareas 70%
  • 3 Exámenes 20%
  • Proyecto final 10%
Las fechas de entrega de tareas y del proyecto final son estrictas y los exámenes tienen fecha única de presentación, salvo por causa de fuerza mayor que sea comprobable documentalmente. Las tareas por lo general son teórico - prácticas y la entrega es individual o por equipos de dos personas, es decir, se puede pedir la descripción de algoritmos en pseudocódigo o la aplicación detallada de los mismos para casos concretos con entrega escrita y también puede pedirse su implementación en el lenguaje de programación Java, entregada por correo electrónico.
El proyecto y los exámenes son individuales. El proyecto puede involucrar una parte que requiera investigación y la solución será implementada en Java. Las normas de entrega de la parte práctica de las tareas por correo se definirán en la primera ayudantía.
Se puede presentar la reposición de ejercicios correspondientes a dos tareas, o bien, un examen final que combina una parte escrita con otra práctica, con el cual se renuncia a las calificaciones obtenidas en las tareas y exámenes. En este caso, la evaluación considera los siguientes rubros:
  • Examen final 90%
  • Proyecto final 10%
No se puede renunciar a la calificación final. Una persona obtendrá NP como calificación si no entrega nada.
Bibliografía

[1] A.V. Aho, J.E.Hopcroft and J.D.Ullman.

Data Structures and Algorithms. Addison Wesley, 1983.

[2] T. Budd.

Classic Data Structures in Java. Addison Wesley, 2001.

[3] G. Chartrand and O.R. Oellermann.

Applied and Algorithmic Graph Theory.

McGraw-Hill, 1993.

[4] T.H.Cormen, C.E.Leiserson, R.L.Rivest and C.Stein.

Introduction to Algorithms.

Second edition, McGraw-Hill, 2001.

[5] J.Kingston.

Algorithms and Data Structures: Design, Correctness and Analysis.

Addison Wesley, 1990.

[6] J.Kleinberg and E.Tardos.

Algorithms Design.

Addison Wesley, 2005.

[7] U.Manber.

Introduction to Algorithms. A creative approach.

Addison Wesley, 1989.

[8] R.Sedgewick, K.Wayne.

Algorithms.

Fourth edition, Addison Wesley, 2011.

[9] S.S.Skiena.

The Algorithm Design Manual.

Second edition, Springer-Verlag, 2008.

[10] M.A.Weiss.

Data Structures and Problem solving using Java.

Addison Wesley, 1998.

[11] M.A.Weiss.

Data Structures and Algorithn Analysis in Java.

Addison Wesley, 1999.

[12] R.E.Neapolitan and K.Naimipour.

Foundations of Algorithms using Java Pseudocode.

Jones and Bartlett Publishers, 2004.

[13] S. Dasgupta, C. Papadimitriou y U. Vazirani.

Algorithms.

McGraw-Hill, 2006.

[14] M.T.Goodrich and R. Tamassia.

Algorithm Design: Foundation, Analysis and Internet Examples.

John Wiley & Sons, 2006.

[15] C.A.Shaffer.

Data Structures and Algorithm Analysis.

Dover Publications, 2011.

 


Hecho en México, todos los derechos reservados 2011-2016. Esta página puede ser reproducida con fines no lucrativos, siempre y cuando no se mutile, se cite la fuente completa y su dirección electrónica. De otra forma requiere permiso previo por escrito de la Institución.
Sitio web administrado por la Coordinación de los Servicios de Cómputo de la Facultad de Ciencias. ¿Dudas?, ¿comentarios?. Escribenos. Aviso de privacidad.