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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

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

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

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

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

Тула 2019



СОДЕРЖАНИЕ

• Введение
• 1. Постановка задачи на проектирование
• 2. Теоретическая часть
• 3. Сведения о средствах языка программирования
• 4. Инструкция по установке
• 5. Руководство пользователя
• 6. Руководство программиста
• 7. Программная реализация
• 8. Тестирование
• Заключение
• Список использованной литературы
• Приложение


Введение

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

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

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

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

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

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

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



1. Постановка задачи на проектирование

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

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

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

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

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

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

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

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

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

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



4. Инструкция по установке

4.1 Установка бинарного дистрибутива программного комплекса.

Для установки и успешной работы разработанного программного комплекса необходимо:

-выполнить распаковку дистрибутивного архива, поставляемого в формате ZIP, извлечь файл MTX.exe.

-скачать и установить свободно распространяемые компоненты библиотек периода выполнения из комплекта средства разработки MicrosoftVisualStudio 2019. Дистрибутив этих компонент свободно распространяется и доступен на сайте компании Microsoft по ссылке https://aka.ms/vs/16/release/vc_redist.x64.exe. Файл vc_redist.x64.exe следует запустить от аккаунта с правами администратора, чтобы установка компонент успешно выполнилась. Если эти компоненты уже установлены на системе, повторная установка не требуется.

-для работы запустить файл MTX.exe и следовать инструкциям по работе с программным комплексом.

Минимальные требования к операционной системе, на которой может быть запущен бинарный вариант программного комплекса:

MicrosoftWindows 7 x64.

Аппаратная архитектура: совместимая с Intel x64 (архитектуру также часто обозначают: x86_64 или Intel64/AMD64).

4.2 Сборка программного комплекса из исходных текстов

Для компиляции и сборки программного комплекса необходимо установить программный комплекс MicrosoftVisualStudio 2019 .

Среду VisualStudio 2019 можно установить и работать в ней на следующих операционных системах (перечислены официально поддерживаемые версии):

- Windows 7 с Service Pack 1;

-Windows 8.1 (собновлением 2919355);

-Windows 10 (1703 и выше);

-WindowsServer 2012 R2 (с обновлением 2919355);

-Windows Server 2016 (Standard и Datacenter);

-Windows Server 2019 (Standard и Datacenter).

Минимальные требования к оборудованию:

-процессор с тактовой частотой не ниже 1,8 ГГц. Рекомендуется использовать как минимум двухъядерный процессор;

-2 ГБ оперативной памяти, рекомендуется 8 ГБ (если устанавливать на виртуальную машину, то минимум 2.5 ГБ);

-свободного места на жестком диске от 800 мегабайт до 210 гигабайт, в зависимости от установленных компонентов. В большинстве случаев выделяйте как минимум 30 гигабайт.ТакжеMicrosoft рекомендует устанавливать VisualStudio на SSD диск.

-видеоадаптер с минимальным разрешением 1280 на 720 пикселей (для оптимальной работы VisualStudio рекомендуется разрешение 1366 на 768 пикселей и более высокое).

Дополнительные важные моменты:

-для установки VisualStudio 2019 требуются права администратора;

-для работы VisualStudio 2019 требуется платформа .NET Framework 4.7.2, она будет установлена во время установки среды;

Для проведения компиляции и сборки программного комплекса из исходных текстов требуется:

-выполнить распаковку дистрибутивного архива, поставляемого в формате ZIP, извлечь все файлы поставки, кроме MTX.exe.

-из окна программной среды MicrosoftVisualStudio 2019 открыть файл MTX.sln.

-в меню программной среды выбрать пункт «BuildSolution», дождаться окончания компиляции и сборки программного комплекса.

-в результате работы программной среды повится новый файл MTX.exe, находящийся во вновь созданном подкаталоге «x64/Release». Этот файл является результатом процедуры компиляции и сборки, его можно использовать аналогично поставляемому бинарному образу MTX.exe так, как описано в п.3.1 настоящего документа.



5. Инструкция пользователю

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

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

Есть вариант сборки программы MTX.exeв консольном формате. Такой вариант сборки не предполагает диалога с пользователем( Рисунок 2).

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



.

Рисунок 2 - Окно в консольном формате



6. Руководство программиста

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

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

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

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

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

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

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



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



7. Программная реализация

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

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 - реализует операцию вывода заданной матрицы в табличном формате.

Листингпрограммы:

#defineWITH_GUI

#ifdefWITH_GUI

#include<nana/gui.hpp>

#include<nana/gui/widgets/button.hpp>

#include<nana/gui/widgets/group.hpp>

#include<nana/gui/widgets/textbox.hpp>

#include<nana/gui/widgets/label.hpp>

#endif

#include"element.h"// COO matrix element-level structures and helpers

#include"coo_mtx.h"// COO matrix class implementation

#include"sp_m_algo.h"// sp_mm_add(), sp_m_transpose() and sp_mm_multiply() algorithms implementation

#include"output.h"// Matrix pretty print implementation

int main()

{

// Text mode basic tests

{

coo_mtxa(5, 5);

a.add(element_t(0, 0, 1));

a.add(element_t(1, 1, 2));

a.add(element_t(2, 2, 3));

a.add(element_t(3, 3, 4));

a.add(element_t(4, 4, 5));

std::cout<<"|a|:"<<std::endl;

std::cout<< a <<std::endl;

coo_mtx b(5, 5);

b.add(element_t(0, 4, 200));

b.add(element_t(1, 3, 300));

b.add(element_t(2, 2, 400));

b.add(element_t(3, 1, 500));

b.add(element_t(4, 0, 600));

std::cout<<"|b|:"<<std::endl;

std::cout<< b <<std::endl;

coo_mtx c(5, 5);

sp_mm_add(a, b, c);

std::cout<<"|c|=|a|+|b|:"<<std::endl;

std::cout<< c <<std::endl;

sp_m_transpose(c);

std::cout<<"Transpose(|c|):"<<std::endl;

std::cout<< c <<std::endl;

}

{

coo_mtxa(3, 3);

a.add(element_t(0, 0, 1));

a.add(element_t(2, 2, 9));

coo_mtx b(3, 3);

b.add(element_t(0, 0, 1));

b.add(element_t(1, 1, 1));

b.add(element_t(2, 2, 1));

std::cout<<"|a|:"<<std::endl;

std::cout<< a <<std::endl;

std::cout<<"|b|:"<<std::endl;

std::cout<< b <<std::endl;

coo_mtx c(3, 3);

sp_mm_multiply(a, b, c);

std::cout<<"|c|=|a|*|b|:"<<std::endl;

std::cout<< c <<std::endl;

}

{

coo_mtxa(3, 3);

a.add(element_t(0, 0, 1));

a.add(element_t(1, 1, 2));

a.add(element_t(2, 2, 3));

coo_mtx b(3, 3);

b.add(element_t(0, 2, 10));

b.add(element_t(1, 1, 100));

b.dd(element_t(2, 0, 1000));

std::cout<<"|a|:"<<std::endl;

std::cout<< a <<std::endl;

std::cout<<"|b|:"<<std::endl;

std::cout<< b <<std::endl;

coo_mtx c(3, 3);

sp_mm_multiply(a, b, c);

std::cout<<"|c|=|a|*|b|:"<<std::endl;

std::cout<< c <<std::endl;

}

#ifdefWITH_GUI

coo_mtxa(5, 5);

a.add(element_t(0, 0, 1));

a.add(element_t(1, 1, 2));

a.add(element_t(2, 2, 3));

a.add(element_t(3, 3, 4));

a.add(element_t(4, 4, 5));

coo_mtx b(5, 5);

b.add(element_t(0, 4, 200));

b.add(element_t(1, 3, 300));

b.add(element_t(2, 2, 400));

b.add(element_t(3, 1, 500));

b.add(element_t(4, 0, 600));

coo_mtx c(5, 5);

std::stringA_str, B_str, C_str;

{ std::stringstreamss; ss<< a; A_str=ss.str(); }

{ std::stringstreamss; ss<< b; B_str=ss.str(); }

usingnamespace nana;

formfm(API::make_center(900, 600));

fm.caption("MTX -- sparse matrix operations");

placefm_place {fm};

enumaction_t { SUM, TRANS, MULT };

action_t action = SUM;

textboxA_box { fm, A_str };

A_box.multi_lines(true).editable(false);

labelA_lab(fm, "Matrix |A|:");

textboxB_box{ fm, B_str };

B_box.multi_lines(true).editable(false);

labelB_lab(fm, "Matrix |B|:");

textboxC_box{ fm, C_str };

C_box.multi_lines(true).editable(false);

labelC_lab(fm, "Matrix |C|:");

buttonbtn{ fm, "Process" };

btn.tooltip("Sum");

group act { fm, "Actions" };

act.add_option("Sum: |C|=|A|+|B|")

.events().click([&]() { action = SUM; btn.tooltip("Sum"); });

act.add_option("Trans: |X|=Transpose(|X|)")

.events().click([&]() { action = TRANS; btn.tooltip("Transpose"); });

act.add_option("Multiply: |C|=|A|*|B|")

.events().click([&]() { action = MULT; btn.tooltip("Multiply"); });

btn.events().click([&]() {

switch (action) {

caseSUM: c.empty(); sp_mm_add(a, b, c); break;

caseTRANS: sp_m_transpose(a); sp_m_transpose(b); sp_m_transpose(c); break;

caseMULT: c.empty(); sp_mm_multiply(a, b, c); break;

}

{ std::stringstreamss; ss<< c; C_str=ss.str(); C_box.caption(C_str); }

{ std::stringstreamss; ss<< a; A_str=ss.str(); A_box.caption(A_str); }

{ std::stringstreamss; ss<< b; B_str=ss.str(); B_box.caption(B_str); }

return;

});

act.radio_mode(true);

act.option_check(0);

fm_place.div("vertical <weight=8% labels margin=13 gap=5>|<weight=60% boxes margin=13 gap=5>|<actions margin=13>|<weight=10% button margin=15>");

fm_place["labels"]<<A_lab<<B_lab<<C_lab;

fm_place["boxes"]<<A_box<<B_box<<C_box;

fm_place["actions"]<< act;

fm_place["button"]<<btn;

fm_place.collocate();

fm.show();

exec();

#endif

return 0;

}



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

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

Рисунок 4 - Автоматическое тестирование

Программа позволяет выполнить три вида операций над матрицами: сложение двух матриц(Рисунок 5), транспонирование матриц(Рисунок 6) и умножение двух матриц.



Рисунок 5 - Сложение

Рисунок 6 - Транспонирование



Рисунок 7 - Умножение



ЗАКЛЮЧЕНИЕ

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

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



СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

Основнаялитература

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 Благодатских В.А. Стандартизация разработки программных средств : учебное пособие для вузов / В.А.Благодатских, В.А.Волнин,

7 К.Ф.Поскакалов;подред.О.С.Разумова .-- М. : Финансы и статистика, 2006 .-- 288с.

Камаев В.А. Технологии программирования : учебник для вузов / В.А.Камаев, В.В.Костерин .-- 2-е изд., перераб.и доп. -- М. : Высш.шк., 2006 .-- 454с.

5 Котляров, В.П. Основы тестирования программного обеспечения: учеб.пособие/ В.П.Котляров, Т.В.Коликова .-- М. : Интернет - Ун-т ин-форм.технологий: Бином ЛЗ, 2006 .-- 285с: учеб.пособие -- М. :

Дополнительнаялитература

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

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

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

4 Kernigan B.W. Практика программирования : пер.сангл. / Б.Керниган, Р.Пайк .-- [8-е изд.,испр.и доп.].-- М.;СПб.; Киев: Вильямс, 2004 .-- 287с.

5ТамреTamres L. Введение в тестирование программного обеспечения / Л.Тамре; пер.сангл.иред.В.В.Марченко .-- М.и др. : Вильямс, 2003 .-- 359с.

6Калбертсон, Culbertson R. Быстрое тестирование : пер.с англ. / Р.Калбертсон, К.Браун,Г.Кобб .-- М.и др. : Вильямс, 2002 .-- 384с

7 Винниченко, И.В. Автоматизация процессов тестирования / И.В.Винниченко .-- М. : Питер, 2005 .-- 203с.

8 Стотлемайер, Stottlemyer D. Тестирование Web-приложений: средства и методы для автоматизированного и ручного тестирования программногообеспечения Web-сайтов: пер.с англ. / Д.Стотлемайер .-- М. : КУДИЦ-ОБРАЗ, 2003 .-- 240с.

9 Липаев В.В. Методы обеспечения качества крупномасштабных про-граммных средств / В.В.Липаев;РАН.Ин-т системного программирования .-- М. : СИНТЕГ, 2003 .-- 510с.

10 Макгрегор Д. Тестирование объектно-ориентированного программного обеспечения: Практ.пособие:Пер.с англ. / Д.Макгрегор,Д.Сайкс .-- М.и др.: DiaSoft, 2002 .-- 432c.



Приложение 1

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

#pragma once

#include <assert.h>

#include <vector>

#include <algorithm>

#include "element.h"

structcoo_mtx {

bool sorted = true;

intnrows = 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(constelement_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));

}

}

boolis_empty() {

check();

returnnnz == 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;

}

voidremove_nonexistents() {

size_tnremoved = elems.size();

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

[](element_t& el) {

returnelement_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>

typedefstd::tuple<int, int, double>element_t;

structelement_traits {

usingrow_t = std::tuple_element<0, element_t>::type;

usingcol_t = std::tuple_element<1, element_t>::type;

usingval_t = std::tuple_element<2, element_t>::type;

staticrow_t row(constelement_t& el) { return std::get<0>(el); }

staticcol_t col(constelement_t& el) { return std::get<1>(el); }

staticval_tval(constelement_t& el) { return std::get<2>(el); }

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

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

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

staticconstrow_t NONEXISTENT_ROW = (row_t)-1;

staticconstcol_t NONEXISTENT_COL = (col_t)-1;

};

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

{

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

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

}

returnelement_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(constelement_t& a, constelement_t& b)

{

returnis_this_coord(b, (int)element_traits::row(a), (int)element_traits::col(a));

}

bool operator==(constelement_t& a, constelement_t& b)

{

returnis_same(a, b);

}

bool operator>(constelement_t& a, constelement_t& b)

{

returnis_further_coord(b, element_traits::row(a), element_traits::col(a));

}

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

#pragma once

#include <assert.h>

#include <algorithm>

voidsp_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_tnremoved = 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();

}

}

voidsp_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);

}

voidsp_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);

autoa_it = a.elems.begin();

autob_it = b.elems.begin();

autoa_row_start_it = a.elems.begin();

element_traits::row_ttarget_row = element_traits::row(*a_it);

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

boolgo_to_next_row = false;

element_traits::val_tacc = 0;

booltarget_col_changed = false;

boolacc_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);

}

Курсовой структуры

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

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

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

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

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

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

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

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

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

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

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