Matemáticas Discretas 2

Semestre:

4°

Fecha de elaboración:

Febrero de 2014

Fecha de revisión:

Febrero de 2014

Elaborado por:

Nodari Vakhania Maizuradse, Antonio Daniel Rivera López

Ciclo de formación:

Profesional

Área curricular:

Ciencias de la Disciplina

Tipo de unidad:

Teórica

Carácter de unidad:

Obligatoria

Clave:

MD02FP050010

Créditos:

10

Semestre:

4°

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:

Domina los fundamentos matemáticos necesarios para el desarrollo de la habilidad de entender y crear argumentos matemáticos.

Antecedentes Recomendadas:

Ninguna

Consecuentes Recomendadas:

  • Teoría de la Computación

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.

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 Probabilidad y conteo.
    1. Probabilidad discreta (distribución uniforme).
    2. Distribución no uniforme. Probabilidad condicional.
    3. Eventos independientes.
    4. Distribución binomial y teorema de Bernouli. Variables aleatorizadas y valores esperados.
    5. Complejidad computacional caso promedio.
    6. Relaciones de recurrencia. Solución de recurrencias.
    7. Forma complementaria del principio de inclusión-exclusión y sus aplicaciones.
    8. Divide y vencerás.
  2. II Grafos y árboles.
    1. 2.1 Grafos planos. Fórmula de Euler. Coloreado de grafos, números cromáticos máximales.
    2. 2.2 Introducción a árboles. Cobertura de árboles (preorder, inorder y postorder). Búsqueda profundidad primero y altura primero.
    3. 2.3 Cobertura mínima de árboles, algoritmo de Prim.
    4. 2.4 Búsqueda en árboles binarios.
    5. 2.5 Árboles de decisión y tiempo mínimo para el ordenamiento. Bubble sort, merge sort, quick sort.
    6. 2.6 Isomorfismo de árboles.
  3. III Modelos de redes.
    1. 3.1 Flujo en redes. Flujo máximo. Teorema de flujo máximo corte mínimo. Algoritmo de nivelado de Ford-Fuckerson.
    2. 3.2 Matchings. Problemas Matchings como problemas de flujo.
  4. IV Modelado computacional.
    1. 4.1 Circuitos secuenciales y máquinas de estado finito.
    2. 4.2 Autómata de estado finito.
    3. 4.3 Lenguaje y gramática.
    4. 4.4 Autómata de estado finito no determinista.
    5. 4.5 Lenguajes y autómata.
  5. V Elementos de optimización discreta.
    1. 5.1 Problemas de programación lineal.
    2. 5.2 Método simplex. Interpretación geométrica. Teorema dual.
    3. 5.3 Problemas polinomiales y no polinomiales, clasificación de los problemas NP. NP-completo.
    4. 5.4 Métodos de solución común para los problemas NP-completos: branch-and-bound y programación dinámica.

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.