Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Recolector de Cienci...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
versions View all 4 versions
addClaim

Cotas asintóticas de coste

Authors: Alonso Blas, Diego Esteban;

Cotas asintóticas de coste

Abstract

La complejidad asintótica de un programa describe la escalabilidad de su coste de ejecución. Observa su comportamiento cuando procesa datos arbitrariamente grandes y considera semejantes dos programas cuyos costes crecen de manera similar. Existen algunos analizadores automáticos de coste que, cuando se emplean para procesar programas reales, generan funciones no asintóticas de coste demasiado complejas para su uso práctico. En este trabajo desarrollamos e implementamos un algoritmo capaz de simpli- ficar esas funciones a su forma asintótica, más compacta y manejable.Hemos integrado dicho algoritmo en un resolutor de ecuaciones, capaz de generar directamente funciones asintóticas sin necesidad de calcular las no asintóticas; lo que en nuestras pruebas experimentales ha resultado ser más eficaz. Ello permite mejorar la escalabilidad de los analizadores de coste, un aspecto crucial para su uso industrial. [ABSTRACT] Asymptotic complexity analysis is used for describing programs' excution cost scalability, by observing its behaviour when processing large input data and considering as equivalent two programs whose costs grow at the same rate. There are non-asymptotic cost analyzers which, when used over realistic programs, provide complex non-asymptotic cost functions that can't be used in some practical applications. That's why we have developed an algorithm that simplifies a cost function to its asymptotic form, more compact and manageable. We have integrated that algorithm into a cost analyzer, and now it generates asymptotic functions without having to firstly compute their non-asymptotic counterparts, a process that our experiments show to be more effcient. This allows us to improve cost analyzers' scalability, a concerning issue for its application in software industry.

Country
Spain
Related Organizations
Keywords

Lenguajes de Programación, 1203.23 Lenguajes de Programación, Java Bytecode, Análisis Automático de Complejidad, Abstract Interpretation, Asymptotic Complexity Order, Análisis Estático de Programas, Cost Analysis, Closed-Form Upper Bounds, Cotas Superiores en Forma Cerrada Interpretación Abstracta, Proof Carrying Code, Programación de ordenadores, Automatic Complexity Analysis, Código Byte de Java, Análisis de Coste, 510.52(043.3), Código con Certificados, Órdenes de Complejidad Asintótica, Static Program Analysis, Programación de ordenadores (Informática), Programming Languages

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Green