Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091)
Текст из файла
ББК 32.973.26-018.2.75 А65 УДК 681.3.07 Издательский дом "Вильямс" Зав. редакцией С.Н. Тригуб Перевод с английского канд. физ.-мат. наук М.М. Беловой Под редакцией канд. физ.-мат, наук С.С. Шкильняка и М.Р. Саит-Аметова Научный консультант докт. физ.-мат. наук, проф.
Ю.В. Казаченко По общим вопросам обращайтесь в Издательский дом "Вильямс" по адресу; !010©тч!!!!агпзриЫ!8)т!пд.сот, И!!р://чгтчтч.тч!ШатзрцЫ!85(пя.сот Андерсон, Джеймс А. А65 Дискретная математика и комбинаторика.: Пер. с англ. — М.: Издательский дом "Вильямс", 2004 — 960 с ил — Парал.
тит. англ. 15ВЫ 5-8459-0498-6 (рус.) Эта книга представляет собой современный учебник по дискретной математике. Кроме таких разделов, как математическая логика, теория множеств, комбинаторика, теория графов, теория алгоритмов и вычислений, традиционно включаемых в основной курс дискретной математики, она содержит обширные сведения по теории вероятностей, алгебре и теории чисел.
Особое внимание уделено теории доказательств. Чтение книги требует некоторой математической культуры, хотя для изучения основных глав достаточно знаний по математике в объеме средней школы. Материал сопровождается многочисленными примерами, в конце каждого раздела приводится большое количество упражнений. Книга адресована в первую очередь преподавателям и студентам технических специальностей. Она будет также полезна тем, кто интересуется дискретной математикой и желает изучить ее самостоятельно.
ББК 32.973.26-018.2.75 Все названия программных продуктов являются зарегистрированными торговыми марками соответствующих фирм. Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой бы то ни было форме и какими бы та ни было средствами, будь то злектронные или механические, включая фотокопирование и запись нз магнитный носитель, если нв это нет письменного разрешения издательства Ргепнсе Нан, 1пс Ацгьогйед !ганя)з!юп !гоги йе Еп91нй 1впвцвие ебп(оп рцЫ~зьеб Ьу Ргепгке-Нзп, !пс, Спрут(кш ф 2001 АИ Паше гезегчей Хо рег! о1 гшз Ьоой гпву Ье гергобцсеб ог !гзпзгп~пеб !п впу 1оггп ог Ьу япу пзевпз, е)ес!гоп!с ог тесьзп!сз1, шс)цб!пк рьо!осорушк, гесогйпк ог Ьу епу )п1оггпзиоп гп, чгньоц! регтнмоп 1гогп йе РцЬИйег.
йцзз)зп 1зпвцаке ейиоп рцЫ~зьеб Ьу цгпизгпз РцЬИзшпи Ноцзе зссогйпк ! гг( Еп!егрмзез 1пгегпз!юоз1, Спрут!ИЫ ф 2003 рзВЫ 5-8459-0498-б (рус ) 15ВХ 0-13-Овб998-8 (енгл.) ф Издатель ф Ргепгке-Н 6 Содержание Функции и матрицы 150 4.1. Функции !56 4.2. Специальные функции !0! 4.3. Матрицы 167 4.4. Мощность 4.5. Мощность (продолжение) нв Алгоритмы и рекурсия !64 Циклы и алгоритмы для матриц 1В4 Рекурсивные функции и алгоритмы 1ВВ Сложность алгоритмов 201 Алгоритмы сортировки 205 Префиксная и суффиксная записи 214 Двоичные и шестнадцатеричные числа 2!В Числа со знаком 23! Дальнейшее изучение матриц 237 Графы, ориентированные графы и деревья 244 6.1. Графы 244 6.2. Ориентированные графы 252 6.3.
Деревья 2ВВ 6.4. Мгновенное безумие 207 6.5. Пути и циклы Эйлера 270 6.6. Матрицы инцидентности и смежности 6.7. Гиперкубы и код Грея 2В0 Теория чисел 2вв 7.1. Решето Эратосфена 2ВВ 7.2. Метод выделения множителей Ферма 300 7.3. Алгоритмы деления и алгоритм Евклида 30! 7.4. Цепные дроби 200 7.5.
Подходящие дроби 3!0 Содержание 7 Комбинаторика и вероятность зтв 8.1. Основные комбинаторные принципы 318 8.2. Комбинаторный принцип сложения З24 8.3. Перестановки и сочетания 331 8.4. Формирование перестановок и сочетаний 343 8.5. Введение вероятности 347 8.6. Обобщенные перестановки и сочетания 354 8.7. Перестановки и сочетания с повторением ЗЗВ 8.8. Принцип клеток 363 8.9. Снова о вероятности звв 8.10. теорема Байеса З84 8.11. Цепи Маркова зве Алгебраические структуры зв2 9.1. Вновь о частично упорядоченных множествах 392 9.2. Полугруппы и полурешетки ЗВ7 9.3.
Решетки 403 9.4. Группы 4ОВ 9.5. Группы и гомоморфизмы 4!3 Некоторые специальные вопросы теории чисел 422 10.1. Целочисленные решения линейных уравнений 422 10.2. Решения сравнений 424 10.3. Китайская теорема об остатках 423 10.4. Свойства функции Е 4ЗЗ 10.5. Порядок целого числа 43в Некоторые специальные вопросы теории рекурсии 443 11Л. Однородные линейные рекуррентные отношения 448 11.2. Неоднородные линейные рекуррентные отношения 4ВО 11.3. Конечные разности 4ВВ 11.4.
Факториальные многочлены 473 11.5. Суммирование разностей 4ЗЗ 8 Содержание Снова о комбинаторных подсчетах 469 12.1. Задачи о размещении 469 12.2. Числа Каталана 496 12.3. Общее включение-исключение и разупорядочения 662 12.4. Ладейные полиномы и запрещенные позиции 669 Производящие функции вгз 13.1.
Определение производящей функции 62З 13.2. Производящие функции и рекуррентные отношения 626 13.3. Производящие функции и комбинаторные подсчеты $35 13.4. Разбиения 642 13.5. Экспоненциальные производящие функции 649 Некоторые специальные вопросы теории графов 666 14.1. Алгебраические свойства графов 666 14.2. Планарные графы 666 14.3. Раскраска графов 666 14.4. Пути и циклы Гамильтона 6ОО 14.5. Взвешенные графы и алгоритмы поиска кратчайшего пути ви ДЕРЕВЬЯ 624 15.1. Свойства деревьев 624 15.2. Бинарные деревья поиска 6Зт 15.3.
Взвешенные деревья 6З6 15.4. Обход бинарных деревьев 649 15.5. Остовные деревья 666 15.6. Минимальные остовные деревья 662 Сети 697 16.1. Сети и потоки 697 16.2. Паросочетание 7от 16.3. Сети Петри 716 содержаное 9 Теория вычислений 72ь 17.1. Регулярные языки 778 17.2. Автоматы 781 17.3. Грамматики 741 Теория кодов тьз 18.1. Введение 7ЬЗ 18.2. Порождающие матрицы 787 18.3. Коды Хемминга 787 Перечисление цветов 77ь 19.1. Теорема Бернсайда 77Ь 19.2. Теорема Пойа 781 Кольца, области целостности И ПОЛЯ 788 20.1.
Кольца и области целостности 788 20.2. Области целостности 797 20.3. Полиномы зот 20.4. Алгебры и полиномы звз Характеры групп и полугрупп 819 21.1. Комплексные числа 819 21.2. Характеры групп 820 21.3. Характеры полугрупп 828 Приложения теории чисел 82в 22 1. Приложение: поиск по образу 829 22.2. Приложение: функции хеширования 887 22.3. Приложение: криптография з4з Литература зьо Ответы к упражнениям зье Предметно-именной указатель 942 Список обозначений вь4 П'.мм пи Змиу)а В (:пиуип и Ор~~,,~,~о / 1'~(и Чю~' ымье Мэ~и льн, Зуди, Кри~'юип и Юьл~ :~и|пс;:чм, «о~повпи>,и и доц~ьяч ТХзд~~ Предисловие 11 Теория графов, включающая ориентированные графы, циклы и пути Эйлера, циклы и пути Гамильтона, плоские и взвешенные графы; Деревья, включающая бинарные деревья поиска, взвешенные деревья, обход деревьев, коды Хаффмана и остовные деревья; Комбинаторика, включающая перестановки, сочетания, включение-исключение, разбиения, производящие функции, числа Каталана, числа Стирлинга, ладейные многочлены, разупорядочения и перечисления цветов; Алгебра, включающая полугруппы, группы, решетки, полурешетки, булевы алгебры, кольца, поля, области целостности, полиномы и матрицы.
Книга содержит обширные сведения по алгебре и теории чисел, что, по мнению автора, усиливает ее содержание, хотя включать эти темы в курс лекций вовсе не обязательно. Материал соответствующих глав полностью независим от остальных частей книги, и в каком объеме его стоит излагать — решать лектору. Данное пособие содержит также элементы теории вероятностей, сведения о конечных разностях и другие темы, обычно не рассматриваемые в книгах по дискретной математике. СТРУКТУРА КНИГИ Содержание первых трех глав охватывает логику и теорию множеств.
Здесь позиция автора состоит в том, что понимание основ теории доказательств необходимо для логического построения передовых компьютерных технологий. Изложены основные положения теории доказательств и проиллюстрированы многочисленными примерами.
В главе 2 студенту предлагается самостоятельно доказать некоторые элементарные утверждения теории множеств. В главе 3 вводится понятие аксиоматической системы для теории чисел. Студенту предоставляется возможность попрактиковаться в доказательстве теорем о хорошо знакомых ему объектах. В этой же главе вводится метод доказательства по индукции. Далее в книге приводится множество доказательств, а также посвященных им задач. Сначала эти задачи довольно просты, но по ходу изложения книги уровень их сложности постепенно возрастает.
Отношения и графы вводятся в главе 2. В главе 4 из понятия отношения естественным образом выводится понятие функции. Однако подробное изучение функций в главе 4 проводится независимо от материала главы 2. Точно так же в главе 6 графы исследуются вне контекста главы 2, где они рассматриваются в связи с отношениями. Матрицы, перестановки и последовательности вводятся в главе 4 как функции специального вида.
Дальнейшее изучение свойств этих функций продолжается в главе б. Здесь же вводятся алгоритмы операций над матрицами и рассматриваются те свойства матриц, которые используются далее в главах, посвященных алгебре, комбинаторике и теории кодов. В главе 8 перестановки используются как инструмент комбинаторных подсчетов. Перестановки также используются в последующих главах, посвященных прикладным вопросам алгебры и комбинаторики. Глава 8, хотя она и связана с главой 4, может изучаться независимо. 12 Предословив Содержание главы 5 не связано с предыдущими главами ничем, за исключением того, что касается матриц.
Подробно изучены алгоритмы, в частности, алгоритмы сортировки. Понятие сложности алгоритмов также рассмотрено в этой главе. Здесь же даны сведения о префиксной и суффиксной записях. Эта тема опять обсуждается в главе 15 в связи с обходом бинарных деревьев. В главе 5 вводятся также двоичные и шестнадцатеричные числа. Многие элементарные понятия, связанные с графами, ориентированными графами и деревьями, рассматриваются в главе 6. Более глубоко эти вопросы изучаются в главах!4-16. Содержание главы 6 не зависит от содержания предыдущих глав. В главах 7 и 1О получает дальнейшее развитие теория чисел.
Характеристики
Тип файла DJVU
Этот формат был создан для хранения отсканированных страниц книг в большом количестве. DJVU отлично справился с поставленной задачей, но увеличение места на всех устройствах позволили использовать вместо этого формата всё тот же PDF, хоть PDF занимает заметно больше места.
Даже здесь на студизбе мы конвертируем все файлы DJVU в PDF, чтобы Вам не пришлось думать о том, какой программой открыть ту или иную книгу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
