A modular calculus for the average cost of data structuring: efficiency-oriented programming in MOQA

The main time measure currently used for real-time languages (worst-case time) is well-known not to be modular in general, which makes average-case analysis notoriously difficult, involving a variety of techniques which typically do not allow for automation. This book introduces the first programming language for which average-case time analysis of its programs is guaranteed to be modular. The book includes sample programs and sample derivations of the average-case time of these programs to illustrate this radically different approach to average-case timing. The book presets a single foundation for Average-Case Analysis, based on the notion of Random Structure Preservation, and solves severalwell-known open problems discussed by Knuth. A novel foundation is provided for this classical area of computing. As opposed to a series of methods which need to match the algorithm under consideration, a new uniform foundation is provided which is semi-automatable and which provides a single approach to analyze all algorithms from a wide class INDICE: Bridging Semantics and Complexity. The MOQA Programming Language. Implications for Real-Time Languages and Automated Average-Case Analysis. Basic sorting Algorithms. Compositionality as a Key to Software Timing. Random Structures. Series-Parallel MOQA Data Structures. Examples of MOQA Programs. Compositional Determination of Average Time. Examples of Average-Case Analysis in MOQA.

• ISBN: 978-0-387-73383-8
• Editorial: Springer
• Encuadernacion: Cartoné
• Páginas: 250
• Fecha Publicación: 01/03/2008
• Nº Volúmenes: 1
• Idioma: Inglés