Алгоритмы и структуры данных пилотный поток 2022/2023 — различия между версиями

Текущая версия на 14:35, 12 апреля 2023

Лектор: Иван Фёдорович Смирнов

Важные ссылки
Текущая успеваемость	Запись на консультации		Сдача ДЗ

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

Формула оценивания пока предварительная и может поменяться!

Курс длится 4 модуля (со 2-го по 5-й) и предполагает две итоговые оценки: на первом курсе (2-4 модули) и на втором (5 модуль). Оценки за каждый модуль ставятся независимо. Итоговая оценка за первый курс составляется из оценок за 2-4 модули (точные правила будут сообщены позднее). Оценка за 5-й модуль является итоговой оценкой за второй курс.

После 3-го, 4-го и 5-го модулей будут экзамены.

Правила выставления оценок за модули:

2-й модуль: О_итог = 0.4286 · О_{контесты} + 0.3571 · O_листки + 0.2143 · О_КР + O_бонус

3-й модуль: О_итог = 0.3 · О_{контесты} + 0.25 · O_листки + 0.15 · О_КР + 0.3 · О_{экзамен} + O_бонус

4-й модуль: О_итог = 0.3 · О_{контесты} + 0.25 · O_листки + 0.15 · О_КР + 0.3 · О_{экзамен} + O_бонус

В ведомость за каждый модуль идёт округлённое значение из формулы выше. Для подсчёта итоговой оценки за год берётся среднее арифметическое по неокруглённым оценки за модули 2, 3, 4. Если оценка за модуль превышает 10, она считается равной 10.

Итог за год (1-й курс): (min(10, O_{2-й модуль}) + min(10, O_{3-й модуль}) + min(10, O_{4-й модуль})) / 3

• О_листки вычисляется по формуле:

  Олистки = 10 ·	количество решённых задач
  	количество обязательных задач - поправка

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

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

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

Теоретическое домашнее задание

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

1. Если в задаче говорится про запросы, то по умолчанию online

2. Если не оговорено иное, можно использовать столько же памяти, сколько времени

3. Если не оговорено иное, то можно ожидаемое амортизированное время с хешами

Правила сдачи письменных работ

1. Пожалуйста, убедитесь, что вашу работу можно идентифицировать (имя написано в файле, или ваш гугл-аккаунт подписан вашим именем).

2. При отправке убедитесь, что у вас появилась кнопка "отменить отправку" — это означает, что работа отправлена на проверку.

3. Домашние задания, сданные не в формате .pdf или набранные не с помощью системы вёрстки LaTeX не принимаются.

4. Нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки).

5. Решение должно представлять из себя свзяный цензурный текст без обсценной лексики, который может быть прочитан носителем русского языка, и являть собой решение задачи. Если текст не являет собой решение задачи, не надо прикладывать его к решению.

6. Списывание в работах повлечёт за собой обнуление баллов по работе.

7. Если вы не чувствуете себя уверено при работе с LaTeX, используйте шаблон https://www.overleaf.com/read/bpvmhqcvfgqq. В нём отражена основная функциональность системы вёрстки. Вы можете склонировать проект и использовать его.

Список заданий

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

Все длинные контесты доступны по ссылке.

Экзамены

Темы к экзамену 3-го модуля

• Бинарные деревья поиска. Определение, базовые свойства.
• B+-дерево. Простейшие операции. Операции Split и Merge.
• Splay-дерево. Операции. Доказательство амортизированного времени работы.
• Декартово дерево. Операции Split и Merge. Оценка матожидания глубины вершины. Декартово дерево по неявному ключу.
• Запросы на отрезках. Дерево отрезков, общие идеи. Sparse table. Disjoint sparse table.
• Персистентность. Общие идеи, примеры частично и полностью персистентных структур данных. Применение в задачх.
• Методы Path copying и Fat nodes. Их комбинирование для получения частично персистентного списка без штрафа по времени и памяти.
• LCA. Метод двоичных подъёмов. Алгоритм Тарьяна с СНМ. Алгоритм Фараха-Колтона и Бендера.
• Запросы на деревьях. Heavy-light декомпозиция, оптимизация времени работы до O(log n) на запрос.
• Переборные алгоритмы. Подходы через поиск в глубину и поиск в ширину. Способы хеширования состояний. Iterative deepening. Примеры отсечений.
• Кратчайшие пути в графах. Алгоритмы Дейкстры и Форда-Беллмана. Двусторонний алгоритм Дейкстры.
• Алгоритм Contraction Hierarchies для поиска кратчайших путей в графах, возникающих на практике.
• Альфа-бета отсечение в антагонистических играх.
• Мосты, точки сочленения. Построение деревьев компонент рёберной и вершинной двусвязности.
• Конденсация ориентированного графа. Алгоритм Тарьяна.
• Система непересекающихся множеств. Доказательство амортизированного времени работы O(log* n) на запрос.
• Минимальные остовные деревья. Алгоритмы Прима, Краскала, Борувки.
• Линейный вероятностный алгоритм построения MST (в предположении существования алгоритма проверки минимальности за линейное время). Проверка остовного дерева на минимальность за O(m log log n).
• Потоки в сетях. Теорема Форда-Фалкерсона. Примеры решения задач через сведение к минимальному разрезу или максимальному потоку.
• Теорема Кёнига-Эгервари, лемма Холла. Доказательство через теорему Форда-Фалкерсона.
• Алгоритм Эдмондса-Карпа. Алгоритм Диница, доказательство времени работы O(E sqrt(V)) при поиске максимального двудольного паросочетания.

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

Записи семинаров, сделанные силами студентов: https://disk.yandex.ru/d/yVmC7VRuXWblIw

2 модуль

3 модуль

4 модуль

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

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

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

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