÷ÓÅ Ï ÇÅÏÌÏÇÉÉ :: ÎÁ ÇÌÁ×ÎÕÀ ÓÔÒÁÎÉÃÕ! çÅÏ×ÉËÉÐÅÄÉÑ 
wiki.web.ru 
ðÏÉÓË  
   Rambler's Top100 Service
 çÌÁ×ÎÁÑ ÓÔÒÁÎÉÃÁ  ëÏÎÆÅÒÅÎÃÉÉ: ëÁÌÅÎÄÁÒØ / íÁÔÅÒÉÁÌÙ  ëÁÔÁÌÏÇ ÓÓÙÌÏË    óÌÏ×ÁÒØ       æÏÒÕÍÙ        ÷ ÐÏÍÏÝØ ÓÔÕÄÅÎÔÕ     ðÏÓÌÅÄÎÉÅ ÐÏÓÔÕÐÌÅÎÉÑ
   çÅÏÌÏÇÉÑ | ëÕÒÓÙ ÌÅËÃÉÊ
 ïÂÓÕÄÉÔØ × ÆÏÒÕÍÅ  äÏÂÁ×ÉÔØ ÎÏ×ÏÅ ÓÏÏÂÝÅÎÉÅ
÷ÐÅÒÅÄ ÷×ÅÒÈ îÁÚÁÄ óÏÄÅÒÖÁÎÉÅ ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ
÷ÐÅÒÅÄ: 5.5.2 óÅÍÅÊÓÔ×Á ÏÄÎÏÓÔÏÒÏÎÎÉÈ ÈÜÛ-ÆÕÎËÃÉÊ ÷×ÅÒÈ: 5.5 ôÅÏÒÅÔÉÞÅÓËÉÅ ÁÓÐÅËÔÙ îÁÚÁÄ: 5.5 ôÅÏÒÅÔÉÞÅÓËÉÅ ÁÓÐÅËÔÙ   óÏÄÅÒÖÁÎÉÅ   ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ


5.5.1 õÎÉ×ÅÒÓÁÌØÎÙÅ ÓÅÍÅÊÓÔ×Á ÈÜÛ-ÆÕÎËÃÉÊ

ðÏÎÑÔÉÅ ÕÎÉ×ÅÒÓÁÌØÎÏÇÏ ÓÅÍÅÊÓÔ×Á ÈÜÛ-ÆÕÎËÃÉÊ ÂÙÌÏ ××ÅÄÅÎÏ × 1979 Ç. ëÁÒÔÅÒÏÍ É ÷ÅÇÍÁÎÏÍ [CW].

ïÐÒÅÄÅÌÅÎÉÅ 1.  ðÕÓÔØ $ A$ É $ B$ -- Ä×Á ËÏÎÅÞÎÙÈ ÍÎÏÖÅÓÔ×Á É $ H$ -- ÓÅÍÅÊÓÔ×Ï ÆÕÎËÃÉÊ ÉÚ $ A$ × $ B$. $ H$ ÎÁÚÙ×ÁÅÔÓÑ ÕÎÉ×ÅÒÓÁÌØÎÙÍ ÓÅÍÅÊÓÔ×ÏÍ ÈÜÛ-ÆÕÎËÃÉÊ, ÅÓÌÉ ÄÌÑ ÌÀÂÙÈ $ x_1\ne x_2\in A$ É $ y_1,y_2\in B$

$\displaystyle \Pr[h(x_1)= y_{1}\land h(x_{2})=y_{2}]=1/\vert B\vert^{2}. $

÷ÅÒÏÑÔÎÏÓÔØ ÂÅÒÅÔÓÑ ÐÏ ÓÌÕÞÁÊÎÏÍÕ ÒÁ×ÎÏ×ÅÒÏÑÔÎÏÍÕ ×ÙÂÏÒÕ ÆÕÎËÃÉÉ $ h$ ÉÚ ÓÅÍÅÊÓÔ×Á $ H$.

ïÂÙÞÎÏ ÐÒÅÄÐÏÌÁÇÁÅÔÓÑ, ÞÔÏ ÍÏÝÎÏÓÔØ ÏÂÒÁÚÁ (ÍÎÏÖÅÓÔ×Á $ B$) ÍÅÎØÛÅ, ÞÅÍ ÍÏÝÎÏÓÔØ ÐÒÏÏÂÒÁÚÁ ($ A$), É ÞÔÏ ÈÜÛ-ÆÕÎËÃÉÉ "ÓÖÉÍÁÀÔ" ×ÈÏÄÎÙÅ ÓÌÏ×Á. ëÁË ÐÒÁ×ÉÌÏ, ÒÁÓÓÍÁÔÒÉ×ÁÀÔÓÑ ÓÅÍÅÊÓÔ×Á ÈÜÛ-ÆÕÎËÃÉÊ, ËÏÔÏÒÙÅ ÐÅÒÅ×ÏÄÑÔ ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ Ä×ÏÉÞÎÙÈ ÓÔÒÏË ÄÌÉÎÙ $ n$ × ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ Ä×ÏÉÞÎÙÈ ÓÔÒÏË ÄÌÉÎÙ $ m$, ÇÄÅ $ m<n$. çÏ×ÏÒÑ ÎÅÆÏÒÍÁÌØÎÏ, ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÓÅÍÅÊÓÔ×Ï ÈÜÛ-ÆÕÎËÃÉÊ -- ÜÔÏ ÍÅÔÏÄ "ÐÅÒÅÍÅÛÉ×ÁÎÉÑ" Ó ÓÏËÒÁÝÅÎÉÅÍ ÄÌÉÎÙ ÓÔÒÏË, ÐÒÉ ËÏÔÏÒÏÍ ×ÙÈÏÄÎÙÅ ÚÎÁÞÅÎÉÑ ÒÁÓÐÒÅÄÅÌÅÎÙ ÒÁ×ÎÏÍÅÒÎÏ.

óÅÍÅÊÓÔ×Ï ÈÜÛ-ÆÕÎËÃÉÊ ÉÚ ÏÐÒÅÄÅÌÅÎÉÑ 1 ÐÒÉÎÑÔÏ ÎÁÚ×ÁÔØ 2-ÕÎÉ×ÅÒÓÁÌØÎÙÍ ÓÅÍÅÊÓÔ×ÏÍ. åÓÌÉ × ÜÔÏÍ ÏÐÒÅÄÅÌÅÎÉÉ ÚÁÍÅÎÉÔØ ÐÁÒÙ ÚÎÁÞÅÎÉÊ $ x$ É $ y$ ÎÁ ÎÁÂÏÒÙ ÉÚ $ k$ ÚÎÁÞÅÎÉÊ, ÔÏ ÐÏÌÕÞÉÍ ÏÐÒÅÄÅÌÅÎÉÅ $ k$-ÕÎÉ×ÅÒÓÁÌØÎÏÇÏ ÓÅÍÅÊÓÔ×Á ÈÜÛ-ÆÕÎËÃÉÊ (ÓÍ., ÎÁÐÒÉÍÅÒ, [Ro]).

ìÅÍÍÁ Ï ËÏÍÐÏÚÉÃÉÉ [DeSY].  ðÕÓÔØ $ H_1$ É $ H_2$ -- 2-ÕÎÉ×ÅÒÓÁÌØÎÙÅ ÓÅÍÅÊÓÔ×Á ÈÜÛ-ÆÕÎËÃÉÊ, ÄÅÊÓÔ×ÕÀÝÉÈ ÉÚ $ C_1$ × $ C_2$ É ÉÚ $ C_2$ × $ C_3$ ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏ. ôÏÇÄÁ

$\displaystyle H=\{h=h_2\circ h_1\,\vert\,h_1\in H_1,\ h_2\in H_2\}, $

ÇÄÅ $ \circ$ ÏÂÏÚÎÁÞÁÅÔ ËÏÍÐÏÚÉÃÉÀ, Ñ×ÌÑÅÔÓÑ 2-ÕÎÉ×ÅÒÓÁÌØÎÙÍ ÓÅÍÅÊÓÔ×ÏÍ ÈÜÛ-ÆÕÎËÃÉÊ, ÄÅÊÓÔ×ÕÀÝÉÈ ÉÚ $ C_1$ × $ C_3$.

îÅËÏÔÏÒÙÅ ÉÚ ÍÎÏÇÏÞÉÓÌÅÎÎÙÈ ÐÒÉÍÅÒÏ× ÐÒÉÍÅÎÅÎÉÑ ÕÎÉ×ÅÒÓÁÌØÎÙÈ ÓÅÍÅÊÓÔ× ÈÜÛ-ÆÕÎËÃÉÊ × ÍÁÔÅÍÁÔÉËÅ ÍÏÖÎÏ ÎÁÊÔÉ × ÒÁÂÏÔÁÈ [CW], [Sip], [GS], [IZ], [Nis]. îÁÓ ÖÅ ÜÔÉ ÓÅÍÅÊÓÔ×Á ÉÎÔÅÒÅÓÕÀÔ × ÏÓÎÏ×ÎÏÍ ËÁË ÉÎÓÔÒÕÍÅÎÔ ÄÌÑ ÏÐÒÅÄÅÌÅÎÉÑ É ÐÏÓÔÒÏÅÎÉÑ ÓÅÍÅÊÓÔ× ÏÄÎÏÓÔÏÒÏÎÎÉÈ ÈÜÛ-ÆÕÎËÃÉÊ, ÒÁÓÓÍÁÔÒÉ×ÁÅÍÙÈ × ÓÌÅÄÕÀÝÅÍ ÐÏÄÒÁÚÄÅÌÅ.

ó ÐÒÉËÌÁÄÎÏÊ ÔÏÞËÉ ÚÒÅÎÉÑ ÕÎÉ×ÅÒÓÁÌØÎÙÅ ÓÅÍÅÊÓÔ×Á ÈÜÛ-ÆÕÎËÃÉÊ ÄÏÌÖÎÙ ÕÄÏ×ÌÅÔ×ÏÒÑÔØ ÎÅËÏÔÏÒÙÍ ÄÏÐÏÌÎÉÔÅÌØÎÙÍ ÔÒÅÂÏ×ÁÎÉÑÍ. ÷Ï-ÐÅÒ×ÙÈ, ÈÜÛ-ÆÕÎËÃÉÉ ÄÏÌÖÎÙ ÂÙÔØ ÜÆÆÅËÔÉ×ÎÏ ×ÙÞÉÓÌÉÍÙÍÉ. þÁÓÔÏ ÜÔÏ ÔÒÅÂÏ×ÁÎÉÅ ×ËÌÀÞÁÀÔ × ÏÐÒÅÄÅÌÅÎÉÅ ÕÎÉ×ÅÒÓÁÌØÎÏÇÏ ÓÅÍÅÊÓÔ×Á É ÆÏÒÍÁÌÉÚÕÀÔ ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏÍ. õ ËÁÖÄÏÊ ÈÜÛ-ÆÕÎËÃÉÉ $ h\in H$ ÉÍÅÅÔÓÑ ÄÏÓÔÁÔÏÞÎÏ ËÏÒÏÔËÏÅ ÏÐÉÓÁÎÉÅ $ \overline h$ É ÓÕÝÅÓÔ×ÕÀÔ Ä×Á ÜÆÆÅËÔÉ×ÎÙÈ ÁÌÇÏÒÉÔÍÁ, ÐÅÒ×ÙÊ ÉÚ ËÏÔÏÒÙÈ ÐÏ ÚÁÐÒÏÓÕ ×ÙÄÁÅÔ ÓÌÕÞÁÊÎÏÅ $ \overline h\in H$, Á ×ÔÏÒÏÊ ÐÏ $ \overline h$ É ÁÒÇÕÍÅÎÔÕ $ x$ ×ÙÞÉÓÌÑÅÔ $ h(x)$.

÷Ï-×ÔÏÒÙÈ, ×Ï ÍÎÏÇÉÈ ÓÌÕÞÁÑÈ ÔÒÅÂÕÀÔÓÑ ÓÅÍÅÊÓÔ×Á ÈÜÛ-ÆÕÎËÃÉÊ, ËÏÔÏÒÙÅ ÏÐÒÅÄÅÌÑÀÔÓÑ ÎÅ ÎÁ ÓÔÒÏËÁÈ ÔÏÌØËÏ ÄÁÎÎÏÊ ÆÉËÓÉÒÏ×ÁÎÎÏÊ ÄÌÉÎÙ, Á ÎÁ ÓÔÒÏËÁÈ ×ÓÅÈ ÄÌÉÎ (ÉÌÉ ÂÅÓËÏÎÅÞÎÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ ÄÌÉÎ). ÷ ÜÔÏÍ ÓÌÕÞÁÅ ÍÎÏÖÅÓÔ×Ï $ H_{n}$, ËÏÔÏÒÏÅ ÄÅÊÓÔ×ÕÅÔ ÓÏÇÌÁÓÎÏ ÏÐÒÅÄÅÌÅÎÉÀ 1 ÎÁ ÓÔÒÏËÁÈ ÄÌÉÎÙ $ n$, ÎÁÚÙ×ÁÀÔ ËÏÌÌÅËÃÉÅÊ ÈÜÛ-ÆÕÎËÃÉÊ, Á ÕÎÉ×ÅÒÓÁÌØÎÙÍ ÓÅÍÅÊÓÔ×ÏÍ ÎÁÚÙ×ÁÀÔ $ \{H_{n}\}$.

÷-ÔÒÅÔØÉÈ, ÄÌÑ ËÒÉÐÔÏÇÒÁÆÉÞÅÓËÉÈ ÐÒÉÌÏÖÅÎÉÊ ÉÎÏÇÄÁ ÔÒÅÂÕÅÔÓÑ ÔÁË ÎÁÚÙ×ÁÅÍÏÅ Ó×ÏÊÓÔ×Ï ÄÏÓÔÕÐÎÏÓÔÉ ËÏÌÌÉÚÉÊ (collision accessibility). ïÎÏ ÔÒÅÂÕÅÔ ÓÕÝÅÓÔ×Ï×ÁÎÉÑ ÜÆÆÅËÔÉ×ÎÏÇÏ ÁÌÇÏÒÉÔÍÁ, ËÏÔÏÒÙÊ ÐÏ ÄÁÎÎÙÍ $ x_{1}$ É $ x_{2}$ ×ÙÂÉÒÁÅÔ $ h\in H$ ÔÁËÕÀ, ÞÔÏ $ h(x_{1})=h(x_{2})$, ÒÁ×ÎÏ×ÅÒÏÑÔÎÙÍ ÏÂÒÁÚÏÍ ÓÒÅÄÉ ×ÓÅÈ ÆÕÎËÃÉÊ ÉÚ $ H$, ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÉÈ ÜÔÏÍÕ Ó×ÏÊÓÔ×Õ. îÁÏÒ É àÎÇ [NY] ÆÏÒÍÕÌÉÒÕÀÔ ÜÔÏ ÔÒÅÂÏ×ÁÎÉÅ ËÁË ÄÏÐÏÌÎÉÔÅÌØÎÏÅ. òÏÍÐÅÌØ [Ro] ×ËÌÀÞÁÅÔ ÎÅÓËÏÌØËÏ ÂÏÌÅÅ ÓÉÌØÎÏÅ ÔÒÅÂÏ×ÁÎÉÅ ÎÅÐÏÓÒÅÄÓÔ×ÅÎÎÏ × ÏÐÒÅÄÅÌÅÎÉÅ $ k$-ÕÎÉ×ÅÒÓÁÌØÎÏÇÏ ÓÅÍÅÊÓÔ×Á ÈÜÛ-ÆÕÎËÃÉÊ: ÓÕÝÅÓÔ×ÕÅÔ ÜÆÆÅËÔÉ×ÎÙÊ ÁÌÇÏÒÉÔÍ, ËÏÔÏÒÙÊ ÄÌÑ ÄÁÎÎÙÈ

$\displaystyle j\leqslant k,\quad x_{1},\ldots,x_{j}$   É$\displaystyle \quad y_{1},\ldots,y_{j}, $

ÇÄÅ ×ÓÅ $ x_{l}$ ÒÁÚÌÉÞÎÙ, ×ÙÂÉÒÁÅÔ ÒÁ×ÎÏ×ÅÒÏÑÔÎÙÍ ÏÂÒÁÚÏÍ ÓÒÅÄÉ ×ÓÅÈ ÆÕÎËÃÉÊ $ h_{i}$ ÔÁËÉÈ, ÞÔÏ $ h_{i}(x_{1})=y_{1},\ldots,h_{i}(x_{j})=y_{j}$.

åÓÔØ ÎÅÓËÏÌØËÏ ÈÏÒÏÛÏ ÉÚ×ÅÓÔÎÙÈ ÜÆÆÅËÔÉ×ÎÙÈ ÐÕÔÅÊ ÐÏÓÔÒÏÅÎÉÑ ÕÎÉ×ÅÒÓÁÌØÎÙÈ ÓÅÍÅÊÓÔ× ÈÜÛ-ÆÕÎËÃÉÊ. íÙ ÓÎÁÞÁÌÁ ÏÐÉÛÅÍ Ä×Å ËÏÎÓÔÒÕËÃÉÉ 2-ÕÎÉ×ÅÒÓÁÌØÎÙÈ ÓÅÍÅÊÓÔ×, × ËÁÖÄÏÊ ÉÚ ËÏÔÏÒÙÈ ÄÌÉÎÁ ÏÐÉÓÁÎÉÑ ÈÜÛ-ÆÕÎËÃÉÉ ÌÉÎÅÊÎÏ ÚÁ×ÉÓÉÔ ÏÔ ÄÌÉÎÙ ÏÐÉÓÁÎÉÑ ÜÌÅÍÅÎÔÁ ÉÚ ÏÂÌÁÓÔÉ ÏÐÒÅÄÅÌÅÎÉÑ ÍÎÏÖÅÓÔ×Á $ A$.

1. ðÕÓÔØ $ F$ -- ÐÒÏÉÚ×ÏÌØÎÏÅ ËÏÎÅÞÎÏÅ ÐÏÌÅ É $ A=B=F$. óÅÍÅÊÓÔ×Ï $ H$, ËÏÔÏÒÏÅ ÓÏÓÔÏÉÔ ÉÚ ×ÓÅÈ ÌÉÎÅÊÎÙÈ ÆÕÎËÃÉÊ ÎÁ $ F$, Ñ×ÌÑÅÔÓÑ 2-ÕÎÉ×ÅÒÓÁÌØÎÙÍ ÓÅÍÅÊÓÔ×ÏÍ ÈÜÛ-ÆÕÎËÃÉÊ. éÎÙÍÉ ÓÌÏ×ÁÍÉ,

$\displaystyle H=\{ax+b\,\vert\,a,b\in F\}, $

É ËÁÖÄÁÑ ÆÕÎËÃÉÑ $ h\in H$ ÏÐÒÅÄÅÌÑÅÔÓÑ ÅÄÉÎÓÔ×ÅÎÎÙÍ ÏÂÒÁÚÏÍ Ä×ÕÍÑ ÜÌÅÍÅÎÔÁÍÉ $ a$ É $ b$.

îÁÏÒ É àÎÇ [NY] ÉÓÐÏÌØÚÏ×ÁÌÉ ÓÌÅÄÕÀÝÕÀ ÍÏÄÉÆÉËÁÃÉÀ ÜÔÏÇÏ ÓÅÍÅÊÓÔ×Á. ðÕÓÔØ $ F=GF(2^{k})$ É $ \qopname\relax o{chop}\colon\{0,1\}^{k}\to\{0,1\}^{k-1}$ -- ÆÕÎËÃÉÑ, ËÏÔÏÒÁÑ ÐÒÏÓÔÏ ÏÔÂÒÁÓÙ×ÁÅÔ ÐÏÓÌÅÄÎÉÊ ÂÉÔ. ôÏÇÄÁ ÓÅÍÅÊÓÔ×Ï ÈÜÛ-ÆÕÎËÃÉÊ $ \{\qopname\relax o{chop}(ax+b)\}$ Ñ×ÌÑÅÔÓÑ 2-ÕÎÉ×ÅÒÓÁÌØÎÙÍ É ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ Ó×ÏÊÓÔ×Õ ÄÏÓÔÕÐÎÏÓÔÉ ËÏÌÌÉÚÉÊ.

2. ðÕÓÔØ $ A=\{0,1\}^{n}$ É $ B=\{0,1\}^{m}$. äÌÑ $ x\in\{0,1\}^{n}$ É $ y\in \{0,1\}^{n+m-1}$ ÏÐÒÅÄÅÌÉÍ ËÏÎ×ÏÌÀÃÉÀ $ y\circ x$ ÜÌÅÍÅÎÔÏ× $ y$ É $ x$ ËÁË ×ÅËÔÏÒ ÄÌÉÎÙ $ m$, $ i$-Ñ ËÏÏÒÄÉÎÁÔÁ ËÏÔÏÒÏÇÏ ÏÐÒÅÄÅÌÑÅÔÓÑ ÐÏ ÆÏÒÍÕÌÅ

$\displaystyle z_{i}=\sum_{j=1}^{n} x_{j}y_{i+j-1}\bmod2. $

ôÏÇÄÁ ÓÅÍÅÊÓÔ×Ï

$\displaystyle H=\{(a\circ x)\oplus b\,\vert\,a\in \{0,1\}^{n+m-1}, b\in \{0,1\}^{m}\} $

ÐÒÅÄÓÔÁ×ÌÑÅÔ ÓÏÂÏÊ ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÓÅÍÅÊÓÔ×Ï ÈÜÛ-ÆÕÎËÃÉÊ.

÷ ËÁÞÅÓÔ×Å ÐÒÉÍÅÒÁ $ k$-ÕÎÉ×ÅÒÓÁÌØÎÏÇÏ ÓÅÍÅÊÓÔ×Á ÈÜÛ-ÆÕÎËÃÉÊ ÍÏÖÎÏ ÐÒÅÄÌÏÖÉÔØ ÓÌÅÄÕÀÝÅÅ ÓÅÍÅÊÓÔ×Ï, ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÅÅ ÏÐÒÅÄÅÌÅÎÉÀ òÏÍÐÅÌÑ [Ro].

3. ðÕÓÔØ $ F=GF(2^{m})$, $ A=B=F$. óÅÍÅÊÓÔ×Ï

$\displaystyle H=\left\{\left.h_{a_{0},\ldots,a_{k-1}}(x)= a_{0}+a_{1}x+\ldots+a_{k-1}x^{k-1}\,\right\vert\, a_{0},\ldots, a_{k-1}\in F\right\} $

Ñ×ÌÑÅÔÓÑ $ k$-ÕÎÉ×ÅÒÓÁÌØÎÙÍ.

îÁËÏÎÅÃ, ÐÏÓÌÅÄÎÉÊ ÐÒÉÍÅÒ.

4. ðÕÓÔØ $ H_{n,m}$ -- ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ Ô£ÐÌÉÃÅ×ÙÈ ÍÁÔÒÉà ÒÁÚÍÅÒÁ $ m\times n$ ÎÁÄ $ GF(2)$. $ H_{n,m}$ Ñ×ÌÑÅÔÓÑ 2-ÕÎÉ×ÅÒÓÁÌØÎÙÍ ÓÅÍÅÊÓÔ×ÏÍ ÈÜÛ-ÆÕÎËÃÉÊ. ðÏÓËÏÌØËÕ ÜÌÅÍÅÎÔÙ Ô£ÐÌÉÃÅ×ÙÈ ÍÁÔÒÉà ÕÄÏ×ÌÅÔ×ÏÒÑÀÔ ÓÏÏÔÎÏÛÅÎÉÀ $ a_{i,j}=a_{i+1,j+1}$, ÔÁËÁÑ ÍÁÔÒÉÃÁ ÐÏÌÎÏÓÔØÀ ÏÐÒÅÄÅÌÑÅÔÓÑ Ó×ÏÉÍÉ ÐÅÒ×ÏÊ ÓÔÒÏËÏÊ É ÐÅÒ×ÙÍ ÓÔÏÌÂÃÏÍ. ðÏÜÔÏÍÕ ÏÐÉÓÁÎÉÅ ÈÜÛ-ÆÕÎËÃÉÉ ÉÍÅÅÔ ÄÌÉÎÕ $ o(n+m)$.

÷ÐÅÒÅÄ ÷×ÅÒÈ îÁÚÁÄ óÏÄÅÒÖÁÎÉÅ ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ
÷ÐÅÒÅÄ: 5.5.2 óÅÍÅÊÓÔ×Á ÏÄÎÏÓÔÏÒÏÎÎÉÈ ÈÜÛ-ÆÕÎËÃÉÊ ÷×ÅÒÈ: 5.5 ôÅÏÒÅÔÉÞÅÓËÉÅ ÁÓÐÅËÔÙ îÁÚÁÄ: 5.5 ôÅÏÒÅÔÉÞÅÓËÉÅ ÁÓÐÅËÔÙ   óÏÄÅÒÖÁÎÉÅ   ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ

ðÒÏÅËÔ ÏÓÕÝÅÓÔ×ÌÑÅÔÓÑ ÐÒÉ ÐÏÄÄÅÒÖËÅ:
 çÅÏÌÏÇÉÞÅÓËÏÇÏ ÆÁËÕÌØÔÅÔÁ íçõ,
òææé
    
TopList Rambler's Top100