Encabezado Facultad de Ciencias
Presentación

Ciencias de la Computación (plan 2013) 2025-1

Segundo Semestre, Estructuras de Datos

Grupo 7054, 50 lugares.
Profesor Ulises Rodríguez Domínguez ma ju 16 a 17:30
Ayudante Jesús Enrique Robles López lu mi 15 a 16
Ayud. Lab. Julio Vázquez Álvarez lu mi 16 a 18 Laboratorio de Ciencias de la Computación 2

 

Estructuras de Datos

Semestre 25-01

Profesor: Ulises Rodríguez Domínguez Horario del curso: Ma Jue 16:00 – 17:30 hrs.
( ulises.rodriguez.dominguez@ciencias.unam.mx )
Ayudante: Jesús Enrique Robles López Horario de ayudantías: Lu Mi 15:00 – 16:00 hrs.
( jesus.robleslopez@ciencias.unam.mx )
Ayudante Lab.: Julio Vázquez Álvarez Horario de Lab.: Lu Mi 16:00 – 18:00 hrs.
( julio.vazquez@ciencias.unam.mx )

Página del curso:

  • Se enviará un enlance a los(as) alumnos(as) inscritos(as).

Horas de oficina: agendar en caso requerido.

Objetivo: Entender el rol de las estructuras de datos más comunes en la implementación de soluciones computacionales adecuadas, y adquirir la capacidad para manipularlas con el fin de poder cumplir con los requerimientos de cómputo en distintos problemas. Para ello los(as) alumnos(as) adquirirán experiencia: construyendo programas con correctez verificable, haciendo un uso adecuado de los recursos computacionales en tiempo y memoria y aplicando algunos principios de programación orientada a objetos para escribir software de calidad. Con ello los(as) alumnos(as) serán capaces de resolver mediante programación problemas más complicados o problemas en contextos más realistas, en comparación con las habilidades adquiridas en cursos previos.

Temario:

  1. Tipos de datos abstractos y conceptos de programación orientada a objetos (POO)

    • Tipos de datos abstractos (TDAs) y estructuras de datos

    • POO: clase, objeto, encapsulación, acoplamiento y cohesión.

  2. Elementos de complejidad algorítmica

    • Análisis asintótico, notación O( ).

    • Recurrencias.

  3. Elementos de corrección de algoritmos

    • Pruebas basadas en invariantes.

    • Pruebas basadas en un TDA.

  4. Arreglos

    • Polinomios de direccionamiento, vectores de Iliffe.

    • Arreglos empacados.

  5. Recursión

    • Estrategia divide y vencerás, solución de problemas mediante recursión.

    • Búsqueda con retroceso mínimo (backtracking).

  6. Listas

    • TDA lista, operaciones y complejidad.

    • Variantes de una lista.

  7. Pilas y colas

    • TDA pila, operaciones y complejidad.

    • TDA cola, operaciones y complejidad.

  8. Árboles

    1. Conceptos y TDA

    2. Árboles binarios

    3. Árboles de búsqueda binarios

    4. Árboles de búsqueda balanceados

      1. Árboles AVL.

      2. Árboles rojinegros.

  9. Funciones de dispersión (hash)

    • Motivación, diseño y manejo.

  10. Heaps

    • Conceptos, TDA, operaciones y complejidad.

  11. Algoritmos de ordenamiento

    • Inserción, selección, burbuja y análisis de complejidad.

    • Shellsort, Heapsort, Quicksort, Mergesort y análisis de complejidad.

  12. Algoritmos en grafos

    • Representación y complejidad en el espacio.

    • Recorridos en amplitud (BFS) y a profundidad (DFS).

    • Algoritmos de Dijkstra y Floyd para las rutas más cortas.

Bibliografía:

  • Carrano, Frank M. y Janet J. Prichard, Data Abstraction and Problem Solving with Java, 2a ed., Addison Wesley, 2005.

  • Goldman Sally y Kenneth J. Goldman, A Practical Guide to Data Structures and Algorithms Using Java, Chapman & Hall - CRC Press, 2007.

  • Peláez, Canek, Estructuras de Datos con Java Moderno: Comportamiento + Objetos = Programas. Las Prensas de Ciencias, Facultad de Ciencias, UNAM, México, 2018.

  • Skiena, Steven S., The Algorithm Design Manual, 2a ed. Springer, 2008.

  • Brass, Peter, Advanced Data Structures, Cambridge University Press, 2008.

  • Preiss, Bruno R., Data Structures and Algorithms with Object-Oriented Design Patterns in Java, Wiley, 1999.

Evaluación:

Mini-cuestionarios 10%
Tareas 20%
Prácticas 30%
Proyecto final 15%
Exámenes parciales 25%

Políticas del curso:

  • Se utlizará Google Classroom como la plataforma para subir las sesiones del curso así como para entregar las tareas, prácticas y proyectos.

  • A menos que se indique lo contrario, todas las tareas y prácticas se llevarán a cabo de manera individual. Sin embargo es válido discutir acerca de las mismas con otros compañeros(as) sin que ello implique pedir o copiar respuestas.

  • Se considerará Java como lenguaje de programación para la primera parte del curso. Para la segunda parte del curso se podrá seguir utilizando Java pero se fomentará el uso de Python.

Deshonestidad académica: Si se detectan copias entre alumnos(as) la calificación se dividirá entre el número de alumnos(as) involucrados(as). Si se detectan copias de recursos en línea o elaboración de trabajos por parte de gente externa, la calificación del trabajo correspondiente será de cero.

 


Hecho en México, todos los derechos reservados 2011-2016. Esta página puede ser reproducida con fines no lucrativos, siempre y cuando no se mutile, se cite la fuente completa y su dirección electrónica. De otra forma requiere permiso previo por escrito de la Institución.
Sitio web administrado por la Coordinación de los Servicios de Cómputo de la Facultad de Ciencias. ¿Dudas?, ¿comentarios?. Escribenos. Aviso de privacidad.