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

Являются ли самоприыснимыми следующие алгоритмы

а) f[ = {“ ^ ^ (u,fc* Л) б) fj - {Л Л

в)^= {Ш .> Ьв^

д) К ;= |м -> .|(* ,и л ) е) = jl —>■!l(*,l е Ji)

25. Дана машина Тьюринга

Чъ'Ц\

?0-

На ленте записано слово J° - 1 и читающая гсшпвка находится над зтнм словом, а машина находится во внутреннем состоянии </о, инвче - задана начальная конфигурация gt l. Описать работу машнны Тьюринга-

26. Задана машинаТмирннгв

qM qt ?оbSfit

и начальная конфигурация сцР. Применима ли данная машина к этой

конфигурации, гели
I )Р=ааЬЬЬщ	1)Р=сЬЬ-,
3) P--acb;	4)Р=Ьас.

Earn машинаприменимаксловуЯ, точемуравняетсярезультат? 27. Пусть ^=-(1,2,3,...,9,0). Построить машину 'Люриита Г», ко­

торая любое число и (в десятичной чаоиси) перерабатывала оы в нуль, т.е. а д н з .

28. Пусть Л-{ 1,2,3,...,9,0}. Построил, машину Тьюринга Г,, ко­ торая любое число п (в десятичнойзаписи) перерабатывала бы вчисло )-!+(,т.е. Г|(м)=и+1.

271

29. Построй» машины Тьюринга Г| и Го, перерабатывающие Л1СЙыв числа п а 0 и я+1 соответственно, при условии, что числа запи­

саны только с использованием алфавита	1}, т.е. п обозначено сло­
вом

30.Составить команды машины Тьюринга, когирня будет счи­ тал записанныеподряд (без пропусков) палочки и запишет их число:

1)в двоичной системе счисления;

2)в троичной системе ечнелеки»;

3)в системе счисления с основанием л.

31.На тенте записано число в системе счисления с основанием

п.Составить команды машины Тьюринга, которая запишет число:

1)непосредственно следующее заданним;

I)непосредственно предшествующее данному.

32.На ленте записано некоторое число слов Р\,Ръ... Рц В алфа­ вите А, разделенных звездочками («. Ч.А). Составить команды маши­ ны Тьюринга, которая счигала быколичество слов и записывалабы их

1)в алфавите Ц |;

2)в двоичной систшесчислепии;

3)в троичной системе счисления;

4)в системе счисленил г основанием п.

33.Построить машину Тьюринга, которая приписывала бы справа от любого слова? в алфавите Л слово cab(a.beA).

34.Выяснить, в какое слово перерабатывается слово т*г ма­ шинойТьюринг»:

qo'Stfo	9:'%]	q-'lg2
goSjfiiji	fliSolft
	qi!Lqi

(начальной конфигурацией яалиется конфигурация q<,m* п ). 35. Построитьмашину Тьюринга для умножение на 2.

272

36.Построить машину Тьюринга для вычисления целой части частного приделении на 3.

37.Построитьмашину Тьюринга для вычисления |*-у|.

38.Наценте записано некоторое число палочек |б:з пропусков). Составить команды машины Тьюринга, которая стирает каждую тре­ тью палочку, двигаясь слева направо, стирает каждуютретью палочку из оставшихся и т.д. При этом машина должна указать последнюю стираемуюпалочку

39.МашиныТьюринга, заданные с помощью команд айда

qSMr f e t e q£jL?r,

можно задатьс помощью пятисимнольных командвила

объединяющих две команда и q*Si@q„ где Q=R, Q -l или

Q-S; при Q=S читающая головка не передвигавгея ни влево и НИ вправо.

Выяснить, применимыли следующие машины Тьюринга к за­ данным слонам:

1)qiflqfiR

qn\qilR

(JiQqiOR

q-,Gq*W!

jjlfcU? Р|=1111)Ш=13Ш\ Pj-10[l)llJl;

2)

qiOqilL qilqAS

f “ lJ013, ?2=1‘ ,

273

3)qtfiijtMf qt,\q№

qi\q%\L

¢0^1/. /’i-lUl2 ?2*lV l.

40.Построить в алфавите {0.1} wanimiy Тьюринга о шписюаволькыш комягщами. обладающую следующимсвойством

1) машина применима к любому непустому слову к алфавите

{0,1};

2) машина не применима ни к «акочу непустому слову в алфа­ вите (0,1} и зона работына каждомслове-бесконечна*;

3) машина не применима ни к какому непустому слову в алфа­ вите {0,1} и зона работы на каждом слове аграмичена одним н темже числом ятеок, не зависящим отвыбранного слова;

4) машина применима к словам вида 1 , »21, в ие применима словам вида 1'’"'“, иг!, ¢=1,2.

41.Постронгь в алфавите {0,1} машину Тнорннга с пягисимвсльными командами, дереволя1цуюконфигурациюАГ0 вК’:

1)		Л*“?*Г0Г
	(*21);
2)	K ,- ?0OV	Л-^^fO l]
	(tel);
3)	t f j - j y i	^=9*120
	(«21).
42.	Машину Тьюринга можно задать с помощмо сяел

На пересечении l-ro столбца иj -Ъстроки(й0,_/>0) записываете# выражение q&Q, являющееся частью команда

если такая команда есть, Если команды, начинающейся с q,S;, нет, то на пересеченииi-го столбца и/-й строки ставится прочерк.

По гапанной машине Тьюринга и начальной конфигурации Кп нлй1и заключительную конфигурациюдли следующих вариантов.

I)

а)Ло=1^й] 5) !01; а) К»=1Од,!'".

43, Доказать, что следующие функциипримитивно-рекурсивны:

Глава 7. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ

СПОМОЩЬЮ АЛГОРИТМОВ

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

Вглаве 6 рассматривались проблемы принципиальной возмож­ ностивычистений ибили исследованыразличные подходык понятию вычиспичооти. При этом не обращалось внимание на ресурсы време­ ни н памяти. Однаот существуют зада'Ш, которые тефвтичкки раз­ решимы, но при практической реализации трфбуют столь больши*

вычислении, тго нх решение Практически неосуществимо. Следова­ тельно, принципиальна* алго[]Н1«ическая разрешимость гше не озна­ чает практическую реализуемость. Рассмотри некоторые >дракт»ри-

Считаем, что привычислениииспользуем алгоритм.
Различаю'! сложность описания алгоритма и исходных ляешых,
и аюжность примененияалгоритма л всходт.ш данным.
Сложность списании алгоритма зависит or выбора того или
иного способа задания алгоритаа. Если такой способ аыбран (машина
Тыоринга, нормальная алгоритм или рекурсивное задание и т.д.), то
сложность алгоритмаможет бить введена какдлина з а			п алгоритмаи с и	п
или как длина в с т	р еспециальныхч а ю	выраженийщ и х	и»т.а. Н а
мер. дня машины Тыорннга ее сложность может быть введена как
число бум внешнегои	внутреннего алфавитов.
Введем следующее определение. Говорят, что неотрицательная

функция g(«) есть 0(f!nj), если существует такал постоянная с, что g(n)£cfln) для всех, кроме конечного (возможно пустого) иножестю значенийв, «с (0,1,2, 3,...). В этом случае записываем: 5(ир0(/(«)).

276

Сложность исходныхданных понимается гак длина (размер) их записи. Что такое размер входа? Все зависит от того, что ямяетси входом. Размером входа, в общем случае, считают число символов, с помощьюкоторых записав вход.

Пусть входом шляется целое число. Считаем, что число пред­ ставлено в системе счисления с некоторым фиксированным основани­ ем. D .них системах число символов, необходимыхдля представления целого числа я, равно ]log,n[, где ,462 - основание системы, а М обозначает наименьшее целое q, такое, что q>х. Известно, что loleiPtiogj/il/flog^). здесь lagyt является константой при фиксиро­ ванном А. Таким образом, число символов, необходимых дли прелстаэнения целого числаиесть0(logi«).

Рассмотрим второйпример. Пустьтребуется перемножигь квиратньге п/п патрицы Л и В. Ясно, т а подходящей мерой сложности исходных данных будет число, пропорциональное I - пг, ииеега в виду, 'Гго для запоминания отдельного числа (злемеита матрицы) выэеленопределенныйобъем памяти.

Во многих задачах вколом явстета граф. Граф G-(KX) можно, например, задатьеш матрицей смежностейAQ-[H^)рачмера | V\ х |у |.

Где я,=1, если ребро (v,,v,)e X и	<з,-0 s противном случае.
Ясно, что максимальное число	возможных ребер равно

А/= С||,;“0(| v\ ‘), Однавю многие графы являются разреженными,

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

При задании списков смежностей для каждий вершикы v&V быоисьтаегч мнокестао A(v) {A(v)<r.V) вершин, смежных еv(рис. 7,1).

-<«-{»3, Щ}; ц, У():

лСчМ*!.»*};

<4(vj)-£vi. У и}. '

Ряс.7.1

277

Размер этого представления зависит от суммы длин списков, Каждое ребро вносит вершин}' в два списка, поэтому сумма длин спвскоа содержит l\x\ элементов. На для различении вершин, как пра­ вило. вводятся числовые индексы. Так как имеется I У\ вершин, то длЯ индексов потребуется 0(1о& | У\) двоичны* или десятичных раз­ рядов. Следовательно, при таком представлении графа G=(V,X) потре­ буется 0(UI logii V\) символов.

Более экономной записью информации в ячейках памяти ЭВМ (выделенного для одного числа) можно добиться. что для задания графа требуечса 0( |jf|) ячеек памяти.

Сложность шчислсний с помощью алгоритма понимается ка* функция от размера входа алгеретма. Для оценка сложности вычислений сутестпугт много критериев. Важными критериями яв­ ляются; временная сложность. характеризующая преш, затраченное на вычисление, и емкостная (ленточная) сложность, ха­ рактеризующая необходимую для вычисления память, используемую для хранения промежуточных результатов.

Кроме того, сложность вычислений зависит от способа форму­ лировки задачи. В качестве примера рассмотрим следующую задачу. Требуется узнать, является ли натуральное число п простым или составным. Чтобы анализировать сложность задачи, надо выяснить, как задано число п. Если п задано как произведение сооих простых делителей: л-(^)^(^)4..(3,)^, fc? 0. то задачинет есобше.

Следует обрапгъ внимание на то обстоятепьство, что одной и той же задаче woiyr соответствовать разныеязыки, представляющие условия или аходаые данные задачи. Это связано со способами коди­ ровки данных. Из всех языков, представляющих исходную задачу, выбирается «разумный языки или разумный способ кодировки ее ус­ ловий. Таким чбразом, каждой задаче соответствует “разумный язык”, ее представляющий.

278

§2. Временная сложность вычислений (алгоритма)

Временная сложность вычислений (алгоритма) характеризует число операций для решения задачизаданногоразмера.

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

Определим временную июжноапь алгоритма как число опера­ ций в худшем случае по всемвходамразмера(длины) п.

Кроме меры сложности, в наихудшем случае вводят временную сложность алгоритмаА есреднем навходеразмера я;

М М " Z Ж)цИ(«.)).

здесь р(с1,) - вероятность иоааления задачи а„ цЙ(и;)) - чиило операции, аэтрачиваемых ajriopi-nwox на решение индивидуальной задачи а,; Р, - множество рассматриваемых задач размера

чР„-{а,}.

При изучении сложности алгоритма е основном интересуются его поведением при применении его к очень большим входам. Разли­ чив между сложностями 10«J н 9п' считаются несущественными, бо­ лее важен показатель :тепени. а не коэффициент. Сложность алгорит­ ма оценивается асимптотической статностью, т.е. порядком роста числа ипврашй при неигранйчвином рога размера входа. Например, если вход размера и обрабатывается за время сл!>где с - некоторая постоянная, то сложность этого алгоритма есть 0(п2), т.е. постоянная г не содержится в оценке. Для практических задач величина этого ко­ эффициента может быть важна, если онн различаются существенно. Если время работы алгоритмов /11 иА2 пропорционально, гапример, 11)1V и Or?соответственно, то практическоеиспользование алгоритма АI проблематично.

Для решения выбранной задачи иногда можно использовать различные алгоритмы.

279

Пол щ>емснной сложностью задачи понимается временная сложность неилучшего алгоритаа, твестнога для Се решения.

Выясним, как изменяется эффективность различных алгоритмов с pot юм быстродействия ЭВМ, на которых реализуются эти алгорит-

Пусть имеем 5 алгоритмов различной сложности для решения одной И той жв задачи Положим, что каждое действие алгориша осуществляется за 1 млс. Характеристики алгоритмио приведены втабп.7.1 [29].

Из табл. 7.1 видно, что увеличение времени решения задачи, например с одной секунды до одного часа позволяет для алгоритмам увеличить разкер решаемой задачи * 36000 раз, а для алгоритма /(5 только я 2,33 раза,

Предположим, что быстродействие ЭВМ возросла R 10 pa.i. В табл. 7.2 показано, как при этом порастут рпимсры входов [29].

Tabаицо7.2

280