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

Segundo Semestre, Estructuras de Datos

Requisitos

El curso de Estructuras de Datos se imparte después de Introducción a Ciencias de la Computación: por lo tanto se espera que los estudiantes manejen los preceptos básicos de programar. Qué es un algoritmo, representación interna (complemento a 2, números de punto flotante, UTF-8), estructuras de control, recursión, la pila (stack) de ejecución, el espacio de memoria (heap), paso de parámetros por valor y por referencia, alcance de variables, etcétera, serán conceptos que el curso no cubre y que da por hecho que los estudiantes manejan.

En particular se supondrá que los alumnos están familiarizados con el lenguaje de programación Java, por lo que la sintaxis del lenguaje y funcionamento del compilador se considerarán también vistos. Las bases de la Orientación a Objetos (qué son clases, objetos, métodos, propiedades, herencia, polimorfismo, despacho dinámico, excepciones) también se espera que los alumnos las manejen, al menos de manera básica.

El manejar genéricos, iteradores y lambdas es conveniente, pero no necesario; se cubrirán estos temas con cierto detalle en el curso.

Por último y aunque no fundamental, será de ayuda para los alumnos que al menos conozcan las definiciones básicas o haya oído hablar de conceptos como son las máquinas de Turing, el cálculo-λ, el principio de sustitución de Liskov y el problema del paro.

Temario

1. Introducción
2. Genéricos
   1. Tipos genéricos
   2. Borradura de tipos
   3. Acotamiento de tipos
   4. Empacamiento y desempacamiento
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
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
    3. 1. Acciones para vértices de árboles binarios
    4. 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
    3. 1. Algoritmo para agregrar
       2. Algoritmo para eliminar
16. Árboles AVL
    1. Definición de árboles AVL
    2. Algoritmos de los árboles AVL
    3. 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
    5. 1. BFS en gráficas
       2. DFS en gráficas
    6. Algoritmos para gráficas
    7. 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
    3. 1. Acomodando hacia arriba
       2. Acomodando hacia abajo
    4. Implementación en Java
    5. Algoritmos para montículos mínimos
    6. Algoritmo HeapSort
    7. 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:

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. Si el profesor detecta que un proyecto fue bajado de internet, la calificación será cero.

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.