Анализ правильности алгоритмов

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

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

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

Сбой — это потеря части данных либо получение непредусмот­ренных данных. Такого рода ошибки говорят о их частичной нера­ботоспособности программ либо об их недостаточной надежности.

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

О правильности программ нельзя утверждать ничего если неиз­вестны предъявляемые к ним требования. Только при наличии стро­гих, четких спецификаций можно судить о правильности работы программ.

Наличие точной постановки задач позволяет говорить о правиль­ности не только конечных результатов, но и различных способов и методов их решения.

Способ правильный, если он дает правильные результаты. Способ неправильный, если он дает неправильные результаты или не дает результатов вообще.

Метод неправильный, если существуют допустимые данные, для которых он дает неправильные результаты либо не дает результатов вообще.

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

Алгоритм содержит ошибки, если можно указать допустимые ис­ходные данные, при которых либо будут получены неправильные результаты, либо результаты не будут получены вовсе. Использование алгоритмов, содержащих ошибки, приводит к созданию программ, также содержащих ошибки.

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

Первый способ — проверка основных этапов построения алго­ритма:

задача, постановка, метод, алгоритм

Второй способ — анализ результатов выполнения алгоритмов и их сравнение с выбранными методами решения и постановкой задачи:

алгоритм, метод, постановка, задача

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

Систематические методы анализа правильности алгоритмов и программ опираются на сопоставление тех же самых описаний, которые используются при их систематическом составлении.

Основные типы алгоритмических ошибок в программах:

• ошибки в выбранных методах решения;
• ошибки в постановке решаемых задач;
• дефекты в сценариях диалога с ЭВМ;
• ошибки организации ввода данных;
• неправильная реализация методов решения.

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

Будем считать, что программа правильная, если она дает правильные результаты для любых допустимых исходных данных. Такого рода программы вполне можно использовать для решения прикладных задач.

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