Докажите что это программа

Вопрос 39. Методы доказательства правильности программ

2. Методы доказательства частичной правильности программ.

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

Общая характеристика формальных методов доказательства

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

Докажите, что есть Бог (Интервью телеканалу «Тонус», 1999.01.14) / А.И. Осипов

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

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

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

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

Докажите, что это мой сын! (полный выпуск) | Говорить Україна

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

Модель формального доказательства конкретности программы

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

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

Дата добавления: 2018-02-15 ; просмотров: 1403 ; Мы поможем в написании вашей работы!

Источник: studopedia.net

Основные принципы доказательства правильности для блок-схем

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

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

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

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

Таким образом, для простых программ с одним циклом основными приемами при доказательстве правильности блок-схем являются:

1) доказательство того, что при попадании во входную точку цикла всегда будет справедливо некоторое утверждение (инвариант цикла). Чтобы доказать это, мы показывали, во-первых, что это утверждение справедливо при первом попадании на вход цикла, и, во-вторых, если мы попали в эту точку и утвержде­ние справедливо, то после выполнения цикла и возврата во входную точку утверждение будет оставаться справедливым;

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

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

ПРИМЕР 2. Предположим, что нужно вычислить произведение двух любых целых чисел M, N, причем M³0 и операцию умножения использовать нельзя. Для этого можно использовать операцию сложения и вычислить сумму из M слагаемых (каждое равно N). В результате получим M∙N. Рассмотрим блок-схему, реализующую такое вычисление (рис. 2.1).

Нужно доказать, что приведенная программа правильно вычисляет произведение двух любых целых чисел M и N при условии M³0, т. е. если программа выполняется с целыми числами M и N, где M³0, то она в конце концов окончится (достигнув точки 5) со значением J=M∙N.

Для того, чтобы яснее представлять этапы доказательства правильности, будем «приписывать» ключевые утверждения, которые необходимо доказать, непосредственно тем точкам блок-схемы, к которым они относятся (рис. 2.2).

Замечание: доказывая справедливость некоторого высказывания в момент прохож­дения через какую-либо из точек внутреннего цикла (инварианта цикла), мы воспользуемся принципом простой индукции и будем считать, что нужно лишь показать, что: 1) высказывание справедливо при первом попадании в эту точку, и 2) если мы попали в эту точку и в этот момент высказывание справедливо, а затем выполняется цикл и мы вновь возвращаемся в исходную точку, то высказывание будет вновь справедливо. (то есть проще: выполнение цикла не нарушает истинности высказы­вания – инварианта цикла.) Если мы доказали оба этих утверждения, то, восстанавливая необхо­димые детали, можем доказать с помощью индукции по числу прохождений через точку, что исходное высказывание справедливо при любом попадании в данную точку.

Рис. 2.1 Рис. 2.2

Докажем теперь, что приведенная на рис. 2.2 блок-схема правильна, т. е. если ее начать выполнять с M и N, имеющими некоторые целые значения, причем M³0, то выпол­нение в конечном итоге закончится с J = M ∙ N.

Вначале докажем, что при попадании в точку 2 J = I ∙ N.

1. При первом попадании в точку 2 при переходе из точки 1 имеем I = 0 и J = 0. Таким образом, утверждение J = I ∙ N = 0 ∙ N = 0 справедливо.

2. Предположим, что мы попали в точку 2 и утверждение J = I ∙ N справедливо. Пусть I и J в этой точке принимают значения In и Jn, т.е. Jn = In∙ N. Если I ¹ M ложно, то это уже обеспечивает конечный результат.

Предположим теперь, что мы прошли по циклу (от точки 2 через точки 3, 4 вновь в точку 2), что возможно только при выполнении условия I ¹ M. При возвращении в точку 2 I и J принимают новые значения In+1 и Jn+1, которые можно представить следующим образом:

Следовательно, при очередном попадании в точку 2 высказы­вание J=I∙ N вновь справедливо, что и требовалось доказать, т. е. при любом попадании в точку 2 справедливо высказыва­ние J = I ∙ N.

Теперь докажем, что в конце концов попадем в точку 2 со значением I=M. При первом попадании в точку 2 имеем I=0. При последующих попаданиях, если таковые есть, I каждый раз увеличивается на 1. Так как значение M нигде в программе не изменяется и мы предположили, что M³0, то очевидно, что в какой-то момент I станет равным M.

Если мы попадем в точку 2 при I = M, то будет верно и J = I ∙ N = M ∙ N. Отношение I ¹ M в этот момент ложно, и мы попадаем по стрелке с пометкой F (FALSE – ложь) в точку 5 с J = M ∙ N. На этом доказательство правильности программы заканчивается.

Дополнительные примеры доказательства правильности блок-схем простых программ (с одним циклом) можно посмотреть в [1].

Упражнения

1. Докажите, что программа (рис. 2.3) вычисляет произведение M на N при условии, что M и N имеют целые значения и M ³ 0. Что произойдет, если M < 0?

2. Предположим, что на блок-схеме (рис. 2.3) по ошибке вместо проверки i = 0 стоит проверка i = 1. На каких этапах доказательства правильности это выяснится? Предположим, что J по ошибке получает начальное значение 1, а не 0. Где это выяснится при доказательстве? Представим себе, что J присвоено вначале значение N, а не 0 и, кроме того, проверка идет на i = 1. Для каких значений данных программа будет верно вычислять произведение M ∙ N ? Как это показать, исходя из доказательства правильности?

3. Докажите, что программа (рис. 2.4) вычисляет и печатает значение M N . Предполагается, что M и N – целые числа, причем и1 £ M и 1 £ N. Будет ли эта программа работать правильно, если в качестве N введено значение 0? Измените блок-схему так, чтобы программа работала правильно и при N = 0.

Рис. 2.3 Рис. 2.4

4. Докажите, что программа (рис. 2.5) вычисляет и печатает значение
M! = 1 × 2 × 3 × . × (M – 1) × M при условии, что в качестве M вводится положительное целое число.

5. Докажите, что если в программу (рис. 2.6) в качестве значений I и J вводятся соответственно I0 и J0, причем 0 £ I0, то печатаемые в конце значения
I и J будут соответственно 0 и J0 + 2 × I0.

Рис. 2.5 Рис. 2.6

6. Для программ, блок-схемы которых приведены на рис. 2.7–2.8, определите, при каких значениях данных программа будет заканчиваться. Найдите эти значения также для случаев, когда:

а) на рис. 2.7 проверка I £ M заменена на I £ M;

б) на рис. 2.8 команда I ← I + 1 заменена на I ← I + 2;

Рис. 2.7 Рис. 2.8

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования.

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.).

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем.

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам.

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:

Источник: zdamsam.ru

Элементы доказательного программирования

Доказательное программирование — это составление программ с доказательством их правильности. Сложность составления и доказа­тельства правильности алгоритмов и программ состоит в следующем.

Для заключений оналичии ошибок в алгоритме или в программе достаточно указать тест, при котором произойдет сбой, отказ или будут получены неправильные результаты. Поиск и исправление ошибок в программах обычно проводится на ЭВМ.

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

Существуютдва подхода к проверке программ — прагматический и доказательный. При прагматическом подходе проверка программ выполняется на ЭВМ путем тестирования.

Тестирование — это проверка программ на ЭВМ с помощью не­которого набора тестов. Ясно, что тестирование не дает гарантий правильности выполнения программ на всех допустимых данных. Следовательно, тестирование в общем случае не может дать и не дает полных гарантий отсутствия ошибок в программах.

Напомним, чтоотладка программ — это процесс поиска и исправ­ления ошибок в программах на ЭВМ. Однако поскольку поиск оши­бок при отладке программ проводится с помощью тестов, то полных гарантий нахождения и исправления всех ошибок в программах отладка не дает и в принципе дать не может.

По этой же причинене ясно, когда процесс отладки программ — процесс поиска и исправления ошибок на ЭВМ — может считаться завершенным. А выявлены или нет все ошибки в программе при ее отладке не может сказать никто.

Таким образом, прагматический подход чреват созданием про­грамм, содержащих ошибки даже после «завершения» отладки, что и наблюдается практически во всех больших программах для ЭВМ.

Рассмотрим в качестве иллюстрации принципов тестирования алгоритм и программу вычисления максимума из трех чисел: а, b, с.

алг «максимум трех чисел» ‘максимум трех чисел

нач cls

ввод (а, b, с) input a, b, с

если а > b то if а > b then

тах := a max = a

инеc b > с то elseif b > с then

тах := b mах = b

инеc с > а то elseif с > a then

тах:= с mах = с

кесли end if

вывод («тах=»,тах) ? «mах=»; mах

кон end

Запуск этой программы на ЭВМ можно проверить на следующих данных:

? 1 1 2 ? 1 2 3 ? 3 2 1

max = 2 max = 3 max = 3

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

Контрпример1

Но этот результат — неправильный. Следовательно, алгоритм и программа содержат ошибки. Но сколько этих ошибок — одна, две, а может быть больше?

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

Доказательства правильности алгоритмов и программ, равно как и любые другие доказательства, строятся на основе суждений и рас­суждений. В данном случае суждения и рассуждения касаются результатов выполнения алгоритмов и программ с теми или иными данными.

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

В качестве примера проведем анализ результатов алгоритма, со­стоящего из трех присваиваний.

алг «у= х 5 » Результаты Утверждения

Нач

v := х×х v1 = х×х Þ v1 = x 2

у := v×x у = v2×x Þ у = х 5

Кон

Справа от алгоритма приведены результаты выполнения присва­иваний. Результатом первого присваивания v := х×х будет значение v1 = х×х переменной v. Результат следующего присваивания v := v×v — второе значение переменной v, равное v2 = v1×v1 . Результатом треть­его присваивания у := v×x будет значение у = v2×x .

На основе приведенных рассуждений, можно сделать три утверж­дения о промежуточных и конечных результатах вычислений:

Таким образом можно высказать окончательное

Утверждение. Конечным результатом выполнения будет

у = х 5 для любых значений х.

Доказательство. Исходя из описания результатов выполнения присваиваний значение у будет равно

Чтоитребовалось доказать.

Техникаанализаидоказательства правильности алгоритмов и программ во многом совпадает с техникой доказательства любых других утверждений и состоит в применении следующих четырех приемов:

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

алг «у = тах(а, b,с)» Результаты

Нач

если а > b то при а > b

у := а у = а

инес b > с то при b > с

у := b у = b

инес с > а то при с > а

у := с у = с

кеслипри не (b > с)

Кон

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

у = b, при b > с и b ³ а,

с, при с > а и с ³ b.

В то же время значение максимума должно быть равно:

а, при а ³ b и а ³ с,

mах = b, при b ³ с и b ³ а,

с, при с ³ а и с ³ b.

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

Дляопровержения общего утверждения достаточно указать хотя бы один контрпример. В данном случае утверждение о правильности алгоритма гласило бы: для любых значений переменных а, b, с конечным было бы значение mах (а, b, с).

Контрпримером в данном случае будут значения: а = 2, b = 1, с = 3. Для этих данных по определению mах = 3, а по результатам выполнения алгоритма у = 2. Следовательно, в алгоритме содержится ошибка.

Однако оказывается, что этоне единственная ошибка. Более тон­кие ошибки вскрывает второй контрпример: а = 1, b = 1, c = 1. Для этих данных в алгоритме вовсе не определен результат вычислений у = ? и конечный результат выполнения программы будет непред­сказуем!?

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

Постановка задачиМетод решения

Вычисление mах (а, b, с).

Дано: а, b, с — три числа, mх = mах(mах(а,b),с)

Треб.: mх — максимум, mах(х,у) = х, при х ³ у

Где: mх = mах (а, b, с). у, при у ³ х

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

алг «тх = тах(а,b,с)» Результаты

Нач

если а³ b то при а ³ b

тх :=а mx = a

иначе при b > а

mх :=b mх = b

кесли при с < mх

если с ³ mх то при с ³ mх

mх := сmх’ = с

Кесли

Кон

Доказательство правильности алгоритмов можно проводить двумя способами. Первый способ — анализ правильности при по­строении алгоритмов. Второй способ — анализ правильности после построения алгоритмов.

Первый способ — показать, что алгоритм является корректной реализацией метода решения, и доказать, что метод — правильный. Для рассмотренного алгоритма это доказательство изложено выше.

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

Второй способ — исчерпывающий анализ результатов выпол­нения алгоритма на соответствие постановке решаемых задач для любых допустимых данных. Это — доказательство путем исчерпыва­ющего анализа результатов выполнения алгоритмов и программ.

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

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

Лемма: Конечными результатами выполнения алгоритма

АлгоритмРезультаты

если а > b топри а ³ b

тх := а mx = a

иначепри b > a

тх := b mx = b

Кесли

является значение mx = max(а, b) для любых значений а и b.

Доказательство. Результатом вычислений здесь будут значения

что совпадает с определением max (а, b).

С помощью этой леммы легко доказать правильность алгоритма в целом.

если с³mx то при с ³ mx

mx := с mx’ = с

кеслиmx’ = mx

Утверждение. Конечным результатом выполнения алгоритма вы­числения максимума будет значение mx’ = max (а, b, с) для любых значений а, b и с.

Доказательство. В силу предположения предшествующее значе­ние переменной mx = max(a,b). Отсюда получаем, что

Что и требовалось доказать.

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

Одним из важнейших применений аппарата лемм является анализ результатов выполнения и доказательство правильности алгоритмов с циклами. Используемые для анализа циклов леммы называютсяиндуктивными утверждениями. Эти леммы выражают утверждения о промежуточных результатах выполнения циклов.

В качестве примера использования индуктивных рассуждений рассмотрим алгоритм вычисления среднего арифметического после­довательности чисел. В приводимом алгоритме предполагается, что последовательность чисел размещена в массиве X[1:N].

Источник: studopedia.ru

Характеристика базовых методов доказательства

Наиболее известными формальными методами доказательства программ являются метод рекурсивной индукции или индуктивных утверждений Флойда, метод структурной индукции Хоара, метод рекурсивных индукций Маккарти и др. [1]

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

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

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

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

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

Метод Хоара — это усовершенствованный метод Флойда, основанный на аксиоматическом описании семантики ЯП исходных программ. Каждая аксиома описывает изменение значений переменных с помощью операторов этого языка. Основное внимание уделяется формализации операторов перехода и вызовов процедур с помощью правил вывода, каждое из которых задает индуктивное высказывание для каждой метки (точки) и функции исходной программы.

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

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

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

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

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

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

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

Метод Дейкстры основывается на перевычислении, математической индукции и абстрактном описании программы.

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

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

Абстракция позволяет ослабить количественные ограничения, которые накладываются методом перевычислений.

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

Метод математической индукции позволяет доказать истинность некоторого предположения Р(п) в зависимости от параметра п для всех п>п0

и тем самым доказать случай Р(п0). Исходя из истинности Р(п) для любого значения п, доказывается Р(п + 1), что достаточно для доказательства истинности Р(п) для всех п > п0.

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

• 1) что справедливо А( 1) при первом проходе через заданную точку;
• 2) если справедливо А(п) (при и-проходах через заданную точку), то справедливо и А(п + 1) при прохождении через заданную точку п + 1 раз.

Чтобы доказать, что некоторая программа правильная, надо корректно описать то, что эта программа делает, т.е. ее логику. Такое описание называется правильным высказыванием или утверждением. Утверждение о правильности программы будет справедливым, если она успешно завершится.

Проверка правильности программ — это автоматизированный метод Хоара в системе автоматизации — СПРУТ, основанный на системе проверки утверждений о программах на ЯП Паскаль.

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

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

• [1] См.: Лаврищева Е. At. Программная инженерия. Парадигмы, технологии и CASE-средства.

Источник: studme.org