В.Б. Алексеев - Введение в теорию сложности алгоритмов (В.Б. Алексеев - Введение в теорию сложности алгоритмов.pdf)

PDF-файл В.Б. Алексеев - Введение в теорию сложности алгоритмов (В.Б. Алексеев - Введение в теорию сложности алгоритмов.pdf) Дискретная математика (36746): Книга - 2 семестрВ.Б. Алексеев - Введение в теорию сложности алгоритмов (В.Б. Алексеев - Введение в теорию сложности алгоритмов.pdf) - PDF (36746) - СтудИзба2019-04-282019-04-28zzyxelСтудИзба

В.Б. Алексеев - Введение в теорию сложности алгоритмов.pdf349

Описание файла

PDF-файл из архива "В.Б. Алексеев - Введение в теорию сложности алгоритмов.pdf", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр 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 ìû áóäåìîáîçíà÷àòü íàèáîëüøåå (ñîîòâåòñòâåííî, íàèìåíüøåå) öåëîå ÷èñëî, íåáîëüøåå (ñîîòâåòñòâåííî, íå ìåíüøåå), ÷åì α.

Поделитесь ссылкой:

Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.

Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.

Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.

Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.

Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.

Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.

Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.

Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.

Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.

Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.

Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.

Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.