1151042 Algoritmos y Estructuras de Datos
Trimestre 2016 Invierno
Instructor: Dr. Francisco Javier Zaragoza Martínez.
Inicio y fin del curso:
lunes 18 de enero a miércoles 6 de abril de 2016.
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.
Evaluación
Habrá exámenes parciales y tareas semanales. Cada examen valdrá 4
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 de Parlante [P],
Sedgewick y Wayne [SW] y Kernighan y Ritchie [KR] a la derecha de
cada tema. Guía para usar su cuenta de
callix.
18/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].
20/01:
Conjuntos en mapas de bits. Tarea 1 (para el 27/01).
22/01:
Memoria, apuntadores y arreglos
[P102, KR5.1-4].
25/01: Aritmética
de direcciones y cadenas [KR5.5-9].
27/01: No hubo
clase por causas de fuerza mayor. Tarea
2 (para el 03/02).
29/01: Estructuras, apuntadores y
memoria dinámica [P106, KR6.1-7].
01/02:
Conjuntos en arreglos desordenados
y ordenados. Búsqueda lineal y binaria.
03/02:
Recursión. Eficiencia [SW1.4].
05/02:
Día feriado.
08/02: Inicia la primera fase del XIII Concurso de
programación de la UAM.
08/02: Ordenamiento interno: burbuja,
cubeta y mezcla [SW2.2]. Tarea 3 (para el 15/02).
10/02: Ordenamiento interno: quicksort [SW2.3].
12/02: Ordenamiento interno: montículo [SW2.4].
15/02:
Termina la primera fase del XIII Concurso de
programación de la UAM.
15/02:
Pilas de capacidad acotada [SW1.3]. Tarea 4 (para el 22/02).
17/02:
Pilas de capacidad arbitraria [P103, SW1.3].
19/02:
Colas y colas dobles [SW1.3].
22/02: Listas ligadas: pilas y
colas [P103, SW3.1].
24/02: Listas ligadas: ordenadas [P103, SW3.1].
26/02: Listas ligadas: dobles [P105, SW3.1].
29/02: Árboles
binarios de búsqueda: búsqueda, inserción y recorridos [P110, SW3.2]. Tarea 5 (para el 07/03).
02/03:
Árboles binarios de búsqueda: borrado [P110, SW3.2].
04/03:
Día feriado.
07/03: Árboles balanceados: 2-3-4 [SW3.3].
Notas de otro curso.
09/03: Árboles balanceados:
rojinegros [SW3.3].
Tarea 6 (para el 14/03).
11/03: Gráficas [SW4.1] y
digráficas [SW4.2].
14/03: Gráficas
[SW4.1] y
digráficas [SW4.2].
16/03:
Recorridos de gráficas y digráficas [SW4.1 y SW4.2]. Tarea 7 (para el 23/03).
18/03:
Recorridos de gráficas y digráficas [SW4.1 y SW4.2].
21/03: Día
feriado.
23/03: Recorridos de gráficas y
digráficas [SW4.1
y SW4.2].
25/03: Día
feriado.
28/03:
Caminos más cortos: Algoritmo de Dijkstra [SW4.4]. Tarea 8 (para el 04/04).
30/03:
Caminos más cortos: Algoritmo de Warshall [SW4.4].
01/04:
Árboles abarcadores: Algoritmo de Prim [SW4.3].
04/04: Unión y búsqueda [SW1.5]: Algoritmo
de Kruskal. Tarea 9 (para el 08/04).
06/04: Unión y búsqueda [SW1.5]: Algoritmo
de Kruskal. Fin del curso.
12/04: Ya entregué el acta, deben
poder ver su calificación el 13/04 en el sistema.
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.