Matematicas Discretas
Objetivo:
Ofrecer al estudiante un panorama general de las Matemáticas que son particularmente útiles a las Ciencias de la Computación. Se inicia presentando las ideas básicas del principio de conteo y el razonamiento combinatorio elemental. A continuación se ofrece una introducción general a la lógica matemática, un estudio riguroso de la teoría de conjuntos, el principio de la inducción matemática y los métodos recursivos. Posteriormente se estudian las relaciones y funciones y se termina con lenguajes y máquinas de estados finitos. El curso no supone conocimientos matemáticos profundos previos y se enfoca principalmente a desarrollar la capacidad del estudiante para resolver problemas.
Contenido:
1. Relaciones binarias y gráficas.
a) Relaciones binarias.
1) Relaciones y gráficas.
2) Interpretación matricial.
b) Clases de relaciones.
1) Relaciones de equivalencia.
2) Relaciones de orden total y parcial.
3) Retículas y conjuntos parcialmente ordenados.
4) Orden parcial de relaciones de equivalencia.
c) Gráficas y sus aplicaciones.
d) Gráficas de subconjuntos.
e) Gráficas de De Bruijn.
f ) Computación de gráficas con LGraph.
g) Aplicaciones a ingeniería de software: análisis de datos, dependencias
funcionales, etc.
2. Semigrupos, monoides e ideales.
a) Propiedades fundamentales.
1) Semigrupos y monoides: Mapeos, orden parcial en semigrupos.
2) Ideales: Izquierdos, derechos y principales.
3) Semigrupos: Semigrupos simples y semigrup-0, teorema de Jordan-
Holder.
b) Aplicaciones de semigrupos.
1) Semigrupos de relaciones binarias.
2) Semigrupos libres y de transformación: Lenguajes y teoría de máquinas.
3) Semigrupo de substituciones.
3. Teoría de números y computabilidad.
a) Números naturales y enteros.
1) Postulados de Peanoy principio de inducción matemática.
2) Orden total y buen orden.
3) Sistema algebraico de los números naturales y enteros.
4) Algoritmo de la división. Representación de los números enteros.
b) Números, proporción y geometría.
1) Números de Fibonacci.
2) Números de Lucas.
3) Representaciones geométricas.
c) Computabilidad
1) Recursividad.
2) Cardinalidad del continuo y conjunto de Cantor.
3) Palabras infinitas y computación digital infinita.
4) Curvas de Hilbert y Peano.
5) Generación de números aleatorios: variedades de números aleatorios.
4. Grupos y sus aplicaciones
a) Axiomas de grupos.
b) Generadores y gráficas de grupos.
c) Grupos de permutación.
d) Grupos de simetría.
e) Aplicaciones: geometría, cristalografía y códigos.
Bibliografía:
1. Semigrupos y aplicaciones a la computación. Sergio V. Chapa Vergara. Depto. de Ingeniería Eléctrica. Sección de Computación. Notas de clase 2000.
2. Introducción a teoría de grupos. Sergio V. Chapa Vergara. Depto. de Ingeniería Eléctrica. Sección de Computación. Notas de clase 2003.
3. Teoría de números y geometría. Sergio V. Chapa Vergara. Depto. de Ingeniería Eléctrica. Secc. de Computación. Notas de clase 2004.
4. Libro de texto: Kenneth H. Rosen, Discrete Mathematics and Its Applications, McGraw-Hill Education (ISE Editions); 6a edition 2007, ISBN:007288008.
Libros complementarios:
1. Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Pearson Addison Wesley, 5a edition 2003 ISBN:0201726343.
2. Susanna S. Epp, Discrete Mathematics with Applications, Thomson Brooks/Cole, 3a edition 2004, ISBN: 0534359450.
3. Judith L. Gersting, Mathematical structures for Computer Science: A modern approach to Discrete Mathematics, W. H. Freeman and Company, 6a edition 2006, ISBN: 071676864X.
4. Edgar G. Goodaire y Michael M. Parmenter, Discrete Mathematics with Graph Theory, Pearson Prentice Hall, 3a edition 2006, ISBN:0131679953.
5. Rubin H. Landau, A first course in Scientific Computing: Symbolic, graphic, and numeric modeling using Maple, Java, and Fortran 90, Princeton Universtiy Press, 1a edition 2005, ISBN: 0691121834.
6. Edward A. Bender, Mathematics for algorithm and systems analysis, Dover Publications, 1a edición 2005, ISBN: 0486442500.
