Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
1. a) Čo je to algoritmus rozdeľuj a panuj? Vysvetlite všeobecný prístup algoritmov rozdeľuj a panuj. (6 bodov)
(b) Použite prístup rozdeľuj a panuj na navrhnutie algoritmu na nájdenie minimálneho prvku v poli n prvkov. Analyzujte časovú zložitosť svojho algoritmu. (10 bodov)
2. a) Vysvetlite pojem hashovanie a techniky riešenia kolízií. (6 bodov)
(b) Uvažujme hašovaciu tabuľku veľkosti m a množinu n prvkov, ktoré sa majú hašovať. Predpokladajme, že prvky sú rovnomerne rozdelené medzi m slotov. Aká je pravdepodobnosť zrážky, keď n =m/2? Analyzujte priemerný počet porovnaní potrebných na úspešné vloženie všetkých prvkov do hašovacej tabuľky pomocou lineárneho snímania. (10 bodov)
3. (a) Opíšte koncept dynamického programovania a vysvetlite, ako sa líši od prístupu rozdeľuj a panuj. (6 bodov)
(b) Použite dynamické programovanie na vyriešenie problému rezania tyče, kde tyč dĺžky n možno rozrezať na menšie tyče a každá tyč dĺžky i má cenu p[i]. Cieľom je nájsť maximálny výnos, ktorý možno získať rozrezaním tyče na menšie kúsky. Analyzujte časovú a priestorovú zložitosť svojho algoritmu. (10 bodov)
4. (a) Vysvetlite pojem NP-úplnosti a jeho význam pri analýze algoritmov. (6 bodov)
(b) Dokážte, že nasledujúci problém je NP-úplný:Vzhľadom na súbor n položiek s ich príslušnými váhami a hodnotami určite, či existuje podmnožina týchto položiek, ktorých celková hmotnosť je menšia alebo rovná danému limitu a ktorých celková hmotnosť hodnota je maximalizovaná. (10 bodov)
5. (a) Vysvetlite pojem amortizovaná analýza algoritmov. Prečo sa používa a aké sú jeho výhody? (6 bodov)
(b) Vykonajte amortizovanú analýzu dátovej štruktúry zásobníka, kde sú jedinými povolenými operáciami push a pop. Určite priemernú časovú zložitosť každej operácie. (10 bodov)
6. (a) Opíšte Kruskalov algoritmus na nájdenie minimálnej kostry váženého neorientovaného grafu. (6 bodov)
(b) Použite Kruskalov algoritmus na nasledujúci graf a nájdite minimálnu kostru:
```
(1)---2---(3)
/ |
/ |
5/4
-----------
(4)---6---(5)
```
Vypočítajte celkovú hmotnosť minimálnej kostry. (10 bodov)
7. (a) Vysvetlite pojem topologického druhu orientovaného acyklického grafu (DAG). (6 bodov)
(b) Vykonajte topologické triedenie na nasledujúcom DAG:
```
(1) -> (2) -> (3)
\ /
-> (4)
```
Zadajte poradie vrcholov v topologickom triedení. (10 bodov)
8. a) Opíšte koncept binárnych vyhľadávacích stromov (BST). Vysvetlite, ako sa BST používajú na efektívne operácie vyhľadávania a vkladania. (6 bodov)
(b) Do pôvodne prázdneho BST vložte nasledujúce prvky:20, 10, 30, 5, 15, 25, 35. Nakreslite výsledný BST a analyzujte časovú zložitosť hľadania prvku v tomto BST. (10 bodov)
Nezabudnite preukázať jasné pochopenie pojmov, poskytnúť správne vysvetlenia a v prípade potreby analyzovať časovú a priestorovú zložitosť algoritmov.