Алгоритмы 1MIT весна 2022

Преподаватели

• (Л) Копелиович Сергей Владимирович (burunduk30@gmail.com, telegram:@burunduk30)
• (1) Антон Буков (aabukov@edu.hse.ru, telegram:@Xrite)
• (2) Александра Олемская (alexandra.olemskaya@gmail.com, telegram:@SiERic)
• (3) Мария Чухарева (mashapalchenkova@gmail.com, telegram:@MRedor)
• (4) Мария Тигина (tiginamaria@gmail.com, telegram:@tiganam)
• (5) Сергей Кузьмин (serg.kuzmin00@mail.ru, telegram:@kuzyaka)

Экзамены

Списки вопросов к экзаменам Задать вопрос

Лекции

Конспект (осень 2021) Конспект (весна 2021) Конспект (весна 2022)

«Доски» с лекций:

• 4 февраля — введение в теорию сложности: неразрешимость, DTime, P, EXP, NP, NPH, NPC.

• 11 февраля: NP-полные задачи, рандомизированные алгоритмы.

• 18 февраля: проверка на простоту и разложение на множители, случайные блуждания.

• 25 февраля: алгоритм Шонинга, лемма Шварца-Зиппеля, BPP, ZPP, кратчайшие пути.

• 4 марта: корректность алгоритма Дейкстры, алгоритм Флойда, алгоритм Форда-Беллмана.

• 11 марта: замечания про алгоритм Флойда, потенциалы Джонсона, минимальное остовное дерево, система непересекающихся множеств.

• 18 марта: СНМ на деревьях, алгоритм Борувки.

Софт, примеры, справка

• help по TestSys (хотите помощи по контесту? напишите преподу! но сперва прочтите этот хелп)

• TeX (обязательно посмотрите примеры!)

• svn для сдачи теордз (в конце важная часть: как правильно называть файлы)

• Чтение примеров по C++ сделают знакомство с ним проще, а запуск примеров по STL поможет научиться использовать встроенные в C++ структуры данных

Информация

ТеорДЗ отправляется на почту практику вашей группы с темой письма "SPb HSE HW Algorithms". Скопируйте тему, чтобы не ошибиться, на неё могут быть настроены фильтры.

Оценка за курс

Результаты практик

Тестирующая система

Дедлайны

• Теория, вторник 23:59 (своему преподавателю по практике: группа 2 - tex в svn, остальные группы - на почту собранный tex в pdf, тема письма SPb HSE HW Algorithms)

• Контест, пятница 23:59

• Исправления и только исправления (не новые задачи!) можно отправлять до начала практики в пятницу.

• Отношения к дедлайнам: их нельзя продалбывать. Еcли заболели/внезапная контрольная/опаздываете -- всегда предупредите. Если у вас проблемы, и вам жизненно необходим именно на этой неделе разовый сдвиг дедлайна, не постесняйтесь заранее попросить об этом.

Домашние задания

В pdf с домашним заданием также лежат задачи практики и их разбор. Ими полезно пользоваться при решении дз. Конспект прочесть тоже полезно.
Домашнее задание разбирается в начале практики. В этот момент удобно спросить о всём, что не получилось. И про контест тоже.

• Поиск в глубину: условия контеста результаты теордз

• Поиск в глубину 2: условия контеста результаты теордз

• Теория сложности: теордз

• Теория сложности 2 и вероятностные алгоритмы: теордз

• Вероятностные алгоритмы 2: условия Невероятные приключения результаты Невероятные приключения условия Поллард результаты Поллард условия SAT результаты SAT теордз

• Кратчайшие пути 1: условия контеста результаты теордз

• Кратчайшие пути 2: условия контеста результаты теордз

• MST: условия контеста результаты теордз

• DSU, приближения, жадность: условия контеста результаты практика

• Жадность: условия контеста результаты теордз

• Приближённые алгоритмы-1: условия контеста результаты теордз

• Приближённые алгоритмы-2 и центроиды: условия контеста результаты теордз

• Центроиды-2, BST и AVL: условия контеста результаты теордз

• Неявный ключ, treap, персистентность: условия контеста результаты теордз