 |
 |
 |
 |
|
 |
 |
129
1. Как показать наличие ошибок в алгоритме?
2. Сколь долго может продолжаться отладка программ?
3. Зачем нужны доказательства в анализе алгоритмов?
4. Из чего состоит техника доказательств правильности?
5. Когда применяется разбор случаев?
6. Что такое леммы?
7. Что такое индуктивные рассуждения?
3адания
1. Приведите постановку, алгоритм решения и разбор правильности для следующих задач:
а) подсчет суммы целых чисел;
б) подсчет суммы нечетных чисел;
в) подсчет членов арифметической прогрессии;
г) подсчет членов геометрической прогрессии.
2. Для последовательности чисел х1, х2,..., х
N
, приведите постановку, алгоритм решения и разбор правильности
следующих задач:
а) подсчет суммы всех чисел;
б) вычисление среднего арифметического чисел;
в) определение наибольшего из чисел;
г) определение наименьшего из чисел.
3. Для данных о росте и весе учеников приведите постановку задачи, алгоритм решения и разбор
правильности для следующих задач:
а) нахождение самого высокого ученика;
г) нахождение самого легкого ученика;
д) нахождение среднего роста учеников;
е) нахождение суммарного веса учеников.
4. Для прямоугольной матрицы A
nхm
приведите постановку, алгоритм решения и разбор правильности
следующих задач:
а) подсчет сумм элементов матрицы по столбцам;
б) нахождение минимального значения в каждом столбце;
в) нахождение максимального значения в каждой строке;
г) нахождение наибольшего из минимальных значений в столбцах;
д) нахождение наименьшего из максимальных значений в строках.
5. Для N точек на плоскости, заданных случайным образом, приведите постановку, метод решения, сценарий,
алгоритм и программу решения следующих задач:
а) найти точку, наиболее удаленную от центра координат;
б) соединить пару наиболее удаленных точек;
в) найти три точки, образующие треугольник с наибольшим периметром;
г) найти три точки, образующие треугольник с наибольшей площадью.
5.5. Решение сложных задач
Большинство практических задач обработки данных относится к числу сложных. Сложность задач
оценивается сложностью обрабатываемых данных и сложностью алгоритмов их решения. Сложность
данных обычно оценивается их количеством. Сложность алгоритмов оценивается объемом вычислений,
необходимых для получения требуемых результатов.
При решении сложных задач, требующих составления сложных алгоритмов, особенно сказываются
преимущества доказательного программирования. Для этого программы решения сложных задач
составляются из вспомогательных алгоритмов и подпрограмм, решающих более простые подзадачи.
Анализ правильности сложных алгоритмов и программ распадается на анализ правильности
каждого из вспомогательных алгоритмов и на анализ правильности программ в целом. Необходимым
условием для этого является составление спецификаций для каждого из вспомогательных алгоритмов и
каждой подпрограммы.
При таком подходе доказательство правильности сложных алгоритмов и программ подразделяется
на доказательство ряда лемм о правильности вспомогательных алгоритмов и подпрограмм и
доказательство правильности программ в целом.