Matemáticas Discretas 1

Semestre:

3°

Fecha de elaboración:

Agosto de 2013

Fecha de revisión:

Septiembre de 2013

Elaborado por:

Antonio Daniel Rivera López

Ciclo de formación:

Básico

Área curricular:

Ciencias de la Disciplina

Tipo de unidad:

Teórica

Carácter de unidad:

Obligatoria

Clave:

MD01FB050010

Créditos:

10

Semestre:

3°

Horas Teoría:

5

Horas Práctica:

0

Programas académicos en los que se imparte:

Licenciatura en Ciencias Áreas terminales en Matemáticas, Física, Bioquímica y Biología Molecular, y Ciencias Computacionales y Computación Científica

Prerrequisitos:

Analiza y utiliza los principios básicos de la lógica matemática, anclados en la teoría de conjuntos, la lógica proposicional, la deducción natural y la lógica de predicados.

Antecedentes Recomendadas:

Ninguna

Consecuentes Recomendadas:

  • Algorítmica
  • Matemáticas Discretas 2

Presentación de la unidad de aprendizaje:

Se desarrolla la habilidad del estudiante para entender y crear argumentos matemáticos. La matemática discreta es la puerta a cursos más avanzados; proporciona la base matemática a muchos cursos de ciencias de la computación, incluyendo estructuras de datos, algoritmos, teoría de base de datos, teoría de autómatas, lenguajes formales, teoría de compiladores, seguridad informática y sistemas operativos. También contiene el fundamento matemático necesario para resolver problemas en investigación de operaciones, química, ingeniería y biología.

Propósito de la unidad de aprendizaje:

Proporcionar los fundamentos matemáticos necesarios para cursos posteriores, a través del desarrollo de la habilidad del estudiante para entender y crear argumentos matemáticos.

Competencias profesionales:

Se comunica con otros profesionales no informáticos y brinda asesoría en la aplicación de las ciencias computacionales en sus respectivas áreas de trabajo.Participa en equipos de trabajo inter y transdiciplinares para la elaboración y desarrollo de proyectos de investigación

Contribución al perfil de egreso:

Para el cumplimiento del perfil, se desarrolla la habilidad para enlazar conocimientos y técnicas de diferentes áreas de las ciencias exactas y naturales.

Secuencia temática:

  1. I Conjuntos y funciones.
    1. Operaciones con conjuntos. Subconjunto y conjunto potencia de un conjunto. Producto cartesiano de dos conjuntos, unión e intersección de conjuntos, diferencia de conjuntos y complemento de un conjunto.
    2. Funciones. Definición de relación entre dos conjuntos, operaciones sobre relaciones, composición de relaciones, relación de equivalencia, partición de un conjunto definida por una relación de equivalencia, matriz y gráfica asociadas a una relación. Definición de una función como una relación, funciones inyectivas y sobreyectivas, inversa de una función y composición de funciones.
    3. Cardinalidad de conjuntos. Definición de cardinalidad para conjuntos finitos e infinitos, conjuntos numerables, demostración de que el conjunto de los números enteros Z y el conjunto de los números racionales Q son numerables. Demostración de que el conjunto de los números reales R no es numerable.
  2. II Introducción a la teoría de números.
    1. 2.1 Propiedades básicas de los números enteros. Divisibilidad, números primos, teorema fundamental de la aritmética, algoritmo de la división, ideales y máximo común divisor, el algoritmo de Euclides y el algoritmo extendido de Euclides.
    2. 2.2 Congruencias. Definición y propiedades básicas de congruencias, congruencias lineales, teorema chino del residuo, clases residuales y clases de equivalencia módulo n, operaciones de suma y multiplicación en las clases de equivalencia módulo n, definición del anillo formado por las clases de equivalencia módulo n.
    3. 2.3 Introducción a la criptografía. Teorema pequeño de Fermat, criptografía de clave pública, cifrado y descifrado del sistema criptográfico RSA.
  3. III Combinatoria.
    1. 3.1 Permutaciones y combinaciones. Definición y ejemplos de permutaciones y combinaciones, identidad de Pascal, identidad de Vandermonde, permutación con repetición, permutación circular.
    2. 3.2 Los principios de la pichonera y de inclusión-exclusión. Principio de la pichonera y ejemplos de aplicación, generalización del principio de la pichonera, principio de inclusión-exclusión y ejemplos de aplicación.
    3. 3.3 Recurrencia. Relaciones de recurrencia, soluciones particulares, solución de las relaciones de recurrencia utilizando funciones generadoras.
  4. IV Introducción a la teoría de grupos.
    1. 4.1 Introducción a las estructuras algebraicas. Sistemas algebraicos, semigrupos y monoides, homomorfismo de semigrupos y monoides, subsemigrupos y submonoides.
    2. 4.2 Teoría de grupos. Grupos, permutación, grupo de permutaciones, grupo dihedral, grupo cíclico, subgrupos, homomorfismo de grupos, núcleo de un homomorfismo, subgrupo normal y grupo cociente.
    3. 4.3 Algunas aplicaciones de teoría de grupos. Teoría de codificación, codificadores y decodificadores, código de grupo, código de Hamming, corrección de errores en código de grupo, procedimiento paso a paso para decodificar códigos de grupo.
  5. V Introducción a la teoría de gráficas.
    1. 5.1 Definiciones básicas. Gráfica, grado de un vértice, gráfica completa, gráfica regular, gráfica bipartita, subgráficas, gráficas isomorfas, representación matricial de gráficas.
    2. 5.2 Conexidad. Rutas, paseos, caminos, ciclos, conexidad, gráficas eulerianas con demostración de suficiencia y necesidad para la existencia de un ciclo euleriano y un camino euleriano, gráficas hamiltonianas con demostración del Teorema de Ore y del Teorema de Dirac, gráficas dirigidas, conexidad en gráficas dirigidas, el problema del camino más corto.
    3. 5.3 Gráficas planas. Gráficas planas incluyendo la demostración de la Fórmula de Euler y el Teorema de Kuratowski este último sin demostración.
    4. 5.4 Coloreo de los vértices de una gráfica. Aplicaciones del coloreo de vértices y el teorema de los cuatro colores.

Criterios de Evaluación:

  • Exámenes parciales: 40%
  • Examen final: 30%
  • Participación en clase: 10%
  • Búsqueda de información: 10%
  • Otra (especifique): Tareas: 10%

Bibliografía básica:

  • Ferland, Kevin. 2009. Discrete mathematics. Ed. Houghton Mifflin Company.
  • Garnier, Rowan y Taylor, Jhon. 2010. Discrete mathematics, proofs, structures, and applications. 3a edición. Ed. CRC Press Taylor and Francis Group.
  • Garnier, Rowan y Taylor, Jhon. 2002. Discrete mathematics for new technology. 2a edición. Ed. Institute of Physics Publishing.
  • Grimaldi, R. P. 1998. Matemáticas discreta y combinatoria: una introducción con aplicaciones. 3a edición. Ed. Pearson Prentice-Hall.

Bibliografía complementaria:

  • Grossman, Peter. 2002. Discrete mathematics for computing. 2a edición. Ed. Palgrave Macmillan.
  • Penner, R. C. 1999. Discrete mathematics proof techniques and mathematical structures. Ed. World Scientific.
  • Rosen, K.H. 2004. Matemática discreta y sus aplicaciones. 5a edición. Ed. McGraw-Hill.
  • Shanker Rao, G. 2009. Discrete mathematical structures. 2a edición. Ed. New Age International Publishers.
  • Veerarajan, T. 2008. Matemáticas discretas con teoría de gráficas y combinatoria. Ed. McGraw-Hill.