{{Předmět|Vyčíslitelnost I|Antonín Kučera|TIN064}}
== Probraná látka (2007/2008) ==
Čísla (pokud jsou uvedena) odkazují do [[TIN064 Skripta Ladislava Strojila|skript od Ladislava Strojila]] (v.x - věta, l.x - lemma).
* 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, [[TIN064 Imunní a simple množiny|Simple množiny]] 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, [[TIN064 Věty o rekurzi|Věty o rekurzi]]: <span style="color:gray">v.21, v.22, v.23, v.24, v.25</span>
* 3. 12. 07 - [[TIN064 Produktivní a kreativní množiny|Produktivní a kreativní množiny]]: <span style="color:gray">v.26, v.27, v.28, v.29, v.30</span>
* 10. 12. 07 - Produktivní a kreativní množiny: [[TIN064 Produktivní a kreativní množiny#Úplně produktivní množiny|úplná produktivita]] <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>
== 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ě.
=== 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)
* [[TIN064 Lemma o selektoru|Lemma o selektoru]] (11.1.2008, 19.1.2007, 15.2.2007, 13.9.2007)
* Věty o generování rekurzivně spočetných a rekurzivních množin (25.1.2008)
* [[TIN064 Imunní a simple množiny|Konstrukce prosté (simple) množiny]] (18.1.2008, 26.1.2007)
* [[TIN064 Věty o rekurzi|Věty o rekurzi]] + aplikace ([[TIN064 Věty o rekurzi#Riceova věta|Rice]]) (15.2.2007)
** který program počítá déle, jestli ''a'' nebo ''f(a)'' a jak
* [[TIN064 Imunní a simple množiny|Imunní]], [[TIN064 Produktivní a kreativní množiny|produktivní a kreativní mn.]]
* Důkaz, že [[TIN064 Produktivní a kreativní množiny#Věta o produktivní ORF|existuje obecně rekurzivní produktivní funkce]] (26.1.2007, 1.2.2008)
* Vztah [[TIN064 Produktivní a kreativní množiny#Jiná věta o ekvivalenci pojmů|kreativnosti a 1-úplnosti]] (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)
* Dokázat, že <math>\overline{K}</math> (doplněk K) je [[TIN064 Produktivní a kreativní množiny#Věta o ekvivalenci pojmů|nejjednodušší produktivní množina]]. 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)
* Efektivně neoddělitelné množiny (všecho o nich - definice, existence, a ještě dokázat, že ef. neoddělitelnost = 1-úplnost) (2.2.2007)
* Konstrukce efektivně neoddělitelné množiny (11.1.2008, 23.1.2007)
* Gödelovy věty (znát definice (ZAS, axiomatizovatelná teorie...) a znění Gödelovy věty) (8.2.2008)
* Dokázat, že množina [[TIN064 Produktivní a kreativní množiny#Tot je produktivní|Tot je produktivní]] (1.2.2008)
* Dokázat, že univerzalni ČRF nelze rozšířit na ORF (1.2.2008)
* Dokázat [[TIN064 Produktivní a kreativní množiny#Úplně produktivní množiny|úplně produktivní = produktivní]] (8.2.2008)
* Riceove věta + důkaz (15.2.2008)
* NOVINKA - B = {x : W<sub>x</sub> = <math>\empty</math>} - dokázat, že není rekurzivní ani rekurzivně spočetná (15.2.2008)
* NOVINKA - (A,B) jsou efektivně neoddělitelné (disjunktní, rekurzivně spočetné) - dokázat, že A je kreativní (15.2.2008)
== Materiály ==
* [[TIN064 wiki-skripta|Wiki skripta]] - <span style="background:#f66;">'''NOVĚ od února 2008!!!'''</span>, zatím rozpracované.
* [[TIN064 Skripta Ladislava Strojila|Skripta Ladislava Strojila]] 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 [http://atrey.karlin.mff.cuni.cz/~johanka/vyuka/pohadky_vycislitelnost.html Johančiny pohádky o vyčíslitelnosti], pomůže to získat trochu nadhled.
* Pokud jsou i pohádky příliš složité, pak zkuste tyto dva dokumenty: [http://www1.osu.cz/home/habibal/kurzy/vysl1.pdf Vyčíslitelnost a složitost I] a [http://www1.osu.cz/home/habibal/kurzy/vysl2.pdf Vyčíslitelnost a složitost II] od Mgr. Viktora Pavlisky
* [http://lucy.troja.mff.cuni.cz/labtf/poznamky/vycislitelnost.zip 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).
* [http://mff.modry.cz/vycislitelnost/zapisky/Lenka/ Zápisky (Lenka Novotná)], úprava do světlejší tisknutelné podoby 2x2 - [http://beta.arcig.cz/~bernard/lenka.pdf lenka.pdf].
* [http://www.ms.mff.cuni.cz/~zajio1am/notes/vycislitelnost_1-tin064-kucera-mixed.tar Zápisky (Eva Ondráčková, Lenka Novotná)].
* [http://urtax.ms.mff.cuni.cz/~novap2am/poznamky/vycislitelnost.sxw Poznámky z přednášky].
