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

Quinto Semestre, Análisis de Algoritmos

Temario:

1. Introducción a la complejidad de los algoritmos, algunos ejemplos interesantes.
2. Ordenación y búsqueda, cotas inferiores, hepsort, mergesort, quicksort, etc.
3. Búsquedas binarias, árboles binarios. Mediana y k-selección.
4. Programación dinámica, multiplicación de matrices, subsucesión común mas larga, subsucesión creciente mas larga, triangulación de peso mínimo de polígonos convexos.
5. Algoritmos greedy.
6. Algoritmos para gráficas, la ruta mas corta, árboles generadores de peso mínimo, flujos en redes.
7. Breve introducción a los problemas NP-completos.

A lo largo del curso estudiaremos varios problemas recientes cuya solución fue basada en los algoritmos básicos que estudiaremos durante el curso. Por ejemplo, estudiaremos varios problemas de la Geometría Computacional, estructuras de datos dinámicas, problemas de clasificación de datos, problemas de rutas en redes ad-hoc e inalámbricas, etc.

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

Dinámica del curso:

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

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

Sistema de calificaciones:

Las tareas serán entregadas usando classroom.

Tareas - Exámen: 70 %

Dos examenes presenciales: 30 %. Este porcentaje está sujeto a cambios.

Primer examen viernes 07 de octubre de 2022 de 12:00 a 14:30 hrs. en salón Salicrup Instituto de Matemáticas.

Segundo examen viernes 09 de diciembre de 2022 de 12:00 a 14:30 hrs. en salón Salicrup Instituto de Matemáticas.

Para acreditar el curso, los estudiantes tienen que promediar al menos 60% en examenes y tareas-exámenen y en caso de realizarse los examenes presenciales es obligatorio presentarlos para acreditar el curso.

Tendremos 5 o 6 tares durante el semestre. Que deben entregarse por correo en formato pdf, es importante mencionar que no se aceptan tareas con lápiz.

NO hay extraordinarios largos, sólo se aceptan inscripciones ordinarias.

NO hay exámenes de reposición.

UNA VEZ QUE COMIENCE A RECIBIR CALIFICACIONES EN TAREAS-EXAMEN NO SON ELEGIBLES A NP.