Algoritmy 2 Mgr. Tomáš Kühr, Ph.D.
Tato stránka obsahuje informace ke cvičení předmětu Algoritmy 2 (KMI/ALGO2) vedeného Tomášem Kührem. Toto cvičení je určeno pro studenty matematických oborů, u nichž se nepředpokládají žádné programátorské dovednosti.Požadavky na zápočet
Zápočet bude udělen po splnění následujících požadavků:- aktivní účast na cvičeních (maximálně 3 neúčasti)
- vyřešení zápočtových úloh (buď programovací nebo neprogramovací verze)
Programovací verze zápočtové úlohy:
V libovolném programovacím jazyce implementujte datovou strukturu B-strom a základní operace s ní (search, insert, delete). Pro jednoduchost můžete pracovat pouze s klíči (tj. bez externích dat, která jsou na klíče obvykle navázána). Strukturu náležitě otestujte...Neprogramovací verze:
Vyřešte obě následující úlohy.- Napište pseudokód funkcí pro vkládání a odebírání dat do/z hashovací tabulky používající libovolnou variantu otevřeného adresování. V pseudokódu můžete použít primární hashovací funkci c(x), aniž byste ji specifikovali.
- Uvažujme hashovací tabulku používající metodu dvojího hashování. Označme d největší společný dělitel hodnot h2(k) (část hashovací funkce odpovídající posunu při kolizi; pro libovolný klíč k) a m (velikost tabulky). Ukažte, že v případě neúspěšného vyhledávání místa pro klíč k bude prozkoumáváno m/d míst v hashovací tabulce, než se opět dostaneme k indexu h1(k). V případě nesoudělných hodnot h2(k) a m tedy bude prozkoumávána případně i celá hashovací tabulka.
Program cvičení
Program cvičení bude průběžně doplňován a aktualizován.- Opakování - Složitost, O-notace
- Sekvenční vyhledávání v poli
- Binární vyhledávání v poli, zásobník a fronta
- Seznamy
- Binární vyhledávací stromy
- Binární vyhledávací stromy
- Grafy a průchody grafem
- AVL-stromy
- AVL-stromy, B-stromy
- B-stromy
- Hashování
- Digitální vyhledávací stromy, Trie, Patricia Trie
- Randomizované stromy a skip-listy
Správce stránky: Tomáš Kühr