Ciencias de la Computación (plan 2013) 2024-2

Segundo Semestre, Estructuras de Datos

Presentación

El curso de Estructuras de Datos es un bloque constructor requerido por materias avanzadas como Análisis de algoritmos, Inteligencia Artificial y Compiladores. Su objetivo principal y los(as) estudiantes aprendan a definir, analizar, elegir e implementar estructuras de acuerdo a sus necesidades.

Los conceptos y técnicas que se enseñan en este curso deben dotar al(a) estudiante de la capacidad incluso para modificar y adaptar estructuras según sus necesidades particulares y no limitarse a hacer uso de las implementaciones por defecto que incluyen los lenguajes.

Actividades

El semestre consta de 16 semanas de clases y 2 de exámenes. Durante las semanas de clases se realizarán las actividades siguientes:

• 11 prácticas de programación
• 3 proyectos
• 3 exámenes parciales
• Entre 8 y 14 exámenes semanales, algunos presenciales otros en línea, se pueden resolver en 10 minutos.

Prácticas de programación

Son actividades de programación diseñadas para que los(as) estudiantes aprendan a utilizar algunas estructuras ya provistas por el lenguaje de programación y, la gran mayoría, a implementar las estructuras de datos desde cero.

En semestres pares, el lenguaje de programación a utilizar será Java y en semestres impares C#.

Se dejan una o dos prácticas por semana. Las más complejas han sido divididas en dos partes y valen el doble que las demás prácticas.

Se entregan de forma individual. Si se detectan copias, la calificación se divide entre el número participantes. Copiar de sitios de internet implica cero directo en la práctica. Se permite, más aún se fomenta, la consulta de fuentes oficiales así como la discusión entre compañeros para resolver los problemas, pero no se permiten las soluciones colectivas. Cada quien debe desarrollar su propia solución.

Proyectos

Tienen un peso mayor en la calificación pues los proyectos son de realización más libre. No se dan tantas guías como en las prácticas y los(as) estudiantes deben aplicar los conceptos en forma más libre, proponiendo sus propios diseños. El tiempo que se da para resolverlos es semejante al de una práctica, pues no requieren más trabajo, sólo más creatividad e iniciativa.

Parciales

Son 75% preguntas teóricas y 25% programación en papel (sin consulta de notas, documentación o compiladores). Los ejercicios de programación se pueden resolver fácilmente si se han estado haciendo correctamente las prácticas de laboratorio, exámenes semanales y se ha practicado con los ejercicios recomendados en clase.

Los parciales se presentarán de forma presencial en el horario y salón indicado de forma obligatoria incluso si algunos de ellos se presentan por computadora; pueden llevar sus propias laptops o usar las computadoras del taller. Se tomará asistencia y se puede solicitar su credencial de estudiantes el día del examen.

Exámenes semanales

Son pequeños cuestionarios de opción múltiple, arrastrar y soltar, ordenar enunciados, completar código etc. cuando se realizan en la plataforma del curso y se dan 24 hrs para responderlos. Otros son ejercicios de programación en papel que se realizan en el salón de clase los últimos 10 minutos de la clase, usualmente de la segunda clase de la semana, en condiciones semejantes a las de un parcial, pero son mucho más breves.

Material en línea

El curso cuenta con videos de los temas a cubrir, los cuales fueron grabados durante la pandemia y siguen poniéndose a su disposición como material de consulta. El material fue grabado en Java. Sólo está como apoyo, no es obligatorio utilizarlo.

Cada semana se publicarán las actividades a realizar en el aula de moodle, incluyendo los temas de la semana, trabajo de laboratorio y los cuestionarios, cuando se apliquen en línea.

Plan de contingencia

En caso de que, por algún motivo, no nos sea posible tomar las clases de forma presencial, las sesiones se tendrán por Zoom, se les enviará la invitación por el chat del grupo unos minutos antes de la hora de clase.

Vías de comunicación

Moodle será la plataforma central desde la cual se gestiona el curso. Sin embargo, está incomunicada, no cuenta con permisos para enviar correos, por lo que, para que nos puedan enviar mensajes, haremos uso de un grupo de Telegram.

Chat

Durante todo el semestre estaremos disponibles por chat en Telegram, responderemos a lo largo del día según la disponibilidad de cada miembro del equipo. Se solicita utilizar este medio en lugar del correo electrónico, pues es fácil que los correos se pierdan o queden rezagados y no podemos garantizar que sean atendidos a tiempo.

Nota: Si, la tabla de porcentajes suma 110% pero ojo, no se confíen, pues quienes lo han hecho tienden a reprobar. El objetivo es que ustedes intenten sacarse 110, para que, si cometen algún error mientras aprenden o les ocurre algún imprevisto eventual, éste no sea catastrófico para su calificación y al final obtengan resultados satisfactorios.

No se otorgan NPs a menos que se justifique la causa para abandonar el curso, estima bien tus tiempos para no sobrecargarte con material.

Temario

1. Introducción
   1. Tipos de datos abstractos (TDA) y Estructuras de datos
   2. Modelos de memoria
   3. Elementos de complejidad algorítmica
      1. Análisis asintótico, notación O()
      2. Recurrencias
   4. Elementos de corrección de algoritmos
      1. Pruebas basadas en invariantes
   5. Recursión
      1. Estrategia divide y vencerás, solución de problemas mediante recursión
      2. Búsqueda con retroceso mínimo (backtrack)
2. Arreglos
   1. Polinomios de direccionamiento
   2. Vectores de Iliffe
   3. Arreglos empacados
3. Colecciones
4. Estructuras lineales
   1. Pilas
   2. Colas
   3. Bicolas
   4. Listas
      1. Doblemente ligadas
      2. Circulares
5. Árboles
   1. Definiciones
   2. Árboles binarios
   3. Árboles binarios de búsqueda
   4. Árboles de búsqueda balanceados
      1. AVL
      2. Rojinegros
6. Funciones y tablas de dispersión (hash)
7. Algoritmos de ordenamiento
   1. Métodos básados en comparaciones
      1. Burbuja
      2. Selección
      3. Inserción
      4. Quicksort
      5. Mergesort
      6. Montículos (heap) y heapsort
   2. Métodos especializados
      1. Ordenamiento de Shell
      2. Cubetas (Bucketsort o Comparison Sort)
      3. Radixsort
   3. Búsqueda binaria
8. Gráficas
   1. Representaciones
      1. Listas de adyacencias (o diccionarios)
      2. Matriz de adyacencias
   2. Recorridos en amplitud y profundidad
   3. Rutas más cortas: Dijkstra y Floyd
   4. Árbol generador de peso mínimo: Prim y Kruskal

Aula virtual: https://quetzalcoatl.fciencias.unam.mx/moodle/course/view.php?id=38
Actualmente permite el acceso con cuenta de invitado, pero el acceso completo se enviará por correo electrónico a las personas inscritas el primer día de clases.