Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 166
Текст из файла (страница 166)
! Если х — характер на Я вЂ” 1, то определим х' на 5 соотношениями (Х(з), если з б Я вЂ” 1; х'(з) = ~ ~<О, если з б 1. 3. Пусть С = (С,!) = а!г'. Тогда е,(о ) ь=! ь=! Х (дьКХг(дь)) = ь=! х!(дь)(х! Ьь)Г ь=! пбо согласно теореме 21.19. Раздел 22.1. 1.
Пусть )т(И') = ег2" '+ег2" г+ . Ч-е г2' Ч-е„и Ф(У) = уг2" '+у!2" г+ + у„г2'+ у„. Тогда — М(УК < !а! — у!)2" + !ег — уг)2" + +)к ! — у !)2 +)(а — у )( (з! — ул2" * < ~~ 2" )Дг(1У) Раздел 21.8 . 1. Пусть ! Е 1 и з Е Я. Х(г. з) = Х(!) Х(з) = О Х(з) = О и ! з б Г.
Следовательно, 1 — идеал. Пусть з, з' б Я вЂ” 1. Тогда Х(зз') = Х(з)Х(з') = 1 1 = 1. Таким образом, зз' Е Я вЂ” 1 и Я принадлежат идеалу. Следовательно, 1 — простой идеал. Обратно, если 1 — простой идеал, то искомый характер может быть получен путем отображения. Если Х вЂ” отображение из ср40 Ответы к упражнениям 3. ис = 7,8, 11, 12, 13, 14, 15, 16. 5. Ь слов для хранения гс простых чисел; гс слов для хранения )тр(Х) для 1с простых чисел р; гс слов для хранения И„(У(с)) для й простых чисел р; й слов для хранения [[2" ']]гл незначительное количество слов для циклов и т.пх всего приблизительно 41с слов.
Раздел 22.2. 1. Если И[а и д[Ь, то в[а-Ь. Поэтому Ы] НОД(а — Ь, а) и НОД(а, Ь)] НОД(а — Ь, а). Обратно, если д]а и Ы]а-Ь, то д]Ь, и, следовательно, Ы[ НОД(а, Ь). Таким образом, НОД(а — Ь, а)] НОД(а, Ь). Значит, НОД(а — Ь,а) = НОД(а, Ь). 3. НОД(6,10,15) = 1, однако НОД(6,10) ф 1. Фактически, наибольший обший делитель любой пары этих целых чисел не равен единице. 5. а) с асс са, М, Ь, ЛГ, М,ь,дгс 1 12 145 26551252 532 0 0 2 14 169 22730660 5 43 4897641900 3 15 181 21270340 711 91 1376212263340 4 16 217 17741620 61 163 234242606660 Р = 12; С = 2231403840; [2231403840~~ 12 х 12+ 1 [2231403840~11 12 х 14+1 у(12) = [ 7(14) = [ =0 [[[2231403840~~~ 12 х 15+1 г'(15) = =2 /(18) = [[[ ~11 = 3 7. а) с Ус, т, 1 5 301 2 15 901 3 20 1201 4 25 1501 Р = 60; М, Ь, 1сГ, М,Ь,Дс, 6496934404 1066 0 0 2170452004 232 226 113601139473723 1628290804 379 601 370390451044316 1302849604 5632 1126 3555594470734528 С' = 1607985850884; =0 [[ 1607985850884 Ш 60 х 25 + 1 з'(25) = 7'(5) = [ У(15) = [ /(20) = [ 1607985850884~1 бох 5+1 ! 1607985850884~~ 60 х 15+1 1607985850884~ 60 х 20+1 Ответы к упрелснениям 941 Раздел 22.а.
1. [[1683ш ]]гддз = 77~ [[79 ]]гддз = 79; [[2560 ]]гддз = 78; [[872 ]]гддз = 69; [[2571 ]]гддз = 89. 3. Для шифрования необходимо иметь значения е и и, Если известно дг[п), то, используя формулы из теоремы 22.15, можно найти д, что обеспечит возможность дешифровки. Предметно-именной укезетель 943 Бинарное дерево поиска — В1пагу ьеагсЬ 1гее, 631 обход — ггачегьгпя, 649 Биномнальная теорема — В|погша| 1Ьеогегп, 337 Биномиальное распределение — В|попив! йь1пЬи1юп, 375 Битовая строка — ВН 51г!пн, 3!8 Блоковый код — В!осй соде, 753 Боер, Р.
С. (Воуег, В. 5.), 836 Булева алгебра — Воо1еап а!ИеЬга, 84, 406 дополнение законов тождества— сигор!егпеп1 о1 Ыеп|И|еь!агчь, 87 законы ассоциативности — аььос|а||че ргорег||еь, 85 законы де Моргана — Ре Могяап'ь |амь, 87 законы дистрибутивности— йь1пЬииче ргорегиеь, 85 законы дополнения — сотр|егпеп1 ргорег||еь, 85 законы идемпотентности— Ыетро|еп1 !а» ь, 86 законы инволюции — |пчо|и1|оп !агчь, 87 законы коммутативности— сотти|а1|че ргорегиеь, 85 законы поглощения — аЬьогр1юп !агчь, 86 законы тождества — Ыеп|йу ргорегиеь, 85 свойства констант — пий !атчь, 86 Бурали-Форти (Витай-Еогг!), 67 В Вероятность — РгоЬаЬИйу, 348, 369, 833 биномиальное распределение— Ь|попиа| ййпЬиноп, 3?5 математическое ожидание— та|Ьетаиса! ехрес|а|юп, 376 множество элементарных событий— ьатр|е ьрасе, 347 независимые события — гпберепбеп1 ечеп1ь, 374 непересекающиеся множества— йь)о|п1 ье|, 348 ожидаемое значение — ехресгег| ча!ие, 376 среднее значение — гпеа, 379 условная — сопй||опа|, 370 Взаимоисключающие множества— Ми1иайу ехс!иь!че ье1ь, 11О Включение-исключение— 1пс|ияоп-ехс!иь!оп, 502 Внутреннее произведение — !ппег ргобис1, 169 Вполне упорядоченная область целостности — чггей огдегеб |п1еяга! бота|о, 798 Выводимость — Ребис|Ь|йгу, 34 Выражение — Ехргеььюп, 726 регулярное — гено!аг, 726 Высказывание — Ргороь(||оп, ! 5 Вычет — Веь!бие, 153 Гамильтонов — Напи11оп|ап путь — ра1Ь, 601 цикл — сус1е, 601 Гауссово кольцо — ()пгг|ие |ас1ог|га||оп бота!и, 797 Гиперкуб — НурегсиЬе, 290 Гипотеза — Нуро1Ьеьгь, 35 Гомоморфизм — Нототогршяп колец — г!пе Ьогпогпогрщяп, 790 полугрупп — ьегп!нгоир ЬогпотогрЫяп, 415 Грамматика — Пгатгпаг, 741 контекстная — соп!ех1-ьепь!1|че, 749 начальный символ — ыаг| ьугпЬо1, 742 непосредственных составляющих— рЬгаье йгис|иге, 742 нетерминальные символы— поп|ется|па! ьугпЬо!ь, 741, 742 порождаемый язык — 1апйиаде яепега1еб Ьу, 742 продукции — ргобис1юпь, 741 регулярная — геди(аг, 751 соответствующее дерево— соггеьропйпн 1гее, 747 терминальные символы — !егпипа| ьугньО|, ?41, 742 формальная — |оппа|, 742 Граф — СггарЬ, 95, 244, 556 Петерсена — Ре1егьеп дгарЬ, 584 вершина — чег|ех, 95, 244 взвешенный — гче!яЬ|ей 611 гомеоморфный — ЬогпеотогрЫс, 557 944 Предметно-именной уквзагпель гомоморфизм — ЬотошогрЫып, 556 грань — 1асе, 581 двойственный — бца1, 587 двудольный — Ыраг!Ие, 250 двусвязный — Ь|соппес1еб, 562 диаметр — б!агпе!ег, 290 дополнение — сотр!ешеп|, 559 изомарфизм — |зотогрЫып, 556 компонента — согпропепг, 250 компонента двусвязности— Ь~согпропепг, 563 матрица инцидентности — |псщепсе ша!Их, 278 матрица смежности — аб|асепсу та1пх, 279 мультиграф — тиИ!ягарЬ, 245 объединение — оп|оп, 559 остовное дерево — зрапп!пй 1гее, 560 остовной граф — зрапп!пд ягарЬ, 559 пересечение — |п1егзес|юп, 559 планарный граф — р!апаг цгарЬ, 580 полный — сошр!е|е, 250 полный двудольный — сошр!е1е Ыраг!Ие, 25! попарно непересекающиеся— ра!гэг!эе б!з!о!пг, 559 производный — депмеб, 557 простой путь — Штр1е ра1Ь, 248 простой цикл — э|гпр|е сус|е, 250 путь — ра1Ь, 248 разрезающее множество — си! эе|, 561 разрезающее ребро — сц1 едяе, 561 раскраска — со!опий, 589 расстояние — б!э!апсе, 290 расширение — ех1епзюп, 557 ребро — едце, 95, 244 связный — соппес!ед, 249 сетка — йгкй 295 смежные вершины — ад!асеп! тег!!сез, 244 смежные ребра — ад!асеп! ег!яез, 244 степень вершины — беягее о| чег!ех, 247 точка сочленения — аг!|сйа!|оп ро|п1, 561 хроматический многочлен— сйготанс ро|упогп!а1, 589 хроматическое число — сЬгота1Ю пшпЬег, 589 цикл — сус|е, 250 эйлеров цикл — Ео1ег ра|Ы 270 Группа — сггоцр, 4!О абелева — аЬе!|ап, 4|0 группа симметрий — зупнпе|пс ягоор, 419 единичный элемент — Ыеп1Иу, 410 коммутативная — согпгпо1анче, 410 конечная циклическая — Пине сусйс ягоцр, 412 левый смежный класс — 1еИ созе1, 413 нормальная подгруппа — поппа! зцЬцгоцр, 4|7 обратный элемент — !пчегзе, 4!О подгруппа — эцЬягоир, 4!2 порядок — огбег, 410 порядок элемента — огоег о1 ап е!етеп1, 411 прямая сумма — г|!тес! зппп, 82! симметрий квадрата — зушгпе1пез о| |Ье зг!цаге, 776 смежный класс — соэе1, 4!3 фактор-группа — 1ас!ог ягоцр, 418 характер — сйагас!ег, 821 циклическая — сус1|с йгоцр, 4|2 ядро — кегпе1, 417 Деление остаток — геша!пг!ег, !40 частное — г!цо!!епг, |40 Делитель единицы — !|пн, 795 Дерево — Тгее, 259, 624 пг-арное — ги-агу, 263 бинарный поиск — Ыпагу зеагсЬ, 631 братья — з!Ы!пц, 263 вес — же|азЫ, 639 внутренняя вершина — |п|егпа! чег1ех, 261 высота — Ье|8Ы, 262 корень — гоо|, 262 корневое — гоо!еб, 262 корневое ориентированное — гоо!ед б!тес!еб, 262 лес — 1огеш, 259 листья — !еачез, 261 ориентированное — б!тес!ед, 260, 624 остовное — крэпп!пя !гее, 264, 658 подсчета — соцп!!пц 1гее, 316 Предметно-именной указатель 945 гоиск в глубину — дер!Ь-Пгз! зеагсЬ, 661 поиск в ширину — Ьгеаб!Ьйгз! зеагсЬ, 659 потомок — безсепбеп1, 263 предок — апсез1ог, 263 родитель — рагеп|, 262 сын — сЫЫ, 262 уровень — |ече|, 262 Детерминированный автомат— Ре1егпипш!|с аи!огпа1а, 735 Дешифровка — Ресгур!юп, 844 Диаграмма — Р|аягат Венна — Уепп б|ангат, 77 Ферре — Реггег'з б|аягат, 545 Эйлера — Еи|ег б|айгат, 119 Дизъюнктивная нормальная форма— Р|з)ипс!1че погта| 1опп, 47 Диффи, У.
(Р|П|е, %.), 847 Доказательство — Ргоо1 контрпример — соип!егехатр|е, 129 перебором — сазе ргоо1, 128 приведение к абсурду — гебисио аз абзигбит, 127 Евклид (Еисйб) теорема о простых числах — 1Ьеогет оп рптез, 145 Евклидово кольцо — Еис|щеап бата|и, 809 норма — поггп, 809 Единичная окружность — ()п1! Ыгс|е, 820 Запрещенные позиции — РогЫббеп роз!цопз, 509 Зашифрованный текст — С|рЬег!ех1, 844 Идеал — 1беа), 793, 825 максимальный — тахипа!, 810 простой — ргипе, 795 Идем потент — ! бетро!епг, 401 Идентифицирующая функция— Р|пдегрппг, 831 Изоморфизм — !зотагрЫзгп колец — ппя |зопюгрЫзгп, 790 полугрупп — зепиигоир ВотогрЫмп, 415 Импликация — Сопб|!1опа1, 24, 33 Инверсия — !пчегзе, 33 Инверсная польская запись — йечегзе РойэЬ по!а!1оп, 651, 653 Индукция — !пбис!1оп, 136, 137, 799 Инфиксная запись — 1пйх по1а!|оп, 215 Инфиксный код — |пйх соде, 731 Испытания Бернулли — Вегппоий| !па!з, 377 Кан, Дэвид (КаЬп, Рачщ), 849 Кантор, Георг (Сап!ог, Сгеогя), 67 Карп, Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
