Способы проверки правильности программы: теоретический (аналитический) и экспериментальный (эмпирический)

Лекция. Правильность и эффективность алгоритмов

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

Использование компьютеров для решения возникающих перед человеком проблем ставит новые вопросы. К числу таких вопросов относится надежность программного обеспечения. Универсальные вычислительные машины могут быть запрограммированы для решения самых разных задач – от арифметических вычислений до доказательства теорем, от редактирования текстов до обучения иностранному языку. Однако успешное решение этих и многих других задач возможно лишь при условии, что программа правильна, т.е. не содержит ошибок. Как убедиться, что ошибки на самом деле отсутствуют? Факт безаварийного завершения программы еще ни о чем не говорит: возможно, что программа делает совсем не то, что было задумано и для чего она была написана.

Алгоритм (программа) будет правильным, если в результате его выполнения достигается тот результат, для получения которого и был написан алгоритм.

Способы проверки правильности программы: теоретический (аналитический) и экспериментальный (эмпирический).

Теоретически - доказательство правильности программы состоит в предъявлении такой цепочки аргументов, которые убедительно свидетельствуют о том, что программа действительно решает поставленную задачу. Более строгий путь проверки программы – верификация, которая представляет собой теоретическое обоснование правильного вычисления программы и включает логико-математическое доказательство того, что вычислительное поведение программы правильно.

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

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

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

Однако правильность - далеко не единственное качество, которым должен обладать хороший алгоритм. Одним из важнейших является эффективность.