Análisis y diseño de algoritmos

Ésta es la página de la unidad de aprendizaje impartida en PISIS de la FIME, UANL, a nivel posgrado (especialmente maestría, dando bienvenida a alumnos doctorales que necesitan fortalecer su conocimiento algorítmico) en el semestre enero-junio del 2017 por Elisa Schaeffer los lunes V1–4 (12:00–15:20) @ 5303.

Requisitos

Se necesita contar con un buen entendimiento de varios los conceptos matemáticos, especialmente de matemáticas discretas y probabilidad, o en el caso contrario, estar preparado a estudiarlos según necesidad. También se necesita conocimiento de programación en algún lenguage de programación como por ejemplo Python, C/C++, Scala o Java.

Objetivo

Se introducen los métodos del análisis y diseño de algoritmos para aplicar en algoritmos con el fin de mejor entendimiento de su función y mayor eficiencia en las implementaciones.

Temario

  1. Asuntos organizacionales; fundamentos y repaso
  2. Problemas y algoritmos; máquinas Turing
  3. Complejidad computacional; problemas fundamentales; clases de complejidad
  4. Reducciones y problemas completos
  5. Estructuras de datos
  6. Análisis de algoritmos; técnicas de diseño de algoritmos
  7. Algoritmos de aproximación y computación aleatoriazada
  8. Transiciones de fase

Tareas

Las tareas de programación son individuales: se recomiendan estudiar juntos y discutir las soluciones, pero no se toleran ningún tipo de plagio en absoluto, ni de otros estudiantes ni de la red ni de libros — toda referencia bibliográfica tiene que ser apropiadamente citada. La entrega se realiza por un repositorio en GitHub que debe reflejar todas las fases del trabajo en su log correspondiente. El alumno selecciona su lenguaje de programación y debe respetar la misma selección a lo largo de la unidad (es decir: no se permite cambiarlo). Son ocho tareas, otorgando por máximo 15 puntos por tarea. La calificación final es min(sum(tareas), 100)). No habrá examen.

  1. Representación y manipulación de grafos
  2. Generadores de instancias
  3. Heurísticas para SAT
  4. Recorridos y caminos en grafos
  5. Flujos y árboles de expansión
  6. Ramificaciones y búsquedas para optimización
  7. Aleatorización
  8. Experimentos con transiciones de fase

Materiales

Hay muchos libros y sitios del web sobre el tema. No es obligatorio comprar ningún libro, aunque sin embargo será útil tener acceso a unos libros (de la biblioteca) o al Internet cuando se trabaja en las tareas semanales.

Si sienten una compulsión de imprimir algo, que no sean las diapositivas sino las notas. No recomiendo imprimir nada si leen comodamente de pantalla.

El mundo está lleno de libros sobre algoritmos. Los siguientes libros de texto, que son favoritos personales de la profesora, sirven como material de estudio, aunque asistencia en las clases o estudio de las diapositivas cubrirá los temas esenciales también. No realmente hace falta traer un libro a la clase — libros sirven para las tareas y trabajo fuera del clase. (Sí, estamos en nivel de doctorado y todos los libros recomendados están en inglés. Las clases, las diapositivas y el material de soporte escrito por la profesora están en castellano.)

Libros

Notas y tutoriales

Enlaces útiles

Repositorios

? = tarea no claramente identificada
r = tarea no marcada lista para calificar
- = alumno reporta la tarea como omitida
15 = excede lo que se esperaba (100 %)
12 = cumple con lo que se esperaba (80 %)
10 = ligeramente débil en alcance y/o calidad (67 %)
7 = gravemente débil en alcance y/o calidad (46 %)
5 = gravemente débil en alcance y calidad los dos (33 %)
0 = completamente inadecuado en alzance y calidad (0 %)

ParticipanteT1T2T3T4T5T6T7T8Σ
Anaid 12101210121077 80
Eduardo 1015121215151515 100+
Juan Antonio 1210101010101215 89
Juan Pablo 12121012771012 82
Missael 101012151271212 90
Norberto 1212121212101515 100
Pamela 1515151512121512 100+
Pepe 1212121215101010 93
Actualizado el 16 de junio del 2017.
URL: http://elisa.dyndns-web.com/~elisa/teaching/aa/2017.html