Título: Matemática computacional
Profesor: Dra.C. Leticia Arco García
Correo: leticiaa@uclv.edu.cu
Fecha: 23/01/2017 al 27/01/2017
Créditos y código: 3, 02030034
Contenido: Álgebra de conjunto, relaciones y funciones. Lógica matemática: cálculo proposicional y de predicado. Teoría de grafos. Tipos especiales de grafos. Isomorfismo de grafos. Número cromático de un grafo. Teoremas asociados a la k-coloración de los vértices de un grafo. Grafos Planares. Emparejamientos. Definición de dígrafo y su terminología propia. Redes complejas y sus propiedades. Lenguajes. El problema de las palabras. Gramáticas regulares y autómatas finitos. Completitud y determinismo en tales autómatas. Gramáticas y lenguajes libres de contexto. Autómatas de pila. Máquinas de Turing.
Complejidad Algorítmica. Problemas y Algoritmos. Concepto de cotas mínimas de complejidad de problemas y las herramientas para su determinación. Técnicas de diseño de algoritmos. Enfoque del diseño de acuerdo a las diferentes técnicas. Algoritmos exhaustivos y heurísticos (deterministas y probabilistas). Calculabilidad. Complejidad espacial y temporal de cálculos y algoritmos. NP-completitud. Problemas decidibles y no decidibles, tratables e intratables. Clases de problemas. Transformación polinomial de problemas. Problema de la satisfacibilidad. Otros problemas NP-completos. Problemas NP-duros.
