1151042 Algoritmos y Estructuras de Datos
Trimestre 2015 Invierno
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 19 de enero a miércoles 1 de abril de 2015.
Grupo: CSI81 (martes y
jueves de 14:30 a 16:45).
Asesorías: lunes, miércoles
y viernes de 15:00 a 16:00 en la oficina H-264.
Salón: Babbage.
Cupo: 40 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 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 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.
20/01:
Inicio del curso. Presentación del curso y de las reglas de
evaluación. Tipos de datos abstractos [SW1.1 y SW1.2]. Examen diagnóstico.
Tarea 1 (para el 25/01).
22/01:
Arreglos y apuntadores [KR5.1-5].
26/01: Inicia el examen
calificatorio del XII Concurso
de programación de la UAM. Tarea 2
(para el 01/02).
27/01: Búsqueda interna: lineal,
binaria e interpolación [SW3.1].
29/01: Eficiencia de algoritmos
iterativos y recursivos [SW1.4 y SW2.1].
03/02:
Ordenamiento interno: inserción directa y mezcla [SW2.2]. Tarea 3 (para el 09/02).
05/02:
Día feriado.
10/02: Ordenamiento interno:
selección directa y quicksort [SW2.3]. Tarea 4 (para el 16/02).
12/02: Estructuras y apuntadores
[KR6.1-7].
17/02:
Memoria dinámica [KR6].
19/02:
Pilas y colas [SW1.3].
Tarea 5 (para el 26/02).
24/02: Listas ligadas [SW1.3].
26/02: No hubo
clase por paro. No olviden esto: Tarea
6 (para el 02/03).
03/03:
Estaré en un congreso.
Ordenamiento interno: montículos [SW2.4].
05/03:
Estaré en un congreso.
10/03: Aplicaciones de listas ligadas
[SW1.3]. Tarea 7 (para el 16/03).
12/03: Árboles binarios de búsqueda [SW3.2].
17/03: Árboles
balanceados [SW3.3].
Notas de otro curso.
Tarea 8 (para el 27/03).
19/03:
Gráficas [SW4.1]
y digráficas [SW4.2].
Búsqueda en profundidad y en amplitud.
24/03: Búsqueda por prioridad:
Algoritmos de Prim [SW4.3],
Kruskal [SW1.5]
y Dijkstra [SW4.4].
26/03: Tablas de dispersión [SW3.4].
31/03:
Ordenamiento de cadenas [SW5.1].
Búsqueda de subcadenas [SW5.3].
02/04:
Día feriado.
09/04: Examen global, a las 15:00 en
la Sala Babbage.
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.