Mareš 25.5.18

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Trollwerine

Mareš 25.5.18

Příspěvek od Trollwerine »

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

Zpět na „TIN060 Algoritmy a datové struktury I“