A. Programa de Matemática Discreta y Lógica 1
- Datos de la Actividad
- Curricular Nombre: Matemática Discreta y Lógica 1
- Área de formación: Matemática
- Créditos: 6
2. Objetivo
- Reconocer la importancia de la modelización y abstracción en sistemas informáticos.
- Identificar y aplicar los conceptos de conjunto, relación, función y secuencia, y reconocer su relevancia como herramientas de modelización en computación.
- Reconocer, interpretar y aplicar diferentes tipos de pruebas matemáticas.
- Identificar, interpretar y aplicar las ideas de conjunto inductivo, prueba por inducción (estructural) y función recursiva.
- Reconocer y aplicar Máquina de Estados como herramienta de modelización para el análisis de procesos.
- Aplicar definiciones y resultados básicos de combinatoria y teoría de grafos.
- Utilizar las técnicas de la matemática discreta para abordar problemas de conteo, numeración y combinación.
- Reconocer las nociones de conjuntos numerables y no numerables y su importancia en el contexto de la computación.
El objetivo de esta actividad curricular es que el estudiante comprenda algunos conceptos básicos utilizados en informática para representar elementos de la realidad, pueda razonar y definir funciones sobre éstos. Asimismo, que el estudiante sepa utilizar elementos relevantes de matemática discreta y de lógica matemática, a nivel conceptual.
3. Metodología de enseñanza
- Horas clase (práctico y laboratorio): 30
- Horas evaluación: 6
- Horas estudio: 24
- Total de horas de dedicación del estudiante: 90
- Horas clase (teórico): 30
4. Temario
Nociones sobre pruebas
Nociones de implicación, equivalencia, recíproco, inverso, contrarecíproco, negación y contradicción
Estructura de una prueba matemática
Pruebas directas, por contraejemplo y por absurdo
Tipos de datos matemáticos
Conjuntos y secuencias
Funciones y relaciones binarias
Definiciones inductivas y recursivas
Definición de conjuntos (lenguajes) inductivos
Pruebas por inducción estructural
Funciones recursivas
Máquinas de estado
Estados y transiciones
Análisis de corrección de algoritmos a través de máquinas de estados
Grafos dirigidos y órdenes parciales
Grados de vértice, caminos
matrices de adyacencia, conteo de caminos
grafos acíclicos dirigidos, ordenamiento topológico
Grafos simples
Adyacencia y grados de vértice
Grafos bipartitos y emparejamientos
Caminos, ciclos y conectividad
Bosques y árboles
Combinatoria
Nociones básicas
Progresiones, permutaciones y combinaciones
Resolución de relaciones de recurrencia
5. Bibliografia básica
1. E. Lehman, F. Thomson Leighton, A. R. Meyer: Mathematics for Computer Science, (2017).
Tema | Básica | Complementaria |
Nociones sobre pruebas | (1) | (1) |
Tipos de datos matemáticos | (1) | (1) |
Tipos de datos recursivos | (1) | (1) |
Máquinas de estado | (1) | (1) |
Grafos dirigidos y órdenes parciales | (1) | (1,2) |
Grafos simples | (1) | (1,2) |
Combinatoria | (1) | (1,2) |
6. Bibliografia complementaria
R. Grimaldi: Matemática discreta y combinatoria: Una introducción con aplicaciones, Addison-Wesley World Student Series, 3rd. Edition, (1998).
F. Moller, G. Struth: Modelling Computing Systems: Mathematics for Computer Science, (2013).