Estructuras de datos

Ésta es la página de la unidad de aprendizaje impartida en PISIS de la FIME, UANL, a nivel doctoral en el semestre enero-junio del 2015 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. Se supone que el alumno haya cursado la unidad de algoritmos o cuente con conocimientos similares.

Objetivo

Se introducen e implementan estructuras de datos avanzados 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. Estructuras lineales: arreglos y listas
    inicio de la tarea 2
    inicio de la tarea 4
    inicio de la tarea 5
  3. Algoritmos recursivos
  4. Estructuras ramificadas: árboles
    inicio de la tarea 6
  5. Estructuras ramificadas: montículos
  6. Estructuras ramificadas: grafos
    inicio de la tarea de recorridos
  7. Dividir-conquistar
  8. Podar-buscar
  9. Algoritmos de línea de barrer
  10. Programación dinámica
  11. Ramificar-acotar
  12. 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 un algoritmo para el problema elegido, implementarlo con una estructura de datos básica y con una avanzada y comparar analítica y experimentalmente su complejidad computacional. 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 abril. Cada uno también presentará su trabajo en las últimas clases. La duración de cada presentación es 20–30 minutos.

Tareas

Hay tareas semanales desde la primera semana hasta la última. Cada tarea típicamente consiste en implementar una estructura de datos y experimentar con ella. 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 hay.

Criterios de calificación

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.

Actualizado el 6 de marzo del 2015.
URL: http://elisa.dyndns-web.com/~elisa/teaching/aa/2015.html