MATERIA: Matemáticas Discretas

CLAVE: COMP-120

SEMESTRE DE UBICACION: Primero

AREA: Ciencias de la Computación

OBJETIVOS: Este curso da a los estudiantes una introducción al área de las matemáticas finitas, poniendo especial énfasis, en teoría de algoritmos, gráficas, álgebra de Boole, introducción y recursión

TEMARIO:

  1. Lógica formal, demostraciones y análisis de algoritmos

    • Enunciados, representaciones simbólicas y tautologías

    • Cuantificadores, predicados y validez

    • Lógica proposicional

    • Lógica de predicados

    • Programación lógica y pruebas de correctez

    • Técnicas de demostración

    • Inducción

    • Recursión y relaciones de recurrencia

    • Análisis de algoritmos y más pruebas de correctez

  2. Relaciones y Gráficas dirigidas u Orientadas

    • Conjuntos producto y particiones

    • Relaciones y gráficas dirigidas

    • Trayectorias en las relaciones y en las gráficas dirigidas

    • Propiedades de las relaciones

    • Representación por computadora de relaciones y gráficas dirigidas

    • Manipulación de las relaciones

    • Conectividad y el algoritmo de Warshall

  3. Funciones

    • Funciones en gráficas

    • Permutaciones

    • Números especiales: de Stirling, Eulerianos, Armónicos, Series Armónicas, Números de Bernoulli, de Fibonacci

  4. Orden, relaciones y estructuras

    • Conjuntos parcialmente ordenados

    • Elementos extremos de los conjuntos parcialmente ordenados

    • Latices

    • Álgebras de Boole

    • Implementación de las funciones booleanas

  5. Arboles y lenguajes

    • Arboles

    • Árboles etiquetados

    • Lenguajes

    • Representación de gramáticas y lenguajes especiales

    • Análisis de un árbol

    • Árboles no dirigidos

  6. Problemas de coloración

BIBLIOGRAFIA:

  • Gersting, J.L., Mathematical Structures For Computer, 3rd. edition, Computer Sciences Press, W.H. Freeman and company, 1993

  • Gries, D. ; Schneider, F.B., A Logical Approach to Discrete Math, Texts and Monographs in Computer Science, Springer-Verlag, 1994

BIBLIOGRAFIA COMPLEMENTARIA:

  • Kolman, B.; Busby R. C. Estructuras de Matemáticas Discretas para la Computación, Prentice Hall Hispanoamericana S.A., 1986

  • Ince, D. C., An Introduction to Discrete Mathematics and Formal System Specification, Clarendon Press, Oxford, 1988

  • Kalmanson, K., And Introduction To Discrete Mathematics and its Applications, Addison-Wesley Publishing Company, 1986

  • Yandl, A. L., Finite Mathematics, Brooks/Cole Publishing Company, 1991

  • Townsend, M., Discrete Mathematics: Applied Combinatorics And Graph Theory, Benjamin-Cummings, 1987

  • Graham, R.L.; Knuth, D. E.; Parashnik, O., Concrete Mathematics, A Foundation For Computer Science, Addison-Wesley Publishing Company, 1989