Wiki - Факультет компьютерных наук - Вклад [ru]

Алгоритмы и структуры данных на ПМИ 2017/2018 (основной поток)/Кр критерии

2018-06-02T11:23:21Z

Sabramov: II.5

= Вариант 1 =

== Задача 1 ==

* Решение за квадратичное время при наличии доказательства и оценки времени — 2 балла
* Решение за квадратичное время без доказательства или оценки времени — 1 балл
* Решение с поиском точек сочленения без учета городов A и B — штраф 2 балла
* Решение с поиском точек сочленения с неполным доказательством корректности и оценкой времени — штраф 1–2 балла
* "Решается через точки сочленения из дз" — 1 балл
* "Решается через мосты из дз" — 0 баллов

== Задача 5 ==

* Решение за время ''O''(''nf'') — 6 баллов
* Решение за время O(''n'' log ''f'') — 8 баллов
* Решение за время ''O''(''n'') — 10 баллов.
* Неправильное решение с разумными мыслями — 2 балла

= Вариант 2 =

==Задача 2==

* Задача верно решена и обоснована — 5 баллов
* Задача решена верно, в обосновании присутствуют недочёты — 4 балла
* Задача решена верно, в обосновании есть серьёзные ошибки, либо оно отсутствует вовсе — 3 балла
* Задача решена частично, получен неправильный ответ — 2 балла
* Решение не доведено до конца — 1 балл
* Решение отсутствует — 0 баллов

==Задача 5==

* Корректное и оптимальное решение — 8 баллов
* Корректное, но не оптимальное решение — 5 балла
* Корректно описано формирование графа — 3 балла

Алгоритмы и структуры данных на ПМИ 2017/2018 (основной поток)

2018-06-02T09:54:28Z

Sabramov:

= Лекции =

# '''2 апреля.''' Графы: определения и приложения. Представление графов: матрица смежности и списки смежности. Поиск в глубину (рекурсивная формулировка). Сложность поиска в глубину. Применение поиска в глубину: поиск компонент связности в неориентированном графе, топологическая сортировка. Поиск в ширину. Сложность поиска в ширину. Поиск кратчайших путей.
# '''5 апреля.''' Компоненты связности в неориентированных и ориентированных графах. Алгоритм поиска компонент сильной связности. Вычисление выполняющего набора для 2-КНФ на основе поиска компонент сильной связности.
# '''9 апреля.''' Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры: формулировка, условия применимости, доказательство корректности, оценка сложности. Формулировка алгоритма Беллмана – Форда для графов без циклов с отрицательным весом.
# '''12 апреля.''' Алгоритмы Беллмана – Форда и Флойда – Уоршелла как алгоритмы динамического программирования.
# '''16 апреля.''' Динамическое программирование: наибольшая общая подпоследовательность, разбиение абзаца на строки, задача о рюкзаке.
# '''19 апреля.''' Жадные алгоритмы: выбор максимального подмножества непересекающихся отрезков; составление плана работ с заданными продолжительностями и повременными штрафами за невыполнение, минимизирующего общий штраф; код Хаффмана.
# '''23 апреля.''' Матроиды: графовый матроид, матроид для последовательности задач. Жадный алгоритм на взвешенном матроиде: поиск минимального остовного дерева, составление расписания задач с минимальным штрафом.
# '''26 апреля.''' Минимальные остовные деревья. Алгоритмы Прима, Крускала, Борувки.
# '''30 апреля.''' ''Лекции не будет.''
# '''10 мая.''' Три подхода к амортизационному анализу: групповой анализ, банковский метод и метод потенциалов (на примере двоичного счетчика и очереди на основе двух стеков).
# '''14 мая.''' ''Письменная контрольная работа по апрельским темам.'' С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. Контрольная проходит в ауд. 317 (группы 172, 174, 175) и ауд. 622 (группы 176, 177 и 178).
# '''17 мая.''' Самоорганизующиеся списки: метод потенциалов для анализа онлайн-алгоритмов. Кучи Фибоначчи.
# '''21 мая.''' Система непересекающихся множеств.
# '''24 мая.''' Минимальный разрез, алгоритмы Каргера и Каргера – Штайна.
# '''28 мая.''' Максимальный поток, алгоритм Форда – Фалкерсона.
# '''31 мая.''' ''Лекции не будет.''

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

Задачи из апрельских домашних заданий можно сдавать после указанного ниже срока, но до конца 9 мая со штрафом 50%. Задачи из майских домашних заданий можно сдавать после указанного ниже срока, но до конца 9 июня со штрафом 50%.

# [https://official.contest.yandex.ru/contest/7940/problems/ Контест 7940] — до 8.04.2018 (22:00) 
# [https://official.contest.yandex.ru/contest/7993/problems/ Контест 7993] — до 15.04.2018 (23:59) 
# [https://official.contest.yandex.ru/contest/8053/problems/ Контест 8053] — до 22.04.2018 (23:59) 
# [https://official.contest.yandex.ru/contest/8116/problems/ Контест 8116] — до 30.04.2018 (9:00) 
# [https://official.contest.yandex.ru/contest/8224/problems/ Контест 8224] — до 23.05.2018 (9:00) 
# [https://official.contest.yandex.ru/contest/8256/problems/ Контест 8256] — до 30.05.2018 (9:00) 
# [https://official.contest.yandex.ru/contest/8329/problems/ Контест 8329] — до 9.06.2018 (9:00) 

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

[https://docs.google.com/spreadsheets/d/1gcmb6g2P6kZFF62CIDdTcbEmEfTnKSaAfI7x6zS7zwQ/edit?usp=sharing Оценки]

[[Алгоритмы_и_структуры_данных_на_ПМИ_2017/2018_(основной_поток)/Кр_критерии|Критерии оценок]]

Даты показа работ:

'''Задачи I варианта'''
# 24 мая, 11:50 - 12:30, ауд. 308
# 23 и 30 мая, 11:30 – 12:00, ауд. 311
# 31 мая 9.00 - 11.30, ауд. 605
#
#

'''Задачи II варианта'''
#
# 29 мая, 11:50 – 12:20, ауд. 313
# 31 мая, 9:00 – 11:50, ауд. 420
# 25 мая, 9:50 – 10:30, ауд. 432
# 6 июня, 9:30 – 12:00, ауд. 412

Алгоритмы и структуры данных на ПМИ 2017/2018 (основной поток)

2018-06-02T09:54:04Z

Sabramov: