Методы создания самотестирующихся и самокорректирующихся программ для решения вычислительных задач

Общие принципы создания двухмодульных вычислительных процедур и методология самотестирования Пусть необходимо написать программу P для вычисления функции f так, чтобы P(x)=f(x) для всех значений x.Традиционные методы верификационного анализа и тестирования программ не позволяют убедиться с вероятностью близкой к единице в корректности результата выполнения программы, хотя бы потому, что тестовый набор входных данных, как правило, не перекрывают весь их возможный спектр. Один из методов решения данной проблемы заключается в создании так называемых самокорректирующихся и самотестирующихся программ, которые позволяют оценить вероятность некорректности результата выполнения программы, то есть, что P(x) f(x) и корректно вычислить f(x) для любых x, в том случае, если сама программа P на большинстве наборах своих входных данных (но не всех) работает корректно.

Чтобы добиться корректного результата выполнения программы P, вычисляющей функцию f, нам необходимо написать такую программу Tf, которая позволяла бы оценить вероятность того, что P(x) f(x) для любых x. Такая вероятность будет называться вероятностью ошибки выполнения программы P. При этом Tf может обращаться к P как к своей подпрограмме.

Обязательным условием для программы Tf является ее принципиальное отличие от любой корректной программы вычисления функции f, в том смысле, что время выполнения программы Tf, не учитывающее время вызовов программы P, должно быть значительно меньше, чем время выполнения любой корректной программы для вычисления f. В этом случае, вычисления согласно Tf некоторым количественным образом должны отличаться от вычислений функции f и самотестирующаяся программа может рассматриваться как независимый шаг при верификации программы P, которая предположительно вычисляет функцию f. Кроме того, желательное свойство для Tf должно заключаться в том, чтобы ее код был насколько это возможно более простым, то есть Tf должна быть эффективной в том смысле, что время выполненияTf даже с учетом времени, затраченное на вызовы P должно составлять константный мультипликативный фактор от времени выполнения P. Таким образом, самотестирование должно лишь незначительно замедлять время выполнения программы P.

Самокорректирующаяся программа это вероятностная программа Cf, которая помогает программе P скорректировать саму себя, если только P выдает корректный результат с низкой вероятностью ошибки, то есть для любого x, Cf вызывает программу P для корректного вычисления f(x), в то время как собственно сама P обладает низкой вероятностью ошибки.

Самотестирующейся/самокорректирующейся программной парой называется пара программ вида (Tf,Cf). Предположим пользователь может взять любую программу P, которая целенаправленно вычисляет f и тестирует саму себя при помощи программы Tf. Если P проходит такие тесты, тогда по любому x, пользователь может вызвать программу Cf, которая, в свою очередь, вызывает P для корректного вычисления f(x). Даже если программа P, которая вычисляет значение функции f некорректно для некоторой небольшой доли входных значений, ее в данном случае все равно можно уверенно использовать для корректного вычисления f(x) для любого x. Кроме того, если удастся в будущем написать программу P' для вычисления f, тогда некоторая пара (Tf,Cf) может использоваться для самотестирования и самокоррекции P' без какойлибо ее модификации. Таким образом, имеет смысл тратить определенное количество времени для разработки самотестирующейся/ самокорректирующейся программной пары для прикладных вычислительных функций.

Перед тем как перейти к более формальному описанию определений самотестирующихся и самокорректирующихся программ необходимо дать определение вероятностной оракульной программе (по аналогии с вероятностной оракульной машиной Тьюринга).

Вероятностная программа M является вероятностной оракульной программой, если она может вызывать другую программу, которая является исполнимой во время выполнения M. Обозначение MA означает, что M может делать вызовы программы A.

Пусть P программа, которая предположительно вычисляет функцию f. Пусть I является объединением подмножеств In, где n принадлежит множеству натуральных чисел N и пусть Dp={Dn|n N} есть множество распределений вероятностей Dn над In. Далее, пусть err(P,f,Dn) это вероятность того, что P(x) f(x), где x выбрано случайно в соответствии с распределением Dn из подмножества In. Пусть β есть некоторый параметр безопасности. Тогда (ε1, ε2)самотестирующейся программой для функции f в отношении Dp с параметрами 0 ε12 1 называется вероятностная оракульная программа Tf, которая для параметра безопасности β и любой программы P на входе n имеет следующие свойства:

    если err(P,f,Dn1, тогда программа TfP выдаст на выходе ответ "норма" с вероятностью не менее .
    если err(P,f,Dn2, тогда программа TfP выдаст на выходе "сбой" с вероятностью не менее 1β.
Оракульная программа Cf с параметром 0 ε 1 называется εсамокорректирующейся программой для функции f в отношении множества распределений Dp, которая имеет следующее свойство по входу n,x In и β. Если err(P,f,Dn, тогда CfP=f(x) с вероятностью не менее 1 β.
12,ε)самотестирующейся/ самокорректирующейся программной парой для функции f называется пара вероятностных программ (Tf,Cf) такая, что существуют константы 0 ε1 < ε2 ε 1 и множество распределений Dp при которых Tf есть (ε12)самотестирующаяся программа для функции f в отношении Dp и Cf есть εсамокорректирующаяся программа для функции f в отношении распределения Dp.
Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок