Вход на персональную страничку (9 "В" класс, 2007-08, contest 3 - Графы-II)

Внимание! Для входа на страничку нужно использовать новые логины и пароли, которые можно получить у В.А.М., например, по e-mail

11 и 19 января 2008. Алгоритм Дейкстры

• Задача A. Реализация вспомогательной функции
• Задача B. "Дейкстра" (включает описание алгоритма Дейкстры)
• Задача C. "Заправки"
• Задача D. "Автобусы"
• Задача E. "Заправки-2"
• Задача F. "Домой на электричках"

26 января 2008. Алгоритм Форда-Белмана

• Описание алгоритма Форда-Белмана
• Задача G. Алгоритм Форда-Белмана
• Задача H. Лабиринт знаний

2 февраля 2008. Алгоритм Флойда

• Задача I. Матрица кратчайших расстояний
• Задача J. Две наиболее удаленные вершины
• Задача K. Существование путей

9 февраля 2008. Восстановление пути

• Задача L. Восстановление пути - 1
• Задача M. Восстановление пути - 2
• Задача N. Восстановление пути - 3^* (дополнительная задача)

9 февраля 2008. Деревья - знакомство (домашнее задание)

• Задача O. Дерево?
• Задача P. Получи дерево

16 февраля 2008. Остовные деревья

• Теория: Алгоритмы построения минимального остова: алгоритм Прима и алгоритм Краскала
• Задача Q. Разминка перед алгоритмом Прима
• Задача R. Минимальный каркас
• Задача S. Разминка перед алгоритмом Краскала
• В этом месте полезно еще раз решить задачу R, но на сей раз пользуясь алгоритмом Краскала
• Задача T. Грузовик^*

Список вопросов к зачету

• Способы представления графов: матрица смежности, список ребер и граф, заданный неявно
• Алгоритм Дейкстры
• Алгоритм Форда-Белмана
• Алгоритм Флойда
• Дополнительные вопросы по алгоритмам поиска кратчайших путей:
  • Область применения каждого алгоритма и решаемая им задача.
  • Обоснование каждого алгоритма.
  • С каким спобом представления графа (матрица смежности, список ребер) данный алгоритм работает
  • Что такое "бесконечность", как и зачем ей пользуются
  • Пример графа с отрицательными ребрами, на котором алгоритм Дейкстры дает неверный ответ
  • Оценка сложности (числа выполняемых операций) алгоритма^*
• Восстановление кратчайшего пути по вычисленным длинам путей
• Определение дерева. Свойства деревьев
• Построение минимального каркаса: алгоритм Прима
• Построение минимального каркаса: алгоритм Краскала