Алгоритмы и модели вычисления [Дмитрий Голубенко] (pdf) читать постранично Книга в формате pdf ! Изображения и текст могут не отображаться!
[Настройки текста] [Cбросить фильтры]
Цвет фона черный светло-черный бежевый бежевый 2 персиковый зеленый серо-зеленый желтый синий серый красный белый
Цвет шрифта белый зеленый желтый синий темно-синий серый светло-серый тёмно-серый красный
Размер шрифта 14px 16px 18px 20px 22px 24px
Шрифт Arial, Helvetica, sans-serif "Arial Black", Gadget, sans-serif "Bookman Old Style", serif "Comic Sans MS", cursive Courier, monospace "Courier New", Courier, monospace Garamond, serif Georgia, serif Impact, Charcoal, sans-serif "Lucida Console", Monaco, monospace "Lucida Sans Unicode", "Lucida Grande", sans-serif "MS Sans Serif", Geneva, sans-serif "MS Serif", "New York", sans-serif "Palatino Linotype", "Book Antiqua", Palatino, serif Symbol, sans-serif Tahoma, Geneva, sans-serif "Times New Roman", Times, serif "Trebuchet MS", Helvetica, sans-serif Verdana, Geneva, sans-serif
Насыщенность шрифта жирный
Обычный стиль курсив Ширина текста 400px 500px 600px 700px 800px 900px 1000px 1100px 1200px Показывать меню Убрать меню Абзац 0px 4px 12px 16px 20px 24px 28px 32px 36px 40px
Межстрочный интервал 18px 20px 22px 24px 26px 28px 30px 32px
Ôåäåðàëüíîå ãîñóäàðñòâåííîå àâòîíîìíîå
îáðàçîâàòåëüíîå
ó÷ðåæäåíèå âûñøåãî îáðàçîâàíèÿ
¾Ìîñêîâñêèé ôèçèêî-òåõíè÷åñêèé èíñòèòóò
(ãîñóäàðñòâåííûé óíèâåðñèòåò)¿
Öåíòð ðàçâèòèÿ ÈÒ-îáðàçîâàíèÿ
Àëãîðèòìû è ìîäåëè âû÷èñëåíèÿ
Äìèòðèé Ãîëóáåíêî
Àëåêñåé Êðîøíèí
Ýäóàðä Ãîðáóíîâ
Ìîñêâà, 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
Ââåäåíèå
Ñî øêîëû êàæäîìó çíàêîìî èíòóèòèâíîå îïðåäåëåíèå àëãîðèòìà ¾íàáîð èíñòðóêöèé, îïèñûâàþùèõ ïîðÿäîê äåéñòâèé èñïîëíèòåëÿ äëÿ äîñòèæåíèÿ íåêîòîðîãî ðåçóëüòàòà¿. Ñ÷èòàåòñÿ, ÷òî àëãîðèòì ïðèíèìàåò íà âõîä íåêîòîðûé
,
âûïîëíÿåò îïðåäåëåííóþ ïîñëåäîâàòåëüíîñòü äåéñòâèé è âîçâðàùàåò (åñëè îñòàíàâëèâàåòñÿ) íîâûé êîíñòðóêòèâíûé îáúåêò. Êîíñòðóêòèâíûé îáúåêò òîò, äëÿ êîòîðîãî ñóùåñòâóåò êîíñòðóêòèâíûé ñïîñîá çàäàòü åãî, íàïðèìåð, íàòóðàëüíîå ÷èñëî, ìàòðèöà èëè
ãðàô.
Òàêîå ïîíÿòèå àëãîðèòìà äîâîëüíî ðàñïëûâ÷àòî è íå ïîçâîëÿåò êîíêðåòíî îòâåòèòü
íà òàêèå âîïðîñû:
êîíñòðóêòèâíûé îáúåêò
•
•
•
ëþáàÿ ëè çàäà÷à ðàçðåøèìà àëãîðèòìè÷åñêè?
åñëè íåêîòîðàÿ çàäà÷à íå ðàçðåøàåòñÿ íèêàêèì àëãîðèòìîì, êàê ýòî äîêàçàòü? Èíûìè ñëîâàìè, êàê ïîêàçàòü, ÷òî ëþáîé àëãîðèòì ðàçðåøàåò çàäà÷ó,
îòëè÷íóþ îò äàííîé?
êàê âû÷èñëèòü âðåìÿ, ñîâåðøåííûõ àëãîðèòìîì, èëè òðåáóåìóþ ïàìÿòü? Íåëüçÿ âû÷èñëèòü âðåìÿ ðàáîòû àëãîðèòìà, ïðîñòî
Последние комментарии
5 минут 55 секунд назад
1 час 32 секунд назад
1 час 3 минут назад
11 часов 54 минут назад
11 часов 56 минут назад
1 день 39 минут назад