Již bylo tento rok

Binární strom
Věta o existenci listů
Věta o trhání listů
BFS
Sklep/střecha
Karkulka

Binomiální strom
Řády, hloubka, stupeň binomiálního, BHMerge BHExtractMin
Binární halda, HeapInsert HeapExtractMin, HeapBuild
Topologické uspořádání
Věta o existenci zdroje
TopSort
Stránka za slovníku, řazení dle abecedy
Propojení uzlů kabely, konektory

QuickSelect
Problém řazení
Dolní složitost vyhledávání, dolní složitost řazení
CountingSort
Minimální kostra, Kruskal
Lemma o řezech unikátních hran
Děti a lyže

Kostra, minimální kostra
Jarník
Lemma o řezech unikátních hran
Délka cesty, vzdálenost
Dijkstra
Union-Find s keříky
Union-Find obměna se zvyšováním cen
Pila a řezání klád

Problém řazení
Dolní složitost vyhledávání
Dolní složitost řazení
CountingSort
Karacuba
BFS
Hledání cesty obsahující co nejméně šipek opačné orientace
Děti a papuče

Binární strom, BST, hloubka, AVL
Hloubka AVL, AVLInsert
Nafukovací pole, NPInsert
Amortizovaná složitost NPInsert
HeapBuild
Problém řazení
Dolní složitost řazení
Ondra S.
Rozdělování pole + součty L/R částí

Pravděpodobnostní prostor, náhodná veličina, střední hodnota
Věta o linearitě střední hodnoty + důkaz
Házení míčků do hrníčků - popsat pravděpodobnostní prostor + střední hodnotu hodů
Graf měst, odstranit co nejmenší počet hran

Posloupnosti délky m,n. Najít počet podposloupností

Binární sčítačka, amortizovaná složitost
QuickSelect náhodný pivot, skoromedián, nejhorší složitost

Levenshteinova vzdálenost - lemma o složitosti, definice, pseudokód
AVLPred
Nejkratší sled na grafu s hranami 3 barev

Truhlář a délka prken (podobné jako pila a řezání klád?)
Počet topologických uspořádání

Červeno/modré hrany, minimum střídání barev, nejlépe jednobarevná cesta
Algoritmus na podposloupnosti, najít nejdelší neklesající podposloupnost

Algoritmus na doplnění krát, plus, mínus, aby byl výsledek největší

MergeSort
Algoritmus na hledání počtu inverzí pomocí MergeSortu

BFS v bludišti, může procházet zdmi, najít nejkratší cestu s nejmenším počtem zdí

Algoritmus na co nejmenší počet doplnění písmen z A-Z do slova, aby vznikl palindrom

Dětské hrací kostky, lze stavět na sebe, najít nejvyšší věž

Nalezení nejkratší cesty, zakázané vrcholy, maximální "k" zakázaných vrcholů

Algoritmus na délku největší orientované cesty, která se v G vyskytuje

Dvě posloupnosti A a B, kolika způsoby lze vybrat podposloupnost A', aby A' = B

Knihovna s nejnižší výškou

Indiana Jones a cesta z bludiště

Rozdělení desítkového čísla na zakódování v abecedě (27 možných znaků)

13.2.21

  • Definice kostra, minimální kostra

  • Algoritmus Jarník, popis, idea zrychlení s použitím nějaké datové struktury

  • Lemma o řezech (unikátních hran)

  • Důkaz lemmatu o řezech

  • Důkaz Jarníka (hint: pomocí lemmatu o řezech)

  • MergeSort, popis a pseudokód (MergeSort i samotný Merge)

  • Důkaz časové a paměťové složitosti, korektnosti

  • Algoritmus na hledání počtu "inverzí". Inverzí označíme pokud pro dva prvky pole platí x_i > x_j a zároveň i < j. Tedy pro pole 1, 4, 2, 3 existují dvě inverze, a to (4, 2) a (4, 3). Diskutujte paměťovou a časovou složitost. (hint: vhodně upravte MergeSort)

  • Amazon a BlackFriday

    • Blíží se Black Friday a vysoká fluktuace zaměstnanců v Amazonu, který potřebuje upravovat počty zaměstnanců podle různých požadavků pro různé dny. Mějme dny označené 1...N. Pro každý den máme zadaný počet potřebných zaměstnanců x_i, kde i je daný den. Pomocí y_i značíme reálný počet zaměstnanců zaměstnaných ten den.
    • Pokud je x_i > y_i, někteří zaměstnanci nemají práci a musíte jim platit náhradu s cenou K.
    • Pokud je x_i < y_i, máte nedostatek zaměstnanců a tedy je potřeba nějakému jinému zaměstnanci platit přesčas, cena L.
    • Pokud je ve dni i počet zaměstnanců vyšší, než ve dni i-1, tedy y_i > x_i-1, je potřeba zaplatit agentuře cenu M za nabrání dalších zaměstnanců.
    • Pokud je ve dni i počet zaměstnanců nižší, než ve dni i-1, tedy y_i < y_i-1, je potřeba zaplatit propuštěným zaměstnancům odstupné, cena N.
    • Najděte pro každý den reálný počet zaměstnanců y_i takový, aby výsledné náklady byly co nejmenší.
    • Dokažte korektnost, časovou a paměťovou složitost
    • Za exponenciální řešení jsou 3b

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25