Алгоритмы и структуры данных 1 2020/2021 Семинары 209-1 — различия между версиями
(→Листки с задачами в 4 модуле) |
|||
(не показаны 42 промежуточные версии этого же участника) | |||
Строка 2: | Строка 2: | ||
'''Занятия:''' | '''Занятия:''' | ||
− | + | Четверг 11:10 - 14:00, аудитория R608 | |
− | Четверг | + | |
'''Ассистент:''' Миша Виноградов | '''Ассистент:''' Миша Виноградов | ||
− | '''Часы приема задач:''' | + | '''Часы приема задач:''' |
− | + | ||
− | + | ||
− | Таблица с | + | Четверг 18:00 |
+ | |||
+ | Суббота 16:00 | ||
+ | |||
+ | |||
+ | [https://docs.google.com/spreadsheets/d/1w0pzjLlUHbb4ouZBjpWZ_3WLfPIvB6cvQaYRKi41UTs/edit#gid=0 Таблица с оценками] | ||
[https://forms.gle/7GCKcbxspb3n7dT28 Форма обратной связи] | [https://forms.gle/7GCKcbxspb3n7dT28 Форма обратной связи] | ||
− | + | [http://wiki.cs.hse.ru/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_1_2020/2021 Общая страница курса — 2 модуль] | |
+ | [http://wiki.cs.hse.ru/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_1_2020/2021_(4_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D1%8C) Общая страница курса — 4 модуль] | ||
+ | |||
+ | |||
+ | == Листки с задачами в 4 модуле == | ||
+ | <br /> | ||
+ | |||
+ | [https://www.dropbox.com/s/hy0q0fxtw4i4eib/mod4_week_1.pdf?dl=0 1 неделя]. Поиск в глубину. Связность, компоненты связности, циклы, двудольность. | ||
+ | |||
+ | ''Оцениваемые задачи:'' 5, 6. | ||
+ | |||
+ | ''Дедлайн:'' четверг 22 апреля в 23:59. | ||
+ | |||
+ | |||
+ | |||
+ | [https://www.dropbox.com/s/qjwk2e4ax29xj9j/mod4_week_2.pdf?dl=0 2 неделя]. Поиск в глубину продолжение: топсорт, мосты, точки сочленения. Поиск в ширину. | ||
+ | |||
+ | ''Оцениваемые задачи:'' 4, 6, 7. | ||
+ | |||
+ | ''Дедлайн:'' четверг 29 апреля в 23:59. | ||
+ | |||
+ | |||
+ | [https://www.dropbox.com/s/mbfc0dofo23diwp/mod4_week_3.pdf?dl=0 3 неделя]. Дейкстра. Форд-Беллман, Флойд. | ||
+ | |||
+ | ''Оцениваемые задачи:'' 5, 8. | ||
+ | |||
+ | ''Дедлайн:'' четверг 29 апреля в 23:59. | ||
+ | |||
+ | |||
+ | [https://www.dropbox.com/s/epqiair52gbl1k3/mod4_week_4.pdf?dl=0 4 неделя]. Остовные деревья, DSU. Сбалансированные деревья поиска. | ||
+ | |||
+ | ''Оцениваемые задачи:'' нет. | ||
+ | |||
+ | ''Дедлайн:'' четверг 13 мая в 23:59. | ||
+ | |||
+ | |||
+ | [https://docs.google.com/document/d/1_tU03ZBjmkko456hHvn7zbTeG2M1zIOsAIqEy6zjSMc/ 5 неделя]. Декартово дерево, LCA (наименьший общий предок). | ||
+ | |||
+ | ''Оцениваемые задачи:'' 1, 7. | ||
+ | |||
+ | ''Дедлайн:'' четверг 10 июня в 23:59. | ||
+ | |||
+ | |||
+ | 6 неделя. - | ||
+ | |||
+ | |||
+ | [https://www.dropbox.com/s/7jxy1x019rqzdf2/mod4_week_7.pdf?dl=0 7 неделя]. Алгоритмы теории чисел. Комбинаторные объекты. | ||
+ | |||
+ | ''Оцениваемые задачи:'' покажите, что алгоритм Евклида работает за O(log(min(a, b))). | ||
+ | |||
+ | ''Дедлайн:'' четверг 10 июня в 23:59. | ||
+ | |||
+ | ==Оценка за семинары в 4 модуле== | ||
+ | <br /> | ||
+ | |||
+ | (UPD: для удобства прежние баллы за тесты и оцениваемые задачи были домножены на 4 — сейчас это 4 и 8 баллов соответственно) | ||
+ | |||
+ | Баллы за семинар можно получить двумя способами: | ||
+ | |||
+ | # Устная сдача оцениваемых задач ассистенту. Каждую неделю такие задачи будут выдаваться из семинарского листка. По умолчанию такие задачи стоят 8 баллов, если другое не оговорено отдельно. Дедлайн по ним до 23:59 четверга следующего за тем, когда были выданы задачи.<br /><br /> | ||
+ | # Короткие тесты на семинарах. Это несколько несложных вопросов. Не на идею, а на какое-то базовое понимание материала. Полностью правильно написанный тест стоит 4 балла. | ||
+ | |||
+ | '''O {семинары} = min(10, <баллы в пунктах 1 и 2> / (0.6 * <максимальное число баллов в пункте 1>)''' | ||
+ | |||
+ | То есть на 10 нужно решить 60% оцениваемых задач или меньше, если есть баллы за тесты. | ||
+ | |||
+ | |||
+ | ==Листки с задачами во 2 модуле== | ||
+ | <br /> | ||
[https://www.dropbox.com/s/vbytazeuajb9p0s/2d_module_seminars_week1.pdf?dl=0 1 неделя]. Алгоритм. Сложность алгоритма. Анализ сложности. Асимптотические оценки. Сортировка слиянием. | [https://www.dropbox.com/s/vbytazeuajb9p0s/2d_module_seminars_week1.pdf?dl=0 1 неделя]. Алгоритм. Сложность алгоритма. Анализ сложности. Асимптотические оценки. Сортировка слиянием. | ||
− | Оцениваемые задачи: Задача 1 (пункты 4, 5, 6), Задача 2, Задача 3 (пункт 2) | + | ''Оцениваемые задачи:'' Задача 1 (пункты 4, 5, 6), Задача 2, Задача 3 (пункт 2), Задача 11. |
+ | |||
+ | ''Дедлайн:'' вс 8 ноября 23:59. | ||
+ | |||
+ | |||
+ | [https://www.dropbox.com/s/jx050p8xg1m9q01/week2_module2_seminars.pdf?dl=0 Неделя 2]. Амортизационный анализ, квадратичные сортировки, двоичная куча, быстрая сортировка, порядковые | ||
+ | статистики. | ||
+ | |||
+ | ''Оцениваемые задачи:'' 1 (см. комментарий в чате), 4 (сложность операций — логарифм), 9, 13с, 14. | ||
+ | |||
+ | ''Дедлайн:'' пн 16 ноября 23:59. | ||
+ | |||
+ | |||
+ | [https://www.dropbox.com/s/x11ta2cg8awd1t3/week3_module2_seminars.pdf?dl=0 Неделя 3]. Сортировка подсчётом. Цифровая сортировка. | ||
+ | Двоичный поиск. | ||
+ | |||
+ | ''Оцениваемые задачи:'' '''2''', '''4''' (все числа от 0 до n, время работы линейное. в алгоритме верните ответ по модулю 10^10 — это нужно, чтобы не думать про длинную арифметику; если этот комментарий вас смущает, то игнорируйте его во время решения и обсудите с примнимающим), '''11''' (предподсчёт за линейное время), '''13'''. | ||
+ | |||
+ | ''Дедлайн:'' пн 23 ноября 23:59. | ||
+ | |||
+ | |||
+ | [https://www.dropbox.com/s/e21p9qzb46f8my3/week4_module2_seminars.pdf?dl=0 Неделя 4]. Биномиальные кучи, фиббоначиевы кучи. | ||
+ | |||
+ | ''Оцениваемые задачи:'' 3, 8, 9, 10. | ||
+ | |||
+ | ''Дедлайн:'' пн 30 ноября 23:59. | ||
+ | |||
+ | |||
+ | [https://www.dropbox.com/s/wbwe57cwuv38ire/week5_module2_seminars.pdf?dl=0 Неделя 5]. Динамическое программирование. | ||
+ | |||
+ | ''Оцениваемые задачи:'' 2, 4, 7, 10, 13. | ||
+ | |||
+ | ''Дедлайн:'' пн 7 декабря 23:59. | ||
+ | |||
+ | |||
+ | [https://www.dropbox.com/s/yoqn88662pnsweg/week6_module2_seminars.pdf?dl=0 Неделя 6] | ||
+ | |||
+ | ''Оцениваемые задачи:'' Нет. | ||
+ | |||
+ | |||
+ | [https://www.dropbox.com/s/cb676sfb8rxi4uw/week7_module2_seminars.pdf?dl=0 Неделя 7] | ||
+ | |||
+ | ''Оцениваемые задачи:'' 7, 11, 12. | ||
+ | |||
+ | ''Дедлайн:'' пн 21 декабря 23:59. | ||
+ | |||
+ | |||
+ | [https://www.dropbox.com/s/soroo2tcfmiqc0w/week8_module2_seminars.pdf?dl=0 Неделя 8]. Дерево отрезков. | ||
+ | |||
+ | ''Оцениваемые задачи:'' 1. 4 — бонусная. За решение бонусной задачи дается +2 балла к сумме баллов за ДЗ, но в знаменателе (числе обязательных задач) она учитываться не будет. | ||
+ | |||
+ | ''Дедлайн:'' пн 21 декабря 23:59. | ||
+ | |||
==Оценка за семинары во 2 модуле== | ==Оценка за семинары во 2 модуле== | ||
+ | <br /> | ||
'''Внимание:''' в течение первых двух недель правила выставления семинарской оценки могут незначительно измениться. | '''Внимание:''' в течение первых двух недель правила выставления семинарской оценки могут незначительно измениться. | ||
Строка 30: | Строка 153: | ||
Каждую неделю будет выдаваться листок с задачами. Часть из них будут разбираться на семинаре, несколько задач из каждого листка будут выделены для индвидуальной устной сдачи — назовем их оцениваемыми задачами. Сдавать задачи можно только устно семинаристке (на парах в выделенное под это время) или ассистенту (в приемные часы). Необходимые для сдачи задачи записи (выкладки / рисунки) просьба делать заранее. Подробно записывать решение не обязательно. | Каждую неделю будет выдаваться листок с задачами. Часть из них будут разбираться на семинаре, несколько задач из каждого листка будут выделены для индвидуальной устной сдачи — назовем их оцениваемыми задачами. Сдавать задачи можно только устно семинаристке (на парах в выделенное под это время) или ассистенту (в приемные часы). Необходимые для сдачи задачи записи (выкладки / рисунки) просьба делать заранее. Подробно записывать решение не обязательно. | ||
− | '''Дедлайн по оцениваемым задачам:''' 23:59 | + | '''Дедлайн по оцениваемым задачам:''' 23:59 понедельника недели следующей за той, когда был выдан листок. То есть по оцениваемым задачам недели 2 дедлайн будет 16 ноября в 23:59. Реально дедлайн будет раньше, поскольку часы сдачи оцениваемых задач ограничиваются семинарами и приемными часами ассистента. |
O {семинары} = 10 * <число сданных оцениваемых задач> / <общее число оцениваемых задач> | O {семинары} = 10 * <число сданных оцениваемых задач> / <общее число оцениваемых задач> | ||
Округление арифметическое. | Округление арифметическое. |
Текущая версия на 12:44, 14 июня 2021
Семинаристка: Катя Минеева
Занятия: Четверг 11:10 - 14:00, аудитория R608
Ассистент: Миша Виноградов
Часы приема задач:
Четверг 18:00
Суббота 16:00
Общая страница курса — 2 модуль
Общая страница курса — 4 модуль
Содержание
Листки с задачами в 4 модуле
1 неделя. Поиск в глубину. Связность, компоненты связности, циклы, двудольность.
Оцениваемые задачи: 5, 6.
Дедлайн: четверг 22 апреля в 23:59.
2 неделя. Поиск в глубину продолжение: топсорт, мосты, точки сочленения. Поиск в ширину.
Оцениваемые задачи: 4, 6, 7.
Дедлайн: четверг 29 апреля в 23:59.
3 неделя. Дейкстра. Форд-Беллман, Флойд.
Оцениваемые задачи: 5, 8.
Дедлайн: четверг 29 апреля в 23:59.
4 неделя. Остовные деревья, DSU. Сбалансированные деревья поиска.
Оцениваемые задачи: нет.
Дедлайн: четверг 13 мая в 23:59.
5 неделя. Декартово дерево, LCA (наименьший общий предок).
Оцениваемые задачи: 1, 7.
Дедлайн: четверг 10 июня в 23:59.
6 неделя. -
7 неделя. Алгоритмы теории чисел. Комбинаторные объекты.
Оцениваемые задачи: покажите, что алгоритм Евклида работает за O(log(min(a, b))).
Дедлайн: четверг 10 июня в 23:59.
Оценка за семинары в 4 модуле
(UPD: для удобства прежние баллы за тесты и оцениваемые задачи были домножены на 4 — сейчас это 4 и 8 баллов соответственно)
Баллы за семинар можно получить двумя способами:
- Устная сдача оцениваемых задач ассистенту. Каждую неделю такие задачи будут выдаваться из семинарского листка. По умолчанию такие задачи стоят 8 баллов, если другое не оговорено отдельно. Дедлайн по ним до 23:59 четверга следующего за тем, когда были выданы задачи.
- Короткие тесты на семинарах. Это несколько несложных вопросов. Не на идею, а на какое-то базовое понимание материала. Полностью правильно написанный тест стоит 4 балла.
O {семинары} = min(10, <баллы в пунктах 1 и 2> / (0.6 * <максимальное число баллов в пункте 1>)
То есть на 10 нужно решить 60% оцениваемых задач или меньше, если есть баллы за тесты.
Листки с задачами во 2 модуле
1 неделя. Алгоритм. Сложность алгоритма. Анализ сложности. Асимптотические оценки. Сортировка слиянием.
Оцениваемые задачи: Задача 1 (пункты 4, 5, 6), Задача 2, Задача 3 (пункт 2), Задача 11.
Дедлайн: вс 8 ноября 23:59.
Неделя 2. Амортизационный анализ, квадратичные сортировки, двоичная куча, быстрая сортировка, порядковые
статистики.
Оцениваемые задачи: 1 (см. комментарий в чате), 4 (сложность операций — логарифм), 9, 13с, 14.
Дедлайн: пн 16 ноября 23:59.
Неделя 3. Сортировка подсчётом. Цифровая сортировка.
Двоичный поиск.
Оцениваемые задачи: 2, 4 (все числа от 0 до n, время работы линейное. в алгоритме верните ответ по модулю 10^10 — это нужно, чтобы не думать про длинную арифметику; если этот комментарий вас смущает, то игнорируйте его во время решения и обсудите с примнимающим), 11 (предподсчёт за линейное время), 13.
Дедлайн: пн 23 ноября 23:59.
Неделя 4. Биномиальные кучи, фиббоначиевы кучи.
Оцениваемые задачи: 3, 8, 9, 10.
Дедлайн: пн 30 ноября 23:59.
Неделя 5. Динамическое программирование.
Оцениваемые задачи: 2, 4, 7, 10, 13.
Дедлайн: пн 7 декабря 23:59.
Оцениваемые задачи: Нет.
Оцениваемые задачи: 7, 11, 12.
Дедлайн: пн 21 декабря 23:59.
Неделя 8. Дерево отрезков.
Оцениваемые задачи: 1. 4 — бонусная. За решение бонусной задачи дается +2 балла к сумме баллов за ДЗ, но в знаменателе (числе обязательных задач) она учитываться не будет.
Дедлайн: пн 21 декабря 23:59.
Оценка за семинары во 2 модуле
Внимание: в течение первых двух недель правила выставления семинарской оценки могут незначительно измениться.
Каждую неделю будет выдаваться листок с задачами. Часть из них будут разбираться на семинаре, несколько задач из каждого листка будут выделены для индвидуальной устной сдачи — назовем их оцениваемыми задачами. Сдавать задачи можно только устно семинаристке (на парах в выделенное под это время) или ассистенту (в приемные часы). Необходимые для сдачи задачи записи (выкладки / рисунки) просьба делать заранее. Подробно записывать решение не обязательно.
Дедлайн по оцениваемым задачам: 23:59 понедельника недели следующей за той, когда был выдан листок. То есть по оцениваемым задачам недели 2 дедлайн будет 16 ноября в 23:59. Реально дедлайн будет раньше, поскольку часы сдачи оцениваемых задач ограничиваются семинарами и приемными часами ассистента.
O {семинары} = 10 * <число сданных оцениваемых задач> / <общее число оцениваемых задач>
Округление арифметическое.