Математические методы в экономике. Копылов Г.Н - 9 стр.

ñòâåííî îòëè÷àòüñÿ. Åñëè, íàïðèìåð, ïñèõîëîã èçó÷àåò îòíîøå-
íèÿ â êîëëåêòèâå, òî îí ìîæåò ïîñòðîèòü ãðàô, â êîòîðîì âåð-
øèíû — ýòî ëþäè, à ðåáðà ñîåäèíÿþò äðóçåé.  ýòîì ñëó÷àå ó íàñ
íåîðèåíòèðîâàííûé ãðàô. Åñëè æå ðàññìîòðåòü ãðàô çíàêîìñòâ,
òî åñòü âåðøèíû ãðàôà ëþäè, à äóãà èäåò îò À ê Â, åñëè À çíàåò
Â, òî òàêîé ãðàô âî ìíîãèõ ñëó÷àÿõ íàäî ðàññìàòðèâàòü îðèåíòè-
ðîâàííûì. Íàïðèìåð, âñå ñòóäåíòû óíèâåðñèòåòà çíàþò, êòî â
óíèâåðñèòåòå ðåêòîð è êòî â ñòðàíå ïðåçèäåíò, íî ðåêòîð íå
ìîæåò çíàòü âñåõ ñòóäåíòîâ, à ïðåçèäåíò Ðîññèè íå ìîæåò çíàòü
âñåõ æèòåëåé. ×àñòî îðèåíòàöèÿ ãðàôà ñâÿçàíà ñ ïåðåâîçêîé òî-
âàðîâ. Èçó÷àÿ ãðóçîïîòîêè òîâàðîâ, ìîæíî ïîñòðîèòü ãðàô, ãäå
âåðøèíû — ïðîèçâîäèòåëè è ïîòðåáèòåëè òîâàðîâ, à ñòðåëêè
óêàçûâàþò ïåðåâîçêè òîâàðîâ. Îòìåòèì, ÷òî â ýòèõ ñëó÷àÿõ ãðàô
âîçìîæíûõ ïåðåâîçîê ÷àñòî ÿâëÿåòñÿ íåîðèåíòèðîâàííûì, íî
ãðàô ðåàëüíî îñóùåñòâëÿåìûõ ïåðåâîçîê îáÿçàòåëüíî îðèåíòè-
ðîâàííûé.
               Î òðóäîåìêîñòè àëãîðèòìîâ
      Âàæíîé õàðàêòåðèñòèêîé àëãîðèòìîâ ÿâëÿåòñÿ èõ òðóäîåì-
êîñòü, òî åñòü ÷èñëî ýëåìåíòàðíûõ îïåðàöèé, íåîáõîäèìûõ äëÿ
ðåøåíèÿ çàäà÷è ýòèì àëãîðèòìîì.
      Ðàññìîòðèì ïðèìåð. Ìîæíî ëè ïåøêîì äîéòè îò Âîëãîãðàäà
äî Ìîñêâû? Àëãîðèòì ðåøåíèÿ çàäà÷è î÷åíü ïðîñò: ñäåëàé øàã
ïðàâîé íîãîé, ñäåëàé øàã ëåâîé íîãîé; òàê ïîñòóïàé äî òåõ ïîð,
ïîêà çàäà÷à íå áóäåò ðåøåíà.
      Àëãîðèòì ïðîñòîé, íî ÷èñëî øàãîâ (êàê àëãîðèòìà, òàê è
åãî èñïîëíèòåëÿ) î÷åíü âåëèêî. Ïîýòîìó ýòîò àëãîðèòì âðÿä ëè
áóäåò ïðèìåíåí íà ïðàêòèêå. Çàäà÷à ïðàêòè÷åñêè íåðàçðåøèìà.
      Ðàññìîòðèì äðóãîé ïðèìåð. Ïóñòü ñòóäåíò ïîòðàòèë ÷àñ íà
ïåðåìíîæåíèå äâóõ ìàòðèö ðàçìåðà 5½5. Ñêîëüêî ïðèìåðíî âðå-
ìåíè åìó ïîíàäîáèòñÿ íà ïåðåìíîæåíèå äâóõ ìàòðèö ðàçìåðà
10½10? Òðóäîåìêîñòü T(n) ñòàíäàðòíîãî àëãîðèòìà ðàñòåò êàê Ñn3.
Çäåñü n — ðàçìåð ìàòðèöû, C — êîíñòàíòà, êîòîðàÿ íå çàâèñèò îò
n. Ïðè ïåðåõîäå îò 5 äî 10 ðàçìåðû ìàòðèöû óâåëè÷èëèñü â äâà
ðàçà. Ïîýòîìó íà ïåðåìíîæåíèå äâóõ ìàòðèö ðàçìåðà 10½10 ñòó-
äåíò ïîòðàòèò â 8 ðàç áîëüøå âðåìåíè, òî åñòü ïðèìåðíî 8 ÷àñîâ.
Åñëè îí ïðèìåíèò êîìïüþòåð, òî ýòî èçìåíèò âåëè÷èíó C, íî
âñå ðàâíî (åñëè íå èçìåíèòü àëãîðèòì), ïåðåìíîæåíèå äâóõ ìàò-
ðèö ðàçìåðà 10½10 çàéìåò ó íåãî â 8 ðàç áîëüøå âðåìåíè, ÷åì

                               9