Линейные рекуррентные соотношения

В работе [KS] исследовались вопросы построения самотестирующихся и самокорректирующихся программ для линейных рекуррентных соотношений, т.е. соотношений видаf(n)=. Такие последовательности являются основными для многих комбинаторных и теоретико-числовых последовательностей, таких как последовательность Фибоначчи и последовательность Лукаша.

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

Аппроксимирующие функции

Пусть для данной функции fи границы ошибки, входаx, программаP(x) вычисляющая функциюf,приблизительно корректна, еслиP(x)-f(x). Это обозначается следующим образом:P(x)_ f(x). Будем также считать, чтоР(,)аппроксимирует функциюfна областиD, еслиP-fна 1-элементах областиD.

Исходя из работ [GLRSW,RS1], можно показать, как тестировать программы, которые вычисляют полиномы и функции, определенные теоремами сложения, когда выход программы, реализующей вычисления над этими полиномами или функциями является приблизительным. В этих работах также показано, как выполнить аппроксимирующие проверку, самотестирование и самокоррекцию полиномов и функциональных уравнений.

В таблице 4.3 показаны некоторые теоремы сложения для функциональных уравнений, где верна следующая форма f(x+y)=G[f(x),f(y)].

Таблица 4.3.

G[f(x),f(y)]	f(x)
f(x)+f(y)	Ax
	tg Ax
	ctg Ax
	A th Bx
f(x)f(y)-	cos Ax
f(x)f(y)+	ch Ax

Кроме того, в ряде работ (см., например, упоминания в [EKR]) было показано, как строить аппроксимирующие чекеры для ряда модулярных и логарифмических операций, а также функций sin, cos, для умножения и инвертирования матриц, решения систем линейных уравнений и определения детерминантов. Также исследовались проблемы тестирования операций деления с плавающей точкой, одномерных полиномов степени до 9 включительно и многомерных полиномов, а также тестирования ряда других тригонометрических и гиперболических функций.

3. Криптография, интерактивные доказательства Вводные замечания

Основная идея использования задач самотестирования в криптографии заключается в девизе «Защитить самих защитников». Так как криптографические методы используются для высокоуровневого обеспечения конфиденциальности и целостности информации, собственно программно-техническая реализация этих методов должна быть свободна от программных и/или аппаратных дефектов. Таким образом, самотестирование и самокоррекция программ может эффективно применяться в современных системах защиты информации от несанкционированного доступа.