home
Datové struktury - skripta
Když jsem narazil na stránku
Martina Vidnera
na které byly ke stažení skripta z datových struktur, zaradoval jsem se.
Moje nadšení trošku opadlo poté co jsem zjistil, že skripta nejsou zdaleka
kompletní. Toto je pokus jejich doplnění do kompletní podoby reflektující
přednášku V. Koubka l.p. 2002/2003.
update: Akademický rok 2003/2004 přináší novinky a mezi nimi i rozložení
DS do dvou jednosemestrálních předmětů. S tím jak se mi budou blížit
státnice, budu skripta opravovat/dopisovat podle přednášek 2003/2004.
31.5.2005 update: Na vlastni kuzi jsem si overil, ze podle techto
skript lze uspesne zodpovedet otazku Datove struktury u statnich zkousek.
Pokud byste/jste
- chtěli přispět k stávajícím zdrojákům
- našli chybu/chyby (překlepy, typograficke, fakticke) v textu
ozvěte se mi. (viz. mail dole) Pokud mi budete posílat opravy,
nespoléhejte se na čísla stránek, ale na číslování (pod)sekcí, vět,
definic atp.
<rant>
Zjistil jsem, že matfyzáci jsou obecně velmi líní a hotovou práci si s
díky vezmou, ale nedá se čekat, že by něco sami udělali. Nejprve jsem
se rozhodl, že na skriptech budu pracovat, ale zveřejním je až za nějakou
dobu, začátkem zkouškového 2002/2003 jsem ovšem vyměkl a zveřejnil vše.
Pro lidi, kteří
jsou zvyklí vzít si hotovou práci jiných, je to ovšem dvojsečné, protože
skripta jsou natolik nehotová, že mohou zatím posložit pouze jako cvičení
v opravování chyb druhých (aneb můžete počítat s tím, že fundamenální
definice může být ve skriptech špatně - na nějaké jsem byl upozorněn od
lidí, co se ze skript učili na státnice).
</rant>
Ke stažení
Co se zkouší
Každoročně má spousta lidí (ti co nechodí na přednášky) pochybnosti o tom,
co se zkouší a co ne. Následující seznamy reflektují přednášky z akad.
roku 2003-2004, v dalších letech se může obsah asi měnit, ale pravděpodobně ne
velmi.
V zimě (Datové struktury I) se zpravidla zkouší násl. témata:
- hašování (se sep. řetězci, s přesuny, s lin. přidáváním,
universální, perfektní, externí)
- vyhledávání (hlavně zobecněné kvadratické)
- binární vyhledávací stromy (optimální BVS, kvadratické programování,
červeno-černé stromy)
V létě (Datové struktury II) jsou to násl. témata:
- (a,b)-stromy (normální, A-sort, paralelní přístup, s prstem)
- Trie (normální, komprimované, velmi komprimované)
- Haldy (d-regulární, binomiální, leftist, fibonacciho) + Dijkstruv alg.
- (Semi)dynamizace
- samoopravující se struktury (algoritmy MFR a TR, splay stromy)
Občas se na zkoušce objeví také některé téma, které se probíralo na
cvičení, ale zřejmě jen velmi zřídka.
Changelog
- 27.10.05 zakomponována část oprav od Vojty Havránka
- 9.5.05 opravy v důkazu pro AVL stromy, dodatečné poznámky k haldám a
AVL stromům
- 8.5.05 menší počet drobných oprav, hlavně co se týče
formátování. Přidány (z mého pohledu cenné) poznámky k Trie.
- 7.5.05 lepší biblografie, mírný redeisgn první stránky, menší počet
kosmetických úprav
- 6.10.04 opravy v kapitolách Hašování I, II, doplněny obrázky k
externímu hašování
- 26.9.04 obrázek a opravy v kapitole Binární vyhl. stromy
- 25.9.04 obrázky a vysvětlení k operacím na (a,b)-stromech
- 22.9.04 opravy v celých skriptech, dopsány Fibonacciho haldy + obrázky
- 20.7.04 vysvětlení k dynamizaci, předmluva ke skriptům
- 23.6.04 spousta oprav hlavně v dynamizaci, trie, splay, heaps, ...
- 22.6.04 kupa práce na splay stromech, dynamizaci, ...
- 10.6.04 doplněny AVL stromy
- 2.2.04 kupa malých změn, převážně opravy
- 30.1.04 napsána zgruntu podkapitola Externí hashování, pouze v
cvs
- 27.1.04 lepší makefile, dopsána kapitola o opt. bin. vyhl. stromech,
opravena kapitola o červenočerných stromech. zatím vše pouze v cvs.
- 26.1.04 pdf soubor se teď překládá včetně obrázků
- 15.6.02 - opraveno mnoho chyb (T.Matoušek, V.Kotal)
vložen referát o skoroopt. vyhl. stromech
(Ladislav Strojil),
připsán text o (a,b) stromech s prstem
- 1.6.02 - opraveno mnoho chyb (T.Matoušek, L.Prošek)
- zčásti dopsána poslední přednáška, chybí tak polovina
- doplněna kapitola o ještě více kompr. tries, raw přepis
- dopsána přednáška z 12.5.02 (Dynam)
- dopsána přednáška z 14.4.02 (Haldy), chybí obrázky
- dopsána přednáška z 7.4.02 (Haldy), chybí obrázky
- dopsána přednáška z 24.3.02 (Splay), chybí obrázky, kusy vzorců
- přednáška z 19.3.02 (MFR, TR), chybí obrázky, kusy vzorců
Credits
Následujícím osobám patří díky:
- Martin Mačok - faktické opravy
- Tomáš Matoušek - množství faktických oprav
- Ladislav Prošek - překlepy, faktické opravy
- Jana Skotáková - zapůjčení poznámek
- Martin Malý - zapůjčení poznámek
- Vojtěch Fried - algoritmus pro INSERT v semidyn. systémech
- Michal Kováč - překlepy, faktické opravy
Kompletní seznam lidí, kteří se na skriptech podíleli je možné najít v
samotných skriptech.