Разработка библиотеки параллельных алгоритмов решения оптимизационных задач на графах

Вернуться к списку проектов На главную страницу курса

Заказчик

Соколов Андрей Владимирович, профессор кафедры информатики и математического обеспечения. Эл.почта: avs@krc.karelia.ru.

Инструктор

Кулаков Кирилл Александрович, доцент кафедры Информатики и математического обеспечения. Эл.почта: kulakov@cs.karelia.ru.

Аннотация проекта

Предполагается разработать на языке С++ с использование технологии параллельного программирования OpenMP библиотеку параллельных алгоритмов решения оптимизационных задач на графах. Библиотека будет включать параллельные алгоритмы Флойда и Джонсона, Краскала, Прима. Также необходимо реализовать алгоритмы ввода, вывода, добавления и удаления вершин и ребер, преобразования представления графа из списка смежности к матрице смежности и обратно и последовательные реализации алгоритмов Дейкстры и Беллмана-Форда.

Ссылки

Кормен Е., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 2- издание, Изд.-дом “ Вильямс”, 2005.
Седжвик Р. Фундаментальные алгоритмы на С++. часть 5, алгоритмы на графах, .: Издательство «Диасофт», 2002.
В.П. Гергель Высокопроизводительные вычисления для многопроцессорных многоядерных систем. Суперкомпьютерный консорциум университетов России. Москва, Физматлит, МГУ, 2010.
А.С. Антонов. Параллельное программирование с использованием технологии OpenMP. МГУ, 2009 г.
Центр высокопроизводительной обработки данных ЦКП КарНЦ РАН.

Разработчики

Сазонов Александр Михайлович, 22303
Старков Святослав Александрович, 22304
Павшев Дмитрий Владимирович, 22303
Шварц Александр Евгеньевич, 22303
Долматов Никита Сергеевич, 22303

Web-ресурс разработки