Citat:
Nedeljko:
@uranium
Kako misliš da "eliminišeš" promenljivu od čije vrednosti bitno zavisi da li je sistem relacija zadovoljen ili ne (recimo, relacija R(x) je zadovoljena za x=2, a nije zadovoljena za x=3). Da li uopšte znaš šta je eliminacija promenljivih?
Pa i sam si u prethodnom postu napisao da
FME (
Fourier-Motzkin eliminacija) može da nam odgovori na pitanje zadovoljivosti datog sistema lin. ne/jednačina. Kako misliš da nam to odgovori a da ne saznamo tako elementarnu stvar kao što je opseg dozvoljenih vrednosti te navedene nepoznate
?
Citat:
Nedeljko:
Ja znam da se na Matematičkom fakultetu u Beogradu eliminacija parametara radi bez ikakvog razumevanja, jer više od 90% profesora pomenutog fakulteta i ne zna šta je to, već samo pljuje po matematičkoj logici. Možeš da pitaš Žarka Mijajlovića ili bilo kog logičara šta je to. Svi ostali će samo da te zavlače. Te, to ti je kad nešto uradiš da se izgubi taj parametar, te ne znam ni ja.
napisao si neke mnogo zanimljive stvari, ali bojim se da ću otići u OT ako krenem da ih komentarišem
Ako si želeo da me oslobodiš odgovornosti za (eventualnu) zabludu u kojoj se nalazim - hvala ti - međutim, potrudiću se u nastavku da pokažem da
nisam u zabludi
Pošto se iz onog što si napisao može zaključiti da se tvoje i Žarkovo mišljenje o eliminaciji podudara (a budući da si i ti logičar) mogu da zamolim tebe da prokomentarišeš moje viđenje eliminacije.
Neka je, primera radi, zadat sistem relacija
u f-ji promenljivih
i neka nam pođe za rukom da nekim transformacijama dobijemo neka ograničenja za promenljivu
npr.
koja su
ekvivalentna sistemu relacija
u f-ji promenljivih
(u kojem se
ne pojavljuje eksplicitno). Na osnovu konstrukcije sistema
jasno je da mora biti
. Ako sada rešimo novi sistem (a to bi trebalo da bude lakše) možemo da se sa tim novootkrivenim vezama između promenljivih
vratimo u
a ako je moguće i u originalni sistem i pokušamo da pronađemo eventualno još neka ograničenja za promenljivu
. U opštem slučaju, sistemi
i
ne moraju biti ekvivalentni, ali ako pričamo o
FME pokazaću kasnije da sistemi
jesu ekvivalentni.
Još nešto, sistem od
linearnih nejednačina sa
nepoznatih zapisan na standardan način je u stvari zamena za
Svaka eliminacija promenljive recimo
(u
FME) iz npr.
-te i
-te nejednačine zapravo ima oblik
i kad god piše ovo poslednje, podrazumevamo da tu u stvari piše ono prvo.
Citat:
Nedeljko:
Dakle, ne radi se tu o ekvivalentnim sistemima relacija. Furije-Mockinov algoritam je algoritam za eliminaciju željene promenljive iz sistema linearnih jednačina i nejednačina, a ne za rešavanje.
Pa ovo me navodi na zaključak da je ono što ti smatraš
FME zapravo samo "prvo poluvreme" onog što ja smatram
FME. Tako da mi ne gine kucanje...
Fourier-Motzkin algoritam eliminacije
preuzeto iz Linear Programming, 1: Introduction - George B. Dantzig, Mukund N. Thapa
Obeležimo dati sistem nejednačina sa
, započnimo proces stavljajući
i
.
1. Postavi
. Ako je
idi na korak
7.
2. Nejednačine iz
zapiši tako da se promenljiva
pojavljuje sa koeficijentom
,
ili
na samo jednoj (recimo levoj) strani nejednačine a da sve nejednačine pri tom budu zapisane sa relacijom
. Sve uslove u kojima je koeficijent uz
jednak
smatraj delom redukovanog sistema.
3. Ako su svi koeficijenti uz
jednaki
, označi promenljivu
kao proizvoljnu, postavi
i idi na korak
1.
4. Ako su svi koeficijenti uz
jednaki
(ili
), onda:
{Ako je
proglasi
za proizvoljne. Idi na korak
9.}
5. Ako su svi koeficijenti uz
mešavina
i
(ili su svi mešavina
i
), onda:
Uslove sa koeficijentima
proglasi redukovanim sistemom
i idi na korak
1.
6. Ako postoji makar jedan par nejednačina sa koeficijentima
i
uz promenljivu
, onda: Za svaki takav par, dodaj redukovanom sistemu njihov zbir. Postavi
da je redukovani sistem i idi na korak
1.
7. Provera neprotivrečnosti. Proveri desne strane sistema
. Ako je barem jedna vrednost pozitivna - proglasi polazni sistem protivrečnim i stani. U protivnom, postavi
.
8. Određivanje
. Ako je
, odredi
na osnovu
. Postavi
.
9. Smenjivanje unazad. Počni sa
. Dok je god
radi sledeće:
a) Ako
nije označeno kao proizvoljno i ako je
vrati
u
i odredi
b) Postavi
Pozabavimo se sada ekvivalentnošću. Jednostavnosti radi, razmatraćemo šta se dešava pri eliminaciji promenljive
.
Sistem
možemo da (nakon sređivanja i izostavljanja kvantora radi sažetosti) podelimo u tri klase:
:
,
:
,
:
,
Za početak, zanimljiv je slučaj kada je
i
.
Uparivanjem nejednačina iz
sa nejednačinama iz
dobijamo sistem od
nejednačina u kojima se
ne pojavaljuje eksplicitno.
Kao što je ranije objašnjeno, svako rešenje originalnog sistema mora biti rešenje i ovog novodobijenog.
Važi i obrnuto.
Za svaki par
,
eliminacijom promenljive
iz
-te i
-te nejednačine (iz odgovarajućih klasa) dobijemo:
Time je pokazano da je svako rešenje redukovanog sistema ujedno i rešenje originalnog sistema.
Citat:
Nedeljko:
Ti si ovde samo jedan sistem relacija preveo u neki drugi oblik o kome bi se koglo raspravljati da li je jednostavniji od polaznog.
Sa ovim se u potpunosti slažem.
Smemo li se uopšte nadati da je moguće naći neku "jednostavnu" reprezentaciju rešenja?
Na kraju, svako ko je spreman da "proguta" npr.
ne bi trebalo da ima bilo šta protiv onakvog oblika rešenja sis. lin. nej. jer je tamo situacija daleko čistija.
[Ovu poruku je menjao uranium dana 26.07.2006. u 20:33 GMT+1]
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.