{{Předmět|Vyčíslitelnost I|Antonín Kučera|TIN064}} {{TIN064 Skripta}}
Probraná látka (2007/2008)
Čísla (pokud jsou uvedena) odkazují do (v.x - věta, l.x - lemma), odkazy míří do .
1. 10. 07 - Turingovy stroje - základ, modifikace
8. 10. 07 - Univerzální TS, halting problem, základní definice k PRF, ORF a ČRF
15. 10. 07 - Vztah PRF, ORF a ČRF, množiny, predikáty
22. 10. 07 - Ackermannova funkce, strukturální složitost, univerzální f-ce, ekvivalence TS a ČRF (1. část)
29. 10. 07 - Ekvivalence TS a ČRF (2. část), Univerzální ČRF, Kleenova věta, s-m-n věta, pojem numerace
5. 11. 07 - Rekurzivně spočetné množiny: 1-převeditelnost, m-převeditelnost, <span style="color:gray">v.4</span>
12. 11. 07 - Rekurzivně spočetné množiny: Myhillova věta <span style="color:gray">(v.5)</span>, Rekurzivní spočetnost: <span style="color:gray">v.6, v.7, v.8, v.9, v.10, v.11</span>
19. 11. 07 - Generování rekurzivně spočetných množin: <span style="color:gray">v.13, v.14?, v.15, l.5</span>, Rekurzivní spočetnost v jiných oblastech
26. 11. 07 - Matijasevičova věta <span style="color:gray">(v.20)</span> bez důkazu, : <span style="color:gray">v.21, v.22, v.23, v.24, v.25</span>
3. 12. 07 - : <span style="color:gray">v.26, v.27, v.28, v.29, v.30</span>
10. 12. 07 - Produktivní a kreativní množiny: <span style="color:gray">v.31</span>, Dvojice množin: <span style="color:gray">v.32, v.34</span>
17. 12. 07 - Gödelovy věty
7. 1. 08 - <span style="color:gray">v.33</span>, těžší část důkazu "1-úplná = ef. neoddělitelná dvoj.", Tot, <span style="color:gray">Důsledek 7</span>
20. 2. 09 - (1) Vztah dom(f) a rang(f) pro f ČRF.; (2) Efektivně neoddělitelné dvojice - definice a existence
Zkouška
Kučera na tabuli napsal dvě otázky (od 1.2.2008 zadává 3) společné pro všechny (viz níže). Vše chtěl i s důkazem. Čas nebyl omezený, chodil mezi námi a průběžně nás usměrňoval (tedy upozornil, když někdo dokazoval něco jinýho než měl...). Pokud byl spokojen, napsal rovnou známku. Nebo taky řekl, že vidí, že tomu nerozumím, jestli bych si nepřišel příště.
Od února 2008 se objevují nové otázky, které již nejsou tolik teoretické, ale jsou spíše zaměřené na pochopení probrané látky a vztahů.
Otázky
(Pokud není datum, letos ani loni se to nejspíše nevyskytlo)
Ackermannova funkce
TS <=> ČRF
Univerzální funkce pro třídu PRF (zda existuje a do jaké třídy patří) (2.2.2007), že (29.1.2010)
Věty o generování rekurzivně spočetných a rekurzivních množin (25.1.2008, 3.2.2014)
(18.1.2008, 26.1.2007, 22.1.2010, 5.2.2010, 18.2.2011, 9.1.2013, 13.01.2014)
+ aplikace () (15.2.2007, 2.6.2009, 5.2.2010, 29.9.2011)
který program počítá déle, jestli a nebo f(a) a jak
Důkaz, že (26.1.2007, 1.2.2008, 23.1.2009, 22.1.2010, 26.1.2012, 30.1.2013, 11.2.2013)
Vztah (navíc i důkaz lemmatu o vztahu produktivních množin a převoditelnosti z <math>\overline{K}</math>) (18.1.2008, 19.1.2007, 13.9.2007, 19.1.2010, 9.1.2013, 13.01.2014)
Dokázat, že <math>\overline{K}</math> (doplněk K) je . Tzn. Všechno co převedu na <math>\overline{K}</math> je produktivní a když je C produktivní, tak ji převedu na <math>\overline{K}</math>. Důkaz byl vlastně totožný s předchozím příkladem z tohoto seznamu. (19.1.2007, 25.1.2008)
(všecho o nich - definice, existence, a ještě dokázat, že ef. neoddělitelnost = 1-úplnost) (2.2.2007, 17.6.2008 - vetu ef.neodd=1-uplnost odo mna nevyzadoval)
Konstrukce efektivně neoddělitelné množiny (23.1.2007, 11.1.2008, 12.2.2010, 30.1.2013, 3.2.2014)
(znát definice (ZAS, axiomatizovatelná teorie...) a znění Gödelovy věty) (8.2.2008)
Dokázat, že univerzální ČRF nelze rozšířit na ORF <span style="color:gray">v.2</span> (1.2.2008, 17.6.2008, 30.1.2009, 1.2.2010, 4.2.2013)
Dokázat (8.2.2008, 30.1.2009, 19.2.2009, 29.1.2010, 1.2.2010, 4.2.2013)
B = {x : Wx = <math>\empty</math>} - dokázat, že není rekurzivní ani rekurzivně spočetná (15.2.2008)
B = {x : Wx != <math>\empty</math>} - dokázat, že není rekurzivní (23.1.2009)
(A,B) jsou efektivně neoddělitelné (disjunktní, rekurzivně spočetné) - dokázat, že A je kreativní (15.2.2008)
KxK' = {<x,y> : x patří do K & y patří do K' } Je mnozina RS? Je její doplněk RS? (22.2.2008)
sestrojte n0 : φn0 (w) = n0
TIN064 Vlastnosti mnoziny K - [ Rekurzivni? Rekurzivne spocetna? Produktivni? 1-Uplna? Kreativni? ] (6.3.2009)
Dukaz: Produktivni mnozina ma nekonecnou rekurzivne spocetnou podmnozinu. (6.3.2009)
Vztah dom(φ) a range(α) pro α,φ ČRF. Zde (20.2.2009,19.1.2010)
Efektivně neoddělitelné dvojice (definice, existence). (20.2.2009, 9.6.2009)
Charakterizace rekurzivních a rekurzivně spočetných množin pomocí (oboru hodnot) ČRF (věty o úsekových ČRF) (19.2.2009, 9.6.2009, 29.1.2010, 12.2.2010, 29.9.2011, 11.2.2013)
Dokažte, že obor hodnot ČRF je rekurzivně spočetná množina (také mohl myslet věty o úsekových ČRF) (předtermín 16.1.2009, 2.6.2009)
Dokažte, že A je produktivní právě tehdy když doplněk K jde m-převést na A (předtermín 16.1.2009)
f je prosta CRF => inverzna k f je CRF (1.2.2010)
Dokázat, že je-li p rekurzivní permutace, pak p-1 je též rekurzivní permutace. (26.1.2012)
Materiály
skripta z VUT Brno - dostatečně ukecané, obrázky, příklady. Dobře vysvětlena např. Riceova věta.
toho obsahují daleko víc, než bylo na přednáškách probráno (obsahují i věci z Vyčíslitelnosti II). Na druhou stranu začínají až Kleenovou větou o normální formě bez jakéhokoliv vysvětlování terminologie. Má-li však člověk základy pochopeny odjinud, je to ideální studijní materiál doporučený také přednášejícím.
Pokud vůbec netušíte o co jde, před tím, než se budete učit formalismy si přečtěte Johančiny pohádky o vyčíslitelnosti - LINK NEFUNGUJE, Zalozni link, ziskano v r.2008 pomůže to získat trochu nadhled.
Pokud jsou i pohádky příliš složité, pak zkuste tyto dva dokumenty: Vyčíslitelnost a složitost I a Vyčíslitelnost a složitost II od Mgr. Viktora Pavlisky
Zápisky (Martin Trčka) Jsou to poznámky za dva semestry Vyčíslitelnosti z let 2001/2002. Nutno ovšem dodat, že látka dnešní Vyčíslitelnosti I končí v těchto poznámkách až někdy v březnu. Důkazy jsou poměrně dobře okomentovány a občas jsou zde zapsány i vtipné výroky z přednášek. Vhodná je kombinace s novějšími zápisky od Lenky Novotné(viz níže).
Zápisky (Lenka Novotná), úprava do světlejší tisknutelné podoby 2x2 - lenka.pdf.