Сходимость, сложность, надежность

В общем виде алгоритм определяет некоторую величину y по известной величине x, символически это можно записать y=A(x). В большинстве случаев бывает достаточно вычислить y*=A*(x*). При этом ожидается, что значение y* будет близко к искомому решению y. Возникает вопрос, что такое "близко"?

Множество элементов x любой природы называется метрическим пространством, если в нем введено расстояние р(х1,х2) между любой парой элементов, удовлетворяющее следующим аксиомам:

а) р(х1,х2) - вещественное неотрицательное число;

б) р(х1,х2)=0, только если х1=х2;

в) р(х1,х2)=р(х2,х1);

г) р(х1,х3)<=р(х1,х2)+ р(х2,х3).

Последовательность метрического пространства хn называют сходящейся по метрике к элементу х, если р(хn,х) 0 при n . Последовательность хn называется фундаментальной, если для любого >0 найдется такое k(), что р(хn,хm)< при всех n и m>k. Метрическое пространство называется полным, если любая фундаментальная последовательность его элементов сходится к элементу того же пространства. Если переменные x и y принадлежат неполным пространствам, то обосновать сходимость метода очень трудно: даже если удается доказать, что при хnх последовательность yn фундаментальная, то отсюда еще не следует, что она сходится к элементу данного пространства, т.е. к решению допустимого класса.

Сложность алгоритмов разделяют на вычислительную и описательную.

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

Вычислительная сложность характеризует сложность переработки алгоритмом А каждого значения исходных данных, к которым он применим (время работы, емкость памяти и т.д.)

Что такое формальное описание алгоритма и сложность описания интуитивно ясно. Ясно и то, что возможны различные способы описания и разные меры сложности. В качестве мер сложности программы машины Тьюринга можно использовать число состояний, произведение числа состояний на число букв алфавита ленты, объем или длину программы. Средства и методы, употребляемые для описания алгоритмов, очень разнообразны. Каждый из них определяет некоторый формальный язык. Характеристики сложности описаний соответственно зависят от выбранного языка.

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

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

Пусть Np – приближенный информационный оператор. Np называется допустимым по отношению к Р, если существует программа вычисления Np(f) " f Î F, состоящая из конечного числа простейших операций.

Число сомр(Np(f)) = сомр(р_i) называется информационной сложностью оператора Np(f).

Алгоритм называется допустимым по отношению к Р, если существует программа вычисления (y) для y = Np(f) " f Î F,, состоящая из конечного числа простейших операций q₁,... q_j. Число сомр((y)) = S comp(q_i) называется комбинаторной сложностью алгоритма (y).

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

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

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

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

Модели можно разделить на:

априорные,

эмпирические,

непрерывные эмпирические,

дискретные эмпирические,

полные.

Идея предсказания надежности программы до ее первого испытания появлялась давно, но до сих пор не создано корректных априорных моделей надежности, пригодных для практического использования. Ясно, что надежность программы зависит от того, кто ее разрабатывал, в каких условиях, какой получилась программа по размерам, по сложности, с использованием каких приемов она создавалась. Но как измерить эти факторы и как они непосредственно влияют на показатели надежности – неясно.

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

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

Дата добавления: 2014-01-06