Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 19.03.2003, 16:29   #1
4294967296
 
Boyov's Avatar
 
Join Date: 03 2002
Location: /proc/1
Age: 33
Posts: 379
Downloads: 4
Uploads: 0
Reputation: 0 | 0
Default Boolean Functions

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
__________________
Free your mind and your OS will follow
Reply With Quote
Old 19.03.2003, 18:19   #2
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

ox-ox, надо все это дело вспоминать я забыл уже.
Reply With Quote
Old 19.03.2003, 19:44   #3
Консервативн
 
VX's Avatar
 
Join Date: 01 2002
Location: Кавказская Албания
Posts: 889
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Es "Chust"-i kursaini vra es mtatsum BTW?
Reply With Quote
Old 19.03.2003, 20:15   #4
Дошкольник
 
Nemra's Avatar
 
Join Date: 07 2002
Location: South Park
Posts: 82
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Talking

Хе-хе... это было моей курсовой на 4-ом курсе.... вроде и файлы реализации есть, надо поискать там пара-тройка классов и алгоритмов...
Reply With Quote
Old 19.03.2003, 21:39   #5
Младенец
 
Join Date: 06 2002
Location: Armenia,Yerevan
Age: 32
Posts: 11
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post Boolean function !!!

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 b@ t@ v dalyneyshem ponimal moi znaki .
Ya dumayu t@ 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 b@ ustanity operacii =>,<=>,+ ostaviv tolyko and ,or,not
2.
ispolyzuem zakon@ de Morgana
~(pvq)=(~p)(~q),
~(pq)=(~p)v(~q)
dlya togo chto b@ kajdaya operaciya
otricanie otnosilasy tolyko k odnoi
peremennoi .
3.
ispolyzuem svoistvo distributivnosti i drugie svoistvo ,chtob@ 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).
Chtob@ poluchity ee (KKNDz),nujno [email protected] dizyunkt ,v kotorom ne xvataet
kakoi-libo peremennoi ,povtority dvajd@: s etoi peremennoi i ee otricaniem:
f(p,q,r)=(~pvqvr)(~pvqv~r)(pv~qv~r)(~pv~qv~r).

Poka!
__________________
The best way to save money is to invest it in knowledge and/or information area...
Reply With Quote
Old 20.03.2003, 09:50   #6
4294967296
 
Boyov's Avatar
 
Join Date: 03 2002
Location: /proc/1
Age: 33
Posts: 379
Downloads: 4
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally posted by VX
Es "Chust"-i kursaini vra es mtatsum BTW?
Tochno tochno . xexe

Quote:
Хе-хе... это было моей курсовой на 4-ом курсе.... вроде и файлы реализации есть, надо поискать там пара-тройка классов и алгоритмов
Chto za algoritm? Sam pisal ? Esli ne slojno postni please.

Quote:
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
Reply With Quote
Old 20.03.2003, 11:40   #7
Младенец
 
Join Date: 06 2002
Location: Armenia,Yerevan
Age: 32
Posts: 11
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

Privet!
Artem a zachem t@ ne ispolyzuesh metod
Kvayna (ayspes asats sosndzumov)??
potom esli b@ t@ [email protected] [email protected] t@ b@ zametil chto v primere ya skazal neskolyko slovami kak minimizirovaty etu funkciu...
Ladno, kstati kak ya ponyal t@ 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
Reply With Quote
Old 20.03.2003, 13:38   #8
4294967296
 
Boyov's Avatar
 
Join Date: 03 2002
Location: /proc/1
Age: 33
Posts: 379
Downloads: 4
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally posted by GeniusRaf
Privet!
Artem a zachem t@ 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.

Quote:
Originally posted by GeniusRaf

potom esli b@ t@ [email protected] [email protected] t@ b@ zametil chto v primere ya skazal neskolyko slovami kak minimizirovaty etu funkciu...
Tak ya je prosil normal'no rabotayushii algorithm a ne "neskolyko slovami"

Quote:
Originally posted by GeniusRaf

Ladno, kstati kak ya ponyal t@ 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.
Reply With Quote
Old 20.03.2003, 16:54   #9
Младенец
 
Join Date: 06 2002
Location: Armenia,Yerevan
Age: 32
Posts: 11
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Quote:
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 t@ voobshe znaish chto takoe "Search Engine"naprimer (alltheweb.com)napishi ka tam t@ etot
tvoi [email protected] metod "Quine-McCluskey " i uvidish mnogo [email protected] v [email protected] napisano pochti vse ob etom metode.(mojet T@ ne ponimaesh po Angliskii),
Ya b@ s udovolystiem pomog tebe prosto u menya net vremeni v [email protected] moment.(Tak chto sam chitai)
Udachi
Reply With Quote
Old 22.03.2003, 21:14   #10
Дошкольник
 
Nemra's Avatar
 
Join Date: 07 2002
Location: South Park
Posts: 82
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Unhappy

Sorry, не нашел файл-ов... а дело было лет 5 назад так что наизусть не помню...
Алгоритм был "изотоп"-ом Блейка, как вы выражаетесь Получая формулу в виде нормальной коньюктивной формы и используя две операции (поглощения и склейки) алгоритм делал проход пока возможно применение. Всех тонкостей я к сожалению просто не помню. Извини...
А реализация что-то вроде:
enum Bool {NEGATIVE, POSITIVE, NOTPRESENT};
typedef std::vector<Bool> ElementaryConjunction;
typedef std::list<ElementaryConjunction> NormalDisjunctiveForm;
Reply With Quote
Old 24.03.2003, 22:06   #11
4294967296
 
Boyov's Avatar
 
Join Date: 03 2002
Location: /proc/1
Age: 33
Posts: 379
Downloads: 4
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally posted by GeniusRaf
Slushay da t@ voobshe znaish chto takoe "Search Engine"naprimer (alltheweb.com)napishi ka tam t@ etot
tvoi [email protected] metod "Quine-McCluskey " i uvidish mnogo [email protected] v [email protected] napisano pochti vse ob etom metode.(mojet T@ ne ponimaesh po Angliskii),
Ya b@ 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,


Quote:
Ya b@ 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.


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

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 13:20.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.