3. Использование гомоморфной свертки для упрощения процесса исследования структуры алгоритма

Гомоморфная свертка помогает упрощению процесса исследования структуры алгоритма. Это хорошо иллюстрируется следующим примером. Предположим, что исследуется параллельная структура алгоритма, заданного программой на некотором алгоритмическом языке. Чтобы решить эту задачу, нужно построить граф алгоритма. Первое, что приходится делать, это ответить на вопрос о том, каким операциям алгоритма должны соответствовать вершины графа. Если операциями считать отдельные операторы, то граф будет отражать алгоритм наиболее детально. Поэтому в данном случае при переходе к графу не будет никаких потерь в информации о структуре алгоритма.

Однако, излишняя подробность представления может привести к затруднениям как в процессе построения, так и в процессе исследования графа. Естественным выходом из этого положения является использование более крупных операций. Ими могут быть линейные участки программы, отдельные ее фрагменты, подпрограммы и т.д. Алгоритм, представленный в терминах подобных операций, даст более простой граф. Этот граф принято называть макрографом. Конечно в макрографе будет потеряна некоторая информация о структуре. Однако часто информация, полученная о параллельной структуре макрографа, может оказаться достаточной. Кроме того, всегда можно перейти от макрографа к детальному графу, представим вместо макровершин графы соответствующих им операций. То, что мы описали в связи с выбором операций, есть в действительности использование гомоморфной свертки. В графе, вершины которого соответствуют отдельным операторам, крупные операции описываются некоторыми подграфами. Из этого графа макрограф может быть получен с помощью простой гомоморфной свертки каждого из подграфов в одну вершину. Операция простого гомоморфизма ассоциативна. Поэтому для получения макрографа безразлично, в какой момент осуществлять простую гомоморфную свертку подграфов. В том числе, это можно сделать до построения всего графа, что и соответствует предварительному выбору крупных операций. Согласно сказанному выше, любая топологическая сортировка макрографа алгоритма порождает обобщенную топологическую сортировку детального графа алгоритма.

Как топологическая, так и обобщенная топологическая сортировки задаются только разбиением вершин графа алгоритма на группы и упорядочиванием самих групп. Несмотря на большое значение этих сортировок в исследовании структуры алгоритмов, они не заменяют графа алгоритма. В графе алгоритма содержится исключительно важная информация, связанная с дугами и показывающая, как именно осуществляется обмен данными между вершинами. Этой информации в топологических сортировках нет. Поэтому топологические и обобщенные топологические сортировки являются предметом исследований лишь настолько, насколько они помогают изучению структуры графов алгоритмов.

Вопросы

1. Какая операция над графом называется операцией элементарного гомоморфизма?

2. К каким последствиям в ациклическом графе может привести операция элементарного гомоморфизма?

3. Какая операция над графом называется простым элементарным гомоморфизмом, кратным элементарным гомоморфизмом?

4. Что называется гомоморфной сверткой графа, простой (кратной) гомоморфной сверткой?

5. Какие два графа называются гомоморфными?

6. Что такое гомоморфный образ, прообраз графа?

7. Как связаны между собой топологические сортировки графа и его гомоморфной свертки?

8. Каким образом гомоморфная свертка помогает упрощению процесса исследования структуры алгоритма?

Литература

7. Воеводин В.В. Параллельные вычисления / В.В.Воеводин, Вл.В.Воеводин. — СПб.: БХВ-Петербург, 2002. — 608 с.

8. Харари Ф. Теория графов / Ф.Харари; пер.с англ. В.П.Козырева. — М.: Мир, 1973. — 300 с.

9. Уилсон Р. Введение в теорию графов / Р.Уилсон. — М.: Мир, 1977. — 207 с.

10. Кристофидес Н. Теория графов. Алгоритмический подход / Н.Кристофидес. — М.: Мир, 1978. — 432 с.

11. Новиков Ф.А. Дискретная математика для программистов / Ф.А.Новиков. — СПб.: Питер, 2006. — 364 с.

12. Иванов Б.Н. Дискретная математика. Алгоритмы и программы / Б.Н.Иванов. — М.: Лаборатория Базовых Знаний, 2001. — 288с.