imported>Polinasha960: /* 4 модуль */

2026-05-26T14:35:42Z

4 модуль

Новая страница

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

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

| style="text-align: center;vertical-align:top;" | [[Image:Telegramlogo.png|x100px |
link=https://t.me/hsealbot|Telegram bot]] 
[https://t.me/hsealbot Запись на консультации]

| style="text-align: center;vertical-align:top;" | [[Image:Google-Sheets-Logo.png|x100px |
link=https://classroom.google.com/c/ODIyOTE4MTE2NTEx?cjc=zvznxdzi | Сдача ДЗ]]
[https://classroom.google.com/c/ODIyOTE4MTE2NTEx?cjc=zvznxdzi Сдача ДЗ]

| style="text-align: center;vertical-align:top;" | [[Image:Telegramlogo.png|x100px |
link=https://t.me/+-4MvN6c1CzFmMjI6|Канал с объявлениями]] 
[https://t.me/+-4MvN6c1CzFmMjI6 Канал с объявлениями]

| style="text-align: center;vertical-align:top;" | [[Image:Telegramlogo.png|x100px |
link=https://t.me/+CXWv3aQsylRiYTJi|Чат]] 
[https://t.me/+CXWv3aQsylRiYTJi Чат]

|}

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

Oнакопленная = (0.3 · Оконтесты + 0.25 · Oд/з + 0.15 · Oконтрольная) / 0.7

Во втором модуле:
Oитог 2 = Oнакопленная + Oбонус

В остальных модулях:
Oитог = 0.7 · Oнакопленная + 0.3 · Oэкзамен + Oбонус

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Пожалуйста, называйте файл, который вы загружаете в классрум в следующем формате:

'''<номер группы с подгруппой> <ФИО> ДЗ<Номер дз>'''

Например правильное следующее название файла:

'''251-1 Иванов Иван Иванович ДЗ1.pdf'''

Если вы назовете файл по-другому, то ассистенты будут иметь полное право не проверять ваше дз.

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

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

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

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

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

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

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

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

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

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

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

{| role="presentation" class="mw-collapsible wikitable"
! Дата !! Тема !! Записи прошлых лет
|-
| colspan="4" style="text-align: center; font-weight: bold" | Лекции
|-
| 06.11 || Вводная лекция. Вероятность. Независимость. Условная вероятность. || [https://disk.yandex.ru/i/N7V9SBZ73IB7_Q Я.Диск]
|-
| 11.11 || Случайные величины. Математическое ожидание. || [https://disk.yandex.ru/d/k3xOlSinB06iaw/1-3%20модуль/7_11_Грибов.MP4 Я.Диск]
|-
| 13.11 || RAM-модель. || [https://youtu.be/IdPgYZOs54k?si=zhTFWRK2UCbkyd-6 YouTube]
|-
| 18.11 || Корректность и сложность алгоритмов, использующих рандом. Квадратичные сортировки. Merge-sort. ||[https://youtu.be/92I4Ho0J6wU?si=be1IZzl0WtcvyDit часть 1] и [https://youtu.be/beyP0TU7-94?si=SeLvpojrtVm1bi4p часть 2]
|-
| 25.11 || Quicksort. K-я порядковая за гарантированную линию. Radix sort. || [https://youtu.be/92I4Ho0J6wU?si=be1IZzl0WtcvyDit часть 1] и [https://youtu.be/beyP0TU7-94?si=SeLvpojrtVm1bi4p часть 2]
|-
| 27.11 || Хеши. Семейства хеш-функций. Свойства. Полиномиальное хеширование. Лемма Шварца-Зиппеля. Хеш-таблицы. || [https://youtu.be/HdTnD9yswcE?si=-RGfLFyCvy2I1yBt YouTube]
|-
| 02.12 || Perfect hashing. Cuckoo hashing. Фильтр Блума. Универсальные семейства хеш-функций. k-независимость. || [https://youtu.be/xcJ9K_gE2rw?si=Wa3aMoYVJe_NUrYQ часть 1] и [https://youtu.be/f6fwf62cnNw?si=4_dxtSDqjOQzOQvP часть 2]
|-
| 09.12 || Амортизационный анализ. Монетки/потенциалы. Очередь на 2 стеках. Дек на 3 стеках. Переливания. || [https://youtu.be/MyEYBIxhcuY?si=p5a0KZR03LivI4qJ YouTube]
|-
| 11.12 || Двоичная куча. k-ичная куча. Skiplist. || [https://disk.yandex.ru/d/k3xOlSinB06iaw/1-3%20модуль/21_11_Грибов.MP4 Я.Диск]
|-
| 16.12 || Биномиальная куча. Фибоначчиева куча. || [https://youtu.be/ZXJ0Gl6caVU?si=EzFWFxUqWkE7Y-zD YouTube] и [https://www.youtube.com/watch?v=IXcdJuRbqPU YouTube]
|-
| colspan="4" style="text-align: center; font-weight: bold" | Семинары
|}

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

{| role="presentation" class="mw-collapsible wikitable"
! Дата !! Тема !! Записи прошлых лет
|-
| colspan="4" style="text-align: center; font-weight: bold" | Лекции
|-
| 13.01 || Модель внешней памяти. Sort во внешней памяти. List Ranking || [https://disk.yandex.ru/i/YAmeWO3Xn1DtLw Я.Диск]
|-
| 15.01 || 2-3-дерево. B+ дерево. Cache-Oblivious Lookahead Array || [https://disk.yandex.ru/i/QoVP9sQr-l9Sig Я.Диск]
|-
| 20.01 || Splay || [https://disk.yandex.ru/i/fcm29gRblAkrPw Я.Диск]
|-
| 22.01 || HLD. Link-cut || [https://disk.yandex.ru/i/VRbiDrLALBorag Я.Диск]
|-
| 27.01 || Персистентность (стек, массив, ДО, деревья поиска). Частичная персистентность (двусвязный список, 2-3-4-5 дерево) || [https://youtu.be/HlqN5ly-ROU?si=3qqpjd8cGc3mvc9O YouTube] и [https://youtu.be/4ZtBK6zIp08?si=Bg0I4Kvzu3zhdzAB YouTube]
|-
| 29.01 || LCA. Бинподъемы. ФКБ (+ алгоритм со стеком для RMQ). Disjoint Sparse Table. || [https://disk.yandex.ru/i/gf1VvYlXc4K0WA Я.Диск] или [https://youtu.be/vkBtUfJFOtQ?si=1736jweYrV03fowB YouTube]
|-
| 03.02 || LA. Лестничная декомпозиция. Алгоритм 4 русских || [https://youtu.be/VG1y_xJUOxc?si=mDqY3e_kSSGWfhGn YouTube]
|-
| 10.02 || Разделяй-и-властвуй. Oптимизация Кнута. Неравенство четырехугольника. Convex hull trick с обновлением при неотсортированных коэффициентах прямых. Дерево Ли-Чао c операциями на отрезке || [https://disk.yandex.ru/i/NidC_oJaoScCnQ Я.Диск]
|-
| 12.02 || Матроиды. Базовые определения, примеры. Алгоритм Радо-Эдмондса, субмодулярность ранговой функции, понятие пересечения матроидов || [https://disk.yandex.ru/i/WiqIE64lpPmTIg Я.Диск]
|-
| 17.02 || Алгоритм поиска множества максимального размера в пересечении матроидов. || [https://www.youtube.com/watch?v=6t7IXE4ueDM Youtube] и [https://www.youtube.com/watch?v=9BZHxgp4Hz0 Youtube]
|-
| 24.02 || Метод Ньютона. Доказательство локальной квадратичной скорости сходимости и начального приближения, при котором будет такая скорость. || [https://disk.yandex.ru/i/jFiuP7QJJzPSjw Я.Диск]
|-
| 26.02 || DFT. Алгоритм Кули-Тьюки. Обратное преобразование к DFT. || [https://disk.yandex.ru/i/FU-LxFDDL3PhBQ Я.Диск]
|-
| 03.03 || DFT по модулю, поиск первообразных. Подсчет Or и And-сверток через задачу Sum Over Subsets. Xor-свертка и преобразование Уолша-Адамара. ||
|-
| 10.03 || Проверка точки на принадлежность выпуклому/произвольному многоугольнику. Касательные к выпуклому многоугольнику, параллельные прямой. || [https://disk.yandex.ru/i/jf3BB1f5va--IQ Я.Диск]
|-
| 12.03 || Поиск самых удаленных точек (вращающиеся калиперы). Касательные к выпуклому многоугольнику из точки. Сумма Минковского. || [https://disk.yandex.ru/i/jKQ7HYHlivEc9A Я.Диск]
|-
| 17.03 || Рандомные алгоритмы в геометрии: MinDisk, две ближайшие точки, пересечение полуплоскостей. || [https://disk.yandex.ru/i/Hfgei6E7hJILNw Я.Диск]
|-
| 19.03 || Метод Монте-Карло. || [https://disk.yandex.ru/i/RQouCPiRVmz2Ew Я.Диск]
|-
| colspan="4" style="text-align: center; font-weight: bold" | Семинары
|-
| 12.02 || Альфа-бета отсечение, время работы при случайном обходе дерева || [https://disk.yandex.ru/i/KbDw3pZPBsbHDg Я.Диск]
|-
| 26.02 || Мастер теорема ||
|-
| 19.03 || Тернарный поиск. Достаточное условие сходимости в многомерном случае || [https://disk.yandex.ru/i/SReMdRw7O-f05A Я. Диск]
|}

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

{| role="presentation" class="mw-collapsible wikitable"
! Дата !! Тема !! Записи прошлых лет
|-
| colspan="4" style="text-align: center; font-weight: bold" | Лекции
|-
| 02.04 || Простые алгоритмы на графах: поиск компонент сильной связности, поиск эйлерового цикла, 2-SAT || [https://disk.yandex.ru/i/oarrNsOfgyvNhQ Я.Диск]
|-
| 07.04 || СНМ: доказательство времени работы с различными эверистиками. Алгоритм Прима и алгоритм Краскала для поиска остовного дерева минимального веса || [https://youtu.be/J3BeNJ8BKJk?si=i7lR-mkXK9cYYhqd Youtube] и [https://disk.yandex.ru/i/1EajCIqJDLZ6ug Я.Диск]
|-
| 09.04 || Алгоритм Борувки. Поиск минимального остовного дерева за O(n) || [https://disk.yandex.ru/i/Tm41SZuNOVeOig Я.Диск]
|-
| 14.04 || Cache-aware и cache-oblivious алгоритмы || [https://disk.yandex.ru/i/uYOFeuhmYlhKwA Я.Диск]
|-
| 16.04 || Алгоритмы на графах во внешней памяти: BFS во внешней памяти и поиск компонент связности ||
|-
| 21.04 || Алгоритм Куна. Максимальное независимое множество в двудольном графе. Покрытие ориентированного графа путями || [https://youtu.be/aml_nFXffcM?si=LKRJSKwN4PyeSxDz Youtube]
|-
| 28.04 || Потоки, основные определения. Теорма Форда-Фалкерсона с доказательством. Алгоритмы Форда-Фалкерсона и Эдмонса-Карпа || [https://disk.yandex.ru/i/dFWreJ_xkwWcjg Я.Диск]
|-
| 30.04 || Алгоритм построения декомпозиции потока. Алгоритм Диница || [https://disk.yandex.ru/i/-9lIpg2isyw9OQ Я.Диск]
|-
| 12.05 || Метод проталкивания предпотока. Алгоритм push-relabel ||
|-
| 14.05 || Глобальный минимальный разрез. Алгоритмы Штор-Вагнера и Карагера-Штейна. || [https://disk.yandex.ru/i/4efKersRuYtj1g Я.Диск]
|-
| 19.05 || Стоимостные потоки. Поиск максимального потока минимальной стоимости || [https://disk.yandex.ru/i/WsV_m6dkjROihA Я.Диск]
|-
| 21.05 || Задача о назначениях. Венгерский алгоритм || [https://disk.yandex.ru/i/gNLmLneFriaslw Я.Диск]
|-
| 26.05 || Оптимизации переборных задач. Поиск макс клики за 2^{0.45n}. MITM. Алгоритм Шрёппеля-Шамира. Алгоритм Хиршберга. || [https://disk.yandex.ru/i/Q4NLkAGviDRM1g Я.Диск]
|-
| colspan="4" style="text-align: center; font-weight: bold" | Семинары
|}

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

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

{| class="wikitable"
|-
! Ассистент !! Подгруппа !! Контакты
|-
| Ижицкий Тимофей || 251-1 || [https://t.me/TimofeyIzhitskiy @TimofeyIzhitskiy]
|-
| Пискарев Иван || 251-2 || [https://t.me/piskarev_i @piskarev_i]
|-
| Агафонов Артём || 252-1 || [https://t.me/Agafonov_Artem @Agafonov_Artem]
|-
| Любин Михаил || 252-2 || [https://t.me/Noinoiio @Noinoiio]
|-
| Павлов Андрей || 253-1 || [https://t.me/Semi4 @Semi4]
|-
| Жукова Елизавета || 253-2 || [https://t.me/elizazh @elizazh]
|-
| Кривощеков Виктор || 256-1 || [https://t.me/robivirt @robivirt]
|-
| Кононов Олег || 256-2 || [https://t.me/A1btwo @A1btwo]
|-
| Понкратов Александр || || [https://t.me/TheEvilBird @TheEvilBird]
|-
| Сулейманов Карам || || [https://t.me/s_k_a_r_a @s_k_a_r_a]
|}

Алгоритмы и структуры данных пилотный поток 2025/2026 - История изменений

imported>Polinasha960: /* 4 модуль */