Файл: Дискрет-ная мат-ка_УМП.pdf

106

èêàãéÜÖçàÖ                                                  

ꇷӘ‡fl ÔðÓ„ð‡Ïχ ÔÓ ‰ËÒÍðÂÚÌÓÈ Ï‡ÚÂχÚËÍÂ

Специальность:  210405 «Радиосвязь,  радиовещание  и  те-

левидение». 

Факультет ― радиотехнический (РТФ). 
Профилирующая кафедра ― ТОР. 
Общая трудоемкость освоения курса ― 85 часов.  
Экзамен. 

1 ñÖãà à áÄÑÄóà äìêëÄ ÑàëäêÖíçéâ 
åÄíÖåÄíàäà 
Целью  преподавания  дисциплины  «Дискретная  математи-

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

2 èêéÉêÄååÄ äìêëÄ  
2.1 íÂÓðËfl ÏÌÓÊÂÒÚ‚ 

Множества, их элементы, подмножества, пустое множество, 

синглетон,  универсальное  множество,  булеан  множества,  диа-
граммы  Эйлера-Венна.  Объединение,  пересечение,  дополнение, 
разность, симметрическая разность. Законы де Моргана. Декар-
тово  произведение  множеств,  степень  множества.  Понятия  би-
нарного  и  п-арного  отношений.  Симметрия,  транзитивность  и 
рефлексивность  отношений.  Отношения  соответствия,  эквива-
лентности. Отображения.  

2.2 å‡ÚÂχÚ˘ÂÒ͇fl ÎÓ„Ë͇  
Традиционная  логика.  Понятие,  суждение,  категорические 

суждения,  умозаключение.  Логический  квадрат.  Модусы  и  фи-
гуры силлогизма. Логические законы. 

107

Понятия  высказывания  и  двоичной  переменной.  Аксиомы 

булевой алгебры логики. Операции дизъюнкции, конъюнкции и 
инверсии.  Язык  алгебры  логики.  Теоремы  одной  переменной. 
Теоремы  двух  и  большего  числа  переменных:  поглощения, 
склеивания и де Моргана.  

Булевы функции, способы их задания: аналитический, таб-

личный,  числовой,  диаграммами  Карно  (Вейча).  Эквивалент-
ность  формул.  Принцип  двойственности.  Дизъюнктивные  и 
конъюнктивные формы. Разложение булевых функций по пере-
менным (теорема Шеннона). Метод Квайна. Понятия импликан-
ты  и  простой  импликанты.  Неопределенные  состояния.  Мини-
мизация булевых функций в классе ДНФ и КНФ с учетом неоп-
ределенных состояний. Симметрические булевы функции. 

Понятие  функциональной  полноты  системы  функций.  Пять 

замечательных классов булевых функций: функции, сохраняющие 
нуль; функции, сохраняющие единицу, монотонные функции; ли-
нейные  функции;  самодвойственные  функции.  Понятие  суперпо-
зиции. Функциональная замкнутость замечательных классов. Тео-
рема  Поста  о  функциональной  полноте.  Элементарные  функции. 
Функционально полные системы элементарных функций.  

Алгебра Жегалкина. Перевод полиномов Жегалкина в буле-

ву алгебру, и наоборот. Карты Вейча в алгебре Жегалкина. 

Булево  дифференциальное  исчисление:  понятие  производ-

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

Логика  предикатов.  Кванторы  общности  и  существования. 

Проблема  разрешимости  в  логике  предикатов.  Интерпретации. 
Элементы теории моделей. Нечеткая и модальные логики. Мно-
гозначные логики. Критерий полноты в многозначной логике. 

2.3 íÂÓðËfl ÍÓ̘Ì˚ı ‡‚ÚÓχÚÓ‚ 
Понятие конечного автомата. Контактные элементы. Синтез 

параллельно-последовательных структур. 

Основные  логические  элементы.  Элементы  Пирса  и  Шеф-

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

108

Триггеры — запоминающие элементы. Триггеры типов RS, 

T и JK. Синхронные и асинхронные автоматы. Синтез синхрон-
ных многотактных автоматов. Примеры простейших автоматов: 
счетчики с произвольной последовательностью счета, распреде-
лители  импульсов.  Автоматы  Мили  и  Мура.  Эксперименты  с 
автоматами, тестирование автоматов. 

2.4 äÓÏ·Ë̇ÚÓðË͇ 
Понятие  факториала.  Правило  суммы  и  произведения. 

Принцип  включения-исключения.  Диаграммы  Эйлера-Венна. 
Комбинаторные  конфигурации:  перестановки,  размещения  и 
сочетания. Основные формулы для числа перестановок, сочета-
ний  и  размещений  с  повторениями  и  без  повторений.  Рекур-
рентные  соотношения  и  производящие  функции.  Комбинатор-
ные  задачи:  о  покрытии  множеств,  о  латинских  прямоугольни-
ках  и  квадратах.  Комбинаторика  в  теории  вероятностей.  Непо-
средственный  подсчет  вероятностей  с  применением  формул 
комбинаторики. Блок-схемы, конечные проективные плоскости. 
Матрицы Адамара. Модели шифросистем. 

2.5 ùÎÂÏÂÌÚ˚ ÚÂÓðËË „ð‡ÙÓ‚ 
Граф,  подграф,  надграф,  частичный  граф.  Смежность,  ин-

цидентность,  степень  вершины.  Однородный  и  полный  графы, 
дополнение  графа.  Матрицы  смежности  и  инциденций.  Мар-
шруты,  цепи,  циклы.  Алгоритм  поиска  всех  простых  цепей  в 
графе. Цикломатическое число графа. Связность графа. Эйлеро-
вы графы, уникурсальная линия в графе. Гамильтоновы графы. 
Задача поиска гамильтонова цикла в графе. Деревья и леса. Ко-
дирование  деревьев  методом  Пруфера.  Построение  дерева  по 
его коду. Хроматическое число графа. Двудольные графы. Пол-
ные  двудольные  графы.  Изоморфизм.  Планарные  и  плоские 
графы.  Критерий  Понтрягина—Куратовского.  Понятие  ориен-
тированного  графа  (орграфа).  Сильная  связность  в  орграфах. 
Элементы теории трансверсалей. Метод нахождения всех транс-
версалей.  Задача  о  коммивояжере.  Экстремальные  и  оптимиза-
ционные  задачи.  Анализ  графа  цепи  Маркова.  Транспортная 
сеть,  нахождение  ее  максимальной  пропускной  способности. 
Перечисление графов. 

109

2.6 íÂÓðËfl ‡Î„ÓðËÚÏÓ‚  
Понятие  алгоритма.  Интуитивное  определение  понятия  ал-

горитма.  Способы  задания  алгоритмов.  Свойства  алгоритмов. 
Типы  алгоритмов.  Формализация  понятия  алгоритма.  Машины 
Тьюринга-Поста.  Программирование  машины  Тьюринга-Поста. 
Равносильность формализаций алгоритма. Алгоритмически раз-
решимые и неразрешимые проблемы.