Информатика


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


x[N], то конечный результат вычислений будет неправильным. В частности, при реализации алгоритма на Бейсике неправильный результат будет получен, если последовательность будет состоять только из положительных чисел. Например, для последовательности чисел: 1, 2, 3, ..., N.

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

 

алг «нахождение минимума»

массив х[1:п]

нач

   тп := x[1]

  от k = 1 до N цикл

    если x[k] < тп то

      тп = x[k]

    все

   кцикл

  Min

= тп

кон

 

 

Результаты:

mn0

= х[1]

[k = (1 ... N)]

Min = mnN

 

Утверждение. Для любой последовательности чисел x[l:N] конечным результатом вычислений будет значение Min = Min (х[1], ..., x[N]).

Доказательство. Воспользуемся результатами анализа выполнения алгоритма, рассмотренного ранее. Различие между ними состоит в добавлении перед началом цикла присваивания 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. Когда применяется разбор случаев?




Начало  Назад  Вперед



Книжный магазин