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

Vše co není uvedeno jinde
Návštěvník

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

Příspěvek od Návštěvník »

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.
Odpovědět

Zpět na „Ostatní“