Презентация (1157491), страница 2
Текст из файла (страница 2)
ðàçëè÷íûå ýëåìåíòûìàññèâà ñ÷èòàþòñÿ íåîòëè÷èìûìè.ÏîÿñíåíèåÄëÿ àíàëèçà ∀i ∈ Z+ ⇒ a[i] ≡ ∗aÎäíîèìåííûå ïîëÿ ðàçëè÷íûõ îáúåêòîâ ñ÷èòàþòñÿ àãðåãàòàìè.ÏîÿñíåíèåÏóñòüstruct Q { int x ; };(÷åðåç SQ ⊆ V áóäåì îáîçíà÷àòü ìíîæåñòâî ýëåìåíòîâ òèïà Q),òîãäà äëÿ àíàëèçà ∀s, t ∈ SQ ⇒ s.x ≡ t.xÈçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)19 / 67Ðàññìàòðèâàòü àëãîðèòì áóäåì óïðîùåííî è íà ïðèìåðàõ.Èçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)20 / 67Ðàññìàòðèâàòü àëãîðèòì áóäåì óïðîùåííî è íà ïðèìåðàõ.Âîçìîæíû ñëåäóþùèå øåñòü îñíîâíûõ îïåðàöèé:p = &a;p = q;p = *r;*p = &a;*p = q;*p = *r;Èçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)20 / 671. p = &a;Äîáàâëÿåì ðåáðî îò p ê a, ïîêàçûâàÿ, ÷òî a ∈ VppÈçâåñòíûå ðåøåíèÿaÀëãîðèòì Àíäåðñåíà (94`)21 / 671. p = &a;Äîáàâëÿåì ðåáðî îò p ê a, ïîêàçûâàÿ, ÷òî a ∈ Vppa2.
p = q;Äîáàâëÿåì ðåáðà îò p êî âñåì âåðøèíàì, êóäà åñòü ðåáðà èç q.Ýòî çíà÷èò òàêæå, ÷òî åñëè ïîçæå áóäóò äîáàâëåíû ðåáðà èç q,àíàëîãè÷íûå ðåáðà äîëæíû áûòü äîáàâëåíû èç p. Ò.å. äîëæíîñîõðàíÿòüñÿ ñâîéñòâî, ÷òî Vq ⊆ Vp.pabqcÈçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)21 / 673. p = *r;SÏóñòü r → Vr è T = Vt. Òîãäà äîáàâëÿåì ðåáðî èç p êt∈Vêàæäîìó ýëåìåíòó èç T . Àíàëîãè÷íî ïðåäûäóùåìó ñëó÷àþ ïðèèçìåíåíèè Vr èëè T íåîáõîäèìî äîáàâèòü ñîîòâåòñòâóþùèåðåáðà.
Ò.å. äîëæíî ñîõðàíÿòüñÿ ñâîéñòâî, ÷òî ∀t ∈ Vr ⇒ Vt ⊆ Vp.rapdebfrcÈçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)22 / 674. *p = &a;Èç êàæäîé âåðøèíû, êóäà åñòü ðåáðà èç p äîáàâëÿåì ðåáðî ê a.Îïÿòü òàêè, ïðè äîáàâëåíèè íîâûõ âåðøèí â Vp èç íèõíåîáõîäèìî äîáàâèòü ðåáðà ê a. Ò.å. äîëæíî ñîõðàíÿòüñÿñâîéñòâî, ÷òî ∀t ∈ Vp ⇒ a ∈ Vt.pqarÈçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)23 / 675. *p = q;Èç êàæäîé âåðøèíû èç Vp äîáàâëÿåì ðåáðî ê êàæäîé âåðøèíå èçVq .
Ïðè äîáàâëåíèè íîâûõ âåðøèí â Vp èëè â Vqñîîòâåòñòâóþùèå íîâûå ðåáðà äîëæíû áûòü äîáàâëåíû. Ò.å.äîëæíî ñîõðàíÿòüñÿ ñâîéñòâî, ÷òî ∀t ∈ Vp ⇒ Vq ⊆ Vt.presfqcÈçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)24 / 676. *p = *r; SÏóñòü T = Vt. Òîãäà íåîáõîäèìî äîáàâèòü ðåáðî èç êàæäîét∈Vâåðøèíû èç Vp â êàæäóþ âåðøèíó èç T . Ïðè äîáàâëåíèè íîâûõâåðøèí â Vp èëè T ñîîòâåòñòâóþùèå ðåáðà äîëæíû áûòüäîáàâëåíû. Ò.å. äîëæíî ñîõðàíÿòüñÿ ñâîéñòâî, ÷òî∀s ∈ Vp , ∀t ∈ Vr ⇒ Vt ⊆ Vs .puawrdvbxrcÈçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)25 / 67Ðåçóëüòàòû àíàëèçàÎïûò ïîêàçûâàåò, ÷òî àëãîðèòì Àíäåðñåíà ïðåäîñòàâëÿåòïîëåçíóþ èíôîðìàöèþ ñèëüíî ïðåâîñõîäÿùóþ`address-taken'ïîäõîä.Èçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)26 / 67Ðåçóëüòàòû àíàëèçàÎïûò ïîêàçûâàåò, ÷òî àëãîðèòì Àíäåðñåíà ïðåäîñòàâëÿåòïîëåçíóþ èíôîðìàöèþ ñèëüíî ïðåâîñõîäÿùóþ`address-taken'ïîäõîä.Èíòåðåñíûé ôàêòÎïûò òàêæå ïîêàçûâàåò, ÷òî äîáàâëåíèå ïîòîêîâîé è êîíòåêñòíîé÷óâñòâèòåëüíîñòè ëèøü íåçíà÷èòåëüíî óëó÷øàåò ðåçóëüòàòûàíàëèçà íà ðàñïðîñòðàíåííûõ áåí÷ìàðêàõ.Èçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)26 / 67Ëîæêà äåãòÿÏðîèçâîäèòåëüíîñòü àëãîðèòìà Àíäåðñåíà â ïåðâîíà÷àëüíîì åãîâèäå (èòåðàòèâíûé àëãîðèòì ðàçðåøåíèÿ îãðàíè÷åíèé)îñòàâëÿåò æåëàòü ëó÷øåãî, åñëè ãîâîðèòü î áîëüøèõïðîãðàììàõ.
Âðåìÿ èñïîëíåíèÿ àëãîðèòìà O(n3), ãäå n - ÷èñëîâåðøèí â ãðàôå (n ìîæíî îöåíèòü ñâåðõó, êàê |V |).Èçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)27 / 67Ëîæêà äåãòÿÏðîèçâîäèòåëüíîñòü àëãîðèòìà Àíäåðñåíà â ïåðâîíà÷àëüíîì åãîâèäå (èòåðàòèâíûé àëãîðèòì ðàçðåøåíèÿ îãðàíè÷åíèé)îñòàâëÿåò æåëàòü ëó÷øåãî, åñëè ãîâîðèòü î áîëüøèõïðîãðàììàõ. Âðåìÿ èñïîëíåíèÿ àëãîðèòìà O(n3), ãäå n - ÷èñëîâåðøèí â ãðàôå (n ìîæíî îöåíèòü ñâåðõó, êàê |V |).Íåñìîòðÿ íà çíà÷èòåëüíûå óñïåõè â óñêîðåíèè åãî ðàáîòû íàðåàëüíûõ ïðèëîæåíèÿõ â ïîñëåäíèå ãîäû, àñèìïòîòèêà âðåìåíèèñïîëíåíèÿ îñòàåòñÿ òîé æå.Èçâåñòíûå ðåøåíèÿÀëãîðèòì Àíäåðñåíà (94`)27 / 67Àëãîðèòì Ñòèíñãàðäà (96`)Ðàçðàáîòàí Áüÿðíå Ñòèíñãàðäîì è ïðåäñòàâëåí âñîîòâåòñòâóþùåé ðàáîòå â 1996-îì ãîäó.Èçâåñòíûå ðåøåíèÿÀëãîðèòì Ñòèíñãàðäà (96`)28 / 67Àëãîðèòì Ñòèíñãàðäà (96`)Ðàçðàáîòàí Áüÿðíå Ñòèíñãàðäîì è ïðåäñòàâëåí âñîîòâåòñòâóþùåé ðàáîòå â 1996-îì ãîäó.Ïîòîêîâî- è êîíòåêñòíî-íå÷óâñòâèòåëüíûéÈçâåñòíûå ðåøåíèÿÀëãîðèòì Ñòèíñãàðäà (96`)28 / 67Àëãîðèòì Ñòèíñãàðäà (96`)Ðàçðàáîòàí Áüÿðíå Ñòèíñãàðäîì è ïðåäñòàâëåí âñîîòâåòñòâóþùåé ðàáîòå â 1996-îì ãîäó.Ïîòîêîâî- è êîíòåêñòíî-íå÷óâñòâèòåëüíûéÐàáîòàåò ïðàêòè÷åñêè çà ëèíåéíîå âðåìÿ (O(n ∗ α(n, n)), ãäåα(n, n) - îáðàòíàÿ ôóíêöèÿ Àêêåðìàíà)Èçâåñòíûå ðåøåíèÿÀëãîðèòì Ñòèíñãàðäà (96`)28 / 67Îñíîâíàÿ èäåÿÂåðøèíû a, b ∈ V áóäóò ïðåäñòàâëåíû îäíîé âåðøèíîé â ãðàôå,åñëè ∃p ∈ P : a, b ∈ Vp.Èçâåñòíûå ðåøåíèÿÀëãîðèòì Ñòèíñãàðäà (96`)29 / 67Îñíîâíàÿ èäåÿÂåðøèíû a, b ∈ V áóäóò ïðåäñòàâëåíû îäíîé âåðøèíîé â ãðàôå,åñëè ∃p ∈ P : a, b ∈ Vp.Òîãäà â ñðàâíåíèè ñ àëãîðèòìîì Àíäåðñåíà ïîëó÷àåì:Àíäåðñåí:pabÈçâåñòíûå ðåøåíèÿÑòèíñãàðä:pÀëãîðèòì Ñòèíñãàðäà (96`)a,b29 / 67Î÷åâèäíûì ÿâëÿåòñÿ òîãäà ôàêò òîãî, ÷òî ðåçóëüòàòû ïîäõîäàÑòèíñãàðäà óñòóïàþò ïî òî÷íîñòè ðåçóëüòàòàì àëãîðèòìàÀíäåðñåíà.Èçâåñòíûå ðåøåíèÿÀëãîðèòì Ñòèíñãàðäà (96`)30 / 67Î÷åâèäíûì ÿâëÿåòñÿ òîãäà ôàêò òîãî, ÷òî ðåçóëüòàòû ïîäõîäàÑòèíñãàðäà óñòóïàþò ïî òî÷íîñòè ðåçóëüòàòàì àëãîðèòìàÀíäåðñåíà.Ïðèìåð:Àíäåðñåí:pabÈçâåñòíûå ðåøåíèÿÑòèíñãàðä:qpqa,bÀëãîðèòì Ñòèíñãàðäà (96`)30 / 67Ðàçíèöà ñ àëãîðèòìîì Àíäåðñåíà íà ïðàêòèêåÃîðâèö è Øàïèðî ïðîòåñòèðîâàëè 61 ïðîãðàììó íà C ñðàçìåðàìè îò 300 äî 24 300 ñòðîê êîäàÈçâåñòíûå ðåøåíèÿÀëãîðèòì Ñòèíñãàðäà (96`)31 / 67Ðàçíèöà ñ àëãîðèòìîì Àíäåðñåíà íà ïðàêòèêåÃîðâèö è Øàïèðî ïðîòåñòèðîâàëè 61 ïðîãðàììó íà C ñðàçìåðàìè îò 300 äî 24 300 ñòðîê êîäàÑòèíñãàðä ìåíåå òî÷åí - â ñðåäíåì ðàçìåð ìíîæåñòâ â 4ðàçà áîëüøå; â õóäøåì ñëó÷àå â 15 ðàçÈçâåñòíûå ðåøåíèÿÀëãîðèòì Ñòèíñãàðäà (96`)31 / 67Ðàçíèöà ñ àëãîðèòìîì Àíäåðñåíà íà ïðàêòèêåÃîðâèö è Øàïèðî ïðîòåñòèðîâàëè 61 ïðîãðàììó íà C ñðàçìåðàìè îò 300 äî 24 300 ñòðîê êîäàÑòèíñãàðä ìåíåå òî÷åí - â ñðåäíåì ðàçìåð ìíîæåñòâ â 4ðàçà áîëüøå; â õóäøåì ñëó÷àå â 15 ðàçÀíäåðñåí ìåäëåííåå - â ñðåäíåì â ïîëòîðà ðàçà ìåäëåííåå; âõóäøåì ñëó÷àå â 31 ðàçÈçâåñòíûå ðåøåíèÿÀëãîðèòì Ñòèíñãàðäà (96`)31 / 67Ðàçíèöà ñ àëãîðèòìîì Àíäåðñåíà íà ïðàêòèêåÃîðâèö è Øàïèðî ïðîòåñòèðîâàëè 61 ïðîãðàììó íà C ñðàçìåðàìè îò 300 äî 24 300 ñòðîê êîäàÑòèíñãàðä ìåíåå òî÷åí - â ñðåäíåì ðàçìåð ìíîæåñòâ â 4ðàçà áîëüøå; â õóäøåì ñëó÷àå â 15 ðàçÀíäåðñåí ìåäëåííåå - â ñðåäíåì â ïîëòîðà ðàçà ìåäëåííåå; âõóäøåì ñëó÷àå â 31 ðàçÂûâîäÍåîáõîäèìî èñïîëüçîâàòü Àíäåðñåíà äëÿ íåáîëüøèõ ïðîãðàìì, àÑòèíñãàðäà äëÿ áîëüøèõ.Èçâåñòíûå ðåøåíèÿÀëãîðèòì Ñòèíñãàðäà (96`)31 / 67Ïîäõîä Ãîðâèö-Øàïèðî (97`)Ðàçðàáîòàí Ñþçàí Ãîðâèö è Ìàðêîì Øàïèðî è ïðåäñòàâëåí âñîîòâåòñòâóþùåé ðàáîòå â 1997-îì ãîäó.Ïîäõîä ïðåäñòàâëÿåò ñîáîé ñïîñîá ïîëó÷èòü ïðîìåæóòî÷íûåçâåíüÿ ìåæäó ïîäõîäàìè Àíäåðñåíà è Ñòèíñãàðäà.Èçâåñòíûå ðåøåíèÿÏîäõîä Ãîðâèö-Øàïèðî (97`)32 / 67Êîëè÷åñòâî èñõîäÿùèõ ðåáåð â ãðàôå áóäåì íàçûâàòü ñòåïåíüþâåðøèíû.Îñíîâíàÿ èäåÿÌîæíî îãðàíè÷èòü ñòåïåíü âåðøèí â ãðàôå íåêèì k (1 ≤ k ≤ n).Ïðè äîñòèæåíèè îãðàíè÷åíèÿ âñå ïîñëåäóþùèå âåðøèíûîáúåäèíÿþòñÿ ñ âåðøèíàìè, ê êîòîðûì óæå åñòü ðåáðà.Èçâåñòíûå ðåøåíèÿÏîäõîä Ãîðâèö-Øàïèðî (97`)33 / 67Êîëè÷åñòâî èñõîäÿùèõ ðåáåð â ãðàôå áóäåì íàçûâàòü ñòåïåíüþâåðøèíû.Îñíîâíàÿ èäåÿÌîæíî îãðàíè÷èòü ñòåïåíü âåðøèí â ãðàôå íåêèì k (1 ≤ k ≤ n).Ïðè äîñòèæåíèè îãðàíè÷åíèÿ âñå ïîñëåäóþùèå âåðøèíûîáúåäèíÿþòñÿ ñ âåðøèíàìè, ê êîòîðûì óæå åñòü ðåáðà.Òîãäà ïðè k = 1 ïîëó÷àåì ïîäõîä Ñòèíñãàðäà.Ïðè k = n ïîëó÷àåì ïîäõîä Àíäåðñåíà.Ïðè ýòîì èòîãîâàÿ ñëîæíîñòü àëãîðèòìà áóäåò ñîñòàâëÿòüO(k 2 n).Èçâåñòíûå ðåøåíèÿÏîäõîä Ãîðâèö-Øàïèðî (97`)33 / 67Ïðèìåðp1p1p1p2====&a;&b;&c;&c;Ïóñòü k = 2 è a, b ñîîòâåòñòâóþò ïåðâîé êàòåãîðèè, à c âòîðîé.Òîãäàp1a,bp2Èçâåñòíûå ðåøåíèÿcÏîäõîä Ãîðâèö-Øàïèðî (97`)34 / 67Ïðèìåðp1p1p1p2====&a;&b;&c;&c;Ïóñòü k = 2 è a, b ñîîòâåòñòâóþò ïåðâîé êàòåãîðèè, à c âòîðîé.Òîãäàp1a,bp2c äàííîì ñëó÷àå òî÷íîñòü àíàëèçà ñîîòâåòñòâóåò àëãîðèòìóÀíäåðñåíà.Èçâåñòíûå ðåøåíèÿÏîäõîä Ãîðâèö-Øàïèðî (97`)34 / 67ÏðèìåðÎäíàêî...Åñëè æå ìû îòíåñåì a ê ïåðâîé êàòåãîðèè, à b, c êî âòîðîé, òîïîëó÷èìp1ap2b,c äàííîì ñëó÷àå ìû ïîòåðÿëè â òî÷íîñòè, ò.ê.
ðåçóëüòàò ãîâîðèò,÷òî b ∈ Vp2.Èçâåñòíûå ðåøåíèÿÏîäõîä Ãîðâèö-Øàïèðî (97`)35 / 67Ìîäèôèêàöèÿ ïîäõîäàÍî, êàê âèäíî èç ïðåäûäóùåãî ïðèìåðà, ñ äâóìÿ ðàçëè÷íûìèâûáîðàìè êàòåãîðèé ìîæíî ïîëó÷èòü áîëåå òî÷íûé îòâåò.Èçâåñòíûå ðåøåíèÿÏîäõîä Ãîðâèö-Øàïèðî (97`)36 / 67Ìîäèôèêàöèÿ ïîäõîäàÍî, êàê âèäíî èç ïðåäûäóùåãî ïðèìåðà, ñ äâóìÿ ðàçëè÷íûìèâûáîðàìè êàòåãîðèé ìîæíî ïîëó÷èòü áîëåå òî÷íûé îòâåò.ÈäåÿÇàïóñêàòü àíàëèç íåñêîëüêî ðàç.Èçâåñòíûå ðåøåíèÿÏîäõîä Ãîðâèö-Øàïèðî (97`)36 / 67Ìîäèôèêàöèÿ ïîäõîäàÍî, êàê âèäíî èç ïðåäûäóùåãî ïðèìåðà, ñ äâóìÿ ðàçëè÷íûìèâûáîðàìè êàòåãîðèé ìîæíî ïîëó÷èòü áîëåå òî÷íûé îòâåò.ÈäåÿÇàïóñêàòü àíàëèç íåñêîëüêî ðàç.Ïóñòü p → Vpi, ãäå i - íîìåð çàïóñêà àíàëèçà. Òîãäà, ó÷èòûâàÿ,÷òî êàæäûé èç àíàëèçîâ íà âûõîäå èìååòTêîíñåðâàòèâíûåðåçóëüòàòû, ìîæíî óòâåðæäàòü, ÷òî p → Vpi òàêæå ÿâëÿåòñÿiêîíñåðâàòèâíûì ðåçóëüòàòîì.Èçâåñòíûå ðåøåíèÿÏîäõîä Ãîðâèö-Øàïèðî (97`)36 / 67Êàê è ñêîëüêî?Ãëàâíûå âîïðîñû, îñòàâøèåñÿ â äàííîì ïîäõîäå:Êàê âûáèðàòü êàòåãîðèè â ðàçëè÷íûõ çàïóñêàõ?Ñêîëüêî çàïóñêîâ ñòîèò äåëàòü?Èçâåñòíûå ðåøåíèÿÏîäõîä Ãîðâèö-Øàïèðî (97`)37 / 67Êàê è ñêîëüêî?Ãëàâíûå âîïðîñû, îñòàâøèåñÿ â äàííîì ïîäõîäå:Êàê âûáèðàòü êàòåãîðèè â ðàçëè÷íûõ çàïóñêàõ?Ñêîëüêî çàïóñêîâ ñòîèò äåëàòü?ÒðåáîâàíèåÍåîáõîäèìî òàê ïîäîáðàòü êàòåãîðèè è êîëè÷åñòâî çàïóñêîâ,÷òîáû êàæäàÿ ïàðà ïåðåìåííûõ õîòÿ áû ðàç ïîïàëà â ðàçëè÷íûåêàòåãîðèè.Èçâåñòíûå ðåøåíèÿÏîäõîä Ãîðâèö-Øàïèðî (97`)37 / 67Äëÿ äàííîé öåëè ìîæíî ïåðåíóìåðîâàòü êàæäóþ ïåðåìåííóþ ïîîñíîâàíèþ k.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
