Алгоритмы и структуры данных пилотный поток 2019/2020 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Debnatkh (обсуждение | вклад) |
Debnatkh (обсуждение | вклад) |
||
| Строка 32: | Строка 32: | ||
== Лекции и семинары == | == Лекции и семинары == | ||
| + | <!-- | ||
| + | Ссылки образуют ребусную последовательность | ||
| + | 64726976 + | ||
| + | 652e676f + | ||
| + | 6f676c65 + | ||
| + | 2e636f6d + | ||
| + | 2f6f7065 + | ||
| + | 6e3f6964 + | ||
| + | 3d315935 + | ||
| + | 42756a31 + | ||
| + | 53643279 | ||
| + | 374d6b47 | ||
| + | 4f503751 | ||
| + | 34597662 | ||
| + | 55493345 | ||
| + | 57426b4b | ||
| + | 56522020 | ||
| + | --> | ||
=== 2 модуль === | === 2 модуль === | ||
| Строка 42: | Строка 60: | ||
| style="white-space: nowrap;" |29 октября | | style="white-space: nowrap;" |29 октября | ||
| style="width: 35%"| Понятие асимптотического времени работы алгоритма. Сильно-, слабо- и псевдополиномиальное время работы. Обозначения O, o, Ω, ω | | style="width: 35%"| Понятие асимптотического времени работы алгоритма. Сильно-, слабо- и псевдополиномиальное время работы. Обозначения O, o, Ω, ω | ||
| − | | style="white-space: nowrap;" |[https://drive.google.com/file/d/13YjOHteA-XsX2l7IWvnFj7rQDGKxtaTq/view?usp=sharing | + | | style="white-space: nowrap;" |[https://drive.google.com/file/d/13YjOHteA-XsX2l7IWvnFj7rQDGKxtaTq/view?usp=sharing 64726976] |
| style="width: 65%"| Знакомство со структурой курса и системой выставления оценок.Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность | | style="width: 65%"| Знакомство со структурой курса и системой выставления оценок.Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность | ||
|- | |- | ||
| style="white-space: nowrap;" |31 октября | | style="white-space: nowrap;" |31 октября | ||
| Совместное решение задач по теории вероятностей | | Совместное решение задач по теории вероятностей | ||
| − | | [https://drive.google.com/file/d/1luO3Tsm1bpsr3uTIyrnWLw4EGP4vGB28/view?usp=sharing | + | | [https://drive.google.com/file/d/1luO3Tsm1bpsr3uTIyrnWLw4EGP4vGB28/view?usp=sharing 652e676f] |
| Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства | | Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства | ||
|- | |- | ||
| style="white-space: nowrap;" |5 ноября | | style="white-space: nowrap;" |5 ноября | ||
| Совместное решение задач на мат. ожидание | | Совместное решение задач на мат. ожидание | ||
| − | | [https://drive.google.com/open?id=1x-gcfGv7Vf3JrqcQ5XFb1pUUlbDO5gVl | + | | [https://drive.google.com/open?id=1x-gcfGv7Vf3JrqcQ5XFb1pUUlbDO5gVl 6f676c65] |
| Модель вычислений, описание RAM-модели. Три основных способа доказательства корректности на примере квадратичных сортировок. | | Модель вычислений, описание RAM-модели. Три основных способа доказательства корректности на примере квадратичных сортировок. | ||
|- | |- | ||
| Строка 65: | Строка 83: | ||
| 14 ноября | | 14 ноября | ||
| Сортировки и порядковые статистики | | Сортировки и порядковые статистики | ||
| − | | [https://drive.google.com/file/d/16wxVKES1aeZQ0K7-TK_1BHO6hHeRaiBW/view?usp=sharing | + | | [https://drive.google.com/file/d/16wxVKES1aeZQ0K7-TK_1BHO6hHeRaiBW/view?usp=sharing 2e636f6d] |
| Сортировки, использующие значения элементов. Сортировка подсчётом, поразрядная сортировка, корзинная сортировка.Сортировка случайных чисел за линейное время. Модель вычислений во внешней памяти. Сортировка сравнениями во внешней памяти | | Сортировки, использующие значения элементов. Сортировка подсчётом, поразрядная сортировка, корзинная сортировка.Сортировка случайных чисел за линейное время. Модель вычислений во внешней памяти. Сортировка сравнениями во внешней памяти | ||
|- | |- | ||
| 19 ноября | | 19 ноября | ||
| Сортировки и порядковые статистики (2) | | Сортировки и порядковые статистики (2) | ||
| − | | [https://drive.google.com/file/d/14A0U8pxeT6su-ZkXmFLB71RgHyg0Hpo1/view?usp=sharing | + | | [https://drive.google.com/file/d/14A0U8pxeT6su-ZkXmFLB71RgHyg0Hpo1/view?usp=sharing 2f6f7065] |
| Элементарные структуры данных, двоичная куча. | | Элементарные структуры данных, двоичная куча. | ||
|- | |- | ||
| Строка 82: | Строка 100: | ||
| 28 ноября | | 28 ноября | ||
| Непростые задачи на простые структуры | | Непростые задачи на простые структуры | ||
| − | | [https://drive.google.com/file/d/1YOslKeDqv6fjkRZa2X-vp2pjvAxEzdAA/view?usp=sharing | + | | [https://drive.google.com/file/d/1YOslKeDqv6fjkRZa2X-vp2pjvAxEzdAA/view?usp=sharing 6e3f6964] |
| Биномиальные кучи и фибоначчиевы кучи | | Биномиальные кучи и фибоначчиевы кучи | ||
|- | |- | ||
| style="white-space: nowrap;" |3 декабря | | style="white-space: nowrap;" |3 декабря | ||
| Задачи на кучи | | Задачи на кучи | ||
| − | | [https://drive.google.com/file/d/1yJFHXpjRX-6YjbfKxjfysFHiEI_x2hHV/view?usp=sharing | + | | [https://drive.google.com/file/d/1yJFHXpjRX-6YjbfKxjfysFHiEI_x2hHV/view?usp=sharing 3d315935] |
| Хеширование, вводная лекция. Полиномиальный хеш. | | Хеширование, вводная лекция. Полиномиальный хеш. | ||
|- | |- | ||
| Строка 99: | Строка 117: | ||
| style="white-space: nowrap;" |12 декабря | | style="white-space: nowrap;" |12 декабря | ||
| Хеши и хеш-таблицы | | Хеши и хеш-таблицы | ||
| − | |[https://drive.google.com/file/d/114mSW6mjeUpv3XqnzNOhtLqK3KKuvMIy/view?usp=sharing | + | |[https://drive.google.com/file/d/114mSW6mjeUpv3XqnzNOhtLqK3KKuvMIy/view?usp=sharing 42756a31] |
| Бинарные деревья поиска. Сбалансированные деревья. Декартово дерево. | | Бинарные деревья поиска. Сбалансированные деревья. Декартово дерево. | ||
|- | |- | ||
| Строка 110: | Строка 128: | ||
| colspan="3" style="background-color:#ecf4ff;" | Бонусный контест №1 | | colspan="3" style="background-color:#ecf4ff;" | Бонусный контест №1 | ||
|} | |} | ||
| + | |||
| + | |||
=== 3 модуль === | === 3 модуль === | ||
Версия 13:00, 15 декабря 2019
Лектор: Глеб Олегович Евстропов
| Важные ссылки | ||
|---|---|---|
 Текущая успеваемость |
 Google.Classroom инвайт: ywktit7
|
Запись на консультации |
Содержание
Формула выставления итоговой оценки
0.3 * Контесты + 0.25 * Листки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус
- Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
- Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные.
- Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.
- Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листок был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (кол-во решенных задач) / (общее число задач - поправка).
- В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.
- За экзамен студент получает оценку от 0 до 10.
- Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.
- Итоговая оценка округляется арифметически (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).
Лекции и семинары
2 модуль
| Датае | Семинар | Листочек | Лекция |
|---|---|---|---|
| 29 октября | Понятие асимптотического времени работы алгоритма. Сильно-, слабо- и псевдополиномиальное время работы. Обозначения O, o, Ω, ω | 64726976 | Знакомство со структурой курса и системой выставления оценок.Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность |
| 31 октября | Совместное решение задач по теории вероятностей | 652e676f | Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства |
| 5 ноября | Совместное решение задач на мат. ожидание | 6f676c65 | Модель вычислений, описание RAM-модели. Три основных способа доказательства корректности на примере квадратичных сортировок. |
| 7 ноября | Короткий контест №1 | ||
| 12 ноября | Разговор про тестирование | не было | Сортировки сравнения, схема доказательства времени работы по индукции, невозможность сортировки быстрее n log n. |
| 14 ноября | Сортировки и порядковые статистики | 2e636f6d | Сортировки, использующие значения элементов. Сортировка подсчётом, поразрядная сортировка, корзинная сортировка.Сортировка случайных чисел за линейное время. Модель вычислений во внешней памяти. Сортировка сравнениями во внешней памяти |
| 19 ноября | Сортировки и порядковые статистики (2) | 2f6f7065 | Элементарные структуры данных, двоичная куча. |
| 21 ноября | Короткий контест №2 | ||
| 26 ноября | Разбор домашнего задания №1 | k-ичная куча, амортизационный анализ методом кредитов и методом потенциалов. Словарь с доступом по значению через сливаемые массивы,очередь с минимумом, дек с минимумом, динамический массив | |
| 28 ноября | Непростые задачи на простые структуры | 6e3f6964 | Биномиальные кучи и фибоначчиевы кучи |
| 3 декабря | Задачи на кучи | 3d315935 | Хеширование, вводная лекция. Полиномиальный хеш. |
| 5 декабря | Контрольная работа №1 | ||
| 10 декабря | Разбор домашнего задания №2 | Хеш-таблицы, стратегии масштабирования, фильтры Блума. | |
| 12 декабря | Хеши и хеш-таблицы | 42756a31 | Бинарные деревья поиска. Сбалансированные деревья. Декартово дерево. |
| 17 декабря | |||
| 19 декабря | Бонусный контест №1 | ||
3 модуль
Листки
Устно листки сдаются преподавателям и ассистентам в присутственные часы. Таблица для записи на консультации sheets.google.com
Листки в электронном виде отправляются в систему Google Classroom (инвайт: ywktit7). Принимается только TeX — нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки); решения, написанные в MS Word и подобных программах и т.д. Решения отправляются ровно один раз — нельзя отправить что-то, а потом через неделю прислать исправленную версию (небольшие исправления и уточнения разрешаются, если сделаны в течение нескольких часов после отправки листка и строго до дедлайна).
Общие предположения, которыми можно пользоваться в задачах:
- Если в задаче говорится про запросы, то по умолчанию online
- Если не оговорено иное, можно использовать столько же памяти, сколько времени
- Если не оговорено иное, то можно ожидаемое амортизированное время с хешами
| Дедлайн | Темы | Листок | Пояснения |
|---|---|---|---|
| Полночь с 25 на 26 ноября | Вероятности и математическое ожидание | тык | |
| Полночь с 9 на 10 декабря | Сортировки, простые структуры данных и кучи | пуп |
|
| Полночь с 21 на 22 декабря | Хеши и деревья поиска | тыц |
|
Короткие контесты
Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
| Дата | Ссылка | Дорешивать |
|---|---|---|
| 7 ноября 2019 | 15290 | полночь с 27 на 28 декабря |
| 21 ноября 2019 | 15816 | полночь с 27 на 28 декабря |
Длинные контесты
| Дедлайн | Темы | Ссылка |
|---|---|---|
| полночь с 9 на 10 декабря | Cортировки, порядковые статистики, простые структуры данных | 15815 |
| полночь с 22 на 23 декабря | Хеши и деревья поиска | 16271 |
Экзамены
| Модуль | Дата | Время, аудитория | Программа | |
|---|---|---|---|---|
| 2 модуль | 28 декабря (суббота) | Письменная часть | 11:00-12:30 | TBA |
| Устная часть | 14:00-17:00 | |||
FAQ
Q: А когда будет FAQ?
A: Уже готово, см. вики-страницу курса
Преподаватели и ассистенты
| Преподаватель | Подгруппа | Присутственные часы | Контакты |
|---|---|---|---|
| Преподаватели | |||
| Глеб Евстропов | 191-1 | ||
| Станислав Артюхин | 191-2 | ||
| Григорий Резников | 193-1 | ||
| Иван Смирнов | 193-2 | ||
| Святослав Фельдшеров | 195-1 | ||
| Никита Сендерович | 195-2 | ||
| Ассистенты | |||
| Филипп Грибов | Покровский бульвар, понедельник, 4 пара (13:30 - 15:10) | grphil | |
| Иван Сафонов | Покровский бульвар, понедельник, 2 пара (10:30 - 11:50) | isaf27 | |
| Максим Деб Натх | Покровский бульвар, четверг, 4 пара (13:40 - 15:00) | debnatkh | |
| Никита Морозов | Покровский бульвар, вторник, 5 пара (15:10 - 16:30) | madn_boi | |
