115132 Temas Selectos de Ingeniería en Computación I
Trimestre 2007 Otoño
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
17 de septiembre a viernes 7 de diciembre.
Grupo: CCT81 (lunes,
miércoles y viernes de 16:00
a
17:30).
Asesorías: lunes,
miércoles y viernes de 11:30 a 13:00 en la
oficina H-264.
Salón: K-107 (antes
E-306 o F-207).
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
tareas. Cada tarea constará de uno o
dos
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.67.155. 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.
- 17/09: Inicio del curso. Presentación del curso y de las
reglas de
evaluación.
- 19/09: Clase cancelada
por falta de llaves para entrar al salón. Nos cambiaron al
salón K-107. Regístrense para probar sus tareas aquí.
- 21/09: Entrada y salida estándar. Esta es la página
del curso que mencioné en clase.
- 24/09: Representación de diccionarios. Primera
tarea (para
el 01/10).
- 26/09: Representación de colas de prioridad.
- 28/09: Representación de conjuntos.
- 01/10: Representación de cadenas. Segunda
tarea (para el 10/10).
- 03/10: Búsqueda de patrones.
- 05/10: Aplicaciones de ordenamiento.
- 08/10: Conferencia sobre número cromático y flujo
en gráficas (Laura
Chávez).
- 10/10: Representación de enteros de alta
precisión.
- 11/10: El disco duro de la máquina donde estaban sus
cuentas amaneció
muerto. Me tomará cierta cantidad de tiempo darles cuentas
nuevas. La fecha de
entrega de cualquier tarea que haya dejado se correrá a al menos
una
semana después de que les dé sus nuevas cuentas.
- 11/10 a 15/10: Cuarto concurso de
programación de la UAM Azcapotzalco. Examen eliminatorio.
- 12/10: Día feriado.
- 15/10: Representación de polinomios.
- 17/10: No habrá
clase, estaré en un congreso.
- 19/10: No habrá
clase, estaré en un congreso.
- 22/10: Primera sesión del minicurso de separación
de puntos (Auxiliadora
Moreno).
- 23/10 [10:00-11:30]: Conferencia sobre mosaicos (Auxiliadora
Moreno).
- 23/10 [13:00-16:00]: Cuarto concurso de
programación de la UAM Azcapotzalco. Examen final.
- 23/10 [16:30-19:00]: Segunda y tercera sesiones del minicurso de
separación de puntos (Auxiliadora
Moreno).
- 24/10: Esta clase se impartió en la segunda sesión
del minicurso de
separación de puntos.
- 26/10: Esta clase se impartió en la tercera sesión
del
minicurso de
separación de puntos.
- 29/10: Técnicas de conteo. Tercera
tarea (para
el 05/11).
- 31/10: Relaciones recursivas.
- 02/11: Día feriado.
- 03/11 y 04/11: Competencia regional de México y
Centroamérica del ACM ICPC en Querétaro.
- 05/11: Primos y primalidad. Cuarta tarea
(para el 12/11).
- 07/11: No hubo clase por
falta de alumnos. Ya
tienen cuentas y claves nuevas. Envíen sus
cuatro primeras tareas a más tardar el 12/11.
- 09/11: Divisores, múltiplos y congruencias.
- 12/11: Búsqueda de caminos y ciclos. Quinta
tarea (para el
19/11).
- 14/11: Búsqueda de componentes conexas y biconexas.
- 16/11: No habrá
clase, estaré en la presentación de un libro del
que soy coautor.
- 19/11: Ordenamiento
topológico. Sexta tarea
(para el 26/11).
- 21/11: Algoritmos de Prim, Kruskal y Dijkstra.
- 23/11: No habrá
clase, estaré en el Consejo Divisional de CBI.
- 26/11: No habrá
clase, estaré con el Dr. Eduardo de la Garza.
- 28/11: Flujo en redes.
- 30/11: Acoplamiento bipartita.
- 03/12: No habrá
clase, esta clase se impartió en la primera sesión
del minicurso de combinatoria aditiva.
- 04/12 [10:00-11:30]: Conferencia sobre suma de conjuntos (Shalom
Eliahou).
- 04/12 [16:30-18:00]: Primera sesión del minicurso de
combinatoria aditiva (Shalom Eliahou).
- 05/12 [16:30-18:00]: Segunda sesión del minicurso de
combinatoria aditiva (Shalom Eliahou).
- 07/12: Fin del curso.
- 10/12: No habrá global, pero está programado para
esta fecha de 16:00 a 19:00.
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.