1151042 Algoritmos y Estructuras de Datos
Trimestre 2015 Otoño
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
jueves 17 de septiembre a viernes 4 de diciembre de 2015.
Grupo: CSI81 (lunes,
miércoles y viernes de 14:30 a 16:00).
Asesorías: lunes, miércoles
y viernes de 16:00 a 17: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á exámenes 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 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.
14/09:
Día feriado.
16/09:
Día feriado.
18/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]. Tarea 1 (para el 25/09).
21/09: Memoria,
apuntadores y arreglos [KR5.1-4].
23/09: Aritmética
de direcciones y cadenas [KR5.5-9].
25/09: Estructuras, apuntadores y
memoria dinámica [KR6.1-7]. Tarea 2
(para el 02/10).
28/09:
Conjuntos en arreglos desordenados
y ordenados. Búsqueda lineal y binaria.
30/09:
Recursividad y eficiencia [SW1.4].
02/10:
Ordenamiento interno [SW2.1]: mezcla [SW2.2]. Tarea 3 (para el 09/10).
05/10: Ordenamiento interno: quicksort [SW2.3].
07/10: Ordenamiento interno: montículo [SW2.4].
09/10: Pilas y colas estáticas [SW1.3]. Tarea 4 (para el 19/10).
12/10:
Día feriado.
14/10:
No hubo clases por paro.
16/10:
Pilas y colas dinámicas [SW1.3]. Tarea 5 (para el 26/10).
19/10: Listas ligadas [SW3.1].
21/10: Listas ligadas [SW3.1].
23/10: Listas ligadas [SW3.1].
26/10:
Árboles binarios de búsqueda [SW3.2]. Tarea 6 (para el 04/11).
28/10:
Árboles binarios de búsqueda [SW3.2].
30/10:
Árboles binarios de búsqueda [SW3.2].
02/11: Día
feriado. Estaré en un evento.
04/11: Árboles balanceados [SW3.3].
Notas de otro curso.
06/11: Árboles balanceados [SW3.3].
09/11:
Gráficas [SW4.1]
y Digráficas [SW4.2].
11/11:
Recorridos de gráficas y digráficas [SW4.1 y SW4.2].
13/11:
Recorridos de gráficas y digráficas [SW4.1 y SW4.2].
16/11: Caminos más cortos: Algoritmo
de Dijkstra [SW4.4].
18/11: Árboles abarcadores: Algoritmo
de Prim [SW4.3].
Unión y búsqueda [SW1.5]:
Algoritmo de Kruskal.
20/11: Día
feriado.
23/11:
Estaré en un evento.
25/11:
Examen de reposición (cualquiera de los
exámenes anteriores).
27/11:
Caminos más cortos: Algoritmo de Warshall [SW4.4].
30/11: Ordenamiento de cadenas [SW5.1].
02/12: Búsqueda de subcadenas [SW5.3].
04/12: Búsqueda de subcadenas [SW5.3].
09/12: Daré una plática
a las 10am en el W002. Último examen (3pm).
10/12: Estas son las calificaciones del curso. Entregaré el
acta el lunes 14 de diciembre.
11/12: Aprovecho para invitarlos al
Concurso de programación de la UAM 2016 (liga al
concurso de 2015).
Bibliografía
- Aho, Ullman y Hopcroft. Estructuras de datos y algoritmos.
Pearson.
- Charras y Leqroc.
Handbook
of Exact String Matching Algorithms. Online.
King's College London.
- Crochemore y
Rytter. Text
algorithms. Online.
Oxford.
- 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. Linked
Lists Problems. Stanford.
- Sedgewick.
Algoritmos en C++. Pearson.
- Sedgewick y Wayne. Algorithms.
Pearson.
