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

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

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

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

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

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

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

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

· Каковы основные переменные? Каких они типов?

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

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

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

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

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

Другой аспект построения программной реализации – это программирование “сверху–вниз”, которое состоит в преобразовании алгоритма в такую последовательность всё более конкретизированных алгоритмов, что окончательный вариант представляет собой программу для ЭВМ.

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