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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Домашние задания)
(Домашние задания)
Строка 10: Строка 10:
 
# [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/7993/problems/ Контест 8053] — до 22.04.2018 (23:59)<br/>
+
# [https://official.contest.yandex.ru/contest/8053/problems/ Контест 8053] — до 22.04.2018 (23:59)<br/>

Версия 10:58, 16 апреля 2018

Лекции

  1. 2 апреля. Графы: определения и приложения. Представление графов: матрица смежности и списки смежности. Поиск в глубину (рекурсивная формулировка). Сложность поиска в глубину. Применение поиска в глубину: поиск компонент связности в неориентированном графе, топологическая сортировка. Поиск в ширину. Сложность поиска в ширину. Поиск кратчайших путей.
  2. 5 апреля. Компоненты связности в неориентированных и ориентированных графах. Алгоритм поиска компонент сильной связности. Вычисление выполняющего набора для 2-КНФ на основе поиска компонент сильной связности.
  3. 9 апреля. Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры: формулировка, условия применимости, доказательство корректности, оценка сложности. Формулировка алгоритма Беллмана – Форда для графов без циклов с отрицательным весом.
  4. 12 апреля. Алгоритмы Беллмана – Форда и Флойда – Уоршелла как алгоритмы динамического программирования.

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

  1. Контест 7940 — до 8.04.2018 (22:00)
  2. Контест 7993 — до 15.04.2018 (23:59)
  3. Контест 8053 — до 22.04.2018 (23:59)