Методы реализации алгоритмов весна 2025

Материал из Public ATP Wiki
Перейти к: навигация, поиск

Общие сведения

Ограничений по регистрации на курс нет.

Команда курса

Руководитель курса, лектор,семинарист:

  • Рубаненко Мария

Ассистенты:

  • Попов Алексей
  • Каштелян Матвей

Аннотация к курсу

Данный курс состоит из 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.

Раздел 3.1 (Оптимизационные задачи: задачи линейного программирования):

  • 1. Постановка задачи линейного программирования. Разрешимость задачи за конечное время. Полиэдры, политопы. Двойственная задача линейного программирования.
  • 2. Симплекс-метод (и его различные вариации).
  • 3. Транспортная задача.

Раздел 3.2 (Оптимизационные задачи: теория расписаний):

  • 1. Основные определения теории расписаний. Примеры.
  • 2. Задача с 1й машиной. Алгоритм Лоулера.
  • 3. Задача с параллельными машинами.
  • 4. Задача с 2мя машинами.

Раздел 4 (Вероятностные алгоритмы):

  • 1. Основные понятия. Примеры. Вероятностное решение задачи о минимальном разрезе.
  • 2. Алгоритм Лас-Вегас, алгоритм Монте-Карло. Градиентный спуск. Имитация отжига. BSP-деревья. Теорема про BSP-дерево.
  • 3. Алгоритм Фрейвалдcа. Проверка равенства двух полиномов. Лемма Шварца-Зиппеля. Сравнение строк.
  • 4. Алгоритм Валианта для сетей. Dragonfly в дата-центрах Yandex.
  • 5. Классы сложностей P, NP, BPP, P/poly. Примеры вероятностного решения NP-трудных задач (нахождение числа пересечений в графе, оценка наибольшего множества несмежных вершин графа).
  • 6. Вероятностные методы в параллельных вычислениях (протокол византийского соглашения). Задача о выполнимости функции, заданной в конъюнктивной нормальной форме (КНФ) и ее вариации.
  • 7. Вероятностный алгоритм задачи о максимальной выполнимости КНФ.
  • 8. Методы дерандомизации (метод условных вероятностей, метод малых вероятностных пространств).
  • 9. Общеизвестные рандомизированные структуры данных: старый добрый фильтр Блума (для проверки принадлежности к множеству) и его модификации, алгоритм HyperLogLog (для оценки мощности), структура Count-Min Sketch (для оценки частоты).
  • 10. НЕ вероятностная проверка числа на простоту за полином.

Раздел 5 (Криптографические алгоритмы):

  • 1. Понятие криптостойкости. “Историческая классика”: шифр Цезаря, шифр Виженера, шифр Хилла.
  • 2. Основные идеи квантовой криптографии. Симуляция кубита на Java. Принцип неопределенности Гейзенберга. Алгоритм протокола BB84.
  • 3. Псевдослучайность. Целые числа Блума. Алгоритм Блум-Блум-Шуба. Линейный конгруэнтный метод. Java.util.Random vs java.security.SecureRandom.
  • 4. Хеш-функции в применении. Семейства хеш-функций BLAKE, GOST, MD, RIPEMD, SHA. Пример реализации на Java с помощью класса java.security.MessageDigest.
  • 5. Алгоритмы симметричного шифрования (DES [с реализацией на Java], AES [с реализацией на Java], RC5, Blowfish, Twofish, RC4, Salsa20).
  • 6. Протокол Диффи - Хеллмана. Алгоритмы ассиметричного шифрования (RSA, DSA, схема Эль-Гамаля, ECDSA).
  • 7. Гомоморфное шифрование. Электронное голосование. Шифрование с поиском.
  • 8. Схема идентификации. Протокол Фейга-Фиата-Шамира с реализацией на Java.
  • 9. Цифровые подписи. Реализация цифровой подписи через RSA+SHA256 и через схему Эль-Гамаля на Java.
  • 10. Постквантовая криптография. Криптография на решетках. Алгоритм LLL (Лентсры - Лентсры - Ловаса). Алгоритм GGH (Голдрейх - Голдвассер - Халеви). NTRU и соответствующая библиотека на Java.
  • 11. Протокол обмена ключами с использованием суперсингулярных изогений.

Отчетность по курсу

За семестр требуется сдать 5 лабораторных работ по каждому из разделов. Решенное задание размещается в приватном репозитории github и проверяющему (контакты проверяющего см. в чате группы) присылается ссылка (по почте или в тг) на данный github репозиторий. Предпочтительный язык, на котором можно присылать код лабораторных работ является Java, С++, Python.

Также после прохождения 3х разделов курса планируется проведение коллоквиума. Коллоквиум проходит устно и состоит из 3х теоретических вопросов и 3х задач (по соответствующему разделу).

В конце курса планируется проведение зачета. Зачет проводится устно и состоит из 4х теоретических вопросов и 2х задач (по соответствующему разделу).

Сроки получения и сдачи заданий: Срок размещения лабораторных работ (кроме последней лабораторной) - в день последней темы раздела. Срок размещения последней лабораторной работы - за 2 занятия до окончания раздела.

Срок сдачи лабораторных работ - 14 дней с момента публикации задания [пример: если задание опубликовано 01.02.2025, то последний день приема - 15.02.2025 23:59 Мск].

Перенос дедлайнов возможен только по уважительной причине.

Критерии оценивания: Лабораторные [0-90] баллов: Лаб. работа 1 = 20 баллов Лаб. работа 2 = 20 баллов Лаб. работа 3 = 20 баллов Лаб. работа 4 = 20 баллов Лаб. работа 5 = 10 баллов

Доклад [3-10] баллов: Сделать доклад статьи на семинаре = [3-10] баллов

Оценка за практику [0-10 баллов] = (Лабораторные + Доклад) / 10

Коллоквиум [0-10 баллов]: Теор. вопрос = [0 | 5/6 | 10/6] баллов Задача = [0 | 5/6 | 10/6] баллов

Зачет [0-10 баллов]: Теор. вопрос = [0 | 5/6 | 10/6] баллов Задача = [0 | 5/6 | 10/6] баллов

Оценка за курс = ( (коллоквиум + зачет)/2 +оценка за практику)/2, где округление происходит в большую сторону, если студент проявлял активность на занятиях, иначе - в меньшую сторону.


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

Раздел 1 (Структуры в СУБД):

  • 1. Sedgewick Robert and Kevin Wayne. 2011. Algorithms (4th Ed.). Boston: Pearson.
  • 2. Knuth Donald E. 1997. The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Algorithms. Boston: Addison-Wesley Longman.
  • 3. Elmasri Ramez and Shamkant Navathe. 2011. Fundamentals of Database Systems (6th Ed.). Boston: Pearson.
  • 4. Justin Sheehy, David Smith. “Bitcask: A log-structured hash table for fast key/value data.” 2010.

Раздел 2 (Обработка многомерных данных):

  • 1. Brown R (2015). "Building a balanced k-d tree in O(kn log n) time". Journal of Computer Graphics Techniques. 4 (1): 50–68.
  • 2. Y. Kwon, D. Nunley, J. P. Gardner, M. Balazinska, B. Howe, and S. Loebman, “Scalable clustering algorithm for n-body simulations in a shared-nothing cluster,” in Proceedings of the 22nd international conference on Scientific and statistical database management, ser. SSDBM’10. Berlin, Heidelberg: Springer-Verlag, 2010, pp. 132–150.
  • 3. E. Januzaj, H.-P. Kriegel, and M. Pfeifle, “Scalable density-based distributed clustering,” in Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, ser. PKDD ’04. New York, NY, USA: Springer-Verlag New York, Inc., 2004, pp. 231–244.

Раздел 3.1 (Оптимизационные задачи: задачи линейного программирования):

  • 1. Канторович Л. В., Горстко А. Б. Математическое оптимальное программирование в экономике. — М. : Знание, 1968. — 96 с.
  • 2. Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М. : Наука, 1980.

Раздел 3.2 (Оптимизационные задачи: теория расписаний):

  • 1. Joseph Y-T. Leung. Handbook of scheduling: algorithms, models, and performance analysis. 2004.
  • 2. Michael Pinedo. Scheduling: theory, algorithms, and systems. 2008.
  • 3. Лазарев А.A., Гафаров Е. Р. Теория расписаний. Задачи и алгоритмы. — М. : МГУ, 2011.— 222 с.

Раздел 4 (Вероятностные алгоритмы):

  • 1. Fuchs, Henry; Kedem, Zvi. M; Naylor, Bruce F. (1980). "On Visible Surface Generation by A Priori Tree Structures".
  • 2. Zippel, Richard (1993). Springer (ed.). Effective Polynomial Computation. The Springer International Series in Engineering and Computer Science. Vol. 241.
  • 3. L. G. Valiant, “General context-free recognition in less than cubic time”, Journal of Computer and System Sciences, 10:2 (1975), 308–314.
  • 4. R. Motwani и P. Raghavan. Randomized algorithms. Англ. Cambridge Univ. Press, 1995.
  • 5. R. Beier и B. Vöcking. “Random Knapsack in Expected Polynomial Time”. Англ. В: Proceedings of the 35th ACM Symposium on Theory of Computing (STOC). 2003, p. 232–241.

Раздел 5 (Криптографические алгоритмы):

  • 1. Paar C., Pelzl J., Guneysu T. Understanding Cryptography: From Established Symmetric and Asymmetric Ciphers to Post-Quantum Algorithms.2nd Edition.: Springer, 2024. — 555 p.
  • 2. Christof Paar, Jan Pelz, Understanding Cryptography. A Textbook for Students and Practitioners. Springer-Verlag Berlin Heidelberg, 2010.
Источник — «http://wiki.atp-fivt.org/index.php?title=Методы_реализации_алгоритмов_весна_2025&oldid=3747»