• Pojem složitosti algoritmů
• Složitost jako funkce délky vstupu
• Prakticky řešitelné problémy, třída P

Cvičení

• časová složitost algoritmů a problémů
• určování složitosti jednoduchých algoritmů
• problém splnitelnosti jako příklad těžkého rozhodnutelného problému

Literatura:
J. Hromkovič kapitola 5