Nová wiki-skripta na Vyčíslitelnost

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.
Milvus
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 7. 9. 2007 18:07

Nová wiki-skripta na Vyčíslitelnost

Příspěvek od Milvus »

Při učení jsem sepsal cosi jako skripta a umístil na http://wiki.matfyz.cz/wiki/TIN064_wiki-skripta. Ještě tam toho dost chybí, ale snad to i v nynějším stavu může někomu pomoci (obzvlášť tam, kde selhává Strojil), zaznamenal jsem už kladné reakce. Dokonce už tam pár lidí opravuje chybky, tak se můžete taky zapojit...
PS: Díky Trupiku za upozornění, abych o tom dal vědět i zde na fóru - nějak jsem zapomněl.
Uživatelský avatar
Hugo
Donátor
Donátor
Příspěvky: 233
Registrován: 2. 6. 2005 13:31
Typ studia: Informatika Mgr.
Bydliště: treti kontejner zleva
Kontaktovat uživatele:

Re: Nová wiki-skripta na Vyčíslitelnost

Příspěvek od Hugo »

nemam slov, super :P
Uživatelský avatar
Trupik
Matfyz(ák|ačka) level III
Příspěvky: 251
Registrován: 3. 1. 2005 14:45
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Nová wiki-skripta na Vyčíslitelnost

Příspěvek od Trupik »

Pro mě strojil selhává už na první stránce - důkaz kleenovy věty :roll:
Domovská stránka: http://www.jakubmaly.cz/, blog: http://blog.jakubmaly.cz/
Petice proti olympiádě http://olympiada.nazory.cz

Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
Uživatelský avatar
nohis
Matfyz(ák|ačka) level III
Příspěvky: 128
Registrován: 7. 11. 2004 13:39
Typ studia: Informatika Mgr.
Bydliště: Praha - Prosek / Krakovany
Kontaktovat uživatele:

Re: Nová wiki-skripta na Vyčíslitelnost

Příspěvek od nohis »

Trupik píše:Pro mě strojil selhává už na první stránce - důkaz kleenovy věty :roll:
Jsem na tom obdobně :roll:
Tak nějak jsem žil v domnění že negace zachovává rekurzivní spočetnost (bylo to na několika místech v poznankách co jsou na studnici) a hned na začátku důkazu té věty to je vyvraceno...samozřejmě že to já asi blbě chápu...
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
Příspěvky: 445
Registrován: 22. 9. 2004 21:07
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Nová wiki-skripta na Vyčíslitelnost

Příspěvek od twoflower »

nohis píše:
Trupik píše:Pro mě strojil selhává už na první stránce - důkaz kleenovy věty :roll:
Jsem na tom obdobně :roll:
Tak nějak jsem žil v domnění že negace zachovává rekurzivní spočetnost (bylo to na několika místech v poznankách co jsou na studnici)
Kde presne je to v tech poznamkach? Nespletl sis castecnou rekurzivitu a rekurzivitu? V druhem pripade ji negace zachovava, v prvnim pripade ne, cehoz asi nejjednodussim pripadem je prave predikat z Vety 2 ve Strojilovi, na nem to je hned videt.
Uživatelský avatar
nohis
Matfyz(ák|ačka) level III
Příspěvky: 128
Registrován: 7. 11. 2004 13:39
Typ studia: Informatika Mgr.
Bydliště: Praha - Prosek / Krakovany
Kontaktovat uživatele:

Re: Nová wiki-skripta na Vyčíslitelnost

Příspěvek od nohis »

Asi spletl :)
Dikes

Takovejch nedorozumeni s Vycislitelnosti mam nějak moc :lol:
Uživatelský avatar
Lada
Donátor
Donátor
Příspěvky: 165
Registrován: 9. 1. 2005 10:17
Typ studia: Informatika Bc.
Bydliště: Slaný / zácpa na Evropské

Re: Nová wiki-skripta na Vyčíslitelnost

Příspěvek od Lada »

Taky se pripojuju k dekovacce za scripta - i diky nim jsem vycislitelnost nakonec udelal:)
Vrele doporucuju vsem komu neni strojil tak uplne jasny...
Hail to you, champion:o)
Uživatelský avatar
Tajro
Matfyz(ák|ačka) level I
Příspěvky: 28
Registrován: 14. 2. 2006 08:23
Typ studia: Informatika Bc.
Bydliště: Praha, Morava
Kontaktovat uživatele:

Re: Nová wiki-skripta na Vyčíslitelnost

Příspěvek od Tajro »

Za wiki skripta také děkuji. Témata, kterým se věnují, jsou díky nim mnohem jasnější.. Výborně :D Jen pak ještě ten zbytek by měl někdo dodělat - já těžko, jsem s tím v háji. Například výše zmíněný důkaz Kleenovi věty snad nikde není.. Ve Strojilovi je jen začátek nebo co.. a na dostupných poznámkách z přednášek taky není nebo je jen naznačen.. tak nevím.. nebo mi chybí nějaký zásadní zdroj? pls help..
Milvus
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 7. 9. 2007 18:07

Re: Nová wiki-skripta na Vyčíslitelnost

Příspěvek od Milvus »

Tak to mě moc těší, jestli to někomu pomohlo. Nicméně zkoušku z vyčíslitelnosti mám za sebou, jiné před sebou, vyčíslitelnost můj obor rozhodně není,... takže motivace dopsat zbývající kapitoly klesá.
Důkaz Kleeneho věty opravdu nikde moc není. Ve Strojilovi je jen náznak myšlenky (navíc poněkud nekompletní) - asi to bylo myšleno jen jako pro připomenutí. Na přednášce se to vzalo taky hopem a řekl bych, že by se tedy neměl u zkoušky objevit. Důležité je ale pochopit, co to vlastně říká (hlavně jaký význam má predikát Tk) - na to u zkoušky určitě dojít může. Něco je v naskenovaných poznámkách (ve Studnici) od Martina a Lenky. Možná si najdu čas a připíšu na wiki aspoň pár vět, ale neslibuju.
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
Příspěvky: 445
Registrován: 22. 9. 2004 21:07
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Nová wiki-skripta na Vyčíslitelnost

Příspěvek od twoflower »

Milvus píše:řekl bych, že by se tedy neměl u zkoušky objevit
Taky si myslim. Uz nevim kde jsem videl poradny dukaz Kleeneho vety, bez zminky o TS, pouzivajici jen notaci rekurzivnich funkci a je to pomerne osklivy a pripadalo mi, ze ani nijak extra zajimavy :)
Uživatelský avatar
Hugo
Donátor
Donátor
Příspěvky: 233
Registrován: 2. 6. 2005 13:31
Typ studia: Informatika Mgr.
Bydliště: treti kontejner zleva
Kontaktovat uživatele:

Re: Nová wiki-skripta na Vyčíslitelnost

Příspěvek od Hugo »

Kucera nam rikal, ze u zkousky opravdu nebude..
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:

Re: Nová wiki-skripta na Vyčíslitelnost

Příspěvek od pasky »

Jen poznamenam pro ty, kteri se treba na wiki skripta koukli a odsoudili je ;), ze jsem se je dovolil v poslednim tydnu pomerne masivne editovat a doplnovat spoustu veci, ktere tam chybely, prevazne kombinovanim Strojila a zapisku Lenky a Petra Hoska, tak snad jsem to moc nepokazil ;-) - stale toho zbyva dodelat az az, zejmena posledni dve kapitoly jsou stale neuplne a nektere veci stale nejsou dostatecne jasne vysvetlene.

Asi nejkontroverznejsi zmena je moje pomerne zasadni preformulovani Kleenovy vety, doufam, ze v soucasnem zneni je ekvivalentni tomu puvodnimu a vyrazne pochopitelnejsi (promenne se definuji az v tom bode vety, kdy se pouziji). Kdyz nejake dalsi pary oci overi, ze je to spravne, a posoudi, bude to fajn.

Jestli budu jeste neco dalsiho dopisovat asi zalezi hlavne na tom, jak pujde rano zkouska. ;-)
Next lecture on time travel will be held on previous Monday.
Odpovědět

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