|
|
| Строка 8: |
Строка 8: |
| | | | |
| | == Формула выставления итоговой оценки == | | == Формула выставления итоговой оценки == |
| − | В первый отчетный период, состоящий из 2 и 3 модулей 2016-17 учебного года будет использоваться следующая формула определения оценки: | + | В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки: |
| | | | |
| | 0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого. | | 0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого. |
| Строка 32: |
Строка 32: |
| | ! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) | | ! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) |
| | |- | | |- |
| − | | Длинный контест || Хеширование, сбалансированные деревья, прочие структуры данных || 23 января 2017 || 13 февраля 2017, дорешивание до 27 февраля 2017
| + | | Теоретические задачи || Введение в теорвер и анализ алгоритмов || || || |
| − | |-
| + | |
| − | | Теоретические задачи || Деревья отрезков, LCA, разное || 19 января 2017 || 2 февраля 2017 ||
| + | |
| − | |-
| + | |
| − | | Короткий контест || Разное || 18 января 2017 || 25 марта 2017 (дорешивание)
| + | |
| − | |-
| + | |
| − | | Теоретические задачи || Сбалансированные деревья поиска || 11 января 2017 || 25 января 2017 ||
| + | |
| − | |-
| + | |
| − | | Теоретические задачи || Фиб. пирамиды, хеширование, амортизационный анализ || 7 декабря 2016 || 21 декабря 2016 ||
| + | |
| − | |-
| + | |
| − | | Короткий контест || Разное || 30 ноября 2016 || 25 марта 2017 (дорешивание)
| + | |
| − | |-
| + | |
| − | | Теоретические задачи || Элементарные структуры и пирамиды || 25 ноября 2016 || 9 декабря 2016 ||
| + | |
| − | |-
| + | |
| − | | Длинный контест || Разное || 22 ноября 2016 || 6 декабря 2016, дорешивание до 20 декабря 2016
| + | |
| − | |-
| + | |
| − | | Теоретические задачи || Сортировки и порядковые статистики || 18 ноября 2016 || 2 декабря 2016 ||
| + | |
| − | |-
| + | |
| − | | Короткий контест || Разное || 16 ноября 2016 || 25 марта 2017 (дорешивание)
| + | |
| − | |-
| + | |
| − | | Теоретические задачи || Введение в теорвер и анализ алгоритмов || 11 ноября 2016 || 25 ноября 2016 || | + | |
| | |- | | |- |
| | |} | | |} |
| | | | |
| | == Лекции == | | == Лекции == |
| − |
| |
| − | * 2 ноября 2016. Структура курса, его концепция и задачи. Введение в теорию вероятностей, понятие вероятностного пространства для случая конечного множества элементарных исходов. Условная вероятность, полная группа события. Понятие геометрической вероятности. '''[https://yadi.sk/i/HE2uuFrpyHXXE Заметки.]'''
| |
| − |
| |
| − | * 9 ноября 2016. Продолжение введения в теорию вероятностей. Понятие случайной величины и математического ожидания в случае конечно множества элементарных исходов. Индикаторные случайные величины. Математическое ожидание случайной величины и его линейность. Неравенства Маркова и Чебышёва. Примеры вероятностного анализа простых случайных структур.
| |
| − |
| |
| − | * 11 ноября 2016. Методы доказательства корректности алгоритмов на примере квадратичных сортировок. Тривиальные методы оценки времени работы. Индуктивный метод доказательства рекуррентных оценок сложности. Сортировка слиянием и быстрая сортировка. Поиск порядковой статистики.
| |
| − |
| |
| − | * 18 ноября 2016. Нижняя оценка на сложность сортировки, использующей только сравнение элементов. Сортировка подсчётом, цифровая (поразрядная) сортировка, карманная сортировка. Линейность времени работы карманной сортировки на случайных данных. Метод бинарного поиска.
| |
| − |
| |
| − | * 23 ноября 2016. Элементарные структуры данных: массив, отсортированный массив, односвязный и двусвязный списки, стек, очередь, дек. Метод амортизационного анализа методом кредитов на примере сливаемых отсортированных массивов и реализации очереди через два стека. Двоичная и k-ичная кучи.
| |
| − |
| |
| − | * 2 декабря 2016. Техника приливания меньшего к большему для объединения двух куч. Биномиальные деревья и сливаемые пирамиды на их основе. Амортизационный анализ методом потенциалов, расширяемый массив, дек с минимумом на трёх стеках.
| |
| − |
| |
| − | * 7 декабря 2016. Фибоначчиевы пирамиды.
| |
| − |
| |
| − | * 7 декабря 2016. Хеширование, парадокс дней рождений, полиномиальный хеш и его применения.
| |
| − |
| |
| − | * 9 декабря 2016. Хеш-таблицы, открытая и закрытая адресация. Способы сканирования. Масштабирование размера и деамортизация оценок.
| |
| − |
| |
| − | * 16 декабря 2016. Сбалансированные деревья поиска. Декартово дерево. Декартово дерево по неявному ключу.
| |
| − |
| |
| − | * 11 января 2017. Задачи о запросах на отрезке. Префиксные суммы, разреженные таблицы, дерево отрезков.
| |
| − |
| |
| − | * 12 января 2017. Групповые операции в деревьях отрезков. Двумерные деревья отрезков.
| |
| − |
| |
| − | * 19 января 2017. Задача о наименьшем общем предке. Сведение к задаче минимума на отрезке. Алгоритм Фараха-Колтона и Бендера решения задачи минимума на отрезке.
| |
| − |
| |
| − | * 25 января 2017. Персистентные структуры данных. Персистентный стек, персистентный массив на основе дерева отрезков, персистентное декартово дерево и его основные операции.
| |
| − |
| |
| − | * 26 января 2017. Перебор комбинаторных объектов. Введение в динамическое программирование, построение объекта по номеру и получение номера по объекту. Динамическое программирование на подотрезках.
| |
| | | | |
| | == Семинары == | | == Семинары == |
| − |
| |
| − | * 2 ноября 2016. Некоторые необходимые обозначения и термины для описания времени работы (и других используемых ресурсов) алгоритма. Совместное решение '''[https://yadi.sk/i/7ZcuFsSWyHXd7 задач.]'''
| |
| − |
| |
| − | * 9 ноября 2016. Совместное решение комбинаторных и геометрических '''[https://yadi.sk/i/PvIzV8QRyiV9n задач]''' по теории вероятностей.
| |
| − |
| |
| − | * 11 ноября 2016. Приём '''[https://yadi.sk/i/xVmmyboeyiW43 задач]''' первого теоретического домашнего задания, темы: введение в теорию вероятностей, анализ алгоритмов.
| |
| − |
| |
| − | * 16 ноября 2016. Короткий личный '''[https://contest.yandex.ru/contest/3437/enter/ контест]'''.
| |
| − |
| |
| − | * 18 ноября 2016. Приём '''[https://yadi.sk/i/ecgtjaRTzHyYc задач]''' второго теоретического домашнего задания, темы: сортировки и порядковые статистики.
| |
| − |
| |
| − | * 23 ноября 2016. Теоретический семинар по методам тестирования и отладки программ.
| |
| − |
| |
| − | * 25 ноября 2016. Приём '''[https://yadi.sk/d/ypNSmk2332eJ6N задач]''' третьего теоретического домашнего задания, темы: элементарные структуры данных, пирамиды.
| |
| − |
| |
| − | * 30 ноября 2016. Короткий личный '''[https://contest.yandex.ru/contest/3518/enter/ контест]'''.
| |
| − |
| |
| − | * 2 декабря 2016. Разбор задач первого теоретического домашнего задания. Совместное решение '''[https://yadi.sk/i/ksHHKXJ232eJhV задач]''' для подготовки к контрольной работе.
| |
| − |
| |
| − | * 7 декабря 2016. Приём '''[https://yadi.sk/i/RoYQOe-032eJm9 задач]''' четвёртого теоретического домашнего задания, темы: фибоначчиевы пирамиды, хеширование, амортизационный анализ.
| |
| − |
| |
| − | * 9 декабря 2016. Разбор задач второго теоретического домашнего задания. '''[https://yadi.sk/i/zyx8ffL_3C5aTd Тест]''' для подготовки к контрольной работе.
| |
| − |
| |
| − | * 14 декабря 2016. Контрольная '''[https://yadi.sk/i/sAq04BzI3C5cRb работа]''' за второй модуль.
| |
| − |
| |
| − | * 16 декабря 2016. Разбор задач контрольной работы и третьего теоретического домашнего задания.
| |
| − |
| |
| − | * 21 декабря 2016. Показ работ первой контрольной, апелляции.
| |
| − |
| |
| − | * 11 января 2017. Приём '''[https://yadi.sk/i/nQaxYYC53C5otj задач]''' пятого теоретического домашнего задания, темы: сбалансированные деревья поиска, декартовы деревья.
| |
| − |
| |
| − | * 12 января 2017. Разбор задач четвёртого теоретического домашнего задания.
| |
| − |
| |
| − | * 18 января 2017. Короткий личный '''[https://contest.yandex.ru/contest/3721/enter/ контест]'''.
| |
| − |
| |
| − | * 19 января 2017. Приём '''[https://yadi.sk/i/nQaxYYC53C5otj задач]''' шестого теоретического домашнего задания, темы: запросы на отрезках, наименьший общий предок.
| |
| − |
| |
| − | * 25 января 2017. Теоретический семинар по методам оптимизации программ.
| |
| − |
| |
| − | * 26 января 2017. Разбор задач пятого теоретического домашнего задания. Совместное решение '''[https://yadi.sk/i/yph6ix7d3C5xir задач]''' на персистентные структуры.
| |
| | | | |
| | == Длинные контесты == | | == Длинные контесты == |
| | | | |
| − | ===Сортировки, порядковые статистики, элементарные структуры===
| |
| | | | |
| − | Ссылка на контест: [https://contest.yandex.ru/contest/3478/problems/ https://contest.yandex.ru/contest/3478/problems/].
| |
| − | Старт: 22 ноября в 21:00.
| |
| − |
| |
| − | Контест идет 2 недели + 3 часа, после чего можно будет сдавать задачи еще 2 недели, но с коэффициентом 0.5. Это будет отражено в баллах
| |
| − | за задачу в контесте.
| |
| − |
| |
| − | По первым двум задачам нужно пройти ревью. Это необходимое условие для получения баллов за остальные задачи. Ревью проводится
| |
| − | в системе [http://anytask.org/course/122 Anytask]. Перед отправкой задачи на ревью '''обязательно''' укажите в настройках свой логин в
| |
| − | контесте (тот, который вы зарегистрировали сами, а не тот, который был выдан в 1-ом модуле), если вы еще этого не сделали.
| |
| − |
| |
| − | В задачах с ревью используется другая схема тестирования. Компилируется 2 варианта вашего решения --- с включенными санитайзерами
| |
| − | и без. На маленьких тестах будет запускаться решение с санитайзерами.
| |
| − |
| |
| − | Полная строка компиляции (с санитайзерами):
| |
| − | clang++ -fsanitize=address,undefined -x c++ -std=c++14 -O2 -Wall -Werror
| |
| − |
| |
| − | Обратите внимание на -Werror --- компилятор не должен выдавать никаких предупреждений при компиляции. Стандарт С++14.
| |
| − |
| |
| − | ===Хеши, сбалансированные деревья, деревья отрезков и прочие структуры===
| |
| − |
| |
| − | Ссылка на контест: [https://contest.yandex.ru/contest/3744/enter/ https://contest.yandex.ru/contest/3744/enter/].
| |
| − | Старт: 23 января в 18:00.
| |
| − |
| |
| − | Контест идет 3 недели + 6 часов, после чего можно будет сдавать задачи еще 2 недели, но с коэффициентом 0.5. Обратите внимание, что в контесте 9 задач, но оценку 10 можно получить и за 8 из них (одна бонусная).
| |
| − |
| |
| − | По первым двум задачам необходимо пройти ревью в anytask, чтобы получить баллы за остальные задачи, как и в прошлом домашнем задании. Ревью должно быть зачтено к концу дорешивания контеста, т.е. за 5 недель, поэтому не затягивайте с его сдачей.
| |
| − |
| |
| − | По второй задаче также необходимо сдать устную часть лично Глебу: описание используемого алгоритма (т.е. дерева) с доказательством.
| |
| − |
| |
| − | Некоторые технические моменты по задачам:
| |
| − |
| |
| − | 1. В обеих задачах на ревью вам может потребоваться реализовать оператор =. Чтобы избежать распространенных ошибок, почитайте как это делать правильно здесь: [https://en.wikibooks.org/wiki/More_C++_Idioms/Copy-and-swap https://en.wikibooks.org/wiki/More_C++_Idioms/Copy-and-swap].
| |
| − |
| |
| − | 2. Если в первой задаче вы реализуете итераторы, то не нужно дублировать код для const и не-const итераторов, используйте шаблоны и/или наследование. Однако в этой задаче можно избежать необходимости писать свои итераторы, если правильно хранить данные.
| |
| − |
| |
| − | 3. Разберитесь в константности методов: [http://stackoverflow.com/questions/751681/meaning-of-const-last-in-a-c-method-declaration http://stackoverflow.com/questions/751681/meaning-of-const-last-in-a-c-method-declaration].
| |
| − |
| |
| − | 4. Разберитесь, в чем отличие списков инициализации конструктора от ининциализации в теле конструктора. А чтобы не дублировать код, ознакомьтесь с делегированием в конструкторах. Все это можно найти здесь: [http://en.cppreference.com/w/cpp/language/initializer_list http://en.cppreference.com/w/cpp/language/initializer_list].
| |
| − |
| |
| − | 5. В первых двух задачах запрещено использовать map/set, а также их unordered-аналоги. Все остальные контейнеры использовать можно. В остальных задачах разрешено все.
| |
| − |
| |
| − | 6. В первой задаче должна быть реализована именно хеш-таблица, используемый метод разрешения коллизий может быть любым.
| |
| − |
| |
| − | ===Динамическое программирование, meet in the middle===
| |
| − |
| |
| − | Ссылка на контест: [https://contest.yandex.ru/contest/4222/enter/ https://contest.yandex.ru/contest/4222/enter/].
| |
| − | Старт: 18 марта 15:00.
| |
| − | Этот контест идет в зачет 4 модуля.
| |
| − |
| |
| − | Контест идет 18 дней + 9 часов, т.е. дедлайн ночью с 5 на 6 апреля. После этого как обычно можно сдавать задачи еще 2 недели
| |
| − | с коэффициентом 0.5. Задача G стоит в 2 раза дороже остальных и чтобы получить баллы за остальные, сдавать ее необязательно. Однако чтобы получить за нее баллы, необходимо пройти ревью. Ревью должно быть зачтено к концу дорешивания контеста, поэтому не затягивайте с его сдачей.
| |
| − |
| |
| − | ===Остовы, обходы графов, строковые алгоритмы===
| |
| − | Ссылка на контест: [https://contest.yandex.ru/contest/4528/problems/ https://contest.yandex.ru/contest/4528/problems/].
| |
| − | Старт: 7 мая в 16:00.
| |
| − |
| |
| − | Контест идет 2 недели + 8 часов с дорешиванием еще 2 недели. По первой задаче необходимо пройти ревью в anytask, чтобы получить баллы за остальные задачи. Ревью должно быть зачтено к концу дорешивания.
| |
| − |
| |
| − | ===Потоки, геометрия, теория чисел===
| |
| − | Ссылка на контест: [https://contest.yandex.ru/contest/4605/problems/ https://contest.yandex.ru/contest/4605/problems/].
| |
| − | Старт: 6 июня в 00:00.
| |
| | | | |
| | == Рекомендуемая литература == | | == Рекомендуемая литература == |
| Строка 206: |
Строка 54: |
| | ! Преподаватель !! Подгруппа !! Присутственные часы | | ! Преподаватель !! Подгруппа !! Присутственные часы |
| | |- | | |- |
| − | | [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 161-1 || Среда, 13:40 - 15:10, ауд. 505 | + | | [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 || |
| | |- | | |- |
| − | | [https://www.hse.ru/org/persons/137640601 Павел Мельничук] || 161-2 || | + | | [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 || |
| | |- | | |- |
| − | | [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 163-1 || | + | | [https://www.hse.ru/org/persons/ Иван Смирнов || 173-1 || |
| | |- | | |- |
| − | | [https://www.hse.ru/org/persons/144545940 Алексей Панов] || 163-2 || | + | | [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 || |
| | |- | | |- |
| − | | Александр Тиунов || || | + | | Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности |
| | |- | | |- |
| − | | Александр Зойкин || || Среда, 14:20-15:40
| + | | Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности |
| − | |-
| + | |
| − | | Валентин Бирюков || || Среда, 12:00-13:00, ауд. 618 | + | |
| | |- | | |- |
| | |} | | |} |
| | | | |
| | == Учебные контесты == | | == Учебные контесты == |
| − |
| |
| | | | |
| | ==Листики== | | ==Листики== |
| − | https://yadi.sk/d/uN86f35WyeryR
| |
| − |
| |
| − | ==Тесты для командного контеста==
| |
| − | https://yadi.sk/d/0-YawHpC3Fqq2c
| |
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:
0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.
