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

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

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

Разработка ПО охватывает множество различных ИТ-направлений: Backend, Frontend, DevOps, BigData, ML, Security и т. п., которые в последнее время стремительно развиваются. На сегодня в сфере ИТ очень востребованными являются M-shaped специалисты: ИТ-специалисты, являющиеся экспертами в двух и более ИТ-областях. В данном курсе мы рассмотрим несколько ИТ-направлений: от backend до security и познакомимся с используемыми алгоритмами каждой отдельной области, выделим общие паттерны и подходы на стыке нескольких областей.

  • Регистрация на курс (нужно вставить актуальную ссылку и удалить ЭТОТ ТЕКСТ в скобках)

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


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

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

Ассистенты: Пугачев Михаил

Темы курса

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

  • 1. Суперсжатие: основные концепции и отличия от сжатия.
  • 2. Scapegoat tree.
  • 3. Динамическая и статическая оптимальность BST (бинарное дерево поиска).
  • 4. Варианты B-деревьев (B*-деревья, ленивые B-деревья, FD-деревья, Bw-деревья, кеш-независимые B-деревья).
  • 5. Журналированные структуры. Понятие LSM-дерева и его реализация.
  • 6. 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. Задача с 2мя машинами.

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

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

Раздел 4.2 (Квантовые алгоритмы):

  • 1. Основные понятия. Квантово-вдохновленные алгоритмы.
  • 2. Алгоритм Шора (задача факторизации числа). Алгоритм Гровера (оптимизация поиска в базах данных).
  • 3. Алгоритм Дойча-Йожи. Алгоритм Саймона.
  • 4. Оптимизационный алгоритм QAOA (Quantum Approximate Optimization Algorithm).
  • 5. Квантовое машинное обучение и квантовые нейронные сети.

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

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

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

За семестр требуется сдать 5 лабораторных работ по каждому из разделов. Решенное задание размещается в приватном репозитории github и проверяющему (контакты проверяющего см. в чате группы) присылается ссылка (по почте или в тг) на данный github репозиторий. Предпочтительный язык, на котором можно присылать код лабораторных работ является Java, С++, Python. Также после прохождения 3х разделов курса планируется проведение коллоквиума. Коллоквиум проходит устно и состоит из 3х теоретических вопросов и 3х задач (по соответствующему разделу). В конце курса планируется проведение зачета. Зачет проводится устно и состоит из 3х теоретических вопросов и 3х задач (по соответствующему разделу). Сроки получения и сдачи заданий: Срок размещения лабораторных работ (кроме последней лабораторной) - в день последней темы раздела. Срок размещения последней лабораторной работы - за 2 занятия до окончания раздела. Срок сдачи лабораторных работ - 14 дней с момента публикации задания [пример: если задание опубликовано 01.02.2026, то последний день приема - 15.02.2026 23:59 Мск]. Перенос дедлайнов возможен только по уважительной причине


* Критерии оценивания:

  • 1) Лабораторные [0-90] баллов: Лаб. работа 1 = 20 баллов Лаб. работа 2 = 20 баллов Лаб. работа 3 = 10 баллов Лаб. работа 4 = 30 баллов Лаб. работа 5 = 10 баллов
  • 2) Доклад [3-10] баллов: Сделать доклад статьи на семинаре = [3-10] баллов

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

  • 3) Коллоквиум [0-10 баллов]: Теор. вопросы = [0-10] баллов, Задачи = [0-10] баллов
  • 4) Зачет [0-10 баллов]: Теор. вопросы = [0-10] баллов, Задачи = [0-10] баллов

Оценка за курс = ( (коллоквиум + зачет)/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 (Вероятностные алгоритмы):

  • 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.
Раздел 4.2 (Квантовые алгоритмы):
  • 1. de Wolf R. Quantum Computing (англ.): Lecture Notes — 2019. — 176 p. — arXiv:1907.09415

Раздел 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=Методы_реализации_алгоритмов_весна_2026&oldid=4535»