Алгоритмы. Часть 1

Стеки и очереди

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

Элементарные методы сортировки

Мы познакомим вас с проблемой сортировки и интерфейсом Comparable Java. Мы изучим два элементарных метода сортировки - сортировку выбором и сортировку вставкой - а также разновидность одного из них — сортировку методом Шелла. Также мы рассмотрим два алгоритма для равномерного перемешивания массива. В завершение мы продемонстрируем применение сортировки на практике для вычисления выпуклой оболочки множества точек с помощью алгоритма сканирования Грэма.

Сортировка с объединением (Mergesort)

Мы рассмотрим алгоритм сортировки с объединением и покажем, что он позволяет отсортировать любой массив из n элементов с максимальным количество сравнений n lg n. Также будет рассмотрена нерекурсивная версия этого алгоритма («снизу вверх»). Мы докажем, что любой алгоритм сортировки, основанный на сравнении, в худшем случае должен выполнить не менее n*lg(n) сравнений. Мы обсудим применение различных схем упорядочения сортируемых объектов и связанную с этим концепцию устойчивости.

Быстрая сортировка

Мы изучим и реализуем алгоритм рандомизированной быстрой сортировки и проанализируем его эффективность. Кроме того, рассмотрим рандомизированный быстрый выбор — вариант быстрой сортировки, находящий k-й наименьший элемент за линейное время. В завершение мы рассмотрим 3-направленную быструю сортировку — вариант быстрой сортировки, особенно хорошо работающий при наличии дублирующихся ключей.

Приоритизированные очереди

Мы рассмотрим тип данных «приоритизированная очередь» и его эффективную реализацию с помощью структуры данных «бинарная куча». Эта реализация также является основой эффективного алгоритма пирамидальной сортировки. В завершение мы познакомимся с применением приоритизированных очередей. В частности, мы смоделируем движение объекта, состоящего из n частиц, по законам упругих столкновений.

Таблицы элементарных символов

Мы рассмотрим API для таблиц символов (также известных как ассоциативные массивы, карты или словари) и опишем две элементарные реализации с использованием отсортированного массива (бинарный поиск) и неупорядоченного списка (последовательный поиск). Если ключи имеют тип Comparable, мы зададим расширенный API, включающий дополнительные методы минимума и максимума, нижнего и верхнего предела, ранжирования и выбора. Для разработки эффективной реализации этого API мы изучим структуру данных «бинарное дерево поиска» и проанализируем ее эффективность.

Сбалансированные деревья поиска

В данном модуле нашей целью является создание таблицы символов, в которой можно было бы гарантированно искать и вставлять записи, а также осущесвтлять множество других операций. с логарифмической эффективностью. Мы начнем с рассмотрения 2-3-деревьев, которые легко анализировать, но сложно реализовать. Затем рассмотрим красно-черные бинарные деревья поиска, которые послужат новым способом реализации 2-3-деревьев в виде бинарных деревьев поиска. Наконец мы представим B-деревья — обобщение 2-3-деревьев, широко применяющееся при реализации файловых систем.

Применение БДП в геометрии

Мы начнем с поиска в 1-мерных и 2-мерных диапазонах, цель которого — найти все точки в заданных диапазонах. Для выполнения данной задачи мы рассмотрим k-мерные деревья — естественное обобщение БДП, ключи которого — точки на плоскости (или в пространствах более высокого порядка). Мы также рассмотрим проблемы пересечений, когда требуется найти все пересечения среди множества отрезков или прямоугольников.

Хэш-таблицы

Мы опишем желательные свойства хэш-функции и рассмотрим ее реализацию в Java, включая фундаментальное допущение о равномерности хэширования, определяющее потенциальную успешность хэширования. Затем мы рассмотрим две стратегии реализации хэш-таблиц — раздельное связывание цепочками и линейное исследование. Обе стратегии имеют постоянную по времени эффективность поиска и вставки при удовлетворении допущения о равномерности хэширования.

Области применения таблиц символов

Мы рассмотрим различные практические области применения таблиц символов, включая множества, клиенты словарей, клиенты индексирования и разреженные векторы.