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

ïåðåìíîæåíèå äâóõ ìàòðèö ðàçìåðà 5½5. Åñëè ðàçìåð ìàòðèöû
óâåëè÷èòü â 10 ðàç, òî âðåìÿ ñ÷åòà óâåëè÷èòñÿ â 1000 ðàç.
     Åñëè òðóäîåìêîñòü àëãîðèòìà îöåíèâàåòñÿ ïîëèíîìîì (ìíî-
ãî÷ëåíîì) îò ðàçìåðîâ çàäà÷è, òî òàêèå àëãîðèòìû íàçûâàþòñÿ
ïîëèíîìèàëüíûìè. Ïðè íàëè÷èè ïîëèíîìèàëüíîãî àëãîðèòìà ïðàê-
òè÷åñêè íà êîìïüþòåðå ìîæíî ðåøèòü çàäà÷ó ëþáûõ ðàçìåðîâ.
Îñíîâíàÿ òðóäíîñòü — ïîëó÷èòü äàííûå è ââåñòè èõ â êîìïüþòåð.
           Î íåâîçìîæíîñòè áîëüøîãî ïåðåáîðà
      Êîìïüþòåðû ðàáîòàþò î÷åíü áûñòðî, è ñ êàæäûì ãîäîì èõ
áûñòðîäåéñòâèå óâåëè÷èâàåòñÿ. Óâåëè÷åíèå ñêîðîñòè ðàáîòû êîì-
ïüþòåðà ïðèâîäèò ê íàäåæäå, ÷òî êîìïüþòåð ìîæåò ðåøèòü ëþ-
áûå çàäà÷è. Íàñêîëüêî îáîñíîâàí ýòîò îïòèìèçì?
      Áûñòðîäåéñòâèå êîìïüþòåðîâ íå áåñïðåäåëüíî. Ñîâðåìåí-
íàÿ ôèçèêà ñ÷èòàåò, ÷òî íèêàêîé ïðîöåññ íå ìîæåò ïðîòåêàòü
áûñòðåå ñêîðîñòè ñâåòà 3·1010 ñì/ñ. Åñëè äëÿ ñîâåðøåíèÿ îäíîé
îïåðàöèè õîòÿ áû îäèí ýëåêòðîí äîëæåí ïåðåäâèíóòüñÿ íà ðàñ-
ñòîÿíèå äèàìåòðà àòîìà âîäîðîäà (1 àíãñòðåì = 10-8 ñì), òî âðåìÿ
âûïîëíåíèÿ îïåðàöèè íå ìåíüøå ÷åì (ðàññòîÿíèå äåëèì íà ñêî-
ðîñòü) 3·10-19 ñ. Ïîýòîìó áûñòðîäåéñòâèå êîìïüþòåðà íå ìîæåò
áûòü áîëüøå 3·1018 îï./ñ.
      Ðàññìîòðèì ïðèìåð. Ïóñòü äâå áðèãàäû äîëæíû âûïîëíèòü
100 ðàáîò. Êàê ðàñïðåäåëèòü ýòè ðàáîòû ìåæäó äâóìÿ áðèãàäàìè?
Âûïîëíåíèå ëþáîé ðàáîòû ìîæíî äîâåðèòü ëþáîé èç áðèãàä.
Ïóñòü ìû ðàçðàáîòàëè àëãîðèòì, è êîìïüþòåð äëÿ ëþáîãî ðàñ-
ïðåäåëåíèÿ ðàáîò ìîæåò îïðåäåëèòü, âîçìîæíî ëè òàêîå ðàñïðå-
äåëåíèå ðàáîò, à òàêæå óìååò ñðàâíèâàòü ðàçëè÷íûå âàðèàíòû.
Ìîæíî ëè ïîëó÷èòü ëó÷øèé âàðèàíò, ðàññìîòðåâ âñå âîçìîæíûå
âàðèàíòû?
      Î÷åâèäíî, ÷òî îáùåå ÷èñëî ýòèõ ñïîñîáîâ ðàñïðåäåëèòü 100
ðàáîò ìåæäó 2 áðèãàäàìè ðàâíî 2100. Îöåíèì ýòó âåëè÷èíó.
210 ≈ 1000, 2100 ≈ 1030. Ïðè áûñòðîäåéñòâèè 1018 îï./ñ êîìïüþòåðó
ïîòðåáóåòñÿ 1012 ñ > 1010 ìèí >108 ÷ > 104 ëåò. Òàêèì îáðàçîì,
ïåðåáðàòü âñå âàðèàíòû ìû íå ñìîæåì.
      Áûñòðîäåéñòâèå êîìïüþòåðà ìîæíî óâåëè÷èòü çà ñ÷åò îäíî-
âðåìåííîãî âûïîëíåíèÿ àëãîðèòìà íà íåñêîëüêèõ êîìïüþòåðàõ.
Ïðåäïîëîæèì, ÷òî îäèí êîìïüþòåð èìååò áûñòðîäåéñòâèå 1018
îï./ñ è îáúåì 1 ñì3. Èç òàêèõ êîìïüþòåðîâ ñäåëàí ñóïåðêîìïüþ-


                               10