{{predmet|Datové struktury I|Václav Koubek|TIN066}}

Zkouška

Zkouska vypada asi takhle: Koubek kazdymu zada jedno tema a pak ceka az neco vyplodite. Po nejaky dobe se zacne rozhlizet, kdo uz neco ma a postupne koluje mezi zkousenymi dokud jim to bud neda nebo je nevyhodi :)

Na trojku temer netreba vedieť dôkazy, stačia základy. Teda pokiaľ nedostanete jasne najavo, že sa od vás dôkaz žiada, napr. otázka Rozhodovací stromy. Naopak, dobrá znalosť algoritmov je silno odporúčaná, dajte si pozor i na to, či dobre rozumiete všakovakým špeciálnym prípadom. Času je na skúške skutočne dosť, skúšajúci vybavuje ľudí podľa toho, ako prejavujú záujem.

S jednotkou sa dá odísť i bez znalosti komplikovanejších dôkazov, je však treba rozumieť princípom.

Dobrá rada: Nad zložitejšími algoritmami či dôkazmi sa asi budete obaja (vy i skúšajúci) trochu zamotávať/strácať. Vyhýbajte sa však postoju, že "ja to mám predsa správne", najmä ak si nie ste 115% istí. Skúšajúci sa bude vašu odpoveď snažiť pochopiť. Ak sa niekde stratí/zmýli, tak sa po dialógu s vami opraví a nakoniec vám férovo uzná všetko, čo ste mali správne, hoci trebárs neprehľadne zapísané. Ak máte vo svojej odpovedi chybu ale máte správny prístup, tak vám umožní - priam od vás očakáva, aby ste sa opravili.

ZS 2006/7

Koubek vezme do posluchárny 20 lidí, každému dá otázku a pak čeká, než se někdo přihlásí, že chce mluvit. Jelikož do loňského roku nebyly datovky povinné, tak se zkoušelo na termínech po čtyrech a i okruh otázek byl podle zpráv co jsem někde vyčetl o něco menší než ten, který jsem slyšel dnes okolo sebe... Koubek je fakt v pohodě.

Proslýchá se, že když si sednete do první řady máte větší šanci dostat nějaké hashování, důkaz pro toto tvrzení zatím ale není znám. :-)

Často kladené dotazy

*(a,b)-stromy *AVL-stromy

*Červeno-černé stromy *Dvojité hašování

*Perfektní hašování *Rozhodovací stromy (môže prejsť na otázku na algoritmy, ktoré "porušujú" dolný odhad zložitosti)

*Univerzální hašování

Menej časté *A-sort

*Externí hašování *Vyhledávání v uspořádaném poli

*Quicksort

Další *Binomiální haldy

*Fibonnaciho haldy *Leftis haldy

*Mergesort s posloupnostmi rozdílné délky *Separované a srůstající hašování (LICH,VICH,EICH)

*Wordsort

2009/2010

Rozsah látky se, zdá se, trochu změnil, vypadá to (bez záruky), že se zkouší/nezkouší:

  • Hashe: Perfektní, univerzální, dvojité hashování --- méně často (ale občas ano!) jednoduchá hashování, separované řetězce, srůstající, ...

  • Stromy: RB stromy, AVL stromy --- méně často normální BVS, (a,b) stromy

  • Haldy: Fibonacciho, binomiální, leftist haldy --- málokdy d-regulární?

  • Třídění: Quicksort, A-sort, rozhodovací stromy

  • Hledání: Vyhledávání v uspořádaném poli, hledani k-teho nejmensiho prvku

  • Dynamizace: --- nic

Ale pozor, to jsou sice nejc podle

Optimálne BVS, Trie, Splay a dynamizácia sú obsahom dátových štruktúr II.

Třídění

Dolní odhad složitosti

Binární rozhodovací strom s n! má výšku alespoň Ω(n*log(n))

Důkaz:

:Tvrzení :(n/2)<sup>n/2</sup><=n!

:Krátký důkaz:

:n!=1.2.3... obs. aspoň n/2 činitelů větších než n/2

:⇒ zlogaritmujeme ⇒...

:Důkaz:

<b>Dle mého názoru příliš bláznivé a zbytečně složité; dole přebásněné IMHO jednodušeji (a bez indukce, skoro :-) )</b>

:Matematickou indukcí

:[(n+1)/2]<sup>(n+1)/2</sup>=[(n+1)/2]<sup>n/2</sup>[(n+1)/2]<sup>1/2</sup>=

:=[(n+1)/2]<sup>1/2</sup>∑k=0n2(n2k)(n2)k(12)n2−k\sum_{k=0}^{n \over 2} {{n \over 2} \choose k}\left ({n \over 2}\right)^k \left ({1 \over 2}\right)^{{n \over 2}-k}<=[(n+1)/2]<sup>1/2<sup>n/2</sup>*2<=(n+1)n! :Mne to vychadza skor takto:

:=[(n+1)/2]<sup>1/2</sup>∑k=0n2(n2k)(n2)k(12)n2−k\sum_{k=0}^{n \over 2} {{n \over 2} \choose k}\left ({n \over 2}\right)^k \left ({1 \over 2}\right)^{{n \over 2}-k} = $\left ({{n + 1} \over 2}\right)^{1 \over 2} \left ({n \over 2}\right)^{n \over 2} \sum_{k=0}^{n \over 2} {{n \over 2} \choose k}\left ({2 \over n}\right)^{{n \over 2} - k} \left ({1 \over 2}\right)^{{n \over 2}-k} = \left ({{n + 1} \over 2}\right)^{1 \over 2} \left ({n \over 2}\right)^{n \over 2} \left ({{1 \over n} +1}\right)^{n \over 2}

$

:: <= (n/2)<sup>n/2<sup>1/2</sup>*2 <= n!(n+1)

:Pravda, vypadl mi při copy&paste člen

:A co přímo takto?

:(n+12)n+12=(n+12)12(n+12)n2≤(n+12)12(n+1n)n2(n2)n2≤(n+12)2(n2)n2≤(n+1)n!\left ({{n + 1} \over 2}\right)^{{n + 1} \over 2}=\left ({{n + 1} \over 2}\right)^{1 \over 2}\left ({{n + 1} \over 2}\right)^{n \over 2}\leq\left ({{n + 1} \over 2}\right)^{1 \over 2}\left ({{n+1} \over n}\right)^{n \over 2}\left ({n \over 2}\right)^{n \over 2}\leq\left ({{n + 1} \over 2} \right)2 \left({n \over 2}\right)^{n \over 2}\leq\left(n+1\right)n!

::Pozn.:(n+1n)n2→e12<2\left ({{n+1} \over n}\right)^{n \over 2}\rightarrow e^{1 \over 2} <2

log(n!)>=log(n/2)<sup>n/2</sup>=n/2log(n/2)=Ω(nlog(n))

Nemůžu si pomoci ale přijde uvedený výsledek mi přijde špatně: Nelíbí se mi ta nerovnost. To bych mohl taky odvodit:

log(n!)>=log(n)=Ω(n) Navíc n/2log(n/2) = n/2(log(n)-log 2) = n/2log(n)-n/2.

Algoritmy

Odkazy