TIN066 wiki-skripta
Obsah
Účel
Tato skripta si dávají za cíl shrnout přednášenou látku předmětu Datové struktury I, přibližně ve stejném pořadí a někdy v budoucnu možná i ve stejném rozsahu, jako se přednáší. V této chvíli jsou ve stádiu nejzákladnějšího rozpracování, nejdříve si dávají za cíl "pokrytí do šířky", tedy zmínění všeho, co se probírá a zkouší, další generace pak snad prohloubí výklad i "do hloubky", tedy včetně všech náležitých důkazů; zatím se předpokládá, že čtenáři tato skripta využijí k získání základního přehledu a detaily si dohledají jinde (a možná doplní i sem ;).
Motivace
Proč další skripta?! Existují skripta přímo doc. Koubka, jsou však na mnoha místech velice nepřehledná, občas i zbytečně podrobná. Dále existují skripta Vidner-Kotal, ta však nejsou kompletní, občas také již předem předpokládají příliš mnoho znalostí, a nesnadno se pro externistu rozšiřují - v tom má wiki forma nespornou výhodu (i když je ošklivější než čistý TeX). Pak existuje např. Tuetschekův výcuc, ten je sice poměrně kompletní, ale také rozhodně nesplňuje charakteristiku "začátečnického materiálu", na který tato skripta aspirují. Všechny tyto zdroje však těm základům již znalým bezesporu dobře poslouží.
Úvod
...nebo spíše prerekvizity; ideálně by se jim měla věnovat celá zvláštní kapitola, ale to ji někdo musí nejdříve napsat. Tak tedy jen stručný přehled, abyste věděli, o čem si třeba přečíst ve Wikipedii...
Předpokládáme, že víte, co je to posloupnost, strom, hashovací tabulka, a tak.
Předpokládáme, že si ještě pamatujete nějaké základy ze složitosti - co znamená O a $ \Theta $ notace a jak spočítat složitost triviálního algoritmu. V důkazech se můžou objevit nějaké rekurentní vztahy a součty základních řad (1/x, 1/x^2, ...); nevím, jestli je někde potřeba Master theorem.
Pro počítání očekávaných složitostí je nutné mít ideu o základech pravděpodobnostního počtu - co je to pravděpodobnost, střední hodnota a rozptyl, jak funguje binomické rozdělení (to se vyskytuje zdaleka nejčastěji), a jak vypadá Markovova nerovnost (čím dále jsme od střední hodnoty, tím jsme méně pravděpodobní) a Čebyševova nerovnost (to samé, ale v závislosti na rozptylu a mnohem přesnější).
Doporučené pořadí: V obsahu jsou kapitoly uspořádané přibližně tak, jak se probíraly, ovšem co se týče stádia dokončenosti a uživatelské přívětivosti, doporučuji si nejdříve přečíst kapitolku o přihrádkovém třídění, to je již téměř dokončené a třeba vám z toho budou jasnější některé základní techniky; obecně pak jsou hotovější kapitoly spíše na konci.
TODO list
Původní autor (Pasky) již zkoušku udělal, takže teď je to na vás!
- Chtělo by to sidebar pro snadnou navigaci - jako u wiki-skript k Vyčíslitelnosti
- Je třeba rozepsat byť i základy kapitol o stromech
- Kromě "okecání" algoritmu by se hodil i nějaký formální popis
- Až na výjimky nejsou ve wiki důkazy složitostí, které bývají potřeba! (Alespoň na lepší známku než tři.)
