od Trollwerine » 26. 5. 2018 17:06
Zkouška u Mareše.
1) násobení n-ciferných čísel rychleji než n^2
2) minimální kostra + důkaz správnosti
3) vymyslet algoritmus na mazání vrcholů v grafu, který zachovává souvislost (když algoritmu dáme souvislý graf a budeme mazat podle toho, co nám řekne, tak v každém kroku bude graf souvislý)
4) okénkový medián k prvků v nekonečné posloupnosti
1) a 2) jsou z přednášky, jenom pokud používáte kuchařku, tak ji vysvětlit
3) udělat z grafu kostru a mazat list po listu
4) držet si AVL strom s hodnotami, u každého vrcholu si pamatovat velikosti stromů na synech, pak jde přidávání, odebírání a hledání k/2-tého v O(log(k))
Zkouška byla fajn, když viděl správný nápad, tak se v tom nešťoural, jenom chtěl mít dobře důkaz správnosti a pořádně vysvětlené kroky (žádné "černá magie mi najde X")
Zkouška u Mareše.
1) násobení n-ciferných čísel rychleji než n^2
2) minimální kostra + důkaz správnosti
3) vymyslet algoritmus na mazání vrcholů v grafu, který zachovává souvislost (když algoritmu dáme souvislý graf a budeme mazat podle toho, co nám řekne, tak v každém kroku bude graf souvislý)
4) okénkový medián k prvků v nekonečné posloupnosti
1) a 2) jsou z přednášky, jenom pokud používáte kuchařku, tak ji vysvětlit
3) udělat z grafu kostru a mazat list po listu
4) držet si AVL strom s hodnotami, u každého vrcholu si pamatovat velikosti stromů na synech, pak jde přidávání, odebírání a hledání k/2-tého v O(log(k))
Zkouška byla fajn, když viděl správný nápad, tak se v tom nešťoural, jenom chtěl mít dobře důkaz správnosti a pořádně vysvětlené kroky (žádné "černá magie mi najde X")