Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 148
Текст из файла (страница 148)
Предположим, что д Ф е и Х вЂ” такой характер, что Х,(д) ~ 1. Такой характер существует, потому что д = д,' дз дз дз, где 0 ( Я1) ( к(г), как показано в доказательстве теоремы 21.10. Далее, поскольку д ф е, то 1(г) Ф 0 для некоторого г. Теперь можем положить х,(д) равным хе,(д) по той причине, что хг.(д) = г'; ~ 1, где г, — первообразный корень к(в)-ой степени из единицы. Тогда Х(д) = ~~ (Х,Х)(д) = согласно лемме 21.16 х х х.Ых(д) = х = Х.(д) ~~' Х(д) х (1 — х-(д)],> х(д) =о. х Поскольку Х,(д) ~ 1, получаем 2Х(д) = О.
х Следующая теорема формулирует два полезных свойства ортогональности характеров групп. Доказательство теорем оставляем читателю. ТЕОРЕМА 21.19. Пусть С вЂ” конечная коммутативная группа порядка и, пусть д„д, Е С, пусть Х, и Хь — характеры группы С. Тогда а) т х(д )х(ду) = О е и д ~д. б) Е,ео х. Ыхь '(д) = (О, если Х фХь. ТЕОРЕМА 21.20.
Предположим, что группа С имеет порядок и и и — (и)- матРиЦа, в котоРой о.„= Х,(д,), гДе Х1,Хз, Хз,...,Մ— хаРактеРы гРУппы С. Если и' — матРица, в котоРой)1 и,'у = о,, то и 0 0 ... 0 0 и 0 0 0 0 и . 0 = о'п~ и'сг = 0 0 0 . и 828 ГЛдВА 21. Характеры групп и попугрупп ДОКАЗАТЕЛЬСТВО. Пусть С = (С;,] = и'а. Тогда и и Е' -Е' а ьаь = ~сг„,аь ь=1 ь=г п ~ХаЫХь(ру) = ь=з и ~ Хь(дг ')Хь(а) ь=1 поэтому первое утверждение теоремы следует из теоремы 2!.19. Доказательство второго утверждения предоставляем читателю. ТЕОРЕМА 21.21.
Всего существует ф(т) различных характеров Дирихле по модулю положительного целого числа т. Каждый характер Дирихле является вполне мультипликативным и обладает тем свойством, что Х([а+ т]) = Х((а]), где [а] — класс вычетов по модулю т, содержащий а, или, что эквивалентно, Х(а + т) = Х(а). Замечание: поскольку сложение и умножение в 2 не зависят от выбора представителя класса из 2, то, как правило, вместо Х([а + т]) используется запись Х(а + т).
Таким образом, область определения функции Х расширена до 2. Именно в этом обобщенном смысле мы говорим о том, что каждый характер является вполне мультипликативным. ДОКАЗАТЕЛЬСТВО. Поскольку каждый характер Дирихле является единственным расширением характера группы из группы приведенных классов вычетов по модулю ги, то первая часть утверждения теоремы следует из того факта, что количество характеров группы совпадает с количеством элементов в группе. Поскольку каждое "целое" в образе характера Дирихле на самом деле представляет класс сравнимости по модулю гп, то [а] = [а + т] и Х([а+ т]) = Х([а]).
Характер Х является вполне мультипликативным, так как если элементы а и Ь вЂ” взаимно простые с т, то (а] и [Ь] принадлежат группе приведенных вычетов, и Х вЂ” гомоморфизм на эту группу. Если а или Ь не является взаимно простым с т, то таковым не является и их произведение, поэтому оба Х((а])Х([Ь]) и Х([аЬ]) равны 0 или, что эквивалентно, оба Х(а)Х(Ь) и Х(аЬ) равны О. ° УПРАЖНЕНИЯ 1. Докажите теорему 21.14. 2. Докажите теорему 21,19. 3. Завершите доказательство теоремы 21.20. 830 ГПАВА 22. Приложения теории чисел применим ко многим типам поисковых контекстов. Ниже мы приводим достаточно обший алгоритм поиска по образцу, разработанный Ричардом М. Карпом и Майклом О.
Рабином [56], в основе которого лежит выбор случайных простых чисел. Этот алгоритм обладает описанными выше свойствами и является примером использования вероятностных методов. Все числа и символы (цифры н буквы алфавита) представлены в компьютере как последовательности нулей и единиц. Например, представлением буквы "е" на основе АБСП 8-битовой кодировки является последовательность битов [01100101], которая трактуется как двоичное целое число 21 + 1 24 + 1 2з + О 24 + О 2з + 1 22 + О 21 + 1 2о Слово "еИес1" можно представить в виде [[01100101] [01100110] [01100110] [01100101] [0110001Ц [01110110].
Рассматривая эту последовательность как битовую строку, мы можем трактовать ее как двоичное целое число О 241+1 24в+1 244+ +1 21+0 2о Строка битов [01100101] для буквы "е" может быть представлена в шестнадцатеричной системе счисления как 651о или в восьмеричной — как 145з. При практической реализиции алгоритма можно выбирать более естественную систему счисления, но при описании алгоритма Карпа и Рабина мы будем рассматривать "образ" н "текст" как битовые строки. Пусть Х вЂ” образ и У вЂ” текст, тогда Х=[хгхзхз х„], где х,=О или 1; У=[У1У2Уз ...
У ], гдеУ1=0или1. Образ имеет длину и битов и текст имеет длину т битов, где п1 > и. Пусть У(1) — подстрока из и последовательных битов строки У, которая начинается с позиции 1, 1 < 1 < гп — п + 1, так что (1) [Уа Уа+1 Уа+2 ' ' ' Уа+аа — 1]. Очевидно, для всякого 1 такого, что Х = У(1), имеется соответствие между образом и частью текста. Заметим, что Х и У(1) можно рассматривать как элементы множества (О, Ц" = (О, Ц х (О, Ц х х (О, Ц вЂ” декартовой и-степени множества (О, Ц, или множества и-элементных наборов с элементами из (О, Ц.
Пусть А1(Х) и 1У(У(1)) — целые двоичные числа, которые имеют представления: АГ(Х) = х12" ' + хг2" 2 + + х„12' + х„; АГ(~ (1)) = уа2 + уа-1-12 + ' ' + уаа-Ьаа-22 + уаа.ьаа-1, при этом соответствие имеет место тогда и только тогда, когда Аа"(Х) = А1(У(г)). РАЗДЕЛ 22.1. Приложение: поиск по обраэу 831 Сравнение Х(Х) и Х(У(г)) потребует не меньше усилий, чем сравнение Х и У(г), Поэтому необходимо "сжать" информацию, содержащуюся в Ф(Х) и Х(У(г)), с тем, чтобы это сравнение требовало меньше работы. Одним из способов осуществления такого сжатия является отображение целых чисел Х(Х) и Х(У(г)) на меньшие целые числа, используя модульную арифметику.
Пусть р— простое число из интервала 1 < р < М, где М вЂ” некоторое достаточно большое положительное целое число, которое будет определено ниже. Пусть Хр — отображение множества битовых строк длины и на множество первичных вычетов по модулю р, (О, 1, 2,..., (р — 1)), определенное соотношением Хр(Иг) = [[Ф(Иг)]]ю так что )чр(Х) = [[Л(Х)]]р и Юр(У(г)) = [[йг(У(э))]]р. В типичных приложениях величина и. может быть порядка 200, а р может находиться в диапазоне от 2~е до 2е~. Большинство компьютеров могут эффективно сравнивать 16-битовые целые числа с 64-битовыми. Функция йГр вырабатывает "доверенное" число Хр(Иг) для )т'(И'), которое будет использоваться в сравнениях вместо И' или Х(И').
Такую функцию часто называют идентифицирующей функцией, а Ьг (И') называют идентификатором для И'. Заметим, что в этом случае идентифицирующая функция Мр не является однозначной, поэтому можно иметь две битовые строки И' и У длины п с одним и тем же идентификатором, т.е. )Ур(И') = Жр(Ъ'). Если Х (И') = )т'„(У), но И' ~ У, то в этом случае будем говорить, что имеет место коллизия — ошибочное соответствие. В дальнейшем мы решим эту проблему.
Если )У(И') сводить по модулю р до Хр(И'), начиная с Ю(И') для каждого новой строки И', то это преобразование потребует значительного количества времени. К счастью, имеется возможность находить последовательность Юр(У(1)), Юр(У(2)), Тр(У(3)), ... без лишних вычислений. Сведение Ж(И') к Жр(Иг) может быть выполнено постепенно. Заметим, что Ж(И') = шэ 2" ' + шз2" ~ +...
+ ш„~ 2' + ш„, = = ( ((шг 2+ шз) 2+шз) 2+ + ш„-г) 2+ ш„. Порядок выполнения операций в последнем выражении определен однозначно. Согласно теореме 3.54, если а = Ь (шоп р), то Ь можно подставить вместо а в любом выражении, содержащем умножение, сложение и вычитание, не меняя при этом вычет выражения по модулю р. Будем говорить, что операция аОЬ для целых чисел а и Ь выполнена по модулю р, если после выполнения операции результат сведен по модулю р до наименьшего неотрицательного вычета; т.е, подставляем первичный вычет [[а О Ь]]р вместо а О Ь.
Для сокращения записи иногда будем писать а ба Ь вместо [[а О Ь]]р, чтобы подчеркнуть, что сведение по модулю р должно быть выполнено после выполнения операции. Например, если подставить ш~ р 2 вместо шг 2, а затем подставить (шг р 2) +ршз вместо (ш1 р 2) + шз, то в резул ьта те пол уч и м )чр(И ) = ( .. ((шг р 2+р шэ) р 2+р шз) р 2+р +р шо ]) р 2+р шп. Таким образом, приведение Ю(Иг) к его первичному вычету по модулю р, )Ур(Иг), может выполняться по одной операции, начиная с самых внутренних круглых скобок. Остается еще необходимость сравнивать Х и У(г) для каждого г, сравнивая 832 ГЛКВА 22.
Приложения теории чисел для каждого г "доверенные" целые числа )Ур(Х) и )Ур(У(г)); таким образом, хотя Агр(У(г)) может быть вычислено эффективно для каждого з, алгоритм поиска может оказаться в целом неэффективным. Однако, это тот случай, когда )Ур(У(1+1)) можно получить из )У (У(г)) и у,еи выполнив несколько арифметических операций, без полного пересчета )т' (У(1 + 1)) из рабочего файла. Поскольку )У(У(1+1)) = ()У(У(г)) — 2" у ) 2+ у ~п то, используя только операции по модулю р, имеем Ю (У(1+ 1)) = ()У (У(1)) — р ((2" ~)]р р у;) „2+р у,е„. Такая формула, как описанная выше, позволяющая легко вычислять "следующее" значение по текущему, называется корректирующей формулой. Таким образом, можно сказать, что Агр(У(г)) легко корректируется. Основная идея алгоритма Карпа и Рабина состоит в выборе случайным образом простого числа р из соответствующего множества 1 < р < М и вычислении идентификатора Юр(Х) битовой строки образа Х.
Далее, необходимо сравнивать )Ур(Х) с идентификатором )Ур(У(г)) каждой последовательности У(1) из и последовательных битов в текстовой строке битов У для 1' = 1,2,3,...,т — и+ 1. Если случается так, что )Ур(Х) = Агр(У(й)) для некоторого к, то имеем доказательство того, что Х = У(й), и процесс завершен. Обычно, если алгоритм применяется с одним простым числом р, необходимо проверять, выполняется ли соотношение Х = У(й), поскольку функция )Ур не является однозначной. Если Х Ф У(1:), необходимо продолжить алгоритм для 1 = й + 1; вскоре мы увидим, что использование нескольких простых чисел и нескольких идентифицирующих функций иллюстрирует сущность вероятностной методологии.
АЛГОРИТМ ПОИСКА ПО ОБРАЗУ (Карп и Рабин) Предположим, что битовой строкой Х длины и задан образ; битовой строкой У длины т, где т > и, задан текст; задано целое положительное число М, которое будет зависеть от т и и. Пусть Я = (р: р простое число и 1 < р < М). Для простого числа р из множества Я пусть )Ур . (0,1)" — (0,1,2,...,(р — 1)) — идентифицирующая функция. Выберем случайным образом к простых чисел р,, рз, ..., рь из множества (1,2,...,М), выбирая случайным образом целые числа из совокупности (1,2,3,...,М), проверяя, являются ли они простыми, и останавливая процесс поиска, когда й простых чисел найдены.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
