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

UptoLike

ВУЗ: 

ВолГУ | Волгоград

Составители: 

Рубрика: 

11
òåð ðàçìåðîì ñ Çåìíîé øàð. Êàêîâî áûñòðîäåéñòâèå òàêîãî ñóïåð-
êîìïüþòåðà? Îáúåì Çåìëè V = 4πR
3
/3. R = 6400 êì = 2
6
·100 êì =
2
6
·10
7
ñì. Ïîýòîìó V≈ 4·(2
6
·10
7
ñì)
3
= 2
20
·10
21
ñì
3
≈ 10
27
ñì
3
. Ïîýòîìó
òàêîé ñóïåðêîìïüþòåð ìîæåò ñäåëàòü 10
18
·10
27
= 10
45
îï./ñ. Ýòî,
êîíå÷íî, î÷åíü ìíîãî. Íî âñåãäà ëè äîñòàòî÷íî?
Ïóñòü èç Âîëãîãðàäà â ñòîðîíó Ñàðàòîâà îòïðàâëÿåòñÿ òî-
âàðíûé ïîåçä. Â íåì îêîëî 50 âàãîíîâ. Ìû õîòèì ñôîðìèðîâàòü
ñîñòàâ, âûáðàâ îïòèìàëüíûé ïîðÿäîê âàãîíîâ. Îáùåå ÷èñëî âà-
ðèàíòîâ 50!≈10
65
. Ïðè áûñòðîäåéñòâèè 10
45
îï/ñ êîìïüþòåðó ïî-
òðåáóåòñÿ 10
65
/10
45
= 10
20
ñ > 10
18
ìèí >10
16
÷ > 10
12
ëåò. Òàêèì
îáðàçîì, ïåðåáðàòü âñå âàðèàíòû ìû íå ñìîæåì è íà òàêîì ñó-
ïåðêîìïüþòåðå.
Ïîäâåäåì èòîãè. Âàæíîé õàðàêòåðèñòèêîé àëãîðèòìà ÿâëÿ-
åòñÿ åãî òðóäîåìêîñòü. Åñëè òðóäîåìêîñòü êàêîãî-ëèáî àëãîðèòìà
ðàñòåò êàê ïîëèíîì (ìíîãî÷ëåí) îò ðàçìåðîâ çàäà÷è, òî ðåøèòü
çàäà÷ó ìîæíî ïðàêòè÷åñêè äëÿ ëþáîé ðàçìåðíîñòè. Åñëè æå òðó-
äîåìêîñòü êàêîãî-ëèáî àëãîðèòìà ðàñòåò êàê 2
n
èëè n!, òî ïðè
áîëüøèõ n ïðèìåíåíèå ýòîãî àëãîðèòìà ïðàêòè÷åñêè íåâîçìîæíî.
òåð ðàçìåðîì ñ Çåìíîé øàð. Êàêîâî áûñòðîäåéñòâèå òàêîãî ñóïåð-
êîìïüþòåðà? Îáúåì Çåìëè V = 4πR3/3. R = 6400 êì = 26·100 êì =
26·107 ñì. Ïîýòîìó V≈ 4·(26·107ñì)3 = 220·1021 ñì3 ≈ 1027 ñì3. Ïîýòîìó
òàêîé ñóïåðêîìïüþòåð ìîæåò ñäåëàòü 1018·1027 = 1045 îï./ñ. Ýòî,
êîíå÷íî, î÷åíü ìíîãî. Íî âñåãäà ëè äîñòàòî÷íî?
      Ïóñòü èç Âîëãîãðàäà â ñòîðîíó Ñàðàòîâà îòïðàâëÿåòñÿ òî-
âàðíûé ïîåçä. Â íåì îêîëî 50 âàãîíîâ. Ìû õîòèì ñôîðìèðîâàòü
ñîñòàâ, âûáðàâ îïòèìàëüíûé ïîðÿäîê âàãîíîâ. Îáùåå ÷èñëî âà-
ðèàíòîâ 50!≈1065. Ïðè áûñòðîäåéñòâèè 1045 îï/ñ êîìïüþòåðó ïî-
òðåáóåòñÿ 1065/1045 = 1020 ñ > 1018 ìèí >1016 ÷ > 1012 ëåò. Òàêèì
îáðàçîì, ïåðåáðàòü âñå âàðèàíòû ìû íå ñìîæåì è íà òàêîì ñó-
ïåðêîìïüþòåðå.
      Ïîäâåäåì èòîãè. Âàæíîé õàðàêòåðèñòèêîé àëãîðèòìà ÿâëÿ-
åòñÿ åãî òðóäîåìêîñòü. Åñëè òðóäîåìêîñòü êàêîãî-ëèáî àëãîðèòìà
ðàñòåò êàê ïîëèíîì (ìíîãî÷ëåí) îò ðàçìåðîâ çàäà÷è, òî ðåøèòü
çàäà÷ó ìîæíî ïðàêòè÷åñêè äëÿ ëþáîé ðàçìåðíîñòè. Åñëè æå òðó-
äîåìêîñòü êàêîãî-ëèáî àëãîðèòìà ðàñòåò êàê 2 n èëè n!, òî ïðè
áîëüøèõ n ïðèìåíåíèå ýòîãî àëãîðèòìà ïðàêòè÷åñêè íåâîçìîæíî.




                                  11

Страницы