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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Новая страница: «Test»)
 
 
(не показано 18 промежуточных версии 3 участников)
Строка 1: Строка 1:
−
Test
+
'''Лектор:''' [https://www.hse.ru/org/persons/210175876 Иван Фёдорович Смирнов]
 +
 
 +
<!-- '''[https://drive.google.com/file/d/1zjs_g2Db8lzkWdI256t9-rpuKApZCRNT/view?usp=sharing Программа курса]''' -->
 +
 
 +
{| class="wikitable"
 +
! colspan="1" | Важные ссылки
 +
|-
 +
| style="text-align: center;vertical-align:top;" | [[Image:Google-Sheets-Logo.png|x100px | link=https://docs.google.com/spreadsheets/d/1yoZ5EtO-odPAiTs8ke6-Ll6EwPnjnFEPjnAcqlOJ4i8/edit?usp=sharing |Google.Classroom]]<br>[https://docs.google.com/spreadsheets/d/1yoZ5EtO-odPAiTs8ke6-Ll6EwPnjnFEPjnAcqlOJ4i8/edit?usp=sharing Текущая успеваемость]
 +
 
 +
| style="text-align: center;vertical-align:top;" | [[Image:Google-Sheets-Logo.png|x100px | link=https://docs.google.com/spreadsheets/d/1_vXpC3EZZ6KJGuRJMuqO_nHBOC1MDQrgbK6LRlcoWuY/edit?usp=sharing |Google.Classroom]]<br>[https://docs.google.com/spreadsheets/d/1_vXpC3EZZ6KJGuRJMuqO_nHBOC1MDQrgbK6LRlcoWuY/edit?usp=sharing Запись на консультации]
 +
|
 +
| style="text-align: center;vertical-align:top;" | [[Image:Google-Sheets-Logo.png|x100px | link=https://docs.google.com/spreadsheets/d/1_vXpC3EZZ6KJGuRJMuqO_nHBOC1MDQrgbK6LRlcoWuY/edit?usp=sharing |Google.Classroom]]<br>[https://classroom.google.com/c/NTY4NjcwMDQ0MjU3?cjc=h4tjjsh Сдача ДЗ]
 +
|}
 +
 
 +
== Формула выставления итоговой оценки ==
 +
'''Формула оценивания пока предварительная и может поменяться!'''
 +
 
 +
Курс длится 4 модуля (со 2-го по 5-й) и предполагает две итоговые оценки: на первом курсе (2-4 модули) и на втором (5 модуль). Оценки за каждый модуль ставятся независимо. Итоговая оценка за первый курс составляется из оценок за 2-4 модули (точные правила будут сообщены позднее). Оценка за 5-й модуль является итоговой оценкой за второй курс.
 +
 
 +
После 3-го, 4-го и 5-го модулей будут экзамены.
 +
 
 +
Правила выставления оценок за модули:
 +
 
 +
'''2-й модуль:''' О<sub>итог</sub>  =  '''0.4286''' &middot; О<sub>контесты</sub> + '''0.3571''' &middot; O<sub>листки</sub> + '''0.2143''' &middot; О<sub>КР</sub> + O<sub>бонус</sub>
 +
 
 +
'''3-й модуль:''' О<sub>итог</sub>  =  '''0.3''' &middot; О<sub>контесты</sub> + '''0.25''' &middot; O<sub>листки</sub> + '''0.15''' &middot; О<sub>КР</sub> + '''0.3''' &middot; О<sub>экзамен</sub> + O<sub>бонус</sub>
 +
 
 +
'''4-й модуль:''' О<sub>итог</sub>  =  '''0.3''' &middot; О<sub>контесты</sub> + '''0.25''' &middot; O<sub>листки</sub> + '''0.15''' &middot; О<sub>КР</sub> + '''0.3''' &middot; О<sub>экзамен</sub> + O<sub>бонус</sub>
 +
 
 +
В ведомость за каждый модуль идёт округлённое значение из формулы выше. Для подсчёта итоговой оценки за год берётся среднее арифметическое по '''неокруглённым''' оценки за модули 2, 3, 4. Если оценка за модуль превышает 10, она считается равной 10.
 +
 
 +
'''Итог за год (1-й курс):''' (min(10, O<sub>2-й модуль</sub>) + min(10, O<sub>3-й модуль</sub>) + min(10, O<sub>4-й модуль</sub>)) / 3
 +
 
 +
<ul>
 +
<!--
 +
<li>
 +
О<sub>контесты</sub> вычисляется по формуле:
 +
{|
 +
| rowspan="2" style="text-align: center;" | О<sub>контесты</sub> = 10 &middot; <span style="font-size:220%; font-weight:light;">(</span>
 +
| style="text-align: center;" | КК + ДК
 +
| rowspan="2" style="text-align: center;" | +
 +
| style="text-align: center;" | БЗ
 +
| rowspan="2" style="text-align: center;" |
 +
| rowspan="2" style="text-align: center;" | <span style="font-size:220%; font-weight:light;">)</span>, где:
 +
|-
 +
| style="text-align: center; border-top:solid 1px black;" align="center"  | ОЗ - поправка
 +
| style="text-align: center; border-top:solid 1px black;" align="center"  | ОЗ
 +
|}
 +
 
 +
* КК — баллы за короткие контесты
 +
* ДК — баллы за длинные контесты (исключая бонусные задачи)
 +
* БЗ — баллы за бонусные задачи в длинных контестах
 +
* ОЗ — общее число задач во всех контестах (исключая бонусные задачи)
 +
* Поправка по умолчанию равна нулю и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.
 +
 
 +
Виды контестов:
 +
 
 +
* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 или 6 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
 +
 
 +
* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''.
 +
 
 +
-->
 +
 
 +
<li> О<sub>листки</sub> вычисляется по формуле:
 +
{|
 +
| rowspan="2" style="text-align: center;" | О<sub>листки</sub> = 10 &middot;
 +
| style="text-align: center;" | количество решённых задач
 +
|-
 +
| style="text-align: center; border-top:solid 1px black;" align="center"  | количество обязательных задач - поправка
 +
|}
 +
 
 +
Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов на консультациях ассистентам.
 +
 
 +
<li> В течение каждого очного модуля предполагается по одной контрольной работе. За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться О<sub>КР</sub>. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
 +
 
 +
<li> За экзамен студент получает оценку от 0 до 10, эта оценка будет являться О<sub>экзамен</sub>.
 +
 
 +
<li> Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.
 +
 
 +
</ul>
 +
 
 +
Итоговая оценка '''округляется арифметически''' (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).
 +
 
 +
== <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://hse.grphil.ru/ по ссылке].
 +
 
 +
{| class="wikitable"
 +
! №
 +
! Дедлайн
 +
! Темы
 +
|-
 +
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 2 модуль
 +
|-
 +
| 1
 +
| 26.11.2022
 +
| Вероятности
 +
|-
 +
| 2
 +
| 10.12.2023
 +
| Простые структуры
 +
|}
 +
 
 +
<!--
 +
== Короткие контесты ==
 +
 
 +
Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 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)) при поиске максимального двудольного паросочетания.
 +
 
 +
== Лекции и семинары ==
 +
 
 +
Записи семинаров, сделанные силами студентов: https://disk.yandex.ru/d/yVmC7VRuXWblIw
 +
 
 +
=== 2 модуль ===
 +
 
 +
{| role="presentation" class="mw-collapsible wikitable"
 +
! Дата
 +
! Тип
 +
! Тема
 +
! Материалы
 +
! Видео
 +
|-
 +
| rowspan="2" | 01.11.2022
 +
| Семинар
 +
| Основные определения, асимптотический рост функций, виды полиномиальности
 +
| <!--[https://drive.google.com/file/d/1ZoUnd7okePTlQxdBZwtB2jRp2QgQrAS7/view?usp=sharing Листочек]-->
 +
| <!--[https://www.youtube.com/watch?v=XdJ4ttt2hc0 Видео]-->
 +
|-
 +
| Лекция
 +
| Знакомство, обзор программы курса, введние в теорию вероятностей
 +
|
 +
| <!--[https://www.youtube.com/watch?v=WYrNMqsDScA Видео]-->
 +
|-
 +
| rowspan="2" | 03.11.2022
 +
| Семинар
 +
| Задачи на теорию вероятностей, конечные вероятностные пространства, геометрическая вероятность
 +
| <!--[https://drive.google.com/file/d/1FN7SzZHSwhKVtNKA6EmHEproKzGXlPCZ/view?usp=sharing Листочек]-->
 +
| <!--[https://www.youtube.com/watch?v=iAmC9FS643k Видео]-->
 +
|-
 +
| Лекция
 +
| Случайные величины. Математическое ожидание, дисперсия, линейность, индикаторные величины.
 +
| <!--[https://drive.google.com/file/d/1iY5YzzpspQqOyuJ_jdAPZHbcSXHDuRQF/view?usp=sharing Материалы]-->
 +
| <!--[https://www.youtube.com/watch?v=irG9tjy2GgM Видео]-->
 +
|}
 +
 
 +
=== 3 модуль ===
 +
 
 +
{| role="presentation" class="mw-collapsible wikitable"
 +
! Дата
 +
! Тип
 +
! Тема
 +
! Материалы
 +
! Видео
 +
|-
 +
| rowspan="2" | 10.01.2023 (вт)
 +
| Семинар
 +
| Антихештесты
 +
| [https://disk.yandex.ru/i/xetD-j0S_pmn-A Листок]
 +
|
 +
|-
 +
| Лекция
 +
| Блум-фильтр. B-деревья.
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 12.01.2023 (чт)
 +
| Семинар
 +
| Деревья поиска
 +
| [https://disk.yandex.ru/i/WwtNchX-N01hlg Листок]
 +
|
 +
|-
 +
| Лекция
 +
| Splay-дерево
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 17.01.2023 (вт)
 +
| Семинар
 +
| Деревья поиска, запросы на отрезках
 +
| [https://disk.yandex.ru/i/LUFR0E6yqgclGg Листок]
 +
|
 +
|-
 +
| Лекция
 +
| Декартово дерево. Доказательство логарифмической высоты.
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 19.01.2023 (чт)
 +
| Семинар
 +
| Запросы на отрезках
 +
| Листки: [https://disk.yandex.ru/d/NCP3V4mzYMXMUA базовый], <br/> [https://disk.yandex.ru/i/RDrpfaX1AQwKQA бонусный]
 +
|
 +
|-
 +
| Лекция
 +
| Частичная персистентность: path copying, fat nodes
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 24.01.2023 (вт)
 +
| Семинар
 +
| Запросы на отрезках, персистентная очередь (бонус)
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| List order maintenance (?)
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 26.01.2023 (чт)
 +
| Семинар
 +
| Задачи на деревья
 +
| [https://disk.yandex.ru/d/uI1OKKPl7fgpEw Листок]
 +
|
 +
|-
 +
| Лекция
 +
| <!-- HLD -->
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 31.01.2023 (вт)
 +
| Семинар
 +
| Простое ДП, задачи о рюкзаке
 +
| [https://disk.yandex.ru/i/AGMSwsEX3GdUYw Листок]
 +
|
 +
|-
 +
| Лекция
 +
| Оптимизация переборов. Подсчёт количества клик в графе.
 +
|
 +
|
 +
|-
 +
| 2.02.2023 (чт)
 +
| Бонусный семинар
 +
| Архитектура, system design
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 7.02.2023 (вт)
 +
| Семинар
 +
| ДП, переборы
 +
| [https://disk.yandex.ru/i/d7oZjXEJv56a4A Листок]
 +
|
 +
|-
 +
| Лекция
 +
| Переборы. Альфа-бета отсечение
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 9.02.2023 (чт)
 +
| Семинар
 +
| ДП, альфа-бета отсечение
 +
| [https://disk.yandex.ru/i/cb63noVLHGy7zg Листок]
 +
|
 +
|-
 +
| Лекция
 +
|
 +
|
 +
|
 +
|-
 +
| 14.02.2023 (вт)
 +
| colspan="4" | Занятий не было
 +
|-
 +
| 16.02.2023 (чт)
 +
| Бонусный семинар
 +
| Модель внешней памяти
 +
| [https://disk.yandex.ru/d/3euDXNlol-JcBQ Листок]
 +
|
 +
|-
 +
| rowspan="2" | 21.02.2023 (вт)
 +
| Семинар
 +
| Пути в графах, кратчайшие и не очень
 +
| [https://disk.yandex.ru/i/NdlcB-1sm9cFlg Листок]
 +
|
 +
|-
 +
| Лекция
 +
| Contraction Hierarchies: поиск кратчайших путей на практике
 +
|
 +
|
 +
|-
 +
| 23.02.2023 (чт)
 +
| colspan="4" | Выходной
 +
|-
 +
| rowspan="2" | 28.02.2023 (вт)
 +
| Семинар
 +
| Разбор КР
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| Линейный алгоритм поиска MST
 +
|
 +
|
 +
|-
 +
| 2.03.2023 (чт)
 +
| Бонусный контест
 +
|
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 7.03.2023 (вт)
 +
| Семинар
 +
| Минимальные остовы
 +
| [https://disk.yandex.ru/d/D3OrHuMgiEzLiw Листок]
 +
|
 +
|-
 +
| Лекция
 +
| Алгоритм Тарьяна для поиска КСС. Неудачное доказательство log* n для СНМ.
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 9.03.2023 (чт)
 +
| Семинар
 +
| Задачи на графы, конденсация, 2-SAT
 +
| [https://disk.yandex.ru/i/B7IW1Rr6wS_Byg Листок]
 +
|
 +
|-
 +
| Лекция
 +
| Доказательство log* n для СНМ. Введение в потоки.
 +
|
 +
|
 +
|}
 +
 
 +
=== 4 модуль ===
 +
 
 +
{| role="presentation" class="mw-collapsible wikitable"
 +
! Дата
 +
! Тип
 +
! Тема
 +
! Материалы
 +
! Видео
 +
|-
 +
| rowspan="1" | 03.04.2023 (вт)
 +
| colspan="4" | Занятий не было
 +
|-
 +
| rowspan="2" | 05.04.2023 (чт)
 +
| Семинар
 +
| colspan="3" | Семинара не было
 +
|-
 +
| Лекция
 +
| Потоки минимальной стоимости
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 11.04.2023 (чт)
 +
| Семинар
 +
| Потоки. Оценки Карзанова.
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| Поиск потока минимальной стоимости за полиномиальное время
 +
|
 +
|
 +
|}
 +
 
 +
== Ссылки на материалы ==
 +
=== Основные источники: ===
 +
# Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ, [2013, 3 издание]
 +
# [https://neerc.ifmo.ru/wiki/index.php neerc.ifmo.ru]
 +
 
 +
== Преподаватели и ассистенты ==
 +
 
 +
 
 +
{| class="wikitable"
 +
|-
 +
! Преподаватель !! Подгруппа !! Присутственные часы !! Контакты
 +
|-
 +
| colspan="4" style="text-align: center;" | Преподаватели
 +
|-
 +
| [https://www.hse.ru/org/persons/210175876 Иван Смирнов] || 221-1 || || [https://t.me/ifsmirnov @ifsmirnov]
 +
|-
 +
| [https://www.hse.ru/org/persons/225527626 Филипп Грибов] || 221-2 || ||
 +
|-
 +
| [https://www.hse.ru/org/persons/738677707 Иван Сафонов] || 222-1 || ||
 +
|-
 +
| Михаил Анопренко || 222-2  || ||
 +
|-
 +
| Сергей Нечаев || 225-1  || ||
 +
|-
 +
| Екатерина Фадеева || 225-2  || ||
 +
|-
 +
<!--
 +
| colspan="4" style="text-align: center;" | Ассистенты
 +
|-
 +
| colspan="2" | Филипп Грибов ||  || [https://teleg.run/grphil @grphil]
 +
|-
 +
| colspan="2" | Максим Деб Натх  || среда, 20:00 || [https://teleg.run/debnatkh @debnatkh]
 +
|-
 +
| Владимир Кауркин || 211 || вторник 20:00  || [https://teleg.run/LordVoldebug @LordVoldebug]
 +
|-
 +
| Игорь Маркелов || 211 || четверг 21:00 || [https://teleg.run/ElderlyPassionFruit @ElderlyPassionFruit]
 +
|-
 +
| Максим Басалаев || 213 || четверг, 19:00 || [https://teleg.run/pojaleesh @pojaleesh]
 +
|-
 +
| Алеся Иванова || 213 || среда 21:00 || [https://teleg.run/alesyaivanova @alesyaivanova]
 +
|-
 +
| Максим Лутан || 215 || суббота, 12:00 (можно договориться о другом дне недели в лс) || [https://teleg.run/Maksim_Lutan @Maksim_Lutan]
 +
|-
 +
| Кирилл Шубников || 215 || среда 21:00 (писать в лс) || [https://teleg.run/Radewoosh51 @Radewoosh51]
 +
-->
 +
|}

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

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


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

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

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

Курс длится 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, O2-й модуль) + min(10, O3-й модуль) + min(10, O4-й модуль)) / 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. В нём отражена основная функциональность системы вёрстки. Вы можете склонировать проект и использовать его.


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

№ Тема Листок Дедлайн
2 модуль

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

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

№ Дедлайн Темы
2 модуль
1 26.11.2022 Вероятности
2 10.12.2023 Простые структуры


Экзамены

Темы к экзамену 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

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

Преподаватель Подгруппа Присутственные часы Контакты
Преподаватели
Иван Смирнов 221-1 @ifsmirnov
Филипп Грибов 221-2
Иван Сафонов 222-1
Михаил Анопренко 222-2
Сергей Нечаев 225-1
Екатерина Фадеева 225-2
Источник — «http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных_пилотный_поток_2022/2023&oldid=77539»