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

Quinto Semestre, Análisis de Algoritmos

La presentación del curso se llevará a cabo el lunes 28 de enero en el salón de clases señalado.

El sitio de apoyo al curso se encuentra en esta dirección:

https://sites.google.com/ciencias.unam.mx/analisis-de-algoritmos/

Objetivos Generales

El estudio de algoritmos forma una parte significativa de los fundamentos de las ciencias de la computación que tiene un impacto profundo en las ciencias en general y en la industria. En este curso se estudian los conceptos de complejidad, justificación y diseño de algoritmos, de modo que puedan aplicarse en diversos tipos de problemas comunes que involucran búsquedas, ordenamientos y gráficas. Asimismo, se presentan ciertos temas sobre subáreas de estudio de la computación teórica prominentes para el desarrollo de algoritmos, en las cuales el alumno puede profundizar posteriormente.

Requisitos para inscripción

C. Computación - Plan 2013

• Útiles: Matemáticas para las ciencias aplicadas I, Algebra Superior II, Probabilidad
• Indispensable: Estructuras de Datos.

C. Computación - Plan 1994

• Útiles: Cálculo Diferencial e Integral I, Algebra Superior II, Probabilidad y Estadística
• Indispensable: Introducción a Ciencias de la Computación II.

Contenido del curso

1) Fundamentos

1.1 Problemas, Ejemplares, Algoritmos y Soluciones.

1.2 Características de los Algoritmos.

1.3 Tipos de Problemas.

2) Análisis de Complejidad de Algoritmos

2.1 Modelos de Cómputo.

2.2 Modelo RAM y Tiempo de Ejecución.

2.3 Notación Asintótica y Propiedades.

2.4 Categorías de Complejidad.

3) Justificación de Algoritmos

3.1 Algoritmos Recursivos.

3.2 Algoritmos Iterativos.

4) Diseño de Algoritmos

4.1 Divide y Vencerás

4.2 Programación Dinámica

4.3 Paradigma Greedy

5) Algoritmos de Búsqueda

5.1 Diccionarios y Mapas (Hashing)

5.2 Búsqueda Binaria y Variantes.

5.3 Búsqueda por Interpolación

6) Algoritmos de Ordenamiento

6.1 Ordenamientos por Comparaciones.

6.2 Cota Mínima de Ordenamiento.

6.3 Ordenamientos para Casos Especiales.

7) Algoritmos Fundamentales en Gráficas

7.1 Recorridos.

7.2 Ordenamiento Topológico.

8) Algoritmos para Optimización en Gráficas

8.1 Problema del Arbol Generador de Costo Mínimo.

8.2 Problema de la Ruta más Corta.

8.3 Flujo en Redes

9) Temas Selectos *

9.1 Apareamiento de cadenas

9.2 Teoría de números y Criptografía

Evaluación

• 9 - 10 Tareas 60%

• 3 Exámenes 20%

• Proyecto final 10%

• Participaciones 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. La entrega de las tareas es individual por escrito (a mano o a máquina) y pueden consistir en describir algoritmos en pseudocódigo o aplicar de forma detallada los mismos para casos concretos y también puede pedirse su implementación en el lenguaje de programación Java, entregada por correo electrónico. Las normas de entrega de la parte práctica de las tareas por correo se definirán en la primera semana de clases.

El proyecto involucra una parte que requiera investigación sobre algún problema y otra de implementación de su solución en Java.

Las participaciones consisten, de manera obligatoria, en la entrega de ejercicios de desarrollo corto por escrito y de manera opcional, por la realización de ejercicios frente al grupo.

Se puede presentar la reposición de dos tareas y de un examen parcial, 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, exámenes y participaciones. 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.

Referencias

[1] J.Kleinberg and E.Tardos. Algorithms Design. AddisonWesley, 2005.

[2] T.H.Cormen, C.E.Leiserson, R.L.Rivest and C.Stein. Introduction to Algorithms. 2nd edition, McGraw-Hill, 2001.

[3] S. Dasgupta, C. Papadimitriou y U. Vazirani. Algorithms. McGraw-Hill, 2006.

[4] M.T. Goodrich and R. Tamassia. Algorithm Design and Applications. John Wiley and Sons, 2015.

[5] U.Manber. Introduction to Algorithms. A creative approach. AddisonWesley, 1989.

[6] S.S.Skiena. The Algorithm Design Manual. 2nd edition, Springer-Verlag, 2008.

[7] M.A.Weiss. Data Structures and Algorithm Analysis in Java. Addison Wesley. 3rd edition, 2012.

[8] R.E.Neapolitan and K.Naimipour. Foundations of Algorithms using Java Pseudocode. Jones and Bartlett Publishers, 2004.

[9] J.Kingston. Algorithms and Data Structures: Design, Correctness and Analysis. Addison Wesley, 1990.

[10] G. Chartrand and O.R. Oellermann. Applied and Algorithmic Graph Theory. McGraw-Hill, 1993.

[11] R.Sedgewick, K.Wayne. Algorithms. 4th edition, Addison Wesley, 2011.