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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показано 17 промежуточных версии 3 участников)
Строка 1: Строка 1:
−
'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]
+
'''Лектор:''' [https://www.hse.ru/org/persons/210175876 Иван Фёдорович Смирнов]
  
−
'''[https://drive.google.com/file/d/1zjs_g2Db8lzkWdI256t9-rpuKApZCRNT/view?usp=sharing Программа курса]'''
+
<!-- '''[https://drive.google.com/file/d/1zjs_g2Db8lzkWdI256t9-rpuKApZCRNT/view?usp=sharing Программа курса]''' -->
  
 
{| class="wikitable"
 
{| class="wikitable"
−
! colspan="4" | Важные ссылки
+
! colspan="1" | Важные ссылки
 
|-
 
|-
−
| style="text-align: center;vertical-align:top;" | [[Image:Google-Sheets-Logo.png|x100px | link=https://docs.google.com/spreadsheets/d/1bRg_nUNZxfPY-JxFXvzAvPb-GwWZ8Cv8gxJSJgo-uhA/edit?usp=sharing |Google.Classroom]]<br>[https://docs.google.com/spreadsheets/d/1bRg_nUNZxfPY-JxFXvzAvPb-GwWZ8Cv8gxJSJgo-uhA/edit?usp=sharing Текущая успеваемость]<br>[https://docs.google.com/spreadsheets/d/1bRg_nUNZxfPY-JxFXvzAvPb-GwWZ8Cv8gxJSJgo-uhA/htmlview html-версия]
+
| 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-Classroom-Logo.png|x100px | link=https://classroom.google.com |Google.Classroom]]<br>[https://classroom.google.com/c/NDEyODEwMjUzMDIz?cjc=27fucrv Google.Classroom]<br>инвайт: <code>27fucrv</code>
+
 
−
| style="text-align: center;vertical-align:top;" | [[Image:Google-Sheets-Logo.png|x100px | link=https://docs.google.com/spreadsheets/d/17JZuEJZPFaItPYl6m9ekjmI1jl_h7gWk9cXxDpnRb6Q/edit?usp=sharing |Google.Classroom]]<br>[https://docs.google.com/spreadsheets/d/17JZuEJZPFaItPYl6m9ekjmI1jl_h7gWk9cXxDpnRb6Q/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:Youtube-logo.png|x100px | link=https://www.youtube.com/playlist?list=PLEwK9wdS5g0p4lTp0x7xgH2CICLvM4rTy]]<br>[https://www.youtube.com/playlist?list=PLEwK9wdS5g0p4lTp0x7xgH2CICLvM4rTy Плейлист с записями лекций]
+
|
 +
| 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 Сдача ДЗ]
 
|}
 
|}
  
Строка 15: Строка 16:
 
'''Формула оценивания пока предварительная и может поменяться!'''
 
'''Формула оценивания пока предварительная и может поменяться!'''
  
−
'''4 модуль:''' О<sub>итог</sub>  =  '''0.3''' &middot; О<sub>контесты (4 модуль)</sub> + '''0.25''' &middot; O<sub>листки (4 модуль)</sub> + '''0.15''' &middot; O<sub>контрольная</sub> + '''0.3''' &middot; O<sub>экзамен</sub> + O<sub>бонус</sub>
+
Курс длится 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>
  
−
'''3 модуль:''' О<sub>итог</sub>  =  '''0.3''' &middot; О<sub>контесты (2 + 3 модуль)</sub> + '''0.25''' &middot; O<sub>листки (2 + 3 модуль)</sub> + '''0.15''' &middot; O<sub>контрольная</sub> + '''0.3''' &middot; O<sub>экзамен</sub> + O<sub>бонус</sub>
+
В ведомость за каждый модуль идёт округлённое значение из формулы выше. Для подсчёта итоговой оценки за год берётся среднее арифметическое по '''неокруглённым''' оценки за модули 2, 3, 4. Если оценка за модуль превышает 10, она считается равной 10.
  
−
'''2 модуль:''' О<sub>итог</sub>  =  '''0.53571428572''' &middot; О<sub>контесты</sub> + '''0.46428571428''' &middot; O<sub>листки</sub> + O<sub>бонус</sub>
+
'''Итог за год (1-й курс):''' (min(10, O<sub>2-й модуль</sub>) + min(10, O<sub>3-й модуль</sub>) + min(10, O<sub>4-й модуль</sub>)) / 3
  
 
<ul>
 
<ul>
 +
<!--
 
<li>
 
<li>
 
О<sub>контесты</sub> вычисляется по формуле:
 
О<sub>контесты</sub> вычисляется по формуле:
Строка 47: Строка 59:
  
 
* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''.
 
* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''.
 +
 +
-->
  
 
<li> О<sub>листки</sub> вычисляется по формуле:
 
<li> О<sub>листки</sub> вычисляется по формуле:
Строка 56: Строка 70:
 
|}
 
|}
  
−
Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов, на консультациях ассистентам.
+
Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов на консультациях ассистентам.
  
−
<li> В течение каждого очного модуля предполагается по одной контрольной работе (так было до перехода в онлайн). За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться О<sub>КР</sub>. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
+
<li> В течение каждого очного модуля предполагается по одной контрольной работе. За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться О<sub>КР</sub>. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
  
−
<li> За [[Алгоритмы_и_структуры_данных_пилотный_поток_2020/2021#Экзамены | экзамен]]
+
<li> За экзамен студент получает оценку от 0 до 10, эта оценка будет являться О<sub>экзамен</sub>.
−
студент получает оценку от 0 до 10, эта оценка будет являться О<sub>экз</sub>.
+
  
 
<li> Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.
 
<li> Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.
Строка 77: Строка 90:
 
3. Если не оговорено иное, то можно ожидаемое амортизированное время с хешами
 
3. Если не оговорено иное, то можно ожидаемое амортизированное время с хешами
  
 +
<!--
 
=== Правила сдачи домашних заданий ===
 
=== Правила сдачи домашних заданий ===
  
Строка 92: Строка 106:
  
 
Написанное выше стоит понимать так: в лучшем сценарии вы решаете задачи и сдаёте какие-то из них (те, которые сложнее всего сдать письменно) устно, а все остальные — письменно. После мягкого дедлайна в течении пары дней ваш ассистент проверяет все работы и отправляет по ним фидбек, после чего у вас несколько дней на исправление недочётов. Мы будем пытаться проверять работы как можно раньше, но не гарантируем ничего лучше, чем описанное в п. 5.
 
Написанное выше стоит понимать так: в лучшем сценарии вы решаете задачи и сдаёте какие-то из них (те, которые сложнее всего сдать письменно) устно, а все остальные — письменно. После мягкого дедлайна в течении пары дней ваш ассистент проверяет все работы и отправляет по ним фидбек, после чего у вас несколько дней на исправление недочётов. Мы будем пытаться проверять работы как можно раньше, но не гарантируем ничего лучше, чем описанное в п. 5.
 +
-->
  
 
===<span id="classroom"></span>Правила сдачи письменных работ===
 
===<span id="classroom"></span>Правила сдачи письменных работ===
Строка 107: Строка 122:
 
6. Списывание в работах повлечёт за собой обнуление баллов по работе.
 
6. Списывание в работах повлечёт за собой обнуление баллов по работе.
  
−
7. Если вы не чувствуете себя уверено при работе с LaTeX, используйте шаблон https://www.overleaf.com/read/bpvmhqcvfgqq. В нём отражена основаня функциональность системы вёрстки. Вы можете склонировать проект и использовать его
+
7. Если вы не чувствуете себя уверено при работе с LaTeX, используйте шаблон https://www.overleaf.com/read/bpvmhqcvfgqq. В нём отражена основная функциональность системы вёрстки. Вы можете склонировать проект и использовать его.
  
  
Строка 116: Строка 131:
 
! Тема
 
! Тема
 
! Листок
 
! Листок
−
! Мягкий дедлайн
+
! Дедлайн
−
! Жесткий дедлайн
+
 
|-
 
|-
−
| colspan="5" style="text-align: center; background-color:#dae8fc;" | 2 модуль
+
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 2 модуль
 
|-
 
|-
−
| 1
 
−
| Вероятности и математическое ожидание
 
−
| [https://drive.google.com/file/d/1uP6YIwqWJiMtjPPHGn5ykleR7shjyAtt/view?usp=sharing Листок]
 
−
| 14.11.2021
 
−
| 22.11.2021
 
−
|-
 
−
| 2
 
−
| Сортировки
 
−
| [https://drive.google.com/file/d/1sdjjrP0TiIFM39Ki6fM6O-L2apcW39dl/view?usp=sharing Листок]
 
−
| 24.11.2021
 
−
| 01.12.2021
 
−
|-
 
−
| 3
 
−
| Простые структуры данных и амортизационный анализ
 
−
| [https://drive.google.com/file/d/1Pk5RHEpI3U3MnL7LBJGy7tLtCN7zbtap/view?usp=sharing Листок]
 
−
| 06.12.2021
 
−
| 13.12.2021
 
−
|-
 
−
| 4
 
−
| Кучи, хеши
 
−
| [https://drive.google.com/file/d/1aI25RLurWWPbZ9WH6_e2MYk2984srxAK/view?usp=sharing Листок]
 
−
| 17.12.2021
 
−
| 25.12.2021
 
−
|-
 
−
| colspan="5" style="text-align: center; background-color:#dae8fc;" | 3 модуль
 
−
|-
 
−
| 5
 
−
| Структуры данных
 
−
| [https://drive.google.com/file/d/1qVeUGutzLUZnSFlDmeNnSlEgH_zLhYOB/view?usp=sharing Листок]
 
−
| 31.01.2022
 
−
| 07.02.2022
 
−
|-
 
−
| 6
 
−
| Структуры данных 2
 
−
| [https://drive.google.com/file/d/1JJ9VcAV7vzw26_DH5zUREOXEmXbjcaUz/view?usp=sharing Листок]
 
−
| 15.02.2022
 
−
| 22.02.2022
 
−
|-
 
−
 
 
|}
 
|}
  
 
== Длинные контесты ==
 
== Длинные контесты ==
 +
 +
Все длинные контесты доступны [https://hse.grphil.ru/ по ссылке].
  
 
{| class="wikitable"
 
{| class="wikitable"
Строка 168: Строка 145:
 
! Дедлайн
 
! Дедлайн
 
! Темы
 
! Темы
−
! Ссылка
 
 
|-
 
|-
 
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 2 модуль
 
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 2 модуль
 
|-
 
|-
 
| 1
 
| 1
−
| 01.12.2021
+
| 26.11.2022
−
| Вероятности, упорядоченные данные, простые структуры
+
| Вероятности
−
| [https://official.contest.yandex.ru/contest/31144 Вход]
+
 
|-
 
|-
 
| 2
 
| 2
−
| 09.12.2021
+
| 10.12.2023
−
| Вероятности, сортировки, простые структуры, кучи
+
| Простые структуры
−
| [https://official.contest.yandex.ru/contest/31739 Вход]
+
−
|-
+
−
| 3
+
−
| 18.12.2021
+
−
| Хеши
+
−
| [https://official.contest.yandex.ru/contest/32954 Вход]
+
−
|-
+
−
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 3 модуль
+
−
|-
+
−
| 4
+
−
| 05.02.2022
+
−
| Деревья поиска, структуры данных, задача на ревью
+
−
| [https://official.contest.yandex.ru/contest/34590 Вход]
+
−
|-
+
−
| 5
+
−
| 19.02.2022
+
−
| Персистентность, динамическое программирование, переборы
+
−
| [https://official.contest.yandex.ru/contest/34885 Вход]
+
−
|-
+
−
| 6
+
−
| 12.03.2022
+
−
| Графы, снм
+
−
| [https://official.contest.yandex.ru/contest/35631 Вход]
+
−
|-
+
−
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 4 модуль
+
−
|-
+
−
| 7
+
−
| 7.05.2022
+
−
| Паросочетания, потоки
+
−
| [https://official.contest.yandex.ru/contest/37311 Вход]
+
−
|-
+
−
| 8
+
−
| 4.06.2022
+
−
| Строки, формальные языки
+
−
| [https://official.contest.yandex.ru/contest/38048/enter Вход]
+
 
|}
 
|}
  
 +
<!--
 
== Короткие контесты ==
 
== Короткие контесты ==
  
Строка 233: Строка 174:
 
|-
 
|-
 
|}
 
|}
 +
-->
  
 
== Экзамены ==
 
== Экзамены ==
 +
=== Темы к экзамену 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)) при поиске максимального двудольного паросочетания.
  
 
== Лекции и семинары ==
 
== Лекции и семинары ==
  
−
=== 3 модуль ===
+
Записи семинаров, сделанные силами студентов: https://disk.yandex.ru/d/yVmC7VRuXWblIw
 +
 
 +
=== 2 модуль ===
  
 
{| role="presentation" class="mw-collapsible wikitable"
 
{| role="presentation" class="mw-collapsible wikitable"
Строка 247: Строка 214:
 
! Видео
 
! Видео
 
|-
 
|-
−
| rowspan="2" | 11.01.2022
+
| rowspan="2" | 01.11.2022
 
| Семинар  
 
| Семинар  
−
| Деревья поиска
+
| Основные определения, асимптотический рост функций, виды полиномиальности
−
| [https://drive.google.com/file/d/1p09Bz3aMYX_HZbQdDmzk2t87HtkWmIPD/view?usp=sharing Листочек]
+
| <!--[https://drive.google.com/file/d/1ZoUnd7okePTlQxdBZwtB2jRp2QgQrAS7/view?usp=sharing Листочек]-->
−
|  
+
| <!--[https://www.youtube.com/watch?v=XdJ4ttt2hc0 Видео]-->
 
|-  
 
|-  
 
| Лекция
 
| Лекция
−
| Первая очная лекция! Бинарные деревья поиска, 2-3 дерево, декартово дерево
+
| Знакомство, обзор программы курса, введние в теорию вероятностей
 
|
 
|
−
| [https://www.youtube.com/watch?v=Wa2II3ZDeM0 Видео]
+
| <!--[https://www.youtube.com/watch?v=WYrNMqsDScA Видео]-->
 
|-
 
|-
−
| rowspan="2" | 13.01.2022
+
| rowspan="2" | 03.11.2022
 
| Семинар  
 
| Семинар  
−
| Деревья Тарьяна-Слейтера (Splay дерево)
+
| Задачи на теорию вероятностей, конечные вероятностные пространства, геометрическая вероятность
−
| [https://drive.google.com/file/d/16MAIZAm1bwOg6nn0GkRbX_fAK-pxK20R/view?usp=sharing Листочек]
+
| <!--[https://drive.google.com/file/d/1FN7SzZHSwhKVtNKA6EmHEproKzGXlPCZ/view?usp=sharing Листочек]-->
−
| [https://www.youtube.com/watch?v=QQnK9sdPzso Видео]
+
| <!--[https://www.youtube.com/watch?v=iAmC9FS643k Видео]-->
−
|-  
+
|-
 
| Лекция
 
| Лекция
−
| Структуры данных для запросов на отрезках
+
| Случайные величины. Математическое ожидание, дисперсия, линейность, индикаторные величины.
−
|
+
| <!--[https://drive.google.com/file/d/1iY5YzzpspQqOyuJ_jdAPZHbcSXHDuRQF/view?usp=sharing Материалы]-->
−
| [https://www.youtube.com/watch?v=4TTYrCTV4h8 Видео]
+
| <!--[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 Листок]
 +
|
 
|-
 
|-
−
| rowspan="2" | 18.01.2022
 
−
| Семинар
 
−
| Задачи на деревья поиска и запросы на отрезках
 
−
| [https://drive.google.com/file/d/1FpjZGqaJnUnapRR7hI9kqHLes544FI3e/view?usp=sharing Листочек]
 
−
| [https://www.youtube.com/watch?v=HAMIhpnmQf8 Видео]
 
−
|-
 
 
| Лекция
 
| Лекция
−
| Корневые деревья, LCA, LA, метод четырёх русских
+
| Блум-фильтр. B-деревья.
 +
|
 
|
 
|
−
| [https://www.youtube.com/watch?v=vkBtUfJFOtQ Видео]
 
 
|-
 
|-
−
| 20.01.2022
+
| rowspan="2" | 12.01.2023 (чт)
−
| Короткий контест
+
| Семинар
−
| Короткий контест 1
+
| Деревья поиска
−
| [https://official.contest.yandex.ru/contest/34684/enter Вход]
+
| [https://disk.yandex.ru/i/WwtNchX-N01hlg Листок]
 
|
 
|
 
|-
 
|-
−
| rowspan="2" | 25.01.2022
 
−
| Семинар
 
−
| Задачи на запросы на отрезках
 
−
| [https://drive.google.com/file/d/19JkY2MhvDtwiNzCZ223ZnbuzWqhT9Mvj/view?usp=sharing Листочек]
 
−
| [https://www.youtube.com/watch?v=I3cthrjK7LY Видео]
 
−
|-
 
 
| Лекция
 
| Лекция
−
| Персистентные структуры данных
+
| Splay-дерево
 +
|
 
|
 
|
−
| [https://www.youtube.com/watch?v=VG1y_xJUOxc Видео]
 
 
|-
 
|-
−
| rowspan="2" | 27.01.2022
+
| rowspan="2" | 17.01.2023 (вт)
−
| Семинар  
+
| Семинар
−
| Запросы на деревьях и персистентность
+
| Деревья поиска, запросы на отрезках
−
| [https://drive.google.com/file/d/1V4sUB-iXgjl1W-DBQIMS_PxBs9zz4gSl/view?usp=sharing Листочек]
+
| [https://disk.yandex.ru/i/LUFR0E6yqgclGg Листок]
−
|
+
−
|-
+
−
| Лекция
+
−
| Частично персистентное бинарное дерево поиска без штрафа по времени и памяти
+
 
|
 
|
−
|
 
 
|-
 
|-
−
| rowspan="2" | 01.03.2022
+
| Лекция
−
| семинар
+
| Декартово дерево. Доказательство логарифмической высоты.
−
| Ещё задачи на структуры и персистентность
+
 
|
 
|
 
|
 
|
 
|-
 
|-
−
| лекция
+
| rowspan="2" | 19.01.2023 (чт)
−
| Метод перебора в задачах оптимизации и генерации комбинаторных объектов. Динамическое программирование, meet-in-the-middle
+
| Семинар
−
|
+
| Запросы на отрезках
 +
| Листки: [https://disk.yandex.ru/d/NCP3V4mzYMXMUA базовый], <br/> [https://disk.yandex.ru/i/RDrpfaX1AQwKQA бонусный]
 
|
 
|
 
|-
 
|-
−
| rowspan="2" | 03.03.2022
+
| Лекция
−
| семинар
+
| Частичная персистентность: path copying, fat nodes
−
| Разбор ДЗ + задачи на ДП
+
 
|
 
|
 
|
 
|
 
|-
 
|-
−
| лекция
+
| rowspan="2" | 24.01.2023 (вт)
−
| Эвристические методы оптимизации перебора
+
| Семинар
 +
| Запросы на отрезках, персистентная очередь (бонус)
 
|
 
|
 
|
 
|
 
|-
 
|-
−
| rowspan="2" | 08.03.2022
+
| Лекция
−
| семинар
+
| List order maintenance (?)
−
| Разбор дз на структуры данных + задачи на ДП и перебор
+
 
|
 
|
 
|
 
|
 
|-
 
|-
−
| лекция
+
| rowspan="2" | 26.01.2023 (чт)
−
| Асимптотические оптимизации перебора, перебор в играх с нулевой суммой, альфа-бета отсечение
+
| Семинар
−
|
+
| Задачи на деревья
 +
| [https://disk.yandex.ru/d/uI1OKKPl7fgpEw Листок]
 
|
 
|
 
|-
 
|-
−
| rowspan="2" | 15.03.2022
+
| Лекция
−
| семинар
+
| <!-- HLD -->
−
| Разбор КР + разбор ДЗ
+
 
|
 
|
 
|
 
|
 
|-
 
|-
−
| лекция
+
| rowspan="2" | 31.01.2023 (вт)
−
| Обходы графов в глубину и ширину, их основные применения, компоненты связности, мосты и точки сочленения, 2-SAT
+
| Семинар
−
|
+
| Простое ДП, задачи о рюкзаке
 +
| [https://disk.yandex.ru/i/AGMSwsEX3GdUYw Листок]
 
|
 
|
 
|-
 
|-
−
| rowspan="2" | 17.03.2022
+
| Лекция
−
| семинар
+
| Оптимизация переборов. Подсчёт количества клик в графе.
−
|
+
 
|
 
|
 
|
 
|
 
|-
 
|-
−
| лекция
+
| 2.02.2023 (чт)
−
| Кратчайшие пути во взвешенных графах, потенциалы Джонсона, эвристика A*
+
| Бонусный семинар
 +
| Архитектура, system design
 
|
 
|
 
|
 
|
 
|-
 
|-
−
| rowspan="2" | 22.03.2022
+
| rowspan="2" | 7.02.2023 (вт)
−
| семинар
+
| Семинар
−
|  
+
| ДП, переборы
−
|
+
| [https://disk.yandex.ru/i/d7oZjXEJv56a4A Листок]
 
|
 
|
 
|-
 
|-
−
| лекция
+
| Лекция
−
| Задача о минимальном остове, алгоритмы нахождения минимального остова и критерии оптимальности
+
| Переборы. Альфа-бета отсечение
 
|
 
|
 
|
 
|
 
|-
 
|-
−
| rowspan="2" | 01.03.2022
+
| rowspan="2" | 9.02.2023 (чт)
−
| семинар
+
| Семинар
−
|  
+
| ДП, альфа-бета отсечение
−
|
+
| [https://disk.yandex.ru/i/cb63noVLHGy7zg Листок]
 
|
 
|
 
|-
 
|-
−
| лекция
+
| Лекция
−
| Графовые алгоритмы в модели со внешней памятью. Задача list ranking
+
 
|
 
|
 
|
 
|
−
|-
 
−
| rowspan="2" | 03.03.2022
 
−
| семинар
 
−
|
 
 
|
 
|
 +
|-
 +
| 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 Листок]
 
|
 
|
 
|-
 
|-
−
| rowspan="2" | 10.03.2022
+
| Лекция
−
| семинар
+
| Contraction Hierarchies: поиск кратчайших путей на практике
−
|  
+
 
|
 
|
 
|
 
|
 
|-
 
|-
−
| лекция
+
| 23.02.2023 (чт)
−
| Задача о максимальном потоке, теорема о декомпозиции потока, теорема Форда-Фалкерсона
+
| colspan="4" | Выходной
 +
|-
 +
| rowspan="2" | 28.02.2023 (вт)
 +
| Семинар
 +
| Разбор КР
 
|
 
|
 
|
 
|
 
|-
 
|-
−
| rowspan="2" | 15.03.2022
+
| Лекция
−
| семинар
+
| Линейный алгоритм поиска MST
−
|  
+
 
|
 
|
 
|
 
|
 
|-
 
|-
−
| лекция
+
| 2.03.2023 (чт)
−
| Полиномиальные алгоритмы решения задачи о максимальном потоке
+
| Бонусный контест
 +
|
 
|
 
|
 
|
 
|
 
|-
 
|-
−
| rowspan="2" | 17.03.2022
+
| rowspan="2" | 7.03.2023 (вт)
−
| семинар
+
| Семинар
−
|  
+
| Минимальные остовы
−
|
+
| [https://disk.yandex.ru/d/D3OrHuMgiEzLiw Листок]
 
|
 
|
 
|-
 
|-
−
| лекция
+
| Лекция
−
|  
+
| Алгоритм Тарьяна для поиска КСС. Неудачное доказательство log* n для СНМ.
 
|
 
|
 
|
 
|
 
|-
 
|-
−
| rowspan="2" | 22.03.2022
+
| rowspan="2" | 9.03.2023 (чт)
−
| семинар
+
| Семинар
−
|  
+
| Задачи на графы, конденсация, 2-SAT
−
|
+
| [https://disk.yandex.ru/i/B7IW1Rr6wS_Byg Листок]
 
|
 
|
 
|-
 
|-
−
| лекция
+
| Лекция
−
| Стоимостной поток
+
| Доказательство log* n для СНМ. Введение в потоки.
 
|
 
|
 
|
 
|
−
|-
 
 
|}
 
|}
  
−
=== 2 модуль ===
+
=== 4 модуль ===
  
 
{| role="presentation" class="mw-collapsible wikitable"
 
{| role="presentation" class="mw-collapsible wikitable"
Строка 451: Строка 423:
 
! Видео
 
! Видео
 
|-
 
|-
−
| rowspan="2" | 26.10.2021
+
| rowspan="1" | 03.04.2023 (вт)
−
| Семинар
+
| colspan="4" | Занятий не было
−
| Основные определения, асимптотический рост функций, виды полиномиальности
+
−
| [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" | 28.10.2021
+
| rowspan="2" | 05.04.2023 (чт)
−
| Семинар  
+
| Семинар
−
| Задачи на теорию вероятностей, конечные вероятностные пространства, геометрическая вероятность
+
| colspan="3" | Семинара не было
−
| [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 Видео]
+
−
|-
+
−
| rowspan="2" | 02.11.2021
+
−
| Семинар
+
−
| Задачи на случайные величины и математическое ожидание
+
−
| [https://drive.google.com/file/d/1zhTrBeLJ3Mm6kfEumCHhRdEKBYJ0m2rR/view?usp=sharing Листочек]
+
−
| [https://www.youtube.com/watch?v=EGvKQ6f0FUg Видео]
+
−
|-
+
−
| Лекция
+
−
| RAM-модель
+
 
|
 
|
−
| [https://www.youtube.com/watch?v=IdPgYZOs54k Видео]
 
−
|-
 
−
| rowspan="2" | 09.11.2021
 
−
| Семинар
 
−
| Задачи на дисперсию, вероятности и матожидание, свойства случайных структур
 
−
| [https://drive.google.com/file/d/14Ea4delZWlsf1h6ChU6Go4639zWghEJE/view?usp=sharing Листочек]
 
−
| [https://www.youtube.com/watch?v=IvKivSR0zxc Видео]
 
−
|-
 
−
| Лекция
 
−
| Доказательство корректности работы алгоритмов, сортировки сравнениями, доказательство времени работы по индукции, рандомизированный поиск порядковой статистики
 
 
|
 
|
−
| [https://www.youtube.com/watch?v=beyP0TU7-94 Видео]
 
 
|-
 
|-
−
| rowspan="2" | 11.11.2021
+
| rowspan="2" | 11.04.2023 (чт)
−
| Семинар  
+
| Семинар
−
| Задачи на сортировку
+
| Потоки. Оценки Карзанова.
−
| [https://drive.google.com/file/d/1JOTWNMazfKzSnZeaX_sqCWa8g0iTRESy/view?usp=sharing Листочек]
+
−
| [https://www.youtube.com/watch?v=Y6a_ariyjXw Видео]
+
−
|-
+
−
| Лекция
+
−
| Детерменированный поиск порядковой статистики, бинарный и интерполяционный поиск, сортировки с учётом способа представления чисел, сортировка случайных данных
+
 
|
 
|
−
| [https://www.youtube.com/watch?v=92I4Ho0J6wU Видео]
 
−
|-
 
−
| rowspan="2" | 16.11.2021
 
−
| Семинар
 
−
| Задачи на cортировки и порядковые статистики
 
−
| [https://drive.google.com/file/d/1XLuFWAyNSl0NmWU7BkFHeJ0g0x31YjTo/view?usp=sharing Листочек]
 
−
| [https://www.youtube.com/watch?v=tKl-h6SgoZ8 Видео]
 
−
|-
 
−
| Лекция
 
−
| Нижняя оценка на сложность сортировки сравнениями, сортирующие сети
 
 
|
 
|
−
| [https://www.youtube.com/watch?v=OnbfE3MJpxQ Видео]
 
−
|-
 
−
| rowspan="2" | 18.11.2021
 
−
| Семинар
 
−
| Сортирующие сети и простые структуры данных
 
−
| [https://drive.google.com/file/d/1VETWg-EqrocnJsRHPc3PVbxXud1u4BA4/view?usp=sharing Листочек]
 
−
| [https://www.youtube.com/watch?v=-6urQgOZdqo Видео]
 
 
|-
 
|-
 
| Лекция
 
| Лекция
−
| Поставнока задач во внешней памяти, модель вычислений. Эффективная сортировка во внешней памяти
+
| Поиск потока минимальной стоимости за полиномиальное время
 
|
 
|
−
| [https://www.youtube.com/watch?v=r6fyYA71Cbc Видео]
 
−
|-
 
−
| rowspan="2" | 23.11.2021
 
−
| Семинар
 
−
| Задачи на алгоритмы во внешней памяти
 
−
| [https://drive.google.com/file/d/1SOKEL_koKErxna49-S8cqW2KWKabFNnN/view?usp=sharing Листочек]
 
 
|
 
|
−
|-
 
−
| Лекция
 
−
| Простые структуры данных. Двоичные и k-ичные кучи, биномиальные пирамиды
 
−
|
 
−
| [https://www.youtube.com/watch?v=CdYXvljG2LY Видео]
 
−
|-
 
−
| rowspan="2" | 25.11.2021
 
−
| Семинар
 
−
| Задачи на простые структуры данных
 
−
| [https://drive.google.com/file/d/1yda5xfWtq4I26TPNTPos_FcSqy2EYPGv/view?usp=sharing Листочек]
 
−
| [https://www.youtube.com/watch?v=IBuNu1gZCuw Видео]
 
−
|-
 
−
| Лекция
 
−
| Амортизационный анализ
 
−
|
 
−
| [https://www.youtube.com/watch?v=MyEYBIxhcuY Видео]
 
−
|-
 
−
| rowspan="2" | 30.11.2021
 
−
| Семинар
 
−
| Задачи на амортизационный анализ
 
−
| [https://drive.google.com/file/d/1WhSVbYpPkK-RlyWvzAbAcap0SnEysT-i/view?usp=sharing Листочек]
 
−
| [https://www.youtube.com/watch?v=YpfAUSFmirI Видео]
 
−
|-
 
−
| Лекция
 
−
| Фибоначчиевые кучи
 
−
|
 
−
| [https://www.youtube.com/watch?v=YpfAUSFmirI Видео]
 
−
|-
 
−
| 02.12.2021
 
−
| Бонусный семинар
 
−
| Реальная эффективность операций, написание быстрого кода, иерархия памяти
 
−
|
 
−
|
 
−
|-
 
−
| rowspan="2" | 07.12.2021
 
−
| Семинар
 
−
| Задачи на кучи
 
−
| [https://drive.google.com/file/d/1pa62hOJaswwj_qQLnmKZtwDRK7C6Ifv7/view?usp=sharing Листочек]
 
−
|
 
−
|-
 
−
| Лекция
 
−
| Хеширование. Постановка задачи, полиномиальное хеширование, лемма Шварца-Зиппеля
 
−
|
 
−
| [https://www.youtube.com/watch?v=HdTnD9yswcE Видео]
 
−
|-
 
−
| rowspan="2" | 09.12.2021
 
−
| Семинар
 
−
| Задачи на хеши
 
−
| [https://drive.google.com/file/d/1RSpq-Mk9Vhpbs9jXQ12bmtIGm_vqgrRM/view?usp=sharing Листочек]
 
−
| [https://www.youtube.com/watch?v=go0BH-005Gc Видео]
 
−
|-
 
−
| Лекция
 
−
| Хеш-таблицы с цепочками и открытой адресацией. Стратегии удаления элементов, сканирования и масштабирования таблиц. Фильтры Блума.
 
−
|
 
−
| [https://www.youtube.com/watch?v=xcJ9K_gE2rw Видео]
 
−
|-
 
−
| rowspan="2" | 14.12.2021
 
−
| Семинар
 
−
| Задачи на хеш-таблицы
 
−
| [https://drive.google.com/file/d/1UpQgg60pC94yI_96UkT_GF5wYPKW7JtL/view?usp=sharing Листочек]
 
−
|
 
−
|-
 
−
| Лекция
 
−
| Идеальное хеширование, статическое и динамическое. Алгоритм min-hash.
 
−
|
 
−
| [https://www.youtube.com/watch?v=f6fwf62cnNw Видео]
 
−
|-
 
−
| 16.12.2021
 
−
| Бонусный контест
 
−
|
 
−
|
 
−
|
 
−
|-
 
 
|}
 
|}
−
 
  
 
== Ссылки на материалы ==
 
== Ссылки на материалы ==
Строка 615: Строка 453:
  
 
== Преподаватели и ассистенты ==  
 
== Преподаватели и ассистенты ==  
 +
  
 
{| class="wikitable"
 
{| class="wikitable"
Строка 622: Строка 461:
 
| colspan="4" style="text-align: center;" | Преподаватели
 
| colspan="4" style="text-align: center;" | Преподаватели
 
|-
 
|-
−
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 211-1 || ||
+
| [https://www.hse.ru/org/persons/210175876 Иван Смирнов] || 221-1 || || [https://t.me/ifsmirnov @ifsmirnov]
 
|-
 
|-
−
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 211-2 || ||
+
| [https://www.hse.ru/org/persons/225527626 Филипп Грибов] || 221-2 || ||
 
|-
 
|-
−
| Дмитрий Ковальков || 213-1 || ||
+
| [https://www.hse.ru/org/persons/738677707 Иван Сафонов] || 222-1 || ||
 
|-
 
|-
−
| [https://www.hse.ru/org/persons/210175876 Иван Смирнов] || 213-2  || ||
+
| Михаил Анопренко || 222-2  || ||
 
|-
 
|-
−
| Глеб Третьяков || 215-1  || ||
+
| Сергей Нечаев || 225-1  || ||
 
|-
 
|-
−
| Максим Гайдук || 215-2  || ||
+
| Екатерина Фадеева || 225-2  || ||
 
|-
 
|-
 +
<!--
 
| colspan="4" style="text-align: center;" | Ассистенты
 
| colspan="4" style="text-align: center;" | Ассистенты
 
|-
 
|-
Строка 651: Строка 491:
 
|-
 
|-
 
| Кирилл Шубников || 215 || среда 21:00 (писать в лс) || [https://teleg.run/Radewoosh51 @Radewoosh51]
 
| Кирилл Шубников || 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»