De programas abstractos a cotas asintóticas precisas en forma cerrada

Abstract

El análisis de coste (o de consumo de recursos) estudia cómo determinar estáticamente cuántos recursos se requireren para ejecutar un programa, donde por recursos se entiende cualquier medida cuantitativa del programa, como el consumo de memoria o pasos de ejecución. Existen varios métodos de análisis de coste que, aunque difieren su teoría básica, normalmente dan el coste de unprograma como una función de cota superior en forma cerrada. También se ha estudiado, aunque menos, cómo inferir funciones de cota inferior.Las propiedades importantes de un analizador de coste son su aplicabilidad, su precisión, y su escalabilidad. Éstas a veces son antagónicas, por lo que para lograr buena escalabilidad se suele sacrificar la precisión, y por ello un analizador de coste puede destacar en una propiedad pero no en la otra. En esta tesis exploramos la distancia entre los enfoques existentes de análisis de coste, para desarrollar técnicas que puedan inferir cotas asintóticamente precisas, a la vez que tengan una buena escalabilidad y aplicabilidad.Nuestro punto de partida es el enfoque clásico al análisis de coste, el cual es ampliamente aplicable, escalable, y en la práctica tiene una buena precisión. Sin embargo, para algunos programas infiere cotas que son asintóticamente menos precisas que las que infieren otros enfoques. En este enfoque, el flujo de trabajo se divide en varias fases: (I) se transforma el programa de entrada en un programa abstracto, reemplazando las estructuras de datos por una noción de tamaño; ( II ) se transforma el programa abstracto en un conjunto de ecuaciones recursivas, que describen el coste del programa en función de los datos de entrada; y ( III ) se resuelven estas ecuaciones a cotas en forma cerrada.Nuestras contribuciones se hallan en los pasos II y III , y consisten en análisis, transformaciones, y técnicas de resolución que permiten ir De Programas Abstractos a Cotas Asintóticas Precisas en Forma Cerrada. Creemos que éstas resuelven la diferencia de precisión con respecto a otros enfoques, en particular con el de análisis amortizado, manteniendo una buena aplicabilidad y escalabilidad. Además, nuestras contribuciones aportan una innovación metodológica, que es aplicar el Cálculo de la Computación al análisis de coste.Palabras Clave: Análisis Estático. Análisis de Coste. Análisis Automático de Complejidad. Cotas en Forma Cerrada.