1151042 Algoritmos y Estructuras de Datos
Trimestre 2017 Primavera
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 8 de mayo a miércoles 19 de julio de 2017.
Grupo: CSI01 (martes y
jueves de 09:15 a 11:30).
Asesorías: lunes, miércoles
y viernes de 10:00 a 11:30 en la oficina H-264.
Salón: E-309.
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.
Evaluación
Habrá al menos diez exámenes semanales y al menos ocho tareas. Cada
examen valdrá 6 puntos y cada tarea valdrá 5 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 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.
09/05:
Inicio del curso. Presentación del curso y de las reglas de
evaluación. Tipos de datos abstractos [P101, SW1.1 y SW1.2]. Conjuntos
en mapas de bits.
11/05:
Memoria,
apuntadores y arreglos [P102, KR5.1-4]. Tarea 1 (para el 18/05).
16/05: Aritmética
de direcciones y cadenas [KR5.5-9].
18/05: Estructuras,
apuntadores y memoria dinámica [P106, KR6.1-7]. Tarea 2 (para el 25/05).
23/05:
Conjuntos
en arreglos desordenados y ordenados. Búsqueda lineal y
binaria.
25/05:
Recursividad
y eficiencia [SW1.4]. Tarea 3 (para el 03/06).
30/05: Ordenamiento interno: burbuja,
cubeta y mezcla
[SW2.2].
01/06: Ordenamiento interno: quicksort
[SW2.3] y
montículo
[SW2.4]. Tarea 4 (para el 09/06).
06/06:
Pilas y colas de capacidad acotada [P103, SW1.3].
08/06:
Pilas de capacidad arbitraria [P103, SW1.3]. Tarea 5 (para el 15/06).
13/06: Listas ligadas: pilas y colas
[P103, SW3.1].
15/06: Listas ligadas: ordenadas [P103, SW3.1] y
dobles [P105, SW3.1]. Tarea 6 (para el 29/06).
20/06:
Árboles binarios de búsqueda: búsqueda, inserción y recorridos [P110, SW3.2].
22/06:
Árboles binarios de búsqueda: borrado [P110, SW3.2].
27/06: Árboles balanceados: 2-3-4 [SW3.3].
29/06: Árboles
balanceados: rojinegros [SW3.3]. Tarea 7 (para el 06/07).
04/07:
Gráficas [SW4.1]
y digráficas [SW4.2].
06/07:
Recorridos de gráficas y digráficas [SW4.1 y SW4.2]. Tarea 8 (para el 13/07).
11/07: Caminos más cortos: Algoritmo
de Dijkstra [SW4.4].
Algoritmo de Warshall [SW4.4].
13/07: Árboles abarcadores: Algoritmo
de Prim [SW4.3].
Unión y búsqueda [SW1.5]:
Algoritmo de Kruskal. Tarea 9 (para el
20/07).
18/07:
Componentes conexas. Componentes biconexas. Orden topológico. Fin
del curso.
20/07:
Día de la evaluación global.
21/07:
Estas son las calificaciones finales.
Planeo entregar el acta este día.
24-28/07: Esta
semana estaré en un evento.
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.