Vyčíslitelnost I: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(Zkouška)
(Materiály: ** Některé věci ze skript přepsány ke státnicovému shrnutí Vyčíslitelnost)
Řádka 53: Řádka 53:
 
* [[TIN064 wiki-skripta|Wiki skripta]] - <span style="background:#f66;">'''NOVĚ od února 2008!!!'''</span>, zatím rozpracované.  
 
* [[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.
 
* [[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.
 +
** Některé věci ze skript přepsány ke státnicovému shrnutí [[Vyčíslitelnost]]
 
* 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 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
 
* 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

Verze z 29. 5. 2008, 02:17

Vyčíslitelnost I
Kód předmětu: NTIN064
Přednáší: Antonín Kučera

Probraná látka (2007/2008)

Čísla (pokud jsou uvedena) odkazují do 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, v.4
  • 12. 11. 07 - Rekurzivně spočetné množiny: Myhillova věta (v.5), Rekurzivní spočetnost: v.6, v.7, v.8, v.9, v.10, v.11
  • 19. 11. 07 - Generování rekurzivně spočetných množin: v.13, v.14?, v.15, Simple množiny l.5, Rekurzivní spočetnost v jiných oblastech
  • 26. 11. 07 - Matijasevičova věta (v.20) bez důkazu, Věty o rekurzi: v.21, v.22, v.23, v.24, v.25
  • 3. 12. 07 - Produktivní a kreativní množiny: v.26, v.27, v.28, v.29, v.30
  • 10. 12. 07 - Produktivní a kreativní množiny: úplná produktivita v.31, Dvojice množin: v.32, v.34
  • 17. 12. 07 - Gödelovy věty
  • 7. 1. 08 - v.33, těžší část důkazu "1-úplná = ef. neoddělitelná dvoj.", Tot, Důsledek 7

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)
  • 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)
  • Konstrukce prosté (simple) množiny (18.1.2008, 26.1.2007)
  • Věty o rekurzi + aplikace (Rice) (15.2.2007)
    • který program počítá déle, jestli a nebo f(a) a jak
  • Imunní, produktivní a kreativní mn.
  • Důkaz, že existuje obecně rekurzivní produktivní funkce (26.1.2007, 1.2.2008)
  • Vztah kreativnosti a 1-úplnosti (navíc i důkaz lemmatu o vztahu produktivních množin a převoditelnosti z $ \overline{K} $) (18.1.2008, 19.1.2007, 13.9.2007)
  • Dokázat, že $ \overline{K} $ (doplněk K) je nejjednodušší produktivní množina. Tzn. Všechno co převedu na $ \overline{K} $ je produktivní a když je C produktivní, tak ji převedu na $ \overline{K} $. 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 Tot je produktivní (1.2.2008)
  • Dokázat, že univerzalni ČRF nelze rozšířit na ORF (1.2.2008)
  • Dokázat úplně produktivní = produktivní (8.2.2008)
  • Riceove věta + důkaz (15.2.2008)
  • B = {x : Wx = $ \empty $} - dokázat, že není rekurzivní ani rekurzivně spočetná (15.2.2008)
  • (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

Materiály