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 doctorado en enero-junio 2020 los miércoles de M5 a V2 (10:20 a 13:40) en el 5307.

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.

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.

Sesiones

Se van a estar leyendo las notas del curso de manera colectiva, definiendo al final de cada sesión entre los participantes las tareas de cada quien (ningunas dos personas harán la misma cosa). Las tareas se revisan al inicio de la sesión siguiente. Análisis matemáticos se suben en PDF, hechas en LaTeX, mientras implementaciones se suben como código, con posibles imágenes para ilustrar resultados.

  1. [22 de enero]
    • Lectura y discusión del capítulo 1
    • Definición de la tarea 1
  2. [29 de enero]
    • Revisión de la tarea 1
    • Discusión de la lectura previa del capítulo 2
    • Definición de la tarea 2
  3. [5 de febrero]
    • Revisión de la tarea 2
    • Discusión de la lectura previa del capítulo 3
    • Definición de la tarea 3
  4. [12 de febrero]
    • Revisión de la tarea 3
    • Discusión de la lectura previa del capítulo 4
    • Definición de la tarea 4
  5. [19 de febrero]
    • Revisión de la tarea 4
    • Discusión de la lectura previa de las secciones 5.1–5.4
    • Definición de la tarea 5
  6. [26 de febrero]
    • Revisión de la tarea 5
    • Discusión de la lectura previa de las secciones 5.5–5.7
    • Definición de la tarea 6
  7. [4 de marzo]
    • Revisión de la tarea 6
    • Discusión de la lectura previa de las secciones 6.1–6.2
    • Definición de la tarea 7
  8. [11 de marzo]
    • Revisión de la tarea 7
    • Discusión de la lectura previa de la sección 6.3
    • Definición de la tarea 8
  9. [18 de marzo]
    • Revisión de la tarea 8
    • Discusión de la lectura previa de la sección 6.4
    • Definición de la tarea 9
  10. [25 de marzo]
    • Revisión de la tarea 9
    • Discusión de la lectura previa de la sección 6.5
    • Definición de la tarea 10
  11. [1 de abril]
    • Revisión de la tarea 10
    • Discusión de la lectura previa de las secciones 6.6–6.8
    • Definición de la tarea 11
  12. [8 de abril] Asueto de la UANL por Semana Santa
  13. [15 de abril] Asueto de la UANL por Semana Santa
  14. [22 de abril]
    • Revisión de la tarea 11
    • Discusión de la lectura previa de las secciones 7.1–7.2
    • Definición de la tarea 12
  15. [29 de abril]
    • Revisión de la tarea 12
    • Discusión de la lectura previa de la sección 7.3
    • Definición de la tarea 13
  16. [6 de mayo]
    • Revisión de la tarea 13
    • Discusión de la lectura previa de la sección 7.4
    • Definición de la tarea 14
  17. [13 de mayo]
    • Revisión de la tarea 14
    • Discusión de la lectura previa de los capítulos 8–9
    • Definición de la tarea 15
  18. [20 de mayo]
    • Revisión de la tarea 15
    • Discusión de la lectura previa del capítulo 10
    • Definición de la tarea 16
  19. [27 de mayo]
    • Revisión de la tarea 16
    • Discusión de la lectura previa del capítulo 11
    • Definición de la tarea 17
  20. [3 de junio]
    • Revisión de la tarea 17
    • Discusión de la lectura previa del capítulo 12
    • Opcional por puntos extra: definición de la tarea 18

Tareas

Las tareas de programación son individuales; se recomienda 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 para cada tarea.

Son 17 tareas (más una opcional por puntos extra al final del semestre), otorgando por máximo 7 puntos por tarea. La calificación final es min(sum(tareas), 100)). No habrá examen.

NP = tarea omitida
7 = claramente excede lo que se esperaba
6 = excede un poco lo que se esperaba
5 = cumple con lo que se esperaba
4 = ligeramente débil en alcance y/o calidad
3 = gravemente débil en alcance y/o calidad
2 = gravemente débil en ambos alcance y calidad
1 = da lástima, pero no contribuye nada de peso
0 = completamente inadecuado en alzance y calidad

Participante Puntos de las 17 tareas regulares y la tarea extra CF
AA 5555NP4NP 44NP56NP4 56NPNP NA
AB 6575366 7445634 554NP 85
DQ NP67NP3NP6 3535NPNPNP NPNPNPNP NA
MB 7675756 6565535 5656 100

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.

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

Mencionados al discutir el capítulo 1

Otros libros

Notas y tutoriales

Enlaces útiles

Actualizado el 29 de mayo del 2020.
URL: http://elisa.dyndns-web.com/~elisa/teaching/aa/2020.html