exam02 6 - stankin/design-part-1 GitHub Wiki

Понятие вычислительной сложности алгоритма. Связанные показатели качества программных средств

Выполнила: Максимова Ольга

Проверила: Горланова Анна

Группа ИДБ-17-06

Понятие программного средства

Программное обеспечение автоматизированной системы (АС) - совокупность программ на носителях данных и программных документов, предназначенная для отладки, функционирования и проверки работоспособности АС

Программное изделие АС - программное средство, изготовленное, прошедшее испытания установленного вида поставляемое как продукция производственно-технического назначения для применения в АС

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

Показатели качества программных средств

ГОСТ 28195-89 "Оценка качества программных средств" устанавливает общие положения по оценке качества программных средств (ПС) вычислительной техники, поставляемых через фонды алгоритмов и программ (ФАП), номенклатуру и применяемость показателей качества ПС. Оценка качества ПС представляет собой совокупность операций, включающих выбор номенклатуры показателей качества оцениваемого ПС, определение значений этих показателей и сравнение их с базовыми значениями.

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

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

Устойчивость функционирования
Работоспособность

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

Структурность
Простота конструкции
Наглядность
Повторяемость

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

Наличие описания алгоритмов влияет на конечную оценку данного фактора. Требования к оформлению алгоритмов в документации регулируются стандартом ГОСТ 19.701-90 ЕСПД. "Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения".

Легкость освоения
Доступность эксплуатационных программных документов
Удобство эксплуатации и обслуживания

Показатели эффективности - характеризуют степень удовлетворения потребности пользователя в обработке данных с учетом экономических, вычислительных и людских ресурсов.

Уровень автоматизации
Временная эффективность
Ресурсоемкость

Показатели универсальности - характеризуют адаптируемость ПС к новым функциональным требованиям, возникающим вследствие изменения области применения или других условий функционирования.

Гибкость
Мобильность
Модифицируемость

Показатели корректности - характеризуют степень соответствия ПС требованиям, установленным в ТЗ, требованиям к обработке данных и общесистемным требованиям.

Полнота реализации
Согласованность
Логическая корректность
Проверенность

В оценочные элементы фактора "корректность" в числе прочих входит:

Наличие описания алгоритмов

Реализация всех алгоритмов

Отсутствие противоречий в описании алгоритмов

Отсутствие противоречий в выполнении алгоритмов

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

Понятие алгоритма

Алгоритм - конечное упорядоченное множество точно определенных правил для решения конкретной задачи.

Алгоритмы как часть требований к разработке и документированию

Процесс разработки программных средств регламентируется целым перечнем стандартов, в частности, стандартом ГОСТ Р 51904-2002 "Программное обеспечение встроенных систем. Общие требования к разработке и документированию". К результатам процессов разработки и верификации ПО применяют просмотры и анализы ПО. Различия между просмотрами и анализами заключаются в том, что анализ дает воспроизводимое доказательство, а просмотр предоставляет качественную (экспертную) оценку.

Внимание алгоритмам уделяется на трех этапах просмотра и анализа ПО:

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

Понятие вычислительной сложности алгоритма

Вычислительная сложность алгоритма (Computational complexity) - количество элементарных операций, затрачиваемых алгоритмом для решения конкретной задачи. Сложность зависит не только от размерности входных данных, но и от самих данных. Очевидно, что чем сложнее алгоритм в вычислительном плане, тем больше времени и вычислительных ресурсов потребует его выполнение.

Классификация вычислительной сложности алгоритма

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

Примеры вычислительных сложностей

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

Примеры вычислительных сложностей:

O(n) — линейная сложность. Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.
O(log n) — логарифмическая сложность. Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.
O(n2) — квадратичная сложность. Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n, т. е. n2.
Также случается, что время работы алгоритма вообще не зависит от размера входных данных. Тогда сложность обозначают как O(1). Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.

Классы сложности

Каждый вычислительный алгоритм может быть отнесен к одному из двух классов сложности. В данном случае это множество задач, для решения которых известны алгоритмы, схожие по трудоемкости.

I. В классе P вычислительные затраты линейно растут с увеличением размерности. Например, время, требуемое на уборку снега, прямо пропорционально площади. Если ее увеличить вдвое, то и временные затраты возрастут в два раза.

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

Показатель качества "Корректность": вычислительная сложность алгоритмов.

Одним из оценочных элементов фактора "Корректность" является логическая корректность, подразумевающая функциональное и программное соответствие процесса обработки данных при выполнении задания общесистемным требованиям. Для уточнения таких соответствий крайне уместно использовать значения вычислительной сложности алгоритмов, использованных в программе. Такой способ крайне удобен, поскольку при задании общесистемных требований, как правило упоминается желаемая оптимальная скорость загрузки/отработки тех или иных блоков кода. Поскольку оттестировать разработанный программный продукт на всех вариациях вычислительной техники попросту невозможно, хорошей идеей является применение понятия математической сложности алгоритмов. Это позволит выбрать математически менее сложный алгоритм из подходящих, а также приближенно оценить скорость выполнения ряда задач. Стоит отметить, что такой способ не характеризуется высокой точностью, однако для выбора оптимальной логики разрабатываемых функций он подходит.

Литература

Бхаргава А. Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. - СПб.: Питер, 2020. - 288 с.: ил. - (Серия "Библиотека программиста").— ISBN 978-5-4461-0923-4.

Ссылки

! 1. Добавить ссылку на ГОСТ "Программное изделие АС":
ГОСТ 34.003-90 Информационная технология (ИТ). Комплекс стандартов на автоматизированные системы. Автоматизированные системы. Термины и определения
! 2. Комментарий по требованиям к оформлению алгоритмов в документации и раздел "Классы сложности" можно сократить.