Алгоритмы и структуры данных на ПМИ 2017/2018 (основной поток) — различия между версиями
.obj (обсуждение | вклад) (→Домашние задания) |
.obj (обсуждение | вклад) (→Оценки) |
||
(не показано 59 промежуточных версии 6 участников) | |||
Строка 3: | Строка 3: | ||
# '''2 апреля.''' Графы: определения и приложения. Представление графов: матрица смежности и списки смежности. Поиск в глубину (рекурсивная формулировка). Сложность поиска в глубину. Применение поиска в глубину: поиск компонент связности в неориентированном графе, топологическая сортировка. Поиск в ширину. Сложность поиска в ширину. Поиск кратчайших путей. | # '''2 апреля.''' Графы: определения и приложения. Представление графов: матрица смежности и списки смежности. Поиск в глубину (рекурсивная формулировка). Сложность поиска в глубину. Применение поиска в глубину: поиск компонент связности в неориентированном графе, топологическая сортировка. Поиск в ширину. Сложность поиска в ширину. Поиск кратчайших путей. | ||
# '''5 апреля.''' Компоненты связности в неориентированных и ориентированных графах. Алгоритм поиска компонент сильной связности. Вычисление выполняющего набора для 2-КНФ на основе поиска компонент сильной связности. | # '''5 апреля.''' Компоненты связности в неориентированных и ориентированных графах. Алгоритм поиска компонент сильной связности. Вычисление выполняющего набора для 2-КНФ на основе поиска компонент сильной связности. | ||
− | # '''9 апреля.''' Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры: формулировка, условия применимости, доказательство корректности, оценка сложности. Формулировка алгоритма | + | # '''9 апреля.''' Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры: формулировка, условия применимости, доказательство корректности, оценка сложности. Формулировка алгоритма Беллмана – Форда для графов без циклов с отрицательным весом. |
+ | # '''12 апреля.''' Алгоритмы Беллмана – Форда и Флойда – Уоршелла как алгоритмы динамического программирования. | ||
+ | # '''16 апреля.''' Динамическое программирование: наибольшая общая подпоследовательность, разбиение абзаца на строки, задача о рюкзаке. | ||
+ | # '''19 апреля.''' Жадные алгоритмы: выбор максимального подмножества непересекающихся отрезков; составление плана работ с заданными продолжительностями и повременными штрафами за невыполнение, минимизирующего общий штраф; код Хаффмана. | ||
+ | # '''23 апреля.''' Матроиды: графовый матроид, матроид для последовательности задач. Жадный алгоритм на взвешенном матроиде: поиск минимального остовного дерева, составление расписания задач с минимальным штрафом. | ||
+ | # '''26 апреля.''' Минимальные остовные деревья. Алгоритмы Прима, Крускала, Борувки. | ||
+ | # '''30 апреля.''' ''Лекции не будет.'' | ||
+ | # '''10 мая.''' Три подхода к амортизационному анализу: групповой анализ, банковский метод и метод потенциалов (на примере двоичного счетчика и очереди на основе двух стеков). | ||
+ | # '''14 мая.''' ''Письменная контрольная работа по апрельским темам.'' С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. Контрольная проходит в ауд. 317 (группы 172, 174, 175) и ауд. 622 (группы 176, 177 и 178). | ||
+ | # '''17 мая.''' Самоорганизующиеся списки: метод потенциалов для анализа онлайн-алгоритмов. Кучи Фибоначчи. | ||
+ | # '''21 мая.''' Система непересекающихся множеств. | ||
+ | # '''24 мая.''' Минимальный разрез, алгоритмы Каргера и Каргера – Штайна. | ||
+ | # '''28 мая.''' Максимальный поток, алгоритм Форда – Фалкерсона. | ||
+ | # '''31 мая.''' ''Лекции не будет.'' | ||
+ | # '''4 июня.''' Детерминированные и недетерминированные конечные автоматы, их эквивалентность. Регулярные языки. Регулярные операции. Замкнутость регулярных языков относительно регулярных операций. | ||
+ | # '''7 июня.''' Регулярные выражения. Эквивалентность регулярных выражений и конечных автоматов. Минимизация конечного автомата. Нерегулярные языки. Формулировка и применение леммы о накачке. | ||
+ | # '''11 июня.''' Доказательство леммы о накачке. Нерегулярный язык, удовлетворяющий условиям леммы о накачке. Теорема Майхилла — Нероуда. | ||
+ | # '''14 июня.''' Разбор [https://www.dropbox.com/s/9gd8o29w7rjgwot/algo-exam2017.pdf?dl=0 экзаменационных задач прошлого года]. | ||
= Домашние задания = | = Домашние задания = | ||
+ | |||
+ | Задачи из апрельских домашних заданий можно сдавать после указанного ниже срока, но до конца 9 мая со штрафом 50%. Задачи из майских домашних заданий можно сдавать после указанного ниже срока, но до конца 9 июня со штрафом 50%. | ||
# [https://official.contest.yandex.ru/contest/7940/problems/ Контест 7940] — до 8.04.2018 (22:00)<br/> | # [https://official.contest.yandex.ru/contest/7940/problems/ Контест 7940] — до 8.04.2018 (22:00)<br/> | ||
# [https://official.contest.yandex.ru/contest/7993/problems/ Контест 7993] — до 15.04.2018 (23:59)<br/> | # [https://official.contest.yandex.ru/contest/7993/problems/ Контест 7993] — до 15.04.2018 (23:59)<br/> | ||
+ | # [https://official.contest.yandex.ru/contest/8053/problems/ Контест 8053] — до 22.04.2018 (23:59)<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/8256/problems/ Контест 8256] — до 30.05.2018 (9:00)<br/> | ||
+ | # [https://official.contest.yandex.ru/contest/8329/problems/ Контест 8329] — до 12.06.2018 (23:59)<br/> | ||
+ | |||
+ | = Контрольная работа = | ||
+ | |||
+ | [[Алгоритмы_и_структуры_данных_на_ПМИ_2017/2018_(основной_поток)/Кр_критерии|Критерии оценок]] | ||
+ | |||
+ | Даты показа работ: | ||
+ | |||
+ | '''Задачи I варианта''' | ||
+ | # 24 мая, 11:50 - 12:30, ауд. 308 | ||
+ | # 23 и 30 мая, 11:30 – 12:00, ауд. 311 | ||
+ | # 31 мая 9.00 - 11.30, ауд. 605 | ||
+ | # | ||
+ | # | ||
+ | |||
+ | '''Задачи II варианта''' | ||
+ | # 8 июня, 9:50 - 11:20, ауд. 420 | ||
+ | # 29 мая, 11:50 – 12:20, ауд. 313 | ||
+ | # 31 мая, 9:00 – 11:50, ауд. 420 | ||
+ | # 25 мая, 9:50 – 10:30, ауд. 432 | ||
+ | # 6 июня, 9:30 – 12:00, ауд. 412 | ||
+ | |||
+ | =Экзамен= | ||
+ | Экзамен пройдет 26 июня в 10:30 – 13:30 в ауд. 317 (группы 172, 174, 175) и ауд. 509 (группы 176, 177 и 178). Экзамен — письменный. С собой на экзамен можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. | ||
+ | |||
+ | Показ работ — 28 июня в 10:30 – 11:50 в ауд. 205. | ||
+ | |||
+ | |||
+ | =Оценки= | ||
+ | |||
+ | '''Накопленная оценка''' = 0,4 * контрольная работа + 0,6 * домашние задания<br/> | ||
+ | '''Итоговая оценка''' = 0,4 * экзамен + 0,6 * накопленная оценка | ||
+ | |||
+ | Для [https://docs.google.com/document/d/1vY4Ews2JnT7KqwDNFtj1qQ6pUdOp7fPnb3h1LtlsAMU/edit?usp=sharing тех, кто пропустил контрольную работу по уважительной причине]: | ||
+ | |||
+ | '''Накопленная оценка''' = домашние задания<br/> | ||
+ | '''Итоговая оценка''' = 0,64 * экзамен + 0,36 * накопленная оценка | ||
+ | |||
+ | [https://docs.google.com/spreadsheets/d/1gcmb6g2P6kZFF62CIDdTcbEmEfTnKSaAfI7x6zS7zwQ Текущие оценки] |
Текущая версия на 18:37, 20 июня 2018
Лекции
- 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 мая. Лекции не будет.
- 4 июня. Детерминированные и недетерминированные конечные автоматы, их эквивалентность. Регулярные языки. Регулярные операции. Замкнутость регулярных языков относительно регулярных операций.
- 7 июня. Регулярные выражения. Эквивалентность регулярных выражений и конечных автоматов. Минимизация конечного автомата. Нерегулярные языки. Формулировка и применение леммы о накачке.
- 11 июня. Доказательство леммы о накачке. Нерегулярный язык, удовлетворяющий условиям леммы о накачке. Теорема Майхилла — Нероуда.
- 14 июня. Разбор экзаменационных задач прошлого года.
Домашние задания
Задачи из апрельских домашних заданий можно сдавать после указанного ниже срока, но до конца 9 мая со штрафом 50%. Задачи из майских домашних заданий можно сдавать после указанного ниже срока, но до конца 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)
- Контест 8256 — до 30.05.2018 (9:00)
- Контест 8329 — до 12.06.2018 (23:59)
Контрольная работа
Даты показа работ:
Задачи I варианта
- 24 мая, 11:50 - 12:30, ауд. 308
- 23 и 30 мая, 11:30 – 12:00, ауд. 311
- 31 мая 9.00 - 11.30, ауд. 605
Задачи II варианта
- 8 июня, 9:50 - 11:20, ауд. 420
- 29 мая, 11:50 – 12:20, ауд. 313
- 31 мая, 9:00 – 11:50, ауд. 420
- 25 мая, 9:50 – 10:30, ауд. 432
- 6 июня, 9:30 – 12:00, ауд. 412
Экзамен
Экзамен пройдет 26 июня в 10:30 – 13:30 в ауд. 317 (группы 172, 174, 175) и ауд. 509 (группы 176, 177 и 178). Экзамен — письменный. С собой на экзамен можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается.
Показ работ — 28 июня в 10:30 – 11:50 в ауд. 205.
Оценки
Накопленная оценка = 0,4 * контрольная работа + 0,6 * домашние задания
Итоговая оценка = 0,4 * экзамен + 0,6 * накопленная оценка
Для тех, кто пропустил контрольную работу по уважительной причине:
Накопленная оценка = домашние задания
Итоговая оценка = 0,64 * экзамен + 0,36 * накопленная оценка