В. Савченко - Анализ алиасов, страница 4

Èç îïðåäåëåíèÿ ρ∗ èìååì, ÷òî @ζ : ζ êîíñåðâàòèâåí è ϕρ∗ < ϕζ . Òîãäà ëèáî ϕξ è ϕρ∗ íåñðàâíèìû, ëèáîϕξ ≤ ϕρ∗ .Ïóñòü ϕξ è ϕρ∗ íåñðàâíèìû. Ðàññìîòðèì χ = ϕξ ◦ ϕρ∗ . Èç äîïîëíåíèÿ 2 ê òåîðåìå î êîìïîçèöèè êîíñåðâàòèâíûõ àíàëèçîâ àëèàñîâ χ êîíñåðâàòèâåí, ïðè÷åì ϕρ∗ < χ. Èç ëåììû 2 ñëåäóåò, ÷òî∃γ : γ = ξ ◦ ρ∗ è χ = ϕγ . Òî åñòü∃γ : γ êîíñåðâàòèâåí è ϕρ∗ < ϕγÝòî ïðîòèâîðå÷èò îïðåäåëåíèþ ρ∗ .Òîãäà îñòàåòñÿ, ÷òî ϕξ ≤ ϕρ∗ . Èç ëåììû 1 ïîëó÷àåì, ÷òî ξ ≤ ρ∗ .Äàííûå ðåçóëüòàòû ïîçâîëÿþò ðàáîòàòü èñêëþ÷èòåëüíî ñ àíàëèçîìóêàçàòåëåé è ãîâîðèòü îá èõ ñâîéñòâàõ âíå êîíòåêñòà àíàëèçà àëèàñîâ.Äàëåå, äëÿ êðàòêîñòè, â ñèòóàöèÿõ, êîãäà ïîäðàçóìåâàåòñÿ îäèí âûáðàííûé àíàëèç óêàçàòåëåé ξ , ∀p ∈ P áóäåì ïèñàòü Vp è èìåòü â âèäó,÷òî ξ(p) = Vp .5Êëàññè÷åñêèå ðåøåíèÿÂñå êëàññè÷åñêèå ðåøåíèÿ îòíîñÿòñÿ ê êàòåãîðèè ïîòîêîâî- è êîíòåêñòíîíå÷óâñòâèòåëüíûõ àíàëèçîâ.5.1Àëãîðèòì Àíäåðñåíà (94`)Ðàçðàáîòàí Ëàðñîì Óëå Àíäåðñåíîì è ïðåäñòàâëåí â ñîîòâåòñòâóþùåéðàáîòå â 1994-îì ãîäó.

Ñòîèò îòìåòèòü, ÷òî äàííûé ìåòîä ÿâëÿåòñÿ íàèáîëåå òî÷íûì ñðåäè òåõ, ÷òî ìîãóò áûòü ïîëó÷åíû çà ïîëèíîìèàëüíîåâðåìÿ.19Ïðè ðàññìîòðåíèè àëãîðèòìà áóäåì èñïîëüçîâàòü îðèåíòèðîâàííûéãðàô ñëåäóþùåãî âèäà: G =< V, E >, ãäå V = V , à E = {(p, a) : p ∈P, a ∈ Vp }.Òî åñòü â äàííîì ãðàôå âåðøèíû ïðåäñòàâëÿþò âñå ïåðåìåííûå ïðîãðàììû. Îò âåðøèíû p èìååòñÿ ðåáðî â âåðøèíó a, òîëüêî åñëè p ìîæåòóêàçûâàòü íà a.Îñíîâíûì îñòàåòñÿ âîïðîñ î òîì, êàê íà îñíîâàíèè êîäà ïðîãðàììûñîñòàâèòü àíàëèç óêàçàòåëåé.Àíäåðñåí âûäåëÿåò ñëåäóþùèå îïåðàöèè:• p = &a;• p = q;• p = *r;• *p = &a;• *p = q;• *p = *r;Âñå îñòàëüíûå îïåðàöèè ìîãóò áûòü ñâåäåíû ê äàííûì ñëó÷àÿì.Ïðèìåð 15.Íèæå ïðèâåäåí ïðèìåð òàêîãî ñâåäåíèÿ....t = *b;a = *t;......a = ** b ;...Ëèñòèíã 15: Äî ïðèâåäåíèÿ5.1.1Ëèñòèíã 16: ÏîñëåÏîñòðîåíèå àíàëèçà óêàçàòåëåéÒåïåðü ðàññìîòðèì êàê àíàëèçèðóåòñÿ êàæäûé òèï ïðèñâàèâàíèÿ. Äëÿáîëüøåé íàãëÿäíîñòè êàæäûé òèï ñðàçó æå ðàññìàòðèâàåòñÿ íà ïðèìåðå.1.

p = &a;Äîáàâëÿåì ðåáðî îò p ê a, ïîêàçûâàÿ, ÷òî a ∈ Vp .pa2. p = q;Äîáàâëÿåì ðåáðà îò p êî âñåì âåðøèíàì, êóäà åñòü ðåáðà èç q .Ýòî çíà÷èò òàêæå, ÷òî åñëè ïîçæå áóäóò äîáàâëåíû ðåáðà èç q ,àíàëîãè÷íûå ðåáðà äîëæíû áûòü äîáàâëåíû èç p. Òî åñòü äîëæíîñîõðàíÿòüñÿ ñâîéñòâî, ÷òî Vq ⊆ Vp .20paqbcÇäåñü è äàëåå ïóíêòèðîì îáîçíà÷åíû ðåáðà, êîòîðûå áûëè äîáàâëåíû ïîçæå.  äàííîì ñëó÷àå íà ìîìåíò îáðàáîòêè èíñòðóêöèèp = q; áûëî íåèçâåñòíî, ÷òî c ∈ Vq (èçìåíèëîñü Vq ).3. p = *r;SVt . Òîãäà äîáàâëÿåì ðåáðî èç p ê êàæäîìó ýëåìåíÏóñòü T =t∈Vròó èç T . Àíàëîãè÷íî ïðåäûäóùåìó ñëó÷àþ ïðè èçìåíåíèè Vr èëèT íåîáõîäèìî äîáàâèòü ñîîòâåòñòâóþùèå ðåáðà.

Òî åñòü äîëæíîñîõðàíÿòüñÿ ñâîéñòâî, ÷òî ∀t ∈ Vr ⇒ Vt ⊆ Vp .apdebfrc äàííîì ïðèìåðå ïóíêòèðîì âûäåëåíû ðåáðà (p, c) è (p, d), òàêêàê íà ìîìåíò îáðàáîòêè èíñòðóêöèè p = *r; áûëî íåèçâåñòíî, ÷òîd ∈ Ve (èçìåíèëîñü T ) è f ∈ Vr (èçìåíèëîñü Vr ).4. *p = &a;Èç êàæäîé âåðøèíû, êóäà åñòü ðåáðà èç p äîáàâëÿåì ðåáðî ê a.Îïÿòü òàêè, ïðè äîáàâëåíèè íîâûõ âåðøèí â Vp èç íèõ íåîáõîäèìî äîáàâèòü ðåáðà ê a. Òî åñòü äîëæíî ñîõðàíÿòüñÿ ñâîéñòâî, ÷òî∀t ∈ Vp → a ∈ Vt .pqar äàííîì ïðèìåðå ïóíêòèðîì âûäåëåíî ðåáðî (r, a), òàê êàê íàìîìåíò îáðàáîòêè áûëî íåèçâåñòíî, ÷òî r ∈ Vp (èçìåíèëîñü Vp ).215. *p = q;Èç êàæäîé âåðøèíû èç Vp äîáàâëÿåì ðåáðî ê êàæäîé âåðøèíå èçVq . Ïðè äîáàâëåíèè íîâûõ âåðøèí â Vp èëè â Vq ñîîòâåòñòâóþùèåíîâûå ðåáðà äîëæíû áûòü äîáàâëåíû.

Òî åñòü äîëæíî ñîõðàíÿòüñÿñâîéñòâî, ÷òî ∀t ∈ Vp → Vq ⊆ Vt .presfqc äàííîì ïðèìåðå ïóíêòèðîì âûäåëåíû ðåáðà (r, f ), (s, e) è (s, f ),òàê êàê íà ìîìåíò îáðàáîòêè èíñòðóêöèè *p = q; áûëî íåèçâåñòíî,÷òî s ∈ Vp (èçìåíèëîñü Vp ) è f ∈ Vq (èçìåíèëîñü Vq ).6. *p = *r;SÏóñòü T =Vt . Òîãäà íåîáõîäèìî äîáàâèòü ðåáðî èç êàæäîét∈Vrâåðøèíû èç Vp â êàæäóþ âåðøèíó èç T . Ïðè äîáàâëåíèè íîâûõâåðøèí â T , Vr èëè Vp ñîîòâåòñòâóþùèå ðåáðà äîëæíû áûòü äîáàâëåíû. Òî åñòü äîëæíî ñîõðàíÿòüñÿ ñâîéñòâî, ÷òî ∀s ∈ Vp , ∀t ∈Vr → Vt ⊆ Vs .puawdvbxrc äàííîì ïðèìåðå ïóíêòèðîì âûäåëåíû ðåáðà (u, d), (u, b), (v, a),(v, d) è (v, b), òàê êàê íà ìîìåíò îáðàáîòêè èíñòðóêöèè *p = *r; íåáûëî èçâåñòíî, ÷òî v ∈ Vp (èçìåíèëñÿ Vp ), x ∈ Vr (èçìåíèëñÿ Vr ) èb ∈ Vx (èçìåíèëñÿ T ).5.1.2Ðàçðåøåíèå îãðàíè÷åíèé ðàññìîòðåííûõ âûøå ðàçëè÷íûõ òèïàõ èíñòðóêöèé áûëè âûäåëåíûñâîéñòâà, êîòîðûå äîëæíû ñîõðàíÿòüñÿ.

Äàííûå ñâîéñòâà ïðèíÿòî íàçûâàòü îãðàíè÷åíèÿìè. Îñíîâíóþ ñëîæíîñòü â ïîñòðîåíèè àíàëèçà óêàçàòåëåé Àíäåðñåíà ñîñòàâëÿåò êàê ðàç ðàçðåøåíèå îãðàíè÷åíèé òàêîå,÷òîáû âñå îíè áûëè óäîâëåòâîðåíû.22Åùå ðàç ïåðå÷èñëèì âñå òèïû èíñòðóêöèé è îãðàíè÷åíèÿ èì ñîîòâåòñòâóþùèå:1. p = &a: a ∈ Vp2. p = q: Vp ⊇ Vq3. p = *r: ∀t ∈ Vr → Vt ⊆ Vp4. *p = &a: ∀t ∈ Vp → a ∈ Vt5. *p = q: ∀t ∈ Vp → Vq ⊆ Vt6. *p = *r: ∀s ∈ Vp , ∀t ∈ Vr ⇒ Vt ⊆ VsÎïðåäåëèì ôîðìàëüíî çàäà÷ó ïîñòðîåíèÿ àíàëèçà óêàçàòåëåé Àíäåðñåíà ξ .

Ïóñòü I - ìíîæåñòâî èíñòðóêöèé, êîòîðûå âëåêóò çà ñîáîéèçìåíåíèÿ ñîñòîÿíèé óêàçàòåëåé, ðàññìàòðèâàåìîé ïðîãðàììû 1 , à Λ- ôóíêöèÿ, ñîïîñòàâëÿþùàÿ êàæäîìó i ∈ I ïðåäèêàò ëîãèêè ïåðâîãîïîðÿäêà.Îïðåäåëåíèå 15. Îãðàíè÷åíèåì,Λ(i).Îïðåäåëåíèå 16. Àíàëèçïî Àíäåðñåíó 2 , åñëèñâÿçàííûì ñ i ∈ I , áóäåì íàçûâàòüóêàçàòåëåé ξ áóäåì íàçûâàòü ïîñòðîåííûì∀i ∈ I → Λ(i)(ξ)Òî åñòü ξ ïîñòðîåí ïî Àíäåðñåíó, åñëè âñå îãðàíè÷åíèÿ èñòèííû íàξ.Êàê ìîæíî ðàçðåøèòü âñå îãðàíè÷åíèÿ? Ìîæíî èòåðàòèâíî îáõîäèòüâñå èíñòðóêöèè è ïûòàòüñÿ ðàçðåøèòü êàæäîå îãðàíè÷åíèå ïî îòäåëüíîñòè. Åñëè çà îäèí òàêîé ïðîõîä íè÷åãî íå áûëî èçìåíåíî, òî âñå îãðàíè÷åíèÿ óäîâëåòâîðåíû è àíàëèç óêàçàòåëåé ïîñòðîåí. Îòîáðàçèì äàííîåðåøåíèå â ïñåâäîêîäå.Àëãîðèòì 1:(Àíäåðñåí)whilechanged dochanged ← f alse;foreach i ∈ I doif not Λ(i)(ξ) thensolve Λ(i)(ξ);changed ← true;endendend1Áóäåì ñ÷èòàòü, ÷òî â äàííîì ìíîæåñòâå âñå èíñòðóêöèè óæå ïðèâåäåíû ê áàçîâûìòèïàì2Íàðÿäó ñ ýòèì íàçâàíèåì èñïîëüçóåòñÿ òàêæå òåðìèí "àíàëèç óêàçàòåëåé ïîâêëþ÷åíèþ "(inclusion-based)23Øàã solve Λ(i)(ξ) îñóùåñòâëÿåòñÿ ïî ïðàâèëàì, îïèñàííûì â ðàçäåëå"Ïîñòðîåíèå àíàëèçà óêàçàòåëåé".5.1.3ÐåçóëüòàòûÊàê óæå ãîâîðèëîñü ðàíåå, ñðåäè àíàëèçîâ àëèàñîâ, êîòîðûå ìîãóò áûòüïîëó÷åíû çà ïîëèíîìèàëüíîå âðåìÿ, àíàëèç àëèàñîâ, ïîñòðîåííûé ïîÀíäåðñåíó, äàåò íàèëó÷øèé ðåçóëüòàò.

Íà ïðàêòèêå áûëî îòìå÷åíî, ÷òîðåçóëüòàòû ñèëüíî ïðåâîñõîäÿò ïî òî÷íîñòè àíàëèç ïî âçÿòèþ àäðåñà.Òàêæå áûëî îòìå÷åíî, ÷òî äîáàâëåíèå ïîòîêîâîé è êîíòåêñòíîé ÷óâñòâèòåëüíîñòè ëèøü íåçíà÷èòåëüíî óëó÷øàåò ðåçóëüòàò íà ðàñïðîñòðàíåííûõ áåí÷ìàðêàõ.Îäíàêî, àñèìïòîòè÷åñêàÿ ñëîæíîñòü äàííîãî ïîäõîäà O(n3 ), ãäå n =|V|, è â òîì âèäå, â êîòîðîì åãî ïðåäëîæèë Àíäåðñåí, àëãîðèòì áûëíåïðèìåíèì ê áîëüøèì ïðîãðàììíûì ïðîåêòàì èç-çà äîëãîãî âðåìåíèðàáîòû àëãîðèòìà è îãðîìíîãî ïîòðåáëåíèÿ ïàìÿòè (O(n2 )) 1 .5.2Àëãîðèòì Ñòèíñãàðäà (96`)Ðàçðàáîòàí Áüÿðíå Ñòèíñãàðäîì è ïðåäñòàâëåí â ñîîòâåòñòâóþùåé ðàáîòå â 1996-îì ãîäó.Ïðåæäå âñåãî àëãîðèòì Ñòèíñãàðäà ÿâëÿåòñÿ ïîïûòêîé ñóùåñòâåííî óëó÷øèòü àñèìïòîòè÷åñêóþ ñëîæíîñòü, æåðòâóÿ ïðè ýòîì òî÷íîñòüþàíàëèçà.5.2.1Ýêâèâàëåíòíîñòü ïåðåìåííûõÂâåäåì ïîíÿòèå ýêâèâàëåíòíîñòè äâóõ ïåðåìåííûõ.v, w ∈ V áóäåì íàçûâàòü ýêâèâàëåíòíûìè ïî ÀíäåðAè îáîçíà÷àòü v ∼ w, åñëè è òîëüêî åñëè Vv = Vw è ∀p ∈ P âåðíî,÷òî v ∈ Vp ⇔ w ∈ Vp .Îïðåäåëåíèå 17.ñåíóÓòâåðæäåíèå 4.

Ââåäåííîå îòíîøåíèåâèâàëåíòíîñòè íàA∼ ÿâëÿåòñÿ îòíîøåíèåì ýê-V , ò.å. âûïîëíÿþòñÿ ñëåäóþùèå ñâîéñòâà:1. Ðåôëåêñèâíîñòü:A∀a ∈ V → a ∼ a2. Ñèììåòðè÷íîñòü:3. Òðàíçèòèâíîñòü:AA∀a, b ∈ V → a ∼ b ⇒ b ∼ aAAA∀a, b, c ∈ V → a ∼ b, b ∼ c ⇒ a ∼ c1Äàííàÿ îöåíêà ëåãêî ïîêàçûâàåòñÿ, åñëè ðàññìàòðèâàòü çàäà÷ó íà ãðàôå. Äëÿïîëíîãî îðèåíòèðîâàííîãî ãðàôà íà n âåðøèíàõ èìååì n(n − 1) ðåáåð, ÷òî è äàåòàñèìïòîòè÷åñêóþ îöåíêó O(n2 ) ïàìÿòè äëÿ åãî õðàíåíèÿ24Äîêàçàòåëüñòâî äàííîãî óòâåðæäåíèÿ î÷åâèäíî è íàïðÿìóþ ñëåäóåòèç îïðåäåëåíèÿ îòíîøåíèÿ.AÏóñòü a ∈ V . Òîãäà ìíîæåñòâî ïåðåìåííûõ b ∈ V : a ∼ b íàçûâàåòñÿAêëàññîì ýêâèâàëåíòíîñòè a è îáîçíà÷àåòñÿ a/ ∼.AÌíîæåñòâî êëàññîâ ýêâèâàëåíòíîñòè ïî îòíîøåíèþ ∼ íàçûâàþò ôàêAòîð ìíîæåñòâîì è îáîçíà÷àþò V/ ∼.Òåîðåìà 5.

Ïóñòüζ - ïîñòðîåííûé ïî Àíäåðñåíó àíàëèç óêàçàòåëåé.AÅñëè íà ìíîæåñòâå V/ ∼ ïîñòðîèòü àíàëèç óêàçàòåëåé ïî Àíäåðñåíóξ , ïîíèìàÿ ïîä ýòèì, ÷òî i ∈ I âñÿêîå âõîæäåíèå ïðîèçâîëüíîé a ∈ Vïîíèìàåòñÿ êàê [a]A . Òîãäà ξ ñîâïàäàåò ñ ζ .Äëÿ äîêàçàòåëüñòâà òåîðåìû ïîêàæåì, ÷òî â îáîèõñëó÷àÿõ ïðè ïîñòðîåíèè ðåøàþòñÿ èäåíòè÷íûå îãðàíè÷åíèÿ. Íà âðåìÿäîêàçàòåëüñòâà ïîä a0 ìû ïîíèìàåì ïðîèçâîëüíóþ ïåðåìåííóþ èç [a]A .Äîêàçàòåëüñòâî.1. a ∈ ζ(p) è [a]A ∈ ξ([p]A ). Èç îïðåäåëåíèÿ ýêâèâàëåíòíîñòè a0 ∈ζ(p).  ñèëó ïðîèçâîëüíîñòè a0 âåðíî, ÷òî [a]A ⊆ ζ(p). Òàê êàêζ(p) = ζ(p0 ) è ýòî âåðíî äëÿ ïðîèçâîëüíîãî p0 , òî ζ ñîîòâåòñòâóåòîãðàíè÷åíèþ âèäà [a]A ∈ ξ([p]A ).2. ζ(p) ⊇ ζ(q) è ξ([p]A ) ⊆ ξ([q]A ). Èç îïðåäåëåíèÿ p0 è q 0 âåðíû ñëåäóþùèå âûðàæåíèÿ: ζ(p0 ) ⊇ ζ(q), ζ(p) ⊇ ζ(q 0 ), ζ(p0 ) ⊇ ζ(q 0 ).

Òîãäà ζñîîòâåòñòâóåò îãðàíè÷åíèþ âèäà ξ([p]A ) ⊆ ξ([q]A ).3. ∀t ∈ ζ(r) → ζ(t) ⊆ ζ(p) è ∀[t]A ∈ ξ([r]A ) → ξ([t]A ) ⊆ ξ([p]A ).Òàê êàê t ∈ ζ(r), òî t0 ∈ ζ(r). Òàê êàê ζ(r) = ζ(r0 ), ζ(t) = ζ(t0 )è ζ(p) = ζ(p0 ), òî t0 ∈ ζ(r0 ) → ζ(t0 ) ⊆ ζ(p0 ). Òàê êàê ýòî âûïîëíåíîäëÿ ïðîèçâîëüíûõ t0 , r0 è p0 , òî ζ ñîîòâåòñòâóåò îãðàíè÷åíèþ âèäà∀[t]A ∈ ξ([r]A ) → ξ([t]A ) ⊆ ξ([p]A ).Îñòàëüíûå ñëó÷àè äîêàçûâàþòñÿ àíàëîãè÷íî.Èñïîëüçîâàòü ýòî, îäíàêî, äëÿ óëó÷øåíèÿ ïðîèçâîäèòåëüíîñòè àëãîðèòìà íå ïîëó÷èòñÿ, òàê êàê îòíîøåíèå ýêâèâàëåíòíîñòè èñïîëüçóåòóæå ïîñòðîåííûé ïî Àíäåðñåíó àíàëèç óêàçàòåëåé.v, w ∈ V áóäåì íàçûâàòü ýêâèâàëåíòíûìè ïî Ñòèíñãàðäó è îáîçíà÷àòü v ∼ w , åñëè è òîëüêî åñëè ∃p ∈ P : v, w ∈ Vp .Îïðåäåëåíèå 18.SÓòâåðæäåíèå 5.

Ââåäåííîå îòíîøåíèåâèâàëåíòíîñòè íàS∼ ÿâëÿåòñÿ îòíîøåíèåì ýê-V.Àíàëèç óêàçàòåëåé ξ : P → 2V áóäåì íàçûâàòü ïîñòðîåííûì ïî Ñòèíñãàðäó, åñëè îí ïîëó÷åí ïóòåì ïîñòðîåíèÿ ïî ÀíÎïðåäåëåíèå 19.SSäåðñåíó àíàëèçà ζ : P/ ∼→ 2V/∼ .25Äëÿ äàííîãî îòíîøåíèÿ òàêæå âåðíî, ÷òî ðåçóëüòàòû àíàëèçà óêàçàòåëåé ó÷àñòâóþò ïðè ôîðìèðîâàíèè êëàññîâ ýêâèâàëåíòíîñòè. Íî âäàííîì ñëó÷àå âî âðåìÿ ïîñòðîåíèÿ àíàëèçà ìîæíî ñòðîèòü êëàññû ýêâèâàëåíòíîñòè "íà ëåòó". Åñëè ãîâîðèòü äðóãèìè ñëîâàìè, òî êàê òîëüêîñòàíîâèòñÿ èçâåñòíî, ÷òî a, b ∈ Vp äëÿ íåêîòîðîãî p, òî a è b îáúåäèíÿþòñÿ â êëàññ ýêâèâàëåíòíîñòè.5.2.2Ïîñòðîåíèå àíàëèçàÀëãîðèòì îòëè÷àåòñÿ îò àíàëîãè÷íîãî ó Àíäåðñåíà ëèøü òîé äåòàëüþ,÷òî åñëè âî âðåìÿ ðàçðåøåíèÿ îãðàíè÷åíèÿ íåîáõîäèìî (â òåðìèíàõ ãðàôà, ðàññìîòðåííîãî â ãëàâå ïðî àëãîðèòì Àíäåðñåíà) äîáàâèòü ðåáðî îòp ê b ïðè òîì, ÷òî èìååòñÿ ðåáðî ê a, òî âåðøèíû a è b ñëèâàþòñÿ.Ïóíêòèðîì îáîçíà÷åíî ðåáðî, êîòîðîå íåîáõîäèìî áûëîÏðèìåð 16.äîáàâèòü.papa,bbÀëãîðèòì 2:(Ñòèíñãàðä)whilechanged dochanged ← f alse;foreach i ∈ I doif not Λ(i)(ξ) thenΛ(i)(ξ);changed ← true;solve and mergeendendend5.2.3ÐåçóëüòàòûÀñèìïòîòè÷åñêàÿ ñëîæíîñòü ïîëó÷åííîãî àëãîðèòìà ñîñòàâëÿåòO(n ∗ α(n, n)) 1 .Òàêæå àíàëèç óêàçàòåëåé, ïîñòðîåííûé ïî Ñòèíñãàðäó, ïîêàçûâàåòðåçóëüòàòû çíà÷èòåëüíî ïðåâîñõîäÿùèå ïîäõîä ïî âçÿòèþ àäðåñà.1Çäåñü α(n, n) - îáðàòíàÿ ôóíêöèÿ Àêêåðìàíà.