LEADER 00979nam0-22002891i-450 001 990005323010403321 005 20221202090841.0 035 $a000532301 035 $aFED01000532301 035 $a(Aleph)000532301FED01 035 $a000532301 100 $a19990530f---0---9km-y0itay50------ba 101 0 $aita 105 $aa-------00--- 200 1 $aRelazioni Artistiche fra l'Italia e la Polonia$fStanislaw Lorentz 210 $aRoma$cA.Signorelli$ds.d. 215 $a58 p.$cill.$d24 cm 225 1 $aAccademia polacca di Scienze e Lettere. Biblioteca di Roma. Conferenze$v15 300 $aConferenza tenuta nella Biblioteca di Roma dell'Accademia Polacca di Scienze e Lettere il 20 ottobre 1961 700 1$aLorentz,$bStanislaw$0207203 801 0$aIT$bUNINA$gRICA$2UNIMARC 901 $aBK 912 $a990005323010403321 952 $aARCH. BM Q 058$bS.I.$fFLFBC 959 $aFLFBC 996 $aRelazioni artistiche fra l'Italia e la Polonia$9260817 997 $aUNINA LEADER 05342nam 2200625Ia 450 001 996218074803316 005 20230607223649.0 010 $a1-283-30620-4 010 $a9786613306203 010 $a1-118-03277-2 010 $a1-118-03102-4 035 $a(CKB)2550000000056719 035 $a(EBL)694802 035 $a(OCoLC)778616739 035 $a(SSID)ssj0000613258 035 $a(PQKBManifestationID)11356282 035 $a(PQKBTitleCode)TC0000613258 035 $a(PQKBWorkID)10584723 035 $a(PQKB)11128645 035 $a(MiAaPQ)EBC694802 035 $a(EXLCZ)992550000000056719 100 $a20000519d2001 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aAverage case analysis of algorithms on sequences$b[electronic resource] /$fWojciech Szpankowski 210 $aNew York $cJohn Wiley$dc2001 215 $a1 online resource (580 p.) 225 1 $aWiley-Interscience series in discrete mathematics and optimization 300 $aDescription based upon print version of record. 311 $a0-471-24063-X 320 $aIncludes bibliographical references and index. 327 $aAverage 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 327 $a2.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 327 $a4.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 327 $a6 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 327 $a6.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 327 $a7.4 Probability Generating Functions 330 $aA 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 410 0$aWiley-Interscience series in discrete mathematics and optimization. 606 $aComputer algorithms 606 $aAlgorithms 615 0$aComputer algorithms. 615 0$aAlgorithms. 676 $a515.24 700 $aSzpankowski$b Wojciech$f1952-$0553750 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996218074803316 996 $aAverage case analysis of algorithms on sequences$9979053 997 $aUNISA