Алгоритмы и структуры данных пилотный поток 2021/2022 — различия между версиями
Debnatkh (обсуждение | вклад) |
Debnatkh (обсуждение | вклад) |
||
Строка 295: | Строка 295: | ||
! Темы | ! Темы | ||
! Ссылка | ! Ссылка | ||
+ | |- | ||
+ | | colspan="4" style="text-align: center; background-color:#dae8fc;" | 2 модуль | ||
|- | |- | ||
| 1 | | 1 | ||
Строка 310: | Строка 312: | ||
| Хеши | | Хеши | ||
| [https://official.contest.yandex.ru/contest/32954 Вход] | | [https://official.contest.yandex.ru/contest/32954 Вход] | ||
+ | |- | ||
+ | | colspan="4" style="text-align: center; background-color:#dae8fc;" | 3 модуль | ||
|- | |- | ||
|} | |} |
Версия 20:06, 15 января 2022
Лектор: Глеб Олегович Евстропов
Важные ссылки | |||
---|---|---|---|
![]() Текущая успеваемость html-версия |
![]() Google.Classroom инвайт: 27fucrv
|
![]() Запись на консультации |
![]() Плейлист с записями лекций |
Содержание
Формула выставления итоговой оценки
Формула оценивания пока предварительная и может поменяться!
2 модуль: Оитог = 0,53571428572 · Оконтесты + 0,46428571428 · Oлистки + Oбонус
-
Оконтесты вычисляется по формуле:
Оконтесты = 10 · ( КК + ДК + БЗ ), где: ОЗ - поправка ОЗ - КК — баллы за короткие контесты
- ДК — баллы за длинные контесты (исключая бонусные задачи)
- БЗ — баллы за бонусные задачи в длинных контестах
- ОЗ — общее число задач во всех контестах (исключая бонусные задачи)
- Поправка по умолчанию равна нулю и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.
Виды контестов:
- Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 или 6 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
- Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные.
- Олистки вычисляется по формуле:
Олистки = 10 · количество решённых задач количество обязательных задач - поправка Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов, на консультациях ассистентам.
- В течение каждого очного модуля предполагается по одной контрольной работе (так было до перехода в онлайн). За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться ОКР. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
- За экзамен студент получает оценку от 0 до 10, эта оценка будет являться Оэкз.
- Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.
Итоговая оценка округляется арифметически (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).
Лекции и семинары
2 модуль
Дата | Тип | Тема | Материалы | Видео |
---|---|---|---|---|
26.10.2021 | Семинар | Основные определения, асимптотический рост функций, виды полиномиальности | Листочек | Видео |
Лекция | Знакомство, обзор программы курса, введние в теорию вероятностей | Видео | ||
28.10.2021 | Семинар | Задачи на теорию вероятностей, конечные вероятностные пространства, геометрическая вероятность | Листочек | Видео |
Лекция | Случайные величины. Математическое ожидание, дисперсия, линейность, индикаторные величины. | Материалы | Видео | |
02.11.2021 | Семинар | Задачи на случайные величины и математическое ожидание | Листочек | Видео |
Лекция | RAM-модель | Видео | ||
09.11.2021 | Семинар | Задачи на дисперсию, вероятности и матожидание, свойства случайных структур | Листочек | Видео |
Лекция | Доказательство корректности работы алгоритмов, сортировки сравнениями, доказательство времени работы по индукции, рандомизированный поиск порядковой статистики | Видео | ||
11.11.2021 | Семинар | Задачи на сортировку | Листочек | Видео |
Лекция | Детерменированный поиск порядковой статистики, бинарный и интерполяционный поиск, сортировки с учётом способа представления чисел, сортировка случайных данных | Видео | ||
16.11.2021 | Семинар | Задачи на cортировки и порядковые статистики | Листочек | Видео |
Лекция | Нижняя оценка на сложность сортировки сравнениями, сортирующие сети | Видео | ||
18.11.2021 | Семинар | Сортирующие сети и простые структуры данных | Листочек | Видео |
Лекция | Поставнока задач во внешней памяти, модель вычислений. Эффективная сортировка во внешней памяти | Видео | ||
23.11.2021 | Семинар | Задачи на алгоритмы во внешней памяти | Листочек | |
Лекция | Простые структуры данных. Двоичные и k-ичные кучи, биномиальные пирамиды | Видео | ||
25.11.2021 | Семинар | Задачи на простые структуры данных | Листочек | Видео |
Лекция | Амортизационный анализ | Видео | ||
30.11.2021 | Семинар | Задачи на амортизационный анализ | Листочек | Видео |
Лекция | Фибоначчиевые кучи | Видео | ||
02.12.2021 | Бонусный семинар | Реальная эффективность операций, написание быстрого кода, иерархия памяти |
Теоретическое домашнее задание
Общие предположения, которыми можно пользоваться в задачах
1. Если в задаче говорится про запросы, то по умолчанию online
2. Если не оговорено иное, можно использовать столько же памяти, сколько времени
3. Если не оговорено иное, то можно ожидаемое амортизированное время с хешами
Правила сдачи домашних заданий
1. Некоторые из задач домашнего задания можно сдать только письменно, остальные — как письменно, так и устно.
2. Для каждого домашнего задания определены два дедлайна: мягкий дедлайн (обычно — через 2 недели) и жёсткий дедлайн (обычно — через 3 недели после выдачи задания).
3. Вплоть до мягкого дедлайна вы можете сдавать задачи устно любому из шести ассистентов. Для этого необходимо предаварительно записаться на консультацию.
4. Кроме этого, вплоть до мягкого дедлайна вы можете сдавать задачи письменно в Google.Classroom. Проверкой письменных работ занимаются два ассистента, закреплённые за группой.
5. Пусть мягкий дедлайн был в день d, а вы сдали работу в день x. Тогда гарантируется, что не позднее, чем в день max(d + 4, x + 7) ваша работа будет проверена и по ней будут оставлены комментарии и пожелания об исправлении. После этого у вас есть возможность единожды исправить проблемы в работе (закрыть уже существующие дыры, но никак не писать новые задачи) и отправить исправленную работу до вплоть до жёсткого дедлайна. Не позднее, чем через 10 дней после жёсткого дедлайна мы гарантируем проверку исправленных работ.
6. Почти все (кроме, может быть, последних в модуле) домашние задания будут разобраны на семинарах. Разборы будут проводиться не раньше жёсткого дедлайна.
Написанное выше стоит понимать так: в лучшем сценарии вы решаете задачи и сдаёте какие-то из них (те, которые сложнее всего сдать письменно) устно, а все остальные — письменно. После мягкого дедлайна в течении пары дней ваш ассистент проверяет все работы и отправляет по ним фидбек, после чего у вас несколько дней на исправление недочётов. Мы будем пытаться проверять работы как можно раньше, но не гарантируем ничего лучше, чем описанное в п. 5.
Правила сдачи письменных работ
1. Пожалуйста, убедитесь, что вашу работу можно идентифицировать (имя написано в файле, или ваш гугл-аккаунт подписан вашим именем).
2. При отправке убедитесь, что у вас появилась кнопка "отменить отправку" — это означает, что работа отправлена на проверку.
3. Домашние задания, сданные не в формате .pdf или набранные не с помощью системы вёрстки LaTeX не принимаются.
4. Нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки).
5. Решение должно представлять из себя свзяный цензурный текст без обсценной лексики, который может быть прочитан носителем русского языка, и являть собой решение задачи. Если текст не являет собой решение задачи, не надо прикладывать его к решению.
6. Списывание в работах повлечёт за собой обнуление баллов по работе.
7. Если вы не чувствуете себя уверено при работе с LaTeX, используйте шаблон https://www.overleaf.com/read/bpvmhqcvfgqq. В нём отражена основаня функциональность системы вёрстки. Вы можете склонировать проект и использовать его
Список заданий
№ | Тема | Листок | Мягкий дедлайн | Жесткий дедлайн |
---|---|---|---|---|
1 | Вероятности и математическое ожидание. | Листок | 14.11.2021 | 22.11.2021 |
2 | Сортировки | Листок | 24.11.2021 | 01.12.2021 |
3 | Простые структуры данных и амортизационный анализ. | Листок | 06.12.2021 | 13.12.2021 |
4 | Кучи, хеши. | Листок | 17.12.2021 | 25.12.2021 |
5 | Структуры данных | Листок | 24.01.2022 | 31.01.2022 |
Короткие контесты
Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
№ | Дата | Ссылка | Дорешивать |
---|---|---|---|
2 модуль |
Длинные контесты
№ | Дедлайн | Темы | Ссылка |
---|---|---|---|
2 модуль | |||
1 | 01.12.2021 | Вероятности, упорядоченные данные, простые структуры | Вход |
2 | 09.12.2021 | Вероятности, сортировки, простые структуры, кучи | Вход |
3 | 18.12.2021 | Хеши | Вход |
3 модуль |
Экзамены
Ссылки на материалы
Основные источники:
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ, [2013, 3 издание]
- neerc.ifmo.ru
Преподаватели и ассистенты
Преподаватель | Подгруппа | Присутственные часы | Контакты |
---|---|---|---|
Преподаватели | |||
Глеб Евстропов | 211-1 | ||
Станислав Артюхин | 211-2 | ||
Дмитрий Ковальков | 213-1 | ||
Иван Смирнов | 213-2 | ||
Глеб Третьяков | 215-1 | ||
Максим Гайдук | 215-2 | ||
Ассистенты | |||
Филипп Грибов | @grphil | ||
Максим Деб Натх | вторник, 20:00 | @debnatkh | |
Владимир Кауркин | 211 | понедельник 20:00 | @LordVoldebug |
Игорь Маркелов | 211 | четверг 21:00 | @ElderlyPassionFruit |
Максим Басалаев | 213 | четверг, 19:00 | @pojaleesh |
Алеся Иванова | 213 | среда 17:00 | @alesyaivanova |
Максим Лутан | 215 | пятница, 19:00 (можно договориться о другом дне недели в лс) | @Maksim_Lutan |
Кирилл Шубников | 215 | среда 21:00 (писать в лс) | @Radewoosh51 |