Эта своевременная книга посвящена теме, которая вызвала всплеск интереса за последнее десятилетие, отчасти благодаря нескольким новым применениям, наиболее заметным из которых являются сжатие данных и вычислительная молекулярная биология. В ней описываются методы, используемые при анализе алгоритмов в среднем случае, объединяя в одном томе как аналитические, так и вероятностные инструменты. Инструменты иллюстрируются на примерах задач на словах с приложениями к молекулярной биологии, сжатию данных, безопасности и поиску шаблонов. Книга включает главы об алгоритмах и структурах данных на словах, вероятностных и аналитических моделях, принципах включения-исключения, методах первого и второго моментов, подаддитивной эргодической теореме и больших отклонениях, элементах теории информации, генерирующих функциях, сложных асимптотических методах, преобразовании Меллина и его приложениях, а также об аналитической пуассонизации и депуассонизации. Написана опытным исследователем с сильной международной репутацией в этой области.
This timely book examines an important topic with growing applications in recent decades, ranging from data compression to computational molecular biology and beyond. Part analytical, part probabilistic, it describes the methods of average case analysis applied to algorithms - presenting the necessary analytical and probabilical tools in one volume.Tools are illustrated via word-based applications with connections to molecular biology, data compres- sion, information security, as well as pattern matching.Chapters present algorithms and data-structuring, probabilistc-and-analytical modeling, in- clusion- exclusional principles, mean- and variance methods, contingency table calculus for small contingents, the moment-generating function and its applications to limits, elements of infor- mation theory, succession functions and generating equations/functions, complex asympto- tic methods, such as the Mellin transfer and developing a transfer for Mellin's method.This text is by an author of acknowledged standing, who also has a broad international repertoire in the domain. Average case analysis and its relevance to algorithmics has been in continuous development since its inception, and the material and scholarly impact of this book are profound.
Электронная Книга «Average Case Analysis of Algorithms on Sequences» написана автором Группа авторов в году.
Минимальный возраст читателя: 0
Язык: Английский
ISBN: 9781118031025
Описание книги от Группа авторов
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-exclusion principles, first and second moment methods, subadditive ergodic theorem and large deviations, elements of information theory, generating functions, complex asymptotic methods, Mellin transform and its applications, and analytic poissonization and depoissonization. * Written by an established researcher with a strong international reputation in the field.
