Selected Papers on Analysis of Algorithms

Donald E. Knuth

540 pages, parution le 01/01/2000

Ajouter à une liste

Indisponible

Résumé

Donald Knuth's influence in computer science ranges from the invention of methods for translating and defining programming languages to the creation of the TeX and METAFONT systems for desktop publishing. His award-winning textbooks have become classics often credited for shaping the field, while his widely referenced scientific papers stand as developmental milestones over a wide range of topics. The present volume, the fourth in a series of his collected works, is devoted to Analysis of Algorithms, an important subfield of computer science that Knuth founded in the 1960s and still considers his main life's work. A thriving international discipline, Analysis of Algorithms, is the unifying theme underlying Knuth's well known books The Art of Computer Programming.

More than thirty of the seminal papers that helped to shape this field are reprinted and updated in the present collection, together with historical material not previously published.

Contents

Mathematical Analysis of Algorithms
The Dangers of Computer Science Theory
The Analysis of Algorithms
Big Omicron and Big Omega and Big Theta
Optimal Measurement Points for Program Frequency Counts
Estimating the Efficiency of Backtrack Programs
Ordered Hash Tables
Activity in an Interleaved Memory
An Analysis of Alpha-Beta Pruning
Notes on Generalized Dedekind Sums
The Distribution of Continued Fraction Approximations
Evaluation of Porter's Constant
The Subtractive Algorithm for Greatest Common Divisors
Length of Strings for a Merge Sort
The Average Height of Planted Plane Trees
The Toilet Paper Problem
An Analysis of Optimum Caching
A Trivial Algorithm Whose Analysis Isn't
Deletions That Preserve Randomness
Analysis of a Simple Factorization Algorithm
The Expected Linearity of a Simple Equivalence Algorithm
Textbook Examples of Recursion
An Exact Analysis of Stable Allocation
Stable Husbands
Shellsort With Three Increments
The Average Time for Carry Propagation
Linear Probing and Graphs
A Terminological Proposal
Postscript About NP-Hard Problems
An Experiment in Optimal Sorting
Duality in Addition Chains
Complexity Results for Bandwidth Minimization
The Problem of Compatible Representatives
The Complexity of Nonuniform Random Number Generation

Index

L'auteur - Donald E. Knuth

Donald E. Knuth est professeur émérite à l'université de Stanford, membre de l'Académie des sciences des États-Unis, titulaire de la Médaille des sciences et du Prix Turing. Auteur d'une centaine de publications, notamment The Art of Computer Programming en trois volumes dont la section "Préliminaires mathématiques" a inspiré ce livre, il est également le créateur des systèmes TEX et Metafont auxquels il a déjà consacré cinq ouvrages.

Caractéristiques techniques

	PAPIER
Éditeur(s)	CSLI
Auteur(s)	Donald E. Knuth
Parution	01/01/2000
Nb. de pages	540
Format	15,2 x 22,9
Couverture	Broché
Poids	837g
Intérieur	Noir et Blanc
EAN13	9781575862125
ISBN13	978-1-57586-212-5