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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Новая страница: «'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов] == Формула выставления итог…»)
 
(Формула выставления итоговой оценки)
 
(не показаны 63 промежуточные версии 7 участников)
Строка 1: Строка 1:
 
'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]
 
'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]
  
 +
'''[https://drive.google.com/file/d/1zjs_g2Db8lzkWdI256t9-rpuKApZCRNT/view?usp=sharing Программа курса]'''
  
 
+
{| class="wikitable"
 +
! colspan="4" | Важные ссылки
 +
|-
 +
| 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-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 Плейлист с записями лекций]
 +
|}
  
 
== Формула выставления итоговой оценки ==
 
== Формула выставления итоговой оценки ==
О<sub>итог</sub>  =  '''0.3''' &middot; О<sub>контесты</sub> + '''0.25''' &middot; O<sub>листки</sub> + '''0.15''' &middot;  O<sub>КР</sub> + '''0.3''' &middot; O<sub>экз</sub> + O<sub>бонус</sub>
+
'''Формула оценивания пока предварительная и может поменяться!'''
 +
 
 +
'''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>
 +
 
 +
'''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 модуль:''' О<sub>итог</sub>  =  '''0.53571428572''' &middot; О<sub>контесты</sub> + '''0.46428571428''' &middot; O<sub>листки</sub> + O<sub>бонус</sub>
  
 
<ul>
 
<ul>
Строка 30: Строка 44:
 
Виды контестов:
 
Виды контестов:
  
* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
+
* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 или 6 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
  
 
* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''.
 
* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''.
Строка 44: Строка 58:
 
Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов, на консультациях ассистентам.
 
Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов, на консультациях ассистентам.
  
<li> В течение каждого модуля предполагается по одной контрольной работе (так было до перехода в онлайн). За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться О<sub>КР</sub>. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
+
<li> В течение каждого очного модуля предполагается по одной контрольной работе (так было до перехода в онлайн). За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться О<sub>КР</sub>. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
  
 
<li> За [[Алгоритмы_и_структуры_данных_пилотный_поток_2020/2021#Экзамены | экзамен]]
 
<li> За [[Алгоритмы_и_структуры_данных_пилотный_поток_2020/2021#Экзамены | экзамен]]
Строка 55: Строка 69:
 
Итоговая оценка '''округляется арифметически''' (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).
 
Итоговая оценка '''округляется арифметически''' (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).
  
== Лекции и семинары ==
+
== <span id="homework"></span>Теоретическое домашнее задание ==
 +
=== <span id="assumptions"> Общие предположения, которыми можно пользоваться в задачах ===
 +
1. Если в задаче говорится про запросы, то по умолчанию online
  
 +
2. Если не оговорено иное, можно использовать столько же памяти, сколько времени
  
=== 2 модуль ===
+
3. Если не оговорено иное, то можно ожидаемое амортизированное время с хешами
{| role="presentation" class="mw-collapsible wikitable"
+
! Дата
+
! Семинар
+
! Листочек
+
! Лекция
+
|-
+
  
== Листки ==
+
=== Правила сдачи домашних заданий ===
== Короткие контесты ==
+
  
Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
+
1. Некоторые из задач домашнего задания можно сдать только письменно, остальные — как письменно, так и устно.
  
{| class="wikitable"  
+
2. Для каждого домашнего задания определены два дедлайна: мягкий дедлайн (обычно — через 2 недели) и жёсткий дедлайн (обычно — через 3 недели после выдачи задания).
 +
 
 +
3. Вплоть до мягкого дедлайна вы можете сдавать задачи устно любому из шести ассистентов. Для этого необходимо предаварительно [https://docs.google.com/spreadsheets/d/17JZuEJZPFaItPYl6m9ekjmI1jl_h7gWk9cXxDpnRb6Q/edit?usp=sharing записаться на консультацию].
 +
 
 +
4. Кроме этого, вплоть до мягкого дедлайна вы можете сдавать задачи письменно в [https://classroom.google.com/c/NDEyODEwMjUzMDIz?cjc=27fucrv Google.Classroom]. Проверкой письменных работ занимаются два ассистента, закреплённые за группой.
 +
 
 +
5. Пусть мягкий дедлайн был в день d, а вы сдали работу в день x. Тогда гарантируется, что не позднее, чем в день max(d + 4, x + 7) ваша работа будет проверена и по ней будут оставлены комментарии и пожелания об исправлении. После этого у вас есть возможность единожды исправить проблемы в работе (закрыть уже существующие дыры, но никак не писать новые задачи) и отправить исправленную работу до вплоть до жёсткого дедлайна. Не позднее, чем через 10 дней после жёсткого дедлайна мы гарантируем проверку исправленных работ.
 +
 
 +
6. Почти все (кроме, может быть, последних в модуле) домашние задания будут разобраны на семинарах. Разборы будут проводиться не раньше жёсткого дедлайна.
 +
 
 +
Написанное выше стоит понимать так: в лучшем сценарии вы решаете задачи и сдаёте какие-то из них (те, которые сложнее всего сдать письменно) устно, а все остальные — письменно. После мягкого дедлайна в течении пары дней ваш ассистент проверяет все работы и отправляет по ним фидбек, после чего у вас несколько дней на исправление недочётов. Мы будем пытаться проверять работы как можно раньше, но не гарантируем ничего лучше, чем описанное в п. 5.
 +
 
 +
===<span id="classroom"></span>Правила сдачи письменных работ===
 +
 
 +
1. Пожалуйста, убедитесь, что вашу работу можно идентифицировать (имя написано в файле, или ваш гугл-аккаунт подписан вашим именем).
 +
 
 +
2. При отправке убедитесь, что у вас появилась кнопка "отменить отправку" — это означает, что работа отправлена на проверку.
 +
 
 +
3. Домашние задания, сданные не в формате .pdf или набранные не с помощью системы вёрстки LaTeX не принимаются.
 +
 
 +
4. Нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки).
 +
 
 +
5. Решение должно представлять из себя свзяный цензурный текст без обсценной лексики, который может быть прочитан носителем русского языка, и являть собой решение задачи. Если текст не являет собой решение задачи, не надо прикладывать его к решению.
 +
 
 +
6. Списывание в работах повлечёт за собой обнуление баллов по работе.
 +
 
 +
7. Если вы не чувствуете себя уверено при работе с LaTeX, используйте шаблон https://www.overleaf.com/read/bpvmhqcvfgqq. В нём отражена основаня функциональность системы вёрстки. Вы можете склонировать проект и использовать его
 +
 
 +
 
 +
===Список заданий===
 +
 
 +
{| class="wikitable"
 +
! №
 +
! Тема
 +
! Листок
 +
! Мягкий дедлайн
 +
! Жесткий дедлайн
 
|-
 
|-
! style="text-align:center;"| № !! Дата !! Ссылка !! Дорешивать
+
| 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
 +
|-
 +
 
|}
 
|}
  
Строка 82: Строка 165:
  
 
{| class="wikitable"
 
{| class="wikitable"
 +
! №
 
! Дедлайн
 
! Дедлайн
 
! Темы
 
! Темы
 
! Ссылка
 
! Ссылка
 
|-
 
|-
| colspan="3" 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 Вход]
 +
|}
 +
 
 +
== Короткие контесты ==
 +
 
 +
Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
 +
 
 +
{| class="wikitable"
 +
|-
 +
! style="text-align:center;"| № !! Дата !! Ссылка !! Дорешивать
 +
|-
 +
| colspan="4" style="text-align: center; background-color:#dae8fc;" | 3 модуль
 +
|-
 +
| 1
 +
| 20.01.2022
 +
| [https://official.contest.yandex.ru/contest/34684/enter Вход]
 +
| До конца 3 модуля
 
|-
 
|-
 
|}
 
|}
  
 
== Экзамены ==
 
== Экзамены ==
 +
 +
== Лекции и семинары ==
 +
 +
=== 3 модуль ===
 +
 +
{| 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 модуль ===
 +
 +
{| role="presentation" class="mw-collapsible wikitable"
 +
! Дата
 +
! Тип
 +
! Тема
 +
! Материалы
 +
! Видео
 +
|-
 +
| rowspan="2" | 26.10.2021
 +
| Семинар
 +
| Основные определения, асимптотический рост функций, виды полиномиальности
 +
| [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
 +
| Семинар
 +
| Задачи на теорию вероятностей, конечные вероятностные пространства, геометрическая вероятность
 +
| [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
 +
| Семинар
 +
| Задачи на сортировку
 +
| [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
 +
| Бонусный контест
 +
|
 +
|
 +
|
 +
|-
 +
|}
  
  
Строка 106: Строка 622:
 
| colspan="4" style="text-align: center;" | Преподаватели
 
| colspan="4" style="text-align: center;" | Преподаватели
 
|-
 
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || ||  ||
+
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 211-1 ||  ||
 
|-
 
|-
| Максим Гайдук || || ||
+
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 211-2 || ||
 
|-
 
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || || ||
+
| Дмитрий Ковальков || 213-1 || ||
 
|-
 
|-
| [https://www.hse.ru/org/persons/210175876 Иван Смирнов] ||  || ||
+
| [https://www.hse.ru/org/persons/210175876 Иван Смирнов] || 213-2 || ||
 
|-
 
|-
| Дмитрий Ковальков || || ||
+
| Глеб Третьяков || 215-1  || ||
 
|-
 
|-
| Глеб Третьяков ||  || ||
+
| Максим Гайдук || 215-2 || ||
 
|-
 
|-
 
| colspan="4" style="text-align: center;" | Ассистенты
 
| colspan="4" style="text-align: center;" | Ассистенты
Строка 122: Строка 638:
 
| colspan="2" | Филипп Грибов ||  || [https://teleg.run/grphil @grphil]
 
| colspan="2" | Филипп Грибов ||  || [https://teleg.run/grphil @grphil]
 
|-
 
|-
| colspan="2" | Максим Деб Натх  || || [https://teleg.run/debnatkh @debnatkh]
+
| colspan="2" | Максим Деб Натх  || среда, 20:00 || [https://teleg.run/debnatkh @debnatkh]
 +
|-
 +
| Владимир Кауркин || 211 || вторник 20:00  || [https://teleg.run/LordVoldebug @LordVoldebug]
 
|-
 
|-
| colspan="2" | Максим Лутан || || [https://teleg.run/Maksim_Lutan @Maksim_Lutan]
+
| Игорь Маркелов || 211 || четверг 21:00 || [https://teleg.run/ElderlyPassionFruit @ElderlyPassionFruit]
 
|-
 
|-
| colspan="2" | Кирилл Шубников || || [https://teleg.run/Radewoosh51 @Radewoosh51]
+
| Максим Басалаев || 213 || четверг, 19:00 || [https://teleg.run/pojaleesh @pojaleesh]
 
|-
 
|-
| colspan="2" | Алеся Иванова || || [https://teleg.run/alesyaivanova @alesyaivanova]
+
| Алеся Иванова || 213 || среда 21:00 || [https://teleg.run/alesyaivanova @alesyaivanova]
 
|-
 
|-
| colspan="2" | Владимир Кауркин || || [https://teleg.run/LordVoldebug @LordVoldebug]
+
| Максим Лутан || 215 || суббота, 12:00 (можно договориться о другом дне недели в лс) || [https://teleg.run/Maksim_Lutan @Maksim_Lutan]
 
|-
 
|-
| colspan="2" | Игорь Маркелов || || [https://teleg.run/ElderlyPassionFruit @ElderlyPassionFruit]
+
| Кирилл Шубников || 215 || среда 21:00 (писать в лс) || [https://teleg.run/Radewoosh51 @Radewoosh51]
 
|}
 
|}

Текущая версия на 10:08, 16 июня 2022

Лектор: Глеб Олегович Евстропов

Программа курса

Важные ссылки
Google.Classroom
Текущая успеваемость
html-версия
Google.Classroom
Google.Classroom
инвайт: 27fucrv
Google.Classroom
Запись на консультации
Youtube-logo.png
Плейлист с записями лекций

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

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

4 модуль: Оитог = 0.3 · Оконтесты (4 модуль) + 0.25 · Oлистки (4 модуль) + 0.15 · Oконтрольная + 0.3 · Oэкзамен + Oбонус

3 модуль: Оитог = 0.3 · Оконтесты (2 + 3 модуль) + 0.25 · Oлистки (2 + 3 модуль) + 0.15 · Oконтрольная + 0.3 · Oэкзамен + Oбонус

2 модуль: Оитог = 0.53571428572 · Оконтесты + 0.46428571428 · Oлистки + Oбонус

  • Оконтесты вычисляется по формуле:
    Оконтесты = 10 · ( КК + ДК + БЗ ), где:
    ОЗ - поправка ОЗ
    • КК — баллы за короткие контесты
    • ДК — баллы за длинные контесты (исключая бонусные задачи)
    • БЗ — баллы за бонусные задачи в длинных контестах
    • ОЗ — общее число задач во всех контестах (исключая бонусные задачи)
    • Поправка по умолчанию равна нулю и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

    Виды контестов:

    • Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 или 6 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
    • Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные.
  • Олистки вычисляется по формуле:
    Олистки = 10 · количество решённых задач
    количество обязательных задач - поправка

    Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов, на консультациях ассистентам.

  • В течение каждого очного модуля предполагается по одной контрольной работе (так было до перехода в онлайн). За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться ОКР. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
  • За экзамен студент получает оценку от 0 до 10, эта оценка будет являться Оэкз.
  • Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

Итоговая оценка округляется арифметически (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).

Теоретическое домашнее задание

Общие предположения, которыми можно пользоваться в задачах

1. Если в задаче говорится про запросы, то по умолчанию online

2. Если не оговорено иное, можно использовать столько же памяти, сколько времени

3. Если не оговорено иное, то можно ожидаемое амортизированное время с хешами

Правила сдачи домашних заданий

1. Некоторые из задач домашнего задания можно сдать только письменно, остальные — как письменно, так и устно.

2. Для каждого домашнего задания определены два дедлайна: мягкий дедлайн (обычно — через 2 недели) и жёсткий дедлайн (обычно — через 3 недели после выдачи задания).

3. Вплоть до мягкого дедлайна вы можете сдавать задачи устно любому из шести ассистентов. Для этого необходимо предаварительно записаться на консультацию.

4. Кроме этого, вплоть до мягкого дедлайна вы можете сдавать задачи письменно в Google.Classroom. Проверкой письменных работ занимаются два ассистента, закреплённые за группой.

5. Пусть мягкий дедлайн был в день d, а вы сдали работу в день x. Тогда гарантируется, что не позднее, чем в день max(d + 4, x + 7) ваша работа будет проверена и по ней будут оставлены комментарии и пожелания об исправлении. После этого у вас есть возможность единожды исправить проблемы в работе (закрыть уже существующие дыры, но никак не писать новые задачи) и отправить исправленную работу до вплоть до жёсткого дедлайна. Не позднее, чем через 10 дней после жёсткого дедлайна мы гарантируем проверку исправленных работ.

6. Почти все (кроме, может быть, последних в модуле) домашние задания будут разобраны на семинарах. Разборы будут проводиться не раньше жёсткого дедлайна.

Написанное выше стоит понимать так: в лучшем сценарии вы решаете задачи и сдаёте какие-то из них (те, которые сложнее всего сдать письменно) устно, а все остальные — письменно. После мягкого дедлайна в течении пары дней ваш ассистент проверяет все работы и отправляет по ним фидбек, после чего у вас несколько дней на исправление недочётов. Мы будем пытаться проверять работы как можно раньше, но не гарантируем ничего лучше, чем описанное в п. 5.

Правила сдачи письменных работ

1. Пожалуйста, убедитесь, что вашу работу можно идентифицировать (имя написано в файле, или ваш гугл-аккаунт подписан вашим именем).

2. При отправке убедитесь, что у вас появилась кнопка "отменить отправку" — это означает, что работа отправлена на проверку.

3. Домашние задания, сданные не в формате .pdf или набранные не с помощью системы вёрстки LaTeX не принимаются.

4. Нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки).

5. Решение должно представлять из себя свзяный цензурный текст без обсценной лексики, который может быть прочитан носителем русского языка, и являть собой решение задачи. Если текст не являет собой решение задачи, не надо прикладывать его к решению.

6. Списывание в работах повлечёт за собой обнуление баллов по работе.

7. Если вы не чувствуете себя уверено при работе с LaTeX, используйте шаблон https://www.overleaf.com/read/bpvmhqcvfgqq. В нём отражена основаня функциональность системы вёрстки. Вы можете склонировать проект и использовать его


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

Тема Листок Мягкий дедлайн Жесткий дедлайн
2 модуль
1 Вероятности и математическое ожидание Листок 14.11.2021 22.11.2021
2 Сортировки Листок 24.11.2021 01.12.2021
3 Простые структуры данных и амортизационный анализ Листок 06.12.2021 13.12.2021
4 Кучи, хеши Листок 17.12.2021 25.12.2021
3 модуль
5 Структуры данных Листок 31.01.2022 07.02.2022
6 Структуры данных 2 Листок 15.02.2022 22.02.2022

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

Дедлайн Темы Ссылка
2 модуль
1 01.12.2021 Вероятности, упорядоченные данные, простые структуры Вход
2 09.12.2021 Вероятности, сортировки, простые структуры, кучи Вход
3 18.12.2021 Хеши Вход
3 модуль
4 05.02.2022 Деревья поиска, структуры данных, задача на ревью Вход
5 19.02.2022 Персистентность, динамическое программирование, переборы Вход
6 12.03.2022 Графы, снм Вход
4 модуль
7 7.05.2022 Паросочетания, потоки Вход
8 4.06.2022 Строки, формальные языки Вход

Короткие контесты

Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

Дата Ссылка Дорешивать
3 модуль
1 20.01.2022 Вход До конца 3 модуля

Экзамены

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

3 модуль

2 модуль


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

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

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

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

Преподаватель Подгруппа Присутственные часы Контакты
Преподаватели
Глеб Евстропов 211-1
Станислав Артюхин 211-2
Дмитрий Ковальков 213-1
Иван Смирнов 213-2
Глеб Третьяков 215-1
Максим Гайдук 215-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