scientific article; zbMATH DE number 3473265
Der 3. Band [vgl. Bd. 1, Fundamental algorithms (1968; Zbl 0191.17903) und Bd. 2, Seminumerical algorithms (1969; Zbl 0191.18001)] enthält die Kapitel 5 (Sorting) und 6 (Searching) der geplanten 7-bändigen Monographie über die ``Kunst des Programmierens. Die stürmische Entwicklung gerade dieser Teilgebiete der Datenverarbeitung in den letzten Jahren verzögerte zwar das Erscheinen des Buches um fast 3 Jahre, führte aber zu einer erstaunlichen Vielfalt des aufgenommenen Stoffes. Der Verf. umreißt die behandelten Probleme durch die folgenden Fragen: Wie findet man gute Algorithmen? Wie können gegebene Algorithmen und Programme verbessert werden? Wie kann die Effektivität von Algorithmen mathematisch analysiert werden? Wie kann man rationall zwischen verschiedenen Algorithmen für das gleiche Problem wählen? In welchem Sinne können Algorithmen optimal sein? Wie können externe Speicher effektiv eingesetzt werden? Inhaltlich schließt sich der vorliegende Band an Kapitel 2 (Information Structures) des 1. Bandes an. Kap. 5 (Sorting) enthält neben einem Abschnitt über Permutationen und einen über optimales Sortieren die beiden Hauptabschnitte ``Internal Sorting und ``External Sorting. Kap. 6 (Searching) ist in folgende Abschnitte untergliedert: Sequential Searching, Searching by Comparison of Keys, Digital Searching, Hashing, Retrieval an Secondary Keys. Das Buch eignet sich sowohl als Grundlage für Vorlesungen unterschiedlichen Schwierigkeitsgrades (Abschritte vorwiegend mathematischen Inhalts sind durch * gekennzeichnet) als auch zum Selbststudium. Dazu sind die Übungsaufgaben sowohl nach den benötigten mathematischen Kenntnissen als auch nach ihrem Schwierigkeitsgrad sorgfältig klassifiziert. Auch dieser Band ist durch einen Anhang, in dem die in den vorangegangenen Bänden eingeführten Bezeichnungen erklärt werden, weitgehend unabhängig benutzbar.
- Young-Fibonacci insertion, tableauhedron and Kostka numbers
- Order statistics and estimating cardinalities of massive data sets
- Optimality in external memory hashing
- On embedding subclasses of height-balanced trees in hypercubes
- Optimal search for rationals
- Cuckoo hashing: Further analysis
- A new external sorting algorithm with no additional disk space
- Parallel merging with restriction
- On the uniform convergence of interpolating polynomials
- Restricted k-ary words and functional equations
- Bounding restricted rotation distance
- Embedding height balanced trees and Fibonacci trees in hypercubes
- The bandpass problem: Combinatorial optimization and library of problems
- A constant-time dynamic storage allocator for real-time systems
- On bijections for pattern-avoiding permutations
- A generalization of the 0-1 principle for sorting
- \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis
- On the average depth of asymmetric LC-tries
- Almost avoiding permutations
- Transposition of large rectangular matrices
- On a problem of Oppenheim concerning Factorisatio Numerorum
- Una struttura bidimensionale per la memorizzazione dei file trasposti
- The average height of planted plane trees with M leaves
- Optimal multiway search trees for variable size keys
- Minimal and almost minimal perfect hash function search with application to natural language lexicon design
- Approximate counting: a detailed analysis
- Purely top-down updating algorithms for stratified search trees
- Macro-operators: A weak method for learning
- Solution of two sequencing problems
- Lower bounds in algebraic computational complexity
- Complexity lower bounds for machine computing models
- The complexity of finding minimum-length generator sequences
- The average height of the second highest leaf of a planted plane tree
- A proof of Andrews' \(q\)-Dyson conjecture
- A backtracking method for constructing perfect hash functions from a set of mapping functions
- An ordered minimal perfect hashing scheme based upon Euler's theorem
- Optimal solutions for a class of point retrieval problems
- Geometry of a category of complexes and algebraic K-theory
- Significant improvements to the Ford-Johnson algorithm for sorting
- k-fold bitonic sort on a mesh-connected parallel computer
- Possibilistic search trees
- A Schensted algorithm for rim hook tableaux
- A direct combinatorial proof of a positivity result
- A bijective proof of Cassini's Fibonacci identity
- Join during merge: an improved sort based algorithm
- Binomial determinants, paths, and hook length formulae
- Weighted inversion numbers, restricted growth functions, and standard Young tableaux
- Database relations with null values
- The analysis of simple list structures
- General algorithms for the address calculation of lexicographically ordered tuples
- Universal retrieval trees
- Improved upper bounds on Shellsort
- Probabilistic counting algorithms for data base applications
- Finding extreme points in three dimensions and solving the post-office problem in the plane
- Topological transformations as a tool in the design of systolic networks
- Selection of the optimum uniform partition search
- New algorithms for the LCS problem
- Sequential access in splay trees takes linear time
- Low complexity k-dimensional centered forms
- Lattice path combinatorics and linear probing
- A bijective proof of the q-Saalschütz theorem
- Asymptotics of maximal and typical dimensions of irreducible representations of a symmetric group
- Interpolation by a sum of exponential functions when some exponents are preassigned
- Binary trees and uniform distribution of traffic cutback
- An asymptotically exact polynomial algorithm for equipartition problems
- Recurrence relations based on minimization and maximization
- More on the complexity of slice functions
- Average and worst-case analysis of heuristics for the maximum tardiness problem
- On growing a random Young tableau
- Rectilinear planar layouts and bipolar orientations of planar graphs
- A taxonomy of binary tree traversals
- Characterization of partial 3-trees in terms of three structures
- The pairing heap: A new form of self-adjusting heap
- The complexity of hashing with lazy deletion
- Rational equivalence relations
- Computing short generator sequences
- Random sequential bisection and its associated binary tree
- Edge-skeletons in arrangements with applications
- Binary search networks: A new method for key searching
- Effect of data organization in a system of interleaved memories on the performance of parallel search
- Asymptotic equivalence between frequentist and Bayesian prediction limits for the Poisson distribution
- Divisor generating functions and insertion into a heap
- Polygonizations of point sets in the plane
- Automatic evaluation of derivatives
- Strong linear independence in bottleneck algebra
- Array processing machines: an abstract model
- Bijections related to statistics on words
- Visibility between two edges of a simple polygon
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Distributed sorting algorithms for multi-channel broadcast networks
- Computing on a free tree via complexity-preserving mappings
- On determining the on-line minimax linear fit to a discrete point set in the plane
- Information compression and Varshamov-Gilbert bound
- Optimal parallel algorithms for constructing and maintaining a balanced m-way search tree
- Fractional cascading. II: Applications
- A function for evaluating the computing time of a bubbling system
- Optimal worst case trees
- A q-Foata proof of the q-Saalschütz identity
- River routing in VLSI
- Tridiagonal factorizations of Fourier matrices and applications to parallel computations of discrete Fourier transforms
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4057549)