63
правки
Изменения
→Примеры рандомизированных алгоритмов
Это ведет нас к алоритму, который называется рандомизированный алгоритм Ловаса. Сформулируем его: выберем случайные числа для <tex>x_{ij}</tex>. Если <tex>det(X) \ne 0</tex> значит говорим что в графе есть полное паросочетание, иначе говорим что нету. Основное преимущество этого алгоритма в том, что он может быть реализован с помощью рандомизированной <tex>NC</tex> схемы, а это значит что он может быть эффективно реализован используя параллельные вычисления.
===Проверка полиномов на равенство===
====Задача====
Есть полином с целыми коэффициентами. Нужно проверить, является ли полином тождественным нулем. Будем считать что полином представлен в виде арифметической схемы. Арифметическая схема похожа на логическую только вместо операций <tex>{\land, \lor, \neg}</tex> она использует операции <tex>{+, -, \times}</tex>. Формально это ориентированный граф в котором есть <tex>n</tex> источников и каждая вершина не являющаяся источником имеет входа и один выход. Есть одна вершина являющаяся стоком. Каждая внутрення вершина помечена одной из трех aрифметических операций. Значение полинома считается путем помещения на источники целых чисел и применения всех операций в порядки заданном графом.
Заметим что исходная задача звучала как проверка двух полиномов не равенство. Мы свели ее к проверке полинома на равенство нулю путем такого преобразования. Пусть у нас было две арифметические схемы <tex>C, C'</tex> которые нужно проверить на равенство. Мы строим новую схему <tex>D : D(x_1, ..., x_n) = C(x_1, ..., x_n) - C'(x_1, ..., x_n)</tex>.
