Programovani 2 Matematici, teoreticke cviceni
12.03.2024 st
13.03.2024 ct

3. Heap
- Binární strom, hloubka vrcholu a stromu, vyvážený strom a degenerace stromu 
(Binary) Heap definice (min vs max): strom s podminkou a) na tvar a b) na usporadani;
uvahy o vyváženosti
- proc heap? k cemu? 
- Operace: insert, exract extrem 
- visualgo: https://visualgo.net/en/bst

3.6
Hodnotu po hodnotě vložte do prázdné binární min haldy prvky: 30,32,20,11,7,3,8,6
a následně 3krát odeberte minimum
- jakou cas slozitost maji operace insert a extractMin?
 
3.7
Hodnotu po hodnotě vložte do prázdné binární max haldy prvky: 6,8,3,7,11,20,32,30 
a následně 3krát odeberte maximum

3.10
Reprezentace haldy jako pole
3.10.1 Transformujte predchozi haldy ze stromove reprentave do reprezentace v poli 
3.10.3 Provedte priklad 3.6 primo v poli 

3.12
Postaveni Haldy v lineárním čase


4. Jak by mohla vypadat operace find/search v haldě? 
5. Navrhnete metodu, jak vyuzit haldy k hledání i-tého nejmenšího prvku v nestrizenem poli 

7. Abstraktni datove typy

9. Stack - Zásobník - LIFO

11. Fronta - FIFO

13. Mejme prazdny zasobnik "s" a prazdnou frontu "q", provedte krok po kroku nasledujici posloupnost operaci na s a q: 
1. q.push(3)
2. s.push(5)
3. s.push(1)
4. q.push(30)
5. s.push(21)
6. q.push(8)
7. s.push(13)

8. q.pop()
9. q.pop()
10. q.push(17)
11. q.push(20)
12. s.pop()
13  s.push(11)
14. s.pop()

15. s.push(q.pop())
16. q.push(s.pop())
17. s.push(q.pop())
18. q.push(s.pop())
19. q.push(q.pop())






1. Korektní uzávorkování 
Navrhněte algoritmus kontrolující korektní uzávorkování jedním typem závorek
a) rek, 
b) +-1, 
c) stack

1.3 Navrhněte algoritmus kontrolující korektní uzávorkování dvěma typy závorek
1.4 Jak se smění algoritmi máme-li obecně více typů závorek?
1.5 Jake je casova slozitost zminenich algos na kontrolu korektniho uzavorkovani