Дмитрий Голубенко , Алексей Крошнин , Эдуард Горбунов - Алгоритмы и модели вычисления

Ôåäåðàëüíîå ãîñóäàðñòâåííîå àâòîíîìíîå
îáðàçîâàòåëüíîå
ó÷ðåæäåíèå âûñøåãî îáðàçîâàíèÿ
¾Ìîñêîâñêèé ôèçèêî-òåõíè÷åñêèé èíñòèòóò
(ãîñóäàðñòâåííûé óíèâåðñèòåò)¿
Öåíòð ðàçâèòèÿ ÈÒ-îáðàçîâàíèÿ

Àëãîðèòìû è ìîäåëè âû÷èñëåíèÿ
Äìèòðèé Ãîëóáåíêî
Àëåêñåé Êðîøíèí
Ýäóàðä Ãîðáóíîâ

Ìîñêâà, 2019

Îãëàâëåíèå
Ïðåäèñëîâèå

3

×àñòü 1. Ââåäåíèå

5
10
16
19

×àñòü 2. Ñîðòèðîâêè è ìåäèàíû

25
26
39

×àñòü 3. Àëãåáðà è òåîðèÿ ÷èñåë

41
50
51
55
57
59
62
65
70
75
75
82
87
88
89
96
100

Àñèìïòîòè÷åñêèå îöåíêè. Ìåòîä Àêðà-Áàççè
Ëèíåéíûå ðåêóððåíòû
Âåðîÿòíîñòü: ââåäåíèå

Ñîðòèðîâêè
Ïîèñê k-îé ñòàòèñòèêè

Ïîëèíîìèàëüíûå àðèôìåòè÷åñêèå àëãîðèòìû
Ïîëèíîìèàëüíîñòü àëãîðèòìà Åâêëèäà
Áûñòðîå óìíîæåíèå ÷èñåë è ìàòðèö
Áûñòðîå âîçâåäåíèå â ñòåïåíü
Ïîëèíîìèàëüíîñòü àëãîðèòìà Ãàóññà
Ïðîñòåéøèå êðèïòîãðàôè÷åñêèå ïðîòîêîëû
Äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüå
Áûñòðîå ïåðåìíîæåíèå ìíîãî÷ëåíîâ
Ðåøåòî Ýðàòîñôåíà
Âåðîÿòíîñòíûå òåñòû íà ïðîñòîòó
Àëãîðèòì ÀÊÑ
Âçÿòèå êâàäðàòíîãî êîðíÿ ïî ìîäóëþ
Äèñêðåòíîå ëîãàðèôìèðîâàíèå
Ôàêòîðèçàöèÿ öåëûõ ÷èñåë
Ôàêòîðèçàöèÿ ìíîãî÷ëåíîâ. Àëãîðèòì Êàíòîðà-Öàññåíõàóñà
Àëãîðèòì Áåðëåêåìïà
1

Òåîðåòèêî-ãðóïïîâûå àëãîðèòìû
Çàäà÷à ïðèíàäëåæíîñòè
Ôèëüòð Äæåððàìà
Çàäà÷à graph-iso è òåîðåòèêî-ãðóïïîâûå àëãîðèòìû

101
104
109
110

×àñòü 4. Ãðàôû è àëãîðèòìû

115
117
121
125
130
133
143
144
151
154
161
166
169

×àñòü 5. Ýëåìåíòû òåîðèè ñëîæíîñòè
Âåðîÿòíîñòíûå àëãîðèòìû: îïðåäåëåíèÿ
Êëàññû P, NP è co − NP
P RIM ES ⊂ NP ∩ co − NP
Ñèñòåìû ëèíåéíûõ íåðàâåíñòâ
Ïîëèíîìèàëüíàÿ ñâîäèìîñòü

177
187
189
195
199
203

×àñòü 6. Èçáðàííûå çàäà÷è è ðåøåíèÿ

219

Áèáëèîãðàôèÿ

235

Depth-rst search
Ïîèñê òî÷åê ñî÷ëåíåíèÿ
Êîìïîíåíòû ñèëüíîé ñâÿçíîñòè
Breadth-rst search
Ïîèñê êðàò÷àéøèõ ïóòåé
Ìèíèìàëüíûå îñòîâíûå äåðåâüÿ
Àëãîðèòìû Ïðèìà, Êðóñêàëà è Áîðóâêè
Ïîòîêè è ñåòè
Ìåòîä Ôîðäà-Ôàëêåðñîíà. Àëãîðèòì ÝäìîíäñàÊàðïà
Ìåòîä ïðîòàëêèâàíèÿ ïðåäïîòîêà. Àëãîðèòì Òàðüÿíà-Ãîëäáåðãà
0-1 ïîòîêè
Âåðøèííàÿ è ðåáåðíàÿ ñâÿçíîñòè

Ïðåäèñëîâèå
Ýòà êíèæêà íàïèñàíà ïî ìîòèâàì ìàòåðèàëîâ îäíîèìåííîãî êóðñà êàôåäðû ìîó íà
Ôèçòåõå, çàïèñàííûõ Äèìîé Ãîëóáåíêî, Ëåøåé Êðîøíèíûì è Ýäîì Ãîðáóíîâûì. Êóðñ
âåë Ñåðãåé Òàðàñîâ, è îí æå ïðèäóìàë êîíöåïöèþ, ñèëüíî îòëè÷àþùóþ ¾Àëãîðèòìû è
ìîäåëè âû÷èñëåíèÿ¿ îò äðóãèõ àíàëîãè÷íûõ êóðñîâ. Ñòàíäàðòíûé êóðñ ïî àëãîðèòìàì
 îáçîð îñíîâíûõ àëãîðèòìîâ(áûñòðàÿ ñîðòèðîâêà, ïîèñê ìåäèàíû, îáõîäû ãðàôîâ) è
ñòðóêòóð äàííûõ, íåîáõîäèìûõ êàæäîìó ïðîãðàììèñòó. Íåòðóäíî âèäåòü, ÷òî ïî÷òè âñå
ýòè îñíîâíûå àëãîðèòìû âîçíèêëè âî âðåìÿ ðåøåíèÿ íåêîòîðûõ ìàòåìàòè÷åñêèõ çàäà÷.
×èòàÿ ¾Àëãîðèòìû è ìîäåëè âû÷èñëåíèÿ¿, Ñåðãåé â ïåðâóþ î÷åðåäü ñòðåìèëñÿ ïðîäåìîíñòðèðîâàòü ñâÿçü àëãîðèòìîâ è ìàòåìàòèêè, êàêèå àëãîðèòìû è êàê ïîçâîëÿþò ðåøàòü
ìàòåìàòè÷åñêèå çàäà÷è (èç ñàìûõ ðàçíûõ îáëàñòåé, áóäü òî òåîðèÿ ÷èñåë èëè òîïîëîãèÿ)
è êàêàÿ ìàòåìàòèêà ëåæèò â îñíîâå òåõ èëè èíûõ àëãîðèòìîâ. Òåîðèÿ àëãîðèòìîâ âîçíèêëà åñòåñòâåííûì îáðàçîì èç âû÷èñëèòåëüíûõ çàäà÷ â ðàçíûõ îáëàñòÿõ ìàòåìàòèêè è ïî
ñåé äåíü îñòàåòñÿ æèâîé îáëàñòüþ, â êîòîðîé íåêîòîðûå òðèâèàëüíî ñôîðìóëèðîâàííûå
âîïðîñû äî ñèõ ïîð îòêðûòû.  ýòîé êíèæêå ìû ðàññêàæåì ìàòåìàòè÷åñêèì ÿçûêîì îá
îñíîâíûõ àëãîðèòìàõ ñîðòèðîâêè, àëãåáðû, òåîðèè ÷èñåë è òåîðèè ãðàôîâ.
Ìíîãèå øêîëüíèêè èçó÷àþò àëãîðèòìû, ãîòîâÿñü ê îëèìïèàäàì ïî ïðîãðàììèðîâàíèþ. Âîçìîæíî, ÷òî ýòà êíèãà ïîìîæåò ìàòåìàòèêàì-îëèìïèàäíèêàì, íå çàíèìàâøèìñÿ
àëãîðèòìàìè, çàèíòåðåñîâàòüñÿ îëèìïèàäíûì ïðîãðàììèðîâàíèåì, à ìîæåò áûòü  è
òåîðèåé àëãîðèòìîâ.
Àâòîðû áëàãîäàðÿò Ñåðãåÿ Òàðàñîâà, ñîáðàâøåãî íåîáû÷íóþ êîìíàäó ñåìèèíàðèñòîâ
è ïðèäóìàâøåãî îðèãèíàëüíóþ êîíöåïöèþ êóðñà, à òàêæå ñîòðóäíèêîâ Öåíòðà Ðàçâèòèÿ
ÈÒ-Îáðàçîâàíèÿ è ëè÷íî Òàòüÿíó Áàáè÷åâó, ÷üè äîáðîòà, îòçûâ÷èâîñòü è óñèëèÿ ñäåëàëè
ñóùåñòâîâàíèå ýòîé êíèæêè âîçìîæíûì.

×àñòü 1

Ââåäåíèå

Ñî øêîëû êàæäîìó çíàêîìî èíòóèòèâíîå îïðåäåëåíèå àëãîðèòìà  ¾íàáîð èíñòðóêöèé, îïèñûâàþùèõ ïîðÿäîê äåéñòâèé èñïîëíèòåëÿ äëÿ äîñòèæåíèÿ íåêîòîðîãî ðåçóëüòàòà¿. Ñ÷èòàåòñÿ, ÷òî àëãîðèòì ïðèíèìàåò íà âõîä íåêîòîðûé
,
âûïîëíÿåò îïðåäåëåííóþ ïîñëåäîâàòåëüíîñòü äåéñòâèé è âîçâðàùàåò (åñëè îñòàíàâëèâàåòñÿ) íîâûé êîíñòðóêòèâíûé îáúåêò. Êîíñòðóêòèâíûé îáúåêò  òîò, äëÿ êîòîðîãî ñóùåñòâóåò êîíñòðóêòèâíûé ñïîñîá --">