Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Национальный исследовательский институт

Московский Энергетический Институт (Технический Университет)

Институт автоматики и вычислительной техники

Кафедра Прикладной математики

Лабораторная работа №4

по дисциплине «Параллельные системы и параллельное программирование»

тема: «Поиск минимального оставного дерева с использованием нитевого распараллеливания.»

Выполнил:

Машеров Д.Е.

А-13-08

Москва

2012 г.

Постановка задачи

Дана граф, требуется найти минимальное оставное дерева этого графа.

Охватывающим деревом (или остовом ) неориентированного графа G называется подграф T графа G, который является деревом и содержит все вершины из G. Определив вес подграфа для взвешенного графа как сумму весов входящих в подграф дуг, под минимально охватывающим деревом (МОД) T понимается охватывающее дерево минимального веса.

Последовательный алгоритм.

Используется алгоритм Прима.

Алгоритм начинает работу с произвольной вершины графа, выбираемой в качестве корня дерева, и в ходе последовательно выполняемых итераций расширяет конструируемое дерево до МОД. Пусть есть множество вершин, уже включенных алгоритмом в МОД, а величины , 1<= <=n, характеризуют дуги минимальной длины от вершин, еще не включенных в дерево, до множества , т.е.

(если для какой-либо вершины не существует ни одной дуги в , значение устанавливается равным ). В начале работы алгоритма выбирается корневая вершина МОД s и полагается ={s}, =0.

Действия, выполняемые на каждой итерации алгоритма Прима, состоят в следующем:

• определяются значения величин di для всех вершин, еще не включенных в состав МОД;

• выбирается вершина t графа G, имеющая дугу минимального веса до множества ;

• вершина t включается в .

После выполнения n-1 итерации метода МОД будет сформировано. Вес этого дерева может быть получен при помощи выражения

Параллельный алгоритм.

Итерации метода должны выполняться последовательно и, тем самым, не могут быть распараллелены. С другой стороны, выполняемые на каждой итерации алгоритма действия являются независимыми и могут реализовываться одновременно.

Каждому потоку сопоставляется свой набор вершин графа.

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

Результаты вычислительного эксперимента

1. Количество вершин графа: 5 000

1. Количество вершин графа: 10 000

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лабораторной работы