Michel Schellekens

A Modular Calculus for the Average Cost of Data Structuring (eBook, PDF)

• Format: PDF

Produktbeschreibung

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 several well-known open problems discussed by Knuth.

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: Springer US
• Seitenzahl: 245
• Erscheinungstermin: 17. Juni 2008
• Englisch
• ISBN-13: 9780387733845
• Artikelnr.: 37286133

Autorenporträt

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 several well-known open problems discussed by Knuth.

Inhaltsangabe

Introductory Notions.- Compositionality.- Random Bag Preservation and Isolated Subsets.- Basic MOQA Operations.- Average-Case Time of Basic MOQA Operations.- The MOQA Language.- Examples of MOQA Programs.- Average-Case Analysis of MOQA programs.- Distri-Track Joint with D. Hickey and M. Boubekeur.- Conclusion and FutureWork.