Download prog_matematica_discreta

Educación Tecnológica Superior!
Programa de Tecnólogo en Desarrollo de Aplicaciones y
Hardware y Administración de Redes
Asignatura: Matemática Discreta
Código:
Créditos: 4
Horas Teóricas:
Horas Prácticas:
Requisitos: Matemáticas II
Requisito de:
Cuatrimestre : III
- No tiene
OBJETIVOS:
Enseñar al estudiante las propiedades de las estructuras matemáticas discretas más usadas en
computación de tal forma que conozca las bases teóricas necesarias para:
a) Entender y utilizar de manera apropiada las estructuras de datos y los algoritmos empleados para la
solución de problemas específicos en las diferentes áreas de su carrera.
b) Utilizar un enfoque de sistemas en la construcción de modelos matemáticos para la solución a
problemas.
c) Comprender y especificar el desarrollo de nuevas aplicaciones informáticas.
Enseñar al estudiante las nociones básicas de álgebra lineal utilizadas en el estudio de algoritmos para la
solución de problemas en campos como la geometría computacional y computación gráfica.
METODOLOGIA:
Los temas correspondientes al curso, serán desarrollados por el profesor en el aula. Además para ampliar lo
expuesto en clase se asignarán prácticas para realización fuera del aula.
La evaluación se realizará tomando en cuenta la presentación de las tareas asignadas y pruebas de
evaluación de desempeño.
EVALUACIÓN:
2 Exámenes de 25 puntos cada uno.
1 Examen final de 30 puntos
Trabajos prácticos 20 puntos.
BIBLIOGRAFIA:
Matemática para el procesamiento de datos: por W. Prices (CECSA)
Matemática para computación por S. Lipschutz (Mcgraw-Hill)
Matemática Discreta por : R.Miller (Renthort Book Company)
Matemática y Computación por: W.Doris (limusa)
Matemática y Finita por : S Lipschutz (Mcgraw-Hill)
Matemática Discreta por Jame Fisher
Estructura de Matemática para la Computación: por Bernardo Kolmaa y Robert C. Busby
1
CONTENIDOS:
1. Lenguajes formales, Recursividad e Inducción.
1.1 Sucesiones definidas en forma recursiva.
1.2 Conjuntos definidos en forma recursiva.
1.3 Cadenas y lenguajes formales, definición recursiva de lenguajes formales.
1.4 Inducción matemática.
1.5 Demostraciones por recursividad.
2. Relaciones.
2.1 Relaciones y predicados en dos variables.
2.2 Relaciones recursivas.
2.3 Operaciones de relaciones.
2.4 Propiedades de las relaciones.
2.5 Cerradura de relaciones.
2.6 Relación de equivalencia y particiones. Aplicaciones.
3. Matriz de una relación.
3.1 Matrices booleanas y representación matricial de una relación.
3.2 Operaciones de matrices booleanas y operaciones de relaciones.
4. Grafos dirigidos.
4.1 Grafos dirigidos y propiedades de las relaciones.
4.2 Caminos en grafos dirigidos y composición de relaciones.
4.3 Cerradura transitiva y algoritmo de Warshall. Aplicaciones.
4.4 Grafos dirigidos con peso. Aplicaciones.
4.5 Algoritmos para la búsqueda de caminos mínimos en grafos dirigidos con peso.
4.6 Redes de transporte. Aplicaciones.
4.7 Algoritmo para el flujo máximo.
5. Árboles.
5.1 Conceptos básicos.
5.2 Propiedad de los árboles.
5.3 Árboles de expansión.
5.4 Algoritmos para hallar árboles de expansión.
5.5 Árboles de expansión mínimos. Aplicaciones.
5.6 Algoritmos para hallar árboles de expansión mínimos.
6. Multigrafos.
6.1 Conceptos básicos.
6.2 Caminos y circuitos de Euler. Aplicaciones.
6.3 Algoritmos para encontrar caminos y circuitos de Euler.
6.4 Caminos y circuitos hamiltonianos. Aplicaciones.
6.5 Algoritmos para encontrar caminos y circuitos hamiltonianos.
6.6 Coloración de grafos. Aplicaciones.
6.7 Algoritmos para coloración de grafos.
7. Relaciones y estructuras de orden.
7.1 Conjuntos parcialmente ordenados.
7.2 Ordenación lexicográfica en un lenguaje formal.
7.3 Elementos minimales y maximales.
7.4 Ordenación topológica. Aplicaciones.
8. Álgebra Booleana.
8.1 Definición y ejemplos.
8.2 Funciones booleanas, expresiones booleanas.
8.3 Representación y minimización de funciones booleanas.
2
9. Gramáticas y máquinas de estado finito.
9.1 Gramáticas formales. Conceptos básicos.
9.2 Tipos de gramáticas.
9.3 Lenguaje generado por una gramática.
9.4 Máquinas de estado finito. Propiedades.
9.5 Máquinas equivalentes.
9.6 Gramáticas, lenguajes y máquinas: reconocimiento de lenguajes.
3