Notas de Clase#
Computación y Estructuras Discretas I Repositorio del curso.
El curso inicia con una introducción a la lógica formal, donde se abordan distintos métodos de demostración —tanto directos como indirectos—, y se introduce el uso de Coq, un asistente de pruebas formales, para reforzar el razonamiento matemático y la verificación automática de proposiciones.
A continuación, se desarrolla la teoría de conjuntos y funciones, abordando nociones fundamentales como la relación de pertenencia, operaciones entre conjuntos, tipos de funciones (inyectivas, sobreyectivas, biyectivas), funciones inversas y funciones especiales, así como las propiedades del álgebra de funciones.
En la siguiente unidad se estudian estructuras discretas no recursivas y el análisis de algoritmos, con énfasis en la complejidad temporal y espacial, la notación asintótica, y conceptos clave de diseño como generics, desacoplamiento y tipos abstractos de datos. También se exploran estructuras clásicas como tablas hash, pilas, colas, montículos y colas de prioridad.
La parte final del curso aborda las estructuras discretas recursivas, como los árboles N-arios, los árboles de búsqueda binaria y los árboles AVL, para luego introducir la teoría de grafos, incluyendo sus definiciones, representaciones, algoritmos de recorrido (BFS y DFS), cálculo de caminos mínimos y construcción de árboles de expansión mínima.
Estas notas están diseñadas como un recurso de apoyo para el estudio, reforzando tanto la teoría como su aplicación práctica en el contexto de la ingeniería y las ciencias de la computación.