From 3512efbbf001ea533c252c3f468f67e389909e71 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 1 Jun 2009 20:44:30 +0200 Subject: [PATCH] Hashovani zarazeno na spravne misto. --- 12-hash/12-hash.tex | 32 ++++++++--------- 13-hash/13-hash.tex | 84 --------------------------------------------- 13-hash/Makefile | 3 -- 3 files changed, 16 insertions(+), 103 deletions(-) delete mode 100644 13-hash/13-hash.tex delete mode 100644 13-hash/Makefile diff --git a/12-hash/12-hash.tex b/12-hash/12-hash.tex index 01ca78f..776e160 100644 --- a/12-hash/12-hash.tex +++ b/12-hash/12-hash.tex @@ -4,16 +4,16 @@ V pøedchozích kapitolách jsme se zabývali tøídìním prvkù a zjistili jsme, ¾e v obecném pøípadì (kdy¾ smíme prvky pouze porovnávat a prohazovat) nelze tøídit rychleji ne¾ v èase $\Theta(n\log n)$. Zároveò jsme do¹li k tomu, ¾e pokud víme o prvcích nìco více (napø. jejich rozsah), tak jsme v nìkterých pøípadech schopni tøídit i s lineární èasovou slo¾itostí. -V praxi nicménì vìt¹inou netøídíme samotná èísla, ale spí¹e nìjaké polo¾ky, napø. urèené uspoøádanou dvojicí (klíè, hodnota), kde klíèe jsou unikátní a existuje na nich lineární uspoøádání. Ukázali jsme si, jak takovouto mno¾inu udr¾ovat (aby se v ní dalo rychle vyhledávat, zaøazovat i mazat) ve vyhledávacích stromech. Dokázali jsme si, ¾e pokud budeme udr¾ovat strom dostateènì vyvá¾ený, tak budou jednotlivé operace (\, \ a \) trvat $\Theta(\log n)$. +V praxi nicménì vìt¹inou netøídíme samotná èísla, ale spí¹e nìjaké polo¾ky, napø. urèené uspoøádanou dvojicí (klíè, hodnota), kde klíèe jsou unikátní a existuje na nich lineární uspoøádání. Ukázali jsme si, jak takovouto mno¾inu udr¾ovat (aby se v ní dalo rychle vyhledávat, zaøazovat i mazat) ve vyhledávacích stromech. Dokázali jsme, ¾e pokud budeme udr¾ovat strom dostateènì vyvá¾ený, tak budou jednotlivé operace (\, \ a \) trvat $\Theta(\log n)$. -Ne¹lo by to ale rychleji? Odpovìï je jak kdy. Podívejme se na dal¹í mo¾nosti. Nejdøíve si ale pøipomeòme základní pojmy, které budeme pou¾ívat. +Ne¹lo by to ale rychleji? Odpovìï je \uv{jak kdy}. Podívejme se na dal¹í mo¾nosti. Nejdøíve si ale pøipomeòme základní pojmy, které budeme pou¾ívat. -Klíèe budou prvky universa, co¾ je mno¾ina $\{ 0, \dots, U-1 \}$, kterou budeme oznaèovat $[U]$. Tuto mno¾inu budeme chtít udr¾ovat v nìjaké ¹ikovné datové struktuøe, abychom v ní mohli rychle vyhladávat, zaøazovat i mazat. Dále $n$ bude znaèit (maximální) poèet prvkù, které si budeme v jednu chvíli pamatovat. +Klíèe budou prvky universa, co¾ je mno¾ina $\{ 0, \dots, U-1 \}$, kterou budeme oznaèovat $[U]$. Tuto mno¾inu budeme chtít udr¾ovat v nìjaké ¹ikovné datové struktuøe, abychom v ní mohli rychle vyhledávat, zaøazovat i mazat. Dále $n$ bude znaèit (maximální) poèet prvkù, které si budeme v jednu chvíli pamatovat. \h{1. Pole {\it indexované od $0$ do $U-1$}} -Pokud bude velikost universa dostateènì malá, tak si mù¾eme polo¾ky pamatovat v poli o velikosti universa. Operace \, \ i \ pracují v~èase $\O(1)$, ale platíme za~to pamì»ovou slo¾itostí $\O(U)$. Kdy¾ uvá¾íme, ¾e si budeme pamatovat mnohem ménì prvkù, ne¾ je velikost universa, tak je to velké plýtvání. +Pokud bude velikost universa dostateènì malá, tak si mù¾eme polo¾ky pamatovat v poli o velikosti universa. Operace \, \ i \ pracují v~èase $\O(1)$, ale platíme za~to pamì»ovou slo¾itostí $\Theta(U)$. Kdy¾ uvá¾íme, ¾e si budeme pamatovat mnohem ménì prvkù, ne¾ je velikost universa, tak je to velké plýtvání. \h{2. Èíslicový strom} @@ -27,7 +27,7 @@ Operace \ bude trvat $O(\log_b U)$ (najit Èím bude základ $b$ men¹í, tím bude lep¹í pamì»ová a hor¹í èasová slo¾itost a obrácenì. Èíslicový strom tedy vy¾aduje peèlivé nastavení parametrù. -\s{Pøíklad:} Pøedstavme si, ¾e klíèe budou IP-adresy, tedy 32-bitová èísla. Jak zvolit $b$, aby byla èasová i pamì»ová slo¾itost pøijatelná? Zkusme rozdìlit IP-adresu na 4 kusy, $b$ bude tedy 256. Strom bude mít hloubku 4. Èas bude v poødáku, ale po¾adavky na prostor jsou dost vysoké. Výhodnìj¹í bude rozdìlit IP-adresu na 8 èástí, $b$ bude tedy 16, hloubka stromu 8 a nároky na èas i pamì» jsou pøijatelné. +\s{Pøíklad:} Pøedstavme si, ¾e klíèe budou IP-adresy, tedy 32-bitová èísla. Jak zvolit $b$, aby byla èasová i pamì»ová slo¾itost pøijatelná? Zkusme rozdìlit IP-adresu na 4 kusy, $b$ bude tedy 256. Strom bude mít hloubku 4. Èas bude v poøádku, ale po¾adavky na prostor jsou dost vysoké. Výhodnìj¹í bude rozdìlit IP-adresu na 8 èástí, $b$ bude tedy 16, hloubka stromu 8 a nároky na èas i pamì» jsou pøijatelné. \h{4. Hashování } @@ -41,42 +41,42 @@ Probl Jak se dá tedy kolizím bránit? Nejvýhodnìj¹í by bylo mít dobrou hashovací funkci, která by mapovala prvky pokud mo¾no rovnomìrnì. Ale nìkdy staèí i prùmìrnì dobrá funkce a dostateènì náhodné klíèe. -\s{Vsuvka:} Jaká je pravdìpodobnost, ¾e 2 z k lidí mají narozeniny ve stejný den? Staèí 23 lidí, aby nastala kolize s pravdìpodobností vìt¹í ne¾ jedna polovina. Aby nenastala, potøebovali bychom vìt¹í poèet pøihrádek: $p = cm^2$. +\s{Vsuvka:} Jaká je pravdìpodobnost, ¾e 2 z k lidí mají narozeniny ve stejný den? Staèí 23 lidí, aby nastala kolize s pravdìpodobností vìt¹í ne¾ jedna polovina. Aby nenastala, potøebovali bychom vìt¹í poèet pøihrádek: $m \approx n^2$. \h{Praktické hashovací funkce} \s{První pøíklad} -Tato hashovací funkce $h: [U] \rightarrow [m]$ je definovaná pøedpisem: $h(x) = x \mod m$. Pro dostateènì náhodné hodnoty bude fungovat, ale v mnoha pøípadech mù¾e být nevhodná. Napøíklad je zøejmé, ¾e pro sudé $m$ zachovává paritu. V pøípadì, ¾e sudých, resp. lichých klíèù bude mnohem více, vznikne mnoho zbyteèných kolizí. Pro takovouto hashovací funkci je nejlep¹í zvolit za $m$ nìjaké prvoèíslo. +Tato hashovací funkce $h: [U] \rightarrow [m]$ je definovaná pøedpisem: $h(x) = x \mod m$. Pro dostateènì náhodné hodnoty bude fungovat, ale v mnoha pøípadech mù¾e být nevhodná. Napøíklad je zøejmé, ¾e pro sudé $m$ zachovává paritu. V pøípadì ¾e sudých, resp. lichých klíèù bude mnohem více, vznikne mnoho zbyteèných kolizí. Pro takovouto hashovací funkci je nejlep¹í zvolit za $m$ nìjaké prvoèíslo. \s{Druhý pøíklad} Zvolme si iracionální $\alpha$ z intervalu $(0,1)$. Funkce bude definovaná následovnì: $$h(x) = \lfloor m (x \cdot \alpha \mod 1) \rfloor.$$ Tato funkce by mìla na $x$ záviset velmi málo, ale nebudeme si to dokazovat. -\s{Implementace} Reálná èísla se samozøejmì implementují dosti nároènì (resp. to vùbec nejde), tak¾e v praxi se tento postup aproximuje celoèíselnì. Místo reálné $\alpha$ si zvolme $A = \lfloor \alpha \cdot 2^w \rfloor$, kde $2^w$ je ¹íøka slova ($w$ je napø. poèet bitù integeru). Potom místo výrazu $(x \cdot \alpha \mod 1)$, který je z intervalu $(0,1)$, budeme poèítat s výrazem $(x \cdot A \mod 2^w)$. Potom na¹e funkce vyjde následovnì: +\s{Implementace:} Reálná èísla se samozøejmì implementují dosti nároènì (resp. to vùbec nejde), tak¾e v praxi se tento postup aproximuje celoèíselnì. Místo reálné $\alpha$ si zvolme $A = \lfloor \alpha \cdot 2^w \rfloor$, kde $2^w$ je ¹íøka slova ($w$ je napø. poèet bitù integeru). Potom místo výrazu $(x \cdot \alpha \mod 1)$, který je z intervalu $(0,1)$, budeme poèítat s výrazem $(x \cdot A \mod 2^w)$. Potom na¹e funkce vyjde následovnì: -$$h(x) = \lfloor { m(x \cdot A \mod 2^w) \over 2^w } \rfloor$$ +$$h(x) = \left \lfloor { m(x \cdot A \mod 2^w) \over 2^w } \right \rfloor$$ -Zbývá jen otázka, jak volit $\alpha$? Osvìèená hodnota je ${1 \over \tau }$, co¾ je pøibli¾nì 0,618. ($\tau$ je hodnota zlatého øezu.) Takto zvolené $\alpha$ dobøe rozbíjí aritmetické posloupnosti, ale i toto je pouze pøedstava a nebudeme si to dokazovat. +Zbývá jen otázka, jak volit $\alpha$? Osvìèená hodnota je $1/\tau$, co¾ je pøibli¾nì 0,618. ($\tau$ je hodnota zlatého øezu.) Takto zvolené $\alpha$ dobøe rozbíjí aritmetické posloupnosti, ale i toto je pouze pøedstava a nebudeme si to dokazovat. \h{Hashování øetìzcù} Vzhledem k tomu, ¾e hashování nijak speciálnì nepotøebuje, aby byly prvky èísla, tak se mohou hashovat i øetìzce. Uka¾me si jeden pøíklad funkce pro hashování øetìzcù. -Prázdnému øetìzci pøiøaïme nulu: $h(\epsilon) = 0$. Øetìzci znakù $x_1, \dots, x_n$ pøiøaïme hodnotu: +Prázdnému øetìzci pøiøaïme nulu: $h(\varepsilon) = 0$. Øetìzci znakù $x_1, \dots, x_n$ pøiøaïme hodnotu: $$h(x_1, \dots, x_n) = (h(x_1, \dots, x_{n-1}) \cdot + x_n) \mod m.$$ -$A$ je zde nìjaká konstanta. Aby se vyu¾ily v¹echny pøihrádky, tak je vhodné zvlit $A$ tak, aby $A^{{\bb E}[\]} >> m$. Tato funkce vyu¾ívá podobných vlastností jako lineární konkurenèní generátor náhodných èísel, který pomocí vhodných konstant $A$ a $B$ a ¹íøky slova $2^w$ vyrábí nové náhodné èíslo $x'$ z minulého èísla $x$ jako $$x' = (x \cdot A + B) \mod 2^w.$$ +$A$ je zde nìjaká konstanta. Aby se vyu¾ily v¹echny pøihrádky, tak je vhodné zvlit $A$ tak, aby $A^{{\bb E}[\]} \gg m$. Tato funkce vyu¾ívá podobných vlastností jako lineární konkurenèní generátor náhodných èísel, který pomocí vhodných konstant $A$ a $B$ a ¹íøky slova $w$ vyrábí nové náhodné èíslo $x'$ z minulého èísla $x$ jako $$x' = (x \cdot A + B) \mod 2^w.$$ \s{Vìta} Pokud jsou $h(x_1), \dots, h(x_n)$ rovnomìrnì náhodné, pak $$\forall i: {\bb E}[\] = {n \over m}.$$ \proof Poèet prvkù v $i$-té pøihrádce si oznaème $N_i$. Definujme si indikátor $P_{ij}$, který je roven 1, pokud $x_j$ padlo do $i$-té pøihrádky, jinak je roven 0. -Vidíme, ¾e poèet prvkù v $i$-té pøihrádce je souèet $P_{ij}$ pøes v¹echny $j$. +Vidíme, ¾e poèet prvkù v $i$-té pøihrádce je souèet $P_{ij}$ pøes v¹echna $j$. $$N_i = \sum_{j} P_{i,j}.$$ -Teï ji¾ staèí upravit následující výrazy. Vyu¾ijeme mimo jiné vìtu o linearitì støední hodnoty. -$${\bb E}[P_{ij}] = {1 \over m} \cdot 1 + (1 - {1 \over m}) \cdot 0 = {1 \over m}.$$ -$${\bb E}[N_i] = {\bb E}[\sum_{j} P_{i,j}] = \sum_{j} {\bb E}[P_{i,j}] = {n \over m}.$$ +Dále vyu¾ijeme mimo jiné vìtu o linearitì støední hodnoty. +$${\bb E}[P_{ij}] = {1 \over m} \cdot 1 + \left(1 - {1 \over m} \right) \cdot 0 = {1 \over m}.$$ +$${\bb E}[N_i] = {\bb E}\left[\sum_{j} P_{i,j}\right] = \sum_{j} {\bb E}[P_{i,j}] = {n \over m}.$$ \qed \s{Dùsledek:} Pokud bude $n$ pøibli¾nì stejnì velké jako $m$, tak v ka¾dé pøihrádce bude prùmìrnì jeden prvek. diff --git a/13-hash/13-hash.tex b/13-hash/13-hash.tex deleted file mode 100644 index 8035c60..0000000 --- a/13-hash/13-hash.tex +++ /dev/null @@ -1,84 +0,0 @@ -\input lecnotes.tex - -\prednaska{10}{Hashování}{} - -V pøedchozích kapitolách jsme se zabývali tøídìním prvkù a zjistili jsme, ¾e v obecném pøípadì (kdy¾ smíme prvky pouze porovnávat a prohazovat) nelze tøídit rychleji ne¾ v èase $\Theta(n\log n)$. Zároveò jsme do¹li k tomu, ¾e pokud víme o prvcích nìco více (napø. jejich rozsah), tak jsme v nìkterých pøípadech schopni tøídit i s lineární èasovou slo¾itostí. - -V praxi nicménì vìt¹inou netøídíme samotná èísla, ale spí¹e nìjaké polo¾ky, napø. urèené uspoøádanou dvojicí (klíè, hodnota), kde klíèe jsou unikátní a existuje na nich lineární uspoøádání. Ukázali jsme si, jak takovouto mno¾inu udr¾ovat (aby se v ní dalo rychle vyhledávat, zaøazovat i mazat) ve vyhledávacích stromech. Dokázali jsme, ¾e pokud budeme udr¾ovat strom dostateènì vyvá¾ený, tak budou jednotlivé operace (\, \ a \) trvat $\Theta(\log n)$. - -Ne¹lo by to ale rychleji? Odpovìï je \uv{jak kdy}. Podívejme se na dal¹í mo¾nosti. Nejdøíve si ale pøipomeòme základní pojmy, které budeme pou¾ívat. - -Klíèe budou prvky universa, co¾ je mno¾ina $\{ 0, \dots, U-1 \}$, kterou budeme oznaèovat $[U]$. Tuto mno¾inu budeme chtít udr¾ovat v nìjaké ¹ikovné datové struktuøe, abychom v ní mohli rychle vyhledávat, zaøazovat i mazat. Dále $n$ bude znaèit (maximální) poèet prvkù, které si budeme v jednu chvíli pamatovat. - - -\h{1. Pole {\it indexované od $0$ do $U-1$}} - -Pokud bude velikost universa dostateènì malá, tak si mù¾eme polo¾ky pamatovat v poli o velikosti universa. Operace \, \ i \ pracují v~èase $\O(1)$, ale platíme za~to pamì»ovou slo¾itostí $\Theta(U)$. Kdy¾ uvá¾íme, ¾e si budeme pamatovat mnohem ménì prvkù, ne¾ je velikost universa, tak je to velké plýtvání. - -\h{2. Èíslicový strom} - -Zvolíme vhodný základ soustavy $b$, klíè zapí¹eme v soustavì o základu $b$ a zápis ulo¾íme do stromu. Tímto nám vznikne \uv{$b$-ární strom}, tedy strom, jeho¾ ka¾dý vrchol má a¾ $b$ synù. - -Vrcholy na první hladinì pak znaèí první èíslici, na druhé druhou, atd. Na poslední hladinì bude tedy $n$ listù. Hloubka tohoto stromu je $\lceil\log_b U\rceil$. - -Operace \ bude trvat $O(\log_b U)$ (najití jednoho klíèe odpovídá projití jedné cesty ve stromì od koøene do listu). Stejný èas budou trvat i operace \ a \. (Pøi vkládání zakládáme vrcholy, které odpovídají na¹emu klíèi a které je¹tì nejsou zalo¾ené. Pøi mazání sma¾eme list a následnì vrcholy, ze kterých nic nevede. Pro tuto operaci je výhodné si ve vrcholech udr¾ovat jejich stupnì.) Strom zabere prostor velikosti $O(nb\log_b U)$. - - -Èím bude základ $b$ men¹í, tím bude lep¹í pamì»ová a hor¹í èasová slo¾itost -a obrácenì. Èíslicový strom tedy vy¾aduje peèlivé nastavení parametrù. - -\s{Pøíklad:} Pøedstavme si, ¾e klíèe budou IP-adresy, tedy 32-bitová èísla. Jak zvolit $b$, aby byla èasová i pamì»ová slo¾itost pøijatelná? Zkusme rozdìlit IP-adresu na 4 kusy, $b$ bude tedy 256. Strom bude mít hloubku 4. Èas bude v poøádku, ale po¾adavky na prostor jsou dost vysoké. Výhodnìj¹í bude rozdìlit IP-adresu na 8 èástí, $b$ bude tedy 16, hloubka stromu 8 a nároky na èas i pamì» jsou pøijatelné. - - -\h{4. Hashování } - -Mìjme $m$ pøihrádek a v ka¾dé z nich spojový seznam. Dále $h$ bude hashovací funkce, která libovolnému prvku z universa pøiøadí právì jednu pøihrádku. - -Kdyby $h$ fungovala \uv{rovnomìrnì } (ka¾dému prvku by pøiøadila jinou pøihrádku, tedy ka¾dý spojový seznam by mìl jen jeden prvek), tak bychom umìli vyhledávat, pøidávat i mazat prvky v konstantním èase. To je ov¹em samozøejmì pøíli¹ krásné na to, aby to byla pravda. - -Problém je, ¾e pokud bude $m$ výraznì men¹í ne¾ $U$ (co¾ chceme, jinak se jedná o normální (obrovské) pole a funkce je identita -- tento pøípad jsme ji¾ vyøe¹ili), tak urèitì budou existovat prvky, kterým funkce pøiøadí stejnou hodnotu. Takovému pøípadu se øíká {\it kolize}. Prvky se pak zaøadí do spojového seznamu. Kdyby byla naopak funkce hodnì ne¹ikovná a namapovala by nám v¹echny prvky do jedné pøihrádky, tak budeme v¾dy muset projít (v nejhor¹ím pøípadì celý) dlouhý spojový seznam. - -Jak se dá tedy kolizím bránit? Nejvýhodnìj¹í by bylo mít dobrou hashovací funkci, která by mapovala prvky pokud mo¾no rovnomìrnì. Ale nìkdy staèí i prùmìrnì dobrá funkce a dostateènì náhodné klíèe. - - -\s{Vsuvka:} Jaká je pravdìpodobnost, ¾e 2 z k lidí mají narozeniny ve stejný den? Staèí 23 lidí, aby nastala kolize s pravdìpodobností vìt¹í ne¾ jedna polovina. Aby nenastala, potøebovali bychom vìt¹í poèet pøihrádek: $m \approx n^2$. - -\h{Praktické hashovací funkce} - -\s{První pøíklad} - -Tato hashovací funkce $h: [U] \rightarrow [m]$ je definovaná pøedpisem: $h(x) = x \mod m$. Pro dostateènì náhodné hodnoty bude fungovat, ale v mnoha pøípadech mù¾e být nevhodná. Napøíklad je zøejmé, ¾e pro sudé $m$ zachovává paritu. V pøípadì ¾e sudých, resp. lichých klíèù bude mnohem více, vznikne mnoho zbyteèných kolizí. Pro takovouto hashovací funkci je nejlep¹í zvolit za $m$ nìjaké prvoèíslo. - -\s{Druhý pøíklad} - -Zvolme si iracionální $\alpha$ z intervalu $(0,1)$. Funkce bude definovaná následovnì: $$h(x) = \lfloor m (x \cdot \alpha \mod 1) \rfloor.$$ Tato funkce by mìla na $x$ záviset velmi málo, ale nebudeme si to dokazovat. - -\s{Implementace:} Reálná èísla se samozøejmì implementují dosti nároènì (resp. to vùbec nejde), tak¾e v praxi se tento postup aproximuje celoèíselnì. Místo reálné $\alpha$ si zvolme $A = \lfloor \alpha \cdot 2^w \rfloor$, kde $2^w$ je ¹íøka slova ($w$ je napø. poèet bitù integeru). Potom místo výrazu $(x \cdot \alpha \mod 1)$, který je z intervalu $(0,1)$, budeme poèítat s výrazem $(x \cdot A \mod 2^w)$. Potom na¹e funkce vyjde následovnì: - -$$h(x) = \left \lfloor { m(x \cdot A \mod 2^w) \over 2^w } \right \rfloor$$ - - -Zbývá jen otázka, jak volit $\alpha$? Osvìèená hodnota je $1/\tau$, co¾ je pøibli¾nì 0,618. ($\tau$ je hodnota zlatého øezu.) Takto zvolené $\alpha$ dobøe rozbíjí aritmetické posloupnosti, ale i toto je pouze pøedstava a nebudeme si to dokazovat. - -\h{Hashování øetìzcù} - -Vzhledem k tomu, ¾e hashování nijak speciálnì nepotøebuje, aby byly prvky èísla, tak se mohou hashovat i øetìzce. Uka¾me si jeden pøíklad funkce pro hashování øetìzcù. -Prázdnému øetìzci pøiøaïme nulu: $h(\varepsilon) = 0$. Øetìzci znakù $x_1, \dots, x_n$ pøiøaïme hodnotu: -$$h(x_1, \dots, x_n) = (h(x_1, \dots, x_{n-1}) \cdot + x_n) \mod m.$$ -$A$ je zde nìjaká konstanta. Aby se vyu¾ily v¹echny pøihrádky, tak je vhodné zvlit $A$ tak, aby $A^{{\bb E}[\]} \gg m$. Tato funkce vyu¾ívá podobných vlastností jako lineární konkurenèní generátor náhodných èísel, který pomocí vhodných konstant $A$ a $B$ a ¹íøky slova $w$ vyrábí nové náhodné èíslo $x'$ z minulého èísla $x$ jako $$x' = (x \cdot A + B) \mod 2^w.$$ - - -\s{Vìta} Pokud jsou $h(x_1), \dots, h(x_n)$ rovnomìrnì náhodné, pak $$\forall i: {\bb E}[\] = {n \over m}.$$ - -\proof -Poèet prvkù v $i$-té pøihrádce si oznaème $N_i$. Definujme si indikátor $P_{ij}$, který je roven 1, pokud $x_j$ padlo do $i$-té pøihrádky, jinak je roven 0. -Vidíme, ¾e poèet prvkù v $i$-té pøihrádce je souèet $P_{ij}$ pøes v¹echna $j$. -$$N_i = \sum_{j} P_{i,j}.$$ -Dále vyu¾ijeme mimo jiné vìtu o linearitì støední hodnoty. -$${\bb E}[P_{ij}] = {1 \over m} \cdot 1 + \left(1 - {1 \over m} \right) \cdot 0 = {1 \over m}.$$ -$${\bb E}[N_i] = {\bb E}\left[\sum_{j} P_{i,j}\right] = \sum_{j} {\bb E}[P_{i,j}] = {n \over m}.$$ -\qed - -\s{Dùsledek:} Pokud bude $n$ pøibli¾nì stejnì velké jako $m$, tak v ka¾dé pøihrádce bude prùmìrnì jeden prvek. - -\bye diff --git a/13-hash/Makefile b/13-hash/Makefile deleted file mode 100644 index fc04eaf..0000000 --- a/13-hash/Makefile +++ /dev/null @@ -1,3 +0,0 @@ -P=13-hash - -include ../Makerules -- 2.39.2