# Skúška - Algoritmizácia - Töpfer - 10.1.2021

<{ForumPost(poster="Anonymous", timestamp=2022-01-10 23:01:56)}>
1. Navrhnite algoritmus, ktorý v postupnosti 1 a 0 nájde dĺžku najdlhšej pod-postupnosti obsahujúcej rovnaký počet 1 a 0 + zdôvodniť správnosť a určiť časovú a priestorovú zložitosť.  
  
2. Python fukncia, ktorá nájde a vypíše cestu medzi 2 zadanými vrcholmi v binárnom strome (každý vrchol má unikátnu hodnotu) + zdôvodniť správnosť a určiť časovú a priestorovú zložitosť.  
  
3.   
A) rozhodnúť o pravdivosti tvrdení o časových zložitostiach.  
- ak f=O(h) a g=Ω(h) potom f=O(g)  
- ak f=O(h) a g=Ω(h) potom f+g = Ω(h)  
- ak f=O(h) a g=Ω(h) potom f*g = Ω(h)  
  
B)   
- je zadaný konkrétny stavový strom hry s hodnotami v listoch, určite minmaxovú hodnotu koreňa  
- určite v akom poradí treba vyhodnocovať vrcholy, aby sme alfa-beta prerezávaním ušetrili vyhodnotenie čo najviac vrcholov (a určiť koľko ich ušetríme)  
- je nejaké poradie prechádzania vrcholov, pri ktorom nič neušetríme? Ak áno popíšte, ak nie odôvodnite.
<{/ForumPost}>