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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 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:Youtube-logo.png|x100px | link=https://www.youtube.com/playlist?list=PLEwK9wdS5g0p4lTp0x7xgH2CICLvM4rTy]]<br>[https://www.youtube.com/playlist?list=PLEwK9wdS5g0p4lTp0x7xgH2CICLvM4rTy Плейлист с записями лекций]
+
 
|}
 
|}
  
Строка 15: Строка 12:
 
'''Формула оценивания пока предварительная и может поменяться!'''
 
'''Формула оценивания пока предварительная и может поменяться!'''
  
−
'''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 модуль:''' О<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>
+
После 3-го, 4-го и 5-го модулей будут экзамены.
  
−
'''2 модуль:''' О<sub>итог</sub>  =  '''0.53571428572''' &middot; О<sub>контесты</sub> + '''0.46428571428''' &middot; O<sub>листки</sub> + O<sub>бонус</sub>
+
Предварительные правила выставления оценок за модули:
 +
 
 +
'''2 модуль:''' О<sub>итог</sub>  =  '''0.4286''' &middot; О<sub>контесты</sub> + '''0.3571''' &middot; O<sub>листки</sub> + '''0.2143''' &middot; О<sub>КР</sub> + O<sub>бонус</sub>
 +
 
 +
'''3-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>
  
 
<ul>
 
<ul>
 +
<!--
 
<li>
 
<li>
 
О<sub>контесты</sub> вычисляется по формуле:
 
О<sub>контесты</sub> вычисляется по формуле:
Строка 47: Строка 49:
  
 
* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''.
 
* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''.
 +
 +
-->
  
 
<li> О<sub>листки</sub> вычисляется по формуле:
 
<li> О<sub>листки</sub> вычисляется по формуле:
Строка 56: Строка 60:
 
|}
 
|}
  
−
Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов, на консультациях ассистентам.
+
Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов на консультациях ассистентам.
  
−
<li> В течение каждого очного модуля предполагается по одной контрольной работе (так было до перехода в онлайн). За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться О<sub>КР</sub>. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
+
<li> В течение каждого очного модуля предполагается по одной контрольной работе. За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться О<sub>КР</sub>. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
  
 
<li> За [[Алгоритмы_и_структуры_данных_пилотный_поток_2020/2021#Экзамены | экзамен]]
 
<li> За [[Алгоритмы_и_структуры_данных_пилотный_поток_2020/2021#Экзамены | экзамен]]
Строка 77: Строка 81:
 
3. Если не оговорено иное, то можно ожидаемое амортизированное время с хешами
 
3. Если не оговорено иное, то можно ожидаемое амортизированное время с хешами
  
 +
<!--
 
=== Правила сдачи домашних заданий ===
 
=== Правила сдачи домашних заданий ===
  
Строка 92: Строка 97:
  
 
Написанное выше стоит понимать так: в лучшем сценарии вы решаете задачи и сдаёте какие-то из них (те, которые сложнее всего сдать письменно) устно, а все остальные — письменно. После мягкого дедлайна в течении пары дней ваш ассистент проверяет все работы и отправляет по ним фидбек, после чего у вас несколько дней на исправление недочётов. Мы будем пытаться проверять работы как можно раньше, но не гарантируем ничего лучше, чем описанное в п. 5.
 
Написанное выше стоит понимать так: в лучшем сценарии вы решаете задачи и сдаёте какие-то из них (те, которые сложнее всего сдать письменно) устно, а все остальные — письменно. После мягкого дедлайна в течении пары дней ваш ассистент проверяет все работы и отправляет по ним фидбек, после чего у вас несколько дней на исправление недочётов. Мы будем пытаться проверять работы как можно раньше, но не гарантируем ничего лучше, чем описанное в п. 5.
 +
-->
  
 
===<span id="classroom"></span>Правила сдачи письменных работ===
 
===<span id="classroom"></span>Правила сдачи письменных работ===
Строка 107: Строка 113:
 
6. Списывание в работах повлечёт за собой обнуление баллов по работе.
 
6. Списывание в работах повлечёт за собой обнуление баллов по работе.
  
−
7. Если вы не чувствуете себя уверено при работе с LaTeX, используйте шаблон https://www.overleaf.com/read/bpvmhqcvfgqq. В нём отражена основаня функциональность системы вёрстки. Вы можете склонировать проект и использовать его
+
7. Если вы не чувствуете себя уверено при работе с LaTeX, используйте шаблон https://www.overleaf.com/read/bpvmhqcvfgqq. В нём отражена основная функциональность системы вёрстки. Вы можете склонировать проект и использовать его.
  
  
Строка 116: Строка 122:
 
! Тема
 
! Тема
 
! Листок
 
! Листок
−
! Мягкий дедлайн
+
! Дедлайн
−
! Жесткий дедлайн
+
 
|-
 
|-
−
| 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
 
−
|-
 
−
 
 
|}
 
|}
  
Строка 172: Строка 138:
 
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 2 модуль
 
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 2 модуль
 
|-
 
|-
−
| 1
 
−
| 01.12.2021
 
−
| Вероятности, упорядоченные данные, простые структуры
 
−
| [https://official.contest.yandex.ru/contest/31144 Вход]
 
−
|-
 
−
| 2
 
−
| 09.12.2021
 
−
| Вероятности, сортировки, простые структуры, кучи
 
−
| [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: Строка 157:
 
|-
 
|-
 
|}
 
|}
 +
-->
  
 
== Экзамены ==
 
== Экзамены ==
  
 
== Лекции и семинары ==
 
== Лекции и семинары ==
−
 
−
=== 3 модуль ===
 
−
 
−
{| role="presentation" class="mw-collapsible wikitable"
 
−
! Дата
 
−
! Тип
 
−
! Тема
 
−
! Материалы
 
−
! Видео
 
−
|-
 
−
| rowspan="2" | 11.01.2022
 
−
| Семинар
 
−
| Деревья поиска
 
−
| [https://drive.google.com/file/d/1p09Bz3aMYX_HZbQdDmzk2t87HtkWmIPD/view?usp=sharing Листочек]
 
−
|
 
−
|-
 
−
| Лекция
 
−
| Первая очная лекция! Бинарные деревья поиска, 2-3 дерево, декартово дерево
 
−
|
 
−
| [https://www.youtube.com/watch?v=Wa2II3ZDeM0 Видео]
 
−
|-
 
−
| rowspan="2" | 13.01.2022
 
−
| Семинар
 
−
| Деревья Тарьяна-Слейтера (Splay дерево)
 
−
| [https://drive.google.com/file/d/16MAIZAm1bwOg6nn0GkRbX_fAK-pxK20R/view?usp=sharing Листочек]
 
−
| [https://www.youtube.com/watch?v=QQnK9sdPzso Видео]
 
−
|-
 
−
| Лекция
 
−
| Структуры данных для запросов на отрезках
 
−
|
 
−
| [https://www.youtube.com/watch?v=4TTYrCTV4h8 Видео]
 
−
|-
 
−
| rowspan="2" | 18.01.2022
 
−
| Семинар
 
−
| Задачи на деревья поиска и запросы на отрезках
 
−
| [https://drive.google.com/file/d/1FpjZGqaJnUnapRR7hI9kqHLes544FI3e/view?usp=sharing Листочек]
 
−
| [https://www.youtube.com/watch?v=HAMIhpnmQf8 Видео]
 
−
|-
 
−
| Лекция
 
−
| Корневые деревья, LCA, LA, метод четырёх русских
 
−
|
 
−
| [https://www.youtube.com/watch?v=vkBtUfJFOtQ Видео]
 
−
|-
 
−
| 20.01.2022
 
−
| Короткий контест
 
−
| Короткий контест 1
 
−
| [https://official.contest.yandex.ru/contest/34684/enter Вход]
 
−
|
 
−
|-
 
−
| rowspan="2" | 25.01.2022
 
−
| Семинар
 
−
| Задачи на запросы на отрезках
 
−
| [https://drive.google.com/file/d/19JkY2MhvDtwiNzCZ223ZnbuzWqhT9Mvj/view?usp=sharing Листочек]
 
−
| [https://www.youtube.com/watch?v=I3cthrjK7LY Видео]
 
−
|-
 
−
| Лекция
 
−
| Персистентные структуры данных
 
−
|
 
−
| [https://www.youtube.com/watch?v=VG1y_xJUOxc Видео]
 
−
|-
 
−
| rowspan="2" | 27.01.2022
 
−
| Семинар
 
−
| Запросы на деревьях и персистентность
 
−
| [https://drive.google.com/file/d/1V4sUB-iXgjl1W-DBQIMS_PxBs9zz4gSl/view?usp=sharing Листочек]
 
−
|
 
−
|-
 
−
| Лекция
 
−
| Частично персистентное бинарное дерево поиска без штрафа по времени и памяти
 
−
|
 
−
|
 
−
|-
 
−
| rowspan="2" | 01.03.2022
 
−
| семинар
 
−
| Ещё задачи на структуры и персистентность
 
−
|
 
−
|
 
−
|-
 
−
| лекция
 
−
| Метод перебора в задачах оптимизации и генерации комбинаторных объектов. Динамическое программирование, meet-in-the-middle
 
−
|
 
−
|
 
−
|-
 
−
| rowspan="2" | 03.03.2022
 
−
| семинар
 
−
| Разбор ДЗ + задачи на ДП
 
−
|
 
−
|
 
−
|-
 
−
| лекция
 
−
| Эвристические методы оптимизации перебора
 
−
|
 
−
|
 
−
|-
 
−
| rowspan="2" | 08.03.2022
 
−
| семинар
 
−
| Разбор дз на структуры данных + задачи на ДП и перебор
 
−
|
 
−
|
 
−
|-
 
−
| лекция
 
−
| Асимптотические оптимизации перебора, перебор в играх с нулевой суммой, альфа-бета отсечение
 
−
|
 
−
|
 
−
|-
 
−
| rowspan="2" | 15.03.2022
 
−
| семинар
 
−
| Разбор КР + разбор ДЗ
 
−
|
 
−
|
 
−
|-
 
−
| лекция
 
−
| Обходы графов в глубину и ширину, их основные применения, компоненты связности, мосты и точки сочленения, 2-SAT
 
−
|
 
−
|
 
−
|-
 
−
| rowspan="2" | 17.03.2022
 
−
| семинар
 
−
|
 
−
|
 
−
|
 
−
|-
 
−
| лекция
 
−
| Кратчайшие пути во взвешенных графах, потенциалы Джонсона, эвристика A*
 
−
|
 
−
|
 
−
|-
 
−
| rowspan="2" | 22.03.2022
 
−
| семинар
 
−
|
 
−
|
 
−
|
 
−
|-
 
−
| лекция
 
−
| Задача о минимальном остове, алгоритмы нахождения минимального остова и критерии оптимальности
 
−
|
 
−
|
 
−
|-
 
−
| rowspan="2" | 01.03.2022
 
−
| семинар
 
−
|
 
−
|
 
−
|
 
−
|-
 
−
| лекция
 
−
| Графовые алгоритмы в модели со внешней памятью. Задача list ranking
 
−
|
 
−
|
 
−
|-
 
−
| rowspan="2" | 03.03.2022
 
−
| семинар
 
−
|
 
−
|
 
−
|
 
−
|-
 
−
| лекция
 
−
| Паросочетания в двудольных графах
 
−
|
 
−
|
 
−
|-
 
−
| rowspan="2" | 10.03.2022
 
−
| семинар
 
−
|
 
−
|
 
−
|
 
−
|-
 
−
| лекция
 
−
| Задача о максимальном потоке, теорема о декомпозиции потока, теорема Форда-Фалкерсона
 
−
|
 
−
|
 
−
|-
 
−
| rowspan="2" | 15.03.2022
 
−
| семинар
 
−
|
 
−
|
 
−
|
 
−
|-
 
−
| лекция
 
−
| Полиномиальные алгоритмы решения задачи о максимальном потоке
 
−
|
 
−
|
 
−
|-
 
−
| rowspan="2" | 17.03.2022
 
−
| семинар
 
−
|
 
−
|
 
−
|
 
−
|-
 
−
| лекция
 
−
|
 
−
|
 
−
|
 
−
|-
 
−
| rowspan="2" | 22.03.2022
 
−
| семинар
 
−
|
 
−
|
 
−
|
 
−
|-
 
−
| лекция
 
−
| Стоимостной поток
 
−
|
 
−
|
 
−
|-
 
−
|}
 
  
 
=== 2 модуль ===
 
=== 2 модуль ===
Строка 451: Строка 172:
 
! Видео
 
! Видео
 
|-
 
|-
−
| rowspan="2" | 26.10.2021
+
| rowspan="2" | 01.11.2022
 
| Семинар  
 
| Семинар  
 
| Основные определения, асимптотический рост функций, виды полиномиальности
 
| Основные определения, асимптотический рост функций, виды полиномиальности
−
| [https://drive.google.com/file/d/1ZoUnd7okePTlQxdBZwtB2jRp2QgQrAS7/view?usp=sharing Листочек]
+
| <!--[https://drive.google.com/file/d/1ZoUnd7okePTlQxdBZwtB2jRp2QgQrAS7/view?usp=sharing Листочек]-->
−
| [https://www.youtube.com/watch?v=XdJ4ttt2hc0 Видео]
+
| <!--[https://www.youtube.com/watch?v=XdJ4ttt2hc0 Видео]-->
 
|-  
 
|-  
 
| Лекция
 
| Лекция
 
| Знакомство, обзор программы курса, введние в теорию вероятностей  
 
| Знакомство, обзор программы курса, введние в теорию вероятностей  
 
|
 
|
−
| [https://www.youtube.com/watch?v=WYrNMqsDScA Видео]
+
| <!--[https://www.youtube.com/watch?v=WYrNMqsDScA Видео]-->
 
|-
 
|-
−
| rowspan="2" | 28.10.2021
+
| rowspan="2" | 03.11.2022
 
| Семинар  
 
| Семинар  
 
| Задачи на теорию вероятностей, конечные вероятностные пространства, геометрическая вероятность
 
| Задачи на теорию вероятностей, конечные вероятностные пространства, геометрическая вероятность
−
| [https://drive.google.com/file/d/1FN7SzZHSwhKVtNKA6EmHEproKzGXlPCZ/view?usp=sharing Листочек]
+
| <!--[https://drive.google.com/file/d/1FN7SzZHSwhKVtNKA6EmHEproKzGXlPCZ/view?usp=sharing Листочек]-->
−
| [https://www.youtube.com/watch?v=iAmC9FS643k Видео]
+
| <!--[https://www.youtube.com/watch?v=iAmC9FS643k Видео]-->
 
|-
 
|-
 
| Лекция
 
| Лекция
 
| Случайные величины. Математическое ожидание, дисперсия, линейность, индикаторные величины.
 
| Случайные величины. Математическое ожидание, дисперсия, линейность, индикаторные величины.
−
| [https://drive.google.com/file/d/1iY5YzzpspQqOyuJ_jdAPZHbcSXHDuRQF/view?usp=sharing Материалы]
+
| <!--[https://drive.google.com/file/d/1iY5YzzpspQqOyuJ_jdAPZHbcSXHDuRQF/view?usp=sharing Материалы]-->
−
| [https://www.youtube.com/watch?v=irG9tjy2GgM Видео]
+
| <!--[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
+
−
| Семинар
+
−
| Задачи на сортировку
+
−
| [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: Строка 202:
  
 
== Преподаватели и ассистенты ==  
 
== Преподаватели и ассистенты ==  
 +
  
 
{| class="wikitable"
 
{| class="wikitable"
Строка 622: Строка 210:
 
| 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://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;" | Ассистенты

Версия 22:00, 4 ноября 2022

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


Важные ссылки
Google.Classroom
Текущая успеваемость

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

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

Курс длится 4 модуля (со 2-го по 5-й) и предполагает две итоговые оценки: на первом курсе (2-4 модули) и на втором (5 модуль). Оценки за каждый модуль ставятся независимо. Итоговая оценка за первый курс составляется из оценок за 2-4 модули (точные правила будут сообщены позднее). Оценка за 5-й модуль является итоговой оценкой за второй курс.

После 3-го, 4-го и 5-го модулей будут экзамены.

Предварительные правила выставления оценок за модули:

2 модуль: Оитог = 0.4286 · Оконтесты + 0.3571 · Oлистки + 0.2143 · ОКР + Oбонус

3-4 модуль: Оитог = 0.3 · Оконтесты + 0.25 · Oлистки + 0.15 · ОКР + 0.3 · Оэкзамен + Oбонус

  • Олистки вычисляется по формуле:
    Олистки = 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 модуль


Экзамены

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

2 модуль


Ссылки на материалы

Основные источники:

  1. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ, [2013, 3 издание]
  2. neerc.ifmo.ru

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

Преподаватель Подгруппа Присутственные часы Контакты
Преподаватели
Иван Смирнов 221-1
Филипп Грибов 221-2
Иван Сафонов 222-1
Михаил Анопренко 222-2
Сергей Нечаев 225-1
Екатерина Фадеева 225-2
Ассистенты
Филипп Грибов @grphil
Максим Деб Натх среда, 20:00 @debnatkh
Владимир Кауркин 211 вторник 20:00 @LordVoldebug
Игорь Маркелов 211 четверг 21:00 @ElderlyPassionFruit
Максим Басалаев 213 четверг, 19:00 @pojaleesh
Алеся Иванова 213 среда 21:00 @alesyaivanova
Максим Лутан 215 суббота, 12:00 (можно договориться о другом дне недели в лс) @Maksim_Lutan
Кирилл Шубников 215 среда 21:00 (писать в лс) @Radewoosh51
Источник — «http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных_пилотный_поток_2022/2023&oldid=73778»