Дискретная математика и комбинаторика, Андерсон Д.А., 2004

Дискретная математика и комбинаторика, Андерсон Д.А., 2004.

   Эта книга представляет собой современный учебник по дискретной математике. Кроме таких разделов, как математическая логика, теория множеств, комбинаторика, теория графов, теория алгоритмов и вычислений, традиционно включаемых в основной курс дискретной математики, она содержит обширные сведения по теории вероятностей, алгебре и теории чисел. Особое внимание уделено теории доказательств. Чтение книги требует некоторой математической культуры, хотя для изучения основных глав достаточно знаний по математике в объеме средней школы. Материал сопровождается многочисленными примерами, в конце каждого раздела приводится большое количество упражнений.
Книга адресована в первую очередь преподавателям и студентам технических специальностей. Она будет также полезна тем, кто интересуется дискретной математикой и желает изучить ее самостоятельно.




АКСИОМАТИЧЕСКИЕ СИСТЕМЫ: УМОЗАКЛЮЧЕНИЯ И ДОКАЗАТЕЛЬСТВА.
Математики в большинстве своем имеют дело с теоремами и их доказательствами. Теоремы представляют собой “истинные” утверждения относительно рассматриваемых математических систем. Например, утверждение:
Гипотенуза прямоугольного треугольника длиннее любого из катетов,
— это известная из геометрии теорема Евклида. Это утверждение считается истинным, поскольку оно “выводимо” из ранее принятых или выведенных истин геометрии Евклида.

Математическая система начинается с неопределяемых понятий и утверждений, точно описывающих фундаментальные характеристики или истинные утверждения относительно этих понятий, которые математики используют для образования системы. Эти фундаментальные характеристики называются аксиомами или постулатами. Утверждения, выведенные (доказанные) только на основе этих фундаментальных свойств (аксиом и постулатов) и ранее доказанных утверждений с помощью логических правил, называются теоремами.

Таким образом, в математических системах вся информация, необходимая для доказательства теоремы, должна содержаться в аксиомах и ранее доказанных теоремах. Развивая конкретный раздел математики, можно не включать в него все аксиомы и доказанные теоремы. Вместо этого можно принять доказанные теоремы в качестве аксиом. Например, аксиомы для целых чисел и аксиомы Пеано для положительных целых чисел неявным образом предполагают выполнение аксиом теории множеств, но, поскольку в теории чисел акцент делается на свойствах целых чисел, было бы излишним стремиться в ней одновременно к полному развитию теории множеств.

ОГЛАВЛЕНИЕ.
Предисловие.
1 Таблицы истинности, логика, доказательства.
1.1. Высказывания и логические связки.
1.2. Условные высказывания.
1.3. Эквивалентные высказывания.
1.4. Аксиоматические системы: умозаключения и доказательства.
1.5. Полнота в логике высказываний.
1.6. Карты Карно.
1.7. Коммутационные схемы.
2 Теория множеств.
2.1. Понятие множества.
2.2. Операции над множествами.
2.3. Диаграммы Венна.
2.4. Булевы алгебры.
2.5. Отношения.
2.6. Частично упорядоченные множества.
2.7. Отношения эквивалентности.
3 Логика, целые числа и доказательства.
3.1. Исчисление предикатов.
3.2. Основные положения теории доказательств и теории целых чисел.
3.3. Математическая индукция.
3.4. Делимость.
3.5. Простые числа.
3.6. Сравнения.
4 Функции и матрицы.
4.1. Функции.
4.2. Специальные функции.
4.3. Матрицы.
4.4. Мощность.
4.5. Мощность (продолжение).
5 Алгоритмы И рекурсия.
5.1. Циклы и алгоритмы для матриц.
5.2. Рекурсивные функции и алгоритмы.
5.3. Сложность алгоритмов.
5.4. Алгоритмы сортировки.
5.5. Префиксная и суффиксная записи.
5.6. Двоичные и шестнадцатеричные числа.
5.7. Числа со знаком.
5.8. Дальнейшее изучение матриц.
6 Графы, ориентированные графы и деревья.
6.1. Графы.
6.2. Ориентированные графы.
6.3. Деревья.
6.4. Мгновенное безумие.
6.5. Пути и циклы Эйлера.
6.6. Матрицы инцидентности и смежности.
6.7. Гиперкубы и код Грея.
7 Теория чисел.
7.1. Решето Эратосфена.
7.2. Метод выделения множителей Ферма.
7.3. Алгоритмы деления и алгоритм Евклида.
7.4. Цепные дроби.
7.5. Подходящие дроби.
8 Комбинаторика и вероятность.
8.1. Основные комбинаторные принципы.
8.2. Комбинаторный принцип сложения.
8.3. Перестановки и сочетания.
8.4. Формирование перестановок и сочетаний.
8.5. Введение вероятности.
8.6. Обобщенные перестановки и сочетания.
8.7. Перестановки и сочетания с повторением.
8.8. Принцип клеток.
8.9. Снова о вероятности.
8.10. Теорема Байеса.
8.11. Цепи Маркова.
9 Алгебраические структуры.
9.1. Вновь о частично упорядоченных множествах.
9.2. Полугруппы и полурешетки.
9.3. Решетки.
9.4. Группы.
9.5. Группы и гомоморфизмы.
10 Некоторые специальные вопросы теории чисел.
10.1. Целочисленные решения линейных уравнений.
10.2. Решения сравнений.
10.3. Китайская теорема об остатках.
10.4. Свойства функции ф.
10.5. Порядок целого числа.
11 Некоторые специальные вопросы теории рекурсии.
11.1. Однородные линейные рекуррентные отношения.
11.2. Неоднородные линейные рекуррентные отношения.
11.3. Конечные разности.
11.4. Факториальные многочлены.
11.5. Суммирование разностей.
12 Снова о комбинаторных подсчетах.
12.1. Задачи о размещении.
12.2. Числа Каталана.
12.3. Общее включение-исключение и разупорядочения.
12.4. Ладейные полиномы и запрещенные позиции.
13 Производящие функции.
13.1. Определение производящей функции.
13.2. Производящие функции и рекуррентные отношения.
13.3. Производящие функции и комбинаторные подсчеты.
13.4. Разбиения.
13.5. Экспоненциальные производящие функции.
14 Некоторые специальные вопросы теории графов.
14.1. Алгебраические свойства графов.
14.2. Планарные графы.
14.3. Раскраска графов.
14.4. Пути и циклы Гамильтона.
14.5. Взвешенные графы и алгоритмы поиска кратчайшего пути.
15 Деревья.
15.1. Свойства деревьев.
15.2. Бинарные деревья поиска.
15.3. Взвешенные деревья.
15.4. Обход бинарных деревьев.
15.5. Остовные деревья.
15.6. Минимальные остовные деревья.
16 Сети.
16.1. Сети и потоки.
16.2. Паросочетание.
16.3. Сети Петри.
17 Теория вычислений.
17.1. Регулярные языки.
17.2. Автоматы.
17.3. Грамматики.
18 Теория кодов.
18.1. Введение.
18.2. Порождающие матрицы.
18.3. Коды Хемминга.
19 Перечисление цветов.
19.1. Теорема Бернсайда.
19.2. Теорема Пойа.
20 Кольца, области целостности и поля.
20.1. Кольца и области целостности.
20.2. Области целостности.
20.3. Полиномы.
20.4. Алгебры и полиномы.
21 Характеры групп и полугрупп.
21.1. Комплексные числа.
21.2. Характеры групп.
21.3. Характеры полугрупп.
22 Приложения теории чисел.
22.1. Приложение: поиск по образу.
22.2. Приложение: функции хеширования.
22.3. Приложение: криптография.
Литература.
Ответы к упражнениям.
Предметно-именной указатель.
Список обозначений.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Дискретная математика и комбинаторика, Андерсон Д.А., 2004 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Андерсон