Алгоритмы и структуры данных на ПМИ (пилотный поток) — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Tiunovas (обсуждение | вклад) |
Wrg0ababd (обсуждение | вклад) |
||
(не показаны 33 промежуточные версии 4 участников) | |||
Строка 1: | Строка 1: | ||
− | '''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] | + | '''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов] |
[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля] | [https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля] | ||
Строка 30: | Строка 30: | ||
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) | ! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) | ||
|- | |- | ||
− | | Теоретические задачи || | + | | Длинный контест || Хеширование, сбалансированные деревья, прочие структуры данных || 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 (дорешивание) | | Короткий контест || Разное || 16 ноября 2016 || 25 марта 2017 (дорешивание) | ||
+ | |- | ||
+ | | Теоретические задачи || Введение в теорвер и анализ алгоритмов || 11 ноября 2016 || 25 ноября 2016 || | ||
|- | |- | ||
|} | |} | ||
Строка 38: | Строка 56: | ||
== Лекции == | == Лекции == | ||
− | * 2 ноября. Структура курса, его концепция и задачи. Введение в теорию вероятностей, понятие вероятностного пространства для случая конечного множества элементарных исходов. Условная вероятность, полная группа события. Понятие геометрической вероятности. '''[https://yadi.sk/i/HE2uuFrpyHXXE Заметки.]''' | + | * 2 ноября 2016. Структура курса, его концепция и задачи. Введение в теорию вероятностей, понятие вероятностного пространства для случая конечного множества элементарных исходов. Условная вероятность, полная группа события. Понятие геометрической вероятности. '''[https://yadi.sk/i/HE2uuFrpyHXXE Заметки.]''' |
− | * 9 ноября. Продолжение введения в теорию вероятностей. Понятие случайной величины и математического ожидания в случае конечно множества элементарных исходов. Индикаторные случайные величины. Математическое ожидание случайной величины и его линейность. Неравенства Маркова и Чебышёва. Примеры вероятностного анализа простых случайных структур. | + | * 9 ноября 2016. Продолжение введения в теорию вероятностей. Понятие случайной величины и математического ожидания в случае конечно множества элементарных исходов. Индикаторные случайные величины. Математическое ожидание случайной величины и его линейность. Неравенства Маркова и Чебышёва. Примеры вероятностного анализа простых случайных структур. |
− | * 11 | + | * 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. Перебор комбинаторных объектов. Введение в динамическое программирование, построение объекта по номеру и получение номера по объекту. Динамическое программирование на подотрезках. | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
==Преподаватели и ассистенты== | ==Преподаватели и ассистенты== | ||
Строка 87: | Строка 91: | ||
! Преподаватель !! Подгруппа !! Присутственные часы | ! Преподаватель !! Подгруппа !! Присутственные часы | ||
|- | |- | ||
− | | [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 161-1 || Среда, | + | | [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 161-1 || Среда, 13:40 - 15:10, ауд. 505 |
|- | |- | ||
− | | [https://www.hse.ru/org/persons/137640601 Павел Мельничук] || 161-2 | + | | [https://www.hse.ru/org/persons/137640601 Павел Мельничук] || 161-2 || |
|- | |- | ||
− | | [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 163-1 | + | | [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 163-1 || |
|- | |- | ||
− | | [https://www.hse.ru/org/persons/144545940 Алексей Панов] || 163-2 | + | | [https://www.hse.ru/org/persons/144545940 Алексей Панов] || 163-2 || |
|- | |- | ||
− | | Александр Тиунов || || | + | | Александр Тиунов || || |
|- | |- | ||
− | | Александр Зойкин || || Среда, 14:20-15:40 || | + | | Александр Зойкин || || Среда, 14:20-15:40 |
+ | |- | ||
+ | | Валентин Бирюков || || Среда, 12:00-13:00, ауд. 618 | ||
|- | |- | ||
|} | |} | ||
Строка 106: | Строка 112: | ||
==Листики== | ==Листики== | ||
https://yadi.sk/d/uN86f35WyeryR | https://yadi.sk/d/uN86f35WyeryR | ||
+ | |||
+ | ==Тесты для командного контеста== | ||
+ | https://yadi.sk/d/0-YawHpC3Fqq2c |
Текущая версия на 22:07, 6 ноября 2018
Лектор: Глеб Олегович Евстропов
Предполагаемая программа на 4 модуля
Содержание
Формула выставления итоговой оценки
В первый отчетный период, состоящий из 2 и 3 модулей 2016-17 учебного года будет использоваться следующая формула определения оценки:
0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.
- Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
- Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.
- Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.
- Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).
- В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.
- За экзамен студент получает оценку от 0 до 10.
- Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.
Сроки выполнения заданий
Тип задания | Тема | Дата выдачи | Сроки выполнения до (включительно) | |
---|---|---|---|---|
Длинный контест | Хеширование, сбалансированные деревья, прочие структуры данных | 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. Структура курса, его концепция и задачи. Введение в теорию вероятностей, понятие вероятностного пространства для случая конечного множества элементарных исходов. Условная вероятность, полная группа события. Понятие геометрической вероятности. Заметки.
- 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. Перебор комбинаторных объектов. Введение в динамическое программирование, построение объекта по номеру и получение номера по объекту. Динамическое программирование на подотрезках.
Преподаватели и ассистенты
Преподаватель | Подгруппа | Присутственные часы |
---|---|---|
Глеб Евстропов | 161-1 | Среда, 13:40 - 15:10, ауд. 505 |
Павел Мельничук | 161-2 | |
Станислав Артюхин | 163-1 | |
Алексей Панов | 163-2 | |
Александр Тиунов | ||
Александр Зойкин | Среда, 14:20-15:40 | |
Валентин Бирюков | Среда, 12:00-13:00, ауд. 618 |
Учебные контесты
Листики
https://yadi.sk/d/uN86f35WyeryR