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

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

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

Вопросы

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

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

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

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

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

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

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

Адания

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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