МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Институт Прикладной математики и компьютерных наук
Кафедра Вычислительной техники
Курсовая работа
Программный комплекс осуществления операций над разреженными матрицами
Тула 2019
СОДЕРЖАНИЕ
Введение
В настоящее время объектно-ориентированное программирование (ООП) является доминирующим стилем при создании больших программ и программных систем. Процедурно-ориентированное программирование, широко использовавшееся до появления ООП, обычно позволяет создавать более эффективные в вычислительном отношении реализации приложений, что является существенным фактором при разработке систем реального времени. На практике эти два стиля программирования часто используются совместно, позволяя варьировать степень их применения в программах.
Использование объектно-ориентированного (ОО) подхода при разработке программного обеспечения (ПО) позволяет преодолеть естественную сложность разрабатываемого ПО, упростить процесс отладки и последующего сопровождения, расширения и переноса ПОна другие платформы. программное обеспечение инструментальный
В данной курсовой работе в процессе проектирования и реализации конкретного приложения используются комбинация процедурно-ориентированного и объектно-ориентированного подхода и проводится сравнительный анализ их свойств и возможностей применения.
Курсовая работа выполняется для закрепления знаний и приобретения навыков объектно-ориентированной реализаций прикладной задачи (задачи нахождения реализации базовых матричных операций для разреженных матриц) с использованием различных языков, инструментальных систем и библиотек, автоматизирующих проектирование, программирование и отладку создаваемых приложений.
Задачами курсовой работы являются:
- приобретение навыков решения вычислительных задач
-практическое освоение современных инструментальных систем разработки ПО.
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).