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 2024
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 23/9/2024 to 29/9/2024.
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 30/9/2024 to 6/10/2024.
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 7/10/2024 to 13/10/2024.
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 14/10/2024 to 20/10/2024.
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 21/10/2024 to 27/10/2024.
6. blok: Riceovy věty, redukce
Open
Chapter contains:
2
PDF
3
Video
1
Study text
Teacher recommends to study from 28/10/2024 to 10/11/2024.
Domácí úkol 2
Open
Chapter contains:
2
Homework Vault
2
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 11/11/2024 to 17/11/2024.
8. blok: časová složitost algoritmu, časové složitostnıí třídy
Teacher recommends to study from 18/11/2024 to 24/11/2024.
9. blok: třída P, algoritmus C-Y-K, třída NP
Teacher recommends to study from 25/11/2024 to 1/12/2024.
10. blok: polynomiální redukce a NP-úplné problémy
Teacher recommends to study from 2/12/2024 to 8/12/2024.
Domácí úkol 3
11. blok: další NP-úplné problémy, prostorová složitost, vztahy složitostních tříd
Teacher recommends to study from 9/12/2024 to 15/12/2024.
12. blok: sublineární prostorové složitostní třídy*, TQBF
Teacher recommends to study from 16/12/2024 to 22/12/2024.
Zkoušky
Open
Chapter contains:
2
PDF
1
Study text


Previous
Next
Operations
View all