RT info:eu-repo/semantics/bachelorThesis
T1 Introducción a la Teoría de la Complejidad Computacional
A1 Morán Cañón, Mario
A2 Universidad de Valladolid. Facultad de Ciencias
K1 [Pendiente de asignar]
AB Esre Trabajo de Fin de Grado consiste en una introducción a la Teoría de la Complejidad Computacional de Tiempo, para lo cual se comienza definiendo la máquina de Turing como modelo computacional básico, antes de adentrarnos en las diferentes clases de complejidad tanto deterministas como indeterministas, haciendo una revisión más profunda de las clases P y NP como protagonistas de esta área. Se estudian las reducciones, herramientas fundamentales en el manejo de las clases de complejidad, y la NP-completitud como consecuencia directa de lo anterior. Como colofón, se termina con un capítulo dedicado en exclusiva la famosa Conjetura de Cook, uno de los problemas del milenio. Debido a su utilidad como referencia inicial en Complejidad Computacional, la selección de resultados y demostraciones pretende además familiarizar al lector con las técnicas propias de esta rama de las Matemáticas.
YR 2016
FD 2016
LK http://uvadoc.uva.es/handle/10324/19054
UL http://uvadoc.uva.es/handle/10324/19054
LA spa
DS UVaDOC
RD 24-nov-2024