CURSO : MATEMATICAS DISCRETAS
TRADUCCION : DISCRETE MATHEMATICS
SIGLA : IIC1253
CRÉDITOS : 10
MÓDULOS : 03
REQUISITOS : MAT1203 ALGEBRA LINEAL
CARÁCTER : MINIMO
DISCIPLINA : INGENIERIA
I. DESCRIPCION
El curso ense?a los elementos que permiten formalizar enunciados de problemas diversos de ingenieria
usando conceptos de matematica discreta (conjuntos, relaciones, funciones, induccion, etc.) y a modelar este
tipo de problemas con estos elementos; ademas, se ense?a la teoria de grafos, para representar y resolver
algunos de estos tipos de problemas, y la metodologia formal de analisis de algoritmos y de complejidad
computacional.
II. OBJETIVOS
Al finalizar el curso, el alumno sera capaz de:
1. Formular enunciados formales en notacion matematica usando logica, conjuntos, relaciones, funciones,
cardinalidad, y otras herramientas, desarrollando definiciones y teoremas al respecto, asi como
demostrar o refutar estos enunciados, usando variadas tecnicas.
2. Aplicar induccion como tecnica para demostracion de propiedades en conjuntos discretos y como
tecnica de definicion formal de objetos discretos.
3. Modelar formalmente un problema usando conjuntos, relaciones, y las propiedades necesarias, y
demostrar propiedades al respecto de su modelo.
4. Modelar una problematica discreta usando grafos y las tecnicas asociadas, y demostrar propiedades
acerca de problemas modelados como grafos.
7. Demostrar formalmente que un algoritmo simple funciona correctamente, y determinar la eficiencia de
un algoritmo, desarrollando una notacion asintotica para estimar el tiempo de ejecucion.
8. Determinar la dificultad relativa de problemas computacionales, basando sus argumentos en tecnicas
de complejidad computacional.
III. CONTENIDOS
1. Repaso de conjuntos, relaciones y funciones; clausuras de relaciones; relaciones de equivalencia;
ordenes (totales, parciales, pre-ordenes, reticulados); cardinalidad.
2. Algebras de Boole; logica proposicional.
3. 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.
4. 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).
5. Axiomatizacion de algunas estructuras de datos de la computacion, por ejemplo, strings, listas, colas,
arboles, etc. Principios de induccion estructural.
6. Elementos de grafos y arboles: Trayectorias, Clausura transitiva, Algoritmos de Warshall, Floyd,
Dijkstra, Arbol minimo de cobertura.
7. Elementos de combinatoria y probabilidad discreta.
PONTIFICIA UNIVERSIDAD CATOLICA DE CHILE
FACULTAD DE INGENIERIA / Mayo de 2009
1
IV. METODOLOGIA
Modulos semanales:
- Catedras: 2
- Ayudantias: 1
El curso se realiza usando un metodo de ense?anza centrado en el alumno; este metodo permite a los alumnos
desarrollar las competencias definidas en los objetivos del curso.
Este curso esta dise?ado de manera que el alumno estudie en promedio 6 hrs. de estudio a la semana.
V. EVALUACION
El desempe?o de los alumnos en el curso se evalua a base de pruebas, tareas y un examen.
VI. BIBLIOGRAFIA
Textos Minimos
Epp S. Discrete Mathematics with Applications, 3rd ed. 2003.
PONTIFICIA UNIVERSIDAD CATOLICA DE CHILE
FACULTAD DE INGENIERIA / Mayo de 2009
2
