1151042 Algoritmos y Estructuras de Datos
Trimestre 2018 Invierno
Instructor: Dr. Francisco Javier Zaragoza Martínez.
Inicio y fin del curso:
lunes 15 de enero a miércoles 4 de abril de 2018.
Grupo: CSI03 (lunes,
miércoles y viernes de 11:30 a 13:00).
Asesorías: lunes, miércoles
y viernes de 10:00 a 11:30 en la oficina H-264.
Salón: Babbage.
Cupo: 45 alumnos.
Contenido
Se cubrirá el contenido
oficial del curso (el cual se detalla abajo). Es posible que
el temario se cubra en un orden distinto al allí mencionado.
- Tipos de datos abstractos y estructuras dinámicas.
- Recursividad y eficiencia.
- Estructuras para listas.
- Estructuras para árboles.
- Estructuras para gráficas.
- Algoritmos de búsqueda interna.
- Algoritmos de ordenamiento interno.
Evaluación
Habrá cuatro exámenes parciales y diez tareas. Cada examen valdrá 10
puntos y cada tarea valdrá 6 puntos. No habrá examen terminal. Se
requiere obtener
- al menos 20 puntos en los exámenes, 30 puntos en las tareas y
un total de al menos 60 puntos para acreditar con S,
- al menos 25 puntos en los exámenes, 35 puntos en las tareas y
un total de al menos 73 puntos para acreditar con B y
- al menos 30 puntos en los exámenes, 40 puntos en las tareas y
un total de al menos 87 puntos para acreditar con MB.
Las tareas se deberán estar
escritas en C. Recuerden que, de acuerdo al Reglamento de
Alumnos de la UAM, es falta de los alumnos en contra de la
Institución el suplantar o permitir ser suplantado en la realización
de actividades académicas (Artículo 9) y se impondrá desde
amonestación escrita hasta suspensión por dos trimestres (Artículo
13).
Calendario
El calendario de clases, de entrega de tareas y de evaluaciones que
muestro abajo es tentativo e irá apareciendo paulatinamente. He
anotado los capítulos y secciones correspondientes de Parlante [P],
Sedgewick y Wayne [SW] y Kernighan y Ritchie [KR] a la derecha de
cada tema.
15/01:
Inicio del curso. Presentación del
curso y de las reglas de evaluación. Tipos de datos concretos y
abstractos [P101,
SW1.1 y SW1.2]. Tarea 1 (para el 22/01).
17/01:
Conjuntos en mapas de bits.
19/01:
Memoria, apuntadores y arreglos
[P102, KR5.1-4].
22/01: Aritmética
de direcciones y cadenas [KR5.5-9]. Tarea
2 (para el 29/01).
24/01: Estructuras, apuntadores y
memoria dinámica [P106, KR6.1-7].
26/01: Conjuntos en arreglos desordenados.
Búsqueda lineal.
29/01:
Conjuntos en arreglos ordenados.
Tarea
3 (para el 08/02).
31/01:
Recursión. Búsqueda binaria.
Eficiencia [SW1.4].
02/02:
Primer examen parcial.
05/02: Día
feriado.
07/02: Ordenamiento interno: burbuja
y mezcla [SW2.2]. Tarea
4 (para el 14/02).
09/02: Ordenamiento interno: quicksort [SW2.3] y montículo [SW2.4].
12/02:
Pilas de capacidad acotada [SW1.3].
14/02:
Pilas de capacidad arbitraria [P103, SW1.3]. Tarea
5 (para el 21/02).
16/02:
Colas y colas dobles [SW1.3].
19/02: Listas ligadas: pilas [P103, SW3.1].
21/02: Listas ligadas: ordenadas [P103, SW3.1]. Tarea
6 (para el 28/02).
23/02: Listas ligadas: colas dobles [P105, SW3.1].
26/02:
Segundo examen parcial.
28/02:
Árboles binarios de búsqueda: búsqueda, inserción y recorridos [P110, SW3.2]. Tarea
7 (para el 09/03).
02/03:
Árboles binarios de búsqueda: borrado [P110, SW3.2].
05/03: Árboles balanceados: 2-3-4 [SW3.3].
Notas de otro curso.
07/03: Árboles balanceados:
rojinegros [SW3.3].
Tarea 8 (para el 14/03).
09/03: Gráficas [SW4.1] y
digráficas [SW4.2].
12/03:
Recorridos de gráficas y digráficas [SW4.1 y SW4.2].
14/03:
Recorridos de gráficas y digráficas [SW4.1 y SW4.2]. Componentes conexas.
Componentes
biconexas.
16/03:
No hubo clase por paro. Caminos más
cortos: Algoritmo de Warshall [SW4.4]. Orden topológico.
19/03: Tercer
examen parcial.
21/03: Día
feriado.
23/03: Caminos más cortos: Algoritmo
de Dijkstra [SW4.4]. Tarea
9 (para el 02/04).
26/03:
Árboles abarcadores: Algoritmo de Prim [SW4.3].
28/03:
Unión y búsqueda [SW1.5]:
Algoritmo de Kruskal. Tarea
10 (para el 06/04).
30/03:
Día feriado.
02/04: No habrá clase.
04/04: Cuarto examen parcial.
Fin del curso.
11/04: Estas son las calificaciones finales. Los programas que aparecieron
como copias recibieron 0 puntos.
13/04: Entregaré el acta antes
de la 1pm.
Bibliografía
- Aho, Ullman y Hopcroft. Estructuras de datos y algoritmos.
Pearson.
- Harvey. Computer Science Logo Style. Volumes 1,
2,
3.
MIT Press.
- Kernighan y Ritchie. El lenguaje de programación C. Pearson.
- Knuth.
The
Art of Computer Programming: Vol. 3 Sorting and Searching.
Addison Wesley.
- Llana, et al. Ejercicios
de programación creativos y recreativos en C++. Prentice
Hall.
- Parlante. Stanford
CS Education Library.
- Sedgewick.
Algoritmos en C++. Pearson.
- Sedgewick y Wayne. Algorithms.
Pearson.