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 2021
Informace o předmětu: sylabus, literatura, výuka, domácí úkoly, hodnocení
Open
Chapter contains:
3
PDF
1
Study text
Technické info k domácím úlohám
Open
Chapter contains:
1
Study Materials
1
Study text
3
Web
Teacher recommends to study from 8/10/2021 to 9/12/2021.

1. blok: úvod, while-programy, makropříkazy, Churchova teze
Open
Chapter contains:
2
PDF
5
Video
1
Study text
Teacher recommends to study from 13/9/2021 to 26/9/2021.
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 20/9/2021 to 3/10/2021.
3. blok: věta o parametrizaci, programovací systémy*
Open
Chapter contains:
2
PDF
2
Video
1
Study text
Teacher recommends to study from 27/9/2021 to 10/10/2021.
Domácí úkol 1
Open
Chapter contains:
2
Homework Vault
4
PDF
3
Study Materials
1
Study text
Teacher recommends to study from 4/10/2021 to 12/10/2021.

4. blok: rekurzivní a r.e. množiny, standardní numerace r.e. množin
Open
Chapter contains:
2
PDF
3
Video
1
Study text
Teacher recommends to study from 4/10/2021 to 17/10/2021.
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 11/10/2021 to 24/10/2021.
6. blok: Riceovy věty
Open
Chapter contains:
2
PDF
2
Video
1
Study text
Teacher recommends to study from 18/10/2021 to 31/10/2021.
Domácí úkol 2
Open
Chapter contains:
2
Homework Vault
4
PDF
2
Study Materials
1
Study text
Teacher recommends to study from 23/10/2021 to 11/11/2021.
7. blok: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém*
Open
Chapter contains:
3
PDF
5
Video
1
Study text
Teacher recommends to study from 25/10/2021 to 7/11/2021.
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 1/11/2021 to 14/11/2021.
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 8/11/2021 to 21/11/2021.
10. blok, část A: polynomiální redukce, SAT
Open
Chapter contains:
2
PDF
2
Video
1
Study text
Teacher recommends to study from 15/11/2021 to 28/11/2021.
10. blok, část B: 3SAT, CLIQUE, VERTEX-COVER
Open
Chapter contains:
2
PDF
3
Video
1
Study text
Teacher recommends to study from 22/11/2021 to 5/12/2021.
Domácí úkol 3
Open
Chapter contains:
2
Homework Vault
6
PDF
2
Study Materials
1
Study text
Teacher recommends to study from 27/11/2021 to 7/12/2021.
11. blok: prostorová složitost, vztahy složitostních tříd, TQBF
Open
Chapter contains:
2
PDF
3
Video
1
Study text
Teacher recommends to study from 29/11/2021 to 12/12/2021.
Zkoušky
Open
Chapter contains:
2
PDF
1
Study text


Previous
Next