Základy informatiky
Týden 9
- Pojem složitosti algoritmů
- Složitost jako funkce délky vstupu
- Asymptotická notace
Literatura: kapitoly 8.1 a 8.2.
Cvičení:
- rozhodnutelné a nerozhodnutelné problémy
- důkaz nerozhodnutelnosti problému zastavení
- ukázka důkazu nerozhodnutelnosti pomocí redukce