Алгоритмы и структуры данных

Раздел описывает способы организации данных и построения вычислительных процедур для эффективного решения задач.

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

Основные направления

• Анализ алгоритмов — оценка времени выполнения и потребления памяти, сравнение решений и определение зависимости стоимости вычислений от размера входных данных.
• Асимптотическая сложность — обозначения Big O, Big Theta и Big Omega, верхние и нижние оценки, а также типичные классы сложности.
• Корректность алгоритмов — предусловия, постусловия, инварианты, доказательство завершения и проверка соответствия результата требованиям.
• Массивы — последовательное хранение элементов, индексированный доступ, изменение размера, вставка, удаление и влияние расположения данных в памяти.
• Связные списки — односвязные, двусвязные и циклические списки, последовательный доступ и управление связями между элементами.
• Стек — структура LIFO, управление вложенными операциями, история действий, обработка выражений и связь со стеком вызовов.
• Очередь — структура FIFO, очереди задач, кольцевые буферы, двусторонние очереди и приоритетная обработка элементов.
• Хеш-таблицы — хеш-функции, коллизии, коэффициент заполнения, изменение размера и ожидаемая сложность операций.
• Множества и отображения — хранение уникальных значений, сопоставление ключей и значений, проверка принадлежности и операции над наборами данных.
• Деревья — иерархические структуры, узлы, рёбра, высота, глубина, обходы и представление вложенных отношений.
• Двоичные деревья поиска — упорядоченное хранение данных, поиск, вставка, удаление и влияние формы дерева на сложность операций.
• Сбалансированные деревья — AVL-деревья, красно-чёрные деревья, B-деревья и способы поддержания ограниченной высоты.
• Кучи — структуры для эффективного извлечения минимального или максимального элемента, приоритетные очереди и heap sort.
• Префиксные деревья — хранение строк по общим префиксам, поиск слов, автодополнение и маршрутизация по последовательностям символов.
• Графы — вершины, рёбра, направленные и ненаправленные графы, веса, циклы, связность и способы представления.
• Обходы графов и деревьев — поиск в ширину, поиск в глубину, обходы дерева и применение обходов для исследования связей.
• Поиск — линейный поиск, бинарный поиск, поиск по деревьям, графам и индексированным структурам.
• Сортировка — сортировка вставками, выбором, слиянием, быстрая сортировка, пирамидальная сортировка и сравнение их свойств.
• Строковые алгоритмы — поиск подстрок, сравнение последовательностей, префиксные функции, хеширование строк и обработка текстовых данных.
• Алгоритмы кратчайшего пути — поиск минимального пути в графе, алгоритмы Дейкстры, Беллмана — Форда и A*.
• Минимальные остовные деревья — построение связующей структуры минимального веса с помощью алгоритмов Прима и Краскала.
• Непересекающиеся множества — структура Union-Find, объединение компонентов и проверка принадлежности элементов одной группе.
• Рекурсия — решение задачи через её уменьшенные экземпляры, базовый случай, глубина вызовов и преобразование рекурсии в итерацию.
• Разделяй и властвуй — разбиение задачи на независимые подзадачи, их решение и объединение результатов.
• Жадные алгоритмы — последовательный выбор локально оптимального решения и условия, при которых он приводит к глобальному результату.
• Динамическое программирование — повторное использование результатов подзадач, мемоизация, табуляция и построение рекуррентных зависимостей.
• Поиск с возвратом — перебор вариантов, откат состояния, отсечение неподходящих ветвей и решение задач с ограничениями.
• Скользящее окно — обработка непрерывных диапазонов данных без повторного вычисления результата для каждого положения.
• Два указателя — координированное перемещение позиций по последовательности для поиска пар, диапазонов и выполнения преобразований.
• Алгоритмы кеширования — стратегии LRU, LFU, FIFO и управление ограниченным объёмом быстрого хранилища.
• Вероятностные структуры данных — Bloom filter и другие структуры, допускающие контролируемую погрешность ради экономии памяти.
• Внешние алгоритмы — обработка данных, которые не помещаются в оперативную память, внешняя сортировка и блочное чтение.
• Параллельные алгоритмы — разбиение вычислений между потоками или процессами, синхронизация и оценка эффективности параллельного выполнения.
• Практическое решение задач — декомпозиция условий, выбор структуры данных, формулирование инвариантов, анализ граничных случаев и проверка результата.

Свойства структур данных

При изучении каждой структуры данных рассматриваются:

• способ размещения элементов в памяти;
• поддерживаемые операции;
• временная сложность операций;
• дополнительное потребление памяти;
• сохранение порядка элементов;
• устойчивость к увеличению объёма данных;
• влияние кеша процессора;
• ограничения и типичные сценарии применения.

Свойства алгоритмов

При изучении каждого алгоритма рассматриваются:

• входные и выходные данные;
• предусловия применения;
• последовательность вычислений;
• доказательство корректности;
• временная и пространственная сложность;
• лучший, средний и худший случаи;
• устойчивость к граничным значениям;
• возможность параллельного выполнения;
• альтернативные решения и компромиссы.

Основные вопросы раздела

Материалы раздела должны помогать отвечать на следующие вопросы:

• Как выбрать структуру данных для конкретного набора операций?
• Как оценить зависимость времени выполнения от размера входных данных?
• Чем худший случай отличается от среднего и амортизированного?
• Как расположение данных в памяти влияет на производительность?
• Когда массив эффективнее связного списка?
• Почему операции хеш-таблицы не всегда имеют постоянную сложность?
• Как сбалансированное дерево сохраняет эффективность поиска?
• Как представить граф и выбрать подходящий алгоритм обхода?
• Когда следует использовать бинарный поиск?
• Как сравнивать алгоритмы сортировки?
• Как определить, применим ли жадный алгоритм?
• Когда задача требует динамического программирования?
• Как уменьшить объём повторных вычислений?
• Как доказать корректность алгоритма?
• Как проверить алгоритм на граничных и ошибочных данных?
• Когда стандартная библиотека предпочтительнее собственной реализации?
• Как связаны выбор алгоритма, потребление памяти и свойства оборудования?

Границы раздела

Раздел посвящён абстрактным структурам данных, алгоритмам их обработки и методам анализа вычислительных решений.

Синтаксис и особенности реализации структур в конкретных языках рассматриваются в разделе программирования и сред выполнения. Устройство памяти и влияние аппаратных кешей относятся к разделу вычислительных систем. Индексы, планы запросов и структуры хранения баз данных рассматриваются в разделе данных и хранилищ. Организация модулей и архитектура приложений относятся к разделу проектирования программного обеспечения.