markov_teorija_algorifmov (522344), страница 32
Текст из файла (страница 32)
Г. Жарову в [!! (см. также [2)) удалось построить удваивающий алгорифм со сложностью 5п+С, и показать, что дальнейшее улучшение мультипликативной константы прн и здесь невозможно. Соответствующее усиление получила прн этом и общая теорема Остроухова. ") Аналогичный подход использован А. Н. Кол ма го р ов ы м 121 длн определенна слогкноснгн конечного конструкмнаного обагкгпа. 164 НОРМ*ЛЬНЫВ АЛГОРИФМЫ 1гл. Рп 4. Удваивающий алгорнфм 5А мы построили как нормальный алгорифм в трехбуквенном расширении алфавита А.
Впоследствии — в $ 41 — мы покажем, что сравнительно простым приемом число „вспомогательных" букв здесь может быть уменьшено до двух (и — несколько сложнее — даже до единицы: см. 3 41.8.1). Однако в случае непустого А совсем обойтись без них невозможно. Покажем это. Пусть Й вЂ” нормальный алгорифм в алфавите А. Если схема Й содержит заключительные формулы подстановок, то для каждой такой формулы У вЂ” У мы вычислим разность [Р'а — [Уа и наибольшее из полученных таким образом чисел обозначим символом з(й). Если же схема алгорифма Й состоит только из простых формул подстановок, то определим з(й) „как-нибудь", например будем считать, что з (Й) равняется нулю.
з (Й) представляет собой некоторую сложностную характеристику алгорифма Й. Пусть А — рациональное число. Нормальный алгорифмй в алфавите А мы будем называть А-растягиваюи(ии, если для всякого слова Р в алфавите А такого, что й(Р) определено, (1) [й (р)а - ь.[ра (Здесь и далее до конца параграфа ~>, > и = будут означать обычные отношения порядка и равенства для рациональных чисел.) Имеет место следующее утверждение (Н. М. На горный [21, теорема 3.1): 4.1. Пусть и — рациональное число, большее единицы, и пусть Й вЂ” й-растягивающий нормальный алгорифм в алфавите А. Если Й применим к непустоиу слову Р, то з(й) Р (и — 1) [Р .
В самом деле, пусть й > 1 — рациональное число, и пусть й-растягнвающий нормальный алгорифм Й в алфавите А применим к непустому слову Р. Тогда для некоторого слова йг имеем (2) Й (Р) Х !Р". Одно из двух: либо (3) Й: Р~=Я7~, либо (4) й: Р)= %'. 1бб , взн УДВАИВАЮШИИ АЛГОРИФМ Если имеет место (3), то (5) й (йг) х йг :: и, так как йà †сло в А, ,," (6) [Ига) й [!у"а [(5) (!)1. Но [УРА=-.й.[ра>О [(2), (1)1, и потому 1~ )й [(6)], чего, однако, быть не может, так как по условию й > 1. Итак, имеет место (4), н, значит, существует слово Я в А такое, что й: Р~9 и (7) й: Я1 — ° !!г.
Рассмотрим заключительную формулу у .у, и потому (1О) С другой [)ра, [ра+ з (Й) стороны, Й (ф х яг [(7)1, и потому (11) Следовательно, [е' я'+. (Й) [вга > ь.[()а [(1)1 [(11), (1О)1 и (12) активную иа слове м' в схеме алгорифма й. Существуют такие слова К и Я в алфавите А, что (8) Я ~АУЛ, (9) %' Х Я'у'о.
Так как [Ра — [Уа(з(й), имеем [)Ра — Яа(з(й) [(9), (8)1, ОБРАЩАЮЩИЙ АЛГОРИФМ 1б7 1гл. Ри 1бб НОРМАЛЬНЫЕ АЛГОРИФМЫ так что РГа ~",~', + з (а) «(1О), (12)1 ь а(6) А — 1 (13) Но й (Р) Х 57 «(2)1, * г)ра ~ А «ра г(!)1 Й «Ра» (( ) ~(14), (13)) и потому (14) что дает и (й — 1) «Р ~ з(а) $32. Обращающий алгорифм 1. Построим нормальный алгорифм над алфавитом А, перерабатывающий всякое слово в алфавите А в обращение этого слова (317.3.2). Пусть и и 5 означают две различные буквы, не принадлежащие А.
Зададим нормальный алгорифм 9А в алфавите Амр сокращенно записанной схемой аи — ~а 1)а— Б — Ц) ()в а4ц т«а4 где $ и 11 пробегают алфавит А, что и требовалось доказать. Из 4.1 вытекает, в частности, невозможность построения в непустом алфавите А нормального алгорифма л, удваиваю- щего любое слово в А. В самом деле, такой алгорифм был бы 2-растягивающим, и, значит, для любого непустого слова Р в А выполнялось бы неравенство (Ра =з(л) (4.1!, что очевидным образом невозможно. Этот алгорифм и является искомым обращающим алго- рнфмом над алфавитом А, т. е. (2) Й~ (Р) х ~Р для всякого слова Р в А.
Этот факт легко может быть доказан по образцу доказа- тельства, проведенного в предыдущем параграфе. Поэтому мы лишь наметим здесь доказательство вкратце, предоставляя подробности читателю. Вообще, по мере того, как у читателя будет накапливаться опыт, мы будем делать доказательства менее подробными, не доходя, впрочем, в этом отношении до крайностей. Каки впредыдущем параграфе, Р, Я, Р будут обозначать произвольные слова в А, а 5, т« — любые буквы этого алфавита.
Нам потребуется операция Е над словами в А, которую мы определим равенствами (3) е(л) л, (4) е (Рб) е (Р) а5. Легко видеть, что (5) Е($) Хи$1(4), (3)1, Кроме того, правой индукцией по 1',! нетрудно показать, что (5) е(рд)хе(Р) е(Е «(3), (4)), Имеем 1.1. 6А. Рею) «-Яре(в. В самом деле, на слово РЕЯ) действует только послед- няя строка схемы (1). ч,'А РР « 'Р. В самом деле, первой действующей на Рр формулой в схеме (1) является формула р — ° . 1.3. $А: Опт«РЕ (Р) «- Ят«и5РЕ (Р) В самом деле, формулы, представленные первыми четырьмя строками схемы (1), не действуют на слово Царит«ре()г). Активна формула иб11 — ~1аб из пятой строки схемы. 1.4. $А'.
аИРЕ()т) «=Ои5РЕ()т), Доказывается правой индукцией по 9 с использованием 1.3. 1.5. $А, 'аде(Р) «=('«сне()7). Частный случай 1.4 при РХЛ. 1.5. 6„: РО«=()е([Р"). Доказывается правой индукцней по Р с использованием 1,1 и 1.5. 168 НОРМАЛЬНЫЕ АЛГОРИФМЫ 1гл. Ри В самом деле, при Р 1АЛ имеет место графическое равен- ство слов РЯ и ~Е([Р ) и тем более нужное нам утвержде- ние.
Предположим, кроме того, что для какого-либо Р ЭА. РЯ)=Юе([Р ) имеет место прн любом Я, и пусть | — произвольная буква. Тогда 9„: РЩ)=54~Е([Р ) [инд. предпол.] 1- ~Ее([Р") [1.1] 1= с,1а5Е ([Р ) [1.б] Х ОЕ(ЦР") [(б), (б)] х ое([Рб") [б п.з,2], т. е. в этом случае для любого Я 9А. РЫ~Яе([Р5 ). Таким образом, обе предпосылки применения метода пра- вой индукции выполнены. 9А Р) е(Р )' Частный случай 1.б при ДАЛ.
1.8. Если Р.ЛЛ, то,фА. аЕ(Р) 1- рЕ(Р). В самом деле, пусть Р ~Г Л. Тогда Р л. $Я, Е (Р) о я. Е (я) Е (~'1) х а5Е (Я) и аЕ (Р) лА аа$Е (Р). Легко видеть, что РА. .ас4Е (11) 1- 1)а$Е (9). Но Р ~Е(())-Г])ЕааЩЕ(Р). 1.8. ф,: 1)е(РФ~Рбе(а. Доказывается правой индукцией по Р. В самом деле, при Р мЛ имеет место графическое равен- ство слов 1)е (РЯ) и Р ре (Я) и тем более нужное нам утверж- дение. Пусть„кроме того, для какого-либо Р ч)А: ре(РЮ)-Р[)еЯ) имеет место при любом (с, и пусть | — произвольная буква. Тогда а1А, бЕ(РЩ ~= РНЕ($Я) [инд.
предпол.] х Рр 4е (Я) [(б), (бИ 1- РЯЕ(Я) [(1), строка 2] 1- РЯ~Е (1~) [(1), строка 3] и, следовательно, в этом случае для любого 9 'ЧА 1ЩРЫ) )= РЬРе (Я) сОА. Л 1- сс 1 — аа 1- ра 1 — Л. Теперь докажем утверждение (2). Пусть Р— произвольное слово в А.
Если Р пусто, то [Р также пусто, и тогда справедливость (2) вытекает из 1.Г1. Если же Р д.Л, то Е~: Р,)= Е ([Р") [1.7] 1- аЕ ([Р") [1.1] 1- ре ([Р") [1.8] ~ [Р Р [1.1()] [Р" [1.2], откуда 6А Р) '[~ 6А (Р) ~ [Р и, следовательно, что и заканчивает наше доказательство. 2. Легко усмотреть, что работу алгорифма $А в применении к исходному слову Р в А можно описать следующим образом. Сначала перед Р возникаег буква а. Она „приклеивается" к первой букве слова и „протаскивает" ее направо сквозь все буквы алфавита А. Затем перед получившимся таким образом новым словом снова возникает а.
Если слово Р еще не исчерпалось, то сс „приклеивается" ко второй его букве и тоже проносит ее сквозь все буквы алфавита А до ближайшей буквы а. Этот цикл повторяется до полного исчерпания Р. Обращение слона Р к этому времени оказывается фактически уже полученным 1!.71, правда, в слегка закодированном виде. Раскодирование (выбрасывание „лишних" вхождений а) начинается с того, что перед обрабатываемым словом еще раз возникает буква а. Теперь их оказывается рядом две, и первая из них превращается в ]1 И.81.
После этого р „бежит" по слову слева направо. перепрыгивая через буквы алфавита А 1(1), фц 1зз1 ОЬРАЩАЮЩИЙ АЛГОРИФМ 169 Таким образом, обе предпосылки применения метода правой индукции выполнены. 1.1о. Е,: бе(Р) ~Рб [1,8, Ехл]. 1.11.,В,: Л)= Л. Действительно, 170 НОРМАЛЬНЫЕ АЛГОРИФМЫ 1ГЛ. Гп строка 31 и стирая буквы а ((1), строка 2).
Добежав до конца слова и тем самым закончив чистку, () исчезает и на этом работа 9А заканчивается. (Фактически в нашем комментарии рассматривался общий случай непустого слова Р. Случай пустого Р рассмотрен в лемме 1.11.) Сложность, т. е. длина схемы алгорифма Арл, как нетрудно подсчитать, равна 8пз+бп+18, где л — число букв алфавита А. Обращающий алгорифм, построенный по методике Жарова ь), имеет схему длины 5п-' С (у Остроухова соответственно 1Оп+С,). 3.
В схеме алгорнфма фА используются две вспомогательные буквы — сс и р. Легко понять, что роль второй из них можно поручить слову аа, взяв вместо схемы 1(!) схему сиз$ — вессс а$3 — з1а$ — ~а, где $ н з) пробегают алфавит А. Эта схема содержит всего одну вспомогательную букву и также определяет обращающий алгорифм. Естественно возникает вопрос, нельзя лн здесь обойтись совсем без вспомогательных букв, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
