Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
mdoko Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12) Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
Postano: 16:32 uto, 17. 3. 2009 Naslov: Izračunljivost - druga studentska zadaća |
|
|
Zadaci su u donjoj listi. Ako ponestane zadataka, javite se (mailom ili postajte ovdje), pa cu smisliti jos zadataka.
[list]
1. Definirajte regularne jezike. Kako se dokazuje ekvivalencija končnih automata i regularnih izraza. Pronađite primjer izračunljivog jezika koji nije regularan. Kako se (njačešće) dokazuje neregularnost nekog jezika? [b][Goran Repinc][/b]
2. Definirajte konačne automate i nedeterminističke konačne automate. Dokažite ekvivalenciju konačnih automata i nedeterminističkih konačnih automata. [b][Ksenija Hodak][/b]
3. Definirajte kontekstno slobodne jezike. Pronađite primjer izračunljivog jezika koji nije kontekstno slobodan. Kako se (najčešće) dokazuje neregularnost nekog jezika?[b] [Zoran Gaćeša][/b]
4. Definirajte kontekstno slobodne gramatike i Chomskyjevu normalnu formu. Dokažite da se svaka kontekstno slobodna gramatika može prikazati u Chomskyjevoj normalnoj formi. [b][Ilija Pavlic][/b]
5. Definirajte višetračni Turingov stroj. Kako se dokazuje ekvivalencija višetračnog Turingovog stroja i "običng" Turingovog stroja?[b] [Antonija Malenica][/b]
6. Definirajte nedeterministički Turingov stroj. Kako se dokazuje ekvivalencija nedeterminističkog Turingovog stroja i "običng" Turingovog stroja?[b] [Jurica Levatić]
[/b]
7. Definirajte pojmove izračunljivih i definabilnih realnih brojeva. Koja je veza među tim dvama klasama brojeva?[b] [Marija Bajić][/b]
8. Dokažite da je RAM-stroj s tri instrukcije (INC, DEC, GOTO) ekvivalentan RAM-stroju s dvije instrukcije (INC, DEK).[b] [Jelena Kovačić][/b]
9. Postov stroj je sličan Turingovom, s jednom razlikom, a to je da Postov stroj ne može u jednom koraku pisati po traci i pomicati se, nego samo jedno od to dvoje. Dajte formalnu definiciju Postovog stroja i dokažite ekvivalenciju Postovih i Turingovih strojeva (ili barem opišite ideju dokaza). [b][Jurica Bradarić][/b]
10. Dajte intuitivni opis i formalnu definiciju Turingovog stoja koji ima dvodimenzionalnu "traku" (nešto kao beskonačna šahovska ploča). Dajte ideju dokaza ekvivalencije s (običnim) Turingovim strojem. [b][Goran Ljubej][/b]
11. Dajte intuitivni opis i formalnu definiciju "višeglavog" Turingovog stoja (više glava koje čitaju i pišu po jednoj traci). Dajte ideju dokaza ekvivalencije s (običnim) Turingovim strojem. [b][Danijel Mandić][/b]
12. Da li za svaku RAM-izračunljivu funkciju [latex]f\colon S\subseteq\mathbb{N}\to\mathbb{N}[/latex] postoji RAM-program koji ne koristi niti jedan registar s indeksom većim od [latex]k[/latex]?
13. Dajte formalnu definiciju Turing-izračunljive funkcije. Dokažite da su po toj definiciji zbrajanje i množenje Turing-izračunljive funkcije. [b][Andreja Jerešić][/b]
[/list:u]
U uglatim zagradama su imena studenata koji su već na vježbama u ponedjeljak rezervirali svoje zadatke.
Rezervacija 9. zadatka, kao i dodatnih zadataka (ako ih bude) ide po principu "tko se prvi javi" tj. tko prvi posta na ovom topicu rezervaciju zadatka.
Za većinu zadataka odgovore i upute možete pronaći u knjizi Michaela Sipsera [i]Introduction to the Theory of Computation[/i] (knjiga postoji u našoj knjižnici), također, nije na odmet prokopati po Internetu za dodatnim izvorom informacija :)
EDIT: dodan 10. i 11. zadatak
Zadaci su u donjoj listi. Ako ponestane zadataka, javite se (mailom ili postajte ovdje), pa cu smisliti jos zadataka.
1. Definirajte regularne jezike. Kako se dokazuje ekvivalencija končnih automata i regularnih izraza. Pronađite primjer izračunljivog jezika koji nije regularan. Kako se (njačešće) dokazuje neregularnost nekog jezika? [Goran Repinc]
2. Definirajte konačne automate i nedeterminističke konačne automate. Dokažite ekvivalenciju konačnih automata i nedeterminističkih konačnih automata. [Ksenija Hodak]
3. Definirajte kontekstno slobodne jezike. Pronađite primjer izračunljivog jezika koji nije kontekstno slobodan. Kako se (najčešće) dokazuje neregularnost nekog jezika? [Zoran Gaćeša]
4. Definirajte kontekstno slobodne gramatike i Chomskyjevu normalnu formu. Dokažite da se svaka kontekstno slobodna gramatika može prikazati u Chomskyjevoj normalnoj formi. [Ilija Pavlic]
5. Definirajte višetračni Turingov stroj. Kako se dokazuje ekvivalencija višetračnog Turingovog stroja i "običng" Turingovog stroja? [Antonija Malenica]
6. Definirajte nedeterministički Turingov stroj. Kako se dokazuje ekvivalencija nedeterminističkog Turingovog stroja i "običng" Turingovog stroja? [Jurica Levatić]
7. Definirajte pojmove izračunljivih i definabilnih realnih brojeva. Koja je veza među tim dvama klasama brojeva? [Marija Bajić]
8. Dokažite da je RAM-stroj s tri instrukcije (INC, DEC, GOTO) ekvivalentan RAM-stroju s dvije instrukcije (INC, DEK). [Jelena Kovačić]
9. Postov stroj je sličan Turingovom, s jednom razlikom, a to je da Postov stroj ne može u jednom koraku pisati po traci i pomicati se, nego samo jedno od to dvoje. Dajte formalnu definiciju Postovog stroja i dokažite ekvivalenciju Postovih i Turingovih strojeva (ili barem opišite ideju dokaza). [Jurica Bradarić]
10. Dajte intuitivni opis i formalnu definiciju Turingovog stoja koji ima dvodimenzionalnu "traku" (nešto kao beskonačna šahovska ploča). Dajte ideju dokaza ekvivalencije s (običnim) Turingovim strojem. [Goran Ljubej]
11. Dajte intuitivni opis i formalnu definiciju "višeglavog" Turingovog stoja (više glava koje čitaju i pišu po jednoj traci). Dajte ideju dokaza ekvivalencije s (običnim) Turingovim strojem. [Danijel Mandić]
12. Da li za svaku RAM-izračunljivu funkciju postoji RAM-program koji ne koristi niti jedan registar s indeksom većim od ?
13. Dajte formalnu definiciju Turing-izračunljive funkcije. Dokažite da su po toj definiciji zbrajanje i množenje Turing-izračunljive funkcije. [Andreja Jerešić]
U uglatim zagradama su imena studenata koji su već na vježbama u ponedjeljak rezervirali svoje zadatke.
Rezervacija 9. zadatka, kao i dodatnih zadataka (ako ih bude) ide po principu "tko se prvi javi" tj. tko prvi posta na ovom topicu rezervaciju zadatka.
Za većinu zadataka odgovore i upute možete pronaći u knjizi Michaela Sipsera Introduction to the Theory of Computation (knjiga postoji u našoj knjižnici), također, nije na odmet prokopati po Internetu za dodatnim izvorom informacija
EDIT: dodan 10. i 11. zadatak
_________________ Extraordinary claims require extraordinary evidence. – Carl Sagan
Zadnja promjena: mdoko; 22:37 sri, 18. 3. 2009; ukupno mijenjano 8 put/a.
|
|
[Vrh] |
|
m00nblade Forumaš(ica)
Pridružen/a: 30. 10. 2005. (13:26:10) Postovi: (54)16
Spol:
|
|
[Vrh] |
|
Gogs Forumaš(ica)
Pridružen/a: 17. 10. 2002. (22:28:12) Postovi: (155)16
Lokacija: Zagreb
|
|
[Vrh] |
|
DanijelM Forumaš(ica)
Pridružen/a: 20. 02. 2008. (11:56:05) Postovi: (29)16
|
|
[Vrh] |
|
iuppiter Forumaš(ica)
Pridružen/a: 03. 01. 2006. (12:15:51) Postovi: (6A)16
Spol:
Lokacija: Nigdjezemska
|
|
[Vrh] |
|
mdoko Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12) Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
[Vrh] |
|
iuppiter Forumaš(ica)
Pridružen/a: 03. 01. 2006. (12:15:51) Postovi: (6A)16
Spol:
Lokacija: Nigdjezemska
|
|
[Vrh] |
|
Gost
|
|
[Vrh] |
|
pero Forumaš(ica)
Pridružen/a: 02. 02. 2005. (17:13:37) Postovi: (81)16
Spol:
|
|
[Vrh] |
|
mdoko Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12) Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
[Vrh] |
|
Gost
|
|
[Vrh] |
|
|