[es] - Kako se rade ovi tipovi zadataka?

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Kako se rade ovi tipovi zadataka?

^{19.07.2006. u 00:39 - pre 216 meseci}

Hm... možda imamo neki nesporazum oko toga šta smatramo rešenim oblikom sistema.

Evo da rešim dati sistem Fourier-Motzkin metodom:

Primera radi, eliminisaćemo

. Dakle, množimo prvu nejednačinu sa 2 i dodajemo drugoj.
Dobijamo redukovan sistem:

eliminišemo

što je tačno, pa možemo da nastavimo vraćanjem unazad... rešavanjem prethodnih redukovanih sistema po odgovarajućim nepoznatim veličinama:

tim uslovima su opisana sva rešenja.

Dakle, koliko je meni poznato, Fourier-Motzkin metodom možemo ili da rešimo sistem nejednačina (svođenjem sistema na neki ekvivalentan sistem u rešenom obliku) ili da u nekom trenutku zaključimo da je sistem protivrečan.

Druga je stvar to što se lako može konstruisati slučaj u kome je rešen oblik toliko složen da možemo samo da plačemo od muke...

_{[Ovu poruku je menjao uranium dana 19.07.2006. u 20:40 GMT+1]}

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

THEPRODIGY
Stefan Mihajlovic
Beograd, Zvezdara

Član broj: 76363
Poruke: 234
..njuel-bg.customer.sbb.co.yu.

Sajt: +381640142525

Profil

Re: Kako se rade ovi tipovi zadataka?

^{24.07.2006. u 14:26 - pre 216 meseci}

Citat:

uranium:

što je tačno, pa možemo da nastavimo vraćanjem unazad... rešavanjem prethodnih redukovanih sistema po odgovarajućim nepoznatim veličinama:

tim uslovima su opisana sva rešenja.

ovaj deo ne razumem!
sada upisujem prvi razred 6. beogradske!

Registered linux user #483732
Registrovani korisnik linux u Srbiji #1544
Registered ubuntu user #25959

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Kako se rade ovi tipovi zadataka?

^{24.07.2006. u 15:26 - pre 216 meseci}

@THEPRODIGY:

Primer koji sam uradio je isuviše jednostavan da bi se jasno pokazali svi detalji Fourier-Motzkin algoritma.
Moj prethodni post je bio upućen Nedeljku, pa nije ni bilo potrebe da ulazim u opis postupka, jer on to sve zna, a ako te zanima tačna formulacija algoritma, dokaz da je korektan i tome slično, možeš da pogledaš neku literaturu iz linearnog programiranja...

Nisam siguran šta ti nije jasno.
Nadam se da vidiš da je:

Na kraju, rešenje je skup svih uređenih parova

koji zadovoljavaju oba uslova:

što opet ima očiglednu geometrijsku interpretaciju:

u pojasu između trojke i sedmice šetamo se između zadatih pravih.

_{[Ovu poruku je menjao uranium dana 24.07.2006. u 16:49 GMT+1]}

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

THEPRODIGY
Stefan Mihajlovic
Beograd, Zvezdara

Član broj: 76363
Poruke: 234
..njuel-bg.customer.sbb.co.yu.

Sajt: +381640142525

Profil

Re: Kako se rade ovi tipovi zadataka?

^{24.07.2006. u 21:08 - pre 216 meseci}

shvatio u potpunosti!

Registered linux user #483732
Registrovani korisnik linux u Srbiji #1544
Registered ubuntu user #25959

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.

+2790 Profil

Re: Kako se rade ovi tipovi zadataka?

^{25.07.2006. u 16:03 - pre 216 meseci}

@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?

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.

Neka je dat sistem relacija

R(x,y,t) : x=cos(t), y=sin(t), x,y,t su realni brojevi.

Eliminacijom parametra t dobijamo relaciju

S(x,y) : x²+y²=1.

Postavlja se pitanje u kojoj su logičkoj vezi te dve relacije. Da li možemo kvadrate zameniti kubovima? Zašto baš ta jednačina, a ne neka druga?

Veza je sledeća:

Na žalost, u Beogradu se još ne zna za ovo "otkriće".

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.

Ti si ovde samo jedan sistem relacija preveo u neki drugi oblik o kome bi se koglo raspravljati da li je jednostavniji od polaznog.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Kako se rade ovi tipovi zadataka?

^{26.07.2006. u 18:49 - pre 216 meseci}

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

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

.

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

(ili su svi mešavina

), onda:
Uslove sa koeficijentima

proglasi redukovanim sistemom

i idi na korak 1.

6. Ako postoji makar jedan par nejednačina sa koeficijentima

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

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

.
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

-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.}

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.

+2790 Profil

Re: Kako se rade ovi tipovi zadataka?

^{29.07.2006. u 18:07 - pre 216 meseci}

Citat:

uranium: Neka je, primera radi, yadat sistem relacija P po promenljivim...i neka nam podje za rukom da nekim transformacijama dobijemo neka ograničenja za promenljivu x_n npr. S(x₁,...,x_n) koja su ekvivalentna sistemu relacija Q

Ja ovde ništa ne razumem. Pojasni mi to i potrudi se da budeš maksimalno precizan.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Kako se rade ovi tipovi zadataka?

^{29.07.2006. u 22:41 - pre 216 meseci}

Ako pričamo o eliminaciji promenljive u kontekstu FME evo još jednom:

Neka je dat sistem

.
Recimo da želimo da eliminišemo promenljivu

.
Originalni sistem linearnih nejednačina dovedemo u ekvivalentan oblik

za neke

.

Sada imamo redukovan sistem

u kome se promenljiva

ne pojavljuje eksplicitno, a to nam olakšava traženje rešenja. Naglasimo i to da je promenljiva

potpuno određena promenljivama

. Dakle, ako bismo hteli da "teramo mak na konac", redukovan sistem bi mogli da pišemo kao

, ali to se ionako podrazumeva.

U prethodnoj poruci sam detaljno objasnio da će u slučaju FME biti

.

Naravno, ovo nije jedini način da se to formalno opiše (ja vidim bar još dve varijante).

_{Sistem nejednačina je shvaćen kao relacija.

Relacija se obično poistovećuje sa skupom svih objekata koji je zadovoljavaju.}

Ja se nadam da si u celosti pročitao moj prethodni post, pa ako i dalje vidiš neku grešku u vezi sa FME - molim te napiši precizno o čemu se radi.

Ako imaš da napišeš nešto uopšteno o eliminaciji bilo bi mi zadovoljstvo da to pročitam.

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.

+2790 Profil

Re: Kako se rade ovi tipovi zadataka?

^{29.07.2006. u 22:49 - pre 216 meseci}

Citat:

uranium: Naglasimo i to da je promenljiva

potpuno određena promenljivama

Zapravo, jednoznačno je određen skup svih mogućih vrednosti za x_n. No, u prethodnom postu si u delu koji sam citirao ipak govorio uopšteno o eliminaciji parametara. Ovo sada jeste čisto, ali je ograničeno samo na slučaj Furije-Mockinovog algoritma. No, čak i u tom slučaju tome treba da prethodi neka opštija priča. Džaba nam algoritam ako ne znamo šta taj algoritam tačno radi, to jest, šta mu je ulaz, a šta izlaz.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Kako se rade ovi tipovi zadataka?

^{29.07.2006. u 22:54 - pre 216 meseci}

Slažem se i zahvaljujem se na ispravci.

Da li možeš da mi preporučiš nešto za čitanje o toj opštoj priči?

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.

+2790 Profil

Re: Kako se rade ovi tipovi zadataka?

^{30.07.2006. u 11:45 - pre 216 meseci}

Pa, sama definicija je jednostavna. Data je relacija R(x₁,...,x_n,t). Eliminisati parametar t znači naći potrebne i dovoljne uslove po x₁,...,x_n takve da relacija R(x₁,...,x_n,t) ima barem jedno rešenje po t. E sad, ako te zanima nešto više o eliminaciji kvantora, ima teorija koje je dopuštaju u opštem slučaju, kao i onih drugih. Tu naravno da ima tomova i tomova knjiga, ali evo nekih teorija koje dopuštaju QE.

- Teorija uređenih realno zatvorenih polja (sledstveno, elementarna euklidska/hiperbolička/projektivna/eliptička/afina geometrija).
- Teorija algebarski zatvorenih polja.
- Teorija algebarski zatvorenih polja date karakteristike.
- Teorija diferencijalno zatvorenih polja.
- Teorija gustih linearnih uređenja sa krajevima/bez krajeva/sa levim krajem bez desnog/sa desnim krajem bez levog.
- Teorija struktura (R,+,<), (Q,+,<) (ista je).

Zanimljivo je da teorija strukture (R,+,*,0,1,<,exp), gde je exp unaran funkcijski znak za eksponencijalnu funkciju, dopušta QE, ali se ne zna da li je odlučiva.

Čak i kada neka teorija ne dopušta QE u opštem slučaju, to ne znači da nema važnih posebnih slučajeva QE u njoj. Recimo, teorija algebarskih polja ne dopušta QE u opštem slučaju, ali zato znamo kada kvadratan sistem linearnih jednačina nad poljem ima tačno jedno rešenje - upravo onda kada mu je determinanta različita od nule.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu