Catálogo de publicaciones - tesis
Título de Acceso Abierto
Un modelo de cómputo basado en ocultamiento de la información para cotas inferiores de complejidad en geometría algebraica efectiva
Andrés Avelino Rojas Paredes Joos Heintz
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
Para estudiar la complejidad intrínseca de un problema computacional siempre es posible dar y demostrar cotas inferiores de complejidad. Una cota inferior de complejidad es un teorema que establece la mínima complejidad que tiene cualquier algoritmo que intente resolver el problema que estamos considerando. Con esta definición, una cota posible es (1) que es una cota inferior trivial, cualquier algoritmo tarda al menos un paso. Lo difícil es obtener una cota inferior alta. Cuanto más alta es la cota inferior, es más difícil de demostrar, por ejemplo, aún es una pregunta abierta saber si existen o no cotas inferiores exponenciales para problemas en la clase de complejidad NP. En esta tesis se establece que la dificultad de encontrar tales cotas puede deberse a la naturaleza del modelo de cómputo utilizado que no debe ser general ni muy específico. Esta idea empezó con la noción de algoritmo programable (programmable algorithm) que distingue entre algoritmos en general y algoritmos producidos siguiendo una especificación (ver [HKRP13b]). De acuerdo con [Bor75], obtener una cota inferior de complejidad requiere la definición de dos ingredientes fundamentales: el modelo de cómputo que contiene los algoritmos que vamos a estudiar y una adecuada medida de complejidad computacional. Entonces, vamos a ser cuidadosos con la definición de estos ingredientes y vamos a definir un modelo de cómputo para algoritmos programables en el sentido de [HKRP13b]. En particular, en esta tesis introducimos un modelo de cómputo basado en conceptos de Ingeniería de Software. Esta característica permite demostrar cotas inferiores de complejidad no triviales para algoritmos de eliminación en geometría algebraica efectiva. Esta tesis esta basada en un proyecto de 20 años de investigación en complejidad algebraica y teoría del cálculo simbólico que fue iniciado en el trabajo J. Heintz, J. Morgenstern, On the Intrinsic Complexity of Elimination Theory, Journal of Complexity 9 471-498 (1993). El objetivo original del proyecto fue determinar la complejidad intrínseca de resolver sistemas de ecuaciones polinomiales (teoría de la eliminación), se quería demostrar su carácter de complejidad no polinomial. Este objetivo fue logrado en esencia en el trabajo J. Heintz, B. Kuijpers, A. Rojas Paredes, Software Engineering and Complexity in Effective Algebraic Geometry, Journal of Complexity 29 92-138 (2013), Journal of Complexity 2013 Best Paper Award, donde se fijó la estructura de datos que utilizaban los algoritmos de eliminación, esto se llamó modelo de circuitos (polinomios implementados en términos de circuitos aritméticos). Más tarde nos dimos cuenta de que el modelo de circuitos no era esencial y que nuestra argumentación también podía aplicarse a otras cuestiones de complejidad en el cálculo científico, por ejemplo, la interpolación polinomial (ver [GHMS11]). La observación principal fue que habíamos desarrollado en nuestro contexto un modelo matemático para ciertos aspectos de la Ingeniería de Software, en particular, habíamos desarrollado un modelo para el ocultamiento de la información y el requerimiento no funcional de la robustez, esto nos permitió sacar conclusiones sorprendentes sobre la complejidad de los algoritmos de eliminación, ver B. Bank, J. Heintz, G. Matera, J. L. Montaña, L. M. Pardo, A. Rojas Paredes, Quiz Games as a Model for Information Hiding, Journal of Complexity 34 1-29 (2016). Esta tesis describe un modelo de cómputo que se inspira en las nociones de ocultamiento de la información y requerimientos no funcionales, entre otros conceptos importantes en Ingeniería de Software como las nociones de abstracción y el diseño de software. Nuestro modelo de cómputo permite probar cotas inferiores de complejidad exponencial para los algoritmos de eliminación. Mostramos que cualquier implementación orientada a objetos (y robusta) de algoritmos de eliminación es necesariamente ineficiente. Este resultado muestra una sinergia existente entre Ingeniería del Software y Teoría de la Complejidad Algebraica.Palabras clave – provistas por el repositorio digital
TIPO ABSTRACTO DE DATOS; FUNCION DE ABSTRACCION; ALGORITMO DE ELIMINACION; INTERPOLACION; OCULTAMIENTO DE LA INFORMACION; COTA INFERIOR DE COMPLEJIDAD; REQUERIMIENTO NO-FUNCIONAL; ROBUSTEZ; DIAGRAMA DE CLASES; MODELO DE COMPUTO; PROGRAMACION ORIENTADA A OBJETOS; POLINOMIOS; DISEÑO DE SOFTWARE; ABSTRACT DATA TYPE; ABSTRACTION FUNCTION; ELIMINATION ALGORITHM; INTERPOLATION; INFORMATION HIDING; LOWER COMPLEXITY BOUND; NON-FUNCTIONAL REQUIREMENT; ROBUSTNESS; CLASS DIAGRAM; COMPUTATION MODEL; OBJECT-ORIENTED PROGRAMMING; POLYNOMIALS; SOFTWARE DESIGN
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 2018 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
2018-02-26
Información sobre licencias CC
