Zadání úkolů do předmětu Vyčíslitelnost a složitost
výpočtů
1. Navrhněte TS, který přijímá jazyk L = {ww | w ∈ {a, b, c}* }.
Nápověda: použijte více pásek
2. Vypočítejte asymptotickou složitost:
1. f(x) = log2
(x)
a. O(x)
b. Ω(x)
c. Θ(x)
d. o(x)
2. f(x) = log2
(x)
a. O(log(x))
b. Ω(log(x))
c. Θ(log(x))
d. o(log(x))
3. f(x) = 33x33
a. O(2x)
b. Ω(2x)
c. Θ(2x)
d. o(2x)
4. f(x) = 0,1x3
log(x)
a. O(100x3
)
b. Ω(100x3
)
c. Θ(100x3
)
d. o (100x3
)
5. f(x)= 33x+ 3 log(x)
a. O(log2
(x))
b. Ω(log2
(x))
c. Θ(log2
(x)
d. o(log2
(x))
3. Zjistěte časovou a prostorovou složitost algoritmů a zdůvodněte
a. Insertion sort
b. Shell sort
c. Counting sort
d. Heapsort
e. Comb sort
4. Aplikace dynamického programování. Vyberte si jednu úlohu.
a. Knapsack problem
b. Partition problem