Решение сложных задач

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

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

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

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

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

Первая задача: упорядочение массивов данных. Пример, для чисел 3, 7, 9, 1, 4 упорядоченная последовательность имеет вид: 1, 3, 4, 7, 9.

Существует несколько способов и методов упорядочения масси­вов и последовательностей. Простейший из них называется методом «пузырька».

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

Для рассматриваемых чисел метод «пузырька» дает следующие перестановки:

исходные числа: 3, 7, 9, 1, 4.

перестановка₁: 1, 7, 9, 3, 4.

перестановка₂: 1, 3, 9, 7, 4.

перестановка₃: 1, 3, 4, 7, 9. упорядочено.

Приведем точную математическую постановку задачи.

Постановка задачи

Упорядочение последовательности чисел.

Дано: x₁, х₂,..., х_N - исходные числа.

Треб.: x₁', x₂',..., х_N' - упорядоченные числа.

Где: х₁' £ х₂' £... £ х_N'.

При: N > 0.

Упорядочение чисел по методу «пузырька» в общей форме имеет вид:

Способ «упорядочение чисел»

нач

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

хтп:= xk

imn:= k

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

если xi < хтп то

хтп:= xi

imn: = i

кесли

кцикл

xmn = Min (х_k,..., х_N)

xk' = хтп

ximn ' = xk

кцикл х_k¢ = Min (х_k,..., х_N)

кон x₁ < х₂ <... < х_k¢

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

Первый фрагмент (внутренний цикл) решает подзадачу нахожде­ния минимального значения в подмассиве x[k:N]. Второй фрагмент решает подзадачу перемещения k-го минимального значения на k-e место в массиве.

Лемма 1. Для вспомогательного алгоритма

алг «поиск минимума»

Нач

хтп:= xk

imn:= k

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

если x_i < хтп то

хтп:= x_i

imn:= i

Кесли

кцикл { xmn = Min (х_k,..., х₁) }

Кон

конечным результатом вычислений будет значение

xmn = Min (х_k,..., х_N).

Доказательство. Применим индуктивную схему рассуждений. Первое присваивание дает

xmn_k = x_k.

Далее на первом шаге цикла при i = k + 1 будет получен минимум первых двух чисел:

x_k+1 при x_k+1 < xmn_k,

xmn_k+l =

xmn_k при x_k+1 ³ xmn_k.

На втором шаге цикла будет получен минимум первых трех чисел:

xmn_k+2 = min (x_k+2, min (х_k+1, х_k)) = Min (х_k+2, х_k+1, х_k).

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

хmn_i = Min (х_k,..., х_i).

Данное утверждение доказывается с помощью математической индукции. На первых двух шагах при i = k + 1, k + 2 оно уже уста­новлено. Покажем, что оно будет выполняться на (i + 1)-м шаге. Действительно, на следующем шаге цикла результатом будет:

x_i+1 при х_i+1 < xmn_i = min(x_i+1, хmn_i)

хmn_i+1 =

хmn_i при х_i+1 ³ хmn_i = min(x_i+1, xmn_i)

= min (x_i+1, Min (х_k,..., х_i)) = Min (х_k,..., х_i, x_i+1).

Что и требовалось показать. Следовательно, в силу принципа мате­матической индукции конечным результатом выполнения рассмат­риваемого цикла будет значение:

xmn_N = Min (x_k, ..., х_N)

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

Лемма 2. Для вспомогательного алгоритма

алг «перестановки»

нач { xmn = Min (х_k,..., х_N) }

x_i¢_mn= x_k

Кон

конечным результатом будет значение х_k' = Min (х_k,..., х_N).

Доказательство. В силу леммы 1 xmn = Min (x_k,..., х_N). А так как в этом алгоритме х_k' = xmn, то в итоге получим

х_k' = xmn = Min (х_k,..., х_N).