Алгоритмы и структуры данных 1 2020/2021 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
V.folunin (обсуждение | вклад) (→Домашние задания) |
|||
| Строка 20: | Строка 20: | ||
# 3 ноября. Куча. Сортировка кучей. [https://drive.google.com/file/d/1XsMcxnQiovEv3o2Ml4bsrLaUDZFZBJrE/view?usp=sharing Jupyter][https://drive.google.com/file/d/1TE-39NKRNne8Y6FUh5xnDuWBO4GAhYyq/view?usp=sharing pdf] [https://www.youtube.com/watch?v=BUpHMEFbYf0 Video] | # 3 ноября. Куча. Сортировка кучей. [https://drive.google.com/file/d/1XsMcxnQiovEv3o2Ml4bsrLaUDZFZBJrE/view?usp=sharing Jupyter][https://drive.google.com/file/d/1TE-39NKRNne8Y6FUh5xnDuWBO4GAhYyq/view?usp=sharing pdf] [https://www.youtube.com/watch?v=BUpHMEFbYf0 Video] | ||
# 5 ноября. Сортировка выбором. Сортировка пузырьком. Быстрая сортировка. Поиск k-й порядковой статистики. [https://drive.google.com/file/d/1YPcVTPLmG8JOUUjFXVx6WHP45_i_CNbj/view?usp=sharing Jupyter][https://drive.google.com/file/d/11XwL9QUtdzdcxPNUoX9ohCAi0j3rnM9j/view?usp=sharing pdf] [https://youtu.be/JbfiFW1Fyvo Video] | # 5 ноября. Сортировка выбором. Сортировка пузырьком. Быстрая сортировка. Поиск k-й порядковой статистики. [https://drive.google.com/file/d/1YPcVTPLmG8JOUUjFXVx6WHP45_i_CNbj/view?usp=sharing Jupyter][https://drive.google.com/file/d/11XwL9QUtdzdcxPNUoX9ohCAi0j3rnM9j/view?usp=sharing pdf] [https://youtu.be/JbfiFW1Fyvo Video] | ||
| − | # 10 ноября. Оценка снизу на сортировки сравнениями. Сортировка подсчётом. Цифровая сортировка. [https://drive.google.com/file/d/1e2oEHNUSdrZp66FgUoj884-uvN9gjyjE/view?usp=sharing Jupyter] [https://drive.google.com/file/d/1Ee5hPbFrEB8dDi5Sh21Kzf3jjG2WnogO/view?usp=sharing pdf] | + | # 10 ноября. Оценка снизу на сортировки сравнениями. Сортировка подсчётом. Цифровая сортировка. [https://drive.google.com/file/d/1e2oEHNUSdrZp66FgUoj884-uvN9gjyjE/view?usp=sharing Jupyter] [https://drive.google.com/file/d/1Ee5hPbFrEB8dDi5Sh21Kzf3jjG2WnogO/view?usp=sharing pdf] [https://www.youtube.com/watch?v=qFtnZI6j-wM Video] |
| − | # 12 ноября. Двоичный поиск. Троичный поиск. [https://drive.google.com/file/d/1-PBPKOhg7TnsirbHtunGU4fOh3fW__vq/view?usp=sharing Jupyter] [https://drive.google.com/file/d/1K2OmdSELMtUFoDm7h2eetoygjrJoLXMw/view?usp=sharing pdf] | + | # 12 ноября. Двоичный поиск. Троичный поиск. [https://drive.google.com/file/d/1-PBPKOhg7TnsirbHtunGU4fOh3fW__vq/view?usp=sharing Jupyter] [https://drive.google.com/file/d/1K2OmdSELMtUFoDm7h2eetoygjrJoLXMw/view?usp=sharing pdf] [https://www.youtube.com/watch?v=muaZ3DTlwGo Video] |
| − | # 17 ноября. Биномиальная куча, Фибоначчиева куча. [https://drive.google.com/file/d/1Pf8PTS32F-mdR3OBMTz8-jW2BNhHzANG/view?usp=sharing Jupyter][https://drive.google.com/file/d/1JGbb4kvxo39b4gCnoc45TPIt-dAv3Gay/view?usp=sharing pdf] | + | # 17 ноября. Биномиальная куча, Фибоначчиева куча. [https://drive.google.com/file/d/1Pf8PTS32F-mdR3OBMTz8-jW2BNhHzANG/view?usp=sharing Jupyter][https://drive.google.com/file/d/1JGbb4kvxo39b4gCnoc45TPIt-dAv3Gay/view?usp=sharing pdf] [https://www.youtube.com/watch?v=NbYEnaEcg5A Video] |
# 19 ноября. Контрольная работа. | # 19 ноября. Контрольная работа. | ||
Версия 17:18, 18 ноября 2020
Лектор: Сергей Мельников
Контакты: 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 * Экзамен
Лекции
- 27 октября. Алгоритм. Сложность алгоритма. Анализ сложности. Асимптотические оценки. Сортировка вставками. Сортировка слиянием. Jupyterpdf Video
- 29 октября. Структуры данных. Динамический массив (list с append-ом). Стек. Очередь. Дек Jupyterpdf Video
- 3 ноября. Куча. Сортировка кучей. Jupyterpdf Video
- 5 ноября. Сортировка выбором. Сортировка пузырьком. Быстрая сортировка. Поиск k-й порядковой статистики. Jupyterpdf Video
- 10 ноября. Оценка снизу на сортировки сравнениями. Сортировка подсчётом. Цифровая сортировка. Jupyter pdf Video
- 12 ноября. Двоичный поиск. Троичный поиск. Jupyter pdf Video
- 17 ноября. Биномиальная куча, Фибоначчиева куча. Jupyterpdf Video
- 19 ноября. Контрольная работа.
Контрольная работа 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 (дедлайн — 5 ноября; дедлайн со штрафом 50% — 12 ноября)
- Домашнее задание 2 (дедлайн — 12 ноября; дедлайн со штрафом 50% — 19 ноября)
- Домашнее задание 3 (дедлайн — 19 ноября; дедлайн со штрафом 50% — 26 ноября) Обратите внимание, что добавлена проверка решений на PEP8.
- На неделе 16.11–22.11 домашнее задание не выдаётся. Удачи на контрольной работе!
Итоговая оценка за выполнение домашних заданий пропорциональна общему количеству решённых задач во всех домашних контестах (задачи, решённые после основного дедлайна, учитываются с весом 0.5). В момент появления последнего набора домашних задач также будут объявлены:
- Количество решённых задач, требующееся для получения итоговой оценки 10 баллов (это количество будет меньше общего количества задач во всех домашних контестах);
- Величина штрафа за нарушение академических норм. Повторное нарушение влечёт повторный штраф.
