Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Вот именно, что внимателней ;-) 09.03.05 20:35 Число просмотров: 3592
Автор: Партизан Статус: Незарегистрированный пользователь
|
> > У Тельпиза как раз выходом на исходы 1 или 2-3 и
> > заканчивается
> > "текущий вариант анализа".
Стр. 13 статьи:
"Перед тем, как перейти к анализу ведущего столбца
с номером k - 1 (к такому анализу переходим лишь
в том случае, когда номер исхода для k-того столбца
больше 3)...".
Т. е. текщий анализ продолжается только при номерах
исходов больше 3. При исходах 1-3 текущий анализ
заканчивается (заканчивается построение набора в
третьей служебной строке, т. е. имеем здесь лист в дереве
расщепления исходной формулы). Посмотрите хотя бы
примеры - видно же, что везде третья служебная
заканчивает заполняться справа налево при исходах 1-3.
> "Текущий вариант анализа" заканчивается, только выходом на
> вариант 2-3
Выходом на варианты 2-3 вообще-то заканчивается
решение задачи выполнимости, т. к. при этих
исходах имеем выполнимость и даже построенный
выполняющий набор. Дальнейший анализ в этом
случае - это уже не решение задачи выполнимости,
а поиск остальных выполняющих наборов.
> или при получении 0 в варианте 1.
При получении 0 для всей исходной формулы опять
же заканчивается не текущий анализ, а вообще поиск
выполняющих наборов, т. к. если формула
тождественно равна нулю, значит выполняющих
наборов для неё больше нет.
> Все остальные выходы на вариант 1 приводят к рекурсии.
Все остальные выходы на вариант 1 - это
"локальный 0", т. е. 0 только для анализируемой на
данном шаге подтаблицы (с исключёнными строками
и столбцами) и это означает, что дальнейшее
построение набора (т. е. дальнейшее заполнение
третьей служебной строки) не имеет смысла, т. к.
уже при текущем неполном наборе ясно, что здесь
выполнимого набора не найдём и надо что-то менять
в этом текущем наборе, а меняем значение в одном
из тех столбцов, который является столбцом
ветвления (исход 6б), и после этого в этом столбце
ветвления не будет, а именно, в этом столбце
меняется T на 5 или T* на 4, а в каком из столбцов
ветвления менять значение - определяется при
помощи построения резолюций: если
результирующая резольвента не будет равна нулю,
то начало этого резолюционного вектора и
покажет, в каком столбце поменяется значение
и с этого столбца продолжится уже следующий
вариант анализа и с этого столбца изменится
следующая третья служебная строка.
> > > таблицы, после получения варианта 1, мы должны
> > > снова проанализировать часть таблицы,
> > Пусть даже всю таблицу - O(l). Общее число этих
> > вариантов анализа будет не
> > больше количества дизъюнктов m.
> Откуда это следует?
Это имелось в виду до нахождения первого выполняющего
набора, или получения невыполнимости для всей исходной
анализируемой таблицы.
При каждом варианте анализа, когда он заканчивается
исходом 1, у нас имеются векторы (а значит и дизъюнкты),
помеченные звёздочкой. Звёздочкой помечаем по одному
вектору, который приводил нас к исходам 4 или 5
(т .е. когда по анализируемой переменной не получаем
ветвления), а также помечаем звёздочкой пару векторов,
приведшую к исходу 1. Те из векторов, помеченных звёздочкой,
которые потребуются на этапе вычисления резолюций,
войдут в минимальный согласованный сегмент.
Т. е. количество этих минимальных согласованных
сегментов - количество вариантов анализа.
Дальше см. стр. 28, там доказательство того, что количество
этих сегментов не может быть больше числа m - количества
строк исходной таблицы (количества дизъюнктов исходной формулы).
> > > А если внимательно присмотреться к приводимым
> > > примером
> > > легко можно заметить, что
> > > чаще всего происходит ПОЛНЫЙ перебор некоторого
> > > подмножества переменных, и только
> > > часть переменных отсеивается в дальнейшем.
> > Что Вы называете ПОЛНЫМ перебором некоторого
> > подмножества переменных?
> > O(n) - это не экспоненциальная сложность. ;-)
> Ну вот в таблице 1, явно идет полный перебор значений
> переменных 4,5. Для 6 переменных это довольно много.
Немного.
Перебор по двум переменным - это 2^2 = 4
Перебор по 6 переменным - это 2^6 = 64, в 16 раз больше.
Всё равно, общее количество вариантов анализа (количество
третьих служебных строк, количество построенных наборов)
равно 10, а количество строк в исходной таблице (количество
дизъюнктов в исходной формуле КНФ) равно 28.
10 <= 28, так что всё сходится с утверждениями о сложности.
> Если
> для каждых n переменных мы будем иметь k = n/3 которые
> будут перебираться полностью, то где-же тут полимиальная
> сложность?
> Ну даже, если это будет и не n/3, но все равно значительная
> чать переменных, мы полимиальной сложности не получим.
Число m, как я упоминал, для k-ВЫП реальных задач обычно
приблизительно пропорционально числу n, и коэффициент
пропорциональности зависит от k.
Допустим, задача 3-ВЫП, и 1000 переменных и 4096 дизъюнктов.
Значит, количество строк в исходной таблице - 4096, количество
столбцов - 1000, и, если верить Тельпизу, количество минимальных
согласованных сегментов (количество вариантов анализа
таблицы) будет не больше 4096, т. о. получается, что может
быть не больше 12 переменных, по которым может произойти
полный перебор. Т. е. количество переменных, по которым
может произойти полный перебор, может возрастать в среднем
не быстрее чем log от m, а значит и log от n.
Зависимость не пропорциональная, а логарифмическая.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
