Ш.И._Галиев_МЛ_и_ТА_2004

экспоненциальной, если существуют постоянные с >0, а >1, что csf £ Дя) для всех, кроме конечного числа значенийп.

При первом определении, например, задача, имеющая слож­ ность порядка 0 ( ^ ") ( 0 ( ^ ° ) - 0 ( 2 ^ ^ ) ) , будет отнесена к задаче с экспоненциальной временной сложностью, а по второму определению - нет. Отметим, что функция п е,п, хот» и растет быст­ рее любого полинома, но растет медленнее, чей, гапример 2".

Большинство экспоненциальных алгоритмов - это просто вари­ анты полного перебора. Экспоненциальные алгоритмы не считаются «хорошими», R отличие от полиномиальных алгоритмов, которые, как уже указывалось, считаются «хорошими». К экспоненциальным зада­ чам относятся задачи, в которых требуете» построить множество всех

графа или же все поддеревья некоторогографа.

Некоторые зкепоненцнальные алгоритмы весьма хорошо зарекомендовали себя на практике. Дело в том, что временная слож­ ность определяется для худшего случая, а многие задачи могут быть

Для решения задачи линейного программирования существует так называемый симплекс-метод (алгоритм), который хотя и экспоненциален s худшем случае - уверенно работает на практике для задач достаточно большого размера. Отметим, что для решения задачи линейного програымироаанив Л. Г. Хачиян в 1979 г. предло­ жил алгоритм эллипсоидов, который имееп полиномиальную времен­ ную сложность.

Метол ветвей а границ успешно рвшает задачу о рюкзаке, хотя этот алгоритм имеет экспоненциальную временнуюсложность.

Примеров экспоненциальных алгоритмов, успешно используе­ мых на практике, мало. Более тою, лаже ддк полиномиальных алго­ ритмов представляют практический интерес алгоритмы, сложность которых имеет порядок я2 или и’. Ясно, что алгоритмы со сложностью

291

Интересно, что экспоненциальный алгоритм может оказаться лри малом размере задачи более быстрым, чем полиномиальны*, однако с ростом размера задачи полиномиальный становится бсикс быстрым.

Экслоненииальнвд сложность задачи имеет следующие аспекты:

-дня отыскания решения требуется экспоненциальное время;

-искомое решсвие может быть настолько велико, что не может быть представлено выраягением, длина которого была бы огракетюна

Вторая ситуация возникает, например, если в задаче КОМИИВМГ-

жера гребуется найти асе маршруты диины, не превосходящей задан­ ной величины L. Может оказаться, что имеется экспоненциальное

число маршрутов длины, не превосходящей L.

§ 7, Емкостная (ленточная) сложность алгоритма

Емкостная, или ленточная, сложность алгоритма характеризует необходимую для вычисления память для хранения исходных данных, промежуточных результатов и окончательного результата. При при­ менении машины Тьюринга как модели вычислений, емкостная слож­ ность оценивается длиной части ленты, используемой для записи ис­ ходных данных и вычислений.

Пусть машина Тьюринга вычисляв! значение функции/ Активной зоной ленты (машины Тьюринга) в данный момент

времени t называется связанная часть лееты, содержащая обозревае­ мую ячейку и все ячейки, в которых имеются символы да внешнего алфавита машины. Активной зоной при рв5оте машины Тьюринга на числе п называется объединение всех активных зон ia врет вычисления.

Определим 5/х) как длину активной зоны при рабэтг машины Г на числе х, если fix) определено. В противном случае значение S/i)

292

Кудем считать неопределенным. Функцию S/x) назовем лоточной

Ответим, что в настоящее время уделяется существенно больше внимания временным характеристикам и значительно меньше емкостяым, хот» эта характеристика тоже существенна при использовании ЭВМ с ограниченная память».

Для задач вводятся понятия задач г поланомиальяой потребной памятью, г ЛР-иотребноИпамятью ит.д.

Hveer место следующихтеорема:
Теорема 7.2. Для ленточной (емкостной)	характеристики I
сложности вычисления фуккции/кмеет место оценка	I
S/W < х+1+ 1/(х),
где <Д*)- временная сложность мчнемма Дх>	I

Доказательство. В начальный момент на ленте машины Тьюриша записано числа х (в унарной систскв), следовательно, занято 1+1 клеток лгты. На каждомтахте (шаге) шиивной становится не более одной новой клетки, поэтому получим указанную оценку для

Э Д ' яостъ, то можно оценить сверхуленточную сложность.

5ол®есложная задача.

§8. Вопросы и темы аля самопроверки

1.Понятие о сложности вычислений.

2.Рюкер исходных данных задачи для случаев, когдв входом является число, матрица, ipaiji.

3.Вргменн&я сложность алгоритма. Временная сложность

293

4.Временная сложность алгоритма в наихудшем случае, вре­ менная сложностьалгоритма в средней.

5.Могут ли для решения одной н тоП #£ задачи сущ&ггеовап. алгоритмы разной сложности? Если да, го какова сложность задачи?

6.Полиномиальная сложность алгоритма, задачи.

7.Классификация задач по сложности.

8.Класс Р, примеры задач из этого классе.

9. .VP-Kjiaoc.

10.Недетерминированная машина Тьюринга, ее отличие от детерминированной машины Тыоринга.

11.Задачи из .УР-класса.

12.VP-трудные и AV-полные задачи, в чем их различие?

13.Примеры jVP-noлных задач.

14.Кла-с Е.

15.Емкостная (ленточная) сложность алгоритма, оценка лен­

точной сложности через временную сложностьалгоритма.

§ 9, Упражнения

Рассмотрим известную задачу коммивояжера. Имеется п горо­ дов C“ {ci,cj, . и известны расстояние d(c„cj) между каждой парой городов СиС]из С. Нужно найти обход городов, чтобы побывать в каж­ дом городе из С один и только один раз, и вернуться в исходный го­ род, т. е. найти упорядоченный набор (cti.cn,...,rt*} и этот набор дол­ жен минимизировать суммарное расстояние обхода:

Эта задача, очевидно, алгоритмически разрешима, ибо можно перебрать все возможные варианты обходов и выбрать тот, дня кото­ рого указанное суммарное расстояние минимально.

Легко найти, чтп чжлп обходов п городов равно М-(п-1}112. Известно [26], что число 501 имеет около 65 десэтичшх знаков. Пусть для выбора одного варианта обхода городов и вычисле­ ния величины S по формуле (7.3) требуется (D= 0,001 с.

2М

]. Оценить, каким должно быть быстродействие ЭВМ, которая пере&рет все варианты обхода городов задачи коммивояжера для я = 51 за миллиард дет непрерывной работы.

2. Оценить время непрерывной работы ЭВМ с современными вычислительными возможностями для перебора всех указанны* s задаче I вариантов.

3.Построить алгоритм нахождения наибольшего элемент мно­ жества S, содержащего п действительных чисел, где п - степеньчисла 2, на базе стратегии дублирования. Оценить временную сложность построенного алгоритма.

4.Построить алгоритм нахождения наименьшего элемента мно­ жества S, содержащего и действительных неотрицательных чисел,

на базе стратегии дублирования. Оиенить временную сложность

построенного алгоритма.

5.Пусть Л массив размера и, состоящий из целых чисел (положительных и отрицательных), причем М,<Лг<...*ЛГ1 Построить алгоритм нахождения числа i, для которого A,=i (если такое / сущест­ вует). Каков порядок времени работа алгоритма?

6.Построить по стратегии дублирования алгоритм умножения

двух полиномов степени и, где п~2к, frs{1,2.,3,...), и определить вычислительную сложность,

7. Доказать, что сложности умножения, дслени», обращения н возведения в квадрат (М{щ, D(n), Щп) и ЭД) целых двоичных чисел размера п совпадают с точностьюдо постоянных множителей и имеют порядок 0(n/og2«), если и- степень числа 2,

8. Доказать, что сложности умножения, деления, обращения и возведения в к-падрэт (М(л), 0(л), Щп) и S(n)) полиномов степени п совпадают с точностью до постоянных множителей и имеют порядок O('ilogjn), если п - степень числа 2.

ПРИЛОЖЕНИЕ

надэпреждевсегоидти.

О. Бммш

Вариантытипового «даннн

1.Записатьприведенное высказыванье о виде формулы логит высказываний. Для оолученной формулы составить таблицу

2.Упростить формулу логики иыскашааний, используя основ­ ные равносильное™ иевду формулами.

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

4.Методом резолюций выяснить, истинно ли приведенное утверждение. Решитьзгу задячу, используя два метода из следующих:

кетод ксперлдкия уровня, стратегию вычеркивания, лок-резолюцгоо и табличный метод (последний для случая, если заданное множество является множествомхорновскихдизъюнктов).

5.Записагь предложениеввидеформулылогикипредикатов,

6.Привести гример интерпретации, для которой данная фор-

7.Получить предваренные нормальные формы и сколечовскне стандартные формы для данных формул.

296

8. Записигь предложения a аидг соотношений формул Логики предикатов. Методом резолюций выяснят! будет ли заключение

результат

с помощьюдишрамм Эй.!ара-Венна.

9 Построить нормальный алгоритм дна преобразования слою Р Dслово Q, при условии, чго в каждой подстановке Pr—>(, )0i алгормма чньло 5укв удовлетворяет неравенству: IР, i< и, IQ, I < п, где /i=2+[iVVraod 3), здесь К - ваш номер в описке группы,

a[,V)(imid 3) означаег число N номодулютри.

10.Построить машину Тьюринга дл» преобразования слова Р

лыюю(>.

11.Построить машину Тиорииш, которая будет считать запи­ санные подряд (без пропусков) единицы (нх чисто не преяисходит л)

изапишет их число в системе счисления с основанием я т|, здесь n=3-[jV](mod 13) и Л' « (ваш номер в списке гругтаы)+{номер вашей группы).

12.Докгзвть, что приведенная функция является примитивно

рекурсианой

13.Доказать методами исчисления высказываний, что двнная формулаяилягтея теоремой исчисления высказываний.

14.Выяснять, равносильны ли приведенные формулы а трех-

работанноа вами программы на любой известном вам алгоритмвчг-

версальном множестве 0-{х: Cl S i £ 10} функциями принадлежности:

здесь n=l+[W](raod 25) и N = (ааш номер в списке группы)-’ (номер вашей группы). Построить (о аналитическом а графическом видах) функции принадлежности для нечетких подмножвотй. указанных для вашего варианта.

297

2.A&CvA&D&\CvA&i.CvDSiB&\ D vS&A&\C&DvBvBv.

1.ASLCVA&B&]C.

A.A=-(B=-C), BvCvA ^=>Q vB .

5.Все А суть не В, а некоторые В суть С, кроме того, существуютЛ тихие, что С.

6.Vx3yP{xy)=VxPt,x,x).

7. Vx3

В+1хУуР(х.у)^3 y'ixPiy.x).

8.Ни одно С не есчъ D. Вое А О'ть D, Все В суть С. Следовательно, все В не есть Л

9.РжааЬсс, Q^aahccdabcdd

10.P=aabc, Q-aabccdcb.

1 1. Смотри условия здачи.

12.ад= [д-1, если х>0 [ 0, если х =0.

14. (0'Л)=.(ВД)&г, 0=м)&1. 15.Л*оВ* А 'и С* 1 ’ л(Л*иС*).

Вариант 2

'..А необходимо для В, я В достаточно для С н А, т А

неэквивалентно Сили В.

2.^T(CvD)&(W.BvlCva)&[TdvlCvIVC&l B)v£

3.'AvCvA&B&lC.

4."iPvlgvR, lM gvS. P.Q (■S.

5.Некоторые В суть не А, но ни одно В не есть С, тогда некоторые неА суть не С.

6.V.cM>,a)=> ЗУ'ЛсРСг.у).

l.A-3xVyP[xy)^yxP(x,x),B~Vx3yViR(x,y,t)=b3yViQ(y,z).

8.Все Сне etib D. Все.-4 суть не Л. Все Всуги С. Следователь-

9.P=bbcab, Q=bbcabLalabcdd.

10.P=abab, Q=abababcdab.

11.Смирн условия задачи

13.(Л=.в)=(1в=>Ъ).

14.(N((Nx)&y))ics, 0=M)Scz.

15./1*иВ*, A'r^C*, A*\J{B*n С*).

2.(/4vC)&(£V("U&]C))v(1£>&"Ii)v(^vQ&(1CV"1d) VB&A&"U. 3.A=>(D=>Q.

4.P-J Q, >70, f v lg [:PkQ.

5.Bee A cyib isB , а некатпрые С суть В или некоторые С суть

6.ЧхЧуР{х,у)=й1х!‘[х,х).

7.Л~ЭуЧхР(х,у'р^ЧтР(а,х), B=Vx3yP{x,y)^ ЗгЗуУх@(у:х.г).

8.Некоторые С не есть В. Все А суть не Д. Все В суть С. Сле­ довательно, все В суть А.

9.P-ccoab, Q-ccuabecabcdd.

10.P=cabc,Q^cabccdab.

11.Смотри условие идачи.

299

14.((ВД^ЛУ))&г, (N(y&x)yks.

15.А*пВ*,А*иСм,А*п{В*J C).

Вариант4

1. Если А ю й, а Я достаточно для С или ни Л не эквива-

оне С.

2. (^vlQ&f'U&OvBiOv^&lDvS&lDJ&UvOvSS^&lR

1.(4*С;*А&В&)С.

4. lPv'gvi?. P v .gvfff i ,^ R.

5. Ни одно С не естьД но всеЛ суть D, а вге Ясуть Сили А.

6.(3xP[i))vatfi(*)«a*№)ve(*)).

Л-ЛЭ >2(*.«.У)=*3

8.Все А суть не В, а некоторые Л суть С, слелошельпэ, ществуетЛ, ткихчго В ШГи С.

9.P-dilaab, Q~ddaabbbabcdd.

10.P=ddccc, Q=ddcccbccab.

|2 ,л>-|о. 217,1

13. (A=>B)o{(\A^Bj=>B).

\i. ((Wx'p(Ny))&i, ((ty)=>№))&j. !5.^eriC*B*wC* J ‘ u(2T,C*).

1.А тогда, когда В, а В только тогда, хогда С или А, недостаточно дп*С.

2.(Xvrt)&[5&1CvS&DvC&SvlB&D)&(lDv^)vB&4&lfl.

3. Л&0(,

4. PvQ, RvQ, R-JS. l«v>, ISvlg |= R&Q.