Элементы доказательного программирования
Доказательное программирование - это составление программ с доказательством их правильности. Сложность составления и доказательства правильности алгоритмов и программ состоит в следующем.
Для заключений о наличии ошибок в алгоритме или в программе достаточно указать тест, при котором произойдет сбой, отказ или будут получены неправильные результаты. Поиск и исправление ошибок в программах обычно проводится на ЭВМ.
Для утверждений о правильности программ
необходимо показать, что правильные результаты будут получаться для всех допустимых данных. Такие утверждения могут быть доказаны только путем исчерпывающего анализа результатов выполнения программ при любых допустимых данных.
Существуют два подхода к проверке программ - прагматический и доказательный. При прагматическом подходе проверка программ выполняется на ЭВМ путем тестирования.
Тестирование - это проверка программ на ЭВМ с помощью некоторого набора тестов. Ясно, что тестирование не дает гарантий правильности выполнения программ на всех допустимых данных. Следовательно, тестирование в общем случае не может дать и не дает полных гарантий отсутствия ошибок в программах.
Напомним, что отладка программ - это процесс поиска и исправления ошибок в программах на ЭВМ. Однако поскольку поиск ошибок при отладке программ проводится с помощью тестов, то полных гарантий нахождения и исправления всех ошибок в программах отладка не дает и в принципе дать не может.
По этой же причине не ясно, когда процесс отладки программ - процесс поиска и исправления ошибок на ЭВМ - может считаться завершенным. А выявлены или нет все ошибки в программе при ее отладке не может сказать никто.
Таким образом, прагматический подход чреват созданием программ, содержащих ошибки даже после «завершения» отладки, что и наблюдается практически во всех больших программах для ЭВМ.
Рассмотрим в качестве иллюстрации принципов тестирования алгоритм и программу вычисления максимума из трех чисел: а, 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
Запуск этой программы на ЭВМ можно проверить на следующих данных:
Tecт1 Тест2 Тест3
? 1 1 2 ? 1 2 3 ? 3 2 1
max = 2 max = 3 max = 3
Все три результата правильные. Отладку программы после запуска этих примеров можно было бы считать завершенной. Однако есть контрпример:
Контрпример1
? 2 1 3
max = 2
Но этот результат - неправильный. Следовательно, алгоритм и программа содержат ошибки. Но сколько этих ошибок - одна, две, а может быть больше?
При доказательном подходе разработка алгоритмов и программ предполагает составление спецификаций и доказательство их правильности по отношению к этим спецификациям. Процесс разработки программ считается завершенным после проверки их на ЭВМ и предоставлении доказательств отсутствия ошибок.
Доказательства правильности алгоритмов и программ, равно как и любые другие доказательства, строятся на основе суждений и рассуждений.
В данном случае суждения и рассуждения касаются результатов выполнения алгоритмов и программ с теми или иными данными.
Конструктивно, доказательства правильности алгоритмов и программ строятся на суждениях и утверждениях о результатах выполнения каждого из составляющих их действий и операций в соответствии с порядком их выполнения.
В качестве примера проведем анализ результатов алгоритма, состоящего из трех присваиваний.
алг «у = х5» Результаты Утверждения
нач
:= х×х v1 = х×х Þ v1 = x2
v := v×v v2
= v1×v1 Þ v2 = x4
у := v×x у = v2×x Þ у = х5
кон
Справа от алгоритма приведены результаты выполнения присваиваний. Результатом первого присваивания v := х×х будет значение v1
= х×х переменной v. Результат следующего присваивания v := v×v - второе значение переменной v, равное v2 = v1×v1 . Результатом третьего присваивания у := v×x будет значение у = v2×x .
На основе приведенных рассуждений, можно сделать три утверждения о промежуточных и конечных результатах вычислений:
Результаты Утверждения
{ v1 = х×х Þ v1 = х2
{ v2 = v1×v1 Þ v2 = x4
{ у = v2×x Þ у = х5
Таким образом можно высказать окончательное
Утверждение. Конечным результатом выполнения будет
у = х5 для любых значений х.
Доказательство. Исходя из описания результатов выполнения присваиваний значение у будет равно
у = v2×x = (v1×v,)×x = ((х×х).(х×х))) ×х = x5.
Что и
требовалось доказать.
Техника анализа и
доказательства правильности алгоритмов и программ во многом совпадает с техникой доказательства любых других утверждений и состоит в применении следующих четырех приемов:
· разбор случаев;
· подбор контрпримеров;
· выделение лемм;
· индуктивный вывод.
Разбор случаев применяется для анализа результатов выполнения конструкций альтернативного выбора. В качестве примера проведем анализ приведенного выше алгоритма «выбора» максимума трех чисел, содержащего выбор альтернатив.
алг «у = тах(а, 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,с)» Результаты
нач
тх := а mx = a
mх := b mх = b
кесли { mх = mах(а,b) } при с < mх
mх
mх := с mх' = с
кесли
кон
Доказательство правильности алгоритмов можно проводить двумя способами. Первый способ - анализ правильности при построении алгоритмов. Второй способ - анализ правильности после построения алгоритмов.
Первый способ - показать, что алгоритм является корректной реализацией метода решения, и доказать, что метод - правильный.
Для рассмотренного алгоритма это доказательство изложено выше.
Привлечение для создания алгоритмов известных методов решения, для которых доказана их правильность, позволяет существенно упростить обоснование правильности программ. При этом центр тяжести проблем смещается к созданию и обоснованию гарантированно правильных методов решения задач.
Второй способ - исчерпывающий анализ результатов выполнения алгоритма на соответствие постановке решаемых задач для любых допустимых данных. Это - доказательство путем исчерпывающего анализа результатов выполнения алгоритмов и программ.
Результаты выполнения рассматриваемого алгоритма вычисления максимума трех чисел приведены справа от него. Анализ результатов алгоритмов, содержащих конструкцию выбора, требует разбора случаев. Отметим, что все эти случаи были уже указаны ранее при разборе ошибочной версии алгоритма.
Для обоснования правильности алгоритма докажем вспомогательное утверждение о результатах выполнения конструкции альтернативного выбора
Лемма: Конечными результатами выполнения алгоритма
Алгоритм Результаты
тх := а mx = a
тх
:= b mx = b
кесли
является значение mx = max(а, b) для любых значений а и b.
Доказательство. Результатом вычислений здесь будут значения
mx =
b при а < b
что совпадает с определением max (а, b).
С помощью этой леммы легко доказать правильность алгоритма в целом.
если с ³ mx то при с ³ mx
mx := с mx' = с
при с < mx
Утверждение. Конечным результатом выполнения алгоритма вычисления максимума будет значение mx' = max (а, b, с) для любых значений а, b и с.
Доказательство. В силу предположения предшествующее значение переменной mx = max(a,b). Отсюда получаем, что
mx¢ = = max(a,b,c).
mx, при с < mx
Что и требовалось доказать.
Доказательство лемм - основной прием доказательства правильности сложных алгоритмов и программ. Напомним, что лемма — это вспомогательное утверждение, предполагающее отдельное доказательство.
Одним из важнейших применений аппарата лемм является анализ результатов выполнения и доказательство правильности алгоритмов с циклами. Используемые для анализа циклов леммы называются индуктивными утверждениями. Эти леммы выражают утверждения о промежуточных результатах выполнения циклов.
В качестве примера использования индуктивных рассуждений рассмотрим алгоритм вычисления среднего арифметического последовательности чисел. В приводимом алгоритме предполагается, что последовательность чисел размещена в массиве X[1:N].
алг «среднее значение»
массив X[1:N]
нач Результаты:
S := S * (k-l)/k + X[k]/k Sk
= Sk-1*(k-l)/k + X[k]/k
кцикл [k = (1...N)]
Xcp := S Xcp = S
кон
Этот алгоритм обычно считается ошибочным (?!). «Ошибкой» в этом алгоритме считается отсутствие присваивания S := 0 перед началом цикла.
Разберем результаты выполнения алгоритма на первых трех шагах:
S1 = S0×(l - 1)/1 + Х[1]/1 = S0×0/1 + Х[1]/1 = Х[1]/1;
S2 = S1×(2 - 1)/2 + Х[2]/2 = S1×1/2 + Х[2]/2 = Х[1]/2 + Х[2]/2;
S3 = S2×(3 - 1)/3 + Х[3]/3 = S2×2/3 + Х[3]/3 = Х[1]/3 + Х[2]/3 + Х[3]/3.
Можно утверждать, что на первых трех шагах результатом является среднее арифметическое обрабатываемых чисел. На основе этих примеров можно сделать индуктивное утверждение - «на каждом очередном k-м шаге выполнения цикла результатом будет среднее арифметическое»
Sk
= Sk-1×(k-l)/k + X[k]/k = X[l]/k + X[2]/k + ... + X[k]/k.
Доказательство этого утверждения проводится с помощью мате матической индукции. На первом шаге при k = 1 оно уже доказано. Допустим, что оно справедливо на (k -1)-м шаге
Sk-1
= X[l]/(k-l) + X[2]/(k-l) + ... + X[k-l]/(k-l).
Подставим его в описание результатов цикла на k-м шаге
Sk= Sk-1×(k-l)/k +X[k]/k.
Тогда результат выполнения цикла на k-м шаге оказывается равным
Sk
= X[l]/k + X[2]/k + ... + X[k-l]/k + X[k]/k,
т. е. среднему арифметическому первых k чисел.
Таким образом, индуктивное утверждение доказано. В силу математической индукции это утверждение верно для всех k = l, 2, ..., N. Следовательно, на последнем шаге конечным результатом выполнения цикла станет значение
SN
= SN-1×(N-1) + X[N]/N = X[1]/N + ... + X[N]/N.
Исходя из этого утверждения конечным результатом выполнения алгоритма в целом будет среднее арифметическое значение
Xcp = SN = X[1]/N + ... + X[N]/N.
Следовательно, приведенный алгоритм, несмотря на содержащуюся в нем «ошибку», является правильным. В целом анализ правильности алгоритмов с циклами во многом построен на использовании индукции.
Индукция - это вывод общих суждений из частных примеров. При анализе циклов она используется для подбора индуктивных утверждений о промежуточных результатах выполнения циклов. Однако для доказательства правильности индуктивных утверждений о результатах выполнения циклов используется полная математическая индукция.
Математическая индукция - это принцип доказательства последовательностей утверждений Р(1), Р(2), Р(3), ..., P(N), .... когда известно, что верны первые утверждения для n = 1, 2, 3 и из истинности (n - 1)-го утверждения следует истинность n-го утверждения:
Принцип математической индукции:
если первое утверждение Р(1) истинно
и из утверждения Р(n - 1) следует
утверждение Р(n), то истинны все
утверждения Р(1), Р(2), Р(3), ..., Р(n), ... .
Приведем примеры индуктивного анализа циклов для алгоритма нахождения минимального значения в последовательности чисел, который в этот раз действительно будет ошибочным.
алг «нахождение минимума»
массив x[1:N]
нач Результаты:
от k = 1 до N цикл
тп := x[k] mnk = { x[k], при x[k] < mnk-1,
все { mnk-1, в ином случае
кцикл [ k = (1 ... N)]
Min := тп Min = mnN
кон
Утверждение. Приведенный алгоритм определения минимального значения последовательности чисел неправильный.
Доказательство. Для демонстрации ошибок необходимо привести контрпример. Для построения контрпримера разберем результаты выполнения на первом шаге цикла.
Результаты выполнения первого шага цикла при k = 1:
mn1
= = min (х[1], mn0).
mn0
при х[1] £
mn0
Следовательно, результатом будет
mn1 = min (x[l], mn0)
Однако поскольку начальное значение mn0 неизвестно, то неопределено значение результата выполнения первого шага цикла. Аналогичное утверждение можно сделать о втором и всех последующих шагах выполнения цикла:
mnk
= min (x[k], Min(x[k-l], ..., х[1], mn0) = Min (x[k], x[k-1], ..., х[1], mn0).
В силу математической индукции это утверждение справедливо при k = N:
mnN
= Min (x[N], x[N - 1], ..., x[2], х[1], mn0),
Таким образом на основании этого утверждения можно сделать заключение о конечном результате выполнения алгоритма в целом:
Min = mnN
= Min (x[N], x[N - 1], ..., x[2], х[1], mn0).
Из этой формулы видно, что конечный результат равно как и результат первого присваивания зависит от начального значения mn0 переменной mn. Однако эта величина не имеет определенного значения, соответственнно неопределен и конечный результат выполнения алгоритма в целом, что и является ошибкой.
В самом деле, если значение mn0 окажется меньше любого из значений последовательности х[1], ....
x[N], то конечный результат вычислений будет неправильным. В частности, при реализации алгоритма на Бейсике неправильный результат будет получен, если последовательность будет состоять только из положительных чисел. Например, для последовательности чисел: 1, 2, 3, ..., N.
Приведем правильную версию алгоритма с доказательством отсутствия ошибок, используя технику индуктивных утверждений.
 массив х[1:п] нач тп := x[1] от k = 1 до N цикл если x[k] < тп то тп = x[k] все кцикл Min = тп кон |
Результаты: mn0 = х[1] [k = (1 ... N)]  Min = mnN |
Доказательство. Воспользуемся результатами анализа выполнения алгоритма, рассмотренного ранее. Различие между ними состоит в добавлении перед началом цикла присваивания mn := х[1], которое задает начальное значение переменной mn, равное mn0 = х[1].
Тогда в силу приведенных ранее рассуждений и выкладок конечным результатом выполнения новой версии алгоритма будет значение
Min = mnN = Min(x[N], x[N-l], ..., х[2], х[1], mn0) =
= Min(x[N], x[N-l], ..., x[2], x[l], x[l]) = Min(x[N], .... х[1]).
Что и требовалось.
Рассмотренные примеры являются образцами доказательств
правильности алгоритмов и программ, которые могут использоваться для анализа и доказательства правильности других новых алгоритмов и программ обработки данных.
Общий вывод, который мы хотим сделать, состоит в том, что применение доказательных методов превращает программирование в научную дисциплину создания безошибочных алгоритмов и надежных программ для ЭВМ.
В о п р о с ы
1. Как показать наличие ошибок в алгоритме?
2. Сколь долго может продолжаться отладка программ?
3. Зачем нужны доказательства в анализе алгоритмов?
4. Из чего состоит техника доказательств правильности?
5. Когда применяется разбор случаев?
6. Что такое леммы?
7. Что такое индуктивные рассуждения?
3 а д а ч и
1. Приведите постановку, алгоритм решения и разбор правильности для следующих задач:
а) подсчет суммы целых чисел;
б) подсчет суммы нечетных чисел;
в) подсчет членов арифметической прогрессии;
г) подсчет членов геометрической прогрессии.
2. Для последовательности чисел х1, х2,..., хN, приведите постановку, алгоритм решения и разбор правильности следующих задач:
а) подсчет суммы всех чисел;
б) вычисление среднего арифметического чисел;
в) определение наибольшего из чисел;
г) определение наименьшего из чисел.
3. Для данных о росте и весе учеников приведите постановку задачи, алгоритм решения и разбор правильности для следующих задач:
а) нахождение самого высокого ученика;
г) нахождение самого легкого ученика;
д) нахождение среднего роста учеников;
е) нахождение суммарного веса учеников.
4. Для прямоугольной матрицы Anm приведите постановку, алгоритм решения и разбор правильности следующих задач:
а) подсчет сумм элементов матрицы по столбцам;
в) нахождение минимального значения в каждом столбце;
е) нахождение максимального значения в каждой строке;
ж) нахождение наибольшего из минимальных значений в столбцах;
з) нахождение наименьшего из максимальных значений в строках.
5. Для N точек на плоскости, заданных случайным образом, приведите постановку, метод решения, сценарий, алгоритм и программу решения следующих задач:
а) найти точку, наиболее удаленную от центра координат;
б) соединить пару наиболее удаленных точек;
в) найти три точки, образующие треугольник с наибольшим периметром;
г) найти три точки, образующие треугольник с наибольшей площадью.
