CURSO : Matematicas Discretas
SIGLA : IIC2252
CRÉDITOS : 10
REQUISITOS : MAT1202 Algebra Lineal;
IIC1102 Introduccion a la Programacion
SEMESTRE : II
1. OBJETIVOS
En este curso se entrega al alumno materias de matematica que son fundamentales y utiles
para los alumnos de las carreras de computacion. En todo momento se establece la
conexion de las materias tratadas con temas de ciencia de computacion.
Se expone al alumno al desarrollo de algunas teorias matematicas; con sus
correspondientes axiomatizaciones, teoremas y demostraciones. Esta actividad, aparte de
sus interesantes aspectos computacionales, tiene el poder formativo de la capacidad de
enfrentarse de manera fundamentada y rigurosa a las materias generales de estudio y
actividad profesional. En esta actividad se hace aparecer de manera natural las
axiomatizaciones y los modelos matematicos a traves de la inspeccion de situaciones
computacionales concretas, en las cuales tambien se comprueba las consecuencias de los
modelos.
2. CONTENIDO
- Repaso de conjuntos, Relaciones y funciones. Clausuras de relaciones. Relaciones de
equivalencia. Ordenes (totales, parciales, pre-ordenes, reticulados). Cardinalidad.
- Algebras de Boole. Logica proposicional.
- Induccion. Induccion por curso de valores. Definiciones inductivas. Principio de buen
orden. Recursion. Induccion como definicion de dominios constructibles y
minimizacion. Aplicacion a correccion de programas.
- Algebra abstracta basica: Grupos, Anillos, Cuerpos, Cuerpos finitos. Elementos de
teoria de numeros. Vision desde algebra computacional: Versiones efectivas y
eficientes de teoremas existenciales. Protocolo criptografico de Rivest-Shamir-Adleman
(RSA).
- Axiomatizacion de algunas estructuras de datos de la computacion, por ejemplo,
strings, listas, colas, arboles, etc. Principios de induccion estructural.
- Elementos de grafos y arboles: Trayectorias, Clausura transitiva, Algoritmos de
Warshall, Floyd, Dijkstra, Arbol minimo de cobertura.
- Elementos de combinatoria y probabilidad discreta.
3. BIBLIOGRAFIA
Complementaria:
AHO, Alfred and ULLMAN Jeffrey D. Foundations of computer science. C ed. New
York, Computer Science Press, 1996.
GARDING, Lars and TAMBOUR, Torbjorn. Algebra for computer science. New
York, Springer, 1988.
GRAHAM, L.R., KNUT, D.E. and PATASHNICK, O. Concrete mathematics.
Reading, Mass., Addison Wesley, 1989.
GRASSMAN, W.K. and TREMBLAY, J.P. Logic and discrete mathematics: a
computer science perspective. New York, Prentice Hall, 1996.
GRIES, D. and SCHNEIDER, F.B. A logical approach to discrete mathematics. New
York, Springer, 1993.
GROSSMAN, J.W. Discrete mathematics. New York, MacMillan, 1990.
LIPSON, J.D. Elements of algebra and algebraic computing. Reading, Mass.,
Addison Wesley, 1981.
MANNA, Zohar and WALDINGER, Richard. The logical basis for computer
programming. Reading, Mass., Addison Wesley 1985-1990. 2v.
ROSEN, K.H. Discrete mathematics and its application. 3rd ed. New York, McGraw
Hill, 1995.
ROSS, K.A. and WRIGHT, Ch.R. Discrete mathematics. 3rd. ed. New York,
Prentice Hall, 1992.
