|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 18 Apr 2002 14:20:58
To : Constantin Stefanov
Subject : Эквивалентность формул.
--------------------------------------------------------------------------------
Replying to a message of Constantin Stefanov to Max Alekseyev:
CS>>> Есть две формулы, представленные деревьями. Требуется определить,
CS>>> являются ли эти два дерева представлениями одной и той же формулы
CS>>> (в идеале - с учетом коммутативности и ассоциативности, но для
CS> Э-э-э, тут я просто спутал. Имеется в виду коммутативность и
CS> дистрибутивность, ассоциативность у сложения и умножения
CS> предполагается. Вообще, в идеале это задаваемые шаблоны, т.к. речь
CS> идет об анализе программ на Си, а там еще есть дистрибутивность
CS> конъюнкции по дизъюнкции и наоборот, два унарных минуса можно
CS> сократить и т.д.
[...]
MA>> Если интересно, могу предложить эффективный вероятностный алгоритм.
CS> Интересно.
Прежде всего обозначим параметры задачи: n = число переменных, m = число
операций в дереве формулы.
Формула есть не что иное как "линейная" программа, т.е. последовательность чисел
P: x_1, x_2, ..., x_n, f_1(.), f_2(.), ..., f_m(.),
где сначала идут переменные, а затем функции от предшествующих чисел
последовательности. Результатом вычислений называется последнее число, т.е.
значение функции f_m(.), которое обозначается P(x_1,x_2,...,x_n).
Задача эквивалентности линейных программ ставиться так:
Даны две линейные программы P и Q от набора переменных x_1,...,x_n. Верно ли что
P(x_1,...,x_n)=Q(x_1,...,x_n) на любом наборе значений переменных?
Вероятностный алгоритм для решения этой задачи:
Сгенерировать случайное простое p число длины 4m (в двоичном представлении).
Сгенерировать случайные числа x_1,...,x_n из интервала [0,2^(n+m)].
Вычислить u=P(x_1,...,x_n) mod p и v=P(x_1,...,x_n) mod p.
Если u=v вернуть "эквивалентны", иначе вернуть "не эквивалентны".
Доказывается, что вероятность ошибки, т.е. возврата "эквивалентны" в случае
неэквивалетности программ, равна
O(m 2^(-2m) + 2^(-n)).
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.7
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Эквивалентность формул.