а у меня вот другая проблема, мне нужен сам алгоритм для решения системы булевых уравнений. В интернете искал , но пока ничего не нашел. Думаю, что можно метод Гауса переделать для решения таких уравнений. 

Гаусс не пойдет:
Во-первых в силу особенностей булевых функций - шанс потерять решение гораздо выше чем на действительных числах, поэтому придется проверять половину всех решений(просто занулять ведь нельзя, а у нас всего 2 цифры а не 10), что фактически эквивалентно полному перебору
Во-вторых, возможно на небольших системах он и сработает, а вот при решении систем с количеством переменных >90 надолго заглохнет, проще перебор.
Если есть желание поразвлечься - попробуйте эволюционные исчисления(ГА, муравьи, если станет интересно - пишите, я сам этим плотно занимаюсь,поделимся результатами), либо поищите специфические алгоритмы(#метод линеаризующего множества, посмотрите жадные алгоритмы, хотя они, помнится, не очень хорошо здесь работают, уверен - что-нибудь еще есть)
При количестве переменных <50 - полный перебор(если эффективно реализовать и распараллелить можно и за сотню убежать, а может и больше)
Если надо - могу более конкретную задачку на эту тему подбросить 


Это сообщение отредактировал(а) dengalf - 15.12.2009, 07:34

Если система линейная (а видимо такая и есть), то конечно Гаусса.

Работает он за O(n^3), а для булевых систем его можно реализовать с помощью битовых операций за порядка n^3 / 32 операций.

dengalf Что вы такое говорите, никакой потери точности не будет: если Гаусс применяем для решения булевых систем, то никакого типа данных, кроме булева (false/true) не потребуется, никакой потери точности. Во-вторых, асимптотика его n^3, и даже при простой реализации будет за секунду запросто решать системы с несколькими сотнями переменных. При хорошей реализации - с битовыми операциями, про что я упоминал, - будет вообще систему с 1000 переменными успевать за секунду решать.

Zhenia87 Могу помочь с реализацией на C++, на нём алгоритм даже за n^3 / 32 очень короткий и простой.

А зачем интересно?  

Если линейная - то действительно Гаусс, но в изначальной теме(откуда этот вопрос перенесли) речь шла именно о нелинейной

Опять же для нелинейных оценка - экспонента. Есть конечно алгоритмы, которые подводят к полиномиальной(да и то, думаю с некоторыми ограничениями на условия), но это, как правило, за счет параллельной обработки. Или я не прав? Задача - NP-полная...

Речь не о потере точности(какую такую точность тут в принципе можно потерять?), а о эффективности алгоритма: на каждом шаге Гаусса придется проверять не равно ли x[i] нулю, а это как раз половина полного перебора.
Повторюсь, я имел ввиду именно нелинейные системы, как и было сформулировано изначально

в дипломной работе при исправлении ошибок стирания в циклических кодах реализованных с помощью ЛПМ.



я буду реализовывать на С#, но думаю твой алгоритм на С++ очень поможет. 
У меня нужно будет решать системы такого вида, причем сложе́ние по модулю 2 :
х1+х2+nx3=0
x3+nx1+x4=0
x2+x3=0

Это сообщение отредактировал(а) Zhenia87 - 16.12.2009, 19:08

Ничего не понял. Ты должен научиться объяснять то, чем ты занимаешься людям, которые не в теме - иначе никто и не оценит...

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

Причем здесь подробности твоей дипломки и вопрос "на хрена нужно решать булевые уравнения?" Никто из тебя тайн не выпытвает, не боись...  

да я и не боюсь     просто долго объяснять всю суть. В моей дипломной работе я декодирую циклические коды, при этом могут возникнуть некоторые типы ошибок(пакеты ошибок, стирания, независимые инвертированные). Для декодирования я использую теорию логических последовательстных машин (ЛПМ). Так вот, при ошибках стирания на одном из этапов мне нужно решать системы булевых уравнений(вид которых я описал выше). Вот в чем моя проблема.

Это сообщение отредактировал(а) Zhenia87 - 16.12.2009, 22:16

что-то странное вообщем  

  

Вот решение линейных систем за N^2 / 32:



Для плохо знающих C++: трюк в том, что булевый массив bitset<макс.размер> умеет ксориться с другим таким же за (макс.размер / число_бит_в_int) операций, т.е. обычно за N/32 операций. А это место и было самым узким в алгоритме.