Теория и практика параллельных вычислений

         

Контрольные вопросы


  1. Приведите определение графа. Какие основные способы используются для задания графов?
  2. В чем состоит задача поиска всех кратчайших путей?
  3. Приведите общую схему алгоритма Флойда. Какова трудоемкость алгоритма?
  4. В чем состоит способ распараллеливания алгоритма Флойда?
  5. В чем заключается задача нахождения минимального охватывающего дерева? Приведите пример использования задачи на практике.
  6. Приведите общую схему алгоритма Прима. Какова трудоемкость алгоритма?
  7. В чем состоит способ распараллеливания алгоритма Прима?
  8. В чем отличие геометрических и комбинаторных методов разделения графа? Какие методы являются более предпочтительными? Почему?
  9. Приведите описание метода покоординатного разбиения и алгоритма разделения с учетом связности. Какой из этих методов является более простым для реализации?



Содержание раздела