[Zk] 5.2.2010

Základní přednáška z teorie algoritmů a efektivní vyčíslitelnosti. Turingovy stroje. Částečně rekurzivní funkce. Rekurzivní a rekurzivně spočetné množiny. Algoritmicky nerozhodnutelné problémy. Věta o rekurzi. Kreativní množiny.
pasky
Matfyz(ák|ačka) level II
Příspěvky: 89
Registrován: 4. 1. 2005 22:57
Typ studia: Informatika Bc.
Kontaktovat uživatele:

[Zk] 5.2.2010

Příspěvek od pasky »

Tentokrat lidi hrstka, zadani snadne, stejne jsem se zamotal a odesel s trojkou. :(

1. Konstrukce simple mnoziny, pokud mozno s dukazem, ze funguje.
2. Veta o rekurzi a Riceova veta - formulovat a dokazat.
[doplnujici otazka] Tem, kterymi si nebyl jisty, uniforme daval navic dokazat, ze K neni rekurzivni.

Myslim, ze z peti lidi jsme to udelali tri. Zkonstruovat simple mnozinu delalo vetsine lidi velky problem, vetsinou ji definovali zpusobem, ktery asi nebyl ani rekurzivne spocetny - pozor, abyste RSM zavadeli pomoci nejake definice, ktera se i da RS-upocitat. Trochu neprijemne je, ze do toho sice vrta pratelsky, ale snad schvalne tak, ze ukazuje spory a potize tech definic aby z toho nebylo videt, jakym smerem vede spravna cesta; ja mel zakladni ideu vseho dobre, ale kdyz jsem ho slysel u jinych, mel jsem z toho takovy pocit.

Co jsem na tu "trojku s odrenyma usima" musel predvest?
* Konstrukci simple mnoziny jsem mel (pry) ideove spravne, ale nedelal jsem to pres extra predikat a selektor a tak jsem se zamotal do omezeni kroku turingace (resp. nejdrive jsem na to zapomnel, tak mi rekl, ze ta moje definice vyhazuje z imunni mnoziny prilis mnoho prvku, tak jsem si uvedomil, ze musim z kazde W_x vyhodit jen jeden, ale pak uz jsem mel malo casu na to, abych vymyslel nejakou formalni cestu, jak to udelat). Z dukazu jsem vetsinu mel, ale consequently mi chybelo dokazane, ze ta doplnkova imunni mnozina je nekonecna.
* Vetu o rekurzi jsem zformuloval, Riceovu vetu jsem zformuloval i dokazal. Ve vete o rekurzi jsem si pamatoval ideu a=s1(z,z), ale pocital jsem s tim, ze "zbytek nejak vymyslim". Nevymyslel jsem, substituoval jsem z=e a s-m-n-oval az do umoru a furt mi tam prebyvala promnenna. Zapomnel jsem, ze psi(f(s1(z,z)),x) musi byt funkce dvou promnennych z,x, ne jen x.
* Nakonec mi dal dokazat, ze K neni rekurzivni, coz jsem hbite provedl a poslal mne domu, sedel jsem tam posledni (na zacatku se u mne dlouho nezastavoval, jinak bych mozna stihl vymyslet i ten turingac).

Nebylo to prave mirne hodnoceni, na druhou stranu zadani bylo hodne snadne, nic z produktivnich mnozin nebo nedejboze neceho za tim. Jen jednoho cloveka, se ptal, jestli chce jeste dokazat dvojnou vetu o rekurzi, nebo uz jit domu.

Hodne zdaru pristim generacim!
Next lecture on time travel will be held on previous Monday.
Odpovědět

Zpět na „TIN064 Vyčíslitelnost I“