Encabezado Facultad de Ciencias
Presentación

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

Segundo Semestre, Estructuras de Datos

Grupo 7024, 45 lugares. 45 alumnos.
Profesor Canek Peláez Valdés lu mi 13 a 14:30 O220
Ayudante Víctor Zamora Gutiérrez ma ju 13 a 14 O220
Ayud. Lab. Luis Soto Martínez ma ju 10 a 12 Laboratorio de Ciencias de la Computación 1
 

Temario

  1. Introducción
  2. Genéricos
    1. Tipos genéricos
    2. Borradura de tipos
    3. Acotamiento de tipos
    4. Empacamiento y desempacamiento
    5. Los genéricos en este libro
  3. Iteradores
    1. El operador for-each
  4. Colecciones
  5. Listas
    1. Definición de listas
    2. Algoritmos para listas
    3. Iteradores para listas
  6. Complejidad computacional
    1. La notación de O grandota
    2. Complejidades en tiempo y en espacio
  7. Arreglos
    1. El polinomio de redireccionamiento
    2. Arreglos y genéricos
  8. Pilas y colas
    1. Algoritmos de la clase abstracta
    2. Algoritmos para pilas
    3. Algoritmos para colas
    4. Pilas y colas en el resto del libro
  9. Lambdas
    1. Lambdas y funciones de primera clase
    2. Clases internas anónimas
    3. Lambdas en Java con interfaces funcionales
  10. Ordenamientos
    1. Ordenamientos en arreglos
      1. Algoritmo SelectionSort
      2. Algoritmo QuickSort
      3. Manteniendo arreglos ordenados
    2. Ordenamientos en listas
      1. Algoritmo MergeSort
      2. Manteniendo listas ordenadas
    3. La razón para ordenar colecciones
  11. Búsquedas
    1. Búsquedas en arreglos
    2. Búsquedas en listas
  12. Árboles binarios
    1. Definición de árboles binarios
    2. Propiedades de árboles binarios
    3. Implementación en Java
    4. Algoritmos para árboles binarios
    5. Aprovechando referencias no utilizadas
  13. Árboles binarios completos
    1. Definición de árboles binarios completos
    2. Recorriendo árboles por amplitud
      1. Acciones para vértices de árboles binarios
    3. Algoritmos para árboles binarios completos
  14. Árboles binarios ordenados
    1. Definición de árboles binarios ordenados
    2. Recorriendo árboles por profundidad
      1. DFS pre-order
      2. DFS post-order
      3. DFS in-order
    3. Algoritmos para árboles binarios ordenados
    4. Complejidades en tiempo y en espacio
  15. Árboles rojinegros
    1. Definición de árboles rojinegros
    2. Algoritmos de los árboles rojinegros
      1. Algoritmo para agregrar
      2. Algoritmo para eliminar
  16. Árboles AVL
    1. Definición de árboles AVL
    2. Algoritmos de los árboles AVL
      1. Algoritmo de rebalanceo
  17. Gráficas
    1. Definición de gráficas
    2. Propiedades de gráficas
    3. Implementación en Java
    4. Recorridos en gráficas
      1. BFS en gráficas
      2. DFS en gráficas
    5. Algoritmos para gráficas
    6. Implementaciones alternativas de gráficas
  18. Montículos mínimos
    1. Definición de montículos mínimos
    2. Acomodando hacia arriba y hacia abajo
      1. Acomodando hacia arriba
      2. Acomodando hacia abajo
    3. Implementación en Java
    4. Algoritmos para montículos mínimos
    5. Algoritmo HeapSort
    6. Montículos de arreglos
  19. Algoritmo de Dijkstra
    1. Definición de trayectoria de peso mínimo
    2. Implementación en Java
    3. Algoritmos para gráficas con pesos en las aristas
    4. Algoritmo de trayectoria mínima
    5. Algoritmo de Dijkstra
    6. Reconstruyendo trayectorias
    7. Pesos con matrices de adyacencias
  20. Funciones de dispersión
    1. Colisiones en funciones de dispersión
    2. Implementación en Java
      1. Cascando huevos
    3. Función de dispersión XOR
    4. Función de dispersión Bob Jenkins
    5. Función de dispersión de Daniel J. Bernstein
    6. Funciones de dispersión para diccionarios
  21. Diccionarios
    1. El arreglo del diccionario
    2. Implementación en Java
    3. Algoritmos para diccionarios
    4. Complejidades en tiempo y en espacio
    5. Implementaciones alternas de diccionarios
  22. Conjuntos
    1. Implementación en Java
    2. Algoritmos para conjuntos
    3. Otros usos de conjuntos
  23. Mejorando gráficas
    1. Modificaciones al código
  24. Conclusiones

Evaluación

El curso se evaluará de la siguiente manera:

Exámenes parciales: 30%
Exámenes semanales: 20%
Proyectos: 30%
Prácticas: 20%

Evaluación teórica

Habrá tres exámenes parciales, cada uno de los cuales cubrirá aproximadamente la tercera parte del material visto en clase. En ningún examen parcial se les solicitará escribir código (a menos que se ofrezca como punto extra del examen), pero sí que lean y analicen código.

Los exámenes semanales son exámenes cortos (diez minutos) que se llevarán a cabo los miércoles al término de la clase, y donde se harán preguntas referentes a los conceptos vistos durante la semana. Una vez que todos los alumnos hayan entregado el examen, será resuelto ahí mismo por el profesor. La calificación más baja de todos los exámenes semanales no será contabilizada en el promedio de los mismos.

No hay exámenes de reposición ni examen final.

Evaluación práctica

Habrá tres proyectos, para realizarse de forma individual, y consistirán en implementar la solución a un problema específico, utilizando los conceptos y herramientas vistos durante el curso.

Las prácticas consistirán en implementar, en su totalidad o en parte, las clases y métodos correspondientes que se les dejen. Las prácticas también deberán realizarse de forma individual.

La calificación de las prácticas depende en su mayoría de las pruebas unitarias incluidas en cada una de ellas. Si la práctica que el alumno entregue pasa todas las pruebas unitarias, y además los algoritmos implementados cumplen los requerimientos de complejidad en tiempo y espacio la calificación será, en principio, 10. Si un estudiante consigue escribir código erróneo que pase todas las pruebas unitarias de una práctica, y le avisa al profesor antes de la fecha de entrega, el estudiante obtendrá un punto extra en esa práctica. Además de pasar las pruebas unitarias, los algoritmos implementados deben satisfacer las complejidades en tiempo y en espacio vistos en clase.

Para alcanzar al menos el 5 de calificación, la práctica debe compilar correctamente y sin advertencias. No está permitido bajo ninguna circunstancia utilizar clases del paquete java.util, ni agregar variables de clase (ni públicas ni privadas) a ninguna clase vista durante el curso. Tampoco está permitido agregar métodos públicos; pero métodos privados están permitidos, y de hecho se les sugiere que los utilicen.

Si el ayudante o profesor detectan que han copiado en alguna práctica, la calificación de la misma se dividirá entre el número de estudiantes que hayan copiado.

La fecha límite de entrega de prácticas y proyectos es inamovible.


Renuncias y NPs

Para alumnos inscritos, la única forma en que se les pondrá NP en actas es si solicitan renunciar al curso mediante un correo electrónico dirigido al profesor, a más tardar en la octava semana de clases. Si no mandan un correo electrónico a más tardar en la octava semana, un alumno inscrito tendrá en actas la calificación que obtenga en el curso, no importa cuál sea ésta, y no importa si deja o no de asistir a clases, entregar prácticas y proyectos, y/o realizar exámenes.

No se guardan calificaciones para próximos semestres ni para exámenes extraordinarios. Mucho menos se “pasan” o “reciben” calificaciones a o de otros profesores.

 


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.