- •Содержание дисциплины "Дискретная математика" введение
- •Входная контрольная работа
- •1Вариант
- •2 Вариант
- •Раздел 1. Основы теории множеств
- •Тема 1.1 Основные понятия теории множеств.
- •Тема 1.2 Операции над множествами.
- •Самостоятельная работа № 1
- •Тема 1.3 Свойства операций.
- •Контрольная работа
- •1 Вариант
- •2 Вариант
- •Раздел 2. Формулы логики.
- •Тема 2.1 Основные логические операции.
- •Тема 2.2 Формулы логики.
- •Самостоятельная работа №2.
- •Тема 2.3 Дизъюнктивная нормальная форма.
- •Различны все члены дизъюнкции;
- •Тема 2.4 Конъюнктивная нормальная форма.
- •Тема 2.5 Равносильные формулы. Свойства.
- •Раздел 3. Булевы функции.
- •Тема 3.1 Понятие булевой функции.
- •Тема 3.2 Совершенная днф. Совершенная кнф. Совершенной дизъюнктивной формой формулы алгебры высказываний (сднф) называется днф, в которой:
- •Различны все члены дизъюнкции;
- •Самостоятельная работа №5.
- •Тема 3.3 Минимальная днф.
- •Тема 3.4 Представление булевой функции в виде минимальной днф.
- •Самостоятельная работа №6. Самостоятельная работа №7
- •Тема 3.5 Полнота множества функций.
- •Тема 3.6 Важнейшие замкнутые классы.
- •Важнейшие замкнутые классы в р2
- •Тема 3.7 Теорема Поста.
- •Примеры использования теоремы Поста.
- •3. Составим критериальную таблицу для другой полной системы функций из р2: {0, 1, x1x2, x1x2}.
- •Контрольная работа
- •Раздел 4. Предикаты и бинарные отношения.
- •Тема 4.1 Понятие предиката. Область определения и область истинности предиката.
- •Тема 4.2 Логические операции над предикатами.
- •Самостоятельная работа №8.
- •Тема 4.3 Кванторные операции над предикатами.
- •2. Квантор существования
- •- «Все люди любят всех людей».
- •- «Существует человек, который кого-то любит» .
- •- «Существует человек, который любит всех людей».
- •Тема 4.4 Понятие предикатной формулы.
- •Тема 4.5 Равносильность предикатов. Исчисление предикатов.
- •Самостоятельная работа №9.
- •Тема 4.6 Бинарные отношения и их свойства.
- •Самостоятельная работа №10. Контрольная работа
- •Раздел 5. Отображения. Подстановки.
- •Тема 5.1 Отображения и их свойства.
- •Самостоятельная работа №11.
- •Тема 5.2 Композиция отображений и обратное отображение.
- •Тема 5.3 Подстановки. Обратные подстановки. Формула количества подстановок.
- •Самостоятельная работа №12. Контрольная работа
- •1 Вариант
- •2 Вариант
- •3 Вариант
- •4 Вариант
- •5 Вариант
- •Раздел 6. Метод математической индукции.
- •Тема 6.1 Принцип метода математической индукции.
- •Раздел 7. Основы теории графов.
- •Тема 7.1 Понятие неориентированный граф. Основные определения.
- •Лабораторная работа № 1.
- •Тема 7.2 Теорема о сумме степеней вершин графа. Полный граф, его свойства.
- •Лабораторная работа № 2.
- •Тема 7.3 Метрические характеристики графа.
- •Лабораторная работа № 3.
- •Тема 7.4 Двудольные и изоморфные графы.
- •Лабораторная работа № 4.
- •Тема 7.5 Эйлеровы и гамильтоновы графы.
- •Лабораторная работа № 5
- •Тема 7.6 Плоские графы.
- •Тема 7.7 Деревья. Код Пруфера.
- •Тема 7.8 Понятие ориентированный граф (орграф).
- •Тема 7.9 Достижимость вершин в орграфе.
- •Раздел 8. Элементы теории алгоритмов.
- •Тема 8.1 Определение класса финитно-поставленных задач.
- •Тема 8.2 Машины Тьюринга.
- •Тема 8.3 Уточнения понятия алгоритм.
- •Итоговая (выходная) контрольная работа.
Тема 7.9 Достижимость вершин в орграфе.
Вершина А достижима из вершины В, если существует путь от В до А.
Для ориентированного графа Г вводят матрицу достижимости, следующего вида:
г де , если вершина достижима из вершины и , если не достижима.
Считается, что вершина достижима сама из себя, т.е. элементы главной диагонали матрицы достижимости равны 1.
Раздел 8. Элементы теории алгоритмов.
Тема 8.1 Определение класса финитно-поставленных задач.
Класс однотипных задач называется классом финитно-поставленных задач, если существует конечный алфавит А, словами которого можно закодировать условие и ответ любой задачи этого класса.
Класс финитно-поставленных задач можно свести к задаче вычисления значений некоторой функции на множестве N.
Пусть f(n) определена на N, закодируем все слова с помощью конечного алфавита А={а1, …аn} следующим образом: берем каждый символ и ставим ему в соответствие его порядковый номер.
, тогда если - слова, то
где р – все простые числа
При этом натуральное число является кодом, если оно делиться на все простые числа, начиная с 2 и заканчивая этим числом. Тогда если к – некоторый класс финитно-поставленных задач и существуют конечные алфавиты, словами которого можно закодировать условие и ответ, то задача сводиться к определению кода на множестве N.
Общий метод решения задач в данном случае имеет вид:
Задача → кодируем условие на N( )→ вычисляем ( )→ декодируем ответ.
Функция - называется кодовой.
Тема 8.2 Машины Тьюринга.
Будем считать, что машина Тьюринга имеет ленту (магнитную, печатную и т.д.), которая бесконечна в обе стороны и разбита на участки называемые ячейками. Имеется считывающее устройство и существует механизм, который передвигает это устройство, как вправо, так и влево. Дан конечный алфавит А, следующего вида:
, где - пустой знак
В каждую ячейку машина может печатать только один знак. Алфавит А называется внешним алфавитом машины.
Считаем, что машина может находиться в одном из конечного числа состояний: . Состояние Q – называется внутренним алфавитом машины, где - пассивное состояние машины, а все остальные состояния называются активными состояниями машины.
В каждый момент времени t считывающее устройство видит только одну ячейку и при этом на ленте конечное число знаков (не пустых символов).
Если в момент времени t машина находиться в состоянии и обозревает ячейку , то называется локальной информацией машины.
Участок между непустыми символами - называется глобальной информацией машины.
Машина делает 4 операции:
переход от состояния к состоянию - называется сменой состояния
смена обозреваемого значка: в
считывающее устройство передвигается на одну ячейку вправо (П)
считывающее устройство передвигается на одну ячейку влево (Л)
Работа машины заключается в следующей последовательности шагов:
смена обозреваемого значка и смена состояния: ;
машина меняет состояние и двигается на одну ячейку вправо: ;
машина меняет состояние и двигается на одну ячейку влево: ;
Выполнение этих шагов осуществляется под действием команды (приказы), которые зависят от настоящей ситуации.
Множество приказов обозначается: и называется программой машины.