Алгоритмы и структуры данных на ПМИ 2017/2018 (основной поток) — различия между версиями
Материал из Wiki - Факультет компьютерных наук
.obj (обсуждение | вклад) (→Лекции) |
.obj (обсуждение | вклад) (→Лекции) |
||
| Строка 2: | Строка 2: | ||
# '''2 апреля.''' Графы: определения и приложения. Представление графов: матрица смежности и списки смежности. Поиск в глубину (рекурсивная формулировка). Сложность поиска в глубину. Применение поиска в глубину: поиск компонент связности в неориентированном графе, топологическая сортировка. Поиск в ширину. Сложность поиска в ширину. Поиск кратчайших путей. | # '''2 апреля.''' Графы: определения и приложения. Представление графов: матрица смежности и списки смежности. Поиск в глубину (рекурсивная формулировка). Сложность поиска в глубину. Применение поиска в глубину: поиск компонент связности в неориентированном графе, топологическая сортировка. Поиск в ширину. Сложность поиска в ширину. Поиск кратчайших путей. | ||
| − | |||
# '''5 апреля.''' Компоненты связности в неориентированных и ориентированных графах. Алгоритм поиска компонент сильной связности. Вычисление выполняющего набора для 2-КНФ на основе поиска компонент сильной связности. | # '''5 апреля.''' Компоненты связности в неориентированных и ориентированных графах. Алгоритм поиска компонент сильной связности. Вычисление выполняющего набора для 2-КНФ на основе поиска компонент сильной связности. | ||
| + | # '''9 апреля.''' Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры: формулировка, условия применимости, доказательство корректности, оценка сложности. Формулировка алгоритма Беллмана–Форда для графов без циклов с отрицательным весом. | ||
= Домашние задания = | = Домашние задания = | ||
# [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/> | ||
Версия 14:42, 9 апреля 2018
Лекции
- 2 апреля. Графы: определения и приложения. Представление графов: матрица смежности и списки смежности. Поиск в глубину (рекурсивная формулировка). Сложность поиска в глубину. Применение поиска в глубину: поиск компонент связности в неориентированном графе, топологическая сортировка. Поиск в ширину. Сложность поиска в ширину. Поиск кратчайших путей.
- 5 апреля. Компоненты связности в неориентированных и ориентированных графах. Алгоритм поиска компонент сильной связности. Вычисление выполняющего набора для 2-КНФ на основе поиска компонент сильной связности.
- 9 апреля. Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры: формулировка, условия применимости, доказательство корректности, оценка сложности. Формулировка алгоритма Беллмана–Форда для графов без циклов с отрицательным весом.
Домашние задания
- Контест 7940 — до 8.04.2018 (22:00)
