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

Текущая версия на 10:19, 8 февраля 2021

Информация о пересдачах экзамена

Лектор: Сергей Мельников

Контакты: http://t.me/melnikov hse@melnikov.ch (пожалуйста представляйтесь)

Расписание лекций:
вторник 11:10 – 12:30
четверг 11:10 – 12:30

Канал для объявлений:
https://t.me/aisd1_20

Формула оценки
0.3 * Домашнее задание + 0.2 * Контрольная работа + 0.1 * Работа на семинаре + 0.4 * Экзамен

Лекции

записи лекций на ютубе

1. 27 октября. Алгоритм. Сложность алгоритма. Анализ сложности. Асимптотические оценки. Сортировка вставками. Сортировка слиянием. Jupyterpdf Video
2. 29 октября. Структуры данных. Динамический массив (list с append-ом). Стек. Очередь. Дек Jupyterpdf Video
3. 3 ноября. Куча. Сортировка кучей. Jupyterpdf Video
4. 5 ноября. Сортировка выбором. Сортировка пузырьком. Быстрая сортировка. Поиск k-й порядковой статистики. Jupyterpdf Video
5. 10 ноября. Оценка снизу на сортировки сравнениями. Сортировка подсчётом. Цифровая сортировка. Jupyter pdf Video
6. 12 ноября. Двоичный поиск. Троичный поиск. Jupyter pdf Video
7. 17 ноября. Биномиальная куча, Фибоначчиева куча. Jupyterpdf Video
8. 19 ноября. Контрольная работа.
9. 24 ноября. Динамическое программирование. Числа Фибоначчи. Кузнечик, черепашка. Наибольшая возрастающая последовательность. Jupyterpdf Video
10. 26 ноября. Динамическое программирование. Задача о выравнивании текста. Расстояние Левенштейна. Задача о рюкзаке. JupyterpdfVideo
11. 3 декабря. Динамическое программирование по подмножествам. Задача о нескольких рюкзаках. Задача Коммивояжёра. JupyterpdfVideo
12. 8 декабря. Хеш-таблицы. Разрешение коллизий с помощью списков. Открытая адресация. Jupyterpdf Video
13. 10 декабря. Хеш-таблицы. Идеальное хеширование. Хеширование Кукушки. Фильтр Блума. JupyterpdfVideo
14. 15 декабря. Дерево отрезков. Реализации сверху и снизу. JupyterpdfVideo
15. 17 декабря. Дерево отрезков. Массовая операция на отрезке. Jupyterpdf

Контрольная работа 19.11

• 19.11 11:10–12:30 Ссылка на контест
• Контест из 5 задач, аналогичных домашним. Темы: сортировка, стек, очередь, двоичная куча, двоичный поиск, троичный поиск.
• Оценка зависит от количества решённых задач: 0 задач → 0 баллов, 1 задача → 4 балла, 2 задачи → 7 баллов, 3 задачи → 9 баллов, 4 или 5 задач → 10 баллов, штрафов за количество посылок нет.
• Используются правила асинхронного прокторинга, аналогичные курсу ОиМП. Ссылку на запись нужно будет отправить через форму до 13:00.
• Разрешается пользоваться только сайтом тестирующей системы (в том числе своими посылками в ДЗ), средами разработки (не онлайн, а установленными на компьютере), выложенными на wiki jupyter/pdf и документацией на docs.python.org. Заранее отключите все мессенджеры и закройте лишние вкладки.
• Можно и нужно использовать функции стандартной библиотеки Python (например, незачем реализовывать сортировку вручную, если можно воспользоваться встроенной).

Домашние задания

1. Домашнее задание 1 (дедлайн — 5 ноября; дедлайн со штрафом 50% — 12 ноября)
2. Домашнее задание 2 (дедлайн — 12 ноября; дедлайн со штрафом 50% — 19 ноября)
3. Домашнее задание 3 (дедлайн — 19 ноября; дедлайн со штрафом 50% — 26 ноября) Обратите внимание, что добавлена проверка решений на PEP8.
4. Домашнее задание 4 (дедлайн — 3 декабря; дедлайн со штрафом 50% — 10 декабря)
5. Домашнее задание 5 (дедлайн — 13 декабря; дедлайн со штрафом 50% — 17 декабря)
6. Домашнее задание 6 (дедлайн — 20 декабря)
7. Домашнее задание 7 (дедлайн — 20 декабря)

Итоговая оценка за выполнение домашних заданий определяется по формуле round((A + 0.5B - 2C) / 47 * 10), где:

• A — количество задач, сданных до дедлайнов;
• B — количество задач, сданных после дедлайнов;
• C — количество штрафных баллов за нарушение академических норм.

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

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

Автомат

Чтобы претендовать на автомат, студент должен удовлетворять следующим критериям:

• Иметь оценку за работу на семинарах не ниже 8;
• Иметь доэкзаменационную оценку не ниже 8.

Доэкзаменационная оценка вычисляется по формуле round((0.1С + 0.2К + 0.3Д) / 0.6), где С — оценка за семинары, К — оценка за контрольную работу, Д — оценка за домашние задания. Все оценки — целые числа от 0 до 10.

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

Экзамен

• 23.12 11:10–12:30. Ссылка на контест
• Контест из 5 задач, преимущественно по темам второй половины модуля (но темы первой половины также могут встретиться).
• Оценка зависит от количества решённых задач: 0 задач → 0 баллов, 1 задача → 4 балла, 2 задачи → 7 баллов, 3 задачи → 9 баллов, 4 или 5 задач → 10 баллов, штрафов за количество посылок нет.
• Используются правила асинхронного прокторинга. Ссылку на запись нужно будет отправить через форму до 13:00.
• Разрешается пользоваться только сайтом тестирующей системы (в том числе своими посылками в ДЗ), средами разработки (не онлайн, а установленными на компьютере), выложенными на wiki jupyter/pdf и документацией на docs.python.org. Заранее отключите все мессенджеры и закройте лишние вкладки.
• Можно и нужно использовать функции стандартной библиотеки Python (например, незачем реализовывать сортировку вручную, если можно воспользоваться встроенной).

Пересдачи экзамена

• Первая пересдача: 25.01 11:10–12:30. Ссылка на контест
• Вторая пересдача: 02.02 09:30–10:50. Ссылка на контест
• Пересдача (комиссия): 08.20.2020 11:10–12:30 Ссылка на контест
• Содержание, формат проведения и правила пересдач те же, что и у экзамена.
• Форма для отправки записей. Запись нужно отправить в течение получаса после окончания пересдачи.

Семинары

Подгруппа 209-1