Tesis:
Termination and cost analysis:complexity and precision issues.
- Autor: MASUD, Abu Naser
- Título: Termination and cost analysis:complexity and precision issues.
- Fecha: 2013
- Materia: Sin materia definida
- Escuela: FACULTAD DE INFORMATICA
- Departamentos: LENGUAJES Y SISTEMAS INFORMATICOS E INGENIERIA DE SOFTWARE
- Acceso electrónico: http://oa.upm.es/14944/
- Director/a 1º: PUEBLA SANCHEZ, Álvaro Germán
- Director/a 2º: GENAIM, Samir
- Resumen: La investigaciones llevadas a cabo en esta tesis se centran en el análisis estático de coste y el análisis de terminación. Mientras que el objetivo del análisis de coste es estimar la cantidad de recursos consumida por un programa durante su ejecución, el análisis de terminación se centra en garantizar que la ejecución de un programa terminará en un tiempo finito. Sin embargo, ambos análisis se encuentran estrechamente relacionados, de hecho, muchas de las técnicas utilizadas para el análisis de coste se basan en técnicas desarrolladas inicialmente para el análisis de terminación. La precisión, la escalabilidad y la aplicabilidad son aspectos clave para cualquier análisis estático: un aumento de precisión mejora la calidad de la información inferida por el análisis; la escalabilidad del mismo hace referencia a la capacidad de analizar programas de mayor tamaño; y la aplicabilidad a la clase de programas que se pueden analizar satisfactoriamente (independientemente de la precisión y escalabilidad). Esta tesis aborda todos estos aspectos en el contexto del análisis de coste y de terminación, haciéndolo tanto desde una perspectiva teórica como práctica. Con respecto al análisis de coste, esta tesis aborda el problema de, dado un sistema de relaciones de coste (una forma de relaciones de recurrencia), resolver estas relaciones y expresarlas en forma de funciones de coste en forma cerrada, permitiendo establecer tanto las cotas superiores como inferiores del consumo de recursos del programa. Este problema es crucial para la mayoría de los analizadores de coste modernos, y en él radican muchas de las limitaciones de precisión y aplicabilidad de los análisis. En esta tesis se desarrollan y detallan los fundamentos teóricos de nuevas técnicas para la resolución de relaciones de coste, venciéndose las limitaciones de trabajos anteriores, y resultando en un aumento tanto de la precisión obtenida, como en una mejora en la escalabilidad de los análisis. Una característica única de las técnicas descritas en esta tesis es la de poder inferir tanto cotas superiores como cotas inferiores, solo con invertir las nociones correspondientes en la teoría subyacente. En lo que respecta al análisis de terminación, nuestro trabajo se centra en el estudio de la dificultad de decidir sobre la terminación de cierto tipo de bucles sencillos que aparecen en el contexto del análisis de coste. Este estudio nos ayuda a esclarecer los límites teóricos de la aplicabilidad y de la precisión tanto de los análisis de coste como de los análisis de terminación.