Datové struktury I: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(Často kladené dotazy)
(Často kladené dotazy)
Řádka 30: Řádka 30:
  
 
Další
 
Další
*Separované a srůstající hašování
+
*Separované a srůstající hašování (LICH,VICH,EICH)
 
*Leftis haldy
 
*Leftis haldy
 
*Binomiální haldy
 
*Binomiální haldy
Řádka 37: Řádka 37:
 
*Mergesort s posloupnostmi rozdílné délky
 
*Mergesort s posloupnostmi rozdílné délky
 
*Vyhledávání v uspořádaném poli
 
*Vyhledávání v uspořádaném poli
*Srustající hashování (LICH,VICH,EICH)
 
  
 
= Třídění =
 
= Třídění =

Verze z 11. 2. 2007, 18:08

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

  • Univerzální hašování
  • (a,b)-stromy
  • A-sort
  • AVL-stromy
  • Červeno-černé stromy
  • Rozhodovací stromy (môže prejsť na otázku na algoritmy, ktoré "porušujú" dolný odhad zložitosti)

Menej časté

  • Dvojité hašování
  • Perfektní hašování
  • Externí hašování

Další

  • Separované a srůstající hašování (LICH,VICH,EICH)
  • Leftis haldy
  • Binomiální haldy
  • Wordsort
  • Quicksort
  • Mergesort s posloupnostmi rozdílné délky
  • Vyhledávání v uspořádaném poli

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!
Důkaz:
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))

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