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

Купить бумажную книгу и читать

Автор: Билл Смит

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

Издательство: И.Д. Вильямс

Год: 2006

Формат: djvu / rar

Размер: 6.07 MB

Для сайта:

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

Рассмотренные в книге алгоритмы предназначены для нахождения в строковых последовательностях определенных типов паттернов — частных, характеристических и внутренних. Каждому типу паттернов посвящена соответствующая часть книги.

Книга отличается последовательным изложением материала, большим количеством иллюстративных примеров, свободным обсуждением текущих исследований в этой области, содержит более 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