https://www.wikicshse.ru/index.php?action=history&feed=atom&title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_2_%D0%9A%D0%9D%D0%90%D0%94_24%2F25 2026-06-06T17:12:24Z История изменений этой страницы в вики MediaWiki 1.45.3 https://www.wikicshse.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_2_%D0%9A%D0%9D%D0%90%D0%94_24/25&diff=942&oldid=prev 2024-10-22T06:46:34Z

<p>Migrated current public revision from wiki.cs.hse.ru</p> <p><b>Новая страница</b></p><div>[https://t.me/+wNPuVnDwe5U3NmEy Ссылка на чат курса]<br /> <br /> == Лекции и ДЗ ==<br /> <br /> Лектор: [https://www.hse.ru/org/persons/191485259 Куренков Владимир Вячеславович]<br /> <br /> Запись лекций:<br /> https://disk.yandex.ru/d/SYzrnC3HeOJIDA<br /> <br /> {| class=&quot;wikitable&quot;<br /> |-<br /> ! № !! Дата !! Тема !! ДЗ<br /> |-<br /> | 1 || 07.09 || Хэш-функция. || [https://official.contest.yandex.ru/contest/67753 ДЗ 1]<br /> |-<br /> | 2 || 10.09 || Z-функция. Префикс функция. || [https://official.contest.yandex.ru/contest/67809 ДЗ 2]<br /> |-<br /> | 3 || 14.09 || Суффиксный массив. || [https://official.contest.yandex.ru/contest/68181 ДЗ 3]<br /> |-<br /> | 4 || 17.09 || Бор. Алгоритм Ахо-Карасика || [https://official.contest.yandex.ru/contest/68182 ДЗ 4]<br /> |-<br /> | 5 || 21.09 || Метод имитации отжига. Перебор. || [https://official.contest.yandex.ru/contest/68699 ДЗ 5]<br /> |-<br /> | 6 || 24.09 || Задача нахождения максимального потока в транспортной сети. Алгоритмы: Форда-Фалкерсона, Эдмондса — Карпа. || -<br /> |-<br /> | 7 || 28.09 || Нахождение максимального паросочетания в двудольном графе: алгоритм Куна. || -<br /> |- <br /> | 8 || 01.10 || Алгоритм Диницы. || [https://official.contest.yandex.ru/contest/69235/standings ДЗ 6]<br /> |- <br /> | 9 || 05.10 || Сбалансированные деревья поиска. АВЛ - дерево. Splay - дерево. || -<br /> |- <br /> | 10 || 08.10 || Длинная арифметика. || [https://official.contest.yandex.ru/contest/69532/standings/ ДЗ 7]<br /> |- <br /> | 11 || 12.10 || Быстрое преобразование Фурье. || -<br /> |- <br /> | 12 || 15.10 || - || -<br /> |- <br /> | 13 || 19.10 || Контрольная работа в формате теста. || [https://official.contest.yandex.ru/contest/69741/ К.Р.]<br /> |- <br /> | 14 || 22.10 || Запасная лекция. || -<br /> |}<br /> <br /> == Система оценки ==<br /> <br /> Итоговая оценка, для ЭАД:<br /> 0.4 * ДЗ + 0.15 Коллоквиум + 0.15 * К.Р. + 0.1 * max(Семинары, Бонусное д.з.) + 0.2 * Экзамен<br /> <br /> Количество домашних контестов может измениться. Гарантируется, что общий вклад дз в итоговую оценку 0,4 и что у всех блоков дз будет одинаковый вес.<br /> <br /> <br /> Таблица с промежуточными результатами:<br /> <br /> == Бонусные баллы ==<br /> <br /> Бонусные баллы можно получить следующим образом:<br /> <br /> * Бонусные баллы за 1/8 финала ICPC<br /> <br /> <br /> == Выполнение ДЗ. Правила оценивания ==<br /> <br /> После каждой лекции выдается контест, как правило, состоящий из 10 задач. Дедлайн - в 23:59, дня, указанного в таблице. В течение недели после дедлайна разрешается дорешивать задачи домашнего контеста за половину стоимости.<br /> <br /> == К.Р. Общие положения ==<br /> <br /> https://official.contest.yandex.ru/contest/69741<br /> <br /> == Темы для Экзамена ==<br /> <br /> Будет предложено решить 5 задач за 1:30 - 2:00<br /> <br /> 1. Строки. Хэш функция, префикс функция, z-функция.<br /> <br /> 2. Строки. Бор.<br /> <br /> 3. Деревья поиска.<br /> <br /> 4. Паросочетания. Алгоритм Куна.<br /> <br /> 5. Сложная на любую из пройденных тем.<br /> <br /> == Темы для коллоквиума ==<br /> <br /> Хэш-функция. Полиномиальное хеширование.<br /> Применение: Количество разных подстрок.<br /> Поиск подстроки в строке. Сравнение подстрок.<br /> Палиндромность подстроки. Количество палиндромов.<br /> <br /> Z-функция. Префикс функция. Построение за линейное время.<br /> Применение: Поиск подстроки в строке.<br /> Количество различных подстрок в строке.<br /> Сжатие строки(Период строки). <br /> <br /> Алгоритм Ахо-Карасик. Построение дерева. Оценка трудоёмкости алгоритма. Применение.<br /> <br /> Суффиксный массив. Сортировка суффиксов. Оценка трудоёмкости алгоритма. Применение в задачах на строки. Поиск lcp.<br /> <br /> Задача построения максимального потока в сети.<br /> Алгоритм Форда-Фалкерсона построения максимального потока в сети. Оценка сложности алгоритма.<br /> Минимальный разрез сети. Величина разреза.<br /> Алгоритм Эдмондса-Карпа построения максимального потока в сети. Оценка сложности алгоритма.<br /> <br /> Нахождение максимального паросочетания в двудольном графе: алгоритм Куна. Оценка сложности алгоритма.<br /> <br /> Деревья поиска, их представление в компьютере. Алгоритм поиска элемента. Добавление элемента в дерево. Удаление элемента из дерева. АВЛ-деревья. Алгоритм добавления элемента и балансировки АВЛ-дерева. Оценка высоты АВЛ-дерева.</div>

imported>Vvkurenkov