2006 Ответы на экзаменационные вопросы по ПОД (Lilalbrother), страница 16
Описание файла
PDF-файл из архива "2006 Ответы на экзаменационные вопросы по ПОД (Lilalbrother)", который расположен в категории "". Всё это находится в предмете "суперкомпьютерное моделирование и технологии" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 16 страницы из PDF
Так как при каждом шаге помечается не менее однойвершины, то число различных индексов не превышает числа вершин графа.Отсюда следует, что никакие две вершины с одним и тем же индексом не связаныдугой. Минимальное число индексов, которым можно пометить все вершины графа, на 1больше длины его критического пути. И, наконец, для любого целого числа s, непревосходящего общего числа вершин, но большего длины критического пути,существует такая разметка вершин графа, при которой используются все s индексов.Граф, размеченный в соответствии с утверждением 4.1, называется строгойпараллельной формой графа. Если в параллельной форме некоторая вершина помеченаиндексом k, то это означает, что длины всех путей, оканчивающихся в данной вершине,меньше к.
Существует строгая параллельная форма, при которой максимальная из длинпутей, оканчивающихся в вершине с индексом k, равна k-1. Для этой параллельной формычисло используемых индексов на 1 больше длины критического пути графа. Средиподобных параллельных форм существует такая, в которой все входные вершины находятся в группе с одним индексом, равным 1.
Эта строгая параллельная форма называетсяканонической. Для заданного графа его каноническая параллельная форма единственна.Группа вершин, имеющих одинаковые индексы, называется ярусом параллельной формы,а число вершин в группе — шириной яруса. Число ярусов в параллельной форменазывается высотой параллельной формы, а максимальная ширина ярусов — еешириной.
Параллельная форма минимальной высоты называется максимальной.48. Зависимость степени параллелизма от формы записи алгоритма (на примеререализации метода Гаусса)..