115133 Temas Selectos de Ingeniería en Computación II
Trimestre 2010 Invierno
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
11 de enero a viernes 26 de marzo de 2010.
Grupo: CCT81 (martes de 16:00 a
17:30 y jueves
de 16:00 a 19:00).
Asesorías: lunes,
miércoles y viernes de 10:00 a 11:30 en la
oficina H-264.
Salón: Babbage.
Cupo: 30 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á de 1 a 10 puntos.
Además, se otorgarán 4 puntos adicionales al que aparezca
como campeón, 3 a los que aparezcan con medalla de oro, 2 a los
que aparezcan con medalla de plata y 1 a los que aparezcan con medalla
de bronce en cada evaluación. 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 callix.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.79.29. 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 que
muestro abajo es tentativo e irá
apareciendo paulatinamente.
- 12/01: Inicio del
curso. Presentación del curso y de las
reglas de
evaluación. Entrada y salida estándar.
- 14/01: Práctica
en el sistema TJU. Ejemplo de
evaluación.
- 19/01: Representación de diccionarios, colas de prioridad.
- 21/01: Evaluación.
- 26/01:
Representación de cadenas y búsqueda de
patrones. Aplicaciones de ordenamiento.
- 28/01: Evaluación.
- 02/02: Representación de conjuntos, enteros de alta
precisión y polinomios.
- 04/02: Evaluación.
- 09/02:
Técnicas de conteo y relaciones recursivas.
- 11/02: Evaluación.
- 15/02 y 16/02: Visita de
los evaluadores de CACEI para la acreditación de
Ingeniería en Computación.
- 16/02: Primos y primalidad. Divisores, múltiplos y
congruencias.
- 18/02: Evaluación.
- 23/02:
Búsqueda de caminos y ciclos. Búsqueda de
componentes conexas.
- 25/02: Evaluación.
Enunciados 10812 Beat, 572 Oil, 10685 Nature
(números según el sistema de la UVA).
- 02/03: Estaré en un congreso.
- 04/03: Día feriado.
- 09/03:
Búsqueda de
componentes biconexas. Ordenamiento
topológico.
- 11/03: Evaluación.
- 16/03: Algoritmos de Prim, Kruskal y Dijkstra.
- 18/03: Evaluación.
- 23/03: Flujo en
redes. Acoplamiento bipartita.
- 25/03: Evaluación.
[Háganlo en su casa, ya no nos vemos en la Babbage.]
- 01 y 02/04: Examen
global [todos los problemas en dos exámenes
para 48 horas].
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.