ВВЕДЕНИЕ 3
ПОСТАНОВКА И РЕАЛИЗАЦИЯ СТАНДАРТНОГО И ПАРАЛЛЕЛЬНОГО АЛГОРИТМОВ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ 6
1.1. Формулировка транспортной задачи 6
1.2. Математическая модель транспортной задачи 7
1.3. Метод решения транспортной задачи. 8
1.4 Алгоритмы решения транспортной задачи 13
1.5 Пример параллельного метода решения транспортной задачи 42
2. ВЕНГЕРСКИЙ АЛГОРИТМ.РЕШЕНИЕ ЗАДАЧ О НАЗНАЧЕНИЯХ 64
2.1. Венгерский алгоритм. Решение задач о назначениях 64
2.2 Параллельная реализация алгоритма. 66
3. РЕШЕНИЕ ГРАДИЕНТНЫХ ЗАДАЧ. 67
3.1 Метод градиентного спуска. 67
3.2 Параллельный метод градиентного спуска. 69
3.3 Решение систем линейных уравнений методом градиентного спуска. 71
3.4 Параллельный алгоритм нахождения решений систем уравнений методом наискорейшего спуска. 76
РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЙ 78
ЗАКЛЮЧЕНИЕ 85
СПИСОК ЛИТЕРАТУРЫ. 86
ПРИЛОЖЕНИЕ 87
Приведём классификацию многопроцессорных систем:
Векторно-конвейерные компьютеры. Они характеризуются наличием функциональных конвейерных устройств и набором векторных команд.
Массивно-параллельные компьютеры с распределенной памятью. Они представляют собой класс компьютеров, в которых соединение микропроцессоров осуществляется при помощи сетевого оборудования.
Параллельные компьютеры с общей памятью. На них вся оперативная память разделяется несколькими одинаковыми процессорами, обращающимися к общей дисковой памяти. При этом проблем с обменом данными между процессорами и синхронизацией их работы практически не возникает.
Кластерные компьютеры. Это класс, который представлен комбинацией предыдущих трёх классов.
Параллельные машины и параллельные вычисления создаются для ускорения решения задач большой размерности. При использовании свойств и методов конкретной задачи, существенно облегчается процесс её распараллеливания. Однако, не всегда распараллеленная задача будет иметь преимущество по скорости , относительно её обычного, непараллельного аналога. Как показывает практика, наиболее лучшим вариантом по эффективному решению задач служит комбинированный метод вычислений , который будет зависеть от входных данных конкретной задачи.
Наиболее распространённым методом распараллеливания является выделение наиболее часто повторяющейся операции. При этом , следует учитывать , с какими данными она будет производить операции, чтобы результат от этого не пострадал.
В данной работе описаны алгоритмы решения транспортной задачи( параллельный метод потенциалов и матричный способ) , венгерский алгоритм ( решение задачи о назначениях , параллельная и стандартная реализации) , метод решения систем линейных алгебраических уравнений (стандартный и параллельный метод) и метод нахождения минимума при помощи градиентного спуска(стандартный и параллельный метод).
Предполагается, что описанные в данной работе алгоритмы будут выполнятся на модели массивно параллельных компьютеров.
При оценке трудоемкости параллельных алгоритмов будем использовать следующие критерии . Под временем исполнения алгоритма будет приниматься разница между таймером один , который засекается до начала исполнения программы, и таймером , который фиксирует время после завершения работы программы. под вычислительной сложностью будет принимать число элементарных операций, которые будет исполнять алгоритм в течение его работы. Под ускорением будет принимать некоторый коэффициент , между непараллельным аналогом алгоритма и его параллельной реализацией.
Также стоит отметить , что кластеризация в наше время является проблемой актуальной , так как вычисления становятся все более громоздкими. Появляются новые зависимости в таких отраслях как химия , нефтегазовое дело , метеорология , где необходимо вычислять функции от нескольких десятков переменных и вычислять довольно быстро.
Войти
в кабинет
в кабинет
Пролистайте материалы и убедитесь в качестве
Разработка параллельных алгоритмов в методах оптимизации. А также похожие готовые работы: страница 8 #9102233
Артикул: 9102233
- Предмет: Программирование
- Уникальность: 79% (Антиплагиат.ВУЗ)
- Разместил(-а): 185 Рамиль в 2019 году
- Количество страниц: 36
- Формат файла: docx
999p.
2 000p.
только 24 ноября!
1. Гергель, В.П. Теория и практика параллельных вычислений./ В.П. Гергель/ -М.: 2007 - 423 стр.
2. Эндрюс, Г. Р. Основы многопоточного, параллельного и распределенного программирования. / Г. Р. Эндрюс / Издательство "Вильямс 2003 - 512 стр.
3. Барский, А.Б. Параллельные информационные технологии./ А.Б. Барский/ -Интернет-университет информационных технологий, Бином. Лаборатория знаний 2007.
4. Васильев, Ф.П. Линейное программирование./ Ф.П. Васильев, А.Ю. Иваницкий/ -М.:Факториал Пресс, 2003 – 352 стр.
5. Бажанов, С.Е. Язык функционального параллельного программирования и его реализация на кластерных системах./ С.Е. Бажанов, В.П. Кутепов, Д.А. Шестаков/ Программирование, 2005.
6. Богачев, К.Ю. Основы параллельного программирования./ К.Ю. Богачев / Издательство "Бином. Лаборатория знаний" 2003 г . - 342 стр.
7. Букатов, А. А. Программирование многопроцессорных вычислительных систем./ А. А. Букатов, В. Н. Дацюк, А. И. Жегуло / - Ростов-на-Дону. Издательство ООО «ЦВВР», 2003 - 208 стр.
8. Воеводин, В.В. Параллельные вычисления./ В.В. Воеводин, Вл.В. Воеводин/ -СПб: BHV, 2002.
9. Летова, Т.А. Экстремум функций в примерах и задачах: Учебное пособие/Т.А. Летова, А.В. Пантелеев/ М.: Изд-во МАИ, 1998 - 376 стр.
10. Немнюгин, С.А. Параллельное программирование для многопроцессорных вычислительных систем./ С.А. Немнюгин, О.Л. Стесик/ -СПб.: Петербург, 2002.
2. Эндрюс, Г. Р. Основы многопоточного, параллельного и распределенного программирования. / Г. Р. Эндрюс / Издательство "Вильямс 2003 - 512 стр.
3. Барский, А.Б. Параллельные информационные технологии./ А.Б. Барский/ -Интернет-университет информационных технологий, Бином. Лаборатория знаний 2007.
4. Васильев, Ф.П. Линейное программирование./ Ф.П. Васильев, А.Ю. Иваницкий/ -М.:Факториал Пресс, 2003 – 352 стр.
5. Бажанов, С.Е. Язык функционального параллельного программирования и его реализация на кластерных системах./ С.Е. Бажанов, В.П. Кутепов, Д.А. Шестаков/ Программирование, 2005.
6. Богачев, К.Ю. Основы параллельного программирования./ К.Ю. Богачев / Издательство "Бином. Лаборатория знаний" 2003 г . - 342 стр.
7. Букатов, А. А. Программирование многопроцессорных вычислительных систем./ А. А. Букатов, В. Н. Дацюк, А. И. Жегуло / - Ростов-на-Дону. Издательство ООО «ЦВВР», 2003 - 208 стр.
8. Воеводин, В.В. Параллельные вычисления./ В.В. Воеводин, Вл.В. Воеводин/ -СПб: BHV, 2002.
9. Летова, Т.А. Экстремум функций в примерах и задачах: Учебное пособие/Т.А. Летова, А.В. Пантелеев/ М.: Изд-во МАИ, 1998 - 376 стр.
10. Немнюгин, С.А. Параллельное программирование для многопроцессорных вычислительных систем./ С.А. Немнюгин, О.Л. Стесик/ -СПб.: Петербург, 2002.
Материалы, размещаемые в каталоге, с согласия автора, могут использоваться только в качестве дополнительного инструмента для решения имеющихся у вас задач,
сбора информации и источников, содержащих стороннее мнение по вопросу, его оценку, но не являются готовым решением.
Пользователь вправе по собственному усмотрению перерабатывать материалы, создавать производные произведения,
соглашаться или не соглашаться с выводами, предложенными автором, с его позицией.
| Тема: | Разработка параллельных алгоритмов в методах оптимизации |
| Артикул: | 9102233 |
| Дата написания: | 05.06.2019 |
| Тип работы: | Дипломная работа |
| Предмет: | Программирование |
| Оригинальность: | Антиплагиат.ВУЗ — 79% |
| Количество страниц: | 36 |
Скрин проверки АП.ВУЗ приложен на последней странице.
В работе представлены только пояснительная записка и листинг программы. Самой программы нет
В работе представлены только пояснительная записка и листинг программы. Самой программы нет
Файлы артикула: Разработка параллельных алгоритмов в методах оптимизации. А также похожие готовые работы: страница 8 по предмету программирование
Пролистайте "Разработка параллельных алгоритмов в методах оптимизации. А также похожие готовые работы: страница 8" и убедитесь в качестве
После покупки артикул автоматически будет удален с сайта до 23.01.2025
Посмотреть остальные страницы ▼
Честный антиплагиат!
Уникальность работы — 79% (оригинальный текст + цитирования, без учета списка литературы и приложений), приведена по системе Антиплагиат.ВУЗ на момент её написания и могла со временем снизиться. Мы понимаем, что это важно для вас, поэтому сразу после оплаты вы сможете бесплатно поднять её. При этом текст и форматирование в работе останутся прежними.
Гарантируем возврат денег!
Качество каждой готовой работы, представленной в каталоге, проверено и соответствует описанию. В случае обоснованных претензий мы гарантируем возврат денег в течение 24 часов.
Утром сдавать, а работа еще не написана?
Через 30 секунд после оплаты вы скачаете эту работу!
Сегодня уже купили 15 работ. Успей и ты забрать свою пока это не сделал кто-то другой!
ПРЕДЫДУЩАЯ РАБОТА
Разработка интернет-магазина по продаже смартфонов
СЛЕДУЮЩАЯ РАБОТА
Разработка программного обеспечения для обнаружения вредоносного программного обеспечения