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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Экзамен)
(не показаны 33 промежуточные версии 2 участников)
Строка 4: Строка 4:
  
 
Лектор: [https://www.hse.ru/org/persons/133408680 Михаил Сергеевич Густокашин]
 
Лектор: [https://www.hse.ru/org/persons/133408680 Михаил Сергеевич Густокашин]
 +
 +
[https://docs.google.com/spreadsheets/d/e/2PACX-1vSu12yaEDNFey5wvUihzckmm8WuFtozI_LxJn9AyuP45dexlK5flwcGsVA2RO2zIIGkv40q2TeLdsrr/pubhtml?gid=1202613864&single=true Текущие результаты]
  
 
Лекции по понедельникам с 14:40 до 16:00 и по четвергам с 13:00 до 14:20.
 
Лекции по понедельникам с 14:40 до 16:00 и по четвергам с 13:00 до 14:20.
Строка 11: Строка 13:
 
! № !! Дата !! Тема !! Запись лекции !! ДЗ !! Дедлайн
 
! № !! Дата !! Тема !! Запись лекции !! ДЗ !! Дедлайн
 
|-
 
|-
| 1 || 25.10 || Алгоритмы и их сложность || Лекция 1 || [ДЗ 1 https://official.contest.yandex.ru/contest/30819] || 10.11
+
| 1 || 25.10 || Алгоритмы и их сложность || [https://disk.yandex.ru/i/64wOA1qrfiqzCw Лекция 1] || [https://official.contest.yandex.ru/contest/30819 ДЗ 1] || 10.11
 
|-
 
|-
| 2 || 28.10 || Динамический массив. Стек. Очередь. Дек || Лекция 2 || ДЗ 2 || 13.11
+
| 2 || 28.10 || Динамический массив. Стек. Очередь. Дек || [https://disk.yandex.ru/i/2r9oy-wwYnXcyw Лекция 2] || [https://official.contest.yandex.ru/contest/30905 ДЗ 2] || 13.11
 
|-
 
|-
| 3 || 1.11 || Сортировки. Куча || Лекция 3 || ДЗ 3 || 17.11
+
| 3 || 1.11 || Сортировки. Куча || [https://disk.yandex.ru/i/sVun8v-2LjhLXw Лекция 3] || [https://official.contest.yandex.ru/contest/30956 ДЗ 3] || 17.11
 
|-
 
|-
| 4 || 8.11 || Быстрая сортировка. Кучи || Лекция 4 || ДЗ 4 || 17.11
+
| 4 || 8.11 || Быстрая сортировка. Двоичный поиск || [https://disk.yandex.ru/i/GVwZ6u7IeiyCFg Лекция 4] || [https://official.contest.yandex.ru/contest/31185 ДЗ 4] || 17.11
 
|-
 
|-
| 5 || 11.11 || Сортировка подсчетом и поразрядная. Хеш-таблицы. || Лекция 5 || ДЗ 5 || 20.11
+
| 5 || 11.11 || Сортировка подсчетом и поразрядная. Хеш-таблицы. || [https://disk.yandex.ru/i/0xv9lChY8sipRw Лекция 5] || [https://official.contest.yandex.ru/contest/31315 ДЗ 5] || 20.11
 
|-
 
|-
| 6 || 15.11 || Два указателя. Сортировка событий || Лекция 6 || ДЗ 6 || 24.11
+
| 6 || 15.11 || Два указателя. Сортировка событий || [https://disk.yandex.ru/i/7ZSFAuZ4HbJWOw Лекция 6] || [https://official.contest.yandex.ru/contest/31497 ДЗ 6] || 24.11
 
|-
 
|-
| 7 || 18.11 || Динамическое программирование. Классические задачи || Лекция 7 || ДЗ 7 || 27.11
+
| 7 || 18.11 || Динамическое программирование. Классические задачи || [https://disk.yandex.ru/i/ky4qZdW_BaRNEw Лекция 7] || [https://official.contest.yandex.ru/contest/31732 ДЗ 7] || 27.11
 
|-
 
|-
 
| - || 22.11 || '''Защита ДЗ 1-5''' || - || - || -
 
| - || 22.11 || '''Защита ДЗ 1-5''' || - || - || -
 
|-
 
|-
| 8 || 25.11 || Двумерная динамика. Динамика по подстрокам || Лекция 8 || ДЗ 8 || 4.12
+
| 8 || 25.11 || Двумерная динамика. Динамика по подстрокам || [https://disk.yandex.ru/i/qXv0tvxy-v90PA Лекция 8] || [https://official.contest.yandex.ru/contest/32263 ДЗ 8] || 6.12
 
|-
 
|-
| 9 || 29.11 || Динамическое программирование. Задача о рюкзаке. Жадные алгоритмы || Лекция 9 || ДЗ 9 || 8.12
+
| 9 || 29.11 || Динамическое программирование. Задача о рюкзаке. Жадные алгоритмы || [https://disk.yandex.ru/i/oRtDZui-FtUg-w Лекция 9] || [https://official.contest.yandex.ru/contest/32470 ДЗ 9] || 10.12
 
|-
 
|-
| 10 || 2.12 || Хеши для строк || Лекция 10 || ДЗ 10 || 11.12
+
| 10 || 2.12 || Хеши для строк || [https://disk.yandex.ru/i/fMRunLRgOe_rjw Лекция 10] || [https://official.contest.yandex.ru/contest/32748 ДЗ 10] || 12.12
 
|-
 
|-
| 11 || 6.12 || Биномиальная и Фибоначчиевы кучи || Лекция 11 || - || -
+
| 11 || 6.12 || Биномиальная и Фибоначчиевы кучи || [https://disk.yandex.ru/i/40_lN4w8FCmkJQ Лекция 11] || - || -
 
|-
 
|-
 
| 12 || 9.12 || Запасная лекция || Лекция 12 || - || -
 
| 12 || 9.12 || Запасная лекция || Лекция 12 || - || -
 
|-
 
|-
| - || 13.10 || '''Защита ДЗ 6-10''' || - || - || -
+
| - || 13.12 || '''Защита ДЗ 6-10''' || - || - || -
 
|-
 
|-
| - || 16.10 || '''Переписывание защиты по выбору студента''' || - || - || -
+
| - || 16.12 || '''Переписывание защиты по выбору студента''' || - || - || -
 
|}
 
|}
  
Строка 59: Строка 61:
  
 
Защита ДЗ 1-5 будет проходить в онлайн-формате с использованием прокторинга. Прокторинг как на курсах ОиМП: http://wiki.cs.hse.ru/%D0%9A%D0%A0_1_%D0%9E%D0%B8%D0%9C%D0%9F-3_2021  
 
Защита ДЗ 1-5 будет проходить в онлайн-формате с использованием прокторинга. Прокторинг как на курсах ОиМП: http://wiki.cs.hse.ru/%D0%9A%D0%A0_1_%D0%9E%D0%B8%D0%9C%D0%9F-3_2021  
 +
 +
Вход в контест: https://official.contest.yandex.ru/contest/31838
 +
 +
Форма для сдачи записанных видео: https://docs.google.com/forms/d/e/1FAIpQLScGcUyDIRyDMEzg-MNDV4FjNAUZkqJqVifiIUM0w6PPsgfGKw/viewform
  
 
На защите ДЗ разрешается использовать эту вики-страницу, сайт https://docs.python.org, а также свои решения задач из контестов с домашними заданиями.
 
На защите ДЗ разрешается использовать эту вики-страницу, сайт https://docs.python.org, а также свои решения задач из контестов с домашними заданиями.
Строка 95: Строка 101:
 
|-
 
|-
 
|}
 
|}
 +
 +
== Защита ДЗ 6-10 ==
 +
 +
Защита ДЗ происходит во время и вместо лекции 13.12 с 14:40 до 16:00.
 +
 +
Правила как на защите ДЗ 1-5
 +
 +
Вход в контест: https://official.contest.yandex.ru/contest/33456
 +
 +
Форма для сдачи записанных видео: https://docs.google.com/forms/d/e/1FAIpQLSfufTklXvVJo_-jsjc7JEsht1uJ10Q7XKyezExPgA1tA9Uirw/viewform
 +
 +
== Переписывание защиты ==
 +
 +
Переписывание защиты ДЗ происходит во время и вместо лекции 16.12 с 13:00 до 14:20.
 +
 +
Правила как на защите ДЗ 1-5. Переписывать можно только одну из защит
 +
 +
Вход в контест для переписывания защиты 1-5: https://official.contest.yandex.ru/contest/33559
 +
 +
Вход в контест для переписывания защиты 6-10: https://official.contest.yandex.ru/contest/33654
 +
 +
Форма для сдачи записанных видео: https://docs.google.com/forms/d/e/1FAIpQLSetcyrOep6V6YP-7bG928rmjebTqRQBhd_M5SDVeF7_TVN0TA/viewform
  
 
== Экзамен ==
 
== Экзамен ==
  
Экзамен пройдет в устном формате.
+
Экзамен заочный, состоится в пятницу 24 декабря, с 12:00 до 14:00 (продолжительность — 2 астрономических часа).
 +
 
 +
Ссылка на вход в контест для ПМИ: https://official.contest.yandex.ru/contest/33910
  
Студенту будет предложены простые вопросы, отвечать на которые нужно без подготовки.
+
Ссылка на вход в контест для КНАД: https://official.contest.yandex.ru/contest/33965
  
Тематика вопросов совпадает с темами лекций.
+
Контест состоит из большого количества вопросов с кратким ответом. Примеры вопросов:
 +
* Выберите правильную оценку сложности для показанного фрагмента кода;
 +
* С изначально пустым стеком выполнили следующую последовательность операций. Выведите текущее состояние стека;
 +
* В отсортированном массиве размера 100 000 ищут элемент при помощи бинарного поиска. Какое максимальное количество итераций потребуется?
  
Если у студента есть автомат, либо студент не желает приходить на экзамен, то на экзамен можно не приходить (в последнем случае в ведомость будет выставлена неявка, что эквивалентно оценке 0).
+
Ответ на каждый вопрос требуется ввести в текстовое поле или выбрать один из вариантов. Количество попыток не ограничено, проверяется последняя. Результаты проверки ответов становятся видны '''только после окончания экзамена'''.
  
Время экзамена для одного студента 25 минут, затем перерыв 5 минут.
+
В каждом вопросе явно описан формат ответа: одно число, два числа через пробел, перестановка букв без разделителей и т. п. <span style="color:red">Будьте внимательны: если правильный ответ «abc», а вы напишете «a b c» или «a,b,c», то ответ не будет зачтен.</span>
  
Студенту предлагаются четыре вопроса, на которые можно отвечать в любом порядке.
+
Ответ на каждый вопрос оценивается как верный или неверный (промежуточных оценок нет). Оценка за экзамен равна 10 * количество верных ответов / количество вопросов.
  
Если студент отказывается отвечать на вопросы экзамена, он получает 0 и уходит. Если студент начинает отвечать, он сразу получает 1 балл («за волю к победе»).
+
Разрешается использовать приложения «блокнот» (и аналоги) и «калькулятор», писать программы на Python, а также пользоваться чистой бумагой и ручкой.
  
За каждый вопрос студент получает 0, 1 или 2 балла (в зависимости от полноты решения).
+
Не разрешается использовать телефон и устройства, наушники. '''Не разрешается пользоваться конспектом лекций или смотреть записи лекций, а также использовать решения домашних заданий.'''
  
Если студент набрал 9 баллов и остается время, студенту предлагается пятый вопрос, за который можно получить 0 или 1 балл.
+
Осуществляется прокторинг аналогично контрольным работам. Ссылка на форму для отправки видео: https://docs.google.com/forms/d/e/1FAIpQLSeX7T6j4hw8d40GeVSaCkLUCtyXoyd0KeZTTB0wvDSHMS6lBA/viewform

Версия 23:39, 23 декабря 2021

Форма сбора пожеланий и предложений по курсу

Лекции и ДЗ

Лектор: Михаил Сергеевич Густокашин

Текущие результаты

Лекции по понедельникам с 14:40 до 16:00 и по четвергам с 13:00 до 14:20.

Дата Тема Запись лекции ДЗ Дедлайн
1 25.10 Алгоритмы и их сложность Лекция 1 ДЗ 1 10.11
2 28.10 Динамический массив. Стек. Очередь. Дек Лекция 2 ДЗ 2 13.11
3 1.11 Сортировки. Куча Лекция 3 ДЗ 3 17.11
4 8.11 Быстрая сортировка. Двоичный поиск Лекция 4 ДЗ 4 17.11
5 11.11 Сортировка подсчетом и поразрядная. Хеш-таблицы. Лекция 5 ДЗ 5 20.11
6 15.11 Два указателя. Сортировка событий Лекция 6 ДЗ 6 24.11
7 18.11 Динамическое программирование. Классические задачи Лекция 7 ДЗ 7 27.11
- 22.11 Защита ДЗ 1-5 - - -
8 25.11 Двумерная динамика. Динамика по подстрокам Лекция 8 ДЗ 8 6.12
9 29.11 Динамическое программирование. Задача о рюкзаке. Жадные алгоритмы Лекция 9 ДЗ 9 10.12
10 2.12 Хеши для строк Лекция 10 ДЗ 10 12.12
11 6.12 Биномиальная и Фибоначчиевы кучи Лекция 11 - -
12 9.12 Запасная лекция Лекция 12 - -
- 13.12 Защита ДЗ 6-10 - - -
- 16.12 Переписывание защиты по выбору студента - - -

Система оценки

Оценка за весь курс: 0.3 * ДЗ1-5 + 0.3 * ДЗ6-10 + 0.1 * Семинары + 0.3 * Экзамен

Оценка за может быть выставлена автоматом, если выполнены два условия:

  • текущая оценка ((0.3 * ДЗ1-5 + 0.3 * ДЗ6-10 + 0.1 * Семинары) / 0.7) >= 8
  • оценка за семинары >= 8

Автоматом выставляется текущая оценка.

Округление происходит один раз, при выставлении оценки за весь курс

Защита ДЗ 1-5

Защита ДЗ происходит во время и вместо лекции.

Защита ДЗ 1-5 будет проходить в онлайн-формате с использованием прокторинга. Прокторинг как на курсах ОиМП: http://wiki.cs.hse.ru/%D0%9A%D0%A0_1_%D0%9E%D0%B8%D0%9C%D0%9F-3_2021

Вход в контест: https://official.contest.yandex.ru/contest/31838

Форма для сдачи записанных видео: https://docs.google.com/forms/d/e/1FAIpQLScGcUyDIRyDMEzg-MNDV4FjNAUZkqJqVifiIUM0w6PPsgfGKw/viewform

На защите ДЗ разрешается использовать эту вики-страницу, сайт https://docs.python.org, а также свои решения задач из контестов с домашними заданиями.

Предварительная оценка за ДЗ 1-5 (обозначатся в формулах как ДЗ) считается как средняя оценка за все ДЗ с 1 по 5 включительно. Защита ДЗ 1-5 состоит из 5 задач. Итоговая оценка за ДЗ 1-5 определяется следующим образом:

  • Если на защите решено 0 задач: ДЗ * 0.25
  • Если на защите решена 1 задача: min(ДЗ, max(0, 2 + (ДЗ - 2) * 0.25))
  • Если на защите решено 2 задачи: min(ДЗ, 4 + max(0, (ДЗ - 4) * 0.5))
  • Если на защите решено 3 задачи: min(ДЗ, 6 + max(0, (ДЗ - 6) * 0.75))
  • Если на защите решено 4 задачи: ДЗ
  • Если на защите решено 5 задач: min(ДЗ + 2, 10)

В таблице показаны примеры применения формулы для целочисленных значений ДЗ:

0 1 2 3 4 5 6 7 8 9 10
0 0 0,25 0,5 0,75 1 1,25 1,5 1,75 2 2,25 2,5
1 0 1 2 2,25 2,5 2,75 3 3,25 3,5 3,75 4
2 0 1 2 3 4 4,5 5 5,5 6 6,5 7
3 0 1 2 3 4 5 6 6,75 7,5 8,25 9
4 0 1 2 3 4 5 6 7 8 9 10
5 2 3 4 5 6 7 8 9 10 10 10

Защита ДЗ 6-10

Защита ДЗ происходит во время и вместо лекции 13.12 с 14:40 до 16:00.

Правила как на защите ДЗ 1-5

Вход в контест: https://official.contest.yandex.ru/contest/33456

Форма для сдачи записанных видео: https://docs.google.com/forms/d/e/1FAIpQLSfufTklXvVJo_-jsjc7JEsht1uJ10Q7XKyezExPgA1tA9Uirw/viewform

Переписывание защиты

Переписывание защиты ДЗ происходит во время и вместо лекции 16.12 с 13:00 до 14:20.

Правила как на защите ДЗ 1-5. Переписывать можно только одну из защит

Вход в контест для переписывания защиты 1-5: https://official.contest.yandex.ru/contest/33559

Вход в контест для переписывания защиты 6-10: https://official.contest.yandex.ru/contest/33654

Форма для сдачи записанных видео: https://docs.google.com/forms/d/e/1FAIpQLSetcyrOep6V6YP-7bG928rmjebTqRQBhd_M5SDVeF7_TVN0TA/viewform

Экзамен

Экзамен заочный, состоится в пятницу 24 декабря, с 12:00 до 14:00 (продолжительность — 2 астрономических часа).

Ссылка на вход в контест для ПМИ: https://official.contest.yandex.ru/contest/33910

Ссылка на вход в контест для КНАД: https://official.contest.yandex.ru/contest/33965

Контест состоит из большого количества вопросов с кратким ответом. Примеры вопросов:

  • Выберите правильную оценку сложности для показанного фрагмента кода;
  • С изначально пустым стеком выполнили следующую последовательность операций. Выведите текущее состояние стека;
  • В отсортированном массиве размера 100 000 ищут элемент при помощи бинарного поиска. Какое максимальное количество итераций потребуется?

Ответ на каждый вопрос требуется ввести в текстовое поле или выбрать один из вариантов. Количество попыток не ограничено, проверяется последняя. Результаты проверки ответов становятся видны только после окончания экзамена.

В каждом вопросе явно описан формат ответа: одно число, два числа через пробел, перестановка букв без разделителей и т. п. Будьте внимательны: если правильный ответ — «abc», а вы напишете «a b c» или «a,b,c», то ответ не будет зачтен.

Ответ на каждый вопрос оценивается как верный или неверный (промежуточных оценок нет). Оценка за экзамен равна 10 * количество верных ответов / количество вопросов.

Разрешается использовать приложения «блокнот» (и аналоги) и «калькулятор», писать программы на Python, а также пользоваться чистой бумагой и ручкой.

Не разрешается использовать телефон и устройства, наушники. Не разрешается пользоваться конспектом лекций или смотреть записи лекций, а также использовать решения домашних заданий.

Осуществляется прокторинг аналогично контрольным работам. Ссылка на форму для отправки видео: https://docs.google.com/forms/d/e/1FAIpQLSeX7T6j4hw8d40GeVSaCkLUCtyXoyd0KeZTTB0wvDSHMS6lBA/viewform