информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsПортрет посетителяГде водятся OGRы
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Google закрывает безлимитные Photos 
 Имя компании как средство XSS-атаки 
 Утекший код XP и Windows Server... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / site updates
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Посмотрите ещё более внимательно... 04.03.05 22:14  Число просмотров: 2976
Автор: Партизан Статус: Незарегистрированный пользователь
Отредактировано 06.03.05 17:54  Количество правок: 1
<"чистая" ссылка>
>>> Потом смотрим основную теорему №5. Там сказано, что число
>>> шагов алгоритма не может превышать m, число строк таблицы.

>> Не число шагов алгоритма, а число вариантов анализа
>> таблицы.

> Ну это я так для краткости обозвал. Ну хорошо, пусть будет
> число вариантов анализа таблицы.
> Но сложность каждого варианта нигде не раскрыта!

Каждый вариант - это фактически прохождение какой-либо ветви дерева
расщепления формулы.
Если ветвь дерева "закрылась" (исход 1 у Тельпиза),
т. е. не получили ни пустого дизъюнкта (нулевой вектор у Тельпиза),
ни выполняющего набора, то переходим к следующему варианту анализа.
При каждом варианте анализа до получения результата "невыполнимость"
или до получения первого выполняющего набора в резолюционном выводе
участвует какой-нибудь дополнительный дизъюнкт, который в предыдущих
вариантах (в предыдущих ветвях дерева) не участвовал, поэтому
количество вариантов анализа (количество пройденных ветвей в дереве
расщепления) ограничено не 2^n, а количеством дизъюнктов m.
Каждый анализ состоит из нескольких шагов. На каждом шаге анализируется
какая-либо переменная (столбец в таблице).
Всего переменных (столбцов) - n, значит количество шагов - не больше n.
Таким образом, при каждом анализе таблица просматривается не более
одного раза, сложность - не больше O(m*n), или если использовать разреженную
таблицу - O(l), где l - общее число вхождений всех переменных в формулу
(общее число непустых ячеек в таблице).

>>> Но во-первых m лежит в диапазон 0 <= m <= 2^n, где n
>>> - число переменных.

>> Решаем задачу ВЫП, её размеры - это не n.

> Ладно, сознаюсь. Я не знаю как измеряются размеры задачи
> ВЫП, расскажите если не сложно.

А тут не надо ни чего знать, или Вы КНФ никогда не видели? Какие у КНФ размеры?
Количество переменных - n,
количество дизъюнктов (клозов) - m,
общее число l вхождений всех переменных в формулу.
Для k-ВЫП ещё: k - максимальный размер дизъюнкта.
l в общем-то определяет длину всей формулы F, поэтому можно сказать,
что l - определяет размер формулы КНФ в целом.
Ясно, что l<=m*n, а конкретно для задачи k-ВЫП l<=m*k.
Если l сравнимо с m*n, т. е. близко к m*n (не знаю, бывает ли такое в
реальности), тогда можно хранить формулу КНФ в памяти в виде 2-мерной таблицы
размерами m*n, как это сделано у Тельпиза. Тогда и оценивать сложность можно
относительно произведения m*n.
Если же l много меньше m*n, тогда разумнее хранить КНФ в разреженной таблице,
её размеры как раз и определяются количеством непустых ячеек, т. е. числом l.
К тому же разреженная таблица и ускорит обработку - не надо будет
просматривать пустые ячейки, т. е. и время однократного прочтения всей
таблицы тоже будет пропорционально числу l.

> Но мне всетаки казалось что
> количество переменных - определяющий фактор. Т.к. верхняя
> граница скорости выполнения как раз и задается полным
> перебором 2^n вариантов.

Угу. Но сложность алгоритма нужно оценивать относительно размеров задачи.

Известно, что для k-ВЫП случайного вида некий "фазовый переход", в смысле
есть некое число, зависящее от k, что если m/n заметно превышает это число,
то вероятность того, что КНФ выполнима, резко падает, стремится к нулю.
Если m/n меньше этого числа, то, наоборот, скорее всего КНФ выполнима.
Для 3-ВЫП, если не ошибаюсь фазовый переход происходит при отношении m/n
равном чуть больше 4 (4.2 или 4.25 - не помню).
Т. е. реально m имеет размеры сравнимые с n. И если сложность решения
относительно n полиномиальна, тогда и относительно l будет полиномиальна,
если относительно n - экспоненциальна, тогда и относительно l будет
экспоненциальна.

Если, как Вы говорите, m экпоненциально зависит от n (что почти невероятно в
реальных задачах), тогда оценивать сложность задачи ВЫП относительно n -
неразумно. Да и сведение других NP-полных задач размера n к задаче ВЫП не
будет полиномиальным, что не есть правда.

Обычно, оценивают сложность решения ВЫП относительно m или l.

>> На каждом шаге анализа таблицы просматриваем один
>> столбец.
>> Следовательно на одном шаге просматривается не более m
>> ячеек таблицы. Для каждого варианта столбцы
>> просматриваются
>> последовательно, двигаясь в левую сторону,
>> следовательно
>> при каждом варианте анализа просматривается не больше
>> n столбцов и не больше m*n ячеек, то есть таблица
>> просматривается при каждом варианте не более одного
>> раза.
>> До получения ответа на вопрос о выполнимости таблицы
>> просматриваем её не более m раз.

> Ладно. Допустим на каждом шаге мы просматриваем один
> столбец.
> Тогда получается, что для каждого "вывода" нужно
> просмотреть всю таблицу.

Не "вывод", "вариант анализа" у Тельпиза, фактически - это прохождение
одной ветви дерева расщепления.

> Вывод - это выход на вариант 1-3. НО! выход на вариант 1 -
> это еще не конец "анализа"

У Тельпиза как раз выходом на исходы 1 или 2-3 и заканчивается
"текущий вариант анализа".

> таблицы, после получения варианта 1, мы должны снова
> проанализировать часть таблицы,

Пусть даже всю таблицу - O(l). Общее число этих вариантов анализа будет не
больше количества дизъюнктов m.

> а потом снова и снова. Нигде не показана сложность
> вытекающая из этой рекурсии.

См. теорему 5. Сложность O(m) * сложность одного варианта анализа, общая
сложность до находения первого выполняющего набора - O(m*l) или
O(m*m*n), если таблица неразрежена (т. е. хранятся и обрабатываются пустые
ячейки).

> А если внимательно присмотреться к приводимым примером
> легко можно заметить, что
> чаще всего происходит ПОЛНЫЙ перебор некоторого
> подмножества переменных, и только
> часть переменных отсеивается в дальнейшем.

Что Вы называете ПОЛНЫМ перебором некоторого подмножества переменных?
O(n) - это не экспоненциальная сложность. ;-)

Экспоненциальная сложность - это, например, ПОЛНЫЙ перебор
_всех_наборов_значений_ переменных O(2^n)
или подмножества переменных, в случае, если это
подмножество имеет размеры O(n).

Составление третьей служебной строки в процессе одного анализа
таблицы - это и есть фактически составление набора значений переменных:
на каждом шаге запись номера исхода 2, 4, T или 3, 5, T* в третью служебную
строку означает, что соответствующей переменной присваивается значение
1 или 0 (см. внизу страницы 14 ) и исключаются из рассмотрения
выполненные (принявшие значение =1) дизъюнкты (строки таблицы),
а в оставшихся вычёркивается эта переменная. Кроме исхода 6б - в этом случае
соответствующая переменная в набор не входит (т. е. получается неполный набор)
Причём расщепление формулы ("ветвление", "разбиение таблицы на две подтаблицы"
у Тельпиза) осуществляется только при выходе на исход 6б, а при исходах 4 и 5, 6а
ветвления не происходит.

Посмотрите ещё более внимательно: где-нибудь количество вариантов анализа,
а значит и число рассмотренных наборов превышает m?

Чтобы доказать, что Тельпиз неправ, достаточно придумать пример простейшей
таблицы, на которой его алгоритм будет давать больше, чем m вариантов анализа,
или будет зацикливаться...

Кстати, вот ссылка на работу (институт Стеклова) 2001 года , где описаны и
проанализированы на русском языке некоторые алгоритмы выполнимости:
http://cs.roosevelt.edu/~dantsin/ps/DHIV01b.ps
<site updates> Поиск 








Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2020 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach