Ciencias de la Computación (plan 2013) 2025-1

Primer Semestre, Estructuras Discretas

Temario

I Introducción
I.1 ¿Qué son las estructuras discretas?
I.2 Panorama de las matemáticas discretas.
I.3 Introducción a los lenguajes formales: expresiones y mecanismos para su descripción (gramáticas y árboles de derivación).

II Inducción y recursión
II.1 Los números naturales: axiomas de Peano, principios de inducción.
II.2 Definiciones recursivas: definición de conjuntos y funciones mediante uso de patrones, ejemplos con estructuras de datos no numéricas.
II.3 Inducción estructural: principios de inducción estructural, dualidad entre inducción y recursión, ejemplos de demostración en diversas estructuras.

III Lógica matemática
III.1 Lógica proposicional: sintaxis, semántica, equivalencia lógica, análisis de argumentos correctos.
III.2 Aplicaciones a circuitos digitales. Componentes básicos. Minimización de funciones booleanas. Contadores. Multiplexores.
III.3 Introducción a la lógica de predicados: sintaxis, especificación formal, semántica informal en micromundos.

IV Relaciones
IV.1 Definiciones básicas, relaciones binarias y n-arias, aplicaciones.
IV.2 Relaciones binarias: propiedades, representación mediante matrices y digráficas.
IV.3 Operaciones con relaciones binarias: operaciones conjuntistas, composición, cerraduras (algoritmo de Warshall).
IV.4 Relaciones de orden: órdenes parciales y lineales, ordenación topológica, elementos minimales y maximales, retículas.

Bibliografía