Алгоритмы и структуры данных пилотный поток 2020/2021

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Лектор: Глеб Олегович Евстропов

Программа курса

Важные ссылки
Google.Classroom
Текущая успеваемость
html-версия
Google.Classroom
Google.Classroom
инвайт: 7a66mfc
Google.Classroom
Запись на консультации


Формула выставления итоговой оценки

2, 5 модули: Оитог = 0.375 · Оконтесты + 0.325 · Oлистки + 0.3 · Oэкз + Oбонус


3, 4 модули: Оитог = 0.3 · Оконтесты + 0.25 · Oлистки + 0.15 · OКР + 0.3 · Oэкз + Oбонус

  • Оконтесты вычисляется по формуле:
    Оконтесты = 10 · ( КК + ДК + БЗ ), где:
    ОЗ - поправка ОЗ
    • КК — баллы за короткие контесты
    • ДК — баллы за длинные контесты (исключая бонусные задачи)
    • БЗ — баллы за бонусные задачи в длинных контестах
    • ОЗ — общее число задач во всех контестах (исключая бонусные задачи)
    • Поправка по умолчанию равна нулю и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

    Виды контестов:

    • Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
    • Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные.
  • Олистки вычисляется по формуле:
    Олистки = 10 · количество решённых задач
    количество обязательных задач - поправка

    Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов, на консультациях ассистентам.

  • В течение каждого модуля предполагается по одной контрольной работе (так было до перехода в онлайн). За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться ОКР. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
  • За экзамен студент получает оценку от 0 до 10, эта оценка будет являться Оэкз.
  • Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

Итоговая оценка округляется арифметически (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).

Лекции и семинары

2 модуль

3 модуль


4 модуль

Листки

Устно листки сдаются преподавателям и ассистентам в присутственные часы. Таблица для записи на консультации sheets.google.com

Листки в электронном виде отправляются в систему Google Classroom (инвайт: 7a66mfc). Принимается только TeX — нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки); решения, написанные в MS Word и подобных программах и т.д. Решения можно отправлять несколько раз — проверяться будет последнее отправленное.

Общие предположения, которыми можно пользоваться в задачах

  • Если в задаче говорится про запросы, то по умолчанию online
  • Если не оговорено иное, можно использовать столько же памяти, сколько времени
  • Если не оговорено иное, то можно ожидаемое амортизированное время с хешами

Список листков

Дедлайн Темы Листок Пояснения
2 модуль
1 Полночь с 23 на 24 ноября Вероятности и математическое ожидание 1PuoS9
2 Полночь с 7 на 8 декабря Сортировки, простые структуры данных и кучи 1MgD2m
3 Полночь с 19 на 20 декабря Фибоначчиевые кучи, хеши и деревья поиска 12Xt1d
3 модуль
4 Полночь с 1 на 2 февраля Структуры данных 1PQkaa
5 Полночь с 24 на 25 февраля Динамическое программирование, перебор и метод meet-in-the-middle 17qBZ6
6 Полночь с 15 на 16 марта Обходы графов, кратчайшие расстояния и остовные деревья 1BULcw
4 модуль
7 Полночь с 12 на 13 апреля Паросочетания и потоки 1HwONt
8 Полночь с 24 на 25 мая Строки и языки 1kMXCq

Короткие контесты

Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

Дата Ссылка Дорешивать
2 модуль
1 5 ноября 2020 21895 полночь с 23 на 24 декабря
2 19 ноября 2020 22752 полночь с 23 на 24 декабря
3 модуль
3 21 января 2021 24514
4 4 февраля 2021 24808
4 модуль
5 15 апреля 2021 26747
6 29 апреля 2021 27185

Длинные контесты

Дедлайн Темы Ссылка
2 модуль
полночь с 28 на 29 ноября Вероятности, упорядоченные данные, структуры данных 21961
полночь с 20 на 21 декабря Хеши и деревья поиска 23375
3 модуль
полночь с 24 на 25 февраля Cтруктуры данных, запросы на отрезках 24924
полночь с 10 на 11 мая Ддинамика, перебор, графы 26746
4 модуль

Экзамены

Ссылки на материалы

Основные источники:

  1. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ, [2013, 3 издание]
  2. neerc.ifmo.ru

Изученные темы:

2 модуль

  1. Виды задач, сильно-, слабо-, и псевдополиномиальность: https://www.epfl.ch/labs/disopt/wp-content/uploads/2018/09/algorithms.pdf
  2. Ликбез по теории вероятностей
    1. Кормен, приложение В "Комбинаторика и теория вероятности", c 1235
    2. Памятка по основным определениям
  3. Индикаторная случайная величина: Кормен, раздел 5.2, с 144.
  4. Методы решения рекуррентных соотношений: Кормен, гл. 4, разделы 4.3-4.5 (со стр. 108)
  5. Модель вычислений во внешней памяти, сортировка слиянием во внешней памяти: https://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_во_внешней_памяти._Базовые_конструкции
  6. Двоичная куча, сортировки, порядковые статистики
    1. Кормен, часть 2 "Сортировка и порядковая статистика" с. 173
    2. https://neerc.ifmo.ru/wiki/index.php?title=Двоичная_куча
  7. Невозможность сортировки быстрее n log n: Кормен, начало главы "Сортировка за линейное время", стр. 220
  8. Фибоначчиевы кучи
    1. Кормен, гл. 19, с 542
    2. https://neerc.ifmo.ru/wiki/index.php?title=Фибоначчиева_куча
  9. Биномиальные кучи: https://neerc.ifmo.ru/wiki/index.php?title=Биномиальная_куча
  10. Хеширование и хеш-таблицы
    1. Кормен, гл. 11, с. 285
    2. http://neerc.ifmo.ru/wiki/index.php?title=Разрешение_коллизий
  11. Фильтр Блума: http://neerc.ifmo.ru/wiki/index.php?title=Фильтр_Блума
  12. Амортизационный анализ: Кормен, гл. 17, с 487
  13. Бинарные деревья поиска: Кормен, гл. 12, c 319
  14. Декартово дерево
    1. https://neerc.ifmo.ru/wiki/index.php?title=Декартово_дерево
    2. https://neerc.ifmo.ru/wiki/index.php?title=Декартово_дерево_по_неявному_ключу
  15. B-деревья
    1. Кормен, гл.18, стр. 521
    2. http://neerc.ifmo.ru/wiki/index.php?title=B-дерево
  16. 2-3-деревья: http://neerc.ifmo.ru/wiki/index.php?title=2-3_дерево
  17. Стек и очередь с минимумом: https://e-maxx.ru/algo/stacks_for_minima
  18. Дек на 3 стеках: https://neerc.ifmo.ru/wiki/index.php?title=Дек

Преподаватели и ассистенты

Преподаватель Подгруппа Присутственные часы Контакты
Преподаватели
Глеб Евстропов 201-1
Станислав Артюхин
Григорий Резников
Иван Смирнов
Святослав Фельдшеров
Глеб Третьяков
Ассистенты
Филипп Грибов TBD @grphil
Максим Деб Натх TBD @debnatkh
Александр Курилкин TBD @wrg0ababd
Никита Морозов TBD @madn_boi
Алексей Упирвицкий TBD @Aleks5d
Дамир Петров TBD @O442A4O3