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
Course
Term
Autumn 2023
Informace o předmětu: sylabus, literatura, výuka, domácí úkoly, hodnocení
Open
Chapter contains:
3
PDF
1
Study text
Informace k domácím úlohám
Open
Chapter contains:
1
Folder
1
Study Materials
1
Study text
3
Web

1. blok: úvod, while-programy, makropříkazy, Churchova teze
Open
Chapter contains:
2
PDF
4
Video
1
Study text
Teacher recommends to study from 18/9/2023 to 24/9/2023.
2. blok: standardní numerace, problém zastavení, věta o numeraci
Open
Chapter contains:
2
PDF
3
Video
1
Study text
Teacher recommends to study from 25/9/2023 to 1/10/2023.
3. blok: věta o parametrizaci, programovací systémy*, rekurzivní množiny
Open
Chapter contains:
2
PDF
3
Video
1
Study text
Teacher recommends to study from 2/10/2023 to 8/10/2023.
Domácí úkol 1
Open
Chapter contains:
2
Homework Vault
4
PDF
3
Study Materials
1
Study text

4. blok: r.e. množiny a jejich standardní numerace
Open
Chapter contains:
2
PDF
3
Video
1
Study text
Teacher recommends to study from 9/10/2023 to 15/10/2023.
5. blok: uzávěrové vlastnosti rekurzivnı́ch a r.e. množin, věta o projekci, 10. Hilbertův problém*
Open
Chapter contains:
2
PDF
3
Video
1
Study text
Teacher recommends to study from 16/10/2023 to 22/10/2023.
6. blok: Riceovy věty, redukce
Open
Chapter contains:
2
PDF
3
Video
1
Study text
Teacher recommends to study from 23/10/2023 to 29/10/2023.
Domácí úkol 2
Open
Chapter contains:
2
Homework Vault
4
PDF
2
Study Materials
1
Study text
7. blok: opakování, Turingovy stroje a redukce, Postův korespondenční problém
Open
Chapter contains:
2
PDF
3
Video
1
Study text
Teacher recommends to study from 30/10/2023 to 5/11/2023.
8. blok: časová složitost algoritmu, časové složitostnıí třídy
Open
Chapter contains:
2
PDF
2
Video
1
Study text
Teacher recommends to study from 6/11/2023 to 12/11/2023.
9. blok: třída P, algoritmus C-Y-K, třída NP
Open
Chapter contains:
2
PDF
3
Video
1
Study text
Teacher recommends to study from 13/11/2023 to 19/11/2023.
10. blok: polynomiální redukce a NP-úplné problémy
Open
Chapter contains:
2
PDF
4
Video
1
Study text
Teacher recommends to study from 20/11/2023 to 26/11/2023.
Domácí úkol 3
Open
Chapter contains:
2
Homework Vault
4
PDF
2
Study Materials
1
Study text
11. blok: další NP-úplné problémy, prostorová složitost, vztahy složitostních tříd
Open
Chapter contains:
2
PDF
3
Video
1
Study text
Teacher recommends to study from 27/11/2023 to 3/12/2023.
12. blok: sublineární prostorové složitostní třídy*, TQBF
Open
Chapter contains:
2
PDF
1
Video
1
Study text
Teacher recommends to study from 4/12/2023 to 10/12/2023.
Zkoušky
Open
Chapter contains:
2
PDF
1
Study text


Previous
Next