Методы реализации алгоритмов весна 2025
Общие сведения
Аннотация к курсу
Данный курс состоит из 5 разделов, которые охватывают основные задачи и алгоритмы применительно в областях разработки БД/СУБД, в обработке больших данных и ML, в экономических и коммуникационно-сетевых задачах, а также в реализации безопасных приложений.
Темы курса
Раздел 1 (Структуры в СУБД):
- 1. Succinct data structure. Дисковые структуры. B-деревья в применении.
- 2. Scapegoat tree. Варианты B-деревьев (B*-деревья, копирование при записи, абстракции для управления обновлениями).
- 3. Варианты B-деревьев (ленивые B-деревья, FD-деревья, Bw-деревья, кеш-независимые B-деревья).
- 4. Журналированные структуры. Понятие LSM-дерева и его реализация.
- 5. Неупорядоченное LSM-хранилище. Параллелизм в LSM-деревьях.
- 6. Многоуровневое совмещение журналов и LLAMA.
- 7. LRU, LFU кэш в однопоточных и многопоточных средах. Примеры применения кэша.
Раздел 2 (Обработка многомерных данных):
- 1. Kd-деревья, R-деревья, SS-деревья.
- 2. Методы кластеризации: k-means, DBSCAN, OPTICS.
- 3. Концепция MapReduce. Распараллеливание k-means методом навеса. Распараллеливание k-means через MapReduce. MR-DBSCAN.
