Структуры данных и алгоритмы, группы М3305 - М3308

Весенний семестр, 2016-2017

Таблица результатов

Преподаватели

• Вторник, чет. неделя, 13-30, ауд. 151 — Практика М3305
• Вторник, нечет. неделя, 13-30, ауд. 239 — Практика М3306

• Вторник, чет. неделя, 13-30, ауд. 556 — Практика М3307

• Вторник, нечет. неделя, 13-30, ауд. 556 — Практика М3308

• Вторник, чет. неделя, 11-40, ауд. 332 — Лекция

Лабораторные работы

• Как сдавать задачи
• Лабораторная 1
• Лабораторная 2

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

• В случаях, когда источник не указан, подразумевается Кормен, Лейзерсон и др. "Алгоритмы. Построение и анализ" (второе издание).
• Лекция 1. Графы: основные определения. Поиск в ширину.
  • Упражнения с 22.1-1 по 22.1-7.
  • Лемма 22.1, 22.2
  • Лемма 22.3, следствие 22.4.
  • Теорема 22.5.
  • Упраженения 22.2-1, 22.2-6.
• Лекция 2. Поиск в глубину. Топологическая сортировка. Компоненты сильной связности.
  • Теорема 22.7 + следствие 22.8.
  • Теорема 22.9.
  • Доказательство корректности алгоритма поиска компонент сильной связности (стр. 636-640).
  • Упражнения 22.3-1, 22.3-2.
  • Упражнения 22.3-7, 22.3-8.
  • Упражнения 22.4-1, 22.4-2.
  • Упражнения 22.4-3 (для неориентированного графа).
  • Упражнения 22.5-1, 22.5-3.
• Лекция 3. Минимальное остовное дерево. Алгоритм Прима.
  • Теорема 23.1 (стр. 647).
  • Доказательство выполнения инварианта цикла в алгоритме Прима (стр. 655).
  • Упражнения 23.1-2, 23.1-4, 23.1-7.
• Лекция 4. Алгоритмы поиска кратчайших путей в графах.
  • Свойства кратчайших путей (с доказательствами, стр. 671, стр. 694).
  • Теорема 24.4 (корректность алгоритма Беллмана-Форда, стр. 674).
  • Теорема 24.6 (корректность алгоритма Дейкстры, стр. 681).
  • Привести пример, в котором алгоритм Дейкстры некорректно работает на графе с отрицательными весами.
  • Упражнения 24.1-1, 24.2-1, 24.3-1, 24.3-3, 24.3-8, 25.2-1.
  • Разработка алгоритма Флойда-Воршалла (стр. 718-720).
  • Рассказать, как работает алгоритм Джонсона (стр. 726-730).
• Лекция 5. Задача о максимальном потоке.
  • Лемма 26.2, лемма 26.3, теорема 26.7.
  • Привести пример транспортной сети, на которой достигается верхняя оценка времени работы алгоритма Форда-Фалкерсона (стр. 752).
  • Лемма 26.8, теорема 26.9 (время работы алгоритма Эдмондса-Карпа).
  • Упражнения 26.1-6, 26.2-4, 26.1-7.
  • Как решать задачу поиска максимального потока в транспортной сети с несколькими источниками и стоками? (стр. 739)
• Лекция 6. Поиск подстрок.
  • Проанализировать время работы Compute_Transition_Function (стр 1035).
  • Доказать лемму 32.2.
  • Доказать лемму 32.3.
  • Доказать теорему 32.4.
  • Построить автомат для P=aabab.
  • Продемонстрировать работу автомата из предыдущего задания при поиске подстроки P в тексте T=aaababaabaabab.
  • Построить автомат для поиска строки P=abab.