3.Правильность алгоритма

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

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

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

Пример. Алгоритм ETS настолько прост, что его правильность легко доказать. Поскольку проверяется каждый тур, должен быть проверен и тур с минимальной стоимостью; как только до него дойдет очередь, он будет запомнен. Он не будет отброшен — это может слу­читься только в том случае, если существует тур с меньшей стоимо­стью. Алгоритм должен закончить работу, так как число туров, ко­торые нужно проверить, конечно. Подобный метод доказательства известен как «доказательство исчерпыванием»; это самый грубый из всех методов доказательства.

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

4.Реализация алгоритма

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

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

Каковы основные переменные?

Каких они типов?

Сколько нужно массивов и какой размерности?

Имеет ли смысл пользоваться связными списками?

Какие нужны подпрограммы (возможно, уже записанные в па­мяти)?

Каким языком программирования пользоваться?

Конкретная реализация может существенно влиять на требования к памяти и на скорость алгоритма.

Другой аспект построения программной реализации —• это про­граммирование сверху - вниз. Объяснение этого понятия будет дано в разд. 2.1, а пока укажем, что программирование сверху - вниз — это подход к разработке и реализации, который состоит в преобразо­вании алгоритма в такую последовательность все более конкретизи­рованных алгоритмов, что окончательный вариант представляет собой

программу для ЭВМ.

Сделаем одно важное замечание. Одно дело — доказать правиль­ность конкретного алгоритма, описанного в словесной форме. Другое дело — доказать, что данная машинная программа, предположи­тельно являющаяся реализацией этого алгоритма, также правильна. Таким образом, необходимо очень тщательно следить, чтобы процесс преобразования правильного алгоритма (в словесной форме) в машин­ную программу «заслуживал доверия».

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