В общем виде алгоритм определяет некоторую величину 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,, состоящая из конечного числа простейших операций q1,... qj. Число сомр((y)) = S comp(qi) называется комбинаторной сложностью алгоритма (y).
|
|
В качестве простейших операций часто выбирают четыре арифметические операции над вещественными числами, считая при этом, что сложность каждой из них равна единице. Предполагается, что мы можем точно и с единичными затратами выполнять эти действия. На практике почти всегда производят вычисления с плавающей точкой. Так можно получить только приближенные результаты, и при этом встает вопрос об устойчивости алгоритмов.
Надежность программного обеспечения – это его свойство производить вычисления, сохраняя значения установленных эксплутационных показателей в заданных пределах, соответствующих заданным режимам и условиям использования, обслуживания, ремонта, хранения и копирования.
При проектировании любой системы обязательно устанавливаются показатели ее качества, для программ такими показателями могут быть время расчета одного варианта и точность вычислений. Быстродействие оценить относительно просто. Сложнее определить точность, для этого в процессе отладки обычно используются эталонные результаты, полученные или с помощью другого программного обеспечения или путем измерения при работе тех объектов, для моделирования которых и создавалось программное обеспечение. Наиболее распространенным показателем надежности программ является вероятность правильного функционирования при определенных условиях R. С этим показателем непосредственно связан другой – средняя наработка на отказ Т, т.е. проявление неправильного вычисления.
Третий показатель – это интенсивность отказов Z, с помощью которого определяется распределение отказов по какому-то аргументу (например, во времени). Любые оценки показателей надежности программ могут иметь только вероятностный характер. Информация о любом дефекте должна однозначно вести к устранению этого дефекта. А в программе остаются те дефекты, о которых ничего не известно или известно недостаточно много, чтобы их найти и устранить. Получение оценок показателей надежности программ производится с помощью моделей – математических выражений, связывающих значение одного из показателей надежности с непосредственно измеряемыми параметрами, которые характеризуют программное обеспечение.
|
|
Модели можно разделить на: априорные,
эмпирические,
непрерывные эмпирические,
дискретные эмпирические,
полные.
Идея предсказания надежности программы до ее первого испытания появлялась давно, но до сих пор не создано корректных априорных моделей надежности, пригодных для практического использования. Ясно, что надежность программы зависит от того, кто ее разрабатывал, в каких условиях, какой получилась программа по размерам, по сложности, с использованием каких приемов она создавалась. Но как измерить эти факторы и как они непосредственно влияют на показатели надежности – неясно.
Наиболее известной непрерывной эмпирической моделью надежности является модель Шумана, в которой интенсивность отказов зависит от скорости исполнения команд, числа команд в программе и числа дефектов, оставшихся в программе.
С помощью верификации либо доказывается абсолютная правильность программ и тогда никакие модели надежности не требуются, либо относительно программы в целом не доказывается ничего. Кроме того, дефекты семантического происхождения (например, по вине заказчика) с помощью верификации не могут бытьобнаружены вообще.
Универсальные алгоритмы
Основные понятия(Кирьянов)
Можно выделить три основных типа универсальных алгоритмических моделей:
1- й тип связывает понятие алгоритма с наиболее традиционными понятями математики – вычислениями и числовыми функциями;
2- й тип основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент времени лишь весьма примитивные операции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Кроме того эвристика этих моделей близка к ЭВМ. Основной теоретической моделью этого типа является машина Тьюринга.
3- й тип – это преобразования слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замены куска слова другим словом. Преимущества этого типа – в его максимальной абстрактности и возможности применить понятие алгоритма к объектам произвольной природы.
Машины Тьюринга
Понятие машины Тьюринга возникло в результате прямой попытки разложить известные нам вычислительные процедуры на элементарные операции. Тьюринг привел ряд доводов в пользу того, что повторения его элементарных операций было бы достаточно для проведения любого возможного вычисления.
До сих пор все вычислительные машины в некотором смысле базируются на идее Тьюринга: их память физически состоит из битов, каждый из которых содержит либо 0 либо 1. Более того, т.н. микропрограммное управление унаследовало от этих абстрактных машин и программу, помещенную в "постоянную память", и в значительной мере структуру команды.
Машина Тьюринга представляет собой автомат, с конечным числом состояний, соединенный с внешней памятью – лентой, разбитой на ячейки, в каждой из которых записан один из символов конечного алфавита А= { a1,... am}.
Автомат связан с лентой с помощью головки, которая в каждый момент времени обозревает одну ячейку ленты, и в зависимости от символа в этой ячейке и состояния управляющего устройства записывает в ячейку символ (совпадающий с прежним или пустой), сдвигается на ячейку вправо или влево или остается на месте. Среди состояний управляющего устройства выделим начальное состояние q1 и заключительное состояние qz. В начальном состоянии машина находится перед началом работы. Попав в заключительное состояние, машина останавливается. Т.о. память машины Т – это конечное множество состояний (внутренняя память) и лента (внешняя память). Лента бесконечна в обе стороны, однако в любой момент времени лишь конечный отрезок ленты будет заполнен символами. Поэтому важна не фактическая бесконечность ленты, а ее неограниченность, т.е. возможность писать на ней сколь угодно длинные, но конечные слова.
Данные в машине Т – это слова в алфавите ленты; на ленте записываются и исходные данные и окончательные результаты. Элементарные шаги – это считывание и запись символов, сдвиг головки на ячейку влево или вправо, а также переход управляющего устройства в следующее состояние.
Детерминированность машины Т определяется следующим образом: для любого внутреннего состояния qi и символа aj однозначно заданы
а) следующее состояние qi`
б) символ aj`, который надо записать в ту же ячейку вместо aj (стирание – это запись пустого символа)
в) направление сдвига головки dk (L – влево, R – вправо, E – на месте).
Это задание может описываться либо системой правил
qiaj qi`aj`dk
либо таблицей, строкам которой соответствуют состояния, столбцам – входные символы, а на пересечении записана тройка символов qi`aj`dk.
либо блок-схемой (диаграммой переходов), в которой состояниям соотвествуют вершины, а правилу вида (qiaj qi`aj`dk) – ребро, ведущее из qi в qi`.
Полное состояние машины Т, по которому однозначно можно определить ее дальнейшее поведение, определяется ее внутренним состоянием, состоянием ленты (т.е. символом, записанным на ленте) и положением головки на ленте.
Полное состояние будем называть конфигурацией или машинным словом. Стандартной начальной конфигурацией называется конфигурация вида q1, то есть конфигурацию, содержащую начальное состояние, в котором головка обозревает крайний левый символ слова, написанного на ленте. Аналогично, стандартной заключительной конфигурацией называется конфигурация вида qz. Ко всякой незаключительной конфигурации К машины Т применима ровно одна команда вида
qiaj qi`aj`dk,
которая конфигурацию К переводит в конфигурацию К. По-следовательность К1 К2 К3... однозначно определяется исходной конфигурацией К1 и полностью описывает работу машины Т, начиная с К1.
Для того чтобы говорить о том, что могут делать машины Т, уточним как будет интерпретироваться их поведение и как будут представляться данные.
Исходными данными машины Т будем считать записанные на ленте слова в алфавите исходных данных и векторы из таких слов. Для любого набора V над Аисх машина Т либо работает бесконечно, либо перерабатывает его в совокупность слов в алфавите результатов (Аисх и Арез могут пересекаться и даже совпадать).
Пусть f – функция, отображающая множество векторов над Аисх в множество векторов над Арез. Машина Т правильно вычисляет функцию f, если
1) для любых V и W таких, что f(V)=W q1V* q1zW*, где V* и W* – правильные записи V, W.
2) для любого V такого, что f(V) не определена, машина Т,запущенная в стандартной начальной конфигурации q1V*, работает бесконечно долго.
Если для f существует машина Т, которая ее правильно вычисляет, f называется правильно вычислимой по Тьюрингу. С другой стороны, любой правильно вычисляющей машине Т можно поставить в соответствие вычисляемую ею функцию.
Пусть f() задана описанием: "если P() истинно, то f()=g1(), иначе f()=g2() ". Функция называется разветвлением или условным переходом к g1() и g2() по условию P().
Благодаря вычислимости композиции и разветвления словесные описания и язык блок-схем можно сделать вполне точным языком для описания работы машин Тьюринга.
Cистему команд машин Тьюринга можно интерпретировать и как описание работы конкретного механизма и как программу. Естественно поставить задачу построения машины Тьюринга, реализующей алгоритм воспроизведения работы машины Тьюринга – такая машина называется универсальной. Существование универсальной машины Тьюринга означает, что систему команд любой машины Тьюринга можно представить двояко: либо как описание работы конкретного устройства машины Т, либо как программу для универсальной машины U. Это естетственно: для инженера, проектирующего систему управления, любой алгоритм управления может быть реализован либо аппаратурно – построением соответствующей схемы, либо программно – написанием программы для универсальной управляющей ЭВМ.
Такая интерпретация на абстрактном уровне сохраняет основные плюсы и минусы инженерной реализации: конкретная машина Т работает гораздо быстрее; управляющее устройство U довольно громоздко, однако его величина постоянна и, будучи раз построено, оно годится для реализации сколь угодно больших алгоритмов. Кроме того при смене алгоритма не понадобится строить новых устройств, нужно будет лишь написать новую программу.
Тезис Тьюринга: Всякий алгоритм может быть реализован машиной Тьюринга. Доказать тезис нельзя, поскольку само понятие алгоритма является неточным. Подтверждением тезиса являются во-первых, математическая практика, а во-вторых, то, что описание алгоритма в терминах любой другой известной алгоритмической модели может быть сведено к его описанию в виде машины Тьюринга.
В числе общих требований, предъявляемых к алгоритмам упоминалось требование результативности. В наиболее радикальном виде: по любому алгоритму А и данным определить, приведет ли работа А при исходных данных к результату или нет. Иначе говоря, нужно построить алгоритм В такой, что В(А,)=И, если А() дает результат, и В(А,)=Л, если нет.
В силу тезиса Тьюринга эту задачу можно сформулировать как задачу о построении машины Тьюринга. Эта задача называется проблемой остановки.
Теорема: Не существует машины Тьюринга, решающей проблему остановки для произвольной машины Тьюринга.
Эта теорема дает первый пример алгоритмически неразрешимой проблемы. Следует иметь в виду, что речь идет об отсутствии единого алгоритма, решающего данную проблему, при этом не исключается возможность решения в частном случае. И неразрешимость общей проблемы остановки не снимает необходимости доказывать сходимость предлагаемых алгоритмов.