Record Nr.

UNINA9910139571403321

Autore

Szpankowski Wojciech <1952->

Titolo

Average case analysis of algorithms on sequences [[electronic resource] /] / Wojciech Szpankowski

Pubbl/distr/stampa


New York, : John Wiley, c2001

ISBN

1-283-30620-4

9786613306203

1-118-03277-2

1-118-03102-4

Descrizione fisica

1 online resource (580 p.)

Collana

Wiley-Interscience series in discrete mathematics and optimization

Disciplina

515.24

Soggetti

Computer algorithms

Algorithms

Electronic books.

Lingua di pubblicazione

Inglese

Formato

Materiale a stampa

Livello bibliografico

Monografia

Note generali

Description based upon print version of record.

Nota di bibliografia

Includes bibliographical references and index.

Nota di contenuto

Average Case Analysis of Algorithms on Sequences; Contents; Forword; Preface; Acknowledgments; PART I PROBLEMS ON WORDS; 1 Data Structures and Algorithms on Words; 1.1 Digital Trees; 1.2 Data Compression: Lempel-Ziv Algorithms; 1.2.1 Lempel-Ziv'77 Algorithm; 1.2.2 Lempel-Ziv'78 Algorithm; 1.2.3 Extensions of Lempel-Ziv Schemes; 1.3 Pattern Matching; 1.4 Shortest Common Superstring; 1.5 String Editing Problem; 1.6 Optimization Problems; 1.7 Exercises; 2 Probabilistic and Analytical Models; 2.1 Probabilistic Models of Strings; 2.2 Review of Probability; 2.2.1 Some Useful Inequalities

2.2.2 Types of Stochastic Convergence2.3 Review of Complex Analysis; 2.4 Special Functions; 2.4.1 Euler's Gamma Function; 2.4.2 Riemann's Zeta Function; 2.5 Extensions and Exercises; PART II PROBABILISTIC AND COMBINATORIAL TECHNIQUES; 3 Inclusion-Exclusion Principle; 3.1 Probabilistic Inclusion-Exclusion Principle; 3.2 Combinatorial Inclusion-Exclusion Principle; 3.3 Applications; 3.3.1 Depth in a Trie; 3.3.2 Order Statistics; 3.3.3 Longest Aligned Word; 3.4 Extensions and Exercises; 4 The First and Second Moment Methods; 4.1 The Methods; 4.2 Applications

4.2.1 Markov Approximation of a Stationary Distribution4.2.2 Excursion into Number Theory; 4.2.3 Height in Tries; 4.2.4 Height in PATRICIA Tries; 4.2.5 Height in Digital Search Trees; 4.2.6 Height in a Suffix Tree; 4.3 Extensions and Exercises; 5 Subadditive Ergodic Theorem and Large Deviations; 5.1 Subadditive Sequence; 5.2 Subadditive Ergodic Theorem; 5.3 Martingales and Azuma's Inequality; 5.4 Large Deviations; 5.5 Applications; 5.5.1 Edit Distance; 5.5.2 Knuth-Morris-Pratt Pattern Matching Algorithms; 5.5.3 Large Deviations of a Random Sequence; 5.6 Extensions and Exercises

6 Elements of Information Theory6.1 Entropy, Relative Entropy, and Mutual Information; 6.2 Entropy Rate and Rényi's Entropy Rates; 6.2.1 The Shannon-McMillan-Breiman Theorem; 6.2.2 Rényi's Entropy Rates; 6.3 Asymptotic Equipartition Property; 6.3.1 Typical Sequences; 6.3.2 Jointly Typical Sequences; 6.3.3 AEP for Biased Distributions; 6.3.4 Lossy Generalizations of AEP; 6.4 Three Theorems of Shannon; 6.4.1 Source Coding Theorem; 6.4.2 Channel Coding Theorem; 6.4.3 Rate Distortion Theorem; 6.5 Applications; 6.5.1 Phrase Length in the Lempel-Ziv Scheme and Depth in a Suffix Tree

6.5.2 Shortest Common Superstring Problem6.5.3 Fixed-Database Lossy Lempel-Ziv Algorithm; 6.6 Extensions and Exercises; PART III ANALYTIC TECHNIQUES; 7 Generating Functions; 7.1 Ordinary Generating Functions; 7.1.1 Formal Power Series; 7.1.2 Combinatorial Calculus; 7.1.3 Elements of Analytic Theory; 7.1.4 Generating Functions Over an Arithmetic Progression; 7.2 Exponential Generating Functions; 7.2.1 Elementary Properties; 7.2.2 Labeled Combinatorial Structures; 7.3 Cauchy, Lagrange and Borel Formulas; 7.3.1 Cauchy Coefficient Formula; 7.3.2 Lagrange Inversion Formula; 7.3.3 Borei Transform

7.4 Probability Generating Functions

Sommario/riassunto

A timely book on a topic that has witnessed a surge of interest over the last decade, owing in part to several novel applications, most notably in data compression and computational molecular biology. It describes methods employed in average case analysis of algorithms, combining both analytical and probabilistic tools in a single volume.* Tools are illustrated through problems on words with applications to molecular biology, data compression, security, and pattern matching.* Includes chapters on algorithms and data structures on words, probabilistic and analytical models, inclusion-ex

Record Nr.

UNINA9910817078903321

Autore

Morton James

Titolo

Gangland Oz : yesterday, today and tomorrow / / James Morton and Susanna Lobez

Pubbl/distr/stampa


Carlton, Victorias : , : Victory Books, , 2017

ISBN

0-522-86864-9

Descrizione fisica

1 online resource (257 pages)