Лекция Сложность и модели вычислений. Анализ учетных стоимостей (начало)



Скачать 29.54 Kb.
Дата13.02.2017
Размер29.54 Kb.
Просмотров182
Скачиваний0
ТипЛекция

Алгоритмы и структуры данных поиска, часть 1

Автор: к.ф.-м.н. Бабенко Максим Александрович



Лекция 1. Сложность и модели вычислений. Анализ учетных стоимостей (начало)

Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и худшем случаях. Пример: задача сортировки. Сортировка выбором. Теоретико-информационная нижняя оценка сложности. Разрешающие деревья. Нижняя оценка сложности в модели разрешающих деревьев. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода.



Лекция 2. Анализ учетных стоимостей (окончание)

Анализ учетных стоимостей операций: функция потенциала, истинные и учетные стоимости. Стеки и очереди. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков. Задача о поддержании динамического максимума в стеке и очереди. Изменяемые (mutable) и неизменяемые (immutable) структуры данных. Структуры данных с хранением истории (persistent). Immutable-стек и immutable-очередь. Проблема множественного будущего при анализе учетных стоимостей в persistent-структурах.



Лекция 3. Алгоритмы Merge-Sort и Quick-Sort

Понятие о методе «разделяй и властвуй». Алгоритм Merge-Sort. Слияние двух упорядоченных списков. Оценка сложности. K-way Merge-Sort для работы во внешней памяти. Сортировка слиянием без использования дополнительной памяти. Общая схема алгоритма Quick-Sort. Два варианта реализации Partition. Примеры неудачного выбора опорных элементов. Рандомизированный выбор опорного элемента. Сложность Quick-Sort в худшем и среднем случаях. Глубина рекурсии в худшем и среднем случаях. Элиминация хвостовой рекурсии. Задача об оптимальном дереве слияний. Коды Хаффмана. Слияние двух упорядоченных последовательностей различной длины. Теоретико-информационная нижняя оценка. Бинарный поиск "от края" (galloping).



Лекция 4. Порядковые статистики. Кучи (начало)

Нахождение порядковых статистик с помощью рандомизированной модификации алгоритма Quick-Sort. Линейность матожидания времени работы. Приближенные медианы. Выбор k-й порядковой статистики за линейное в худшем случае. Деревья со свойствами кучи. Почти полные бинарные деревья: нумерация вершин, навигация. Двоичная куча. Операция просеивания вниз и вверх. Реализация операций вставки, удаления и поиска минимума. Преобразование произвольного массива ключей в кучу (операция Make-Heap), линейность времени работы. Алгоритм сортировки Heap-Sort.



Лекция 5. Кучи (окончание)

k-ичные кучи, зависимость сложности операций от выбора k. Биномиальные (binomial), левацкие (leftlist) и косые (skew) кучи.



Лекция 6. Хеширование

Хеш-функции. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей. Совершенные хеш-функции. Построение совершенной хеш-функции с помощью универсального семейства. Интерфейс множества с ошибками. Фильтр Блюма (Bloom filter). Оценка вероятности ложноположительного срабатывания. Интерфейс словаря с ошибками. Модификация фильтра Блюма (bloomier filter).



Лекция 7. Деревья поиска (начало)

Определение дерева поиска. Вставка и удаление элементов. Inorder-обход дерева. Красно черные деревья: определение и основные свойства. Реализация операций вставки для красно-черного дерева. Splay-деревья. Операция splay: zig, zig-zig и zig-zag шаги. Реализация операций вставки, удаления, слияния и разделения для splay-деревьев.



Лекция 8. Деревья поиска (продолжение)

Декартовы деревья (дучи). Единственность декартова дерева для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания высоты дучи.Операции слияния и разделения для дуч. Операции вставки и удаления элементов для дуч. Построение декартового дерева за линейное время при условии предварительной сортировки ключей.



Лекция 9. Деревья поиска (окончание). Система непересекающихся множеств

B+ деревья: определения и основные свойства. Операции поиска, вставки и удаления для B+ деревьев. Системы непересекающихся множеств. Реализация с использованием леса. Ранги вершин, эвристика ранга. Логарифмическая оценка ранга через количество элементов. Рандомизированная ранговая эвристика. Эвристика сжатия путей. Оценка учетной стоимости операций (без доказательства).



Лекция 10. Задачи RMQ и LCA

Задачи RMQ (range minimum query) и LCA (least common ancestor). Сведение от задачи RMQ к задаче LCA, декартово дерево. Алгоритм Таржана для offline-версии задачи LCA. Простейшие алгоритмы для online-версии задачи LCA: полная и разреженная таблицы ответов. Алгоритм Фарах-Колтона-Бендера для к задаче ±1-RMQ. Сведение задачи LCA к задаче ±1-RMQ: эйлеров обход дерева.



Лекция 11. Структуры данных для геометрического поиска

Location problem, stabbing problem. Деревья интервалов. Сведение системы интервалов к двумерной задаче. Задача поиска точек в коридоре. Priority search tree. Задача поиска точек в прямоугольнике. Дерево отрезков по координате X, упорядоченные по Y списки точек в каждой вершине. Сложность O(n log n) для построения и O(log^2 n) для запроса. Уменьшение времени поиска до O(log n). Задача одновременного поиска в наборе упорядоченных списков. Fractional cascading.



Лекция 12. Задача о динамической связности в ненаправленном графе

Задача о динамической связности: вставки и удаления ребер, запросы о связности. Частный случай задачи для случая лесов. Дервья эйлеровых обходов: слияние и разделение. Использование амортизации и набора остовных лесов для решения со сложностью O(log^2 n).



Рекомендуемая литература

М. А. Бабенко, М. В. Левин "Введение в теорию алгоритмов и структур данных" МЦНМО Библио-глобус



  • http://en.wikipedia.org/wiki/Introduction_to_Algorithms

  • Бьёрн Страуструп, "Язык C++", http://lib.ru/CPPHB/cpptut.txt

  • Scott Meyers, Effective C++: 55 Specific Ways to Improve Your Programs and Designs, 3rd Edition

  • Martin Fowler, Refactoring: Improving the Design of Existing Code

  • http://en.wikipedia.org/wiki/Design_Patterns

  • http://en.wikipedia.org/wiki/Code_Complete

  • http://misko.hevery.com/2008/11/11/clean-code-talks-dependency-injection/

  • http://misko.hevery.com/attachments/Guide-Writing%20Testable%20Code.pdf

  • Scott Meyers, More Effective C++: 35 New Ways to Improve Your Programs and Designs

  • Scott Meyers, Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library

  • http://en.wikipedia.org/wiki/The_Pragmatic_Programmer



Алгоритмы и структуры данных поиска, часть 2

Автор: к.ф.-м.н. Бабенко Максим Александрович

Лекция 1. Обход в ширину. Обход в глубину (начало)

Графы: основные определения, обозначения и способы хранения. Обход в ширину и его использование для нахождения кратчайших путей. Обход в глубину и его основные свойства.



Лекция 2. Обход в глубину (продолжение)

Эйлеровы обходы графов. Построение эйлерового обхода с помощью варианта обхода в глубину. Дерево обхода в глубину. Классификация дуг графа относительно дерева обхода в глубину (дуги дерева, обратные, прямые, перекрестные). Отсутствие перекрестных дуг при поиске в ненаправленном графе. Точки сочленения и их нахождение за линейное время с помощью обхода в глубину.



Лекция 3. Обход в глубину (окончание). 2-разрезы

Отношение взаимной достижимости вершин. Компоненты сильной связности, конденсация. Ацикличность конденсации. Поиск сильно связных компонент с помощью обхода в глубину. Топологическая сортировка конденсации. 1- и 2-разрезы. Линейное пространство на ребрах графа, его размерность. Подпространство циклов графа, его размерность и базис. Подпространство разрезов графа. Разложение пространства в прямую ортогональную сумму подпространств циклов и разрезов. Генерация случайного равновероятного элемента в пространстве циклов. Рандомизированный поиск 2-разрезов на основе fingerprints.



Лекция 4. Поиск кратчайших путей (начало)

Кратчайшие пути в графе, примеры функции длин. Оценки расстояний и их релаксация. Алгоритмы Форда-Беллмана и Флойда. Алгоритм Дейкстры.



Лекция 5. Поиск кратчайших путей (продолжение)

Анализ сложности алгоритма Дейкстры. Использование бинарных и k-ичных куч. Двунаправленный алгоритм Дейкстры. Системы потенциалов в задаче о кратчайших путях. Критерий консервативности функции длин дуг в терминах наличия допустимого набора потенциалов. Алгоритм Джонсона для задачи APSPP при произвольных длинах дуг. Использование маяков (landmarks) для быстрого поиска кратчайших путей. Алгоритм ALT.



Лекция 6. Минимальные остовные деревья

Задача об оптимальном остовном дереве. Хорошие множества, лемма о минимальном ребре в разрезе. Алгоритмы Краскала, Прима и Борувки. Оценки сложности.



Лекция 7. Минимальные разрезы. Поиск подстрок (начало)

Задачи о минимальном глобальном разрезе и о минимальном s-t разрезе, их связь. Стягиванияя графа. Алгоритм Штёра-Вагнера. Строки: основные определения и обозначения. Задача поиска подстроки в строке: различные варианты постановки. Наивный алгоритм. Префикс-функция: определение и свойства. Построение префикс-функции за линейное время. Алгоритм Кнута-Морриса-Пратта.



Лекция 8. Поиск подстрок (продолжение)

Z-функция: определение и использование в задаче поиска подстроки. Построение Z-функции за линейное время. Оптимизация поиска подстрок с помощью Z-функции по памяти. Использование Z-функции для задачи приближенного поиска подстрок с одной ошибкой за линейное время. Задача множественного поиска подстрок, ожидаемая асимптотика времени работы. Бор для набора слов: определение и способы представления. Префикс-функция на боре. Алгоритм Ахо--Корасик для множественного поиска подстрок.



Лекция 9. Поиск подстрок (окончание)

Поиск подстрок: джокеры типа "?" и "*". Использование алгоритма Ахо-Корасик. Оценка сложности. Редукция по символу алфавита. Поиск подходящих позиций с использованием сверток. Связь сверток с умножением полиномов. Пара оптимизаций: бинаризация алфавита и сокращение длины текста с помощью двуслойного покрытия.



Лекция 10. Суффиксные деревья (начало)

Быстрое преобразование Фурье, рекурсивный вариант алгоритма. Обратное преобразование Фурье. Суффиксный бор и суффиксное дерево, оценки размеров. Явные и неявные положения в суффиксном дереве. Суффиксные ссылки.



Лекция 11. Суффиксные деревья (окончание). Суффиксные массивы (начало)

Общая схема алгоритма Укконена для построения сжатого суффиксного дерева за время, линейное по длине строки. Итерации и шаги алгоритма. Классификация шагов. Лемма о возможных переходах между шагами различных типов. Элиминация шагов типа 1: неявные пометки листовых дуг. Элиминация шагов типа 3: досрочное окончание итерации. Оценка количества шагов типа 2. Поиск положений для шагов типа 2: суффиксные ссылки. Прием «скачок по счетчику» для быстрого вычисления суффиксных ссылок. Лемма об изменении вершинной глубины при переходе по суффиксной ссылке. Доказательство линейности времени работы алгоритма Укконена. Суффиксные массивы. Поиск подстрок с помощью суффиксных массивов и бинарного поиска. Построение суффиксного массива за время O(n log n) методом маркировки (алгоритм Карпа-Миллера-Розенберга).



Лекция 12. Суффиксные массивы (окончание)

Ускорение поиска подстрок с помощью предварительно рассчитанных lcp-значенеий. Алгоритм Каркайнена-Сандерса построения суффиксного массива за линейное время. Наименьшие общие предки в суффиксном дереве, связь с LCP-функцией. LCP-массив: определение и свойства. Построение LCP-массива по суффиксному массиву за линейное время (алгоритм Арикавы-Аримуры-Касаи-Ли-Парка).



Лекция 13. Длиннейшие общие подстроки. Приближенный поиск подстрок.

Задача о длиннейшей общей подстроке. Решение за линейное время с помощью суффиксного дерева и суффиксного массива. Задача приближенного поиска подстрок в тексте. Формулировка в терминах расстояний по графу динамического программирования. Алгоритм Ландау-Вишкина: множества достижимых вершин и их границы. База и шаг алгоритма, использование LCP.



Рекомендуемая литература

М. А. Бабенко, М. В. Левин "Введение в теорию алгоритмов и структур данных" МЦНМО Библио-глобус



  • http://en.wikipedia.org/wiki/Introduction_to_Algorithms

  • Бьёрн Страуструп, "Язык C++", http://lib.ru/CPPHB/cpptut.txt

  • Scott Meyers, Effective C++: 55 Specific Ways to Improve Your Programs and Designs, 3rd Edition

  • Martin Fowler, Refactoring: Improving the Design of Existing Code

  • http://en.wikipedia.org/wiki/Design_Patterns

  • http://en.wikipedia.org/wiki/Code_Complete

  • http://misko.hevery.com/2008/11/11/clean-code-talks-dependency-injection/

  • http://misko.hevery.com/attachments/Guide-Writing%20Testable%20Code.pdf

  • Scott Meyers, More Effective C++: 35 New Ways to Improve Your Programs and Designs

  • Scott Meyers, Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library

  • http://en.wikipedia.org/wiki/The_Pragmatic_Programmer





Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал