Алгоритмы и структуры данных пилотный поток 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;" | Ассистенты

Версия от 19: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
Источник — https://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных_пилотный_поток_2022/2023&oldid=73778