Vyčíslitelnost a složitost
prof. RNDr. Jan Strejček, Ph.D.
Vyčíslitelnost a složitost
prof. RNDr. Jan Strejček, Ph.D.
Vyčíslitelnost a složitost
Info
Předmět
Období
podzim 2022
Informace o předmětu: sylabus, literatura, výuka, domácí úkoly, hodnocení
Přejít
Kapitola obsahuje:
3
PDF
1
Studijní text
Technické info k domácím úlohám
Přejít
Kapitola obsahuje:
1
Studijní materiály
1
Studijní text
3
Web

1. blok: úvod, while-programy, makropříkazy, Churchova teze
Přejít
Kapitola obsahuje:
2
PDF
4
Video
1
Studijní text
Učitel doporučuje studovat od 14. 9. 2022 do 20. 9. 2022.
2. blok: standardní numerace, problém zastavení, věta o numeraci
Přejít
Kapitola obsahuje:
2
PDF
3
Video
1
Studijní text
Učitel doporučuje studovat od 21. 9. 2022 do 4. 10. 2022.
3. blok: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
Přejít
Kapitola obsahuje:
2
PDF
3
Video
1
Studijní text
Učitel doporučuje studovat od 5. 10. 2022 do 11. 10. 2022.
Domácí úkol 1
Přejít
Kapitola obsahuje:
2
Odevzdávárna
4
PDF
3
Studijní materiály
1
Studijní text
Učitel doporučuje studovat od 6. 10. 2022 do 18. 10. 2022.

4. blok: r.e. množiny a jejich standardní numerace
Přejít
Kapitola obsahuje:
2
PDF
2
Video
1
Studijní text
Učitel doporučuje studovat od 12. 10. 2022 do 18. 10. 2022.
5. blok: uzávěrové vlastnosti rekurzivnı́ch a r.e. množin, věta o projekci, 10. Hilbertův problém*
Přejít
Kapitola obsahuje:
2
PDF
3
Video
1
Studijní text
Učitel doporučuje studovat od 19. 10. 2022 do 25. 10. 2022.
6. blok: Riceovy věty, redukce
Přejít
Kapitola obsahuje:
2
PDF
3
Video
1
Studijní text
Učitel doporučuje studovat od 26. 10. 2022 do 1. 11. 2022.
Domácí úkol 2
Přejít
Kapitola obsahuje:
2
Odevzdávárna
4
PDF
2
Studijní materiály
1
Studijní text
Učitel doporučuje studovat od 28. 10. 2022 do 8. 11. 2022.
7. blok: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
Přejít
Kapitola obsahuje:
2
PDF
3
Video
1
Studijní text
Učitel doporučuje studovat od 2. 11. 2022 do 8. 11. 2022.
8. blok: časová složitost algoritmu, časové složitostnıí třídy
Přejít
Kapitola obsahuje:
2
PDF
2
Video
1
Studijní text
Učitel doporučuje studovat od 9. 11. 2022 do 15. 11. 2022.
9. blok: třída P, algoritmus C-Y-K, třída NP
Přejít
Kapitola obsahuje:
2
PDF
3
Video
1
Studijní text
Učitel doporučuje studovat od 16. 11. 2022 do 22. 11. 2022.
10. blok: polynomiální redukce a NP-úplné problémy
Přejít
Kapitola obsahuje:
2
PDF
5
Video
1
Studijní text
Učitel doporučuje studovat od 23. 11. 2022 do 29. 11. 2022.
Domácí úkol 3
Přejít
Kapitola obsahuje:
2
Odevzdávárna
4
PDF
2
Studijní materiály
1
Studijní text
Učitel doporučuje studovat od 29. 11. 2022 do 9. 12. 2022.
11. blok: prostorová složitost, vztahy složitostních tříd, TQBF
Přejít
Kapitola obsahuje:
2
PDF
3
Video
1
Studijní text
Učitel doporučuje studovat od 30. 11. 2022 do 6. 12. 2022.
Zkoušky
Přejít
Kapitola obsahuje:
2
PDF
1
Studijní text


Předchozí
Následující