Способы проверки правильности программы: теоретический (аналитический) и экспериментальный (эмпирический)
Лекция. Правильность и эффективность алгоритмов
Правильность алгоритмов.
Использование компьютеров для решения возникающих перед человеком проблем ставит новые вопросы. К числу таких вопросов относится надежность программного обеспечения. Универсальные вычислительные машины могут быть запрограммированы для решения самых разных задач – от арифметических вычислений до доказательства теорем, от редактирования текстов до обучения иностранному языку. Однако успешное решение этих и многих других задач возможно лишь при условии, что программа правильна, т.е. не содержит ошибок. Как убедиться, что ошибки на самом деле отсутствуют? Факт безаварийного завершения программы еще ни о чем не говорит: возможно, что программа делает совсем не то, что было задумано и для чего она была написана.
Алгоритм (программа) будет правильным, если в результате его выполнения достигается тот результат, для получения которого и был написан алгоритм.
Способы проверки правильности программы: теоретический (аналитический) и экспериментальный (эмпирический).
Теоретически — доказательство правильности программы состоит в предъявлении такой цепочки аргументов, которые убедительно свидетельствуют о том, что программа действительно решает поставленную задачу. Более строгий путь проверки программы – верификация, которая представляет собой теоретическое обоснование правильного вычисления программы и включает логико-математическое доказательство того, что вычислительное поведение программы правильно.
Для экспериментальной проверки в практике программирования используют прием тестирования программ: проверяемую программу неоднократно запускают с теми входными данными, относительно которых результат известен заранее. Затем сравнивают машинный результат с ожидаемым, если результаты совпадают, то появляется небольшая уверенность, что и последующие вычисления не приведут к ошибкам.
Для сложных программ удачное тестирование не дает гарантии того, что программа не содержит ошибок.
Недостаточно доказать правильность алгоритма. Все мы можем сделать ошибки при доказательстве и при переводе правильного алгоритма в программу. Каждый может забыть некоторый частный случай задачи. Мельчайшие особенности операционной системы могут вызвать для некоторых входных данных такое действие части вашего алгоритма, о котором вы и не подозревали. Программа должна быть проверена для широкого спектра допустимых входных данных. Этот процесс может быть утомительным и сложным. Аналитический и экспериментальный анализ дополняют друг друга. Аналитический анализ может быть неточным, если сделаны слишком сильные упрощающие допущения. В этом случае могут быть получены только грубые оценки. Экспериментальные результаты, особенно когда используются случайно сгенерированные данные, могут оказаться слишком односторонними. Чтобы получить достоверные результаты, следует проводить как аналитическое, так и экспериментальное исследование там, где это возможно.
Однако правильность — далеко не единственное качество, которым должен обладать хороший алгоритм. Одним из важнейших является эффективность.
Источник
Проверка правильности алгоритмов
Цель создания любого алгоритма – выполнение некоторых вычислений. При этом требуется, чтобы алгоритм при допустимых значениях входных параметров вычислял верные значения на выходе. Как убедиться, что результат будет правильным при любых допустимых входных значениях? Вопрос о правильности алгоритмов – один из основных вопросов программирования как науки о составлении алгоритмов.
Актуальность вопроса можно проиллюстрировать на таком примере: пусть вероятность того, что алгоритм, занимающий 1 страницу текста, верен, равна 0.9 (из 10 операторов 1 неверный, для начинающих программистов правильнее было бы 9 из 10). Для алгоритма, занимающего 2 страницы – 0.92=0.81, 3 страницы – 0.93 и т.д. Для современных ЭВМ часто длина программы ≈ 100 страниц. Вероятность правильной работы при этом 0.9100=0.000027 – ничтожно мала.
Говорят, что ошибки в программах появились раньше, чем сами машины. Можно выделить три источника ошибок.
· “Описки”, то есть ошибки, появившиеся из-за невнимательности и незначительных нарушений синтаксиса языка.
· Алгоритмические ошибки. Возникают из-за неправильного понимания сути алгоритма или неправильного выражения мыслей. Это более серьезные ошибки.
· Ошибки, возникающие при работе с такими значениями данных, на которые не рассчитана программа. То есть ошибки из-за неправильных данных. Например, 20! – слишком большое число, 1/(20!) – слишком маленькое. Такие ошибки нужно предвидеть.
Методы борьбы с различными группами ошибок различны.
Большая часть “описок” обнаруживается на этапе перевода (автоматического) нашего алгоритма в команды ЭВМ – на так называемом этапе трансляции.
Другая часть «описок», а также некоторые алгоритмические ошибки, может быть найдена путем тестирования. Исторически первым методом проверки правильности алгоритма (программы) явилось тестирование: программа вводится в ЭВМ с заранее подобранными входными данными, и полученные результаты сравнивают с заранее известными правильными результатами (подсчитанными для этих входных данных вручную). Это – тест (проверяющая задача): алгоритм + данные + контрольный пример. Такое тестирование желательно повторить несколько раз.
Если результат совпадает с известным, это дает некоторые основания считать программу верной. Даже при хорошем тестировании в программе могут остаться ошибки. Для того, чтобы рассеять все сомнения, нужно выполнить все возможные варианты (то есть провести расчет со всеми возможными входными данными).
На основе подобных рассуждений Э. Дейкстра (голландский профессор, классик современного программирования) сформулировал такой закон (закон Дейкстры): тестированием можно обнаружить ошибки в программе, но никогда нельзя доказать их отсутствие.
Чтобы убедиться в правильности программы, отсутствии в ней алгоритмических ошибок, нужно уметь проверять правильность структуры алгоритма. Такая аналитическая проверка называется верификацией алгоритма. При использовании этого метода нужно для каждого алгоритма и каждой фразы в нем абстрагироваться от индивидуальных значений переменных и сформулировать условия, которым они должны удовлетворять до и после выполнения алгоритма. Для любого алгоритма можно определить, каким условиям должны удовлетворять входные данные и результат. Это условия подобные тем, которые задаются в операторах IF и WHILE.
Условие на входе называется предусловием, на выходе – постусловием.
Задача состоит в том, чтобы доказать, что входное предусловие алгоритм за конечное число шагов переводит в постусловие.
Наиболее распространенными методами доказательства являются:
· перечисление (перебор вариантов) – для IF-THEN-ELSE и последовательных алгоритмов;
· математическая индукция – для WHILE-DO.
Проиллюстрируем использование метода перебора вариантов на примере алгоритма дихотомии. Входные данные: C, D, EPS. (функция f – фиксирована и не относится к входным данным).
(D>0) AND (EPS>0) AND (f (C-D)*f (C+D) ≤ 0). (*)
(D 0) AND (D>0) AND (f (C-D)*f (C+D) ≤ 0). (**)
Требуется доказать, что алгоритм, имеющий на входе условие (*) на выходе получит условие (**).
while d>eps do
Begin
if f (c)*f(c+d) >0
then c:=c-d/2
else c:=c+d/2;
end;
Пусть выполняется условие
Тогда в результате одного выполнения цикла получим новые значения Cнов и Dнов:
f (Cнов- Dнов)*f (Cнов+ Dнов) = f (C-D/2-D/2)* f (C-D/2+D/2) =
=f (C-D)*f (C)≤0 (из (*) и (1)). (3)
Таким образом мы доказали, что внутри цикла действует предусловие
(f (C-D)*f (C+D)≤0) AND (D>0)
и такое же постусловие. Доказательство провели методом перебора вариантов.
Выберите второй вариант условия f (C) *f (C-D) ≤0 и докажите то же самое.
Доказательство по методу математической индукции строится на переборе вариантов, зависящих от некоторого натурального числа n, где n=n0, n0+1, n0+2,…,∞.
Пусть P(n) – некоторое проверяемое условие.
Схема метода математической индукции:
· непосредственной подстановкой проверяем, что P(n0) выполняется;
· предполагаем, что P верно для некоторого n=k, k≥n0;
· доказываем, что из предположения п.2) следует, что P будет верно для n=k+1.
Докажем, что вычисление по рекуррентной последовательности f (0) = 1,
где n>0, даст в результате значение f(n)=n!.
f (0) =1 0! = 1 — выполняется.
предполагаем, что f (k) = k!
убедимся, что из п.2 следует f (k+1) = (k+1)!
Действительно, f (k+1) = f (k)*(k+1) = k!*(k+1) = (k+1)!, что и требовалось доказать.
Для циклических алгоритмов под величиной n обычно понимают количество повторений цикла. В частном случае оно может быть равно нулю.
Ценность методов верификации состоит в том, что мы получаем доказательство правильности для всего комплекса допустимых значений данных. При этом успех методов зависит от того, насколько правильно и полно мы задали пред- и постусловия.
Для доказательства правильности больших алгоритмов разбиваем их на части и для каждой части формулируем пред- и постусловия. Постусловие для одной части является предусловием для следующей. Доказываем правильность алгоритма в целом, затем — отдельно для каждого внутреннего алгоритма.
Ошибки из-за неправильных данных представляют собой совокупность таких входных данных, при которых программа неработоспособна. Для избежания таких ошибок целесообразен следующий подход.
На входе программы делаются специальные проверки на правильность данных. Затем либо выдаётся сообщение о том, что данные неверны, либо проводятся вычисления. Схема такой проверки выглядит следующим образом.
IF данные верны THEN выполнить алгоритм ELSE выдать сообщение о неправильности данных.
В этом состоит суть метода программной защиты от неправильных данных. Данные могут быть неверны и из-за ошибок при вводе. Поэтому чем больше входных данных, тем жестче должна быть их проверка.
Далее приведен пример решения задачи проверки правильности программы.
Задача. Придумать тесты для отладки приведенной ниже программы для нахождения наибольшего общего делителя двух натуральных чисел.
write(‘Введите два натуральных числа’);
Решение. Для тестирования построим столько тестов, чтобы можно было пройти по каждой ветви программы хотя бы по разу. В ней имеются пять ветвей:
четвертая — С, D, В;
Путей здесь много. Примерами путей являются последовательности из следующих ветвей:
четвертый — 1,2 4,2,5,3;
шестой — 1, 2, 5, 2, 5, 2, 4, 3 и т.д.
Среди указанных путей есть такие, в которых используются не все ветви (это пути 1, 2, 3, 5), но есть и такие, в которых проходится каждая ветвь программы хотя бы по одному разу (это пути 4, 6).
Для построения теста выбранного пути построим сначала предикат пути, который будет принимать значение «истина», если в процессе исполнения программы реализуется данный путь, и «ложно» — при реализации других путей.
Для построения предиката пути проходим путь в обратном направлении и выписываем конъюнкцию всех условий, которые встречаются на этом пути. Если при обратном проходе пути осуществляется переход через оператор присваивания (переменная: =выражение), то в предикат пути вместо всех вхождений переменной из левой части оператора присваивания подставляется выражение из его правой части. Предикаты пути, построенные так, как описано выше, всегда выражаются в терминах констант и входных переменных. Чтобы пройти заданный путь во время исполнения программы, необходимо найти такие значения исходных данных, которые делают предикат пути истинным.
Рассмотрим процесс построения предиката для четвертого пути приведенной выше программы.
Вначале проходим ветвь 3 от F к В. При исполнении программы в блок F попадаем в случае ложности условия В, поэтому предикат этой ветви имеет вид Р: X=Y.
Движемся дальше от В к С через Е. При переходе оператора присваивания Y:=Y-X в предикате Р все вхождения переменной Y заменим на выражение Y-X. Получаем Р: X=Y-X или Р: 2*X=Y. Поскольку Е выполняется в случае ложности условия С, присоединяем его отрицание через конъюнкцию к Р. Р: (2*X=Y) and (X Y). В полученном предикате из первого члена конъюнкции 2*X=Y следует третий: Х, не равный Y, поэтому третий член конъюнкции можно отбросить. Получим Р: (2*X=Y) and (X Y).
В полученном предикате вновь из первого члена конъюнкции следует третий, поэтому его можно отбросить. Получаем Р: (2*X=3*Y) and (X =b then do
получены сообщения об ошибках:
• одно сообщение —Error 26: Type mismatch;
• одно сообщение —Error 36: BEGIN expected;
• одно сообщение —Error 85: «;» expected;
• одно сообщение —Error 113: Error in statement.
Определить характер ошибок и исправить их.
4. В результате компиляции программы
получены сообщения об ошибках:
• одно сообщение —Error 3:Unknown identifier;
• одно сообщение — Error 94: «.» expected;
• одно сообщение —Error 91: «:=» expected.
Определить характер ошибок и исправить их.
Дата добавления: 2018-09-22 ; просмотров: 1016 ; Мы поможем в написании вашей работы!
Источник
Тестирование математических алгоритмов
Эта статья написана для людей, прямо или косвенно связанных с промышленной разработкой математических алгоритмов для бизнеса, а также для профессиональных тестировщиков, от которых мы хотим услышать критику.
Кто мы
Мы работаем в российской компании, которая более 10 лет занимается разработкой уникальных программных решений в области анализа данных, прогнозирования, классификации и других областей датамайнинга. Все решения – не абстрактные инструменты, а интегрированные системы для решения конкретных задач заказчиков. Наша ключевая особенность – алгоритмы собственной разработки, заточенные под высокое качество результата.
В нашей компании есть чёткое разделение обязанностей между математиками и программистами. Для наглядной расстановки акцентов добавлю, что команда математиков почти не уступает по размеру команде программистов.
О какой проблеме пойдёт речь
Упрощённо, процесс создания нового решения выглядит так:
После проверки идеи, наши математики разрабатывают полноценную аналитическую систему и реализуют в ней все процессы заказчика. На этой системе как правило происходит демонстрация работы наших алгоритмов в условиях, приближенных к боевым. Наши математики предпочитают работать на Matlab, поэтому их система очень удобна для быстрой проверки гипотез, но по многим причинам не может использоваться в промышленных целях. Нужно заново реализовывать тоже самое в подходящей среде разработки, например, .NET (в нашем случае). Этот момент – слабое звено процесса.
Разработчик промышленного софта имеет перед собой документацию и исходники на Matlab, но не обладает образованием и опытом математика. Однако из-под его пера должен выйти точно такой же алгоритм. Здесь возникает задача: как правильно тестировать промышленную версию алгоритма на соответствие прототипу математика?
В чём сложность этой задачи?
Нужно заметить, что поймать ошибку в математическом алгоритме и, например, в процессе синхронизации двух СУБД – две принципиально разные задачи. С базами данных всё более понятно: количество записей после синхронизации совпадает, контрольные суммы совпадают, значит тест пройдён. Легко понять и сравнительно легко автоматизировать.
Алгоритм прогнозирования принимает на вход и выдаёт на выход десятки или сотни величин — чисел с плавающей точкой. Один алгоритм выводит эти числа на экран в Матлабе, другой, промышленный, записывает в переменную в C#-коде. Как их сравнить? Из-за ограниченной точности вычислений с плавающей точкой, совпадать до последнего знака они не будут. Чем ограничить точность сравнения? В наших условиях падение качества прогнозирования на 2-3% может быть существенно, т.к. иногда это сравнимо с эффектом, который мы даём бизнесу.
Как мы решаем проблему
Процедура тестирования, к которой пришли мы, выглядит так:
- Генерация входных наборов данных – так называемых эталонов. Эту работу заранее делает математик в привычной среде – Matlab.
- Запуск системы тестирования, поглощающей эталоны и превращающей их в тесты. Эта система разработана нами на Matlab, по эталону она понимает какой алгоритм нужно запустить, в каком порядке передавать в него данные и чего ожидать на выход.
- Запуск прототипа на Matlab с эталонами в качестве входных данных. Эта процедура выполяется легко, т.к. и эталоны, и прототип созданы в рамках одной системы – Matlab.
- Запуск промышленной .NET-версии, с конвертацией входные и выходные данных из Матлаба в C# и обратно. Перепробовав несколько подходов, для построения такого моста, мы остановились на C#-интерфейсе, реализованном из коробки в последних версиях Матлаб. Он позволяет инстанциировать из Matlab практически любые типы C#-данных, загружать сборки, запускать функции.
- Система получает результаты работы обоих алгоритмов и запускает процедуру сравнения.
- Процедура сравнения выдаёт вердикт: 0 (не совпадает) или 1 (совпадает). Процедуру сравнения требуется разрабатывать вручную под каждый алгоритм, т.к. особенности округления конкретных величин дают разные допуски по значениям. Кроме того, некоторые алгоритмы включают в себя генерацию случайных величин.
- Шаги 2-7 автоматизируются посредством консольного запуска Matlab и запускаются по расписанию.
С учётом необходимости разработки C#-Matlab интерфейса, функции сравнения, а также отладки двух систем, на сведение среднего алгоритма уходит 5-10 дней, что по трудозатратам сравнимо со временем, затрачиваемым на разработку. Это время отражает разницу между алгоритмом, который «в принципе работает и выдаёт что-то нормальное» и алгоритмом, который полностью повторяет задуманное математиком.
Ещё раз, списком, сложности, с которыми мы сталкиваемся:
- Входные данные нужно подавать в Matlab и в C# => нужно разрабатывать конвертации туда и обратно.
- Сравнение и связанные с ним проблемы округления и другие особенности – мешают писать код и вводят в заблуждение при отладке.
- Синхронная отладка: чтобы понять, что не так, часто нужно синхронно запускать два отладчика под двумя системами, это работает, но требует определённого шаманства.
- Генерация исчерпывающего набора эталонов (задача математика). Всевозможные входы перебрать не получится, и веток в алгоритме может быть слишком много для их совместной проверки во всех комбинациях.
- Под каждый алгоритм необходима собственная вручную разработанная функция сравнения результатов.
Особенности кодирования
Разрабатывая промышленный код на C#, мы сразу думаем о том, что его придётся «сводить» с Matlab. Чтобы облегчить себе жизнь, мы используем ряд простых приёмов.
Важно уделить внимание операциям сравнения. Сравнивать на равенство числа с плавающей точкой нельзя (об этом подскажет решарпер). Вместо
используется
Менее очевидно, но явно проявляется в математических алгоритмах, что сравнениянелегальны по той же причине:
Также важно вникнуть в детали обработки с псевдовеличинами, такими как NaN (not a number) и Infinity. Например, в Матлабе:а в C#
Другие пути
Возможные пути облегчения жизни, которыми мы не пошли или идём, но путь пока не пройден:
Источник
