Алгоритмы и структуры данных 1 2020/2021 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
V.folunin (обсуждение | вклад) |
|||
Строка 18: | Строка 18: | ||
# 27 октября. Алгоритм. Сложность алгоритма. Анализ сложности. Асимптотические оценки. Сортировка вставками. Сортировка слиянием. [https://drive.google.com/file/d/1YchZYEW35v4D_5RydRzvP0JqU42MHvaE/view?usp=sharing Jupyter][https://drive.google.com/file/d/15f88STjHa_OhzEDOhDpwoWK7ZaZ_VBf0/view?usp=sharing pdf] [https://www.youtube.com/watch?v=-YE9tP3gQ3Q Video] | # 27 октября. Алгоритм. Сложность алгоритма. Анализ сложности. Асимптотические оценки. Сортировка вставками. Сортировка слиянием. [https://drive.google.com/file/d/1YchZYEW35v4D_5RydRzvP0JqU42MHvaE/view?usp=sharing Jupyter][https://drive.google.com/file/d/15f88STjHa_OhzEDOhDpwoWK7ZaZ_VBf0/view?usp=sharing pdf] [https://www.youtube.com/watch?v=-YE9tP3gQ3Q Video] | ||
# 29 октября. Структуры данных. Динамический массив (list с append-ом). Стек. Очередь. Дек [https://drive.google.com/file/d/1nsm4u7FLxR0tNeB6ZU0xOMWoOutW225j/view?usp=sharing Jupyter][https://drive.google.com/file/d/1KAWpJEnL5f8pqGRNYF8YErpudXKOy8Sa/view?usp=sharing pdf] [https://www.youtube.com/watch?v=sNrO4sPagqo Video] | # 29 октября. Структуры данных. Динамический массив (list с append-ом). Стек. Очередь. Дек [https://drive.google.com/file/d/1nsm4u7FLxR0tNeB6ZU0xOMWoOutW225j/view?usp=sharing Jupyter][https://drive.google.com/file/d/1KAWpJEnL5f8pqGRNYF8YErpudXKOy8Sa/view?usp=sharing pdf] [https://www.youtube.com/watch?v=sNrO4sPagqo 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] | + | # 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] |
− | # 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] |
+ | # 17 ноября. | ||
+ | # 19 ноября. Контрольная работа. | ||
+ | |||
+ | == Контрольная работа 19.11 == | ||
+ | * 19.11 11:10–12:30 | ||
+ | * Контест из 5 задач, аналогичных домашним. Темы: сортировка, стек, очередь, двоичная куча, двоичный поиск, троичный поиск. Ссылка появится здесь чуть позже. | ||
+ | * Оценка зависит от количества решённых задач: 0 задач → 0 баллов, 1 задача → 4 балла, 2 задачи → 7 баллов, 3 задачи → 9 баллов, 4 или 5 задач → 10 баллов, штрафов нет. | ||
+ | * Используются [http://wiki.cs.hse.ru/%D0%97%D0%B0%D1%89%D0%B8%D1%82%D0%B0_%D0%94%D0%97_1-4_%D0%9E%D0%B8%D0%9C%D0%9F-1_2020 правила асинхронного прокторинга, аналогичные курсу ОиМП]. | ||
== Домашние задания == | == Домашние задания == |
Версия 15:35, 16 ноября 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
- 12 ноября. Двоичный поиск. Троичный поиск. Jupyter pdf
- 17 ноября.
- 19 ноября. Контрольная работа.
Контрольная работа 19.11
- 19.11 11:10–12:30
- Контест из 5 задач, аналогичных домашним. Темы: сортировка, стек, очередь, двоичная куча, двоичный поиск, троичный поиск. Ссылка появится здесь чуть позже.
- Оценка зависит от количества решённых задач: 0 задач → 0 баллов, 1 задача → 4 балла, 2 задачи → 7 баллов, 3 задачи → 9 баллов, 4 или 5 задач → 10 баллов, штрафов нет.
- Используются правила асинхронного прокторинга, аналогичные курсу ОиМП.
Домашние задания
- Домашнее задание 1 (дедлайн — 5 ноября; дедлайн со штрафом 50% — 12 ноября)
- Домашнее задание 2 (дедлайн — 12 ноября; дедлайн со штрафом 50% — 19 ноября)
- Домашнее задание 3 (дедлайн — 19 ноября; дедлайн со штрафом 50% — 26 ноября) Обратите внимание, что добавлена проверка решений на PEP8.
Итоговая оценка за выполнение домашних заданий пропорциональна общему количеству решённых задач во всех домашних контестах (задачи, решённые после основного дедлайна, учитываются с весом 0.5). В момент появления последнего набора домашних задач также будут объявлены:
- Количество решённых задач, требующееся для получения итоговой оценки 10 баллов (это количество будет меньше общего количества задач во всех домашних контестах);
- Величина штрафа за нарушение академических норм. Повторное нарушение влечёт повторный штраф.