Ebook: Методы и алгоритмы вычислений на строках

Книга представляет собой фундаментальное введение в алгоритмы и методы, эффективно вычисляющие паттерны в строковых последовательностях. Речь идет об общих алгоритмах и методах, которые находят применение во многих областях науки и информационных технологий: сжатие данных, криптография, распознавание речи и компьютерное зрение, вычислительная геометрия и молекулярная биология.
Рассмотренные в книге алгоритмы предназначены для нахождения в строковых последовательностях определенных типов паттернов — частных, характеристических и внутренних. Каждому типу паттернов посвящена соответствующая часть книги.
Книга отличается последовательным изложением материала, большим количеством иллюстративных примеров, свободным обсуждением текущих исследований в этой области, содержит более 500 упражнений, поясняющих и расширяющих материал, изложенный в тексте книги.
Книга предназначена для тех, кто имеет достаточную подготовку в математике и информатике и хочет познакомиться с этой интересной и важной областью.

---

Книга представляет собой фундаментальное введение в алгоритмы и методы, эффективно вычисляющие паттерны в строковых последовательностях. Речь идет об общих алгоритмах и методах, которые находят применение во многих областях науки и информационных технологий: сжатие данных, криптография, распознавание речи и компьютерное зрение, вычислительная геометрия и молекулярная биология. Рассмотренные в книге алгоритмы предназначены для нахождения в строковых последовательностях определенных типов паттернов — частных, характеристических и внутренних. Каждому типу паттернов посвящена соответствующая часть книги. Книга отличается последовательным изложением материала, большим количеством иллюстративных примеров, свободным обсуждением текущих исследований в этой области, содержит более 500 упражнений, поясняющих и расширяющих материал, изложенный в тексте книги. Книга предназначена для тех, кто имеет достаточную подготовку в математике и информатике и хочет познакомиться с этой интересной и важной областью. Оглавление:Предисловие 10 Часть I. Строковые последовательности и алгоритмы 17 Глава 1. Свойства строковых последовательностей 19 Глава 2. Паттерны? Что такое паттерны? 56 Глава 3. Такие разные строки 85 Глава 4. Строковые алгоритмы и тестовые данные 113 Часть II. Вычисление внутренних паттернов 137 Глава 5. Деревья для строковых последовательностей 139 Глава 6. Декомпозиция строковых последовательностей 191 Часть III. Вычисление частных паттернов 215 Глава 7. Базовые алгоритмы 217 Глава 8. Наследники Бойера-Мура 245 Глава 9. Алгоритмы вычисления расстояния между строками 278 Глава 10. Приближенное сравнение с паттерном 309 Глава 11. Регулярные выражения и множественные паттерны 343 Часть IV. Вычисление характеристических паттернов 381 Глава 12. Периодичность 383 Глава 13. Обобщение периодичности 417 Литература 467 Предметный указатель 483