- •Введение
- •Библиография
- •Теория множеств
- •Множества и подмножества
- •Мощность множества
- •Операции над множествами
- •Декартово произведение
- •Круги Эйлера
- •Мультимножества
- •Бинарные отношения
- •Упорядоченные множества
- •Множества в информатике и программировании
- •Библиография
- •Комбинаторная теория
- •Исчисление конечных сумм
- •Правило сложения
- •Правило умножения
- •Метод включения и исключения
- •Перестановки
- •Размещения
- •Сочетания
- •Перестановки с повторениями
- •Размещения с повторениями
- •Сочетания с повторениями
- •Бином Ньютона и полиномиальная формула
- •Разбиения
- •Генерация всех перестановок
- •Генерация всех подмножеств
- •Генерация всех размещений с повторениями
- •Генерация сочетаний с повторениями
- •Генерация всех сочетаний без повторений
- •Генерация всех размещений без повторений
- •Генерация всех разбиений
- •Библиография
- •Теория графов
- •Основные понятия
- •Представление графов
- •Матрица смежности
- •Матрица инцидентности
- •Список связности
- •Список рёбер
- •Обход графа в глубину
- •Обход графа в ширину
- •Маршруты, цепи и циклы
- •Связность
- •Сочленения
- •Мосты
- •Деревья
- •Эйлеровы графы
- •Гамильтоновы графы
- •Планарные графы
- •Покрытие и независимость
- •Ориентированные графы
- •Топологическая сортировка
- •Библиография
- •Приложение Б. Рекуррентные соотношения
- •Задача о ханойских башнях
- •Задача о разрезании пиццы
- •Задача Иосифа Флавия
- •Библиография
- •Приложение В. Элементы теории чисел
- •Делимость и кратность
- •Алгоритм Евклида
- •Простые числа
- •Сравнения
- •Библиография
- •Библиография
Симоненко Евгений А.
ДИСКРЕТНАЯ МАТЕМАТИКА
ЛЕКЦИИ
(15 февраля 2012 – 18 мая 2013)
Краснодар
2013
Симоненко Е.А. Дискретная математика. Лекции. – Краснодар, 2013. – 46 с.
Учебное пособие представляет из себя сборник лекций по дисциплине «Дискретная математика», читавшихся автором в Кубанском государственном технологическом университете студентам-бакалаврам направлений 230100 – «Информатика и вычислительная техника» и 231000 – «Программная инженерия» в 2011/2012 и 2012/2013 учебных годах и направления 230700 – «Прикладная информатика» в 2012/2013 учебном году. В основной части пособия рассматриваются комбинаторная теория и теория графов. В приложении находятся материалы по дополнительным разделам дискретной математики.
© 2012, 2013 Симоненко Евгений А. <easimonenko@mail.ru>
Оглавление |
|
Введение.............................................................................................................................................. |
5 |
Библиография................................................................................................................................. |
5 |
Теория множеств............................................................................................................................... |
7 |
Множества и подмножества.......................................................................................................... |
7 |
Мощность множества.................................................................................................................... |
8 |
Операции над множествами.......................................................................................................... |
9 |
Декартово произведение............................................................................................................. |
10 |
Круги Эйлера................................................................................................................................ |
11 |
Мультимножества........................................................................................................................ |
11 |
Бинарные отношения................................................................................................................... |
11 |
Упорядоченные множества......................................................................................................... |
12 |
Множества в информатике и программировании..................................................................... |
12 |
Библиография............................................................................................................................... |
12 |
Комбинаторная теория................................................................................................................... |
13 |
Исчисление конечных сумм........................................................................................................ |
13 |
Правило сложения....................................................................................................................... |
13 |
Правило умножения..................................................................................................................... |
13 |
Метод включения и исключения................................................................................................ |
14 |
Перестановки............................................................................................................................... |
14 |
Размещения................................................................................................................................... |
14 |
Сочетания..................................................................................................................................... |
15 |
Перестановки с повторениями................................................................................................... |
16 |
Размещения с повторениями....................................................................................................... |
16 |
Сочетания с повторениями......................................................................................................... |
16 |
Бином Ньютона и полиномиальная формула............................................................................ |
16 |
Разбиения...................................................................................................................................... |
18 |
Генерация всех перестановок..................................................................................................... |
18 |
Генерация всех подмножеств...................................................................................................... |
20 |
Генерация всех размещений с повторениями............................................................................ |
21 |
Генерация сочетаний с повторениями....................................................................................... |
22 |
Генерация всех сочетаний без повторений................................................................................ |
22 |
Генерация всех размещений без повторений............................................................................ |
22 |
Генерация всех разбиений........................................................................................................... |
22 |
Библиография............................................................................................................................... |
23 |
Теория графов................................................................................................................................... |
25 |
Основные понятия....................................................................................................................... |
25 |
Представление графов................................................................................................................. |
27 |
Обход графа в глубину................................................................................................................. |
29 |
Обход графа в ширину................................................................................................................. |
30 |
Маршруты, цепи и циклы........................................................................................................... |
31 |
Связность...................................................................................................................................... |
31 |
Сочленения................................................................................................................................... |
32 |
Мосты............................................................................................................................................ |
32 |
Деревья.......................................................................................................................................... |
32 |
Эйлеровы графы........................................................................................................................... |
33 |
Гамильтоновы графы................................................................................................................... |
34 |
Планарные графы......................................................................................................................... |
35 |
Покрытие и независимость......................................................................................................... |
37 |
Ориентированные графы............................................................................................................. |
37 |
Библиография............................................................................................................................... |
38 |
Приложение Б. Рекуррентные соотношения................................................................................ |
39 |
Задача о ханойских башнях........................................................................................................ |
39 |
Задача о разрезании пиццы......................................................................................................... |
39 |
Задача Иосифа Флавия................................................................................................................ |
39 |
Библиография............................................................................................................................... |
40 |
Приложение В. Элементы теории чисел....................................................................................... |
41 |
Делимость и кратность................................................................................................................ |
41 |
Алгоритм Евклида....................................................................................................................... |
41 |
Простые числа.............................................................................................................................. |
41 |
Сравнения..................................................................................................................................... |
42 |
Библиография............................................................................................................................... |
43 |
Библиография................................................................................................................................... |
45 |
Введение |
5 |
Введение
Дисциплина «Дискретная математика» в образовании специалистов в области информатики и программирования является основополагающей. По важности в этом отношении с ней может сравниться только дисциплина «Алгоритмы и структуры данных».
Предметом дискретной математики являются конечные и счётные множества. В зависимости от того, какие множества изучаются и какие задачи при этом решаются, выделяются следующие разделы:
–комбинаторика (комбинаторная теория);
–исчисление конечных сумм;
–теория рекурсии;
–теория чисел;
–теория графов;
–математическая логика;
–теория алгоритмов;
–теория конечных автоматов.
Старейшим разделом дискретной математики является теория чисел, которая в давние времена носила название арифметики. Самыми же молодыми разделами являются теория графов, теория конечных автоматов и теория алгоритмов.
В этом курсе дискретной математики из вышеперечисленных разделов рассматриваются только комбинаторная теория и теория графов.
Лекционный курс начинается с изложения основных положений теории множеств, знание которых необходимо для изучения комбинаторики и теории графов.
Библиография
При подготовке этих лекций было использовано большое количество классических и современных учебников по дискретной математике и смежной тематике. Назовём здесь лишь
некоторые: |
[Баранов, Стечкин], [Грэхем, Кнут, Паташник], [Кузьмин: комбинаторные |
методы], |
[Кузьмин: комбинаторика], [Новиков], [Окулов: ДМ], [Оре: теория графов], |
[Скиена]. |
|