Просмотр исходного текста страницы Алгоритмы 1MIT весна 2022

Материал из CSC Wiki

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

У вас нет прав на выполнение действия «редактирование этой страницы» по следующей причине:

---

Вы можете просмотреть и скопировать исходный код этой страницы.

== Преподаватели == * (Л) Копелиович Сергей Владимирович ([mailto:burunduk30@gmail.com burunduk30@gmail.com], telegram:@burunduk30) * (1) Антон Буков ([mailto:aabukov@edu.hse.ru aabukov@edu.hse.ru], telegram:@Xrite) * (2) Александра Олемская ([mailto:alexandra.olemskaya@gmail.com alexandra.olemskaya@gmail.com], telegram:@SiERic) * (3) Мария Чухарева ([mailto:mashapalchenkova@gmail.com mashapalchenkova@gmail.com], telegram:@MRedor) * (4) Мария Тигина ([mailto:tiginamaria@gmail.com tiginamaria@gmail.com], telegram:@tiganam) * (5) Сергей Кузьмин ([mailto:serg.kuzmin00@mail.ru serg.kuzmin00@mail.ru], telegram:@kuzyaka) == Экзамены == [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/exams/ Списки вопросов к экзаменам] [https://docs.google.com/spreadsheets/d/1pOeJS5j8mdyxrM1gJy9yWWtZD-qn_7_CRNhsxglWXWk/edit#gid=0 Задать вопрос] == Лекции == [http://acm.math.spbu.ru/~sk1/courses/2122f_au/conspect/conspect.pdf Конспект (осень 2021)] [http://acm.math.spbu.ru/~sk1/courses/2021s_au/conspect/conspect.pdf Конспект (весна 2021)] '''[https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/conspect.pdf Конспект (весна 2022)]''' «Доски» с лекций: * 4 февраля — введение в теорию сложности: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-02-04_Undecidability.pdf неразрешимость], [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-02-04_DTime.pdf DTime, P, EXP], [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-02-04_NP.pdf NP, NPH, NPC]. * 11 февраля: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-02-11_NPc.pdf NP-полные задачи], [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-02-11_RP.pdf рандомизированные алгоритмы]. * 18 февраля: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-02-18_Primes.pdf проверка на простоту и разложение на множители], [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-02-18_RandomWalk.pdf случайные блуждания]. * 25 февраля: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-02-25_Schoening.pdf алгоритм Шонинга], [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-02-25_Schwartz-Zippel_BPP_ZPP.pdf лемма Шварца-Зиппеля, BPP, ZPP], [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-02-25_ShortestPaths.pdf кратчайшие пути]. * 4 марта: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-03-04_DijkstraProof.pdf корректность алгоритма Дейкстры], [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-03-04_Floyd.pdf алгоритм Флойда], [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-03-04_Ford-Bellman.pdf алгоритм Форда-Беллмана]. * 11 марта: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-03-11_FloydNotes.pdf замечания про алгоритм Флойда], [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-03-11_Johnson.pdf потенциалы Джонсона], [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-03-11_MST.pdf минимальное остовное дерево], [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-03-11_DSU.pdf система непересекающихся множеств]. * 18 марта: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-03-18_DSUTrees.pdf СНМ на деревьях], [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/notes/2022-03-18_Boruvka.pdf алгоритм Борувки]. == Софт, примеры, справка == * [https://acm.math.spbu.ru/~sk1/help/testsys/ help по TestSys] (хотите помощи по контесту? напишите преподу! но сперва прочтите этот хелп) * [[help_tex_windows | TeX]] (обязательно посмотрите примеры!) * [[help_algosvn | svn для сдачи теордз]] (в конце важная часть: как правильно называть файлы) * Чтение [http://acm.math.spbu.ru/~sk1/examples/c++/base/ примеров по C++] сделают знакомство с ним проще, а запуск [http://acm.math.spbu.ru/~sk1/examples/c++/stl/ примеров по STL] поможет научиться использовать встроенные в C++ структуры данных == Информация == ТеорДЗ отправляется на почту практику вашей группы с темой письма "SPb HSE HW Algorithms". Скопируйте тему, чтобы не ошибиться, на неё могут быть настроены фильтры. [[algo_scoring_1course_2021f|Оценка за курс]] [https://docs.google.com/spreadsheets/d/12h6-2Y6Uwl1I9igvlMaWijcilFRnO5xTmyl3y7LbQxY/edit?usp=sharing Результаты практик] [https://acm.math.spbu.ru/tsweb Тестирующая система] '''Дедлайны''' * Теория, вторник 23:59 (своему преподавателю по практике: группа 2 - '''tex''' в '''svn''', остальные группы - на почту '''собранный tex в pdf''', тема письма '''SPb HSE HW Algorithms''') * Контест, пятница 23:59 * Исправления и только исправления (не новые задачи!) можно отправлять до начала практики в пятницу. * Отношения к дедлайнам: их нельзя продалбывать. Еcли заболели/внезапная контрольная/опаздываете -- всегда предупредите. Если у вас проблемы, и вам жизненно необходим именно на этой неделе разовый сдвиг дедлайна, не постесняйтесь заранее попросить об этом. == Домашние задания == В pdf с домашним заданием также лежат задачи практики и их разбор. Ими полезно пользоваться при решении дз. Конспект прочесть тоже полезно.<br> Домашнее задание разбирается в начале практики. В этот момент удобно спросить о всём, что не получилось. И про контест тоже. * Поиск в глубину: [http://acm.math.spbu.ru/~sk1/courses/2122s_au/statements/220114_hse.pdf условия контеста] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220114_hse.dat результаты] [https://drive.google.com/file/d/1hi1WfHTxpDEfFOpsq56VtPwno3uqHNgD/view?usp=sharing теордз] * Поиск в глубину 2: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/statements/220128_hse.pdf условия контеста] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220128_hse.dat результаты] [https://drive.google.com/file/d/1l6WLUPpt_ovbfWrJDniiEk5wUhHTGQ3q/view?usp=sharing теордз] * Теория сложности: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/practice/220204.pdf теордз] * Теория сложности 2 и вероятностные алгоритмы: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/practice/220211.pdf теордз] * Вероятностные алгоритмы 2: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/statements/220218_hse.pdf условия Невероятные приключения] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220218_hse.dat результаты Невероятные приключения] [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/statements/220218p_hse.pdf условия Поллард] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220218p_hse.dat результаты Поллард] [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/statements/220218s_hse.pdf условия SAT] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220218s_hse.dat результаты SAT] [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/practice/220218.pdf теордз] * Кратчайшие пути 1: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/statements/220226_hse.pdf условия контеста] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220226_hse.dat результаты] [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/practice/220225.pdf теордз] * Кратчайшие пути 2: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/statements/220305_hse.pdf условия контеста] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220305_hse.dat результаты] [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/practice/220304.pdf теордз] * MST: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/statements/220312_hse.pdf условия контеста] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220312_hse.dat результаты] [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/practice/220311.pdf теордз] * DSU, приближения, жадность: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/statements/220406_hse.pdf условия контеста] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220406_hse.dat результаты] [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/practice/220318.pdf практика] * Жадность: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/statements/220410_hse.pdf условия контеста] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220410_hse.dat результаты] [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/practice/220408.pdf теордз] * Приближённые алгоритмы-1: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/statements/220415_hse.pdf условия контеста] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220415_hse.dat результаты] [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/practice/220415.pdf теордз] * Приближённые алгоритмы-2 и центроиды: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/statements/220423_hse.pdf условия контеста] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220423_hse.dat результаты] [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/practice/220422.pdf теордз] * Центроиды-2, BST и AVL: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/statements/220429_hse.pdf условия контеста] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220429_hse.dat результаты] [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/practice/220429.pdf теордз] * Неявный ключ, treap, персистентность: [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/statements/220513_hse.pdf условия контеста] [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m220513_hse.dat результаты] [https://cdkrot.me/petr/teaching/HSE/2022s-bachelors-algo/practice/220513.pdf теордз]

Возврат к странице Алгоритмы 1MIT весна 2022.