Matemáticas para la Computación

Asignatura

Ficha Técnica
Modalidad Obligatoria
Área Especialización
U.C: 3
Código 2120360000120

Justificación

El desarrollo de la ciencia de la computación tiene como uno de sus pilares fundamentales a las matemáticas, especialmente la parte que aborda a la matemática discreta, ya que esta se encarga del estudio de los conceptos aplicados a los procesos finitos y permite desarrollar metodologías para abordar el estudio de estos procesos. Es por esta razón que este curso es indispensable en la formación básica de los maestrantes de este programa.

Objetivos del Curso

  • El curso de matemática discreta para la computación tiene como objetivo dotar al estudiante de conocimientos para:
  • Entender y aplicar los conceptos básicos de la teoría combinatoria.
  • Entender y aplicar los conceptos de la teoría de conjuntos.
  • Entender y aplicar los conceptos básicos de la teoría de grafos.
  • Entender y aplicar los conceptos básicos de la teoría clásica de optimización.

Prerequisitos

No hay prerequisitos para este curso.

Contenido Programático

Unidad 1: Conjuntos

  • Conjuntos, inclusión e igualdad.
  • Operaciones con conjuntos: Unión, intersección, complemento, diferencia, producto cartesiano.
  • Conjunto potencia.
  • Relaciones.
  • Composición de relaciones.
  • Relaciones de orden.
  • Diagramas de Hasse.
  • Funciones. Tipos de funciones.
  • Números naturales.
  • Axiomas de Peano y principio de inducción matemática.
  • Cardinalidad.
  • Conjuntos Q y R, alepho y potencia del continuo.
  • Prueba diagonal de Cantor.

Unidad 2: Principios básicos de la teoría combinatoria.

  • Correspondencia, suma y producto.
  • Arreglos, arreglos con repetición.
  • Permutaciones.
  • Permutaciones con repetición.
  • Combinaciones.
  • Combinaciones con repetición.
  • Coeficientes binomiales.
  • Interpretación combinatoria, algebraica y geométrica.
  • Triangulo aritmético.
  • Coeficientes multinomiales.
  • Interpretación geométrica.
  • Principios de inclusión y de exclusión.
  • Desarreglos. Números de Stirling de primera y segunda clase.
  • Números de Bell.
  • Triángulos de Stirling y de Bell.
  • Números armónicos.
  • Números de Fibonacci.
  • Funciones generatrices.
  • Aplicaciones: Análisis combinatorio de un algoritmo.
  • Relaciones de recurrencia.

Unidad 3: Estructuras algebráicas.

  • Grupos. Ejemplos: Zn, grupos de permutaciones. Subgrupos.
  • Homomorfismo.
  • Clases laterales.
  • Teorema de Lagrange.
  • Aplicaciones: Detección de errores usando grupos de códigos, teoría de Polya, lema de Burnside.

Unidad 4:Teoría de grafos.

  • Dígrafos. Isomorfismos. Dígrafos con peso. Grafos no dirigidos.
  • Problema de recorrido de aristas y de vértices.
  • Representación matricial de grafos.
  • Algoritmos: Dikjkstra y Warshall.
  • Árboles. Propiedades.
  • Árboles enraizados.
  • Algoritmos de recorrido: Pre-orden, orden y post-orden.
  • Árboles con peso.

Unidad 5:Funciones.

  • Tipos de funciones.
  • Derivadas.
  • Continuidad.
  • Máximos y mínimos de funciones de una variable.
  • Criterios de la primera y segunda derivada.
  • Derivadas parciales.
  • Máximos y mínimos de funciones de varias variables.
  • Derivada direccional y vector gradiente.
  • Criterio de la segunda derivada.

Metodología de la Enseñanza

Se realizarán exposiciones de clase teóricas por parte del profesor. Investigaciones bibliográficas. Asignación de trabajos. Exámenes escritos, etc.

Intensidad Horaria

La intensidad horaria es de 3 horas/semana durante 16 semanas (48 horas/semestre).

Bibliografía

  • Bernard colman y Busby Robert. Estructuras de matemáticas discretas para la computación. Prentice Hall. México. 1984.
  • Antón, Howard and Bernard Colman. Applied finite Mathematics, 3rd ed., Academic Press, Orlando, 1982.
  • Knuth, Donald E., The Art of Computer Programming, v. 1, 2nd ed., Addison-Wesley, Reading Mass., 1973.
  • Colman, Bernard, Introductory Linear Álgebra with Application, 3rd ed., Macmillan, New York, 1984.
  • Lipschutz, Seymour, Theory and Problems of set Theory and Related Topics, Schaum, New York, 1964.
  • Rader, Robert J., Advanced Software Design Techniques, Petrocelli, New York. 1968.
  • Stoll, Robert R., Set Theory and Logic, Freeman, New York, 1963.
  • Wand, Mitchell, Induction, Recursion, and Programming, North Holland, New York, 1980.