[Boyov]

Zdarova

Kto nibud' mojet priduamt' algoritm kotory bi minimiziroval Bulevi funkcii , zadannie v SDNF
(Soverhennaya Dizyunktivnaya Normal'naya Forma) ili tablichno.
Ya znayu chto esrt' algoritm Kveina-Maklavski ( ya ne uveren v pravil'nosti napisaniya imen) , kotori , po suti, yavlyaetsya mashinnoy realizaciey algoritma Bleyk-a.
Esli ne slojno napi****e pliz. ego naibolee prostuyu ( na vash vzglyad ) realizaciyu toje .
Ya dumayu chto ego mojno napisat' s ispolzovaniem dinamicheskix vektorov , no ya ne mogu ponyat' kakoe naibolee optimal'noe uslovie doljno slujit' signalom dlya okonchaniem etogo algoritma.

Spasibo

Boyov

[greka]

ox-ox, надо все это дело вспоминать я забыл уже.

[VX]

Es "Chust"-i kursaini vra es mtatsum BTW?

[Nemra]

Хе-хе... это было моей курсовой на 4-ом курсе.... вроде и файлы реализации есть, надо поискать там пара-тройка классов и алгоритмов...

[GeniusRaf]

Zdarovo Tyom! dumayu chto eto mojet tebe pomochy ne smotrya na to chto eto ne programa(a prosto dumayu shto xoroshii algoritm).
p q (1) (2) (3) (4) (5) (6) (7)
0 0 .0...0...1...0...1...1...1
0 1 .0...1...1...1...0...1...0
1 0 .0...1...0...1...0...1...1
1 1 .1...1...1...0...1...0...0
p^q and (1)
pvq or (2)
p=>q implication(3)
p+q xor(4)
p<=>q equvaluant(5)
p|q not or(6)
p\q not and(7)
not x toje samoe chto(~x)
not=~
eto prosto dlya togo chto [email protected] [email protected] v dalyneyshem ponimal moi znaki .
Ya dumayu [email protected] znaesh svoistva [email protected] funkcii tak chto ya eto ne napishu no esli ponadobitsa mogu skazaty.
Ladno pereidu ka algoritmu ...
1.
p<=>q=(p=>q)(q=>p),
p=>q=(~p)vq
p+q=(~p)qvp(~q)
dlya togo chto [email protected] ustanity operacii =>,<=>,+ ostaviv tolyko and ,or,not
2.
ispolyzuem [email protected] de Morgana
~(pvq)=(~p)(~q),
~(pq)=(~p)v(~q)
dlya togo chto [email protected] kajdaya operaciya
otricanie otnosilasy tolyko k odnoi
peremennoi .
3.
ispolyzuem svoistvo distributivnosti i drugie svoistvo ,[email protected] poluchity normalynuyu formu.Chasto dlya poluchenie sknf(KKNDz)nujno ispolyzovaty sleduyushie svoistvo distributivnosti:
(pq)vr=(pvr)(qvr)
vse..
a tepery odin premer ...
f(p,q,r)=(~p)vq+rq(pvr)

f(p,q,r)=(~p)vq+rq(pvr)=
=(~(~pvq)rq(pvr))v(~pvq)~(rq(pvr))=
=p~qrq(pvr)v(~pvq)(~rv~qv(~p~r))=
=(~pvq)(~rvqv(~p~r))=
=(~pvq)(~rv~qv~p)(~rv~qv~r)=
=(~pvq)(~qv~r).

takim obrozom ,ya poluchil
(Kataryal Normal Dzev) funkcii f(p,q,r).
[email protected] poluchity ee (KKNDz),nujno [email protected] dizyunkt ,v kotorom ne xvataet
kakoi-libo peremennoi ,povtority [email protected]: s etoi peremennoi i ee otricaniem:
f(p,q,r)=(~pvqvr)(~pvqv~r)(pv~qv~r)(~pv~qv~r).

Poka!

[Boyov]

Originally posted by VX
Es "Chust"-i kursaini vra es mtatsum BTW?

Tochno tochno . xexe

Хе-хе... это было моей курсовой на 4-ом курсе.... вроде и файлы реализации есть, надо поискать там пара-тройка классов и алгоритмов

Chto za algoritm? Sam pisal ? Esli ne slojno postni please.

Zdarovo Tyom! dumayu chto eto mojet tebe pomochy ne smotrya na to chto eto ne programa(a prosto dumayu shto xoroshii algoritm).
.........................

Privet Raf, Vo pervix mne nujno bilo Minimizirovat' etu funciyu a ne poluchit' ee KND ( esli ti ne zametil bila zadana SDNF (KDNdz Kataryal Dizyunktiv Normal Dzev), tak chtmo mne KND vse ravno chto
Ribe zontik (ili zayacu STOP signal, same **** ). I eshe odno tvoy algoritm napisan tol'ko dlya 3-x peremennix, u menya ix 5!,
i voobshe menya interesuet algorithm dlya funkcii ot n peremennix.
Potom esli eto vse ravno delaetsya v ruchnuyu naibolee optimal'nim metodom ya schitayu karti KARNO, prikin' esli u tebya budet 10 peremnnix qo algorithm Zadoxnetsya
No vse ravno Spasibo .
BTW ti etot algoritm sam pridumal te et Blake-i algoritgmi izotop-a?

wishes

Boyo6

[GeniusRaf]

Privet!
Artem a zachem [email protected] ne ispolyzuesh metod
Kvayna (ayspes asats sosndzumov)??
potom esli [email protected] [email protected] [email protected] [email protected] [email protected] [email protected] zametil chto v primere ya skazal neskolyko slovami kak minimizirovaty etu funkciu...
Ladno, kstati kak ya ponyal [email protected] ne xochesh ispolyzovaty metod Karno vobshem sluchii ,tak kak eto ocheny dolgo i ne optimalno.No ya mogu pomoch s etim Algoritmom esli zaxochesh??..
A chto kasaetsya "source" moix znanii pravda govorya esty odna zamechatelynaya kniga "Teoriya Avtomatov",no ya dumayu vse chto tebe nujno [email protected] svyazano s etoi problemoi ya tebe uje soobshil.
Esli ponadobitysa esho chto nibudy to ya vsegda rad otvetity v ramkax moix znanii.
Paka

[Boyov]

Originally posted by GeniusRaf
Privet!
Artem a zachem [email protected] ne ispolyzuesh metod
Kvayna (ayspes asats sosndzumov)??

Nu ti skazal Rafik, ti mojesh sebe predstavit' ego realizaciyu ???
Pojaluysta vnimatelnee chitay posti, ya je naverxu napisal chto Metod Quine-McCluskey eto MASHINNAYA (t..e. compyuternaya ) realizaciya algorithma Bleyka (algoritm Bleyka ili Quine -a) odno i toje.

Originally posted by GeniusRaf

potom esli [email protected] [email protected] [email protected] [email protected] [email protected] [email protected] zametil chto v primere ya skazal neskolyko slovami kak minimizirovaty etu funkciu...

Tak ya je prosil normal'no rabotayushii algorithm a ne "neskolyko slovami"

Originally posted by GeniusRaf

Ladno, kstati kak ya ponyal [email protected] ne xochesh ispolyzovaty metod Karno vobshem sluchii ,tak kak eto ocheny dolgo i ne optimalno.No ya mogu pomoch s etim Algoritmom esli zaxochesh??..

Povtoryayu dlya tex kto v BRONEPOEZDE mmne nujen algoritm dly KOMPYUTERA a ne cheloveka, karti Karno klevaya i ochen' udobnaya vesh' , no vo pervix eto chisto VISUALNIY (ne podxodyashi ,ili ploxo podxodyashi dlya compyutera) metod, a vo vtorix
kogda ti minimiziruesh po kartam Karno ti naxodish odnu iz Tupikovix (Pakughayin) DNF.

[GeniusRaf]

Originally posted by Boyov

Pojaluysta vnimatelnee chitay posti, ya je naverxu napisal chto Metod Quine-McCluskey eto MASHINNAYA (t..e. compyuternaya ) realizaciya algorithma Bleyka (algoritm Bleyka ili Quine -a) odno i toje.
(Pakughayin) DNF.

Slushay da [email protected] voobshe znaish chto takoe "Search Engine"naprimer (alltheweb.com)napishi ka tam [email protected] etot
tvoi [email protected] metod "Quine-McCluskey " i uvidish mnogo [email protected] v [email protected] napisano pochti vse ob etom metode.(mojet [email protected] ne ponimaesh po Angliskii),
Ya [email protected] s udovolystiem pomog tebe prosto u menya net vremeni v [email protected] moment.(Tak chto sam chitai)
Udachi

[Nemra]

Sorry, не нашел файл-ов... а дело было лет 5 назад так что наизусть не помню...
Алгоритм был "изотоп"-ом Блейка, как вы выражаетесь Получая формулу в виде нормальной коньюктивной формы и используя две операции (поглощения и склейки) алгоритм делал проход пока возможно применение. Всех тонкостей я к сожалению просто не помню. Извини...
А реализация что-то вроде:
enum Bool {NEGATIVE, POSITIVE, NOTPRESENT};
typedef std::vector<Bool> ElementaryConjunction;
typedef std::list<ElementaryConjunction> NormalDisjunctiveForm;

[Boyov]

Originally posted by GeniusRaf
Slushay da [email protected] voobshe znaish chto takoe "Search Engine"naprimer (alltheweb.com)napishi ka tam [email protected] etot
tvoi [email protected] metod "Quine-McCluskey " i uvidish mnogo [email protected] v [email protected] napisano pochti vse ob etom metode.(mojet [email protected] ne ponimaesh po Angliskii),
Ya [email protected] s udovolystiem pomog tebe prosto u menya net vremeni v [email protected] moment.(Tak chto sam chitai)
Udachi

Vo pervix ne uchi menya chto i gde nado iskat' , (nedoros eshe) vo vtorix esli ti dumaesh chto ya ne znayu chto takoe search engine , to ti v glubokom zablujdenii (pochemu ti tak uveren v tom chto ya ne iskal eto v kakom nibud' google-e ???), v tretyix ete mi bainc KURSI CHES ( opyat' je chitay chto ya napisal v samom pervom poste) to ne nado postit' prosto tak, naschet angliyskogo
ya ne dumayu chto u tebya est' pricihini dumat' chto ya ne ponimayu po angliyski,

Ya [email protected] s udovolystiem pomog tebe prosto u menya net vremeni v [email protected] moment.(Tak chto sam chitai)
Udachi [/B]

A ti uveren chto smojesh ?
I nexera davat' mne tupie soveti tipa "(Tak chto sam chitai)".
VSE.

Sorry, не нашел файл-ов... а дело было лет 5 назад так что наизусть не помню...Алгоритм был "изотоп"-ом Блейка, как вы выражаетесь Получая формулу в виде нормальной коньюктивной формы и используя две операции (поглощения и склейки) алгоритм делал проход пока возможно применение. Всех тонкостей я к сожалению просто не помню. Извини...
А реализация что-то вроде:
enum Bool {NEGATIVE, POSITIVE, NOTPRESENT};
typedef std::vector<Bool> ElementaryConjunction;
typedef std::list<ElementaryConjunction> NormalDisjunctiveForm.

Thanks anyway