Definujte podgraf a indukovaný podgraf. Definujte izomorfismus grafů a automorfismus grafu.
Definujte stupeň vrcholu, okolí vrcholu a regulární graf. Dále formulujte větu o principu sudosti a její důsledek pro počet vrcholů lichého stupně.
Definujte souvislou komponentu neorientovaného grafu a popište alespoň jeden algoritmus pro hledání souvislých komponent.
Popište algoritmus DFS, diskutujte jeho konečnost a korektnost a uveďte jeho časovou složitost. (tento semestr vyřazena)
Definujte slabou souvislost a silnou souvislost orientovaného grafu.
Definujte acyklický orientovaný graf, zdroj a stok. Dále formulujte větu o existenci zdroje.
Definujte topologické uspořádání orientovaného grafu. Popište algoritmus konstrukce topologického uspořádání orientovaného grafu, diskutujte jeho konečnost a korektnost a uveďte jeho časovou složitost.
Definujte strom, les, list. Formulujte tvrzení o existenci listů.
Formulujte větu o trhání listů. Dále formulujte alespoň jednu vlastnost stromů ekvivalentní s definicí stromu.
Definujte kostru neohodnoceného souvislého grafu a popište alespoň jeden algoritmus její konstrukce a diskutujte jeho konečnost a korektnost a uveďte jeho časovou složitost.
Definujte vzdálenost dvou vrcholů v neohodnoceném grafu. Dále popište algoritmus BFS a diskutujte jeho konečnost a korektnost a uveďte jeho časovou složitost.
Popište algoritmy SelectSort, BubbleSort a InsertSort a jejich časové složitosti. U jednoho z nich diskutujte jeho korektnost a uveďte jeho časovou složitost.
Definujte binární strom. Definujte binární minimovou haldu a popište její reprezentaci pomocí pole.
Popište operace vložení prvku a odebrání minima binární minimové haldy a jejich časové složitosti.
Popište algoritmus vytvoření binární minimové haldy z neuspořádaného pole (HeapBuild) a uveďte jeho časovou složitost.
Popište algoritmus HeapSort, diskutujte jeho konečnost a korektnost a uveďte jeho časovou složitost.
Definujte binomiální strom a binomiální minimovou haldu. Popište operaci sloučení dvou binomiálních hald (BHMerge) a vložení prvku do binomiální haldy a jejich časovou složitost.
Definujte binomiální strom a binomiální minimovou haldu. Popište operaci odebrání minimálního prvku z binomiální minimové haldy (BHExtractMin) a její časovou složitost.
Definujte binární strom. Definujte binární vyhledávací strom a popište v něm operace nalezení prvku, následníka a předchůdce a jejich časové složitosti.
Definujte binární strom. Definujte binární vyhledávací strom a popište v něm operace vložení a odstranění prvku a uveďte jejich časové složitosti.
Definujte binární strom. Definujte AVL strom a formulujte větu o hloubce AVL stromu.
Definujte binární strom a AVL strom. Popište jednoduchou rotaci a dvojitou rotaci binárního vyhledávacího stromu a popište základní myšlenku vyvažování při vkládání prvku do AVL stromu.
Definujte binární strom a AVL strom. Popište jednoduchou rotaci a dvojitou rotaci binárního vyhledávacího stromu a popište základní myšlenku vyvažování při odebírání prvku z AVL stromu.
Definujte hešovací tabulku a popište principy hešování s řetízky.
Definujte hešovací tabulku a popište principy hešování s otevřenou adresací s lineárním přidáváním a s dvojitým hešováním.
Popište algoritmus MergeSort, diskutujte jeho korektnost a uveďte jeho časovou složitost.
Popište algoritmus rychlého násobení čísel, diskutujte jeho korektnost a uveďte jeho časovou složitost.
Popište algoritmus QuickSelect (nalezení k-tého nejmenšího prvku neseřazené posloupnosti), diskutujte jeho korektnost a uveďte jeho časovou složitost.
Popište algoritmus QuickSort, diskutujte jeho korektnost a uveďte jeho časovou složitost.
Definujte porovnávací model RAM. Vysvětlete větu o dolní mezi složitosti problému vyhledávání v porovnávacím modelu.
Definujte porovnávací model RAM. Vysvětlete větu o dolní mezi složitosti problému řazení v porovnávacím modelu.
Popište algoritmus CountingSort, jeho předpoklady, diskutujte jeho konečnost a korektnost a uveďte jeho časovou složitost.
Popište algoritmus LexCountingSort, jeho předpoklady, diskutujte jeho konečnost a korektnost a uveďte jeho časovou složitost.
Popište polynomiální algoritmus na výpočet nejdelší rostoucí podposloupnosti (na jaké podproblémy se rozkládá?). Diskutujte korektnost vašeho algoritmu.
Definujte editační vzdálenost dvou řetězců a popište polynomiální algoritmus na výpočet editační vzdálenosti dvou řetězců (na jaké podproblémy se rozkládá?). Diskutujte korektnost vašeho algoritmu.
Definujte elementární řez grafu a formulujte lemma o řezech ohodnoceného grafu.
Definujte minimální kostru ohodnoceného grafu. Popište Jarníkův algoritmus, diskutujte jeho konečnost a korektnost a uveďte jeho časovou složitost.
Definujte minimální kostru ohodnoceného grafu. Popište Kruskalův algoritmus, diskutujte jeho konečnost a korektnost a uveďte jeho časovou složitost.
Popište základní myšlenku reprezentace struktury Union-Find pomocí keříků a uveďte časovou složitost operací Union a Find.
Popište Dijkstrův algoritmus pro hledání nejkratších cest v ohodnoceném orientovaném grafu, jeho předpoklady, diskutujte jeho korektnost a uveďte jeho časovou složitost.
Popište Bellman-Fordův algoritmus pro hledání nejkratších cest v ohodnoceném orientovaném grafu, jeho předpoklady, diskutujte jeho korektnost a uveďte jeho časovou složitost.
Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25