В.Б. Алексеев - Введение в теорию сложности алгоритмов
Описание файла
PDF-файл из архива "В.Б. Алексеев - Введение в теорию сложности алгоритмов", который расположен в категории "". Всё это находится в предмете "сложность алгоритмов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Ìîñêîâñêèé ãîñóäàðñòâåííûé óíèâåðñèòåòèìåíè Ì. Â. ËîìîíîñîâàÔàêóëüòåò âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêèÂ. Á. ÀëåêñååâÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÑËÎÆÍÎÑÒÈÀËÃÎÐÈÒÌÎÂÓ÷åáíîå ïîñîáèå ïî êóðñóÑëîæíîñòü àëãîðèòìîâÌîñêâà 2002ÓÄÊ 519.17:519.71ÁÁÊ 22.176À 47Àëåêñååâ Â. Á. Ââåäåíèå â òåîðèþ ñëîæíîñòè àëãîðèòìîâ (ó÷åáíîåïîñîáèå äëÿ ñòóäåíòîâ) Ì.: Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ(ëèöåíçèÿ ÈÄ N 05899 îò 24.09.2001), 2002 ã. 82 ñ.Êóðñ "Ñëîæíîñòü àëãîðèòìîâ"âõîäèò êàê îñíîâíîé êóðñ â ó÷åáíûéïëàí äëÿ ñòóäåíòîâ êàôåäðû ìàòåìàòè÷åñêîé êèáåðíåòèêè ôàêóëüòåòàÂÌèÊ ÌÃÓ, à òàêæå ìîæåò ñëóæèòü ñïåöêóðñîì äëÿ ñòóäåíòîâ äðóãèõêàôåäð.
Äàííîå ó÷åáíîå ïîñîáèå ïðèçâàíî ïîìî÷ü ñòóäåíòàì â èçó÷åíèèýòîãî êóðñà.  ó÷åáíîì ïîñîáèè ðàññìàòðèâàþòñÿ îáùèå óòâåðæäåíèÿ îñëîæíîñòè çàäà÷, ìåòîäû ïîñòðîåíèÿ áûñòðûõ àëãîðèòìîâ (ìåòîä äèíàìè÷åñêîãî ïðîãðàìììèðîâàíèÿ, "ðàçäåëÿé è âëàñòâóé ìåòîä ðàñøèðåíèÿìîäåëè) è ïðèìåðû èõ ïðèìåíåíèÿ ñ îöåíêàìè ñëîæíîñòè, îñíîâíûåêëàññû çàäà÷ îòíîñèòåëüíî èõ ñëîæíîñòè, ïðèìåðû óíèâåðñàëüíûõ çàäà÷â ýòèõ êëàññàõ.Ðåöåíçåíòû:Ëóïàíîâ Î. Á., ÷ë.-êîðð.
ÐÀÍ, ïðîôåññîðËîæêèí Ñ. À., ä. ô.-ì. í., ïðîôåññîðÏå÷àòàåòñÿ ïî ðåøåíèþ Ðåäàêöèîííî-èçäàòåëüñêîãî ñîâåòà ôàêóëüòåòà âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêè ÌÃÓ èì. Ì. Â. Ëîìîíîñîâà.ISBN 5-89407-087-2c Èçäàòåëüñêèé îòäåëôàêóëüòåòà âû÷èñëèòåëüíîéìàòåìàòèêè è êèáåðíåòèêèÌÃÓ èì. Ì. Â. Ëîìîíîñîâà, 2002ÎÃËÀÂËÅÍÈÅ1. Ââåäåíèå .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1. Ïîèñê â óïîðÿäî÷åííîì ìàññèâå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2. Ñîðòèðîâêà . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72. Ðåêóððåíòíûå ìåòîäû ïîñòðîåíèÿ àëãîðèòìîâ . . . . . . . . . . . . 102.1.2.2.2.3.2.4.2.5.Ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ . . . . . . . .
. . . . . . . . . . . . . . . . . 10Ìåòîä ðàçäåëÿé è âëàñòâóé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14Àëãîðèòì Êàðàöóáû äëÿ óìíîæåíèÿ ÷èñåë . . . . . . . . . . . . . . . . . . . . . . . 16Àëãîðèòì Òîîìà äëÿ óìíîæåíèÿ ÷èñåë. . . . . . . . . . . . . . . . . . . . . . . . . . . .18Àëãîðèòì Øòðàññåíà äëÿ óìíîæåíèÿ ìàòðèö .
. . . . . . . . . . . . . . . . . . . . 203. Ìåòîä ðàñøèðåíèÿ ìîäåëè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.1. Àëãîðèòìû óìíîæåíèÿ 0-1-ìàòðèö . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.2. Òðàíçèòèâíîå çàìûêàíèå ãðàôîâ .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.3. Ðàñïîçíàâàíèå ïðèíàäëåæíîñòè áóëåâûõ ôóíêöèé ïðåäïîëíûìêëàññàì Ïîñòà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.4. Ðàñïîçíàâàíèå ñîõðàíåíèÿ äâóõìåñòíûõ ïðåäèêàòîâ . . . . . . . . . .
. . . . 273.5. Êëàññû F m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294. Îáùàÿ òåîðèÿ ñëîæíîñòè çàäà÷ . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.1.4.2.4.3.4.4.4.5.4.6.4.7.4.8.Ìàøèíû Òüþðèíãà . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33Ñóùåñòâîâàíèå ñëîæíûõ çàäà÷ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34Ìåòîä ñëåäîâ. Ðàñïîçíàâàíèå ñèììåòðèè . . . . . . . . . . . . . . . . . . . . . . . . . . 38Ðåãóëÿðíûå ÿçûêè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 42Êëàññû P è N P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Òåîðåìà Êóêà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 49Ñëîæíîñòü çàäà÷ î âûïîëíèìîñòè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54Íåêîòîðûå N P -ïîëíûå çàäà÷è íà ãðàôàõ . . . . . . . . . . . . . . . . . . . . . . . . . 585. Çàäà÷è îïòèìèçàöèè . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645.1.5.2.5.3.5.4.Çàäà÷à î êðàò÷àéøåì îñòîâíîì äåðåâå . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64Ïðèáëèæåííûå àëãîðèòìû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66Çàäà÷à êîììèâîÿæåðà . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69Çàäà÷à î ìàêñèìàëüíîé êëèêå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 726. ÊëàññûP SP ACE è DLOG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74Ëèòåðàòóðà . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7931. ÂâåäåíèåÊàæäûé àëãîðèòì A õàðàêòåðèçóåòñÿ òåì, ÷òî íà åãî âõîä ìîãóò ïîñòóïàòü ðàçëè÷íûå âõîäíûå äàííûå x, êîòîðûå îí ïðåîáðàçóåò â íåêîòîðûå âûõîäíûå äàííûå y . Ïðè ýòîì ïðîöåññ ðàáîòû A íà âõîäíûõ äàííûõx ìîæíî îõàðàêòåðèçîâàòü íåêîòîðûìè ñëîæíîñòíûìè õàðàêòåðèñòèêàìè LA (x) (÷èñëî øàãîâ àëãîðèòìà, îáúåì èñïîëüçóåìîé ïàìÿòè è äð.).Îäíàêî äàòü ÿâíîå ïðåäñòàâëåíèå ôóíêöèè LA (x) äëÿ âñåõ x îáû÷íî íåïðåäñòàâëÿåòñÿ âîçìîæíûì.
Äàæå ïîâåäåíèå LA (x) êàê ôóíêöèè îò xîáû÷íî òðóäíî îïèñàòü. Ïîýòîìó ïðè àíàëèçå ñëîæíîñòè àëãîðèòìîâ ÷àñòî ðàññìàòðèâàþò áîëåå ãðóáûå õàðàêòåðèñòèêè. Íàèáîëåå ðàñïðîñòðàíåííûì ÿâëÿåòñÿ ñëåäóþùèé ïîäõîä. Âõîäíûå äàííûå õàðàêòåðèçóþòñÿíåêîòîðûì íàòóðàëüíûì ïàðàìåòðîì n èõ ñëîæíîñòè (÷àùå âñåãî n äëèíà ïðåäñòàâëåíèÿ âõîäíûõ äàííûõ íåêîòîðûì çàäàííûì ñïîñîáîì).Äàëåå èçó÷àåòñÿ ôóíêöèÿ LA (n), îïðåäåëÿåìàÿ êàê ìàêñèìóì LA (x) ïîâñåì x ñ ïàðàìåòðîì n (ñëîæíîñòü â õóäøåì ñëó÷àå) èëè êàê íåêîòîðîåñðåäíåå LA (x) ïî âñåì x ñ ïàðàìåòðîì n (ñðåäíÿÿ ñëîæíîñòü).  ýòèõñëó÷àÿõ óæå óäàåòñÿ ïîëó÷àòü èíòåðåñíûå ðåçóëüòàòû.
 äàííîì ïîñîáèè ìû áóäåì ðàññìàòðèâàòü òîëüêî îäíó ñëîæíîñòíóþ õàðàêòåðèñòèêóàëãîðèòìîâ âðåìÿ, èëè ÷èñëî øàãîâ, ðàáîòû àëãîðèòìà. Ïðè ýòîì ìûäîëæíû ÷åòêî îïðåäåëÿòü, ÷òî òàêîå øàã àëãîðèòìà. Åñëè æå ìû õîòèìïîëó÷àòü óòâåðæäåíèÿ òèïà äëÿ ëþáîãî àëãîðèòìà, òî ìû òàêæå äîëæíû ÷åòêî îïèñàòü âåñü êëàññ àëãîðèòìîâ, êîòîðûå ìû ðàññìàòðèâàåì. Ìûïîÿñíèì ýòî âíà÷àëå ïðèìåðàìè.1.1. Ïîèñê â óïîðÿäî÷åííîì ìàññèâå.Ïóñòü èìååòñÿ óïîðÿäî÷åííûé ìàññèâ ýëåìåíòîâ èç íåêîòîðîãîëèíåéíî óïîðÿäî÷åííîãî ìíîæåñòâà a1 < a2 < . . .
< an . Íà âõîäàëãîðèòìà áóäåò ïîñòóïàòü íåêîòîðûé ýëåìåíò a, ñîâïàäàþùèé ñ îäíèìèç ýëåìåíòîâ a1 , a2 , . . . , an . Îäèí øàã àëãîðèòìà ñîñòîèò â ñðàâíåíèè ac íåêîòîðûì ai , ïîëó÷åíèè îäíîãî èç äâóõ îòâåòîâ a 6 ai èëè a > ai èàíàëèçå ýòîãî îòâåòà. Àëãîðèòì äîëæåí âûäàòü íîìåð j òîãî ýëåìåíòàaj , äëÿ êîòîðîãî a = aj .
Ðàññìîòðèì, íàïðèìåð, àëãîðèòì, êîòîðûéñðàâíèâàåò a ïî î÷åðåäè ñî âñåìè ýëåìåíòàìè îò a1 äî an . Òîãäà åñëèa = a1 , îí ìîæåò âûäàòü îòâåò óæå ïîñëå 1-ãî øàãà. Îäíàêî, åñëèa = an−1 èëè a = an , òî àëãîðèòì áóäåò äåëàòü n − 1 øàãîâ.  ñðåäíåì,åñëè ñ÷èòàòü, ÷òî a ñîâïàäàåò ñ ëþáûì ai c âåðîÿòíîñòüþ n1 , ÷èñëî øàãîâ(1+2+...+n−1)+n−11áóäåò= n+1n2 − n. äàëüíåéøåì ìû áóäåì àëãîðèòìû ñ÷èòàòü äåòåðìèíèðîâàííûìè.Òàê, íàïðèìåð, äëÿ ëþáîãî àëãîðèòìà ïîèñêà ýëåìåíòà â óïîðÿäî÷åííîì4ìàññèâå íà ïåðâîì øàãå îäíîçíà÷íî îïðåäåëÿåòñÿ íîìåð i ýëåìåíòà, ñêîòîðûì ñðàâíèâàåòñÿ a.
Ýòîò íîìåð íå çàâèñèò îò âõîäà a.  çàâèñèìîñòè îò îòâåòà (a 6 ai èëè a > ai ) îäíîçíà÷íî îïðåäåëÿåòñÿ ñëåäóþùèéíîìåð ýëåìåíòà, ñ êîòîðûì ñðàâíèâàåòñÿ a, è ò.ä. Òàêèì îáðàçîì âñÿêèé àëãîðèòì ïîèñêà (èç óêàçàííîãî âûøå êëàññà) ìîæíî ïðåäñòàâèòüêîðíåâûì áèíàðíûì äåðåâîì, â êîòîðîì êàæäîé âåðøèíå, îòëè÷íîé îòëèñòüåâ, ïðèïèñàí íåêîòîðûé íîìåð ýëåìåíòà, ñ êîòîðûì ñðàâíèâàåòñÿa, à êàæäîìó ëèñòó ïðèïèñàí íîìåð ýëåìåíòà, ðàâíîãî a.Îïðåäåëåíèå. Ñëîæíîñòüþ (â õóäøåì ñëó÷àå) LA (n) àëãîðèòìàïîèñêà â óïîðÿäî÷åííîì ìàññèâå èç n ýëåìåíòîâ íàçûâàåòñÿ ìàêñèìàëüíîå ÷èñëî ñðàâíåíèé ýëåìåíòà a ñ ýëåìåíòàìè ìàññèâà äî ïîëó÷åíèÿ îòñðâåòà. Ñðåäíåé ñëîæíîñòüþ LA (n) àëãîðèòìà ïîèñêà A â óïîðÿäî÷åííîìPnñðìàññèâå èç n ýëåìåíòîâ íàçûâàåòñÿ âåëè÷èíà LA (n) = n1 i=1 LA (ai ), ãäåLA (ai ) ÷èñëî øàãîâ àëãîðèòìà, åñëè âõîä a = ai .Åñëè α äåéñòâèòåëüíîå ÷èñëî, òî ÷åðåç bαc è dαe ìû áóäåìîáîçíà÷àòü íàèáîëüøåå (ñîîòâåòñòâåííî, íàèìåíüøåå) öåëîå ÷èñëî, íåáîëüøåå (ñîîòâåòñòâåííî, íå ìåíüøåå), ÷åì α.
×àñòî bαc îáîçíà÷àþò [α]è íàçûâàþò öåëîé ÷àñòüþ ÷èñëà α.Òåîðåìà 1.1. Ñóùåñòâóåò àëãîðèòìAïîèñêà â óïîðÿäî÷åííîìLA (n) = dlog2 ne.Äîêàçàòåëüñòâî. Äîêàçûâàòü ñóùåñòâîâàíèå àëãîðèòìà ñ íóæíûìè ñâîéñòâàìè îáû÷íî ëåãêî äîñòàòî÷íî ÿâíî ïðåäúÿâèòü òàêîé àëãîðèòì. Òðåáóåìîìó â òåîðåìå óñëîâèþ óäîâëåòâîðÿåò ñëåäóþùèé àëãîðèòì, íàçûâàåìûé áèíàðíûì ïîèñêîì, è îïèñûâàåìûé ðåêóððåíòíî.Åñëè n = 1, òî âûäàòü îòâåò a = a1 .Åñëè n > 2, òî âû÷èñëèòü k = b n2 c è ñðàâíèòü a ñ ak .
Åñëè a 6 ak ,òî ðåêóððåíòíî (òåì æå àëãîðèòìàì) îñóùåñòâèòü ïîèñê a â ìàññèâåa1 < a2 < . . . < ak . Åñëè a > ak , òî îñóùåñòâèòü (ðåêóððåíòíî) ïîèñê aâ ìàññèâå ak+1 < ak+2 < . . . < an . ëþáîì ñëó÷àå äëèíà ïîëó÷àåìîãî ìàññèâà íå ïðåâîñõîäèò n −nb 2 c = d n2 e, è, ñëåäîâàòåëüíî, LA (n) = 1 + LA (d n2 e). Êðîìå òîãî LA (1) =0. Äîêàæåì èíäóêöèåé ïî m, ÷òî äëÿ âñåõ íàòóðàëüíûõ n, òàêèõ, ÷òî2m−1 < n 6 2m , âûïîëíÿåòñÿ LA (n) = m. Ïðè m = 0 ïîëó÷àåì n = 1 èLA (1) = 0 = m. Ïóñòü óòâåðæäåíèå âåðíî äëÿ m = p è 2p < n 6 2p+1 .Òîãäà 2p−1 < d n2 e 6 2p è ïî ïðåäïîëîæåíèþ èíäóêöèè LA (d n2 e) = p.Îòñþäà LA (n) = 1 + LA (d n2 e) = p + 1, òî åñòü óòâåðæäåíèå âåðíî äëÿm = p + 1. Ïî èíäóêöèè ïîëó÷àåì, ÷òî óòâåðæäåíèå âåðíî äëÿ âñåõ n,òî åñòü LA (n) = m = dlog2 ne.
Òåîðåìà äîêàçàíà.ñðÑëåäñòâèå. Äëÿ àëãîðèòìà A áèíàðíîãî ïîèñêà LA (n) 6ìàññèâå, äëÿ êîòîðîãî5dlog2 ne.Äîêàçàòü óòâåðæäåíèå òèïà äëÿ ëþáîãî àëãîðèòìà îáû÷íî ñóùåñòâåííî òðóäíåå, ÷åì óòâåðæäåíèå òèïà ñóùåñòâóåò àëãîðèòì.  ýòîìñëó÷àå ìû äîëæíû ÷åòêî îïèñàòü âåñü êëàññ ðàññìàòðèâàåìûõ àëãîðèòìîâ. Âûøå áûëî óêàçàíî, ÷òî ëþáîé àëãîðèòì ïîèñêà â óïîðÿäî÷åííîììàññèâå èç n ýëåìåíòîâ ìîæíî ïðåäñòàâèòü â âèäå áèíàðíîãî äåðåâà.Ïîýòîìó äàëåå ìû ðàññìîòðèì íåêîòîðûå ñâîéñòâà áèíàðíûõ äåðåâüåâ.Îïðåäåëåíèå.
Ãëóáèíîé h(x) ëèñòà x â êîðíåâîì äåðåâå D áóäåìíàçûâàòü ÷èñëî ðåáåð â (åäèíñòâåííîì) ïóòè èç êîðíÿ äåðåâà â ëèñò x.Âûñîòîé h(D) äåðåâà D áóäåì íàçûâàòü max h(x), ãäå ìàêñèìóì áåðåòñÿïî âñåì ëèñòüÿì äåðåâà D. Ñðåäíåé âûñîòîé hñð (D) äåðåâà D áóäåìíàçûâàòü ñðåäíåå àðèôìåòè÷åñêîå âåëè÷èí h(x) ïî âñåì ëèñòüÿì äåðåâàD.Ëåììà 1.1. Äëÿ ëþáîãî áèíàðíîãî äåðåâà ñ n ëèñòüÿìè âûïîëíÿþòñÿ íåðàâåíñòâà: 1) h(D) > dlog2 ne, 2) hñð (D) > log2 n.Äîêàçàòåëüñòâî. 1) Ëþáîå áèíàðíîå äåðåâî âûñîòû h ìîæíî äîñòðîèòü äî ïîëíîãî áèíàðíîãî äåðåâà âûñîòû h (â êîòîðîì âñå ïóòè îòêîðíÿ äî ëèñòüåâ ñîäåðæàò ïî h ðåáåð). Äëÿ ýòîãî äîñòàòî÷íî ê êàæäîìóëèñòó x âûñîòû h(x) ïîäêëåèòü ïîëíîå áèíàðíîå äåðåâî âûñîòû h−h(x).Ïðè ýòîì ÷èñëî ëèñòüåâ íå óìåíüøèòñÿ.