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

Quinto Semestre, Análisis de Algoritmos

La presentación se llevará a cabo el Lunes 27 de enero del 2020 a las 15:00 horas en el salón de clase; ese día se especificará el mecanismo de acceso al sitio de apoyo al curso, ubicado en 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, con el fin de aplicarlos en diversos tipos de problemas en las ciencias de la computación que involucran búsquedas, ordenamientos y gráficas. Al final, 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
• Indispensables: Estructuras de Datos.

C. Computación - Plan 1994

• Útiles: Cálculo Diferencial e Integral I, Algebra Superior II, Probabilidad y Estadística
• Indispensables: 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 Tiempo de Ejecución.

2.3 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 Algoritmos Codiciosos

5) Algoritmos de Búsqueda

5.1 Diccionarios

5.2 Búsqueda Binaria y Variantes.

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 Calendarización

9.2 Apareamiento de cadenas

Evaluación

• 9 - 10 Tareas largas 60%

• Participaciones 30%

• Proyecto final 10%

Las participaciones consisten, de manera obligatoria, en la entrega de ejercicios de desarrollo corto (tareas cortas) en la plataforma Classroom, cuyo código se proporcionará a los alumnos inscritos. De manera opcional, por la realización de ejercicios frente al grupo.

Las tareas cortas y largas se entregan en forma individual mediante la plataforma Classroom y se registrará una penalización de dos puntos por cada día natural de retraso con respecto a la fecha de entrega estipulada. A partir del quinto día de retraso en la entrega se le asigna cero de calificación. La fecha de entrega del proyecto final es única.

Es posible evitar la penalización si es posible comprobar mediante un documento alguna causa de fuerza mayor que justifique la omisión en la entrega de tareas cortas, largas y proyecto.

Las tareas 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.

Se puede presentar la reposición de dos tareas largas, 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 largas 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. 3rd edition, MIT Press, 2009.

[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. Foundations of Algorithms. Jones and Bartlett Learning. 5th edition, 2015.

[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.