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 LEADER 04592nam 2200541 450 001 9910794042603321 005 20211105152038.0 010 $a0-8232-8779-3 024 7 $a10.1515/9780823287796 035 $a(CKB)4100000011286124 035 $a(MiAaPQ)EBC6220294 035 $a(DE-B1597)566200 035 $a(DE-B1597)9780823287796 035 $a(OCoLC)1154122262 035 $a(EXLCZ)994100000011286124 100 $a20201014d2020 uy 0 101 0 $aeng 135 $aurcnu|||||||| 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 00$aNoir affect /$fChristopher Breu, Elizabeth A. Hatmaker, editors 210 1$aNew York :$cFordham University Press,$d[2020] 210 4$d©2020 215 $a1 online resource (305 pages) 327 $tFront matter --$tContents --$tPreface --$tIntroduction: Dark Passages --$t1. Toward Alphaville: Noir, Midcentury Communication, and the Management of Affect --$t2. Public Violence as Private Pathology: Noir Affect in The End of a Primitive --$t3. Cold Kink: Race and Sex in the African American Underworld --$t4. Noir Pedagogy: The Problem of Student Masochism in the Classroom Economy --$t5. The Shadows of the Twilight World: Beebo Brinker and the Circulation of Affect --$t6. Peripheral Noir, Mediation, and Capitalism: Noir Form, Noir Mediascape, Sociological Noir --$t7. Cyborg Affect and the Power of the Posthuman in the Ghost in the Shell Franchise --$t8. Playing with Negativity: Max Payne, Neoliberal Collapse, and the Noir Video Game --$t9. Chick Noir: Surveilling Femininity and the Affects of Loss in Gone Girl --$t10. Surplus Feelings: Neoliberal Noir and the Affective Economy of Debt --$t11. Capitalism as Affective Atmosphere: The Noir Worlds of Massimo Carlotto --$tAfterword: Melodrama, Noir?s Kid Sister, or Crying in Trump?s America --$tList of Contributors --$tIndex 330 $aNoir Affect proposes a new understanding of noir as defined by negative affect. This new understanding emphasizes that noir is, first and foremost, an affective disposition rather than a specific cycle of films or novels associated with a given time period or national tradition. Instead, the essays in Noir Affect trace noir?s negativity as it manifests in different national contexts from the United States to Mexico, France, and Japan and in a range of different media, including films, novels, video games, and manga. The forms of affect associated with noir are resolutely negative: These are narratives centered on loss, sadness, rage, shame, guilt, regret, anxiety, humiliation, resentment, resistance, and refusal. Moreover, noir often asks us to identify with those on the losing end of cultural narratives, especially the criminal, the lost, the compromised, the haunted, the unlucky, the cast-aside, and the erotically ?perverse,? including those whose greatest erotic attachment is to death. Drawing on contemporary work in affect theory, while also re-orienting some of its core assumptions to address the resolutely negative affects narrated by noir, Noir Affect is invested in thinking through the material, bodily, social, and political?economic impact of the various forms noir affect takes. If much affect theory asks us to consider affect as a space of possibility and becoming, Noir Affect asks us to consider affect as also a site of repetition, dissolution, redundancy, unmaking, and decay. It also asks us to consider the way in which the affective dimensions of noir enable the staging of various forms of social antagonism, including those associated with racial, gendered, sexual, and economic inequality. Featuring an Afterword by the celebrated noir scholar Paula Rabinowitz and essays by an array of leading scholars, Noir Affect aims to fundamentally re-orient our understanding of noir.Contributors: Alexander Dunst, Sean Grattan, Peter Hitchcock, Justus Nieland, Andrew Pepper, Ignacio Sánchez Prado, Brian Rejack, Pamela Thoma, Kirin Wachter-Grene 606 $aFilm noir 610 $aAffect. 610 $aFilm Noir. 610 $aNegativity. 610 $aNeoliberalism. 610 $aNoir. 610 $aPopular Culture. 610 $aPsychoanalysis. 610 $aPulp literature. 610 $aVideo Games. 615 0$aFilm noir. 676 $a791.430909355 702 $aBreu$b Christopher 702 $aHatmaker$b Elizabeth A. 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910794042603321 996 $aNoir affect$93784290 997 $aUNINA