Файл: Дискретная математика. Методичка. Кацаран.pdf

Федеральное

агентство

по

образованию

Государственное

образовательное

учреждение

Высшего

профессионального

образования

МНОЖЕСТВА

. 

БИНАРНЫЕ

ОТНОШЕНИЯ

. 

КОМБИНАТОРИКА

Методическое

пособие

для

вузов

Для

студентов

 1 

курса

дневного

и

вечернего

отделений

факультета

прикладной

математики

, 

информатики

и

механики

Составители

: 

Т

.

К

. 

Кацаран

Л

.

Н

. 

Строева

Издательско

-

полиграфический

центр

Воронежского

государственного

университета

2007 

Утверждено

научно

-

методическим

советом

факультета

ПММ

ВГУ

 19 

октября

 2007 

г

., 

протокол

№

2 

Рецензент

д

.

т

.

н

., 

профессор

кафедры

математических

методов

исследования

операций

факультета

прикладной

математики

, 

информатики

и

механики

Т

.

М

. 

Леденева

Учебное

пособие

подготовлено

на

кафедре

нелинейных

колебаний

факультета

прикладной

математики

, 

информатики

и

механики

Воронежского

государственного

факультета

. 

Рекомендуется

для

студентов

 1 

курса

дневного

и

вечернего

отделения

факультета

Прикладной

математики

, 

информатики

и

механики

ВГУ

Для

специальности

: 010201 – 

Математика

, 

Прикладная

математика

Курс дискретной математики представляет собой объединение сле-

дующих взаимосвязанных разделов: множества, отношения, комбинато-
рика, математическая логика, булевы функции и их приложения, алго-
ритмы, графы и их применение, кодирование.

Согласно учебному плану по специальности

Прикладная матема-

тика и информатика

более четверти объема информации по данному

курсу рекомендуется для самостоятельного изучения. В связи с этим и
по причине отсутствия доступной литературы по некоторым разделам
курса авторами подготовлено данное методическое пособие.

Методическое пособие содержит краткий курс лекций по дисци-

плине

Дискретная математика

, читаемому на факультете ПММ для

студентов 1 курса дневного и вечернего отделений, программу курса

Дискретная математика

и состоит из четырех глав, в которых изло-

жены основные понятия (определения) и факты (утверждения, свойства,
теоремы и их следствия) по темам

Множества

,

Бинарные отноше-

ния

,

Комбинаторика

,

Линейные рекуррентные соотношения вто-

рого порядка

. Особое внимание уделено доказательствам теорем, так

как они содержат в себе методику исследования и решения теоретиче-
ских и практических задач разного уровня, приведенных в конце каждой
из глав.

ПРОГРАММА КУРСА

ДИСКРЕТНАЯ МАТЕМАТИКА

I. Множества и отношения

. Канторовское описание множества.

Способы задания множеств. Операции над множествами и их свойства.
Мощность конечного множества. Булеан множества, прямое произведе-
ние двух и более множеств, степень множества, вычисление мощности
конечного множества.

Определение и способы задания отношений. Операции над отноше-

ниями. Свойства бинарных отношений. Отношение эквивалентности и
разбиение множества на классы, их взаимосвязь. Отношения строгого и
нестрогого порядка. Частично и вполне упорядоченные множества.

II. Комбинаторика

. Правило суммы и правило произведения. По-

нятие k-выборки. Размещения, перестановки, сочетания. Бином Ньюто-
на. Свойства сочетаний.

Формула включений и исключений и ее применение.

III. Линейные рекуррентные соотношения (ЛРС) второго

порядка

. Общее и частное решение ЛРС в случае простых и кратных

корней характеристического уравнения. Уравнение и числа Фибоначчи.

IV. Математическая логика

. Высказывания. Операции над вы-

3

сказываниями и их свойства. Формулы алгебры высказываний. Равно-
сильность формул. Дизъюнктивная и конъюнктивная нормальные фор-
мы. Основные правила теории доказательств.

V. Предикаты

. Определение предикатов и способы их задания.

Операции над предикатами. Формулы логики предикатов. Равносиль-
ность формул. Кванторы общности и существования n-местных и одно-
местных предикатов и их свойства.

Теоретико-множественный смысл предикатов.
Приведенная и предваренная нормальные формы.

VI. Булевы функции и их приложения

. Определение и спосо-

бы задания булевых функций от n переменных. Элементарные булевы
функции. Принцип двойственности и его применение.

Специальные виды формул. Совершенные дизъюнктивная и конъ-

юнктивная нормальные формы. Полином Жегалкина.

Операция замыкания и ее свойства. Основные замкнутые классы.

Леммы о несамодвойственной, немонотонной и нелинейной функциях.

Замкнутость и полнота. Теорема о полноте двух систем. Теорема о

функциональной полноте, ее значение и практическое применение.

Применение булевых функций к синтезу и анализу дискретных уст-

ройств. Синтез сумматора.

Задача минимизации дизъюнктивных нормальных форм (ДНФ). Ми-

нимальная и кратчайшая ДНФ. Сокращенная ДНФ и способы ее постро-
ения. Тупиковая ДНФ.

VII. Алгоритмы

. Интуитивное описание алгоритма и его свойства.

Машина Тьюринга. Функции, вычислимые по Тьюрингу.

Кодирование машины Тьюринга. Самоприменимые и несамоприме-

нимые машины Тьюринга. Алгоритмически неразрешимые проблемы.

Вычислимые функции. Правила подстановки, примитивной рекур-

сии и взятия

µ

-оператора. Функции примитивно-рекурсивные, обще-

рекурсивные и частично-рекурсивные.

VIII. Графы и их применение

. Основные понятия теории гра-

фов. Отношение связности на множестве вершин графа. Компоненты
связности графа. Связные графы.

Деревья. Характеристическое свойство дерева. Остов графа. Теоре-

ма о соотношении числа вершин и ребер в дереве.

Эйлеровы графы. Необходимое и достаточное условие эйлеровости

графа. Задача о кенигсбергских мостах.

Операции над подграфами. Цикломатическое число графа. Теоремы

о размерности подпространства всех четных подграфов связного графа
и графа с

n

компонентами связности.

4

Задача о раскраске географической карты. Правильно раскрашен-

ный граф. Хроматическое число графа и хроматический класс графа.
Бихроматические графы. Необходимое и достаточное условие бихрома-
тичности графа.

Внутренне устойчивое и внешне устойчивое множества. Числа внут-

ренней и внешней устойчивости графа. Ядро графа.

Транспортные сети. Основная задача теории транспортных сетей.

Алгоритм Форда-Фалкерсона построения потока максимальной величи-
ны. Обоснование алгоритма Форда-Фалкерсона.

IX. Кодирование

. Постановка основных задач теории кодирова-

ния. Алфавитное и равномерное кодирование. Критерий однозначности
декодирования. Самокорректирующиеся коды. Коды Хемминга.

Кодовое дерево. Методы кодирования для ансамбля сообщений. Ме-

тод Шеннона-Фано и Хаффмэна.

5