Mareš 7. 6. 2018

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

Mareš 7. 6. 2018

Příspěvek od Sedmikráska »

1. Algoritmus pro hledání silně souvislých komponent + složitosti + důkaz správnosti
2. Součin čísel v lepším čase než O(n^2)
3. V grafu, jehož hrany jsou ohodnoceny pravděpodobnostmi projití, najděte nejpravděpodobnější cestu, že se dostanete do cíle + složitosti
4. V lexikografickém uspořádání prvků 1 až n najděte k-tou permutaci (nejlépe v lepším než kvadratickém čase)

1. a 2. bylo řečeno na přednášce
3. Dijsktra, ve kterém se místo vah hran počítá s -log(pravděpodobnost projití hrany)
4. Číslo k převedeme do jeho faktoriálové reprezentace a z této reprezentace postupně od začátku vybíráme číslice, které reprezentují, kolikátý prvek z počáteční permutace 1 až n máme vzít - dá se zrychlit pomocí toho, že se ukládají prvky do stromu
Odpovědět

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