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

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

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

План учебной дисциплины

План учебной дисциплины, только лучше


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

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

0.3 · Оконтесты + 0.25 · Oлистки + 0.15 · OКР + 0.3 · Oэкз + Oбонус

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

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

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

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

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

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

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

2 модуль

3 модуль

4 модуль

5 модуль

Листки

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

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

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

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

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

Дедлайн Темы Листок Пояснения
2 модуль
1 Полночь с 25 на 26 ноября Вероятности и математическое ожидание тык
2 Полночь с 9 на 10 декабря Сортировки, простые структуры данных и кучи тук
  • В пятой задаче медиана массива чётной длины — левый из двух возможных элементов
  • Во второй задаче можно считать, что запросы даны заранее и нужно ответить на все сразу
3 Полночь с 21 на 22 декабря Хеши и деревья поиска тыц
  • Если не оговорено иное, то можно ожидаемое амортизированное время с хешами
  • Во второй задаче числа целые
  • В восьмой задаче можно считать, что TreeNode хранит Left, Right, Parent
  • В первой задаче все строки непустые
3 модуль
4 Полночь с 12 на 13 февраля Структуры данных бац
5 Полночь с 26 на 27 февраля Динамическое программирование, перебор и метод meet-in-the-middle бах
  • Во второй задаче алфавит произвольный
6 Полночь с 11 на 12 марта Обходы графов и кратчайшие расстояния бам
  • В седьмой задаче отрицательных весов не бывает
7 Полночь с 30 на 31 марта Остовы, графы и СНМ бум
4 модуль
8 Полночь с 18 на 19 мая Потоки и паросочетания бац
  • В первой в процессе размещения домино разрешается уходить в минус
  • Во втором пункте одиннадцатой задачи имеется в виду рёберное покрытие
  • В третьей под k понимается количество коробок и финальных мест под коробки.
    Пустые клетки поля в k не учитываются. Считать, что k > 0.
9 Полночь с 27 на 28 мая Строки и регулярные языки бах
  • Если это явно не указано, то алфавит нельзя считать константным
  • В десятой задаче звёздочка означает любую строку
  • В десятой задаче вопросиков:
    разрешены только буквы английского алфавита и звёздочки. Знаки вопроса (джокеры, означающие один любой символ) не разрешены
10 Полночь с 10 на 11 июня Классы сложности и теоретико-числовые алгоритмы бан
5 модуль

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

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

Дата Ссылка Дорешивать
2 модуль
1 7 ноября 2019 15290 полночь с 27 на 28 декабря
2 21 ноября 2019 15816 полночь с 27 на 28 декабря
3 модуль
3 21 января 2020 16928 полночь с 20 на 21 июня
4 3 марта 2020 17435 полночь с 20 на 21 июня
5 17 марта 2020 17611 полночь с 20 на 21 июня
4 модуль
6 9 апреля 2020 17927 полночь с 20 на 21 июня
7 23 апреля 2020 18158 полночь с 20 на 21 июня
8 7 мая 2020 18262 полночь с 20 на 21 июня
9 21 мая 2020 18478 полночь с 20 на 21 июня
5 модуль

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

Дедлайн Темы Ссылка
2 модуль
полночь с 9 на 10 декабря Cортировки, порядковые статистики, простые структуры данных 15815
полночь с 22 на 23 декабря Хеши и деревья поиска 16271
3 модуль
Полночь с 17 на 18 февраля Структуры данных, запросы на отрезках 17022
Полночь с 31 марта на 1 апреля Динамика, перебор, графы 17506
4 модуль
Полночь с 24 на 25 мая Графы, паросочетания, потоки 18261
Полночь с 14 на 15 июня Строки, языки, ТЧ 18261
5 модуль

Экзамены

Правила экзамена

  1. Состоит из письменного теста и устной части.
  2. За тест ставится оценка от 1 до 8.
  3. На устную часть приглашаются те, кто написал тест на 4 и выше.
  4. У тех, кто идёт на устную часть, оценка понижается на 1.
  5. На устной части вы последовательно увеличиваете свою оценку на 1, отвечая на теоретические вопросы и задачи.
  6. За экзамен можно два раза перетянуть билет.
  7. Три неправильных подхода к снаряду приводят к форсированному перетягиванию билета в счёт одной попытки.
  8. Если попытки кончились, то экзамен для студента завершается.

Дата и время

Модуль Дата Время, аудитория Программа
2 модуль 28 декабря (суббота) Письменная часть 11:00-12:30, ауд. R401 тык
Устная часть 14:00-17:00, ауд. R401
3-4 модуль 23 июня Письменная часть TBA TBA

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

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

  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=Дек

FAQ

Q: А когда будет FAQ?

A: Уже готово, см. вики-страницу курса


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
Максим Деб Натх среда, 5.5 пара (15:40 - 17:00) @debnatkh
Александр Курилкин среда, (18:00 - ?) @wrg0ababd
Никита Морозов пятница, 5 пара (15:10 - 16:30) @madn_boi