Материал: Дискретная математика. Методичка. Кацаран
Федеральное
агентство
по
образованию
Государственное
образовательное
учреждение
Высшего
профессионального
образования
МНОЖЕСТВА
.
БИНАРНЫЕ
ОТНОШЕНИЯ
.
КОМБИНАТОРИКА
Методическое
пособие
для
вузов
Для
студентов
1
курса
дневного
и
вечернего
отделений
факультета
прикладной
математики
,
информатики
и
механики
Составители
:
Т
.
К
.
Кацаран
Л
.
Н
.
Строева
Издательско
-
полиграфический
центр
Воронежского
государственного
университета
2007
Утверждено
научно
-
методическим
советом
факультета
ПММ
ВГУ
19
октября
2007
г
.,
протокол
№
2
Рецензент
д
.
т
.
н
.,
профессор
кафедры
математических
методов
исследования
операций
факультета
прикладной
математики
,
информатики
и
механики
Т
.
М
.
Леденева
Учебное
пособие
подготовлено
на
кафедре
нелинейных
колебаний
факультета
прикладной
математики
,
информатики
и
механики
Воронежского
государственного
факультета
.
Рекомендуется
для
студентов
1
курса
дневного
и
вечернего
отделения
факультета
Прикладной
математики
,
информатики
и
механики
ВГУ
Для
специальности
: 010201 –
Математика
,
Прикладная
математика
Курс дискретной математики представляет собой объединение сле-
дующих взаимосвязанных разделов: множества, отношения, комбинато-
рика, математическая логика, булевы функции и их приложения, алго-
ритмы, графы и их применение, кодирование.
Согласно учебному плану по специальности
Прикладная матема-
тика и информатика
более четверти объема информации по данному
курсу рекомендуется для самостоятельного изучения. В связи с этим и
по причине отсутствия доступной литературы по некоторым разделам
курса авторами подготовлено данное методическое пособие.
Методическое пособие содержит краткий курс лекций по дисци-
плине
Дискретная математика
, читаемому на факультете ПММ для
студентов 1 курса дневного и вечернего отделений, программу курса
Дискретная математика
и состоит из четырех глав, в которых изло-
жены основные понятия (определения) и факты (утверждения, свойства,
теоремы и их следствия) по темам
Множества
,
Бинарные отноше-
ния
,
Комбинаторика
,
Линейные рекуррентные соотношения вто-
рого порядка
. Особое внимание уделено доказательствам теорем, так
как они содержат в себе методику исследования и решения теоретиче-
ских и практических задач разного уровня, приведенных в конце каждой
из глав.
ПРОГРАММА КУРСА
ДИСКРЕТНАЯ МАТЕМАТИКА
I. Множества и отношения
. Канторовское описание множества.
Способы задания множеств. Операции над множествами и их свойства.
Мощность конечного множества. Булеан множества, прямое произведе-
ние двух и более множеств, степень множества, вычисление мощности
конечного множества.
Определение и способы задания отношений. Операции над отноше-
ниями. Свойства бинарных отношений. Отношение эквивалентности и
разбиение множества на классы, их взаимосвязь. Отношения строгого и
нестрогого порядка. Частично и вполне упорядоченные множества.
II. Комбинаторика
. Правило суммы и правило произведения. По-
нятие k-выборки. Размещения, перестановки, сочетания. Бином Ньюто-
на. Свойства сочетаний.
Формула включений и исключений и ее применение.
III. Линейные рекуррентные соотношения (ЛРС) второго
порядка
. Общее и частное решение ЛРС в случае простых и кратных
корней характеристического уравнения. Уравнение и числа Фибоначчи.
IV. Математическая логика
. Высказывания. Операции над вы-
3
сказываниями и их свойства. Формулы алгебры высказываний. Равно-
сильность формул. Дизъюнктивная и конъюнктивная нормальные фор-
мы. Основные правила теории доказательств.
V. Предикаты
. Определение предикатов и способы их задания.
Операции над предикатами. Формулы логики предикатов. Равносиль-
ность формул. Кванторы общности и существования n-местных и одно-
местных предикатов и их свойства.
Теоретико-множественный смысл предикатов.
Приведенная и предваренная нормальные формы.
VI. Булевы функции и их приложения
. Определение и спосо-
бы задания булевых функций от n переменных. Элементарные булевы
функции. Принцип двойственности и его применение.
Специальные виды формул. Совершенные дизъюнктивная и конъ-
юнктивная нормальные формы. Полином Жегалкина.
Операция замыкания и ее свойства. Основные замкнутые классы.
Леммы о несамодвойственной, немонотонной и нелинейной функциях.
Замкнутость и полнота. Теорема о полноте двух систем. Теорема о
функциональной полноте, ее значение и практическое применение.
Применение булевых функций к синтезу и анализу дискретных уст-
ройств. Синтез сумматора.
Задача минимизации дизъюнктивных нормальных форм (ДНФ). Ми-
нимальная и кратчайшая ДНФ. Сокращенная ДНФ и способы ее постро-
ения. Тупиковая ДНФ.
VII. Алгоритмы
. Интуитивное описание алгоритма и его свойства.
Машина Тьюринга. Функции, вычислимые по Тьюрингу.
Кодирование машины Тьюринга. Самоприменимые и несамоприме-
нимые машины Тьюринга. Алгоритмически неразрешимые проблемы.
Вычислимые функции. Правила подстановки, примитивной рекур-
сии и взятия
µ
-оператора. Функции примитивно-рекурсивные, обще-
рекурсивные и частично-рекурсивные.
VIII. Графы и их применение
. Основные понятия теории гра-
фов. Отношение связности на множестве вершин графа. Компоненты
связности графа. Связные графы.
Деревья. Характеристическое свойство дерева. Остов графа. Теоре-
ма о соотношении числа вершин и ребер в дереве.
Эйлеровы графы. Необходимое и достаточное условие эйлеровости
графа. Задача о кенигсбергских мостах.
Операции над подграфами. Цикломатическое число графа. Теоремы
о размерности подпространства всех четных подграфов связного графа
и графа с
n
компонентами связности.
4
Задача о раскраске географической карты. Правильно раскрашен-
ный граф. Хроматическое число графа и хроматический класс графа.
Бихроматические графы. Необходимое и достаточное условие бихрома-
тичности графа.
Внутренне устойчивое и внешне устойчивое множества. Числа внут-
ренней и внешней устойчивости графа. Ядро графа.
Транспортные сети. Основная задача теории транспортных сетей.
Алгоритм Форда-Фалкерсона построения потока максимальной величи-
ны. Обоснование алгоритма Форда-Фалкерсона.
IX. Кодирование
. Постановка основных задач теории кодирова-
ния. Алфавитное и равномерное кодирование. Критерий однозначности
декодирования. Самокорректирующиеся коды. Коды Хемминга.
Кодовое дерево. Методы кодирования для ансамбля сообщений. Ме-
тод Шеннона-Фано и Хаффмэна.
5