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