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

Sofivinogradova: /* Общие сведения */

2025-01-31T18:11:43Z

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

Sofivinogradova: /* Общие сведения */

2025-01-31T13:08:18Z

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

Sofivinogradova: /* Общие сведения */

2025-01-31T13:08:09Z

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

Sofivinogradova в 12:27, 31 января 2025

2025-01-31T12:27:36Z

Sofivinogradova в 12:26, 31 января 2025

2025-01-31T12:26:13Z

Sofivinogradova: /* Темы курса */

2025-01-30T05:55:37Z

‎Темы курса

Sofivinogradova: /* Аннотация к курсу */

2025-01-29T13:26:54Z

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

Sofivinogradova: Новая страница: «==Общие сведения== [https://docs.google.com/forms/d/e/1FAIpQLSdgbRyir_PIn74MVo5Y_hYmhEhEeeIQyN0BO9cywcDxRdSsow/viewform?usp=header Регистра…»

2025-01-29T13:23:41Z

Новая страница: «==Общие сведения== [https://docs.google.com/forms/d/e/1FAIpQLSdgbRyir_PIn74MVo5Y_hYmhEhEeeIQyN0BO9cywcDxRdSsow/viewform?usp=header Регистра…»

Новая страница

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

[https://docs.google.com/forms/d/e/1FAIpQLSdgbRyir_PIn74MVo5Y_hYmhEhEeeIQyN0BO9cywcDxRdSsow/viewform?usp=header Регистрация на курс]

==Аннотация к курсу==
Данный курс состоит из 5 разделов, которые охватывают основные задачи и алгоритмы применительно в областях разработки БД/СУБД, в обработке больших данных и ML, в экономических и коммуникационно-сетевых задачах, а также в реализации безопасных приложений.

← Предыдущая		Версия 18:11, 31 января 2025
Строка 2:		Строка 2:

	*[https://docs.google.com/forms/d/e/1FAIpQLSdgbRyir_PIn74MVo5Y_hYmhEhEeeIQyN0BO9cywcDxRdSsow/viewform?usp=header Регистрация на курс]		*[https://docs.google.com/forms/d/e/1FAIpQLSdgbRyir_PIn74MVo5Y_hYmhEhEeeIQyN0BO9cywcDxRdSsow/viewform?usp=header Регистрация на курс]
		+	Ограничений по регистрации на курс нет.
	*[https://t.me/+SyKn4udNZw1lYWYy Телеграм чат]		*[https://t.me/+SyKn4udNZw1lYWYy Телеграм чат]

@@ Строка 1: / Строка 1: @@
 ==Общие сведения==
-[https://docs.google.com/forms/d/e/1FAIpQLSdgbRyir_PIn74MVo5Y_hYmhEhEeeIQyN0BO9cywcDxRdSsow/viewform?usp=header Регистрация на курс]
+*[https://docs.google.com/forms/d/e/1FAIpQLSdgbRyir_PIn74MVo5Y_hYmhEhEeeIQyN0BO9cywcDxRdSsow/viewform?usp=header Регистрация на курс]
-[https://t.me/+SyKn4udNZw1lYWYy Телеграм чат]
+*[https://t.me/+SyKn4udNZw1lYWYy Телеграм чат]
 ==Команда курса==

← Предыдущая		Версия 13:08, 31 января 2025
Строка 2:		Строка 2:

	[https://docs.google.com/forms/d/e/1FAIpQLSdgbRyir_PIn74MVo5Y_hYmhEhEeeIQyN0BO9cywcDxRdSsow/viewform?usp=header Регистрация на курс]		[https://docs.google.com/forms/d/e/1FAIpQLSdgbRyir_PIn74MVo5Y_hYmhEhEeeIQyN0BO9cywcDxRdSsow/viewform?usp=header Регистрация на курс]
		+	[https://t.me/+SyKn4udNZw1lYWYy Телеграм чат]

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

@@ Строка 4: / Строка 4: @@
 ==Команда курса==
-'''Руководитель курса:'''
+'''Руководитель курса, лектор,семинарист:'''
 *Рубаненко Мария
 '''Ассистенты:'''
@@ Строка 107: / Строка 107: @@
 Оценка за курс =  ( (коллоквиум + зачет)/2  +оценка за практику)/2, где округление происходит в большую сторону, если студент проявлял активность на занятиях, иначе - в меньшую сторону.
 ==Список литературы==

← Предыдущая		Версия 12:26, 31 января 2025
Строка 2:		Строка 2:

	[https://docs.google.com/forms/d/e/1FAIpQLSdgbRyir_PIn74MVo5Y_hYmhEhEeeIQyN0BO9cywcDxRdSsow/viewform?usp=header Регистрация на курс]		[https://docs.google.com/forms/d/e/1FAIpQLSdgbRyir_PIn74MVo5Y_hYmhEhEeeIQyN0BO9cywcDxRdSsow/viewform?usp=header Регистрация на курс]
		+
		+	==Команда курса==
		+	'''Руководитель курса:'''
		+	*Рубаненко Мария
		+	'''Ассистенты:'''
		+	*Попов Алексей
		+	*Каштелян Матвей

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

← Предыдущая		Версия 05:55, 30 января 2025
Строка 21:		Строка 21:
	*2. Методы кластеризации: k-means, DBSCAN, OPTICS.		*2. Методы кластеризации: k-means, DBSCAN, OPTICS.
	*3. Концепция MapReduce. Распараллеливание k-means методом навеса. Распараллеливание k-means через MapReduce. MR-DBSCAN.		*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.

← Предыдущая		Версия 13:26, 29 января 2025
Строка 5:		Строка 5:
	==Аннотация к курсу==		==Аннотация к курсу==
	Данный курс состоит из 5 разделов, которые охватывают основные задачи и алгоритмы применительно в областях разработки БД/СУБД, в обработке больших данных и ML, в экономических и коммуникационно-сетевых задачах, а также в реализации безопасных приложений.		Данный курс состоит из 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.