Datové struktury I

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
Datové struktury I
Kód předmětu: NTIN066
Přednáší: Václav Koubek

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)n/2<=n!
Krátký důkaz:
n!=1.2.3... obs. aspoň n/2 činitelů větších než n/2
⇒ zlogaritmujeme ⇒...
Důkaz:

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 :-) )

Matematickou indukcí


[(n+1)/2](n+1)/2=[(n+1)/2]n/2[(n+1)/2]1/2=
=[(n+1)/2]1/2$ \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]1/2*(n/2)n/2*2<=(n+1)n!
Mne to vychadza skor takto:
=[(n+1)/2]1/2$ \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)n/2[(n+1)/2]1/2*2 <= n!(n+1)
Pravda, vypadl mi při copy&paste člen


A co přímo takto?
$ \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.:$ \left ({{n+1} \over n}\right)^{n \over 2}\rightarrow e^{1 \over 2} < 2 $

log(n!)>=log(n/2)n/2=n/2*log(n/2)=Ω(n*log(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/2*log(n/2) = n/2(log(n)-log 2) = n/2*log(n)-n/2.



Nemozem si pomoct ale mne to pride spravne - kolega pravdepodobne zabudol 1 nerovnost:

?$ log(n!)\ge xyz \ge log \left ({n \over 2}\right)^{n \over 2} = {n \over 2} log \left ({n \over 2}\right) \in \Omega (n log(n)) $?

Existuje $ xyz $?

Ano $ xyz = {n \over 2}log \left ({n \over 2}\right) $

Patri xyz do $ \Omega (n log(n)) $?

Ano. Hladame konstantu c taku, ze $ xyz \le c*n log(n) $ - od urciteho $ n_o $
Napriklad:
$ c \dot= {2 \over 5} $
$ n_o \dot=32 $




Tvrzení $ n! \ge n^{n/2} $
Důkaz: $ n! = 1\cdot 2\cdot 3\cdot \dots\cdot n = (1\cdot n) \ (2\cdot (n-1)) \ (3\cdot (n-2)) \dots (n/2+i)\cdot (n/2-i+1)\dots ([n/2]+1)\cdot[n/2] \ge n^{n/2} $, neboť každý z "dvojčlenů" má hodnotu alespoň $ n $. To

plyne z toho, že pro libovolná dvě kladná čísla $ a \ge b $ platí, že $ a \cdot b > (a+1)(b-1) = a \cdot b - a + b - 1 $; jinými slovy pokud $ a+b=n+1 $, tak $ a\cdot b $ je minimální když $ a=n $, $ b=1 $. (OT: naopak by se maximalizoval když $ a=[n/2]+1 $, $ b=[n/2] $).

Tvrzení $ \log n! = \Omega(n\cdot \log n) $

Z předchozího je snadné, $ \log n! \ge \log n^{n/2} = n/2 \cdot \log n $. Zřejmě není třeba meditovat, že pravá strana je funkce třídy $ \Theta(n\cdot \log n) $. (Samozřejmě i původní $ n/2 \cdot \log n/2 $ byla $ \Theta(n\cdot \log n) $).

Algoritmy

  • Insert sort
V cyklu zatřizuji prvky do hotové části z nesetříděného zbytku.
  • Select sort
V cyklu hledám min (resp. max) nesetříděného zbytku a přidávám je jako max (rep. min) do hotové části.
  • Bubble sort
V cyklu jedu od začátk ke konci a naopak a opravuji špatně sřazené dvojice.
  • Shell sort
název podle autora (publikováno 1959)
podobný bubble sortu - porovnává a v případě potřeby zaměňuje dvě hodnoty
neporovnává dva sousední prvky, ale prvky od sebe vzdálené d
v dalším průchodu se vzdálenost d zmenšuje na polovinu.
při porovnání i-tého a j-tého prvku a jejich případné záměně se provádí ještě porovnání s prvkem i-d a při jejich záměně i s prvekm i-2d atd. (při prvním průchodu jsou tedy uspořádané stejně vzdálené dvojice, při druhém čtveřice, při třetím osmice,...)
citace
  • Quick sort
  • Merge sort
  • Bucket sort


  • Hybrid sort
  • Radix sort
k mísná čísela postupně v krocích zatřizuje do krabiček (0,1,..,9) a to podle číslice, která je n-tá od konce v kroce n (1 krok==poslední číslice
důležité je pořadí při zatřizování. mezivýsledky po kroce m dávají uspořádání po další krok
  • A-sort

Třídění Třídění

Odkazy

Citováno z „http://wiki.matfyz.cz/index.php?title=Datové_struktury_I&oldid=36244“