Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Ну это я так для краткости обозвал. Ну хорошо, пусть будет... 04.03.05 15:06 Число просмотров: 3404
Автор: NickP Статус: Незарегистрированный пользователь
|
> > Потом смотрим основную теорему №5. Там сказано, что
> число
> > шагов алгоритма не может превышать m, число строк
> таблицы.
>
> Не число шагов алгоритма, а число вариантов анализа
> таблицы.
Ну это я так для краткости обозвал. Ну хорошо, пусть будет число вариантов анализа таблицы.
Но сложность каждого варианта нигде не раскрыта!
> > Но во-первых m лежит в диапазон 0 <= m <= 2^n,
> где n
> > - число переменных.
>
> Решаем задачу ВЫП, её размеры - это не n.
Ладно, сознаюсь. Я не знаю как измеряются размеры задачи ВЫП, расскажите если не сложно. Но мне всетаки казалось что количество переменных - определяющий фактор. Т.к. верхняя граница скорости выполнения как раз и задается полным перебором 2^n вариантов.
> На каждом шаге анализа таблицы просматриваем один столбец.
> Следовательно на одном шаге просматривается не более m
> ячеек таблицы. Для каждого варианта столбцы просматриваются
> последовательно, двигаясь в левую сторону, следовательно
> при каждом варианте анализа просматривается не больше n
> столбцов и не больше m*n ячеек, то есть таблица
> просматривается при каждом варианте не более одного раза.
> До получения ответа на вопрос о выполнимости таблицы
> просматриваем её не более m раз.
Ладно. Допустим на каждом шаге мы просматриваем один столбец.
Тогда получается, что для каждого "вывода" нужно просмотреть всю таблицу.
Вывод - это выход на вариант 1-3. НО! выход на вариант 1 - это еще не конец "анализа"
таблицы, после получения варианта 1, мы должны снова проанализировать часть таблицы,
а потом снова и снова. Нигде не показана сложность вытекающая из этой рекурсии.
А если внимательно присмотреться к приводимым примером легко можно заметить, что
чаще всего происходит ПОЛНЫЙ перебор некоторого подмножества переменных, и только
часть переменных отсеивается в дальнейшем.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
