https://wiki.cs.hse.ru/api.php?action=feedcontributions&feedformat=atom&user=MlevkovWiki - Факультет компьютерных наук - Вклад [ru]2026-09-27T02:33:05ZВкладMediaWiki 1.43.9https://wiki.cs.hse.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D0%BD%D0%B0_%D0%9F%D0%9C%D0%98_2017/2018_(%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%BE%D0%B9_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA)&diff=28030Алгоритмы и структуры данных на ПМИ 2017/2018 (основной поток)2018-05-31T05:43:45Z<p>Mlevkov: /* Контрольная работа */</p>
<hr />
<div>= Лекции =<br />
<br />
# '''2 апреля.''' Графы: определения и приложения. Представление графов: матрица смежности и списки смежности. Поиск в глубину (рекурсивная формулировка). Сложность поиска в глубину. Применение поиска в глубину: поиск компонент связности в неориентированном графе, топологическая сортировка. Поиск в ширину. Сложность поиска в ширину. Поиск кратчайших путей.<br />
# '''5 апреля.''' Компоненты связности в неориентированных и ориентированных графах. Алгоритм поиска компонент сильной связности. Вычисление выполняющего набора для 2-КНФ на основе поиска компонент сильной связности.<br />
# '''9 апреля.''' Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры: формулировка, условия применимости, доказательство корректности, оценка сложности. Формулировка алгоритма Беллмана – Форда для графов без циклов с отрицательным весом.<br />
# '''12 апреля.''' Алгоритмы Беллмана – Форда и Флойда – Уоршелла как алгоритмы динамического программирования.<br />
# '''16 апреля.''' Динамическое программирование: наибольшая общая подпоследовательность, разбиение абзаца на строки, задача о рюкзаке.<br />
# '''19 апреля.''' Жадные алгоритмы: выбор максимального подмножества непересекающихся отрезков; составление плана работ с заданными продолжительностями и повременными штрафами за невыполнение, минимизирующего общий штраф; код Хаффмана.<br />
# '''23 апреля.''' Матроиды: графовый матроид, матроид для последовательности задач. Жадный алгоритм на взвешенном матроиде: поиск минимального остовного дерева, составление расписания задач с минимальным штрафом.<br />
# '''26 апреля.''' Минимальные остовные деревья. Алгоритмы Прима, Крускала, Борувки.<br />
# '''30 апреля.''' ''Лекции не будет.''<br />
# '''10 мая.''' Три подхода к амортизационному анализу: групповой анализ, банковский метод и метод потенциалов (на примере двоичного счетчика и очереди на основе двух стеков).<br />
# '''14 мая.''' ''Письменная контрольная работа по апрельским темам.'' С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. Контрольная проходит в ауд. 317 (группы 172, 174, 175) и ауд. 622 (группы 176, 177 и 178).<br />
# '''17 мая.''' Самоорганизующиеся списки: метод потенциалов для анализа онлайн-алгоритмов. Кучи Фибоначчи.<br />
# '''21 мая.''' Система непересекающихся множеств.<br />
# '''24 мая.''' Минимальный разрез, алгоритмы Каргера и Каргера – Штайна.<br />
# '''28 мая.''' Максимальный поток, алгоритм Форда – Фалкерсона.<br />
# '''31 мая.''' ''Лекции не будет.''<br />
<br />
= Домашние задания =<br />
<br />
Задачи из апрельских домашних заданий можно сдавать после указанного ниже срока, но до конца 9 мая со штрафом 50%. Задачи из майских домашних заданий можно сдавать после указанного ниже срока, но до конца 9 июня со штрафом 50%.<br />
<br />
# [https://official.contest.yandex.ru/contest/7940/problems/ Контест 7940] — до 8.04.2018 (22:00)<br/><br />
# [https://official.contest.yandex.ru/contest/7993/problems/ Контест 7993] — до 15.04.2018 (23:59)<br/><br />
# [https://official.contest.yandex.ru/contest/8053/problems/ Контест 8053] — до 22.04.2018 (23:59)<br/><br />
# [https://official.contest.yandex.ru/contest/8116/problems/ Контест 8116] — до 30.04.2018 (9:00)<br/><br />
# [https://official.contest.yandex.ru/contest/8224/problems/ Контест 8224] — до 23.05.2018 (9:00)<br/><br />
# [https://official.contest.yandex.ru/contest/8256/problems/ Контест 8256] — до 30.05.2018 (9:00)<br/><br />
# [https://official.contest.yandex.ru/contest/8329/problems/ Контест 8329] — до 9.06.2018 (9:00)<br/><br />
<br />
= Контрольная работа =<br />
<br />
[https://docs.google.com/spreadsheets/d/1gcmb6g2P6kZFF62CIDdTcbEmEfTnKSaAfI7x6zS7zwQ/edit?usp=sharing Оценки] <br />
<br />
[[Алгоритмы_и_структуры_данных_на_ПМИ_2017/2018_(основной_поток)/Кр_критерии|Критерии оценок]]<br />
<br />
Даты показа работ:<br />
<br />
'''Задачи I варианта'''<br />
# 24 мая, 11:50 - 12:30, ауд. 308<br />
# 23 и 30 мая, 11:30 – 12:00, ауд. 311<br />
# 31 мая 9.00 - 11.30, ауд. 605<br />
#<br />
# <br />
<br />
'''Задачи II варианта'''<br />
#<br />
# 29 мая, 11:50 – 12:20, ауд. 313<br />
# 31 мая, 9:00 – 11:50, ауд. 420<br />
# 25 мая, 9:50 – 10:30, ауд. 432<br />
#</div>Mlevkovhttps://wiki.cs.hse.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D0%BD%D0%B0_%D0%9F%D0%9C%D0%98_2017/2018_(%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%BE%D0%B9_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA)&diff=28013Алгоритмы и структуры данных на ПМИ 2017/2018 (основной поток)2018-05-30T10:37:15Z<p>Mlevkov: </p>
<hr />
<div>= Лекции =<br />
<br />
# '''2 апреля.''' Графы: определения и приложения. Представление графов: матрица смежности и списки смежности. Поиск в глубину (рекурсивная формулировка). Сложность поиска в глубину. Применение поиска в глубину: поиск компонент связности в неориентированном графе, топологическая сортировка. Поиск в ширину. Сложность поиска в ширину. Поиск кратчайших путей.<br />
# '''5 апреля.''' Компоненты связности в неориентированных и ориентированных графах. Алгоритм поиска компонент сильной связности. Вычисление выполняющего набора для 2-КНФ на основе поиска компонент сильной связности.<br />
# '''9 апреля.''' Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры: формулировка, условия применимости, доказательство корректности, оценка сложности. Формулировка алгоритма Беллмана – Форда для графов без циклов с отрицательным весом.<br />
# '''12 апреля.''' Алгоритмы Беллмана – Форда и Флойда – Уоршелла как алгоритмы динамического программирования.<br />
# '''16 апреля.''' Динамическое программирование: наибольшая общая подпоследовательность, разбиение абзаца на строки, задача о рюкзаке.<br />
# '''19 апреля.''' Жадные алгоритмы: выбор максимального подмножества непересекающихся отрезков; составление плана работ с заданными продолжительностями и повременными штрафами за невыполнение, минимизирующего общий штраф; код Хаффмана.<br />
# '''23 апреля.''' Матроиды: графовый матроид, матроид для последовательности задач. Жадный алгоритм на взвешенном матроиде: поиск минимального остовного дерева, составление расписания задач с минимальным штрафом.<br />
# '''26 апреля.''' Минимальные остовные деревья. Алгоритмы Прима, Крускала, Борувки.<br />
# '''30 апреля.''' ''Лекции не будет.''<br />
# '''10 мая.''' Три подхода к амортизационному анализу: групповой анализ, банковский метод и метод потенциалов (на примере двоичного счетчика и очереди на основе двух стеков).<br />
# '''14 мая.''' ''Письменная контрольная работа по апрельским темам.'' С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. Контрольная проходит в ауд. 317 (группы 172, 174, 175) и ауд. 622 (группы 176, 177 и 178).<br />
# '''17 мая.''' Самоорганизующиеся списки: метод потенциалов для анализа онлайн-алгоритмов. Кучи Фибоначчи.<br />
# '''21 мая.''' Система непересекающихся множеств.<br />
# '''24 мая.''' Минимальный разрез, алгоритмы Каргера и Каргера – Штайна.<br />
# '''28 мая.''' Максимальный поток, алгоритм Форда – Фалкерсона.<br />
<br />
= Домашние задания =<br />
<br />
Задачи из апрельских домашних заданий можно сдавать после указанного ниже срока, но до конца 9 мая со штрафом 50%. Задачи из майских домашних заданий можно сдавать после указанного ниже срока, но до конца 9 июня со штрафом 50%.<br />
<br />
# [https://official.contest.yandex.ru/contest/7940/problems/ Контест 7940] — до 8.04.2018 (22:00)<br/><br />
# [https://official.contest.yandex.ru/contest/7993/problems/ Контест 7993] — до 15.04.2018 (23:59)<br/><br />
# [https://official.contest.yandex.ru/contest/8053/problems/ Контест 8053] — до 22.04.2018 (23:59)<br/><br />
# [https://official.contest.yandex.ru/contest/8116/problems/ Контест 8116] — до 30.04.2018 (9:00)<br/><br />
# [https://official.contest.yandex.ru/contest/8224/problems/ Контест 8224] — до 23.05.2018 (9:00)<br/><br />
# [https://official.contest.yandex.ru/contest/8256/problems/ Контест 8256] — до 30.05.2018 (9:00)<br/><br />
<br />
= Контрольная работа =<br />
<br />
[https://docs.google.com/spreadsheets/d/1gcmb6g2P6kZFF62CIDdTcbEmEfTnKSaAfI7x6zS7zwQ/edit?usp=sharing Оценки] <br />
<br />
Показ работ пройдет в следующие даты:<br />
<br />
'''Задачи I варианта'''<br />
# 24 мая, 11:50 - 12:30, ауд. 308<br />
# 23 и 30 мая, 11:30 – 12:00, ауд. 311<br />
# 31 мая 9.00 - 11.30, ауд. 507<br />
#<br />
#<br />
<br />
'''Задачи II варианта'''<br />
#<br />
# 29 мая, 11:50 – 12:20, ауд. 313<br />
#<br />
# 25 мая, 9:50 – 10:30, ауд. 432<br />
#</div>Mlevkov