Алгоритмы и структуры данных пилотный поток 2020/2021 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Debnatkh (обсуждение | вклад) |
Debnatkh (обсуждение | вклад) |
||
| Строка 78: | Строка 78: | ||
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 | ||
| Строка 153: | Строка 153: | ||
| 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 | ||
|- | |- | ||
|} | |} | ||
Версия 23:11, 21 декабря 2020
Лектор: Глеб Олегович Евстропов
| Важные ссылки | ||
|---|---|---|
 Текущая успеваемость html-версия |
 Google.Classroom инвайт: 7a66mfc
|
Запись на консультации |
Содержание
Формула выставления итоговой оценки
Оитог = 0.375 · Оконтесты + 0.325 · 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 | ||
Листки
Устно листки сдаются преподавателям и ассистентам в присутственные часы. Таблица для записи на консультации sheets.google.com
Листки в электронном виде отправляются в систему Google Classroom (инвайт: tbd). Принимается только TeX — нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки); решения, написанные в MS Word и подобных программах и т.д. Решения можно отправлять несколько раз — проверяться будет последнее отправленное.
Общие предположения, которыми можно пользоваться в задачах
- Если в задаче говорится про запросы, то по умолчанию online
- Если не оговорено иное, можно использовать столько же памяти, сколько времени
- Если не оговорено иное, то можно ожидаемое амортизированное время с хешами
Список листков
| № | Дедлайн | Темы | Листок | Пояснения |
|---|---|---|---|---|
| 2 модуль | ||||
| 1 | Полночь с 23 на 24 ноября | Вероятности и математическое ожидание | 1PuoS9 | |
| 2 | Полночь с 7 на 8 декабря | Сортировки, простые структуры данных и кучи | 1MgD2m | |
Короткие контесты
Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
| № | Дата | Ссылка | Дорешивать |
|---|---|---|---|
| 2 модуль | |||
| 1 | 5 ноября 2020 | 21895 | конец модуля |
| 2 | 19 ноября 2020 | 22752 | конец модуля |
Длинные контесты
| Дедлайн | Темы | Ссылка |
|---|---|---|
| 2 модуль | ||
| полночь с 28 на 29 ноября | Вероятности, упорядоченные данные, структуры данных | 21961 |
Экзамены
Ссылки на материалы
Основные источники:
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ, [2013, 3 издание]
- neerc.ifmo.ru
Изученные темы:
2 модуль
Преподаватели и ассистенты
| Преподаватель | Подгруппа | Присутственные часы | Контакты |
|---|---|---|---|
| Преподаватели | |||
| Глеб Евстропов | 201-1 | ||
| Станислав Артюхин | |||
| Григорий Резников | |||
| Иван Смирнов | |||
| Святослав Фельдшеров | |||
| Глеб Третьяков | |||
| Ассистенты | |||
| Филипп Грибов | TBD | @grphil | |
| Максим Деб Натх | TBD | @debnatkh | |
| Александр Курилкин | TBD | @wrg0ababd | |
| Никита Морозов | TBD | @madn_boi | |
| Алексей Упирвицкий | TBD | @Aleks5d | |
| Дамир Петров | TBD | @O442A4O3 | |
