Análisis y diseño de algoritmos

Ésta es la página de la unidad de aprendizaje impartida en PISIS de la FIME, UANL, impartida a nivel doctoral en el semestre agosto-diciembre del 2014 por la Dra. Elisa Schaeffer los martes y jueves M5&6 (10:20–12:00), salón 5303. Estudiantes del maestría de PISIS pueden inscribirse en el curso con permiso de su tutor asignado. Estudiantes que no son de los programas de maestría o doctorado de PISIS pueden entrar de oyentes si hay cupo en el salón a la hora de clase.

Requisitos

Se necesita tener 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 básico de programación en algún lenguage procedural como C/C++, Java o Python.

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 y horario

Es (por lo general) una sesión teórica (para revisar contenido nuevo) y una práctica (para revisar las tareas del contenido anterior) durante 16 semanas.

Temario

  1. Asuntos organizacionales; fundamentos
  2. Problemas y algoritmos
  3. Máquinas Turing
  4. Complejidad computacional
  5. Problemas fundamentales
  6. Clases de complejidad
  7. Reducciones y problemas completos
  8. Algoritmos de aproximación y computación aleatoriazada
  9. Transiciones de fase
  10. Presentaciones de proyectos

Proyecto individual

Empezando ya desde el comienzo del semestre, en paralelo con las clases, cada estudiante prepara un proyecto individual. Colaboración entre estudiantes es recomendable, pero los proyectos son individuales y entonces cada uno necesita entregar su propio informe técnico (en el formato de una revista indizada).

El proyecto consiste en los siguientes pasos: elegir un problema de un caso práctico que interesa al estudiante mismo, desarrollar o buscar en la literatura uno o dos algoritmos para el problema elegido y analizar su complejidad en teoría y por experimentos. Habrá que escribir un informe de seis a diez páginas de los resultados del estudio en el formato de un artículo científico.

El informe inicial se entrega por correo electrónico en formato PDF a la profesora antes del fin de octubre. Cada uno también presentará su trabajo en la última clase. La duración de cada presentación es 20 minutos.

Tareas

Las tareas 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. Un estudiante que entrega una solución debe ser capaz estar preparado a presentarla en clase.

Exámenes

No habrá examen.

Criterios de calificación

Se utiliza la siguiente ponderaación aproximada:

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

  • Actualizado el 21 de octubre del 2014.
    URL: http://elisa.dyndns-web.com/~elisa/teaching/aa/2014.html