Trabajo Fin de Grado
Complejidad computacional y álgebra de funciones
Autor/es | 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 de publicación | 2016-09 |
Fecha de depósito | 2016-09-29 |
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 ... 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 ... 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Romero González Alberto TFG.pdf | 555.0Kb | [PDF] | Ver/ | |