1151042 Algoritmos y Estructuras de Datos
Trimestre 2015 Primavera
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 4 de mayo a viernes 17 de julio de 2015.
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: E309.
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.
- Algoritmos de procesamiento de cadenas.
Evaluación
Habrá cinco exámenes parciales y al menos diez tareas. Cada examen
valdrá 8 puntos y cada tarea valdrá 6 puntos. No habrá examen
global. 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 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.
04/05:
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].
Tarea 1 (para el 07/05).
06/05: Memoria, apuntadores y arreglos
[KR5.1-4].
08/05:
Aritmética de direcciones y cadenas
[KR5.5-9].
11/05: Estructuras,
apuntadores y memoria dinámica [KR6.1-7]. Tarea
2 (para el 18/05).
13/05: Primer
examen parcial.
15/05: Día
feriado.
18/05:
Conjuntos en arreglos desordenados y
ordenados. Búsqueda lineal y binaria.
20/05:
Recursividad y eficiencia [SW1.4].
22/05:
Ordenamiento interno [SW2.1]: mezcla [SW2.2]. Tarea 3 (para el 29/05).
25/05: Ordenamiento interno: quicksort [SW2.3].
27/05: Ordenamiento interno: montículo [SW2.4].
29/05: Pilas y colas estáticas [SW1.3]. Tarea 4 (para el 05/06).
01/06:
Pilas y colas dinámicas [SW1.3].
03/06:
Segundo examen parcial.
05/06:
Listas ligadas [SW3.1].
08/06: Listas ligadas [SW3.1]. Tarea 5 (para el 17/06).
10/06: Árboles binarios de búsqueda [SW3.2].
12/06: Árboles binarios de búsqueda [SW3.2].
15/06:
Árboles balanceados [SW3.3].
Notas de otro curso.
17/06:
Árboles balanceados [SW3.3]. Tarea 6 (para el 22/06).
19/06:
Tercer examen parcial.
22/06: Gráficas [SW4.1] y
Digráficas [SW4.2].
Tarea 7 (para el 29/06).
24/06: Recorridos de gráficas y
digráficas [SW4.1
y SW4.2].
26/06: Recorridos de gráficas y
digráficas [SW4.1
y SW4.2].
29/06:
Caminos más cortos: Algoritmo de Dijkstra [SW4.4]. Tarea 8 (para el 06/07).
01/07:
Caminos más cortos: Algoritmo de Warshall [SW4.4].
03/07:
Árboles abarcadores: Algoritmo de Prim [SW4.3].
06/07: Unión y búsqueda [SW1.5]: Algoritmo
de Kruskal.
08/07: Cuarto
examen parcial. Calificaciones.
10/07: Búsqueda interna [SW3.1]:
tablas de dispersión [SW3.4].
13/07:
Ordenamiento de cadenas [SW5.1].
15/07:
Búsqueda de subcadenas [SW5.3].
17/07:
Búsqueda de subcadenas [SW5.3].
20/07: Quinto
examen parcial. 16:00 a 17:30 en el E309.
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.