1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 4
Текст из файла (страница 4)
Данная РАМ допускает (воспринимает) язык в следующем смысле. Пусть на входной ленте находится цепочка з=а,а,... а„, причем символ а, расположен в первой клетке, а,— во второй и т. д., а в (и+!)-й клетке расположен Π— символ, который будет использоваться в качестве концевого маркера, т.
е. маркера конца входной цепочки. Входная цепочка з допускается РАМ-программой Р, если Р прочитывает все ее символы и концевой маркер, пишет ! в первой клетке выходной ленты и останавливается. Языком, допускаемым программой Р, называется множество всех цепочек (слов), допускаемых ею. Для входных цепочек, не принадлежащих языку, допускаемому программой Р, оиа может напечатать на выходной ленте символ, отличный от 1, и остановиться, а может даже и не остановиться вообще.
Легко показать, что язык Ьея)п геап г1; И г1(О 1Ьеп тег11е О е!зе Ьед!п г2 — г1; гЗ г1 — 1; тгЬ!1е гЗ > О бо Ьея)п г2 — г2 и г1; гЗ вЂ” гЗ вЂ” 1 епб; итИе г2 епб епб Рнщ 1.6. Программа лля л" на Упрощенном Алголе. ГЛ.
С МОДЕЛИ ВЫЧИСЛЕНИИ Соответствующие операторы на Упрощенном Алголе РАМ-программа геаг! г! !! г!(О !пеп вг!1е О полож г2 -г! ' гз — г1 — 1 пока вЫ!е гз) О г!о г2 — г2 а г! гз гз — ! пока 2 ит!!е г2 Ряс. 1.7. РАМ-программа для и". допускается некоторой РАМ тогда н только тогда, когда он рекурсивно перечислим. Язык допускается РАМ, останавливающейся на всех входах, тогда и только тогда, когда он рекурсивен (о рекурсивных и рекурсивио перечислимых языках см. Хопкрофт, Ульман [1969!). Рассмотрим две программы для РАМ.
Первая определяет функцию, вторая допускает язык. Пример !.1. Пусть !' и" для всех целых и) 1, '( О для п = О. 20 КЕАР ЕОАР ЗОТЕ %К!ТЕ Д Ь'МР 1.0АР ВТОКЕ 1.0АР ЯЗВ ВТОК Е 1.0АР ЛОТЕ д (!МР продолж: 1.0АР М(! Т ЬТОК Е 1.0АР Я!В ВТОКЕ Л1МР конецпока: %1!1ТЕ конецесли: НА1.Т 1 1 полож =О конецесли 2 ) 3 продолж конецпока Ьед1п 1-О; ген х; чгЬ11е хФО Г!о Ьеи!п !1 хчв! 1Ьеп с! — |! — 1 е!ае |! !1+1; геае! х еп|1; !! !!=0 1Ьеп хгг!1е 1 еп|! Рнс. |,8. Распознавание пеночек с одинаковыми числами вхождений | н 2.
Соответствующие операторы на Упрощенном Алголе РАМ-программа =О 2 с! О геае! х АРЬ!1е х~:О е!о 1 1 конецпока пока: 1 =1 конецесли И х~! 1Ьеп д — с! — 1 один: е1ае Г! -с!+! геае! х конецесли: пока 2 коиецпока: выход !! |!= О 1Ьеп мт!1е 1 выход: Рнс. 1.9. РАМ-программа, соответствующая алгорнтму на рнс. |.8. 81 1.0АР ВТОЙ Е НЕАР 1.0АР дЕЕКО 1.0АР ь!1в ЗХЕКО 1.0АР ЯЗВ ВТОРОЕ димр 1.ОАР АРР ВТОР Е БЕАР ,1!ЗМР ЕОАР ЗУЕВО НА!.Т %К! ТЕ НА!.Т !.3. ВЪ|ЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ РАМ ПРОГРАММ гл.
ь моднли вычислвиии Программа на Упрощенном Алголе, вычисляющая 1(п) путем (и — 1)-кратиого умножения на п, приведена на рис. 1.6'). Соответствующая программа для РАМ дана на рис. 1.7. Переменные г1, г2 и гЗ хранятся в регистрах 1, 2 и 3 соответственно. Мы специально не сделали очевидных улучшений программы, чтобы яснее было видно соответствие между рис. 1.6 и 1.7. Пример 1.2. Рассмотрим РАМ-программу, которая допускает язык во входном алфавите (1, 2), состоящий нз всех цепочек с одинаковым числом вхождений 1 и 2. Эта программа считывает каждый входной символ в регистр 1, а в регистре 2 оставляет разность с( между количеством символов 1 и 2, поступивших до текущего момента. Встретив концевой маркер О, программа сравнивает й с нулем и в случае совпадения печатает 1 и останавливается.
Мы считаем О, 1 и 2 единственно возможными входными символами. Основные детали алгоритма приведены в программе на рис. 1.8, Эквивалентная программа для РАМ дана на рис. 1.9; х хранится в регистре 1, а й — в регистре 2. ( ) 1.3. ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ РАМ-ПРОГРАММ Двумя важными мерами сложности алгоритма являются временная и емкостная сложности, рассматриваемые как функции размера входа. Если при данном размере в качестве меры сложности берется наибольшая из сложностей (по всем входам этого размера), то она называется сложностью в худшем случае.
Если в качестве меры сложности берется "средняя" сложность по всем входам данного размера, то она называется средней (или усредненной) сложностью. Обычно среднюю сложность найти труднее, чем сложность в худшем случае. Нужно еще принять некоторое предположение о распределении входов, а реалистичные допущения часто бывает трудно сформулировать математически. Мы будем уделять основное внимание худшему случаю, поскольку его легче исследовать и он имеет универсальную приложимость.
Однако следует помнить, что алгоритм с наименьшей сложностью в худшем случае не обязательно имеет лучшую сложность в среднем. Временная сложность в худшем случае (или просто временндя сложность) РАМ-программы — это функция 1(п), равная наибольшей (по всем входам размера п) из сумм времен, затраченных на каждую сработавшую команду.
Временная сложность в среднем— это средине, взятое по всем входам размера п, тех же самых сумм. Такие же понятия определяются для емкости памяти, только вместо "времен, затраченных на каждую сработавшую команду" надо подставить "емкосгей всех регистров, к которым было обращение". '! Описание упрощенного Алгола сн. в рввд. !.З. ьа. вычислительная сложность иам-программ Чтобы точно определить временную и емкостную сложности, надо указать время, необходимое для выполнения каждой РАМ- команды, и объем памяти, используемый каждым регистром.
Мы ассмотрим два таких весовых критерия для наших программ. ри равномерном весовом критерии каждая РАМ-команда затрачивает одну единицу времени и каждый регистр использует одну единицу памяти. Если не оговорено противное, то сложность РАМ- программы будет измеряться в соответствии с равномерным весовым критерием.
Второе определение, иногда более реалистичное, принимает во внимание ограниченность размера реальной ячейки памяти и называется логарифмическим весовым критерием. Пусть 1(1) — логарифмическая функция на целых числах, заданная равенствами ( 1оа111./ +1, 1ФО, 1 (1) = 1, 1=0. Таблица на рис. 1.10 дает логарифмические веса 1(а) для всех трех возможных видов операнда а. На рис. 1.11 приведены веса РАМ-команд. Здесь учитывается, что для представления целого числа а в регистре требуется ( 1оя и ~+1 битов. Регистры же, напомним, могут содержать произвольно большие целые числа. Логарифмический весовой критерий основан на грубом допущении, что цена выполнении команды (ее вес) пропорциональна длине ее операндов. Например, рассмотрим вес команды АИЭе1.
Сначала мы должны определить трудность декодирования операнда, представленного адресом. Просмотр целого числа 1 занимает время 1(1). Затем, чтобы прочитать содержимое с (1) регистра 1 и определить его местоположение, понадобится время 1(с(1)). Наконец, считывание содержимого с(1) требует время 1(с(с(1))). Так как команда АОО «1 прибавляет целое число с(с(1)) к целому числу с(0) в сумма- Вес 1(а) Операнд а 1(1) 1(1) +1(с(1)) 1(!) + 1(с(1)) + 1(с(с(1))) 'ис. 1ЛО. Логарифмические веса операидов.
гл, к модели вычислении Команда Вес Рис. !.11. Логарифмические веса команд РАМ, где Е(а) — иес операида а, а а обозначает метку. торе, то ясно, что разумным весом, который следует придать команде АО!) «Е, является Е(с(0))+Е(Е)+Е(с(Е))+Е(с(с(Е))). Определим логарифмическую емкостную сложность РАМ-программы как сумму по всем работавшим регистрам, включая сумматор, величин Е(х~), где х1 — наибольшее по абсолютной величине целое число, содержавшееся в Е-м регистре за все время вычислений.
Само собой разумеется, данная программа может иметь радикально различные временные сложности в зависимости от того, какой используется весовой критерий — равномерный или логарифмический. Если разумно предположить, что каждое число, встречающееся в задаче, можно хранить в виде одного машинного слова, то годится равномерная весовая функция. В иной ситуации для реалистического анализа сложности более подходящим может оказаться логарифмический вес. Оценим временную и емкостную сложности РАМ-программы из примера 1.1, вычисляющей и".
При подсчете временной сложности будет доминировать цикл с командой М(ЕЬТ. Когда зта команда выполняется Е-й раз, сумматор содержит а', а регистр 2 содержнтп. Всего команда М1)ЬТ выполняется и — ! раз. При равномерном весовом критерии каждая команда М(ЕЬТ требует одну единицу вре- 24 1. ЬОАО а 2. ИСТОКЕ г ВТОКЕ еЕ 3. АОО а 4. Я)В а 5. М(.ЕЬТ а б.
111Ч а 7. КЕАЕ) Е КЕА1) мЕ 8. %К!ТЕ а 9. ЖМР Ь !0.,)ЙТХ Ь 11. )ЕЕКО Ь 12. НАЬТ Е(а) Е(с(0)) + Е(Е) Е(с(0)) + Е(Е) + Е(с(Е)) Е(с(0)) + Е(а) Е(с(0)) + Е(а) Е(с(0)) + Е(а) Е(с(0)) + Е(а) Е(вход) + Е(Е) Е(вход) + Е(Е) + Е(с(Е)) Е(а) 1 Е(с(0)) Е(с(0)) 1 !.В. ВЫЧИСЛИТИЛЬНЛЯ СЛОЖНОСТЬ РАМ-ПРОГРАММ Равномерный вес Логарифмический вес Для этой программы равномерный вес реалистичен только в ситуации, когда столь большое целое, как а", записывается в виде одного машинного слова. Если и превышает то, что можно представить одним машинным словом, то даже логарифмическая временная сложность до некоторой степени нереалистична, поскольку она предполагает, что два целых числа ( и 1 перемиожаются за время 0 (1 (!)+1(!)), а возможность этого неизвестна. Для программы из примера 1.2 в предположении, что п — длина входного слова, временные и емкостные сложности таковы: Равномерный вес ~ Логарифмический еес Временная сложность Емкостиая сложность О (а) О (!) О (л' )од а) О (л )од М) Для этой программы в ситуации, когда и больше того, что можно запомнить в одном машинном слове, логарифмический вес оказыва- ется вполне реалистичным.
мени, и поэтому на выполнение всех команд МП).Т тратится время 0(п). При логарнфмическом весовом критерии гся команда М(Д.Т занимает время 1(п!)+1(п) ж(!+1) !Он а, так что время выполнения всех команд М(.Д.Т равно а-! ~ (!+1)!Они, 1=! что составляет 0(ла 1оя а). Емкостная сложность определяется числами, которые хранились в регистрах от 0 до 3. При равномерном весовом критерии емкостная сложность составляет 0(1), а при логарифмическом— 0(п 1ои л), поскольку наибольшее целое число среди содержавшихся в этих регистрах есть и", а 1(ла)жп 1оя л. Таким образом, сложности для программы из примера 1.1 таковы: гл. ь модели вычисления 1.4.
МОДЕЛЬ С ХРАНИМОЙ ЛРОГРАММОЙ Поскольку РАМ-программа не хранится в памяти РАМ, она не может изменять себя. Сейчас мы рассмотрим другую модель вычислительной машины, называемую машиной с произвольным доступом н памяти и хранимой программой (или, иначе, рагнодоступной адресной машиной с хранимой программой — сокращенно РАСП), которая отличается от РАМ лишь тем, что ее программа находится в памяти и может изменять себя. Набор команд для РАСП совпадает с соответствующим набором для РАМ во всем, кроме косвенной адресации, которая исключена, ибо она не нужна. Мы увидим, что РАСП может моделировать косвенную адресацию путем изменения команд в процессе выполнения программы.
Общая структура РАСП также подобна структуре РАМ, но только предполагается, что РАСП-программа находится в регистрах памяти. Каждая РАСП-команда занимает два последовательных регистра памяти. Первый регистр содержит код операции, второй — адрес. Если адрес имеет вид =1, то первый регистр будет содержать (в закодированном виде) указание на то, что операнд является литералом, а второй регистр будет содержать А Для кодирования команд берутся целые числа. На рис. 1,12 представлено одно возможное кодирование.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
