Сходимость, сложность, надежность(Федосеева)

В общем виде метод определяет некую величину 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).

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

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

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

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

Модели можно поделить на: априорные,

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

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

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

полные.

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

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

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

Универсальные методы

Главные понятия(Кирьянов)

Можно выделить три главных типа универсальных алгоритмических моделей:

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 достаточно громоздко, но его величина постоянна и, будучи раз выстроено, оно годится для Сходимость, сложность, надежность(Федосеева) реализации сколь угодно огромных алгоритмов. Не считая того при смене метода не пригодится строить новых устройств, необходимо будет только написать новейшую программку.

Тезис Тьюринга: Всякий метод может быть реализован машиной Тьюринга. Обосновать тезис нельзя, так как само понятие метода является неточным. Доказательством тезиса являются во-1-х, математическая практика Сходимость, сложность, надежность(Федосеева), а во-2-х, то, что описание метода в определениях хоть какой другой известной алгоритмической модели может быть сведено к его описанию в виде машины Тьюринга.

В числе общих требований, предъявляемых к методам упоминалось требование результативности. В более конструктивном виде: по хоть какому методу А и данным найти, приведет ли работа А Сходимость, сложность, надежность(Федосеева) при начальных данных к результату либо нет. По другому говоря, необходимо выстроить метод В таковой, что В(А,)=И, если А() дает итог, и В(А,)=Л, если нет.

В силу тезиса Тьюринга эту задачку можно сконструировать как задачку о построении машины Тьюринга. Эта задачка именуется неувязкой остановки Сходимость, сложность, надежность(Федосеева).

Аксиома: Не существует машины Тьюринга, решающей делему остановки для случайной машины Тьюринга.

Эта аксиома дает 1-ый пример алгоритмически неразрешимой задачи. Следует подразумевать, что идет речь об отсутствии одного метода, решающего данную делему, при всем этом не исключается возможность решения в личном случае. И неразрешимость общей трудности остановки не снимает необходимости Сходимость, сложность, надежность(Федосеева) обосновывать сходимость предлагаемых алгоритмов.


shkoli-nauki-upravleniya-processnij-podhod-k-upravleniyu-proizvodstvom-referat.html
shkoli-samorealizacii.html
shkoli-v-kitajskoj-filosofii.html