Алгоритмы и структуры данных пилотный поток 2020/2021 — различия между версиями
Debnatkh (обсуждение | вклад) |
Debnatkh (обсуждение | вклад) (→4 модуль) |
||
(не показано 29 промежуточных версии этого же участника) | |||
Строка 1: | Строка 1: | ||
'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов] | '''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов] | ||
+ | [https://drive.google.com/file/d/18aM-sRHrXQAZOVHmgb1uSSiiCn6bNaSW/view?usp=sharing Программа курса] | ||
{| class="wikitable" | {| class="wikitable" | ||
Строка 12: | Строка 13: | ||
== Формула выставления итоговой оценки == | == Формула выставления итоговой оценки == | ||
+ | '''2, 5 модули:''' | ||
+ | О<sub>итог</sub> = '''0.375''' · О<sub>контесты</sub> + '''0.325''' · O<sub>листки</sub> + '''0.3''' · O<sub>экз</sub> + O<sub>бонус</sub> | ||
+ | |||
+ | |||
+ | {|style="border:solid 4px red;" | ||
+ | | | ||
+ | '''3, 4 модули:''' О<sub>итог</sub> = '''0.3''' · О<sub>контесты</sub> + '''0.25''' · O<sub>листки</sub> + '''0.15''' · O<sub>КР</sub> + '''0.3''' · O<sub>экз</sub> + O<sub>бонус</sub> | ||
+ | |||
+ | |} | ||
<ul> | <ul> | ||
<li> | <li> | ||
− | |||
О<sub>контесты</sub> вычисляется по формуле: | О<sub>контесты</sub> вычисляется по формуле: | ||
{| | {| | ||
Строка 65: | Строка 74: | ||
== Лекции и семинары == | == Лекции и семинары == | ||
− | |||
− | |||
<!-- | <!-- | ||
Строка 76: | Строка 83: | ||
64 69 74 * | 64 69 74 * | ||
2e 63 6f * | 2e 63 6f * | ||
− | 6d 2f 72 | + | 6d 2f 72 * |
− | 2f 41 6e | + | 2f 41 6e * |
− | 69 6d 61 | + | 69 6d 61 * |
− | 6c 73 42 | + | 6c 73 42 * |
− | 65 69 6e | + | 65 69 6e * |
− | 67 44 65 | + | 67 44 65 * |
− | 72 70 73 | + | 72 70 73 * |
− | 2f 63 6f | + | 2f 63 6f * |
− | 6d 6d 65 | + | 6d 6d 65 * |
− | 6e 74 73 | + | 6e 74 73 * |
− | 2f 61 68 | + | 2f 61 68 * |
− | 33 6c 64 | + | 33 6c 64 * |
− | 6a 2f 73 | + | 6a 2f 73 * |
− | 65 61 6c | + | 65 61 6c * |
− | 73 5f 61 | + | 73 5f 61 * |
− | 72 65 5f | + | 72 65 5f * |
− | 64 65 72 | + | 64 65 72 * |
− | 70 79 5f | + | 70 79 5f * |
− | 63 68 6f | + | 63 68 6f * |
− | 6e 6b 79 | + | 6e 6b 79 * |
− | 5f 61 6e | + | 5f 61 6e * |
− | 64 5f 73 | + | 64 5f 73 * |
− | 71 75 69 | + | 71 75 69 * |
73 68 79 | 73 68 79 | ||
--> | --> | ||
− | + | === 2 модуль === | |
− | + | {| role="presentation" class="mw-collapsible mw-collapsed wikitable" | |
− | {| role="presentation" class="mw-collapsible wikitable" | + | |
! Дата | ! Дата | ||
! Семинар | ! Семинар | ||
Строка 147: | Строка 153: | ||
| 24 ноября | | 24 ноября | ||
| colspan="2" style="background-color:#ffeae9;" |Разбор домашнего задания №1 | | colspan="2" style="background-color:#ffeae9;" |Разбор домашнего задания №1 | ||
− | | Амортизационный анализ методом потенциалов. Очередь через два стека, дек через три стека, динамический | + | | Амортизационный анализ методом потенциалов. Очередь через два стека, дек через три стека, динамический массив, деамортизация. |
|- | |- | ||
| style="white-space: nowrap;" |26 ноября | | style="white-space: nowrap;" |26 ноября | ||
| style="width: 35%"| Задачи на кучи и амортизационный анализ | | style="width: 35%"| Задачи на кучи и амортизационный анализ | ||
− | | style="white-space: nowrap;" |[https://drive.google.com/file/d/ | + | | style="white-space: nowrap;" |[https://drive.google.com/file/d/13HDqiIczQz8vSZOQzGwLQtxlHm1DmFT8/view?usp=sharing <code>2e636f</code>] |
| style="width: 65%"| Фибоначчиева куча | | style="width: 65%"| Фибоначчиева куча | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |1 декабря | ||
+ | | style="width: 35%"| Задачи на кучи и амортизационный анализ (2) | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1yQMK6miGRfj1S6YdzwyNMjQzdCRsGs7-/view?usp=sharing <code>6d2f72</code>] | ||
+ | | style="width: 65%"| Хеширование. Постановка задачи, полиномиальный хеш, лемма Шварца-Зиппеля. | ||
+ | |- | ||
+ | | 3 декабря | ||
+ | | colspan="3" | Разговор про эффективный код | ||
+ | |- | ||
+ | | 8 декабря | ||
+ | | colspan="2" style="background-color:#ffeae9;" |Разбор домашнего задания №2 | ||
+ | | Хеш-таблицы. Цепочки и открытая адресация, масштабирование хеш-таблиц. Совершенное хеширование, фильтры Блума. | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |10 декабря | ||
+ | | style="width: 35%"| Задачи на хеши и хеш-таблицы | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1Zq1dq3a7j6DVUWXBxum7C8UNKOupo1b-/view?usp=sharing <code>2f416e</code>] | ||
+ | | style="width: 65%"| Бинарные деревья поиска. Сбалансированные деревья, декартово дерево. Декартово дерево по неявному ключу. | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |15 декабря | ||
+ | | style="width: 35%"| Задачи на бинарные деревья поиска | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1yDKqonnfA8grb1DuElTDLGDnMRouZlbu/view?usp=sharing <code>696d61</code>] | ||
+ | | style="width: 65%"| Дерево Ван Эмде Боаса | ||
+ | |- | ||
+ | | 17 декабря | ||
+ | | colspan="3" style="background-color:#ecf4ff;" | Бонусный контест №1 | ||
+ | |- | ||
+ | |} | ||
+ | |||
+ | === 3 модуль === | ||
+ | {| role="presentation" class="mw-collapsible mw-collapsed wikitable" | ||
+ | ! Дата | ||
+ | ! Семинар | ||
+ | ! Листочек | ||
+ | ! Лекция | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |12 января | ||
+ | | style="width: 35%"| Самобалансирующиеся деревья Тарьяна-Слейтера | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1L3_86pAd7VIFhgKm-egFtSJNVEg7NLho/view?usp=sharing <code>6c7342</code>] | ||
+ | | style="width: 65%"| Запросы на отрезках: разреженные таблицы, ДО, групповые операции | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |14 января | ||
+ | | style="width: 35%"| Задачи на запросы на отрезках | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1ulPGkIaeNwqL0Yx3OwhHCOn8klFHSomk/view?usp=sharing <code>65696e</code>] | ||
+ | | style="width: 65%"| Задачи LCA и LA, метод четырёх русских | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |19 января | ||
+ | | style="width: 35%"| Задачи на запросы на деревьях и многомерные запросы | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1ZfMhzfDXtxFk-6aHIH9R8b17J37jdnp_/view?usp=sharing <code>674465</code>] | ||
+ | | style="width: 65%"| Персистентные структуры данных, определение, массив и ДД | ||
+ | |- | ||
+ | | 21 января | ||
+ | | colspan="3" style="background-color:#ecf4ff;" | Короткий контест №3 | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |26 января | ||
+ | | style="width: 35%"| Задачи на персистентные структуры данных | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1_-w7DjBixQm8ILqPB1hqQiSKJ2QwHdSS/view?usp=sharing <code>727073</code>] | ||
+ | | style="width: 65%"| Частично персистентное дерево поиска без штрафов по времени и памяти | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |28 января | ||
+ | | style="width: 35%"| Разные несложные задачи по ДП | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1E1XMSrg20muSeagUAFFzFIfJYTVkQ8vt/view?usp=sharing <code>2f636f</code>] | ||
+ | | style="width: 65%"| Эвристические ускорения в алгоритмах полного перебора, метод ветвей и границ | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |2 февраля | ||
+ | | style="width: 35%"| Задачи на перебор и сложное ДП: n указателей, разделяй и властвуй | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/11gxPkx1vCiAgxbiHCgdn_X94JC5ieUaa/view?usp=sharing <code>6d6d65</code>] | ||
+ | | style="width: 65%"| Генерация комбинаторных объектов по номеру и наоборот, mitm, восстановление ответа в НОП с линейной памятью | ||
+ | |- | ||
+ | | 4 февраля | ||
+ | | colspan="3" style="background-color:#ecf4ff;" | Короткий контест №4 | ||
+ | |- | ||
+ | | 9 февраля | ||
+ | | colspan="2" style="background-color:#ffeae9;" |Разбор домашнего задания №4 | ||
+ | | Асимптотические ускорения полного перебора, перебор в антагонистических играх, альфа-бета отсечение | ||
+ | |- | ||
+ | | style="white-space: nowrap;" | 11 февраля | ||
+ | | style="width: 35%"| Задачи на mitm и OR-свёртку, задачи на графы | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1vlodLQDVb7vzavEDRGR8epg4pyA8einT/view?usp=sharing <code>6e7473</code>] | ||
+ | | style="width: 65%"| BFS и DFS, поиск мостов и точек сочленения, компоненты вершинной и рёберной двусвязности | ||
+ | |- | ||
+ | | style="white-space: nowrap;" | 16 февраля | ||
+ | | style="width: 35%"| Задачи на графы | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/15DrHA1lcOLyCns-BiTXi4e2zwy22F4IW/view?usp=sharing <code>2f6168</code>]<br>[https://drive.google.com/file/d/1Ya1pPCssOHJHYBipQqp6n2AT_K_kvsOK/view?usp=sharing <code>336c64</code>] | ||
+ | | style="width: 65%"| Поиск цикла в графе, топсорт, компоненты сильной связности, 2-SAT | ||
+ | |- | ||
+ | | style="white-space: nowrap;" | 18 февраля | ||
+ | | style="width: 35%"| Ещё немного задач на графы | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1WeT_ZyUGWe9xFEjKCVPhOQlICUwQBpLL/view?usp=sharing <code>6a2f73</code>] | ||
+ | | style="width: 65%"| Кратчайшие пути во взвешенных графах | ||
+ | |- | ||
+ | | 25 февраля | ||
+ | | colspan="2" style="background-color:#ffeae9;" |Разбор домашнего задания №5 | ||
+ | | Миностовы. Прим, Крускал, Борувка, критерии оптимальности | ||
+ | |- | ||
+ | | style="white-space: nowrap;" | 2 марта | ||
+ | | style="width: 35%"| Задачи на кратчайшие пути и минимальные остовы | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1KBokE5NFl0KbNAS5tJQ6j3TrGhnX5bBK/view?usp=sharing <code>65616c</code>] | ||
+ | | style="width: 65%"| Система непересекающихся множеств | ||
+ | |- | ||
+ | | 4 марта | ||
+ | | colspan="3" | Разговор про архитектуру и сервисы | ||
+ | |- | ||
+ | | style="white-space: nowrap;" | 9 марта | ||
+ | | style="width: 35%"| Задачи на миностовы и СНМ | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1CVIsP3RIaQy6TxGL-imgzud6a22czafv/view?usp=sharing <code>735f61</code>] | ||
+ | | style="width: 65%"| Графы во внешней памяти. Задача ранжирования списка | ||
+ | |- | ||
+ | | style="white-space: nowrap;" | 11 марта | ||
+ | | style="width: 35%"| Задачи на графы во внешней памяти | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1Ybph0ZHbCPBMQhvNAkhA44N2exJ_nTNS/view?usp=sharing <code>72655f</code>] | ||
+ | | style="width: 65%"| Паросочетания в двудольном графе. Алгоритм Куна, теорема Кёнига-Эгервари, теорема Дилворта | ||
+ | |- | ||
+ | | 16 марта | ||
+ | | colspan="2" style="background-color:#ffeae9;" |Разбор домашнего задания №6 | ||
+ | | Задача о максимальном потоке. Две постановки в виде линейной задачи, их эквивалентность. Теорема Форда-Фалкерсона. | ||
+ | |- | ||
+ | | 18 марта | ||
+ | | colspan="3" style="background-color:#ecf4ff;" | Бонусный контест №2 | ||
+ | |- | ||
+ | | style="white-space: nowrap;" | 23 марта | ||
+ | | style="width: 35%"| Задачи на простые паросочетания и потоки | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1xGp6CeJuLs3wDLAVZLkKoB0Z9IiNVd0M/view?usp=sharing <code>646572</code>] | ||
+ | | style="width: 65%"| Полиномиальные алгоритмы поиска максимального потока | ||
+ | |- | ||
+ | | style="white-space: nowrap;" | 25 марта | ||
+ | | style="width: 35%"| Сложные задачи на паросочетания и потоки | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1bF4JRSx9mRlZ_fnQTnjC9sYj6iJVZjEm/view?usp=sharing <code>70795f</code>] | ||
+ | | style="width: 65%"| Стоимостной поток, определение, жадный алгоритм, критерий оптимальности | ||
+ | |- | ||
+ | |} | ||
+ | |||
+ | |||
+ | === 4 модуль === | ||
+ | {| role="presentation" class="mw-collapsible wikitable" | ||
+ | ! Дата | ||
+ | ! Семинар | ||
+ | ! Листочек | ||
+ | ! Лекция | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |8 апреля | ||
+ | | style="width: 35%"| Задачи на стоимостной поток | ||
+ | | style="white-space: nowrap;" |[https://drive.google.com/file/d/1xBQOGFnDiDrfWbKMBqdJzb-VULhDUwv9/view?usp=sharing <code>63686f</code>] | ||
+ | | style="width: 65%"| Строки | ||
+ | |- | ||
+ | | 13 апреля | ||
+ | | colspan="2" style="background-color:#ffeae9;" |Разбор домашнего задания №7 | ||
+ | | Ахо-Корасик и сжатый бор | ||
+ | |- | ||
+ | | 15 апреля | ||
+ | | colspan="3" style="background-color:#ecf4ff;" | Короткий контест №5 | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |20 апреля | ||
+ | | style="width: 35%"| Задачи на строки и Ахо-Корасик | ||
+ | | style="white-space: nowrap;" | [https://drive.google.com/file/d/1TqnXQa5HTJMN02DG2FJGstDOe-QSsGX8/view?usp=sharing <code>6e6b79</code>] | ||
+ | | style="width: 65%"| Суффиксное дерево, алгоритм Укконена | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |22 апреля | ||
+ | | style="width: 35%"| Задачи на суффиксные структуры | ||
+ | | style="white-space: nowrap;" | [https://drive.google.com/file/d/1jnJ8P9QP1oJ-xKT-3ODvdif1HA4OGc1u/view?usp=sharing <code>5f616e</code>] | ||
+ | | style="width: 65%"| Автоматы и РВ, принадлежность языку, эквивалетноность автоматов | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |27 апреля | ||
+ | | style="width: 35%"| Задачи на РВ, эквивалетность автоматных и регулярных языков | ||
+ | | style="white-space: nowrap;" | [https://drive.google.com/file/d/1xj6QSlIj-yu4d_Cs178HH-NazAs0p5dY/view?usp=sharing <code>645f73</code>] | ||
+ | | style="width: 65%"| Минимизация ДКА | ||
+ | |- | ||
+ | | 29 апреля | ||
+ | | colspan="3" style="background-color:#ecf4ff;" | Короткий контест №6 | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |11 мая | ||
+ | | style="width: 35%"| Машина Тьюринга | ||
+ | | style="white-space: nowrap;" | [https://drive.google.com/file/d/1EpBTu1qr-Xw3BDch9tCG8mMO_bfEM0xc/view?usp=sharing <code>717569</code>] | ||
+ | | style="width: 65%"| Классы P, NP и NP-c, теорема Кука-Левина, NP-полнота некоторых задач | ||
+ | |- | ||
+ | | 13 мая | ||
+ | | colspan="3" | Разговор про MapReduce | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |18 мая | ||
+ | | style="width: 35%"| Задачи на языки, машину тьюринга и NP-полноту | ||
+ | | style="white-space: nowrap;" | [https://drive.google.com/file/d/1gPbUQECqtbhvsPk6FcKQGCEqy0jWF7gZ/view?usp=sharing <code>717569</code>] | ||
+ | | style="width: 65%"| Сложные примеры доказательства NP-полноты, классы PSPACE и EXPTIME, BPP, RP, ZP. | ||
+ | |- | ||
+ | | 20 мая | ||
+ | | colspan="2" style="background-color:#ffeae9;" |Подготовка к КР | ||
+ | | Теоретико-числовые алгоритмы: линейное решето, первообразный корень, дискретное логарифмирование, ро-метод полларда | ||
+ | |- | ||
+ | | 25 мая | ||
+ | | colspan="2" style="background-color:#ffeae9;" |Разбор домашнего задания №8 | ||
+ | | ¯\_(ツ)_/¯ | ||
+ | |- | ||
+ | | 27 мая | ||
+ | | colspan="3" style="background-color:#ecf4ff;" | Контрольная работа | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |1 июня | ||
+ | | style="width: 35%"| Разбор контрольной и ещё немного тч | ||
+ | | style="white-space: nowrap;" | [https://drive.google.com/file/d/1gPbUQECqtbhvsPk6FcKQGCEqy0jWF7gZ/view?usp=sharing <code>717569</code>] | ||
+ | | style="width: 65%"| Тест Миллера-Рабина | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |3 июня | ||
+ | | style="width: 35%"| Задачи на ТЧ и протоколы коммуникации | ||
+ | | style="white-space: nowrap;" | [https://drive.google.com/file/d/12QRKeofiLyB0O7-hjCNCJxlehFLkXedR/view?usp=sharing <code>717569</code>] | ||
+ | | style="width: 65%"| Шифрование с открытым ключом, алгоритм RSA, цифровая подпись | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |8 июня | ||
+ | | style="width: 35%"| Алгоритм Карацубы, оценка сложности через дерево рекурсии, мастер-теорема | ||
+ | | style="white-space: nowrap;" | [https://drive.google.com/file/d/15D9xuBaa2iKLOnaXKkabB2rrQvC5_h9B/view?usp=sharing <code>717569</code>] | ||
+ | | style="width: 65%"| Быстрое преобразование Фурье | ||
+ | |- | ||
+ | | 10 июня | ||
+ | | colspan="3" style="background-color:#ecf4ff;" | Бонусный контест №3 | ||
+ | |- | ||
+ | | 15 июня | ||
+ | | colspan="2" style="background-color:#ffeae9;" |Разбор домашнего задания №9 | ||
+ | | Передача данных: коды обнаруживающие и восстанавливающие ошибки | ||
+ | |- | ||
+ | | style="white-space: nowrap;" |17 июня | ||
+ | | style="width: 35%"| Задачи на БПФ | ||
+ | | style="white-space: nowrap;" | [https://drive.google.com/file/d/1QyuYq_YIAg18y7su4r02AV5wP9A9w-e7/view?usp=sharing <code>717569</code>] | ||
+ | | style="width: 65%"| Эвристические методы оптимизации | ||
|- | |- | ||
|} | |} | ||
Строка 160: | Строка 385: | ||
Устно листки сдаются преподавателям и ассистентам в присутственные часы. Таблица для записи на консультации [https://www.youtube.com/watch?v=dQw4w9WgXcQ sheets.google.com] | Устно листки сдаются преподавателям и ассистентам в присутственные часы. Таблица для записи на консультации [https://www.youtube.com/watch?v=dQw4w9WgXcQ sheets.google.com] | ||
− | Листки в электронном виде отправляются в систему [https://classroom.google.com Google Classroom] (инвайт: <code> | + | Листки в электронном виде отправляются в систему [https://classroom.google.com Google Classroom] (инвайт: <code>7a66mfc</code>). Принимается только TeX — нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки); решения, написанные в MS Word и подобных программах и т.д. Решения можно отправлять несколько раз — проверяться будет последнее отправленное. |
=== Общие предположения, которыми можно пользоваться в задачах === | === Общие предположения, которыми можно пользоваться в задачах === | ||
Строка 168: | Строка 393: | ||
=== Список листков === | === Список листков === | ||
+ | |||
+ | {| class="wikitable" | ||
+ | |- | ||
+ | ! style="text-align:center;"| № !! Дедлайн !! Темы !! Листок !! Пояснения | ||
+ | |- | ||
+ | | colspan="5" style="text-align: center; background-color:#dae8fc;" | 2 модуль | ||
+ | |- | ||
+ | | style="text-align:center;"| 1 || Полночь с 23 на 24 ноября || Вероятности и математическое ожидание || [https://drive.google.com/file/d/1PuoS9Kf56UGOBxbOJJXuTSOiSTi6JI-C/view?usp=sharing 1PuoS9] || | ||
+ | |- | ||
+ | | style="text-align:center;"| 2 || Полночь с 7 на 8 декабря || Сортировки, простые структуры данных и кучи || [https://drive.google.com/file/d/1MgD2mwlpGxkw-z0CzkRy30PSiy0-kApI/view?usp=sharing 1MgD2m] ||| | ||
+ | |- | ||
+ | | style="text-align:center;"| 3 || Полночь с 19 на 20 декабря || Фибоначчиевые кучи, хеши и деревья поиска || [https://drive.google.com/file/d/12Xt1dCPc8edJE1dS-B6mzqYBuNFuiUu3/view?usp=sharing 12Xt1d] ||| | ||
+ | |- | ||
+ | | colspan="5" style="text-align: center; background-color:#dae8fc;" | 3 модуль | ||
+ | |- | ||
+ | | style="text-align:center;"| 4 || Полночь с 1 на 2 февраля || Структуры данных || [https://drive.google.com/file/d/1PQkaajg92I7-hA2qRVeN0GneJkdudHmh/view?usp=sharing 1PQkaa] ||| | ||
+ | |- | ||
+ | | style="text-align:center;"| 5 || Полночь с 24 на 25 февраля || Динамическое программирование, перебор и метод meet-in-the-middle | ||
+ | || [https://drive.google.com/file/d/17qBZ6yolMZ1Q0ofolOHeoSB9u1lcUfR1/view?usp=sharing 17qBZ6] ||| | ||
+ | |- | ||
+ | | style="text-align:center;"| 6 || Полночь с 15 на 16 марта || Обходы графов, кратчайшие расстояния и остовные деревья | ||
+ | || [https://drive.google.com/file/d/1BULcwnoQ9rFD04FKtQRhtZJHr0JclQjr/view?usp=sharing 1BULcw] ||| | ||
+ | |- | ||
+ | | colspan="5" style="text-align: center; background-color:#dae8fc;" | 4 модуль | ||
+ | |- | ||
+ | | style="text-align:center;"| 7 || Полночь с 12 на 13 апреля || Паросочетания и потоки | ||
+ | || [https://drive.google.com/file/d/1HwONtdlHrU65QkRVBQx7a0D9q1Wi6AZf/view?usp=sharing 1HwONt] ||| | ||
+ | |- | ||
+ | | style="text-align:center;"| 8 || Полночь с 24 на 25 мая || Строки и языки | ||
+ | || [https://drive.google.com/file/d/1kMXCqy_pnvTGIMGXzIkklIoM8N5cB0HJ/view?usp=sharing 1kMXCq] ||| | ||
+ | |- | ||
+ | |} | ||
+ | |||
+ | == Короткие контесты == | ||
+ | |||
+ | Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста). | ||
+ | |||
+ | {| class="wikitable" | ||
+ | |- | ||
+ | ! style="text-align:center;"| № !! Дата !! Ссылка !! Дорешивать | ||
+ | |- | ||
+ | | colspan="4" style="text-align: center; background-color:#dae8fc;" | 2 модуль | ||
+ | |- | ||
+ | | style="text-align:center;"| 1 || 5 ноября 2020 || [https://official.contest.yandex.ru/contest/21895/enter/ 21895] || полночь с 23 на 24 декабря | ||
+ | |- | ||
+ | | style="text-align:center;"| 2 || 19 ноября 2020 || [https://official.contest.yandex.ru/contest/22752/enter 22752] || полночь с 23 на 24 декабря | ||
+ | |- | ||
+ | | colspan="4" style="text-align: center; background-color:#dae8fc;" | 3 модуль | ||
+ | |- | ||
+ | | style="text-align:center;"| 3 || 21 января 2021 || [https://official.contest.yandex.ru/contest/24514/enter/ 24514] || | ||
+ | |- | ||
+ | | style="text-align:center;"| 4 || 4 февраля 2021 || [https://official.contest.yandex.ru/contest/24808/enter 24808] || | ||
+ | |- | ||
+ | | colspan="4" style="text-align: center; background-color:#dae8fc;" | 4 модуль | ||
+ | |- | ||
+ | | style="text-align:center;"| 5 || 15 апреля 2021 || [https://official.contest.yandex.ru/contest/26747/enter 26747] || | ||
+ | |- | ||
+ | | style="text-align:center;"| 6 || 29 апреля 2021 || [https://official.contest.yandex.ru/contest/27185/enter 27185] || | ||
+ | |- | ||
+ | |} | ||
+ | |||
+ | == Длинные контесты == | ||
+ | |||
+ | {| class="wikitable" | ||
+ | ! Дедлайн | ||
+ | ! Темы | ||
+ | ! Ссылка | ||
+ | |- | ||
+ | | colspan="3" style="text-align: center; background-color:#dae8fc;" | 2 модуль | ||
+ | |- | ||
+ | | полночь с 28 на 29 ноября | ||
+ | | Вероятности, упорядоченные данные, структуры данных | ||
+ | | [https://official.contest.yandex.ru/contest/21961 21961] | ||
+ | |- | ||
+ | | полночь с 20 на 21 декабря | ||
+ | | Хеши и деревья поиска | ||
+ | | [https://official.contest.yandex.ru/contest/23375 23375] | ||
+ | |- | ||
+ | | colspan="3" style="text-align: center; background-color:#dae8fc;" | 3 модуль | ||
+ | |- | ||
+ | | полночь с 24 на 25 февраля | ||
+ | | Cтруктуры данных, запросы на отрезках | ||
+ | | [https://official.contest.yandex.ru/contest/24924 24924] | ||
+ | |- | ||
+ | | полночь с 10 на 11 мая | ||
+ | | Ддинамика, перебор, графы | ||
+ | | [https://official.contest.yandex.ru/contest/26746 26746] | ||
+ | |- | ||
+ | | colspan="3" style="text-align: center; background-color:#dae8fc;" | 4 модуль | ||
+ | |- | ||
+ | |} | ||
== Экзамены == | == Экзамены == | ||
Строка 178: | Строка 494: | ||
=== Изученные темы: === | === Изученные темы: === | ||
==== 2 модуль ==== | ==== 2 модуль ==== | ||
+ | <div class="toccolours mw-collapsible mw-collapsed" style=" overflow:auto;"> | ||
+ | # Виды задач, сильно-, слабо-, и псевдополиномиальность: [https://www.epfl.ch/labs/disopt/wp-content/uploads/2018/09/algorithms.pdf https://www.epfl.ch/labs/disopt/wp-content/uploads/2018/09/algorithms.pdf] | ||
+ | # Ликбез по теории вероятностей | ||
+ | ## Кормен, приложение В "Комбинаторика и теория вероятности", c 1235 | ||
+ | ## [https://drive.google.com/file/d/1K2hRjwDEsHIWduJ1p5IPqYVmdHuahCVS/view Памятка по основным определениям] | ||
+ | # Индикаторная случайная величина: Кормен, раздел 5.2, с 144. | ||
+ | # Методы решения рекуррентных соотношений: Кормен, гл. 4, разделы 4.3-4.5 (со стр. 108) | ||
+ | # Модель вычислений во внешней памяти, сортировка слиянием во внешней памяти: [https://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_во_внешней_памяти._Базовые_конструкции https://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_во_внешней_памяти._Базовые_конструкции] | ||
+ | # Двоичная куча, сортировки, порядковые статистики | ||
+ | ## Кормен, часть 2 "Сортировка и порядковая статистика" с. 173 | ||
+ | ## [https://neerc.ifmo.ru/wiki/index.php?title=Двоичная_куча https://neerc.ifmo.ru/wiki/index.php?title=Двоичная_куча] | ||
+ | # Невозможность сортировки быстрее n log n: Кормен, начало главы "Сортировка за линейное время", стр. 220 | ||
+ | # Фибоначчиевы кучи | ||
+ | ## Кормен, гл. 19, с 542 | ||
+ | ## [https://neerc.ifmo.ru/wiki/index.php?title=Фибоначчиева_куча https://neerc.ifmo.ru/wiki/index.php?title=Фибоначчиева_куча] | ||
+ | # Биномиальные кучи: [https://neerc.ifmo.ru/wiki/index.php?title=Биномиальная_куча https://neerc.ifmo.ru/wiki/index.php?title=Биномиальная_куча] | ||
+ | # Хеширование и хеш-таблицы | ||
+ | ## Кормен, гл. 11, с. 285 | ||
+ | ## [http://neerc.ifmo.ru/wiki/index.php?title=Разрешение_коллизий http://neerc.ifmo.ru/wiki/index.php?title=Разрешение_коллизий] | ||
+ | # Фильтр Блума: [http://neerc.ifmo.ru/wiki/index.php?title=Фильтр_Блума http://neerc.ifmo.ru/wiki/index.php?title=Фильтр_Блума] | ||
+ | # Амортизационный анализ: Кормен, гл. 17, с 487 | ||
+ | # Бинарные деревья поиска: Кормен, гл. 12, c 319 | ||
+ | # Декартово дерево | ||
+ | ## [https://neerc.ifmo.ru/wiki/index.php?title=Декартово_дерево https://neerc.ifmo.ru/wiki/index.php?title=Декартово_дерево] | ||
+ | ## [https://neerc.ifmo.ru/wiki/index.php?title=Декартово_дерево_по_неявному_ключу https://neerc.ifmo.ru/wiki/index.php?title=Декартово_дерево_по_неявному_ключу] | ||
+ | # B-деревья | ||
+ | ## Кормен, гл.18, стр. 521 | ||
+ | ## [http://neerc.ifmo.ru/wiki/index.php?title=B-дерево http://neerc.ifmo.ru/wiki/index.php?title=B-дерево] | ||
+ | # 2-3-деревья: [http://neerc.ifmo.ru/wiki/index.php?title=2-3_дерево http://neerc.ifmo.ru/wiki/index.php?title=2-3_дерево] | ||
+ | # Стек и очередь с минимумом: [https://e-maxx.ru/algo/stacks_for_minima https://e-maxx.ru/algo/stacks_for_minima] | ||
+ | # Дек на 3 стеках: [https://neerc.ifmo.ru/wiki/index.php?title=Дек https://neerc.ifmo.ru/wiki/index.php?title=Дек] | ||
+ | |||
+ | </div> | ||
== Преподаватели и ассистенты == | == Преподаватели и ассистенты == |
Текущая версия на 14:14, 25 июня 2021
Лектор: Глеб Олегович Евстропов
Важные ссылки | ||
---|---|---|
Текущая успеваемость html-версия |
Google.Classroom инвайт: 7a66mfc
|
Запись на консультации |
Содержание
Формула выставления итоговой оценки
2, 5 модули: Оитог = 0.375 · Оконтесты + 0.325 · Oлистки + 0.3 · Oэкз + Oбонус
3, 4 модули: Оитог = 0.3 · Оконтесты + 0.25 · Oлистки + 0.15 · OКР + 0.3 · Oэкз + Oбонус |
-
Оконтесты вычисляется по формуле:
Оконтесты = 10 · ( КК + ДК + БЗ ), где: ОЗ - поправка ОЗ - КК — баллы за короткие контесты
- ДК — баллы за длинные контесты (исключая бонусные задачи)
- БЗ — баллы за бонусные задачи в длинных контестах
- ОЗ — общее число задач во всех контестах (исключая бонусные задачи)
- Поправка по умолчанию равна нулю и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.
Виды контестов:
- Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
- Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные.
- Олистки вычисляется по формуле:
Олистки = 10 · количество решённых задач количество обязательных задач - поправка Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов, на консультациях ассистентам.
- В течение каждого модуля предполагается по одной контрольной работе (так было до перехода в онлайн). За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться ОКР. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
- За экзамен студент получает оценку от 0 до 10, эта оценка будет являться Оэкз.
- Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.
Итоговая оценка округляется арифметически (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).
Лекции и семинары
2 модуль
Дата | Семинар | Листочек | Лекция |
---|---|---|---|
27 октября | Понятие асимптотического времени работы алгоритма. Сильно-, слабо- и псевдополиномиальное время работы. Обозначения O, o, Ω, ω | 687474
|
Знакомство со структурой курса и системой выставления оценок.Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность |
29 октября | Задачи на теорию вероятностей, конечные вероятностные пространства, геометрическая вероятность | 70733a
|
Случайные величины. Математическое ожидание, дисперсия, линейность, индикаторные величины. |
3 ноября | Задачи на случайные величины и математическое ожидание | 2f2f77
|
RAM-модель, доказательство корректности работы алгоритмов |
5 ноября | Короткий контест №1 | ||
10 ноября | Сортировки сравнениями, доказательство времени работы по индукции, поиск порядковой статистики. Бинарный поиск. | 77772e
|
Нижняя оценка на сортировку сравнениями, сортировки чисел, сортировка случайных чисел |
12 ноября | Задачи на сортировки и порядковые статистики | 726564
|
Модель вычислений во внешней памяти, алгоритмы сортировки во внешней памяти |
17 ноября | Простые структуры данных и задачи на них. Реализация во внешней памяти | 646974
|
Двоичная и k-ичная куча. Амортизационный анализ методом кредитов. Слияние куч. Сет для бедных. Биномиальна куча. |
19 ноября | Короткий контест №2 | ||
24 ноября | Разбор домашнего задания №1 | Амортизационный анализ методом потенциалов. Очередь через два стека, дек через три стека, динамический массив, деамортизация. | |
26 ноября | Задачи на кучи и амортизационный анализ | 2e636f
|
Фибоначчиева куча |
1 декабря | Задачи на кучи и амортизационный анализ (2) | 6d2f72
|
Хеширование. Постановка задачи, полиномиальный хеш, лемма Шварца-Зиппеля. |
3 декабря | Разговор про эффективный код | ||
8 декабря | Разбор домашнего задания №2 | Хеш-таблицы. Цепочки и открытая адресация, масштабирование хеш-таблиц. Совершенное хеширование, фильтры Блума. | |
10 декабря | Задачи на хеши и хеш-таблицы | 2f416e
|
Бинарные деревья поиска. Сбалансированные деревья, декартово дерево. Декартово дерево по неявному ключу. |
15 декабря | Задачи на бинарные деревья поиска | 696d61
|
Дерево Ван Эмде Боаса |
17 декабря | Бонусный контест №1 |
3 модуль
Дата | Семинар | Листочек | Лекция |
---|---|---|---|
12 января | Самобалансирующиеся деревья Тарьяна-Слейтера | 6c7342
|
Запросы на отрезках: разреженные таблицы, ДО, групповые операции |
14 января | Задачи на запросы на отрезках | 65696e
|
Задачи LCA и LA, метод четырёх русских |
19 января | Задачи на запросы на деревьях и многомерные запросы | 674465
|
Персистентные структуры данных, определение, массив и ДД |
21 января | Короткий контест №3 | ||
26 января | Задачи на персистентные структуры данных | 727073
|
Частично персистентное дерево поиска без штрафов по времени и памяти |
28 января | Разные несложные задачи по ДП | 2f636f
|
Эвристические ускорения в алгоритмах полного перебора, метод ветвей и границ |
2 февраля | Задачи на перебор и сложное ДП: n указателей, разделяй и властвуй | 6d6d65
|
Генерация комбинаторных объектов по номеру и наоборот, mitm, восстановление ответа в НОП с линейной памятью |
4 февраля | Короткий контест №4 | ||
9 февраля | Разбор домашнего задания №4 | Асимптотические ускорения полного перебора, перебор в антагонистических играх, альфа-бета отсечение | |
11 февраля | Задачи на mitm и OR-свёртку, задачи на графы | 6e7473
|
BFS и DFS, поиск мостов и точек сочленения, компоненты вершинной и рёберной двусвязности |
16 февраля | Задачи на графы | 2f6168 336c64
|
Поиск цикла в графе, топсорт, компоненты сильной связности, 2-SAT |
18 февраля | Ещё немного задач на графы | 6a2f73
|
Кратчайшие пути во взвешенных графах |
25 февраля | Разбор домашнего задания №5 | Миностовы. Прим, Крускал, Борувка, критерии оптимальности | |
2 марта | Задачи на кратчайшие пути и минимальные остовы | 65616c
|
Система непересекающихся множеств |
4 марта | Разговор про архитектуру и сервисы | ||
9 марта | Задачи на миностовы и СНМ | 735f61
|
Графы во внешней памяти. Задача ранжирования списка |
11 марта | Задачи на графы во внешней памяти | 72655f
|
Паросочетания в двудольном графе. Алгоритм Куна, теорема Кёнига-Эгервари, теорема Дилворта |
16 марта | Разбор домашнего задания №6 | Задача о максимальном потоке. Две постановки в виде линейной задачи, их эквивалентность. Теорема Форда-Фалкерсона. | |
18 марта | Бонусный контест №2 | ||
23 марта | Задачи на простые паросочетания и потоки | 646572
|
Полиномиальные алгоритмы поиска максимального потока |
25 марта | Сложные задачи на паросочетания и потоки | 70795f
|
Стоимостной поток, определение, жадный алгоритм, критерий оптимальности |
4 модуль
Дата | Семинар | Листочек | Лекция |
---|---|---|---|
8 апреля | Задачи на стоимостной поток | 63686f
|
Строки |
13 апреля | Разбор домашнего задания №7 | Ахо-Корасик и сжатый бор | |
15 апреля | Короткий контест №5 | ||
20 апреля | Задачи на строки и Ахо-Корасик | 6e6b79
|
Суффиксное дерево, алгоритм Укконена |
22 апреля | Задачи на суффиксные структуры | 5f616e
|
Автоматы и РВ, принадлежность языку, эквивалетноность автоматов |
27 апреля | Задачи на РВ, эквивалетность автоматных и регулярных языков | 645f73
|
Минимизация ДКА |
29 апреля | Короткий контест №6 | ||
11 мая | Машина Тьюринга | 717569
|
Классы P, NP и NP-c, теорема Кука-Левина, NP-полнота некоторых задач |
13 мая | Разговор про MapReduce | ||
18 мая | Задачи на языки, машину тьюринга и NP-полноту | 717569
|
Сложные примеры доказательства NP-полноты, классы PSPACE и EXPTIME, BPP, RP, ZP. |
20 мая | Подготовка к КР | Теоретико-числовые алгоритмы: линейное решето, первообразный корень, дискретное логарифмирование, ро-метод полларда | |
25 мая | Разбор домашнего задания №8 | ¯\_(ツ)_/¯ | |
27 мая | Контрольная работа | ||
1 июня | Разбор контрольной и ещё немного тч | 717569
|
Тест Миллера-Рабина |
3 июня | Задачи на ТЧ и протоколы коммуникации | 717569
|
Шифрование с открытым ключом, алгоритм RSA, цифровая подпись |
8 июня | Алгоритм Карацубы, оценка сложности через дерево рекурсии, мастер-теорема | 717569
|
Быстрое преобразование Фурье |
10 июня | Бонусный контест №3 | ||
15 июня | Разбор домашнего задания №9 | Передача данных: коды обнаруживающие и восстанавливающие ошибки | |
17 июня | Задачи на БПФ | 717569
|
Эвристические методы оптимизации |
Листки
Устно листки сдаются преподавателям и ассистентам в присутственные часы. Таблица для записи на консультации sheets.google.com
Листки в электронном виде отправляются в систему Google Classroom (инвайт: 7a66mfc
). Принимается только TeX — нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки); решения, написанные в MS Word и подобных программах и т.д. Решения можно отправлять несколько раз — проверяться будет последнее отправленное.
Общие предположения, которыми можно пользоваться в задачах
- Если в задаче говорится про запросы, то по умолчанию online
- Если не оговорено иное, можно использовать столько же памяти, сколько времени
- Если не оговорено иное, то можно ожидаемое амортизированное время с хешами
Список листков
№ | Дедлайн | Темы | Листок | Пояснения |
---|---|---|---|---|
2 модуль | ||||
1 | Полночь с 23 на 24 ноября | Вероятности и математическое ожидание | 1PuoS9 | |
2 | Полночь с 7 на 8 декабря | Сортировки, простые структуры данных и кучи | 1MgD2m | |
3 | Полночь с 19 на 20 декабря | Фибоначчиевые кучи, хеши и деревья поиска | 12Xt1d | |
3 модуль | ||||
4 | Полночь с 1 на 2 февраля | Структуры данных | 1PQkaa | |
5 | Полночь с 24 на 25 февраля | Динамическое программирование, перебор и метод meet-in-the-middle | 17qBZ6 | |
6 | Полночь с 15 на 16 марта | Обходы графов, кратчайшие расстояния и остовные деревья | 1BULcw | |
4 модуль | ||||
7 | Полночь с 12 на 13 апреля | Паросочетания и потоки | 1HwONt | |
8 | Полночь с 24 на 25 мая | Строки и языки | 1kMXCq |
Короткие контесты
Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
№ | Дата | Ссылка | Дорешивать |
---|---|---|---|
2 модуль | |||
1 | 5 ноября 2020 | 21895 | полночь с 23 на 24 декабря |
2 | 19 ноября 2020 | 22752 | полночь с 23 на 24 декабря |
3 модуль | |||
3 | 21 января 2021 | 24514 | |
4 | 4 февраля 2021 | 24808 | |
4 модуль | |||
5 | 15 апреля 2021 | 26747 | |
6 | 29 апреля 2021 | 27185 |
Длинные контесты
Дедлайн | Темы | Ссылка |
---|---|---|
2 модуль | ||
полночь с 28 на 29 ноября | Вероятности, упорядоченные данные, структуры данных | 21961 |
полночь с 20 на 21 декабря | Хеши и деревья поиска | 23375 |
3 модуль | ||
полночь с 24 на 25 февраля | Cтруктуры данных, запросы на отрезках | 24924 |
полночь с 10 на 11 мая | Ддинамика, перебор, графы | 26746 |
4 модуль |
Экзамены
Ссылки на материалы
Основные источники:
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ, [2013, 3 издание]
- neerc.ifmo.ru
Изученные темы:
2 модуль
- Виды задач, сильно-, слабо-, и псевдополиномиальность: https://www.epfl.ch/labs/disopt/wp-content/uploads/2018/09/algorithms.pdf
- Ликбез по теории вероятностей
- Кормен, приложение В "Комбинаторика и теория вероятности", c 1235
- Памятка по основным определениям
- Индикаторная случайная величина: Кормен, раздел 5.2, с 144.
- Методы решения рекуррентных соотношений: Кормен, гл. 4, разделы 4.3-4.5 (со стр. 108)
- Модель вычислений во внешней памяти, сортировка слиянием во внешней памяти: https://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_во_внешней_памяти._Базовые_конструкции
- Двоичная куча, сортировки, порядковые статистики
- Кормен, часть 2 "Сортировка и порядковая статистика" с. 173
- https://neerc.ifmo.ru/wiki/index.php?title=Двоичная_куча
- Невозможность сортировки быстрее n log n: Кормен, начало главы "Сортировка за линейное время", стр. 220
- Фибоначчиевы кучи
- Кормен, гл. 19, с 542
- https://neerc.ifmo.ru/wiki/index.php?title=Фибоначчиева_куча
- Биномиальные кучи: https://neerc.ifmo.ru/wiki/index.php?title=Биномиальная_куча
- Хеширование и хеш-таблицы
- Кормен, гл. 11, с. 285
- http://neerc.ifmo.ru/wiki/index.php?title=Разрешение_коллизий
- Фильтр Блума: http://neerc.ifmo.ru/wiki/index.php?title=Фильтр_Блума
- Амортизационный анализ: Кормен, гл. 17, с 487
- Бинарные деревья поиска: Кормен, гл. 12, c 319
- Декартово дерево
- B-деревья
- Кормен, гл.18, стр. 521
- http://neerc.ifmo.ru/wiki/index.php?title=B-дерево
- 2-3-деревья: http://neerc.ifmo.ru/wiki/index.php?title=2-3_дерево
- Стек и очередь с минимумом: https://e-maxx.ru/algo/stacks_for_minima
- Дек на 3 стеках: https://neerc.ifmo.ru/wiki/index.php?title=Дек
Преподаватели и ассистенты
Преподаватель | Подгруппа | Присутственные часы | Контакты |
---|---|---|---|
Преподаватели | |||
Глеб Евстропов | 201-1 | ||
Станислав Артюхин | |||
Григорий Резников | |||
Иван Смирнов | |||
Святослав Фельдшеров | |||
Глеб Третьяков | |||
Ассистенты | |||
Филипп Грибов | TBD | @grphil | |
Максим Деб Натх | TBD | @debnatkh | |
Александр Курилкин | TBD | @wrg0ababd | |
Никита Морозов | TBD | @madn_boi | |
Алексей Упирвицкий | TBD | @Aleks5d | |
Дамир Петров | TBD | @O442A4O3 |