Лекции по информатики 2 (стр. 29 из 43)

В о п р о с ы

1. Как показать наличие ошибок в алгоритме?

2. Сколь долго может продолжаться отладка программ?

3. Зачем нужны доказательства в анализе алгоритмов?

4. Из чего состоит техника доказательств правильности?

5. Когда применяется разбор случаев?

6. Что такое леммы?

7. Что такое индуктивные рассуждения?

3 а д а ч и

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

а) подсчет суммы целых чисел;

б) подсчет суммы нечетных чисел;

в) подсчет членов арифметической прогрессии;

г) подсчет членов геометрической прогрессии.

2. Для последовательности чисел х₁, х₂,..., х_N, приведите постановку, алгоритм решения и разбор правильности следующих задач:

а) подсчет суммы всех чисел;

б) вычисление среднего арифметического чисел;

в) определение наибольшего из чисел;

г) определение наименьшего из чисел.

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

а) нахождение самого высокого ученика;

г) нахождение самого легкого ученика;

д) нахождение среднего роста учеников;

е) нахождение суммарного веса учеников.

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

а) подсчет сумм элементов матрицы по столбцам;

в) нахождение минимального значения в каждом столбце;

е) нахождение максимального значения в каждой строке;

ж) нахождение наибольшего из минимальных значений в столбцах;

з) нахождение наименьшего из максимальных значений в строках.

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

а) найти точку, наиболее удаленную от центра координат;

б) соединить пару наиболее удаленных точек;

в) найти три точки, образующие треугольник с наибольшим периметром;

г) найти три точки, образующие треугольник с наибольшей площадью.

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

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

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

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

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

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

Первая задача: упорядочение массивов данных. Пример, для чисел 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).

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

Утверждение. Конечным результатом выполнения алгоритма будет упорядоченная последовательность чисел х₁', ..., х_N', удовлетворяющая условию х₁' £ х₂' £ ... £ х_N'.

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

алг «упорядочение чисел»

нач

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

xmn:=х_k

...............{ xmn = Min (х_k, ..., х_i) }

х¢_k =xmn_N

хmп¢ = х_k

кцикл{ х_k' = Min (х_k, ..., х_N) }

кон{ х₁' £ х₂' £ ... £ х_k' }

На первом шаге при k = 1 первый элемент последовательности

х₁' = Min (x₁, х₂, ..., х_N),

На втором шаге второй элемент последовательности

x₂' = Min (х₂, ..., х_N).

В силу свойств минимума последовательности чисел будем иметь

х₁' = Min(x₁, x₂, ..., х_N) = min (x₁, Min (х2, ..., хN) £ (Min (х2, ..., хN) = x₂'.

Таким образом, при k = 2 результатом станут значения х₁' и x₂', такие что

х₁' £x₂'

На третьем шаге выполнения основного цикла результатом станет

х₃ = Мin(х₃, ..., х_N).

Опять же в силу свойств минимума последовательности имеем

х₂' = Min (х₂, х₃, ..., х_N) = min (x₂, Min (x₃, ..., х_N)) £ Min (x₃, ..., х_N) = x₂'.