115132 Temas Selectos de Ingeniería en Computación I y II
Trimestre 2008 Otoño
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: martes
30 de septiembre a jueves 11 de diciembre de 2008.
Grupo: CCT81 (martes de 16:00 a
17:30 y jueves
de 16:00 a 19:00).
Asesorías: martes,
miércoles y jueves de 10:00 a 11:30 en la
oficina H-264.
Salón: Babbage.
Cupo: 35 estudiantes.
Contenido
Para inscribirte a Temas Selectos de Ingeniería en
Computación debes haber acreditado Diseño de
Algoritmos. Se cubrirá el siguiente temario:
- Introducción: Entrada y salida estándar.
- Estructuras de datos: Diccionarios, colas de prioridad y
conjuntos.
- Manipulación de cadenas: Búsqueda de patrones.
- Aplicaciones de ordenamiento.
- Aritmética y álgebra: Enteros de alta
precisión, polinomios y raíces.
- Combinatoria: Conteo, recursión e inducción.
- Teoría de números: Primos, divisibilidad y
congruencias.
- Recorrido de grafos: Caminos, ciclos, conexidad y ordenamiento
topológico.
- Algoritmos de grafos: Flujo en redes y acoplamiento bipartita.
- Rejillas: Rectangulares, triangulares y hexagonales.
- Geometría: Líneas, triángulos y
círculos.
Evaluación
Habrá al menos seis evaluaciones. Cada evaluación
constará de uno a tres
problemas y cada problema valdrá 10 puntos. Se
requiere obtener
- al menos 60 puntos para acreditar con S,
- al menos 73 puntos para acreditar con B y
- al menos 87 puntos para acreditar con MB.
Las tareas se deberán entregar por correo electrónico a
la cuenta tsc en gabrijela.azc.uam.mx. Su cuenta
está en la misma máquina, a la que se pueden conectar con
ssh y que tiene
dirección IP 148.206.75.15. 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 y de entrega de tareas que
muestro abajo es tentativo e irá
apareciendo paulatinamente.
- 30/09: Inicio del
curso. Presentación del curso y de las
reglas de
evaluación. Entrada y salida estándar.
- 02/10: Sesión de práctica del Quinto Concurso de
Programación de la UAM.
- 07/10: Representación de diccionarios, colas de prioridad
y conjuntos.
- 09/10: Evaluación: Examen final del Quinto Concurso de
Programación de la UAM.
- 14/10: Solución del examen final del Quinto Concurso de
Programación de la UAM.
- 16/10: Estaré en un congreso.
Evaluación:
Sesión de práctica
para el Concurso Regional de Programación ACM
ICPC.
- 21/10: Representación de cadenas y búsqueda de
patrones. Aplicaciones de ordenamiento.
- 23/10: Evaluación: Sesión de práctica
para
el Concurso Regional de Programación ACM ICPC. Repetición.
- 28/10: Representación de enteros de alta
precisión y de polinomios.
- 30/10: Evaluación: Sesión de práctica
para
el Concurso Regional de Programación ACM ICPC.
- 01 y 02/11: Concurso Regional de Programación
ACM ICPC.
- 04/11: Técnicas de conteo y relaciones recursivas.
- 06/11: Evaluación
y repetición.
- 11/11: Primos y primalidad. Divisores, múltiplos y
congruencias.
- 13/11: Evaluación
y repetición.
- 18/11: Búsqueda de caminos y ciclos. Búsqueda de
componentes conexas y biconexas. Ordenamiento
topológico.
- 20/11: Día feriado.
- 25/11: Algoritmos de Prim, Kruskal y Dijkstra. Flujo en redes.
Acoplamiento bipartita.
- 27/11: Evaluación.
- 02/12: Clase cancelada
debido a la UAMistad. Con el fin de decidir si habrá una
evaluación más o no, me urge que todos los inscritos le
envíen un correo a mi ayudante (sergio10barca [at] yahoo.com.mx)
con copia a mi (franz [at] correo.azc.uam.mx) anotando lo siguiente:
todos los nombres de los integrantes de su equipo y todas las cuentas
que hayan usado en el sistema TJU.
- 04/12: Evaluación.
- 09/12: Estaré en un congreso.
- 11/12: Fin del curso. Estaré en un congreso.
- 16/12: Fecha programada para el examen global.
- 17/12: Entrega del acta.
Bibliografía
- Giblin. Primes and
Programming, Cambridge
University Press.
- Gregorio et
al. Ejercicios de
programación creativos y recreativos en C++. Prentice Hall.
- Kleinberg
y Tardos. Algorithm Design.
Addison Wesley.
- O'Rourke. Computational
Geometry in C, Cambridge
University Press.
- Parberry. Problems on Algorithms.
Prentice Hall.
- Skiena
y Revilla. Programming
Challenges. Springer Verlag. [Libro de texto]
- Skiena. Course Notes for
Programming Challenges. Stony Brook.
