Возвращаясь к напечатанному

50

Возвращаясь к напечатанному

Редакция получила несколько писем, указавших на «ошибки в алгоритмах», которые читатели увидели в статье В. А. Каймина («Квант», № 10, с. 47). Это дает нам повод остановиться на важном вопросе: какие алгоритмы считать правильными?

Алгоритм называем правильным, если он формирует результаты, строго в соответствии с требованиями (постановки задачи или описания сценария) при любых допустимых исходных данных. Соответственно — алгоритм содержит ошибки, если можно указать такие допустимые исходные данные, при которых будет получен результат, не отвечающий заданным требованиям; либо вовсе не будет получены результаты. При отсутствии четкой постановки задачи готовить о наличии ошибок в алгоритмах или программах не имеет смысла.

Пример неправильного алгоритма действительное можно найти в упомянутой статье: к сожалению, в алгоритме подсчета площади кольца (с. 48) после строки $S_2 := \pi \cdot r^2$ пропущена строка $S := S_1 - S_2$. В связи с этим редакция принoit читательам свои извинения.

Другое дело — алгоритм приближенного решения

уравнения $f(x) = 0$ (метод поовинного деления, с. 50). В статье (из-за ограниченности объема) не приводится постановка задачи, поэтому формально ставить вопрос о правильности этого алгоритма неправомерно. Отметим, однако, что в авторской постановке было:

Требе: $x_0$ — приближенное решение;

Связь: $x_1 \leq x_0 \leq x_2$,
$|x_1 - x_2| < e$,
$f(x_1) \cdot f(x_2) \leq 0$.

Для этой постановки приведенный алгоритм — правильный. Можно, конечно, ставить задачу иначе, например требовать $|f(x_0)| < e$, и тогда нужен другой алгоритм. Какая постановка лучше — это уже другой, чисто математический вопрос.