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

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Тульский государственный университет»

Институт Прикладной математики и компьютерных наук

Кафедра Вычислительной техники

Курсовая работа

учебной дисциплины «Программирование»

Уровень профессионального образования: (высшее образование - бакалавриат)

Направление подготовки: 09.03.01 Информатика и вычислительная техника

Профиль подготовки: Вычислительные машины, комплексы, системы и сети

Профиль подготовки: Автоматизированные системы обработки информации и управления

Квалификация выпускника: Академический бакалавр

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

Тула 2019



Оглавление

Введение

1. Техническое задание

2. Теоретическая справка

3. Сведения о средствах языка программирования

4. Программное обеспечение

5. Структура программы и инструкция программисту

6. Тестирование

7. Инструкция программисту

Заключение

Библиографический список

Приложение



Введение

программирование матричный операция

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

Использование объектно-ориентированного (ОО) подхода при разработке программного обеспечения (ПО) позволяет преодолеть естественную сложность разрабатываемого ПО, упростить процесс отладки и последующего сопровождения, расширения и переноса ПО на другие платформы.

В данной курсовой работе в процессе проектирования и реализации конкретного приложения используются комбинация процедурно-ориентированного и объектно-ориентированного подхода и проводится сравнительный анализ их свойств и возможностей применения.

Курсовая работа выполняется для закрепления знаний и приобретения навыков объектно-ориентированной реализаций прикладной задачи (задачи нахождения реализации базовых матричных операций для разреженных матриц) с использованием различных языков, инструментальных систем и библиотек, автоматизирующих проектирование, программирование и отладку создаваемых приложений.

Задачами курсовой работы являются:

приобретение навыков решения вычислительных задач;

практическое освоение современных инструментальных систем разработки ПО.



1. Техническое задание

Программный комплекс должен обеспечивать осуществление операций над разреженными матрицами.

Структуры данных:

Входные данные хранятся в виде текстового файла.

Выполняемые функции:

ввод исходных значений для обработки;

вывод на экран значений в виде матриц;

Требования к среде эксплуатации:

программа предназначена для использования в среде Windows.

Требования к среде разработки:

Программа должна быть разработана на языке программирования C++ в среде разработки Microsoft Visual Studio 2019.

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

Ставится задача проектирования программного комплекса, обеспечивающего решение задач над разреженными матрицами.

Способ решения. Для решения поставленной задачи можно использовать технологию объектно-ориентированного программирования на языке С++.

2. Теоретическая справка

Разрежённая матрица -- это матрица с преимущественно нулевыми элементами. В противном случае, если бомльшая часть элементов матрицы ненулевые, матрица считается плотной.

Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разрежённой. Разные авторы предлагают различные варианты. Для матрицы порядка n число ненулевых элементов[1]:

есть O(n). Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;

в каждой строке не превышает 10 в типичном случае;

ограничено , где .

таково, что для данного алгоритма и вычислительной системы имеет смысл извлекать выгоду из наличия в ней нулей.

Огромные разрежённые матрицы часто возникают при решении таких задач, как интегрирование систем дифференциальных уравнений в частных производных.

При хранении и преобразовании разрежённых матриц в компьютере бывает полезно, а часто и необходимо, использовать специальные алгоритмы и структуры данных, которые учитывают разрежённую структуру матрицы. Операции и алгоритмы, применяемые для работы с обычными, плотными матрицами, применительно к большим разрежённым матрицам работают относительно медленно и требуют значительных объёмов памяти. Однако разрежённые матрицы могут быть легко сжаты путём записи только своих ненулевых элементов, что снижает требования к компьютерной памяти.

Один из возможных вариантов хранения: координатный, часто обозначаемый в литературе аббревиатурой «COO». В базовом варианте этого формата, каждому ненулевому элементу матрицы соответствует триплет из двух координат (номера строки и номера столбца) и значения элемента, а триплеты хранятся в виде простого одномерного массива с произвольным доступом.

Если значение элемента представлено числом с плавающей точкой, а координаты элемента - целыми числами, то общий расход памяти соответствует числу ненулевых элементов (NNZ), умноженному на объём памяти, требуемый для хранения значения и координат. Если для хранения координат используются 32-битные целые, а для хранения значения 32-битное число с плавающей точкой (одинарной точности), то суммарный расход памяти равен в байтах: 3 * 4 * NNZ. В этом случае только треть памяти используется для хранения собственно данных, а две трети - для хранения координат. Вообще говоря, это не самый экономичный с точки зрения использования памяти формат хранения разреженной матрицы, так как известны форматы (например, CSR), которые имеют более экономичные характеристики. Однако, работа с координатным форматом (COO) заметно проще: реализация базовых алгоритмов работы с матрицами оказывается не такой сложной, как для форматов типа CSR.

Дополнительный недостаток формата COO -- доступ к произвольному элементу за O(NNZ) или O(log(NNZ)), где NNZ -- число ненулевых элементов в матрице. Такая скорость достигается либо поиском по индексу полным перебором для неупорядоченного варианта хранения элементов или бинарным поиском по индексу для хранения в виде отсортированного массива. Однако при реализации базовых алгоритмов работы с матрицами можно найти такие пути, которые позволяют не осуществлять доступы к произвольному элементу, тем самым устранив эту затратную операцию. Это возможно, например, если всё время хранить ненулевые элементы матрицы в отсортированном по координатам виде. Порядок сортировки по координатам должен быть таким, что при сравнении координат вначале сравнивается номер строки, а при равенстве - номер столбца.

Операция сортировки после произвольной модификации матрицы имеет сложность классических вариантов сортировки, то есть O(NNZ*log(NNZ)), где NNZ - число ненулевых элементов в матрице. В целом, можно избежать выполнения этой операции вообще в том случае, если формирование матрицы сразу осуществляется в требуемом порядке по координатам. Базовые алгоритмы работы с матрицами также можно постараться построить так, чтобы на их выходе автоматически получалась правильно упорядоченная матрица.



3. Сведения о средствах языка программирования

C++ -- компилируемый, статически типизированный язык программирования общего назначения.

Поддерживает такие парадигмы программирования как процедурное программирование, объектно-ориентированное программирование, обобщённое программирование, обеспечивает модульность, раздельную компиляцию, обработку исключений, абстракцию данных, объявление типов (классов) объектов, виртуальные функции. Стандартная библиотека включает, в том числе, общеупотребительные контейнеры и алгоритмы. C++ сочетает свойства как высокоуровневых, так и низкоуровневых языков. В сравнении с его предшественником -- языком C, -- наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования.

C++ широко используется для разработки программного обеспечения, являясь одним из самых популярных языков программирования. Область его применения включает создание операционных систем, разнообразных прикладных программ, драйверов устройств, приложений для встраиваемых систем, высокопроизводительных серверов, а также развлекательных приложений. Существует множество реализаций языка C++, как бесплатных, так и коммерческих и для различных платформ.

Язык программирования С++ был создан в начале 1980-х годов, его создатель сотрудник фирмы Bell Laboratories -- Бьёрн Страуструп. Он придумал ряд усовершенствований к языку программирования C, для собственных нужд. Т. е. изначально не планировалось создания языка программирования С++. Ранние версии языка С++, известные под именем «Cи с классами», начали появляться с 1980 года. Язык C, будучи базовым языком системы UNIX, на которой работали компьютеры фирмы Bell, является быстрым, многофункциональным и переносимым. Страуструп добавил к нему возможность работы с классами и объектами, тем самым зародил предпосылки нового, основанного на синтаксисе С, языка программирования. Синтаксис C++ был основан на синтаксисе C, так как Бьёрн Страуструп стремился сохранить совместимость с языком C.

4. Программное обеспечение

Запуск осуществляется путём запуска на выполнение файла MTX.exe. Появляется диалоговое окно, которое показывает три матрицы: две исходных и матрицу-результат выполнения операции.

Программа позволяет выполнить три вида операций над матрицами: сложение двух матриц, транспонирование матриц и умножение двух матриц. Выбор вида операции осуществляется путём выбора нужного переключателя в блоке радио-кнопок «Action». Запуск операции на выполнение осуществляется нажатием кнопки «Process».

Допускается вариант сборки программы MTX.exe в консольном формате. В этом случае программа не выводит диалоговых окон, а только осуществляет рад тестов матричных операций с выводом результатов на консоль в текстовом виде. Такой вариант сборки не предполагает диалога с пользователем.

5. Структура программы и инструкция программисту

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

MTX.cpp - основная единица компиляции, содержит в себе функцию «main()», то есть точку входа для C++-программы. Функция main() содержит набор тестов алгоритмов и код, реализующий графический интерфейс и процесс диалога с пользователем с помощью библиотеки графического интерфейса пользователя «nana» (https://github.com/cnjinhao/nana).

Компонент в составе main(), отвечающий за графический интерфейс пользователя, может быть отключен на этапе компиляции с помощью устранения символа препроцессора WITH_GUI.

Файл MTX.cpp включает в себя остальные компоненты программного комплекса с помощью директив #include.

Файл element.h - содержит в себе декларацию структуры хранения элемента матрицы в формате COO, то есть триплета из двух координат и значения. Структура определёна с помощью стандартного класса стандартной библиотеки шаблонов C++ (STL) std::tuple. Там же определён вспомогательный класс element_traits, предоставляющий некоторый сервис для упрощения работы с классом элемента. Дополнительно определены несколько функций сравнения элементов друг с другом по координатам.

Файл coo_mtx.h - содержит декларацию и реализацию класса, инкапсулирующего в себе данные и основной код операций, относящихся к сущности «разреженная матрица в формате COO».

Файл sp_m_algo.h - содержит реализацию трёх матричных операций, которые составляют основу функциональности данного программного комплекса. Это функции:

sp_mm_add(coo_mtx &a, coo_mtx &b, coo_mtx &c);

- выполняет сложение двух матриц a и b одинаковой размерности и помещает результат в пустую матрицу c;

sp_m_transpose(coo_mtx &a);

- выполняет транспонирование

. матрицы a, не создавая новой матрицы, то есть, путём изменения исходной матрицы;

sp_mm_multiply(coo_mtx &a, coo_mtx &b, coo_mtx &c);

- выполняет перемножение двух матриц a и b и помещает результат в пустую матрицу c. Размерности исходных матриц должны соответствовать требованию для операции матричного умножения

Файл output.h - реализует операцию вывода заданной матрицы в табличном формате.

6. Тестирование

Тестирование выполняется в двух вариантах: ряд тестовых входных данных для трёх тестируемых матричных операций «зашит» в программу по аналогии с концепцией юнит-тестов. Решения этих задач выполняются автоматически при каждом запуске, результат выводится на консоль. Предполагается ручное сравнение выходных данных для определения корректности выполненных решений для каждого из алгоритмов. Для решения задачи в графическом интерфейсе необходимо нажимать кнопку «Process», выбрав в поле «Actons» тестируемый алгоритм.

7. Инструкция программисту

Сборка программного комплекса осуществляется средствами Microsoft Visual Studio 2019 с помощью солюшн-файла «MTX.sln». Имеется единственная конфигурация Release/x64, конфигурация для архитектуры x86 может быть добавлена по желанию программиста.

Сборка может быть выполнена в режиме с графическим интерфейсом или без графического интерфейса. Переключение режима осуществляется включением или выключением директивы препроцессора define в первой строке файла MTX.cpp.

Интерфейс программы после запуска выглядит так, как показано на Рисунке 1. Три элемента «textbox» в основной части окна показывают табличное представление матриц a, b и c, которые участвуют в основных операциях, выполняемых программой.

Блок радио-кнопок «Action» позволяет выбрать тип операции над матрицами для осуществления.

Кнопка «Process» в нижней части окна позволяет осуществить выбранную операцию и автоматически вызывает обновление содержимого объектов, отображающих матрицы a, b и c.

Рисунок 1. Вид интерфейса программа сразу после запуска на выполнение

Рисунок 2 показывает пример внешнего вида окна программы после выполнения одной из операций.

Рисунок 2. Вид интерфейса программа сразу после выполнения операции суммирования двух матриц.



Заключение

В данном курсовом проекте при разработке программы были закреплены навыки объектно-ориентированного программирования на языке С++.

При разработке пользовательского интерфейса, были освоены основные объекты и их свойства. При оформлении курсового проекта изучено оформление прикладной документации согласно ГОСТу.



Библиографический список

1. Анисимов, А.Е. Сборник заданий по основаниям программирования: учеб. пособие / А.Е. Анисимов, В.В. Пупышев .-- М.: Интернет-ун-т информ. технологий; БИНОМ. Лаборатория знаний, 2006 .-- 348с. <15>.

2. Макконелл, Д. Основы современных алгоритмов : учеб. пособие -- М.: Техносфера, 2006 .-- 368 с. <7>.

3. Подбельский, В.В. Язык Си+ :Учеб. пособие для вузов / В.В. Подбельский.-- 5-е изд. -- М.: Финансы и статистика, 2003 .-- 560с. <13>.

4. Павловская, Т.А. C/C++:Программирование на языке высокого уровня : Учебник для вузов / Т.А. Павловская.-- М. и др. : Питер, 2004 .-- 461с.<7>.

5. Ганеев, Р.М. Проектирование интерфейса пользователя средствами Win32 API: учеб. пособие для вузов / Р.М. Ганеев .-- 2-е изд., испр. и доп. -- М. : Горячая линия-Телеком, 2007 .-- 358 с.<3>.

6. Вирт Н. Алгоритмы + структуры данных = программы. М.; Mиp, 1985. - 281 с.

7. Шлее, М. Профессиональное программирование на С++ / М. Шлее.-- СПб.: БХВ-Петербург, 2005.-- 544с.: ил. + 1 CD.-- (В подлиннике). <3>.

8. Страуструп, Б. Язык программирования Си++: Спец. изд. / Б. Страуструп; Пер. с англ. С. Анисимова, М. Кононова; Подред. Ф. Андреева, А. Ушаков.-- М.: Бином, 2004 .-- 1098с. <4>.



Приложение

Исходный текст модуля класса матрицы coo_matrix.h

#pragma once

#include <assert.h>

#include <vector>

#include <algorithm>

#include "element.h"

struct coo_mtx {

bool sorted = true;

int nrows = 0, ncols = 0, nnz = 0;

std::vector<element_t> elems;

coo_mtx(int _nrows, int _ncols) : nrows(_nrows), ncols(_ncols) {}

void empty() {

sorted = true;

nrows = ncols = nnz = 0;

elems.resize(0);

}

void add(const element_t& el, bool ruines_sorting = true) {

assert(element_traits::row(el) <= nrows);

assert(element_traits::col(el) <= ncols);

elems.push_back(el);

nnz++;

if (ruines_sorting)

sorted = false;

}

void check() {

assert(nnz == (int)elems.size());

if (nnz && sorted) {

assert(element_traits::row(elems.back()) <= element_traits::row_t(nrows));

assert(element_traits::col(elems.back()) <= element_traits::col_t(ncols));

}

}

bool is_empty() {

check();

return nnz == 0;

}

void sort(bool force = false) {

if (sorted && !force)

return;

std::sort(elems.begin(), elems.end(), [](element_t & a, element_t & b) {

return !is_further_coord(b, element_traits::row(a), element_traits::col(a));

});

sorted = true;

}

void merge(coo_mtx & a, coo_mtx & b) {

std::merge(a.elems.begin(), a.elems.end(), b.elems.begin(), b.elems.end(), std::back_inserter(elems),

[](element_t & a, element_t & b) {

return !is_further_coord(b, element_traits::row(a), element_traits::col(a));

});

sorted = true;

}

void remove_nonexistents() {

size_t nremoved = elems.size();

elems.erase(std::remove_if(elems.begin(), elems.end(),

[](element_t & el) {

return element_traits::row(el) == element_traits::NONEXISTENT_ROW &&

element_traits::col(el) == element_traits::NONEXISTENT_COL; }),

elems.end());

nremoved -= elems.size();

nnz -= (int)nremoved;

}

};

Исходный текст модуля классов элемента матрицы element.h

#pragma once

#include <tuple>

typedef std::tuple<int, int, double> element_t;

struct element_traits {

using row_t = std::tuple_element<0, element_t>::type;

using col_t = std::tuple_element<1, element_t>::type;

using val_t = std::tuple_element<2, element_t>::type;

static row_t row(const element_t& el) { return std::get<0>(el); }

static col_t col(const element_t& el) { return std::get<1>(el); }

static val_t val(const element_t& el) { return std::get<2>(el); }

static row_t& row(element_t& el) { return std::get<0>(el); }

static col_t& col(element_t& el) { return std::get<1>(el); }

static val_t& val(element_t& el) { return std::get<2>(el); }

static const row_t NONEXISTENT_ROW = (row_t)-1;

static const col_t NONEXISTENT_COL = (col_t)-1;

};

static inline bool is_this_coord(const element_t& el, int r, int c)

{

return element_traits::row(el) == static_cast<element_traits::row_t>(r) &&

element_traits::col(el) == static_cast<element_traits::col_t>(c);

}

static inline bool is_further_coord(const element_t& el, int r, int c)

{

return element_traits::row(el) < static_cast<element_traits::row_t>(r) ||

(element_traits::row(el) == static_cast<element_traits::row_t>(r) &&

element_traits::col(el) < static_cast<element_traits::col_t>(c));

}

static inline bool is_same(const element_t & a, const element_t & b)

{

return is_this_coord(b, (int)element_traits::row(a), (int)element_traits::col(a));

}

bool operator==(const element_t & a, const element_t & b)

{

return is_same(a, b);

}

bool operator>(const element_t & a, const element_t & b)

{

return is_further_coord(b, element_traits::row(a), element_traits::col(a));

}

Исходный текст модуля алгоритмов sp_m_algo.h

#pragma once

#include <assert.h>

#include <algorithm>

void sp_mm_add(coo_mtx& a, coo_mtx& b, coo_mtx& c)

{

assert(a.nrows == b.nrows);

assert(a.ncols == b.ncols);

if (!a.is_empty()) {

a.sort();

a.check();

}

if (!b.is_empty()) {

b.sort();

b.check();

}

assert(c.is_empty());

c.nrows = a.nrows;

c.ncols = a.ncols;

if (a.is_empty()) {

c.elems.insert(c.elems.end(), b.elems.begin(), b.elems.end());

c.nnz = (int)c.elems.size();

return;

}

if (b.is_empty()) {

c.elems.insert(c.elems.end(), a.elems.begin(), a.elems.end());

c.nnz = (int)c.elems.size();

return;

}

c.merge(a, b);

c.nrows = a.nrows;

c.ncols = a.ncols;

c.nnz = (int)c.elems.size();

size_t nremoved = 0;

auto it2 = c.elems.begin() + 1;

for (auto it = c.elems.begin(); it != c.elems.end(); ++it, ++it2) {

if (it2 != c.elems.end()) {

if (is_same(*it, *it2)) {

auto& a = *it;

auto& b = *it2;

element_traits::val(a) += element_traits::val(b);

element_traits::row(b) = element_traits::NONEXISTENT_ROW;

element_traits::col(b) = element_traits::NONEXISTENT_COL;

nremoved++;

}

}

}

if (nremoved) {

c.remove_nonexistents();

c.check();

}

}

void sp_m_transpose(coo_mtx& a)

{

for (auto it = a.elems.begin(); it != a.elems.end(); ++it) {

auto r = static_cast<element_traits::row_t>(element_traits::col(*it));

auto c = static_cast<element_traits::col_t>(element_traits::row(*it));

element_traits::row(*it) = r;

element_traits::col(*it) = c;

}

std::swap(a.nrows, a.ncols);

a.sort(true);

}

void sp_mm_multiply(coo_mtx& a, coo_mtx& b, coo_mtx& c)

{

assert(a.ncols == b.nrows);

assert(c.is_empty());

if (a.is_empty() || b.is_empty())

return;

a.sort();

a.check();

b.sort();

b.check();

c.nrows = a.nrows;

c.ncols = b.ncols;

sp_m_transpose(b);

auto a_it = a.elems.begin();

auto b_it = b.elems.begin();

auto a_row_start_it = a.elems.begin();

element_traits::row_t target_row = element_traits::row(*a_it);

element_traits::col_t target_col = static_cast<element_traits::col_t>(element_traits::row(*b_it));

bool go_to_next_row = false;

element_traits::val_t acc = 0;

bool target_col_changed = false;

bool acc_updated = false;

for (;;) {

if (b_it == b.elems.end()) {

go_to_next_row = true;

b_it = b.elems.begin();

target_col_changed = true;

}

if (target_col != static_cast<element_traits::col_t>(element_traits::row(*b_it))) {

target_col_changed = true;

}

if (target_col_changed) {

if (acc_updated) {

c.add(element_t(target_row, target_col, acc), false);

acc_updated = false;

}

target_col = static_cast<element_traits::col_t>(element_traits::row(*b_it));

acc = 0;

while (target_row == element_traits::row(*a_it)) {

++a_it;

if (a_it == a.elems.end())

break;

}

}

if (a_it == a.elems.end() || target_row != element_traits::row(*a_it)) {

if (go_to_next_row) {

if (a_it == a.elems.end())

break;

target_row = element_traits::row(*a_it);

a_row_start_it = a_it;

go_to_next_row = false;

}

else {

a_it = a_row_start_it;

if (!target_col_changed) {

while (target_col == static_cast<element_traits::col_t>(element_traits::row(*b_it))) {

++b_it;

if (b_it == b.elems.end())

break;

}

if (acc_updated) {

c.add(element_t(target_row, target_col, acc), false);

acc_updated = false;

}

target_col = static_cast<element_traits::col_t>(element_traits::row(*b_it));

acc = 0;

}

}

}

target_col_changed = false;

if (b_it == b.elems.end())

continue;

auto c1 = element_traits::col(*a_it);

auto c2 = element_traits::col(*b_it);

if (c1 == c2) {

acc += element_traits::val(*a_it) * element_traits::val(*b_it);

acc_updated = true;

++b_it;

++a_it;

}

else if (c1 > c2) {

++b_it;

}

else {

++a_it;

}

}

sp_m_transpose(b);

}

Размещено на Allbest.ru

...