Алгоритмы и структуры данных на ПМИ 2017/2018 (основной поток) — различия между версиями
Материал из Wiki - Факультет компьютерных наук
.obj (обсуждение | вклад) (→Домашние задания) |
.obj (обсуждение | вклад) |
||
Строка 22: | Строка 22: | ||
# [https://official.contest.yandex.ru/contest/8116/problems/ Контест 8116] — до 30.04.2018 (9:00)<br/> | # [https://official.contest.yandex.ru/contest/8116/problems/ Контест 8116] — до 30.04.2018 (9:00)<br/> | ||
# [https://official.contest.yandex.ru/contest/8224/problems/ Контест 8224] — до 23.05.2018 (9:00)<br/> | # [https://official.contest.yandex.ru/contest/8224/problems/ Контест 8224] — до 23.05.2018 (9:00)<br/> | ||
+ | |||
+ | = Контрольная работа = | ||
+ | Показ работ: | ||
+ | |||
+ | ''Задачи I варианта'' | ||
+ | # | ||
+ | # 23 мая, 11:30 – 12:00, ауд. 311 |
Версия 23:26, 15 мая 2018
Лекции
- 2 апреля. Графы: определения и приложения. Представление графов: матрица смежности и списки смежности. Поиск в глубину (рекурсивная формулировка). Сложность поиска в глубину. Применение поиска в глубину: поиск компонент связности в неориентированном графе, топологическая сортировка. Поиск в ширину. Сложность поиска в ширину. Поиск кратчайших путей.
- 5 апреля. Компоненты связности в неориентированных и ориентированных графах. Алгоритм поиска компонент сильной связности. Вычисление выполняющего набора для 2-КНФ на основе поиска компонент сильной связности.
- 9 апреля. Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры: формулировка, условия применимости, доказательство корректности, оценка сложности. Формулировка алгоритма Беллмана – Форда для графов без циклов с отрицательным весом.
- 12 апреля. Алгоритмы Беллмана – Форда и Флойда – Уоршелла как алгоритмы динамического программирования.
- 16 апреля. Динамическое программирование: наибольшая общая подпоследовательность, разбиение абзаца на строки, задача о рюкзаке.
- 19 апреля. Жадные алгоритмы: выбор максимального подмножества непересекающихся отрезков; составление плана работ с заданными продолжительностями и повременными штрафами за невыполнение, минимизирующего общий штраф; код Хаффмана.
- 23 апреля. Матроиды: графовый матроид, матроид для последовательности задач. Жадный алгоритм на взвешенном матроиде: поиск минимального остовного дерева, составление расписания задач с минимальным штрафом.
- 26 апреля. Минимальные остовные деревья. Алгоритмы Прима, Крускала, Борувки.
- 30 апреля. Лекции не будет.
- 10 мая. Три подхода к амортизационному анализу: групповой анализ, банковский метод и метод потенциалов (на примере двоичного счетчика).
- 14 мая. Письменная контрольная работа по апрельским темам. С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. Контрольная проходит в ауд. 317 (группы 172, 174, 175) и ауд. 622 (группы 176, 177 и 178).
Домашние задания
Задачи из домашних заданий можно сдавать после указанного ниже срока, но до конца 9 мая со штрафом 50%.
- Контест 7940 — до 8.04.2018 (22:00)
- Контест 7993 — до 15.04.2018 (23:59)
- Контест 8053 — до 22.04.2018 (23:59)
- Контест 8116 — до 30.04.2018 (9:00)
- Контест 8224 — до 23.05.2018 (9:00)
Контрольная работа
Показ работ:
Задачи I варианта
- 23 мая, 11:30 – 12:00, ауд. 311