115132 Temas Selectos de Ingeniería en Computación I
Trimestre 2007 Invierno
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
15 de enero a viernes 30 de marzo.
Grupo: CCT81 (lunes,
miércoles y viernes de 10:00 a
11:30).
Asesorías: lunes,
miércoles y viernes de 11:30 a 13:00, martes de 9:00 a 10:00 y
de 16:00 a 18:00 en la oficina H-264.
Salón: Sala de juntas de
Sistemas.
Cupo:
40 estudiantes incluyendo
a los oyentes.
Requisitos
Para inscribirte a Temas Selectos de Ingeniería en
Computación debes haber acreditado Diseño de
Algoritmos. También debes saber programar en alguno de los
lenguajes C, C++ o Java
a un nivel
similar al de los cursos
obligatorios de programación (Introducción
a la
Programación y Métodos Numéricos) y de
preferencia
al nivel del curso de Estructura de Datos (sin objetos).
Contenido
Se cubrirá el siguiente temario (libro y capítulo a
cubrir):
- Procesamiento de cadenas (ver Skiena y Revilla, 3).
- Búsqueda en cadenas (Sedgewick, 19).
- Búsqueda de patrones (Sedgewick, 20).
- Algoritmos geométricos (ver Skiena y Revilla, 14).
- Segmentos y polígonos (Sedgewick, 24).
- Cerradura convexa (Sedgewick, 25).
- Búsqueda por rango (Sedgewick, 26).
- Intersección geométrica (Sedgewick, 27).
- Puntos más cercanos (Sedgewick, 28).
- Algoritmos de grafos (ver Skiena y Revilla, 10).
- Conectividad (Sedgewick, 30 y 32).
- Flujo en redes (Sedgewick, 33).
- Acoplamientos (Sedgewick, 34).
Se harán cuatro o cinco evaluaciones individuales, una o dos por
cada
tema principal. Cada evaluación
constará de dos
problemas y cada problema tendrá un valor entero de 0 a 20
puntos. La
calificación
final será la suma de las calificaciones de los cinco mejores
problemas para cada estudiante. No
habrá examen global. Se
requiere:
- Obtener al menos 60 puntos para acreditar con S.
- Obtener al menos 73 puntos para acreditar con B.
- Obtener al menos 87 puntos para acreditar con MB.
Calendario
El calendario que muestro abajo es tentativo y está sujeto a
modificaciones a lo largo del curso:
- 15/01: Inicio del curso.
- 17/01: Búsqueda en cadenas (fuerza bruta).
- 19/01: Búsqueda en cadenas (Knutt-Morris-Pratt).
- 22/01: Búsqueda en cadenas (Boyer-Moore).
- 24/01: Búsqueda en cadenas (Rabin-Karp).
- 26/01: Búsqueda de patrones.
- 29/01: Intersección de segmentos. Primera
evaluación (para
entregar el 05/02).
- 31/01: Camino cerrado simple.
- 02/02: Inclusión en un polígono.
- 05/02: No hay clases (día feriado).
- 07/02: Cerco convexo (envolventes) y eliminación interior.
- 09/02: Cerco convexo (Graham). Segunda
evaluación (para entregar el 16/02).
- 12/02: Búsqueda por rango (rejilla).
- 14/02: Búsqueda por rango (árboles bidimensionales).
- 16/02: Intersección de segmentos (horizontales y
verticales).
- 19/02: Intersección de segmentos (generales).
- 21/02: Puntos más cercanos (divide y vencerás). Tercera evaluación (para entregar el 05/03)
- 23/02: Puntos más cercanos (diagrama de Voronoi).
- 26/02 y 28/02: No hay clases (estaré
en una conferencia).
- 02/03: Conectividad (componentes conexas). Cuarta
evaluación
(para entregar
el 23/03).
- 05/03: Conectividad (componentes biconexas).
- 07/03: Conectividad (componentes fuertemente conexas).
- 09/03: Flujo en redes (Ford-Fulkerson). Quinta
evaluación (para entregar el
30/03).
- 12/03: Acoplamientos (bipartitas).
- 21/03: No hay clases (día feriado).
- 30/03: Fin del curso.
- 02/04: Pasen a verme de 9:00 a 12:30 o de 16:30 a 18:00 para
mostrarme sus evaluaciones.
Bibliografía y otros recursos electrónicos
- Programming
Challenges, Skiena
y Revilla,
Springer Verlag.
- Programming
Pearls, Bentley, Addison Wesley.
- Primes and
Programming, Giblin,
Cambridge
University Press.
- Problems
on Algorithms, Parberry,
Prentice Hall.
- The
Algorithm Design Manual, Skiena, Telos.
- Algoritmos en C++, Sedgewick,
Pearson.
- Computational
Geometry in C, O'Rourke,
Cambridge University Press.
- El
Lenguaje de Programación C, Kernighan y Ritchie, Pearson.
- Notas del curso
en Stony Brook por Skiena.
La versión más reciente de esta página se puede
encontrar en http://ce.azc.uam.mx/profesores/franz/tsc/