https://wikicshse.ru/index.php?action=history&feed=atom&title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D0%BF%D0%B8%D0%BB%D0%BE%D1%82%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA_2023%2F2024Алгоритмы и структуры данных пилотный поток 2023/2024 - История изменений2026-06-06T11:26:03ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://wikicshse.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D0%BF%D0%B8%D0%BB%D0%BE%D1%82%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA_2023/2024&diff=955&oldid=previmported>Polinasha960: Migrated current public revision from wiki.cs.hse.ru2023-11-09T13:01:01Z<p>Migrated current public revision from wiki.cs.hse.ru</p>
<p><b>Новая страница</b></p><div>'''Лекторы:''' [https://www.hse.ru/org/persons/210175876 Иван Фёдорович Смирнов], [https://www.hse.ru/org/persons/225527626 Филипп Юрьевич Грибов]<br />
<br />
'''[https://drive.google.com/file/d/1PKxZqRCJQir_tpn_tVFxveFLOU-khiYH/view?usp=sharing Программа курса]'''<br />
<br />
{| class="wikitable"<br />
! colspan="4" | Важные ссылки<br />
|-<br />
| style="text-align: center;vertical-align:top;" | [[Image:Google-Sheets-Logo.png|x100px | link=https://todo.com |Google.Sheets]]<br>[https://docs.google.com/spreadsheets/d/1QYQGPl1Yu51hMZwNfJUnq7O4vGwneVpwYGZOOUZPt7w/edit?usp=sharing Текущая успеваемость]<br />
<br />
| style="text-align: center;vertical-align:top;" | [[Image:Google-Sheets-Logo.png|x100px | link=https://docs.google.com/spreadsheets/d/11vlhxQXSgpwoDJyaQ25r04VzIZKC1EaqBKyqbRIHLHE/edit?usp=sharing |Google.Sheets]]<br>[https://docs.google.com/spreadsheets/d/11vlhxQXSgpwoDJyaQ25r04VzIZKC1EaqBKyqbRIHLHE/edit?usp=sharing Распределение по группам]<br />
<br />
| style="text-align: center;vertical-align:top;" | [[Image:Google-Sheets-Logo.png|x100px | link=https://docs.google.com/spreadsheets/d/1m1b3adccyihLncYx87kKloE7oCSQIRcnLSDXZIH8eo0/edit?usp=sharing |Google.Sheets]]<br><br />
[https://docs.google.com/spreadsheets/d/1m1b3adccyihLncYx87kKloE7oCSQIRcnLSDXZIH8eo0/edit?usp=sharing Запись на консультации]<br />
<br />
| style="text-align: center;vertical-align:top;" | [[Image:Google-Sheets-Logo.png|x100px | link=https://classroom.google.com/c/NjM2MDQxMDM5NzIz?cjc=jh37mqs<br />
|Google.Classroom]]<br>[https://classroom.google.com/c/NjM2MDQxMDM5NzIz?cjc=jh37mqs Сдача ДЗ]<br />
|}<br />
<br />
== Формула выставления итоговой оценки ==<br />
<br />
=== Общее описание ===<br />
<br />
'''Детали в формуле оценивания могут меняться с объявлением на лекциях и в канале.'''<br />
<br />
* Курс длится 4 модуля (со 2-го по 5-й).<br />
* За 2-й и 3-й модуль ставится промежуточная оценка.<br />
* За 4-й модуль ставится итоговая годовая оценка за первый курс, вычисляемая из оценок за 2-4 модули. При этом 4-й модуль является блокирующим, т.е. для получения оценки за курс необходимо иметь удовлетворительную оценку за 4-й модуль.<br />
* За 5-й модуль ставится итоговая оценка независимо.<br />
* Экзамены будут в конце 3-го, 4-го и 5-го модуля. В экзамен 3-го модуля входят темы из 2-3 модулей, в остальные экзамены входят только темы соответствующего модуля.<br />
<br />
Есть несколько видов оцениваемой деятельности, попадающие в накоп с соответствующим коэффициентом (кроме экзамена).<br />
* ('''Конт''', коэфф. 0.3) Длинные контесты.<br />
* ('''ДЗ''', коэфф. 0.25) Теоретические домашние задания.<br />
* ('''КР''', коэфф. 0.15) Письменная контрольная работа.<br />
* ('''Экз''', коэфф. 0.3) Устный экзамен.<br />
<br />
Также на курсе предусмотрены бонусы, добавляемые к итоговой оценке за модуль. Бонусы получить за специальные бонусные контесты, за активное участие в семинарах, за участие в ICPC и, возможно, за что-то ещё.<br />
<br />
=== Подробности ===<br />
<br />
Накоп за каждый модуль считается по формуле '''Накоп''' = (0.3 &middot; '''Конт''' + 0.25 &middot; '''ДЗ''' + 0.15 &middot; '''КР''') / 0.7. Затем для каждого модуля считается предварительная итоговая оценка:<br />
* 2-й модуль: '''Итог<sub>2</sub>''' = '''Накоп<sub>2</sub>''' + '''Бонус<sub>2</sub>'''<br />
* 3-5 модули: '''Итог<sub>i</sub>''' = 0.7 &middot; '''Накоп<sub>i</sub>''' + 0.3 &middot; '''Экз<sub>i</sub>''' + '''Бонус<sub>i</sub>'''<br />
<br />
Итоговые оценки считаются так:<br />
* 2-й модуль: min(10, round('''Итог<sub>2</sub>'''))<br />
* 3-й модуль: min(10, round('''Итог<sub>3</sub>'''))<br />
* 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<br />
* 5-й модуль: min(10, round('''Итог<sub>5</sub>'''))<br />
<br />
Обратите внимание, что в ведомость за каждый модуль ставится округлённое значение, но для подсчёта итоговой оценки за первый курс берётся взвешенное среднее по '''неокруглённым''' оценкам за модули 2, 3, 4.<br />
<br />
Итоговые оценки '''округляются арифметически''' (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).<br />
<br />
=== Оцениваемые активности ===<br />
<br />
===== Контесты =====<br />
Длинные контесты имеют продолжительность порядка двух-трёх недель и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Если не сказано иное, каждая задача стоит одинаково. По умолчанию оценка за контесты вычисляется по формуле '''Конт''' = 10 &middot; (Решено задач / (всего обязательных задач - поправка)). Поправка может применяться, если студент по уважительной причине отсутствовал бо́льшую часть контеста.<br />
<br />
В контестах бывают бонусные необязательные задачи, позволяющие набрать в этой категории более 10 баллов. Иногда формула оценки может меняться: к примеру, в контесте может быть обязательная задача или суммарный балл для двух контестов может вычисляться из минимального числа задач, решённых в каждом из них.<br />
<br />
Короткие контесты — это забытый миф, пыль веков, сага давно минувших дней.<br />
<br />
===== Теор. ДЗ =====<br />
<br />
Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов на консультациях ассистентам. Подробнее об этом написано в соответствующем разделе. Оценка вычисляется по формуле '''ДЗ''' = 10 &middot; (Набрано баллов в задачах / (суммарная стоимость обязательных задач - поправка)). Разные задачи стоят разное число баллов, за решение можно получить частичные баллы.<br />
<br />
Как и в контестах, в ДЗ бывают бонусные задачи, отмеченные звёздочкой. Не гарантируется, что преподаватели сами умеют их решать.<br />
<br />
===== Контрольная работа =====<br />
<br />
В течение каждого модуля предполагается по одной контрольной работе. За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться оценкой '''КР'''. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется формула оценки накопа: '''Накоп''' = (0.3 &middot; '''Конт''' + 0.25 &middot; '''ДЗ''') / 0.55.<br />
<br />
===== Экзамен =====<br />
<br />
За экзамен студент получает оценку от 0 до 10, эта оценка будет являться оценкой '''Экз'''.<br />
<br />
===== Бонус =====<br />
<br />
Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к итоговой оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.<br />
<br />
== <span id="homework"></span>Теоретическое домашнее задание ==<br />
=== <span id="assumptions"> Общие предположения, которыми можно пользоваться в задачах ===<br />
1. Если в задаче говорится про запросы, то по умолчанию online<br />
<br />
2. Если не оговорено иное, можно использовать столько же памяти, сколько времени<br />
<br />
3. Если не оговорено иное, то можно ожидаемое амортизированное время с хешами<br />
<br />
<!--<br />
=== Правила сдачи домашних заданий ===<br />
<br />
1. Некоторые из задач домашнего задания можно сдать только письменно, остальные — как письменно, так и устно.<br />
<br />
2. Для каждого домашнего задания определены два дедлайна: мягкий дедлайн (обычно — через 2 недели) и жёсткий дедлайн (обычно — через 3 недели после выдачи задания).<br />
<br />
3. Вплоть до мягкого дедлайна вы можете сдавать задачи устно любому из шести ассистентов. Для этого необходимо предаварительно [https://docs.google.com/spreadsheets/d/17JZuEJZPFaItPYl6m9ekjmI1jl_h7gWk9cXxDpnRb6Q/edit?usp=sharing записаться на консультацию].<br />
<br />
4. Кроме этого, вплоть до мягкого дедлайна вы можете сдавать задачи письменно в [https://classroom.google.com/c/NDEyODEwMjUzMDIz?cjc=27fucrv Google.Classroom]. Проверкой письменных работ занимаются два ассистента, закреплённые за группой.<br />
<br />
5. Пусть мягкий дедлайн был в день d, а вы сдали работу в день x. Тогда гарантируется, что не позднее, чем в день max(d + 4, x + 7) ваша работа будет проверена и по ней будут оставлены комментарии и пожелания об исправлении. После этого у вас есть возможность единожды исправить проблемы в работе (закрыть уже существующие дыры, но никак не писать новые задачи) и отправить исправленную работу до вплоть до жёсткого дедлайна. Не позднее, чем через 10 дней после жёсткого дедлайна мы гарантируем проверку исправленных работ.<br />
<br />
6. Почти все (кроме, может быть, последних в модуле) домашние задания будут разобраны на семинарах. Разборы будут проводиться не раньше жёсткого дедлайна.<br />
<br />
Написанное выше стоит понимать так: в лучшем сценарии вы решаете задачи и сдаёте какие-то из них (те, которые сложнее всего сдать письменно) устно, а все остальные — письменно. После мягкого дедлайна в течении пары дней ваш ассистент проверяет все работы и отправляет по ним фидбек, после чего у вас несколько дней на исправление недочётов. Мы будем пытаться проверять работы как можно раньше, но не гарантируем ничего лучше, чем описанное в п. 5.<br />
--><br />
<br />
===<span id="classroom"></span>Правила сдачи письменных работ===<br />
<br />
1. Пожалуйста, убедитесь, что вашу работу можно идентифицировать (имя написано в файле, или ваш гугл-аккаунт подписан вашим именем).<br />
<br />
2. При отправке убедитесь, что у вас появилась кнопка "отменить отправку" — это означает, что работа отправлена на проверку.<br />
<br />
3. Домашние задания, сданные не в формате .pdf или набранные не с помощью системы вёрстки LaTeX не принимаются.<br />
<br />
4. Нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки).<br />
<br />
5. Решение должно представлять из себя свзяный цензурный текст без обсценной лексики, который может быть прочитан носителем русского языка, и являть собой решение задачи. Если текст не являет собой решение задачи, не надо прикладывать его к решению.<br />
<br />
6. Списывание в работах повлечёт за собой обнуление баллов по работе.<br />
<br />
7. Если вы не чувствуете себя уверено при работе с LaTeX, используйте шаблон https://www.overleaf.com/read/bpvmhqcvfgqq. В нём отражена основная функциональность системы вёрстки. Вы можете склонировать проект и использовать его.<br />
<br />
<br />
===Список заданий===<br />
<br />
{| class="wikitable"<br />
! №<br />
! Тема<br />
! Листок<br />
! Дедлайн<br />
|-<br />
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 2 модуль<br />
|-<br />
|}<br />
<br />
== Длинные контесты ==<br />
<br />
Все длинные контесты доступны [https://hse.grphil.ru/ по ссылке].<br />
<br />
{| class="wikitable"<br />
! №<br />
! Дедлайн<br />
! Темы<br />
|-<br />
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 2 модуль<br />
|-<br />
|}<br />
<br />
<!--<br />
== Короткие контесты ==<br />
<br />
Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).<br />
<br />
{| class="wikitable" <br />
|-<br />
! style="text-align:center;"| № !! Дата !! Ссылка !! Дорешивать<br />
|-<br />
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 3 модуль<br />
|-<br />
| 1<br />
| 20.01.2022<br />
| [https://official.contest.yandex.ru/contest/34684/enter Вход]<br />
| До конца 3 модуля<br />
|-<br />
|}<br />
--><br />
<br />
<br />
== Экзамены ==<br />
<!--<br />
=== Темы к экзамену 3-го модуля ===<br />
<br />
* Бинарные деревья поиска. Определение, базовые свойства.<br />
* B+-дерево. Простейшие операции. Операции Split и Merge.<br />
* Splay-дерево. Операции. Доказательство амортизированного времени работы.<br />
* Декартово дерево. Операции Split и Merge. Оценка матожидания глубины вершины. Декартово дерево по неявному ключу.<br />
* Запросы на отрезках. Дерево отрезков, общие идеи. Sparse table. Disjoint sparse table.<br />
* Персистентность. Общие идеи, примеры частично и полностью персистентных структур данных. Применение в задачх.<br />
* Методы Path copying и Fat nodes. Их комбинирование для получения частично персистентного списка без штрафа по времени и памяти.<br />
* LCA. Метод двоичных подъёмов. Алгоритм Тарьяна с СНМ. Алгоритм Фараха-Колтона и Бендера.<br />
* Запросы на деревьях. Heavy-light декомпозиция, оптимизация времени работы до O(log n) на запрос.<br />
* Переборные алгоритмы. Подходы через поиск в глубину и поиск в ширину. Способы хеширования состояний. Iterative deepening. Примеры отсечений.<br />
* Кратчайшие пути в графах. Алгоритмы Дейкстры и Форда-Беллмана. Двусторонний алгоритм Дейкстры.<br />
* Алгоритм Contraction Hierarchies для поиска кратчайших путей в графах, возникающих на практике.<br />
* Альфа-бета отсечение в антагонистических играх.<br />
* Мосты, точки сочленения. Построение деревьев компонент рёберной и вершинной двусвязности.<br />
* Конденсация ориентированного графа. Алгоритм Тарьяна.<br />
* Система непересекающихся множеств. Доказательство амортизированного времени работы O(log* n) на запрос.<br />
* Минимальные остовные деревья. Алгоритмы Прима, Краскала, Борувки.<br />
* Линейный вероятностный алгоритм построения MST (в предположении существования алгоритма проверки минимальности за линейное время). Проверка остовного дерева на минимальность за O(m log log n).<br />
* Потоки в сетях. Теорема Форда-Фалкерсона. Примеры решения задач через сведение к минимальному разрезу или максимальному потоку.<br />
* Теорема Кёнига-Эгервари, лемма Холла. Доказательство через теорему Форда-Фалкерсона.<br />
* Алгоритм Эдмондса-Карпа. Алгоритм Диница, доказательство времени работы O(E sqrt(V)) при поиске максимального двудольного паросочетания.<br />
<br />
--><br />
<br />
== Лекции и семинары ==<br />
<br />
=== 2 модуль ===<br />
<br />
{| role="presentation" class="mw-collapsible wikitable"<br />
! Дата<br />
! Тип <br />
! Тема<br />
! Материалы<br />
! Видео<br />
|-<br />
|}<br />
<br />
=== 3 модуль ===<br />
<br />
{| role="presentation" class="mw-collapsible wikitable"<br />
! Дата<br />
! Тип <br />
! Тема<br />
! Материалы<br />
! Видео<br />
|-<br />
|}<br />
<br />
=== 4 модуль ===<br />
<br />
{| role="presentation" class="mw-collapsible wikitable"<br />
! Дата<br />
! Тип <br />
! Тема<br />
! Материалы<br />
! Видео<br />
|-<br />
|}<br />
<br />
== Ссылки на материалы ==<br />
=== Основные источники: ===<br />
# Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ, [2013, 3 издание]<br />
# [https://neerc.ifmo.ru/wiki/index.php neerc.ifmo.ru]<br />
<br />
== Преподаватели и ассистенты == <br />
<br />
<br />
{| class="wikitable"<br />
|-<br />
! Преподаватель !! Подгруппа !! Присутственные часы !! Контакты<br />
|-<br />
| colspan="4" style="text-align: center;" | Преподаватели<br />
|-<br />
| [https://www.hse.ru/org/persons/210175876 Иван Смирнов] || 1 || || [https://t.me/ifsmirnov @ifsmirnov]<br />
|-<br />
| [https://www.hse.ru/org/persons/225527626 Филипп Грибов] || 2 || || [https://t.me/grphil @grphil]<br />
|-<br />
| [https://www.hse.ru/org/persons/738677707 Иван Сафонов] || 3 || || [https://t.me/isaf27 @isaf27]<br />
|-<br />
| Екатерина Фадеева || 4 || || [https://t.me/rediska0123 @rediska0123]<br />
|-<br />
|}<br />
<br />
{| class="wikitable"<br />
|-<br />
! Ассистент !! Подгруппа !! Контакты<br />
|-<br />
| colspan="4" style="text-align: center;" | Ассистенты<br />
|-<br />
| Новиков Владимир || 231-1 || [https://t.me/Vladimir_N0vikov @Vladimir_N0vikov]<br />
|-<br />
| Михненко Алексей || 231-2 || [https://t.me/Mangooste @Mangooste]<br />
|-<br />
| Пырко Алексей || 232-1 || [https://t.me/ifrair @ifrair]<br />
|-<br />
| Шулятьев Артём || 232-2 || [https://t.me/tem_shett @tem_shett]<br />
|-<br />
| Ромашов Фёдор || 235-1 || [https://t.me/ormlis @ormlis]<br />
|-<br />
| Лазарев Никита || 235-2 || [https://t.me/vaaven @vaaven]<br />
|-<br />
| Жаймодин Тимофей || || [https://t.me/h0tmi @h0tmi]<br />
|-<br />
| Шайдурова Полина || || [https://t.me/polipolinom @polipolinom]<br />
|}</div>imported>Polinasha960