115132 y 115133
Temas Selectos de Ingeniería en Computación I y II
Profesor: Dr. Francisco Javier
Zaragoza Martínez
Horario: Martes de 16:00 a
17:30 y jueves de 16:00 a 19:00.
Objetivo
Al final del curso el alumno conocerá e implementará
diversos algoritmos y estructuras de datos elementales para la
búsqueda de patrones en cadenas, aritmética,
álgebra, combinatoria, teoría de números, flujo en
redes, acoplamiento, rejillas y geometría plana. Además,
el alumno podrá modelar, resolver e implementar las soluciones a
diversos problemas utilizando estos algoritmos y estructuras.
Contenido sintético
- 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
10 evaluaciones prácticas semanales (desarrollo de programas
para la resolución de problemas). Sólo podrás acreditar
una de las dos UEA.
Bibliografía
- Programming Challenges: The Programming Contest Training Manual.
S. S. Skiena y M. A. Revilla. Springer. 2003.
- Algorithm Design. J. Kleinberg y E. Tardos. Addison Wesley. 2005.
- The Algorithm Design Manual. S. S. Skiena. Telos/Springer. 1997.
- Algorithms from P to NP. B. M. E. Moret y H. D. Shapiro. Benjamin
Cummins. 1990.