Просмотр исходного текста страницы Алгоритмы и структуры данных пилотный поток 2024/2025

'''[https://drive.google.com/file/d/1vQ7wUYuWXIZ5U2j7QeYb5Z4iTODK0BZt/view?usp=sharing Программа курса]'''

{| class="wikitable"
! colspan="4" | Важные ссылки
|-
| style="text-align: center;vertical-align:top;" | [[Image:Google-Sheets-Logo.png|x100px | 
link=https://docs.google.com/spreadsheets/d/1Zbm91INoxVEXkeoaXjH-Eo8P01aG41HHkXffKAZJEjA/edit?usp=sharing |Google.Sheets]]<br>[https://docs.google.com/spreadsheets/d/1Zbm91INoxVEXkeoaXjH-Eo8P01aG41HHkXffKAZJEjA/edit?usp=sharing Текущая успеваемость]

| style="text-align: center;vertical-align:top;" | [[Image:Google-Sheets-Logo.png|x100px | 
link=https://docs.google.com/spreadsheets/d/1vP-yRvV-vX_O2ookPHmqJlUoc35uVFUKxjQlqIXAMFo/edit?usp=sharing |Google.Sheets]]<br>
[https://docs.google.com/spreadsheets/d/1vP-yRvV-vX_O2ookPHmqJlUoc35uVFUKxjQlqIXAMFo/edit?usp=sharing Запись на консультации]

| style="text-align: center;vertical-align:top;" | [[Image:Google-Sheets-Logo.png|x100px | 
link=https://classroom.google.com/c/NzMxMDYxNDk3OTcz?cjc=6xj3isc  |Google.Classroom]]<br>
[https://classroom.google.com/c/NzMxMDYxNDk3OTcz?cjc=6xj3isc Сдача ДЗ]
|}

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

=== Общее описание ===

'''Детали в формуле оценивания могут меняться с объявлением на лекциях и в канале.'''

* Курс длится 4 модуля (со 2-го по 5-й).
* За 2-й и 3-й модуль ставится промежуточная оценка.
* За 4-й модуль ставится итоговая годовая оценка за первый курс, вычисляемая из оценок за 2-4 модули. При этом 4-й модуль является блокирующим, т.е. для получения оценки за курс необходимо иметь удовлетворительную оценку за 4-й модуль.
* За 5-й модуль ставится итоговая оценка независимо.
* Экзамены будут в конце 3-го, 4-го и 5-го модуля. В экзамен 3-го модуля входят темы из 2-3 модулей, в остальные экзамены входят только темы соответствующего модуля.

Есть несколько видов оцениваемой деятельности, попадающие в накоп с соответствующим коэффициентом (кроме экзамена).
* ('''Конт''', коэфф. 0.3) Длинные контесты.
* ('''ДЗ''', коэфф. 0.25) Теоретические домашние задания.
* ('''КР''', коэфф. 0.15) Письменная контрольная работа.
* ('''Экз''', коэфф. 0.3) Устный экзамен.

Также на курсе предусмотрены бонусы, добавляемые к итоговой оценке за модуль. Бонусы получить за специальные бонусные контесты, за активное участие в семинарах, за участие в ICPC и, возможно, за что-то ещё.

=== Подробности ===

Накоп за каждый модуль считается по формуле '''Накоп''' = (0.3 &middot; '''Конт''' + 0.25 &middot; '''ДЗ''' + 0.15 &middot; '''КР''') / 0.7. Затем для каждого модуля считается предварительная итоговая оценка:
* 2-й модуль: '''Итог<sub>2</sub>''' = '''Накоп<sub>2</sub>''' + '''Бонус<sub>2</sub>'''
* 3-5 модули: '''Итог<sub>i</sub>''' = 0.7 &middot; '''Накоп<sub>i</sub>''' + 0.3 &middot; '''Экз<sub>i</sub>''' + '''Бонус<sub>i</sub>'''

Итоговые оценки считаются так:
* 2-й модуль: min(10, round('''Итог<sub>2</sub>'''))
* 3-й модуль: min(10, round('''Итог<sub>3</sub>'''))
* 4-й модуль (итоговая оценка за год): round((0.7 &middot; min(10, '''Итог<sub>2</sub>''') + min(10, '''Итог<sub>4</sub>''') + min(10, '''Итог<sub>4</sub>''')) / 2.7) при условии round('''Итог<sub>4</sub>''') &ge; 4
* 5-й модуль: min(10, round('''Итог<sub>5</sub>'''))

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

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

=== Оцениваемые активности ===

===== Контесты =====
Длинные контесты имеют продолжительность порядка двух-трёх недель и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Если не сказано иное, каждая задача стоит одинаково. По умолчанию оценка за контесты вычисляется по формуле '''Конт''' = 10 &middot; (Решено задач / (всего обязательных задач - поправка)). Поправка может применяться, если студент по уважительной причине отсутствовал бо́льшую часть контеста.

В контестах бывают бонусные необязательные задачи, позволяющие набрать в этой категории более 10 баллов. Иногда формула оценки может меняться: к примеру, в контесте может быть обязательная задача или суммарный балл для двух контестов может вычисляться из минимального числа задач, решённых в каждом из них.

Короткие контесты — это забытый миф, пыль веков, сага давно минувших дней.

===== Теор. ДЗ =====

Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов на консультациях ассистентам. Подробнее об этом написано в соответствующем разделе. Оценка вычисляется по формуле '''ДЗ''' = 10 &middot; (Набрано баллов в задачах / (суммарная стоимость обязательных задач - поправка)). Разные задачи стоят разное число баллов, за решение можно получить частичные баллы.

Как и в контестах, в ДЗ бывают бонусные задачи, отмеченные звёздочкой. Не гарантируется, что преподаватели сами умеют их решать.

===== Контрольная работа =====

В течение каждого модуля предполагается по одной контрольной работе. За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться оценкой '''КР'''. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется формула оценки накопа: '''Накоп''' = (0.3 &middot; '''Конт''' + 0.25 &middot; '''ДЗ''') / 0.55.

===== Экзамен =====

За экзамен студент получает оценку от 0 до 10, эта оценка будет являться оценкой '''Экз'''.

===== Бонус =====

Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к итоговой оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

При выставлении бонусов будет учитываться текущая посещаемость студента. Полученный студентом бонусный балл будет домножаться на долю посещенных семинаров.

== <span id="homework"></span>Теоретическое домашнее задание ==
=== <span id="assumptions"> Общие предположения, которыми можно пользоваться в задачах ===
1. Если в задаче говорится про запросы, то по умолчанию online

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

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

<!--
=== Правила сдачи домашних заданий ===

1. Некоторые из задач домашнего задания можно сдать только письменно, остальные — как письменно, так и устно.

2. Для каждого домашнего задания определены два дедлайна: мягкий дедлайн (обычно — через 2 недели) и жёсткий дедлайн (обычно — через 3 недели после выдачи задания).

3. Вплоть до мягкого дедлайна вы можете сдавать задачи устно любому из шести ассистентов. Для этого необходимо предаварительно [https://docs.google.com/spreadsheets/d/17JZuEJZPFaItPYl6m9ekjmI1jl_h7gWk9cXxDpnRb6Q/edit?usp=sharing записаться на консультацию].

4. Кроме этого, вплоть до мягкого дедлайна вы можете сдавать задачи письменно в [https://classroom.google.com/c/NDEyODEwMjUzMDIz?cjc=27fucrv Google.Classroom]. Проверкой письменных работ занимаются два ассистента, закреплённые за группой.

5. Пусть мягкий дедлайн был в день d, а вы сдали работу в день x. Тогда гарантируется, что не позднее, чем в день max(d + 4, x + 7) ваша работа будет проверена и по ней будут оставлены комментарии и пожелания об исправлении. После этого у вас есть возможность единожды исправить проблемы в работе (закрыть уже существующие дыры, но никак не писать новые задачи) и отправить исправленную работу до вплоть до жёсткого дедлайна. Не позднее, чем через 10 дней после жёсткого дедлайна мы гарантируем проверку исправленных работ.

6. Почти все (кроме, может быть, последних в модуле) домашние задания будут разобраны на семинарах. Разборы будут проводиться не раньше жёсткого дедлайна.

Написанное выше стоит понимать так: в лучшем сценарии вы решаете задачи и сдаёте какие-то из них (те, которые сложнее всего сдать письменно) устно, а все остальные — письменно. После мягкого дедлайна в течении пары дней ваш ассистент проверяет все работы и отправляет по ним фидбек, после чего у вас несколько дней на исправление недочётов. Мы будем пытаться проверять работы как можно раньше, но не гарантируем ничего лучше, чем описанное в п. 5.
-->

===<span id="classroom"></span>Правила сдачи письменных работ===

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

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

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

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

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

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

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


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

{| class="wikitable"
! №
! Тема
! Листок
! Дедлайн
|-
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 2 модуль
|-
|}

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

Все длинные контесты доступны [https://hsealgo2425.contest.codeforces.com/ по ссылке]. Для входа используйте логин и пароль от вступительного тестирования на ПМИ.

{| class="wikitable"
! №
! Дедлайн
! Темы
|-
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 2 модуль
|-
|}

<!--
== Короткие контесты ==

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

{| class="wikitable" 
|-
! style="text-align:center;"| № !! Дата !! Ссылка !! Дорешивать
|-
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 3 модуль
|-
| 1
| 20.01.2022
| [https://official.contest.yandex.ru/contest/34684/enter Вход]
| До конца 3 модуля
|-
|}
-->


== Экзамены ==
<!--
=== Темы к экзамену 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)) при поиске максимального двудольного паросочетания.

-->

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

=== 2 модуль ===

{| role="presentation" class="mw-collapsible wikitable"
! Дата
! Тип 
! Тема
! Материалы
! Видео
|-
|}

=== 3 модуль ===

{| role="presentation" class="mw-collapsible wikitable"
! Дата
! Тип 
! Тема
! Материалы
! Видео
|-
|}

=== 4 модуль ===

{| role="presentation" class="mw-collapsible wikitable"
! Дата
! Тип 
! Тема
! Материалы
! Видео
|-
|}

== Ссылки на материалы ==
=== Основные источники: ===
# Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ, [2013, 3 издание]
# [https://neerc.ifmo.ru/wiki/index.php neerc.ifmo.ru]

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

<!--
{| class="wikitable"
|-
! Ассистент !! Подгруппа !! Контакты
|-
| colspan="4" style="text-align: center;" | Ассистенты
|-
| Новиков Владимир || 231-1 || [https://t.me/Vladimir_N0vikov @Vladimir_N0vikov]
|-
| Михненко Алексей || 231-2 || [https://t.me/Mangooste @Mangooste]
|-
| Пырко Алексей || 232-1 || [https://t.me/ifrair @ifrair]
|-
| Шулятьев Артём || 232-2 || [https://t.me/tem_shett @tem_shett]
|-
| Ромашов Фёдор || 235-1 || [https://t.me/ormlis @ormlis]
|-
| Лазарев Никита || 235-2 || [https://t.me/vaaven @vaaven]
|-
| Жаймодин Тимофей || || [https://t.me/h0tmi @h0tmi]
|-
| Шайдурова Полина || || [https://t.me/polipolinom @polipolinom]
|}
-->