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

Segundo Semestre, Estructuras de Datos

Contacto

Profesor: M. en C. Carlos Zerón Martínez zeronmc@gmail.com

Ayudante: Itzel Azucena Delgado Díaz itzeldelgado314@ciencias.unam.mx

Laboratorista: José Antonio Vilchis Salazar grand_paladin@ciencias.unam.mx

Modalidad del curso

Objetivos generales

Proporcionar habilidades y conocimientos con respecto a:

• La abstracción de datos para resolver problemas.
• El panorama de las estructuras de datos más usuales, características, operaciones soportadas y maneras de instrumentarlas en un lenguaje de programación orientado a objetos en particular (Java).
• Las técnicas de análisis de eficiencia en estructuras de datos y algoritmos que las utilizan.
• Aplicaciones de estructuras de datos en el contexto del desarrollo de sistemas de software.

Contenido

1. Fundamentos
   • Diseño Orientado a objetos: Repaso y conceptos complementarios
   • Diseño Orientado a objetos: Metas y principios
   • Tipo de dato abstracto y estructura de datos
   • Introducción al análisis de algoritmos: eficiencia teórica y experimental
2. Recursión
   • Algoritmos recursivos
   • Eficiencia en la recursión
3. Listas
   • Implementaciones basadas en arreglos
   • Listas con referencia simple (listas ligadas)
   • Listas doblemente ligadas
   • Aplicaciones
4. Pilas y Colas
   • Implementaciones basadas en arreglos
   • Implementaciones basadas en listas ligadas
   • Aplicaciones
5. Árboles
   • Árboles generales: definiciones y algoritmos fundamentales
   • Árboles binarios
   • Árboles binarios de búsqueda
   • Arboles binarios completos. Heaps
   • Aplicaciones
6. Colas de prioridades
   • Implementaciones basadas en listas
   • Implementación basada en un heap
   • Aplicaciones
7. Mapas
   • Implementación con tablas de dispersión
   • Mapas ordenados
   • Aplicaciones
   • Conjuntos, multiconjuntos y multimapas (diccionarios)
8. Algoritmos de Ordenamiento
   • Ordenamiento por Selección
   • Ordenamiento por Inserción
   • Ordenamiento por Mezcla
   • Ordenamiento Rápido
9. Gráficas
   • Gráficas dirigidas y no dirigidas. Repaso y conceptos complementarios.
   • Implementación basada en matriz de adyacencias
   • Implementación basada en lista de adyacencias
   • Algoritmos fundamentales
   • Aplicaciones

Evaluación

• Tareas 20%. Escribir fragmentos de código, ejecutar algoritmos y esquematizar operaciones de las estructuras de datos.
• Exámenes 20%. Reconocer conceptos, analizar eficiencia y ejecutar algoritmos.
• Prácticas 40%. Implementar estructuras de datos y aplicaciones sencillas.
• Proyecto Final 20%. Implementar una aplicación que involucre varias estructuras de datos.

Lineamientos sobre la evaluación

• Todas las entregas serán de forma individual.
• No existe examen final. Sólo se puede presentar reposición de una práctica y un examen al final del ciclo escolar.
• Las prácticas y tareas se entregarán por Classroom en la fecha estipulada; se aplicará una penalización de dos puntos por cada dia natural de retraso.
• Las tareas deberán entregarse en .pdf, generado con una aplicación de su preferencia o como resultado de escanear papeles escritos con tinta.
• El proyecto final es obligatorio para tener derecho a calificación y tiene como fecha única de entrega de al menos dos semanas después de terminar el ciclo escolar.
• Las entregas pueden cambiar de fecha por circunstancias de la Facultad ajenas a nuestro control o por causas de fuerza mayor de los estudiantes, las cuales sean comprobables por algún documento.
• Derecho a NP si no se entrega nada, si se incumple el punto anterior, o bien, si el promedio final es mayor o igual a 5 y menor estricto que 6.