1151042 Algoritmos y Estructuras de Datos
Trimestre 2014 Otoño
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 8 de septiembre a martes 9 de diciembre
de 2014.
Grupo: CSI81 (lunes,
miércoles y viernes de 16:00 a 17:30).
Asesorías: lunes, miércoles
y viernes de 15:00 a 16:00 en la oficina H-264.
Salón: G208.
Cupo: 50 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.
- Algoritmos de procesamiento de cadenas.
Evaluación
Habrá al menos diez exámenes semanales y al menos diez tareas. Cada
examen valdrá 6 puntos y cada tarea valdrá 4 puntos. No habrá examen
global. Se requiere obtener
- al menos 30 puntos en los exámenes, 20 puntos en las tareas y
un total de al menos 60 puntos para acreditar con S,
- al menos 35 puntos en los exámenes, 25 puntos en las tareas y
un total de al menos 73 puntos para acreditar con B y
- al menos 40 puntos en los exámenes, 30 puntos en las tareas y
un total de al menos 87 puntos para acreditar con MB.
Las tareas se deberán entregar por correo electrónico a la cuenta aed en callix.azc.uam.mx y deberán estar escritas en C. Su
cuenta está en la misma máquina, a la que se pueden conectar con ssh. 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 del Sedgewick y
Wayne [SW] y del Kernighan y Ritchie [KR] a la derecha de cada tema.
Guía para usar su cuenta de callix.
08/09:
Inicio del curso. Presentación del curso y de las reglas de
evaluación. Tipos de datos concretos y abstractos [SW1.1 y SW1.2].
10/09:
Memoria y apuntadores [KR5.1-2].
12/09:
Arreglos y apuntadores [KR5.3-5]. Tarea 1
(para el 19/09).
15/09: Día
feriado.
17/09: Estructuras y apuntadores
[KR6.1-4, 6.7].
19/09: Memoria dinámica [KR6.5]. Tarea 2 (para el 26/09).
22/09:
Recursión lineal y binaria.
24/09:
Estaré en un congreso.
Hoy hubo examen.
26/09:
Eficiencia de algoritmos iterativos y recursivos [SW1.4]. Tarea 3 (para el 03/10).
29/09: Pilas [SW1.3].
01/10: Colas [SW1.3].
03/10: Listas ligadas [SW1.3]. Tarea 4 (para el 10/10).
06/10:
Aplicaciones de listas ligadas [SW1.3 y SW3.1].
08/10:
Aplicaciones de listas ligadas [SW1.3 y SW3.1].
10/10:
Árboles binarios de búsqueda [SW3.2]. Tarea 5 (para el 17/10).
13/10: Hoy hubo examen.
15/10: No hubo
clase por paro.
17/10: Árboles binarios de
búsqueda [SW3.2].
Tarea 6 (para el 24/10).
20/10:
Árboles binarios de búsqueda [SW3.2].
22/10:
No hubo clase por paro.
24/10:
Árboles balanceados [SW3.3].
Notas de otro curso.
27/10: Gráficas [SW4.1].
Estaré en un congreso.
29/10: Digráficas [SW4.2].
Estaré en un congreso.
31/10: Recorridos de gráficas y
digráficas [SW4.1
y SW4.2].
Tarea 7 (para el 07/11).
03/11:
Árboles abarcadores: Algoritmo de Prim [SW1.5 y SW4.3].
05/11:
No hubo clase por paro.
07/11:
No hubo clase por paro.
10/11: No hubo
clase por paro.
12/11: Caminos más cortos: Algoritmo
de Dijkstra [SW4.4].
14/11: Unión y búsqueda: Algoritmo de
Kruskal. Tarea 8 (para el 21/11).
17/11:
Ordenamiento interno: montículo [SW2.4].
19/11:
Ordenamiento interno: mezcla [SW2.2].
21/11:
Ordenamiento interno: quicksort [SW2.3]. Tarea 9 (para el 28/11).
24/11: Estaré en un congreso.
26/11: Estaré en un congreso.
28/11: Estaré en un congreso.
01/12: No hubo
clase por paro.
03/12: Ordenamiento de cadenas [SW5.1]. Tarea
10 (para el 08/12).
05/12: Búsqueda de subcadenas [SW5.3].
08/12: Fin del curso. Búsqueda
interna [SW3.1]:
tablas de dispersión [SW3.4].
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.
- Sedgewick.
Algoritmos en C++. Pearson.
- Sedgewick y Wayne. Algorithms.
Pearson.