Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Математика
        Выполнимость КНФ
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Математика" «

Переход к теме
<< Назад Вперед >>
Одна страница
Модераторы: Roman Osipov, RKI, attention, paradise
  

BorisK


Удален

Еще лет 7 назад сделал на Паскале программу для решения задачи выполнимости КНФ для формул исчисления высказываний. Ее можно также использовать для ортогонализации произвольных КНФ или ДНФ и соответственно для вычисления выероятности. При составлении программы использовал придуманную мной алгебру кортежей (См. Автоматика и Телемеханика No 1,2. 1997, Кулик). Программа весьма быстро работает (это, правда, не означает, что проблема NP-полных задач решена), но 1) сделана под MS DOS, 2) не работает с другими кроме КНФ или ДНФ формулами, 3) можно добавить алгоритмы проверки правильности вывода и т.д., 4) перейти от булевых формул к более широким (алгоритмы есть). Программу могу выслать или даже повесить на сайте (без исходников). Но, может быть, есть энтузиасты, которые захотят ее усовершенствовать?

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 9 авг. 2004 12:41 | IP
VF



Administrator

Сложно представить усовершенстование программы без исходников . Я всегда был сторонником свободного распространения исходных текстов, тем более некоммерческих программ написанных "для себя"...

Всего сообщений: 3109 | Присоединился: май 2002 | Отправлено: 9 авг. 2004 13:33 | IP
BorisK


Удален

Я могу выслать и исходники, но конкретным адресатам, если буду уверен, что им ИНТЕРЕСНО этим заниматься.
BorisK

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 9 авг. 2004 14:16 | IP
Dash


Новичок

Народ!!! Помогите решить задачу, плз.

Показать что задача ВЫП КНФ решается эффективно алгоритмом перебора если длина записи m>=C*2^n, C=0.001.

Если я правильно думаю то алгоритм перебора имеет сложность : C*n*m*2^n<=C*n*m(C1*m)<=C2*m^3

я не вижу здесь ограничений на С кроме как 0<C<=1, но препод морочит мне голову, что я должен показать ему почему С=0.001!?!?!

Посоветуйте что-нибудь!!!!

Всего сообщений: Нет | Присоединился: май 2010 | Отправлено: 31 авг. 2004 1:37 | IP
BorisK


Удален

Что такое "эффективно"?, n (число переменных?), m (число конъюнктов или литералов?)?
Вообще-то длина записи - это число литералов, но у Вас ниже в формулах m, кажется, имеет другой смысл.
Здесь C в неравенстве m>=C*2^n, как мне кажется, выбрано произвольно. Если такое соотношение действует, то длина записи формулы также растет экспоненциально. Если под эффективностью понимается сложность алгоритма относительно длины записи, то она будет полиномиальной, но ведь сама задача решается за экспоненциальное время, т.к. длина записи - экспонента относительно числа переменных.

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 2 сен. 2004 11:55 | IP

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Одна страница

Форум работает на скрипте © Ikonboard.com