Дискретная математика и комбинаторика - Эта книга представляет собой современный учебник по дискретной математике. Кроме таких разделов, как математическая логика, теория множеств, комбинаторика, теория графов, теория алгоритмов и вычислений, традиционно включаемых в основной курс дискретной математики, она содержит обширные сведения по теории вероятностей, алгебре и теории чисел. Особое внимание уделено теории доказательств. Чтение книги требует некоторой математической культуры, хотя для изучения основных глав достаточно знаний по математике в объеме средней школы. Материал сопровождается многочисленными примерами, в конце каждого раздела приводится большое количество упражнений. Книга адресована в первую очередь преподавателям и студентам технических специальностей. Она будет также полезна тем, кто интересуется дискретной математикой и желает изучить ее самостоятельно.
Название: Дискретная математика и комбинаторика Автор: Джеймс А. Андерсон Издательство: Вильямс Год: 2004 Страниц: 959 Формат: DJVU Размер: 8,15 МБ ISBN: 5-8459-0498-6 Качество: Отличное
Содержание:
Предисловие 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. Сети Петри 18. Теория вычислений 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. Приложение: криптография Литература Ответы к упражнениям Предметно-именной указатель Список обозначений
