BorisK
Удален
|
    
Еще лет 7 назад сделал на Паскале программу для решения задачи выполнимости КНФ для формул исчисления высказываний. Ее можно также использовать для ортогонализации произвольных КНФ или ДНФ и соответственно для вычисления выероятности. При составлении программы использовал придуманную мной алгебру кортежей (См. Автоматика и Телемеханика No 1,2. 1997, Кулик). Программа весьма быстро работает (это, правда, не означает, что проблема NP-полных задач решена), но 1) сделана под MS DOS, 2) не работает с другими кроме КНФ или ДНФ формулами, 3) можно добавить алгоритмы проверки правильности вывода и т.д., 4) перейти от булевых формул к более широким (алгоритмы есть). Программу могу выслать или даже повесить на сайте (без исходников). Но, может быть, есть энтузиасты, которые захотят ее усовершенствовать?
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 9 авг. 2004 12:41 | IP
|
|
VF 
Administrator
|
 
Сложно представить усовершенстование программы без исходников  . Я всегда был сторонником свободного распространения исходных текстов, тем более некоммерческих программ написанных "для себя"...
|
Всего сообщений: 3110 | Присоединился: май 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!?!?!
Посоветуйте что-нибудь!!!!
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 31 авг. 2004 1:37 | IP
|
|
BorisK
Удален
|
Что такое "эффективно"?, n (число переменных?), m (число конъюнктов или литералов?)?
Вообще-то длина записи - это число литералов, но у Вас ниже в формулах m, кажется, имеет другой смысл.
Здесь C в неравенстве m>=C*2^n, как мне кажется, выбрано произвольно. Если такое соотношение действует, то длина записи формулы также растет экспоненциально. Если под эффективностью понимается сложность алгоритма относительно длины записи, то она будет полиномиальной, но ведь сама задача решается за экспоненциальное время, т.к. длина записи - экспонента относительно числа переменных.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 2 сен. 2004 11:55 | IP
|
|
|
Форум
Выполнимость КНФ
