Параллельные алгоритмы поиска кратчайших путей на графе (7 неделя)
Дисциплина «Технологии программирования, алгоритмы и структуры данных» (2-й семестр)Структуры данных и алгоритмы их обработки. Темы докладов и план семинара «Технологии программирования, алгоритмы и структуры данных» (2-й семестр).Осенний семестр 2018/19 уч. года.
Введение в параллельные вычисления: платформы с распределённой и общей памятью (1 неделя).
1.1. Особенности использования распределенной памяти, синхронизация с помощью сообщения. Режимы доступа к общей памяти. Анализ простейших операций на общей памяти.
1.2. Организация семинара: обзор плана семинаров, используемые информационные ресурсы, темы БДЗ и распределение докладов.
1.3.Домашнее задание (самостоятельно)1: Медиана в наборе чисел — это такое значение, что половина из чисел набора меньше, а другая больше него. Другими словами, если бы значения в списке были отсортированы, то медиана занимала бы в нем в точности среднее положение. Разработайте параллельный алгоритм поиска медианы в модели CREW PRAM. Как быстро работает Ваш алгоритм и какова его стоимость?
1.4. Домашнее задание (самостоятельно)2: Разработайте параллельный алгоритм поиска медианы в модели CRCW PRAM (определение медианы см. в задании 1.3). Каков механизм разрешения конфликтов при записи. Насколько быстро работает Ваш алгоритм, и какова его стоимость?
Параллельные алгоритмы на общей памяти (2 неделя) .
2.1. Параллельный поиск на общей памяти. Макконелл Дж.(2004),208.. 212.
|
|
|
2.2. Параллельные сортировки на общей памяти. Макконелл Дж.(2004), с. 212 .. 218.
2.3. Домашнее задание (самостоятельно)3: в обсуждавшихся выше алгоритмах поиска предполагалось, что в списке нет дубликатов. Если же это не так и искомое значение встречается в списке несколько раз, то обычно принято возвращать номер его первого появления. Какие изменения следует произвести в обоих алгоритмах поиска в модели CREW PRAM, чтобы обеспечить обработку списков с дубликатами? 2) Разработайте параллельный алгоритм поиска в списке с дубликатами в модели CRCW PRAM. Если искомое значение встречается несколько раз, то обычно принято возвращать номер его первого появления. Обратите особое внимание на механизм разрешения конфликтов при записи. Насколько быстро работает Ваш алгоритм и какова его эффективность?
2.4. Домашнее задание (самостоятельно)4: Раздел 7.5.3 и упражнение 7.5.4.1 (Макконелл Дж. (2004), с. 218 см. конец текста «2.2. Параллельные сортировки на общей памяти. Макконелл Дж.(2004), с. 212 .. 218»).
Алгоритмы на графах - 1 (3 неделя) .
3.1. Представление графов в программах (Примеры всех вариантов представление графов). Обходы графов (согласно указаниям привести трассировочную таблицу обхода вершин графа «в глубину»). Новиков Ф. А. (2009) с. 255..260.
|
|
|
3.2. Компоненты связности и сильной связности. Выделение компонент сильной связности. Ахо А.(2003) с. 203..205.
3.3. Домашнее задание 5(самостоятельно): Используя в качестве базового алгоритма «Обход вершин в глубину» разработать алгоритм «Выделение компонентов связности» и выполнить его моделирование (см. указания 3.3).
3.4. Домашнее задание 6(самостоятельно): выполнить моделирование алгоритма выделения компонент сильной связности для заданного примера (см. указания 3.4).
Алгоритмы на графах - 2 (4 неделя) .
4.1. Построение остовных деревьев минимальной стоимости. Алгоритм Прима. Новиков Ф. А. (2009) с. 327..328, 330..331.
4.2. Построение остовных деревьев минимальной стоимости. Алгоритм Крускала. Новиков Ф. А. (2009) с. 327.. 330.
4.3. Домашнее задание 7 (Индивидуальное): Моделирование построения минимального остова с использованием алгоритмов Прима и Крускала. Задания и указания к выполнению будут выданы на семинаре.
Параллельные алгоритмы построения остовных деревьев минимальной стоимости (5 неделя) .
5.1. Экспериментальная и теоретическая оценки параллельных алгоритмов нахождения мимнимального остовного дерева на кластерных системах. Аль – Хулайди А.А., Чернышев Ю.О. (). С. 80-88.
|
|
|
5.2. Параллельный алгоритм построения минимального эвклидова дерева в задаче классификации объектов на изображениях для GPU. Барсук А.А., Иванов О.В. (2011) с. 107-114.
Алгоритмы на графах – 3. Нахождение кратчайших путей (6 неделя) .
6.1. Нахождение кратчайших путей от выделенной вершины до всех остальных вершин графа (алгоритм Дейкстры). Новиков Ф. А. (2009) с. 284, 286..290.
6.2. Поиск кратчайших путей в графах между всеми парами вершин (алгоритм Флойда). Новиков Ф. А. (2009) с. 284..286 .
6.3. Домашнее задание 8 (Индивидуальное): Моделирование алгоритмов Дейкстры и Флойда (см. указания к оформлению 6.3, 6.4).
Параллельные алгоритмы поиска кратчайших путей на графе (7 неделя)
7.1. Алгоритм Дейкстры. Библиотека параллельных алгоритмов ParaLib. Руководство пользователя (2004) с. 19-23.
7.2 Алгоритм Флойда. Гергель В. П.(2007), с. 301-310.
7.3. Домашнее задание 9: Повторить конструктивное перечисление разбиений множеств ТМП-1, осенний семестр).
Дата добавления: 2019-01-14; просмотров: 351; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!