| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
Jelaska
Forumaš(ica)
Pridružen/a: 13. 10. 2004. (14:27:46)
Postovi: (50)16
|
|
| [Vrh] |
|
Boris Davidovič
Forumaš(ica)
Pridružen/a: 08. 01. 2004. (23:05:18)
Postovi: (3C)16
|
 Postano: 10:11 čet, 9. 3. 2006 Naslov: |
    |
|
|
Trebalo bi malo preciznije specificirati što se hoće.
Naime, na vježbama jezik je REG = "postoji DKA koji ga prepoznaje".
Na predavanjima : REG = "generiran regularnim izrazom",
KA = "postoji DKA koji ga prepoznaje".
Što se zadatka 1. tiče nema konflikta, jer je lema o pumpanju dokazana nakon teorema KA=REG (s predavanja).
Nadalje koristim definicije s predavanja.
Kod 2. već imamo konflikt. U predavanjima postoji teorem "KA <=> ima konačan skup reziduala", koji je ako uzmemo definiciju s vježbi točno zadatak 2. (ovdje još ne možemo koristiti KA=REG, jer u tom trenu još nije dokazan). Ako pak želimo "REG <=> ima konačan skup reziduala", tada moramo dokazati jedan smjer direktno, a drugi pomoću "KA=REG" (možemo i oba preko KA=REG i prethodnog teorema). Pitanje je još koliko treba ići u dubinu dokaza, naime, za teorem "KA <=> ima konačan skup reziduala" potrebna je sljedeće lema :
"L=L(M) za neki DKA M i Q skup stanja od M. TAda card(Q)>=card{Res(L)}",
iz koje direktno slijedi zadatak 3. Da li i nju dokazivati?
Kako u tom slučaju rješavati 3?
Trebalo bi malo preciznije specificirati što se hoće.
Naime, na vježbama jezik je REG = "postoji DKA koji ga prepoznaje".
Na predavanjima : REG = "generiran regularnim izrazom",
KA = "postoji DKA koji ga prepoznaje".
Što se zadatka 1. tiče nema konflikta, jer je lema o pumpanju dokazana nakon teorema KA=REG (s predavanja).
Nadalje koristim definicije s predavanja.
Kod 2. već imamo konflikt. U predavanjima postoji teorem "KA <=> ima konačan skup reziduala", koji je ako uzmemo definiciju s vježbi točno zadatak 2. (ovdje još ne možemo koristiti KA=REG, jer u tom trenu još nije dokazan). Ako pak želimo "REG <=> ima konačan skup reziduala", tada moramo dokazati jedan smjer direktno, a drugi pomoću "KA=REG" (možemo i oba preko KA=REG i prethodnog teorema). Pitanje je još koliko treba ići u dubinu dokaza, naime, za teorem "KA <=> ima konačan skup reziduala" potrebna je sljedeće lema :
"L=L(M) za neki DKA M i Q skup stanja od M. TAda card(Q)>=card{Res(L)}",
iz koje direktno slijedi zadatak 3. Da li i nju dokazivati?
Kako u tom slučaju rješavati 3?
|
|
| [Vrh] |
|
Jelaska
Forumaš(ica)
Pridružen/a: 13. 10. 2004. (14:27:46)
Postovi: (50)16
|
| Postano: 16:21 ned, 12. 3. 2006 Naslov: |
|
|
|
[quote="Boris Davidovič"]Trebalo bi malo preciznije specificirati što se hoće.
[/quote]
Ja ne bih tako rekao :shock:
[quote="Boris Davidovič"]
Naime, na vježbama jezik je REG = "postoji DKA koji ga prepoznaje".
Na predavanjima : REG = "generiran regularnim izrazom",
KA = "postoji DKA koji ga prepoznaje".
Što se zadatka 1. tiče nema konflikta, jer je lema o pumpanju dokazana nakon teorema KA=REG (s predavanja).
Nadalje koristim definicije s predavanja.
Kod 2. već imamo konflikt. U predavanjima postoji teorem "KA <=> ima konačan skup reziduala", koji je ako uzmemo definiciju s vježbi točno zadatak 2. ...
[/quote]
Na vježbama se temeljito diskutiralo o ovakvim problemima. Dakle na predavanjima i vježbama iz kolegija "Matematička teorija računarstva" i "Računarstvo" za drugi kolokvij obrađena je teorija i primjena konačnih automata.
Poanta tog dijela gradiva je pokazati da: "problem" koji može biti riješen sa determinističkim konačnim automatom = "problem" koji može biti riješen sa nedeterminističkim konačnim automatom ="problem" koji može biti opisan regularnim izrazom="problem" koji može biti generiran desno linearnom gramatikom. Ono u čemu se razlikuju predavanja i vježbe su polazne točke iz kojih kreće pokazivanje dotičnih ekvivalencija. Npr, ako u teoriju krenemo sa pojmom gramatike pa desno linearne gramatike imati čemo definiciju: "kažemo da je jezik regularan ako postoji desno linearna gramatika koja ga generira", a ako krenemo sa pojmom regularnog izraza imati čemo definiciju: "kažemo da je jezik regularan ako postoji regularan izraz koji ga opisuje". Testirano je, :lol: (od moje malenkosti) ako slučajnim odabirom uzmemo par knjiga koje se bave ovim problemima, skoro sigurno će imati različite definicije regularnosti jezika, samim tim i drugačije početne točke za daljnju analizu. Zaključno: nije bitno kako se što definiralo na predavanjima a kako na vježbama (čak je i prikladno da početne točke budu različite, pogled na neku stvar sa teoretskog aspekta zna biti vrlo drugačiji od pogleda na istu stvar očima prakse) bitno je da na kraju cjelina bude smisleno zaokružena.
Da se vratimo na zadaću... :idea:
Stvar je vrlo jednostavna, smisao zadaće je da student kroz dokaze teorema dobije dublje [b]razumijevanje[/b] praktičnih problema koji su rješavani na vježbama. Koliko duboko "otići", da li koristiti notaciju sa vježbi ili predavanja, ili možda neku "treću", ostavljam pojedincu.
| Boris Davidovič (napisa): | Trebalo bi malo preciznije specificirati što se hoće.
|
Ja ne bih tako rekao 
| Boris Davidovič (napisa): |
Naime, na vježbama jezik je REG = "postoji DKA koji ga prepoznaje".
Na predavanjima : REG = "generiran regularnim izrazom",
KA = "postoji DKA koji ga prepoznaje".
Što se zadatka 1. tiče nema konflikta, jer je lema o pumpanju dokazana nakon teorema KA=REG (s predavanja).
Nadalje koristim definicije s predavanja.
Kod 2. već imamo konflikt. U predavanjima postoji teorem "KA ⇔ ima konačan skup reziduala", koji je ako uzmemo definiciju s vježbi točno zadatak 2. ...
|
Na vježbama se temeljito diskutiralo o ovakvim problemima. Dakle na predavanjima i vježbama iz kolegija "Matematička teorija računarstva" i "Računarstvo" za drugi kolokvij obrađena je teorija i primjena konačnih automata.
Poanta tog dijela gradiva je pokazati da: "problem" koji može biti riješen sa determinističkim konačnim automatom = "problem" koji može biti riješen sa nedeterminističkim konačnim automatom ="problem" koji može biti opisan regularnim izrazom="problem" koji može biti generiran desno linearnom gramatikom. Ono u čemu se razlikuju predavanja i vježbe su polazne točke iz kojih kreće pokazivanje dotičnih ekvivalencija. Npr, ako u teoriju krenemo sa pojmom gramatike pa desno linearne gramatike imati čemo definiciju: "kažemo da je jezik regularan ako postoji desno linearna gramatika koja ga generira", a ako krenemo sa pojmom regularnog izraza imati čemo definiciju: "kažemo da je jezik regularan ako postoji regularan izraz koji ga opisuje". Testirano je,  (od moje malenkosti) ako slučajnim odabirom uzmemo par knjiga koje se bave ovim problemima, skoro sigurno će imati različite definicije regularnosti jezika, samim tim i drugačije početne točke za daljnju analizu. Zaključno: nije bitno kako se što definiralo na predavanjima a kako na vježbama (čak je i prikladno da početne točke budu različite, pogled na neku stvar sa teoretskog aspekta zna biti vrlo drugačiji od pogleda na istu stvar očima prakse) bitno je da na kraju cjelina bude smisleno zaokružena.
Da se vratimo na zadaću... 
Stvar je vrlo jednostavna, smisao zadaće je da student kroz dokaze teorema dobije dublje razumijevanje praktičnih problema koji su rješavani na vježbama. Koliko duboko "otići", da li koristiti notaciju sa vježbi ili predavanja, ili možda neku "treću", ostavljam pojedincu.
_________________
Jelaska Igor
Zadnja promjena: Jelaska; 0:14 uto, 25. 4. 2006; ukupno mijenjano 1 put.
|
|
| [Vrh] |
|
panda_iz_pakla
Gost
|
| Postano: 19:04 ned, 12. 3. 2006 Naslov: odgovor i neke druge opaske |
|
|
|
[quote="Boris Davidovič"]
Kod 2. već imamo konflikt. U predavanjima postoji teorem "KA <=> ima konačan skup reziduala", koji je ako uzmemo definiciju s vježbi točno zadatak 2. (ovdje još ne možemo koristiti KA=REG, jer u tom trenu još nije dokazan). Ako pak želimo "REG <=> ima konačan skup reziduala", tada moramo dokazati jedan smjer direktno, a drugi pomoću "KA=REG" (možemo i oba preko KA=REG i prethodnog teorema). Pitanje je još koliko treba ići u dubinu dokaza, naime, za teorem "KA <=> ima konačan skup reziduala" potrebna je sljedeće lema :
[/quote]
Ja na to gledam ovako: radimo sa pojmvima koji u stvari opisuju
istu stvar. I neki dokazi su lakse provedivi pomocu nekih pojmova a
neki pomocu drugih a ekvivalencije izmedju njih se podrazumjevaju i sve je divno i krasno. Zato mislim se REG=KA podrazumjeva. I dokaz za:
Konacan Skup Reziduala <=> KA
je laksi nego ekvivalent za REG, i zato KA i koristimo. Kazem laksi, ali ipak treba dobrih par strana (meni) pa nebi trebalo bit nikakvih problema ni sto se ulozenog truda tice. Precica je, ali je put svejedno dug :)
[quote="Boris Davidovič"]
"L=L(M) za neki DKA M i Q skup stanja od M. TAda card(Q)>=card{Res(L)}",
iz koje direktno slijedi zadatak 3. Da li i nju dokazivati?
Kako u tom slučaju rješavati 3?[/quote]
Imas pravo, kada se neke tvrdnje jedom raspisu u 2. zadatku ocito
su primjenjive na treci i niko nije lud da ih ide ponovo raspisivat. Medjutim, ova lema ti je samo mali dio treceg, trebas dokazat da je
automat reziduala JEDINSTVEN, tj. da su svi automati sa tim, najmanjim
brojem stanja njemu izomorfni i to je bit zadatka. Minimalnost je trivic.
Samo jedan savjet u vezi reziduala. Formula za reziduale od X* sa
vjezbi i predavanja nije tocna (provjereno) vec je prava formula:
u-1 X* = ( SUMA PO [ u = vw, v iz X* ] OD (w-1 X) ) X* + (e)
e (tj. epsilon) se dodaje samo ako je u = e
da, neda mi se tehat i mislim da sam dokazo tvrdnju
nije bitna za teorijske vec za prakticne.
Sto se tice zadatka konstrukcije automata reziduala za neki izraz/jezik L volim ovaj algoritam: krece se od L (takodjer rezidual). on se stavi na
queue simuliran na papiru.
korak je: popaj rezidual R sa kjua (naravno sve je zapisano pomocu
regularnih izraza), te za svako slovo abecede x
racunaj x-1 R i ako je to razlicito od dosada pronadjenih reziduala
pushaj to na kju
ide automatski, lako se konstruira automat, bla bla...
i algoritam je u biti BFS po automatu reziduala
ako jos neko ima koji savjet za bilo sta, don't hesitate
| Boris Davidovič (napisa): |
Kod 2. već imamo konflikt. U predavanjima postoji teorem "KA ⇔ ima konačan skup reziduala", koji je ako uzmemo definiciju s vježbi točno zadatak 2. (ovdje još ne možemo koristiti KA=REG, jer u tom trenu još nije dokazan). Ako pak želimo "REG ⇔ ima konačan skup reziduala", tada moramo dokazati jedan smjer direktno, a drugi pomoću "KA=REG" (možemo i oba preko KA=REG i prethodnog teorema). Pitanje je još koliko treba ići u dubinu dokaza, naime, za teorem "KA ⇔ ima konačan skup reziduala" potrebna je sljedeće lema :
|
Ja na to gledam ovako: radimo sa pojmvima koji u stvari opisuju
istu stvar. I neki dokazi su lakse provedivi pomocu nekih pojmova a
neki pomocu drugih a ekvivalencije izmedju njih se podrazumjevaju i sve je divno i krasno. Zato mislim se REG=KA podrazumjeva. I dokaz za:
Konacan Skup Reziduala ⇔ KA
je laksi nego ekvivalent za REG, i zato KA i koristimo. Kazem laksi, ali ipak treba dobrih par strana (meni) pa nebi trebalo bit nikakvih problema ni sto se ulozenog truda tice. Precica je, ali je put svejedno dug 
| Boris Davidovič (napisa): |
"L=L(M) za neki DKA M i Q skup stanja od M. TAda card(Q)>=card{Res(L)}",
iz koje direktno slijedi zadatak 3. Da li i nju dokazivati?
Kako u tom slučaju rješavati 3? |
Imas pravo, kada se neke tvrdnje jedom raspisu u 2. zadatku ocito
su primjenjive na treci i niko nije lud da ih ide ponovo raspisivat. Medjutim, ova lema ti je samo mali dio treceg, trebas dokazat da je
automat reziduala JEDINSTVEN, tj. da su svi automati sa tim, najmanjim
brojem stanja njemu izomorfni i to je bit zadatka. Minimalnost je trivic.
Samo jedan savjet u vezi reziduala. Formula za reziduale od X* sa
vjezbi i predavanja nije tocna (provjereno) vec je prava formula:
u-1 X* = ( SUMA PO [ u = vw, v iz X* ] OD (w-1 X) ) X* + (e)
e (tj. epsilon) se dodaje samo ako je u = e
da, neda mi se tehat i mislim da sam dokazo tvrdnju
nije bitna za teorijske vec za prakticne.
Sto se tice zadatka konstrukcije automata reziduala za neki izraz/jezik L volim ovaj algoritam: krece se od L (takodjer rezidual). on se stavi na
queue simuliran na papiru.
korak je: popaj rezidual R sa kjua (naravno sve je zapisano pomocu
regularnih izraza), te za svako slovo abecede x
racunaj x-1 R i ako je to razlicito od dosada pronadjenih reziduala
pushaj to na kju
ide automatski, lako se konstruira automat, bla bla...
i algoritam je u biti BFS po automatu reziduala
ako jos neko ima koji savjet za bilo sta, don't hesitate
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
Jelaska
Forumaš(ica)
Pridružen/a: 13. 10. 2004. (14:27:46)
Postovi: (50)16
|
| Postano: 22:01 ned, 26. 3. 2006 Naslov: Re: što ako ipak ne riješimo |
|
|
|
[quote="Anonymous"]Što ako ne riješimo neki od teorijskih zadataka? Mislim, ne moramo svi znati sve zadatke, a ako ih prepišemo od nekog onda nema smisla.[/quote]
Evo odgovor malo u zakašnjenju :( Da su u zadaći doslovno bili teorijski [b]zadaci[/b], ne bi bilo problema ako neko ne riješi sve zadatke. Teoretski zadatak, bi recimo bio zadatak tipa jedne leme, teorema ili korolara sa naglaskom na tome da se na vježbama ili predavanjima nije radio dotični dokaz. U zadaći su doslovno [b]teoremi[/b] koji su na predavanjima temeljito raspisani, i na vježbama popraćeni nizom primjera. Stoga, ne vidim nikakvu prepreku da studenti 3. ili 4. godine informatičkih smjerova matematičkog odjela PMF-a (ili drugih, koji su kolegij "Matematička teorija računarstva" ili "Računarstvo" upisali kao izborni kolegij) prouče dokaze teorema, eventualno sebi raspišu koju sitnicu te to predaju asistentu 8)
| Anonymous (napisa): | | Što ako ne riješimo neki od teorijskih zadataka? Mislim, ne moramo svi znati sve zadatke, a ako ih prepišemo od nekog onda nema smisla. |
Evo odgovor malo u zakašnjenju  Da su u zadaći doslovno bili teorijski zadaci, ne bi bilo problema ako neko ne riješi sve zadatke. Teoretski zadatak, bi recimo bio zadatak tipa jedne leme, teorema ili korolara sa naglaskom na tome da se na vježbama ili predavanjima nije radio dotični dokaz. U zadaći su doslovno teoremi koji su na predavanjima temeljito raspisani, i na vježbama popraćeni nizom primjera. Stoga, ne vidim nikakvu prepreku da studenti 3. ili 4. godine informatičkih smjerova matematičkog odjela PMF-a (ili drugih, koji su kolegij "Matematička teorija računarstva" ili "Računarstvo" upisali kao izborni kolegij) prouče dokaze teorema, eventualno sebi raspišu koju sitnicu te to predaju asistentu 
_________________
Jelaska Igor
|
|
| [Vrh] |
|
Gost
|
| Postano: 21:13 pon, 27. 3. 2006 Naslov: |
|
|
|
Eh, sad, mozda ja imam krive biljeske, ali na predavanjima NIJE bilo niti jednog od ta tri dokaza. Mislim, za jedan ili dva je bilo nesto tipa grube grube skice, ali "rupe" je trebalo popuniti same, a meni (a, cini se, i drugima) su te "rupe" ipak bile prevelike pa sam (pomalo) improvizirala.
Da, iskazi teorema jesu temeljito raspisani, pa i popraceni primjerima, ali dokazi zato nisu. Otuda i toliko postova na ovu temu.
Eh, sad, mozda ja imam krive biljeske, ali na predavanjima NIJE bilo niti jednog od ta tri dokaza. Mislim, za jedan ili dva je bilo nesto tipa grube grube skice, ali "rupe" je trebalo popuniti same, a meni (a, cini se, i drugima) su te "rupe" ipak bile prevelike pa sam (pomalo) improvizirala.
Da, iskazi teorema jesu temeljito raspisani, pa i popraceni primjerima, ali dokazi zato nisu. Otuda i toliko postova na ovu temu.
|
|
| [Vrh] |
|
|
