Imprimir

Programa

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