Меркурьев Олег Андреевич Эффективные строковые алгоритмы в модели потока данных : Меркур'єв Олег Андрійович Ефективні рядкові алгоритми моделі потоку даних

Краткое описание

Меркурьев Олег Андреевич Эффективные строковые алгоритмы в модели потока данных
ОГЛАВЛЕНИЕ ДИССЕРТАЦИИ
кандидат наук Меркурьев Олег Андреевич
1.1 Предварительные сведения

1.1.1 Строки

1.1.2 Асимптотические оценки сложности

1.1.3 Алгоритмы

1.1.4 Хэш Карпа-Рабина

1.1.5 Словари

1.1.6 Принцип Яо

1.1.7 Модель потока данных

1.2 Обзор диссертации

1.2.1 Цели и задачи диссертации

1.2.2 Основные методы исследования

1.2.3 Структура диссертации и организация текста

1.2.4 Апробация и публикации

1.2.5 Основные результаты диссертации

2 Палиндромы в потоках

2.1 Введение

2.2 Нижние оценки

2.3 Алгоритмы реального времени

2.3.1 Аддитивная погрешность

2.3.2 Мультипликативная погрешность £ <

2.3.3 Мультипликативная погрешность £ >

3 Повторы и обратные повторы в потоках

3.1 Введение

3.2 Определения

3.3 Сведение к сжатым повторам

3.4 Поиск наибольшего обратного повтора

3.5 Поиск наибольшего повтора

3.6 Нижние оценки

4 Максимальные периодические подстроки в потоках

4.1 Введение

4.2 Определения

4.3 Инструменты

4.3.1 Хэши, фреймы, чекпойнты

4.3.2 Видимые периодические строки

4.3.3 Свежие и чёрствые вхождения

4.3.4 Структуры данных

4.4 Алгоритм

4.4.1 Удаление чекпойнтов

4.4.2 Обновление групп

4.4.3 Обнаружение периодических подстрок

4.4.4 Обновление списка отслеживания

Заключение

Список литературы

Список иллюстраций

Глава

Введение