Ciencias de la Computación (plan 2013) 2021-1

Quinto Semestre, Análisis de Algoritmos

Análisis de Algoritmos, Facultad de Ciencias, UNAM.

El análisis y diseño de algoritmos juegan un papel central en el área de las ciencias de la computación. El saber aplicar los conceptos de complejidad y justificación, es uno de los retos más complicados en el diseño de algoritmos. Este curso ofrece profundizar y dar a conocer temas como ordenamientos, búsquedas, programación dinámica, estrategias voraces y algoritmos que involucran el uso de gráficas, con el fin de contar con un amplio bagaje para confrontar los problemas que un científico de la computación tiene en su vida profesional.

Temario

1. Introducción al diseño y análisis de algoritmos
2. Ordenación
3. Búsqueda y medianas
4. Programación Dinámica
5. Algoritmos Voraces (greedy)
6. Algoritmos en gráficas
7. Breve introducción de NP-completez
8. Temas selectos de geometría computacional

Libros:

Introduction to Algorithms.

Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford. The MIT Press. 2009

The Algorithm Design Manual

Skiena, Steven S. Springer Publishing Company, Incorporated. 2008

Algorithm Design

Jon Kleinberg and Éva Tardos. 2005.

Algorithms Illuminated (Part 1): The Basics

Tim Roughgarden, Columbia University. 2017.

Algorithms Illuminated (Part 2): Graph Algorithms and Data Structures

Tim Roughgarden, Columbia University. 2018.

Algorithms Illuminated (Part 3): Greedy Algorithms and Dynamic Programming

Tim Roughgarden, Columbia University. 2019.

Algorithms Illuminated (Part 4): Algorithms for NP-Hard Problems

Tim Roughgarden, Columbia University. 2020.

Dinámica del curso:

Las sesiones del curso serán usando zoom. Todos los días a la hora de clase.

Favor de ver la página el viernes 18 de septiembre de 2020 por la tarde para obtener el identificador.

Nota importante: Se decidió escribir directamente a la lista de correos que la facultad proporciona a los profesores, por lo que recibiran un correo el sábado 19 de septiembre, para tener la lista de estudiantes lo más completa posible, ya que se encuentran alumnos en espera de asignación.

Es importante que los alumnos actualicen su correo electrónico en la página de la facultad para estar en contacto.

Sistema de calificaciones:

Tareas - Exámen: 70 %

Examen Final Oral: 30 % o dependiendo del número de alumnos inscritos, será exposición.

Para acreditar el curso, los estudiantes tienen que promediar al menos 60% en cada rubro de calificación.

Tendremos 5 o 6 tareas durante el semestre. Las tareas se entregarán el día señalado hasta las 23:59 hrs. como máxima hora de entrega y serán en formato latex/pdf, NO se aceptarán tareas hechas a mano.

No hay recuperaciones.

Se dará prioridad a inscripciones ordinarias.

En caso de plagio los involucrados en el hecho se harán acreedores a la calificación de 0.

UNA VEZ QUE COMIENCE A RECIBIR CALIFICACIONES NO ES POSIBLE ELEGIR NP.