Repositorio de producción científica de la Universidad de Sevilla

Complejidad computacional y álgebra de funciones

Opened Access Complejidad computacional y álgebra de funciones
Estadísticas
Icon
Exportar a
Autor: Romero González, Alberto
Director: Lara Martín, Francisco Félix
Departamento: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Fecha: 2016-09
Tipo de documento: Trabajo Fin de Grado
Titulación: Universidad de Sevilla. Grado en Matemáticas
Resumen: Usually, computational complexity classes are given explicitly using computation models and certain restrictions on available resources (time and/or space). However, in many cases, it is possible to obtain alternative descriptions of these classes as algebras of functions. In this work, some results of this type are presented. Logarithmic and lineal time hierarchies are characterized by functions algebras. We also present some functions algebras for polynomial time, logarithmic space and linear space complexity classes. Las clases de complejidad computacional suelen darse de manera explícita mediante modelos de computación y ciertas restricciones sobre los recursos disponibles (normalmente tiempo y/o espacio). Sin embargo, en muchos casos, es posible obtener descripciones alternativas de dichas clases como álgebras de funciones. En este trabajo se presentan algunos resultados de este tipo, caracterizando mediante álgebras de funciones las jerarquías de tiempo logarítmico y tiempo lineal, y las clases de complejidad de tiempo polinomial, espacio logarítmico y espacio lineal.
Cita: Romero González, A. (2016). Complejidad computacional y álgebra de funciones. (Trabajo fin de grado inédito). Universidad de Sevilla, Sevilla.
Tamaño: 555.0Kb
Formato: PDF

URI: http://hdl.handle.net/11441/46279

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones