1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 7
Текст из файла (страница 7)
Например, решая задачу выоора пути в графе со 100 узлами можно было бы для представления наличия или отсутствия пути из данного узла а в каждый из узлов использоватьдвоичиыевекторы длины !00, а именно ыю позицию в векторе для узла и занимает 1 тогда и только тогда, когда существует путь из а в оь В этой же задаче можно также использовать целые числа для счета и индексации, например, и они, вероятно, были бы размера числа 100. Таким образом, для целых чисел требовалось бы 7 битов, тогда как для векторов — 100 битов. Хотя это сравнение и бросает некоторую тень на вычисления а двоичными векторами, большинство вычиолительных машин выполняют логические операции на двоичных векторах, составляющих полное машинное слово, за одну команду.
Поэтому двоичные векторы длины 100 можно было бы обрабатывать за три или четыре шага (вместо одного для чисел). Тем не менее на результаты о временной и емкостной сложностей алгоритмов при применении модели с двоичными векторами, мы должны смотреть еит угала за!!э '), ибо размер задачи, прк котором модель становится нереалистичной, в этом случае много меньше, чем в случае моделей РАМ и неветвящихся программ. Порядок величин при применении модели с двоичными векторами мы будем обозначать через Одв.
е. Дерево» решений Мы рассмотрели три модификации РАМ, игнорирующие команды разветвления и учитывающие только те шаги программы, которые включают арифметический счет. В некоторых задачах удобно в качестве основной меры сложности брать число выполняемых команд разветвления В случае сортировки, например, выходы совпадают ') Буквально (с лип.) — с круиннкой олн; в оереноснон смысле с кровной, язве~ельне. Прим. рео. ЗУ гл.
~ модели вычислвнии Рис. 1.18. Дерево решений. со входами с точностью до порядка. Поэтому разумно рассматривать модель, в которой все шаги дают разветвления, возникающие в результате сравнения двух величин. Обычно программу, состоящую из разветвлений, представляют в виде двоичного дерева '), называемого деревом решений. Каждый внутренний узел представляет один из шагов решения. Тест, представленный корнем, выполняется первым, и затем "управление" передается одному из его сыновей в зависимости от исхода теста. В общем случае управление переходит от узла к одному из его сыновей (причем выбор в каждом случае зависит от исхода теста в этом узле), до тех пор пока не будет достигнут лист. Нужный выход находится иа достигнутом листе.
Пример 1.6. На рис, 1.18 изображено дерево решений для программы, сортирующей три числа а, Ь и с. Тесты указаны заключенными в овал сравнениями в узлах; управление переходит влево, если ответ на тест — "да", и вправо, если — "нет". Д Временная сложность дерева решений равна высоте этого дерева как функции размера задачи. Обычно мы хотим измеритьнаибольшее число сравнений, которые приходится делать, чтобы найти нужный путь от корня к листу.
Порядок величин при использовании модели деревьев решений (сравнений) мы будем обозначать через Ос. Заметим, что общее число узлов в дереве может значительно превосходить его высоту. Например, дерево решений для сортировки л чисел должно содержать по крайней мере п1 листьев, хотя его высота может быть л 1оп и. ') По поводу определений, касаюпшкся деревьев, си. равд. 2.4. ье. пвостиишдя модель вычислении млшиид тьюринга т.6. ПРОСТЕЙШАЯ МОДЕЛЬ ВЫЧИСЛЕНИЙ: МАШИНА ТЬЮРИНГА Лля доказательства того, что для вычисления данной функции требуется какое-то минимальное время, нужна некоторая модель, столь же общая, как те модели, которые у нас были, но более простая. Система команд должна быть ограничена, насколько возможно, хотя эта модель должна быть в состоянии не только вычислить все то, что может вычислить РАМ, но и сделать это "почти" так же быстро.
Под словом "почти" мы будем подразумевать "полиномиальную связанность". Определение. Говорят, что неотрицательные функции Гт(п) и /я(п) полиномиально ггяэпна (энэигалгнтна), если найдутся такие полиномы р,(х) и р,(х), что для всех п справедливы неравенства /~ (п)(~рь Дт (п)) н 1а (п)~(рв Ч~ (п)). Пример 1.7. Две функции гт(п)=2пя и г',(п)=пь полиномиально связаны: можно взять р,(х)=2х, ибо 2п*(2п'„и р,(х)=х', ибо п'((2п')'. Но п' и 2" не являются полниомиально связанными, так как нет такого полинома р(х), что р(па))~к для всех и.
() В настоящее время единственный класс функций, для которых мы можем применить такие общие вычислительные модели, как машины Тьюринга, чтобы получить нижние оценки вычислительной сложности, составляют "быстро растущие" функции. Например, в гл. 11 будет показано, что некоторые задачи требуют экспоненциальные время и память. (Функция )'(и) называется энспонгнциальной, если существуют такие постоянные с, О, /г,)1, с;ьО и й;ь1, что с~"яЦ(п)(стй.," для всех, кроме конечного числа, значений и.) Относительно полиномиальной связанности все экспоненциальные функции, по существу, одинаковы; любая функция, полиномиально связанная с экспоиенцнальной, сама экспоненциальна. Таким образом, это побуждает нас использовать простую модель, для которой временная сложность задач полиномиально связана с их сложностью на РАМ.
В частности, модель, которую мы будем применять, а именно многоленточная машина Тьюринга, может потребовать (у(п))' шагов '), чтобы сделать то, что РАМ прн логарифмической весовой функции делает за 1(п) шагов, но не больше, Итак, временные сложности на РАМ и машинах Тьюринга, как мы увидим, полиномиально связаны.
Определение. А(ноголгнточная машина Тьюринга (МТ) изображена на рис. 1.19. Она состоит из нескольких, скажем А, лент, ') На самом деле верка более инакая оценка 0(11(п)1ой/(л) !ой )ой /(п))а ), ио мы интересуемся оцеиками с точностью до оолииомов и иас вполне устроит реаультат с четвертой стецеиью (см. равд. 7.5).
гл. ь модели вычислении Рис. 1.!9. Многоленточная машина Тьюринга. бесконечно простирающихся вправо. Каждая лента разбита на клетки, каждая из которых содержит один из конечного числа символов на ленте. Одна клетка на каждой ленте обозревается головкой этой ленты; головка может считывать с ленты и записывать на нее. Работа машины Тьюринга определяется простой программой, называемой управляющим устроЫпвсм. Оно всегда находится в одном из конечного числа состояний, которое можно рассматривать как номер текущей команды в программе. Один шаг вычисления на машине Тьюринга состоит в следующем. В соответствии с текущим состоянием управляющего устройства и символами на лентах, обозреваемыми (т.
е. находящимися под) каждой из головок, машина Тьюринга может выполнить некоторые или все из следующих операций: !) изменить состояние управляющего устройства, 2) напечатать новые символы на лентах вместо старых в каких- нибудь или во всех клетках под головками, 3) сдвинуть какие-нибудь или все головки независимо друг от друга на одну клетку влево (!.) или вправо (м) либо оставить на месте (Я). Формально й-ленточная машина Тьюринга задается семеркой © Т, ), б, Ь, д., д~), где !) Я вЂ” множество состояний, 2) Т вЂ” множество символов на лентах, 3) 1 — множество входных символов, !охТ, 4) Ь вЂ” пустой символ, Ь Е Т вЂ” ), 5) а,— начальное состояние, ьо. пгостеяшля модель вычислении: мхшинл тьюгингл 6) 01 — заключительное (или допускаюшее) состояние, 7) б — фупкиия переходов, она отображает некоторое подмножество множества ЯхТ" в Ях (Тх(1., В, 8))', т.
е. по произвольному набору из состояния и (г символов на лентах она выдает новое состояние и я пар, каждая нз которых состоит из нового символа на ленте и направления сдвига головки. Пусть 6(а„аи ам..., аь)=(д', (а'„г1,), (а„'д,),..., (а,', д,)) и машина Тьюринга находится в состоянии а, а ее головка на 1.й ленте обозревает символ ао 1н=(~А. Тогда за один шаг зта машина Тьюринга переходит в состояние д', заменяет а~ на а; и сдвигает головкУ на 1-й ленте в напРавлении (или в соответствии с) ди 1<1(~Й. Машину Тьюринга можно приспособить для распознавания языка.
Символы на лентах такой машины включают алфавит рассматриваемого языка (его буквы играют роль входных символов), пустой символ, обозначаемый Ь, и, возможно, другие символы. Вначале на первой ленте записано слово из входных символов по одному на клетку, начиная с самой левой. Все клетки справа от клеток, содержащих входное слово, пусты. Все остальные ленты целиком пусты. Слово из входных символов допускается (воспринимается) тогда и только тогда, когда машина Тьюринга, начав е Рно. 1.20. Работа машины Тьюринга над цепочкой 01!1О. ГЛ. |. МОДЕЛИ ИЪ|ЧИСЛЕИИИ работу в выделенном начальном состоянии (головки при этом находились на левых концах своих лент), сделает последовательность шагов, которые в конце концов приведут ее в допускающее состояние.
Языком, допускаемым данной машиной Тьюринга, называется множество всех слов из входных символов, допускаемых в описанном только что смысле. Пример 1.8. Двухленточная машина Тьюринга на рис. !.20 распознает палиндромы ') в алфавите (О, 1) следующим образом.
1) Первая клетка на ленте 2 отмечается специальным знаком х, и вход копируется с ленты 1, где он записан вначале (рис. 1,20, а), на ленту 2 (рис. 1.20, б). 2) Затем головка на ленте 2 сдвигается к х (рис. 1.20,в). 3) Повторяется такая процедура; головка на ленте 2 сдвигается вправо на одну клетку, а на ленте 1 — влево на одну клетку и соответствующие символы сравниваются. Если все символы совпадают, то вход является палиндромом и машина Тьюринга доходит до допускающего состояния д,. В противном случае в некоторый момент очередной шаг машины Тьюринга будет не определен, а она остановится, не допустив входного слова.
Функция переходов соответствующей машины Тьюринга приведена на рис. 1.21. Е) Работу машины Тьюринга формально можно описать с помощью омгновеииых описаний". Мгновенным описанием (МО) й-ленточной машины Тьюринга М называется набор (аи |х„..., а„), где а, для каждого | представляет собой слово вида хну, причем ху — слово на 1-й ленте машины М (пустые символы, стоящие справа от его правого конца, опускаются), а д — текущее состояние машины. Головка на |-й ленте обозревает символ, стоящий справа от д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
