Přepis přednášky pro ak. rok 2008/2009

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.
Uživatelský avatar
Petr-H
Matfyz(ák|ačka) level II
Příspěvky: 81
Registrován: 30. 1. 2006 14:18
Typ studia: Informatika Mgr.
Bydliště: VŠK 17. listopadu
Kontaktovat uživatele:

Přepis přednášky pro ak. rok 2008/2009

Příspěvek od Petr-H »

Vystavil jsem na svůj web přepis letošní přednášky. Jedná se o zatím nerevidovanou verzi, pokud narazíte na chyby, ať už gramatické či formální, budu rád pokud mi dáte vědět abych tyto mohl odstranit.
Uživatelský avatar
Void
Matfyz(ák|ačka) level II
Příspěvky: 54
Registrován: 17. 1. 2006 16:21
Typ studia: Informatika Mgr.

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvek od Void »

Díky moc, zrovna na tenhle předmět se to hodí strašně.
Jinak faktycký chyby já asi jen tak neodhalim, ale je tam trochu překlep, protože věta 6.10 = větě 6.15 a věta 6.11 = větě 6.14. Ale to je spíš maličkost.

Edit: Tak přece jenom sem našel i nepříjemnější chybu... Věta o rekurzi 7.1 místo f(x) by určitě mělo být f(a).
Edit2: A věta 7.3 je vůbec podezřelá.
Aurë Entuluva!!
Uživatelský avatar
Petr-H
Matfyz(ák|ačka) level II
Příspěvky: 81
Registrován: 30. 1. 2006 14:18
Typ studia: Informatika Mgr.
Bydliště: VŠK 17. listopadu
Kontaktovat uživatele:

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvek od Petr-H »

Díky za upozornění, opravil jsem a časem vystavím novou verzi. Co se týče chyb, očekávám, že zrovna v tomto přepisu jich bude opravdu hodně, protože tato přednáška je poměrně náročná co se týče vytváření poznámek, ať už rukou nebo elektronicky (jak mi jistě dají za pravdu ti, co se o to někdy pokoušeli :) ). Snad se je ale podaří časem všechny odstranit.
Uživatelský avatar
joshis
Matfyz(ák|ačka) level III
Příspěvky: 127
Registrován: 23. 11. 2006 01:47
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvek od joshis »

Veta 2.9, dukaz druhe casti. Podle me tam dokazujes opacnou implikaci, coz plyne bud z toho, ze Kucera je chaotik (a zde tedy mluvil uz o Postove vete) nebo jsem to totalne nepochopil:

Zneni: Pokud M je rekurzivní mnozina, pak M a M jsou rekurzivne spocetne.
DK s mymi {komentari}: Necht M i M jsou obe rekurzivne spocetne {zaciname od vysledku???}. Necht P1 a P2 jsou dva programy takove, ze [x in M <=> P1(x) & x in M <=> P2(x)]. Spustime oba programy soucasne a cekame, ktery konverguje. {tecka. konec. a co jsem tim dostal?}

Jinak diky za to PDFko, je to asi nejsouvislejsi vec o vycislitelnosti co jsem na netu nasel. Podle me vycislitelnost jako obor vubec neexistuje a Kucera to na nas jen hraje... podle me dokonce i napsal vsechny clanky co existujou na wiki ve vsech jazycich, protoze predstava, ze tohle dela na svete vice nez jeden clovek me trochu desi...
Uživatelský avatar
langosh
Matfyz(ák|ačka) level II
Příspěvky: 96
Registrován: 28. 1. 2006 13:20
Typ studia: Informatika Mgr.
Bydliště: Bohnice
Kontaktovat uživatele:

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvek od langosh »

Ten důkaz ukazuje opačnou implikaci. Jde o to, že když pustím oba najednou, jak M tak doplněk, tak mi jeden z nich konverguje, a podle toho který to je, tak se rozhodnu o M. Na druhý se nemusím ohlížet, ten může totiž klidně divergovat. Celkem je tedy M rekurzivni.
Uživatelský avatar
Petr-H
Matfyz(ák|ačka) level II
Příspěvky: 81
Registrován: 30. 1. 2006 14:18
Typ studia: Informatika Mgr.
Bydliště: VŠK 17. listopadu
Kontaktovat uživatele:

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvek od Petr-H »

Máte pravdu, díky mockrát za upozornění. Těchto a dalších chyb tam byla spousta. Po několika průchodech jsem snad již většinu identifikoval a opravil, některé nelogické konstrukce a chybějící části jsem přepsal příp. doplnil z jiných materiálů a vystavil novou verzi. Nevylučuje to ale, že se nenajdou některé další, takže pokud na nějakou chybu narazíte dejte prosím vědět a já ji opravím.

Kdyby někdo chtěl tyto poznámky nějak výrazněji modifikovat nebo je např. integrovat do nějakého většího celku (napadají mně např. texty pro přípravu ke státní zkoušce), vystavil jsem na svůj web také zdrojový soubor.
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvek od hippies »

Petr-H píše:... texty pro přípravu ke státní zkoušce...
Na to taky urcite dojde;) diky za to
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
qwertie
Matfyz(ák|ačka) level III
Příspěvky: 103
Registrován: 4. 6. 2005 15:49
Typ studia: Informatika Bc.
Bydliště: Vyšehrad

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvek od qwertie »

ahoj, prijde mi ze mas chybnou definici 1-uplnost -sprvne by mela byt ze na takovou mnozinu je libovolna rs mnozina 1-prevoditelna
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: Přepis přednášky pro ak. rok 2008/2009

Příspěvek od pasky »

Diky moc za zapisky, pouzival jsem je jako jeden z hlavnich zdroju pro rozsirovani wikiskript! Sem tam chybicka, ale nic, co by cloveka prilis vykolejilo. :)
Next lecture on time travel will be held on previous Monday.
Odpovědět

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