- •Русаков Алексей Михайлович
- •Лекции по дисциплине «Дискретная математика»
- •Введение.
- •Теория множеств.
- •Понятие множества. Операции над множествами.
- •Определение.
- •Определение.
- •Определение.
- •Пример.
- •Свойства операций сложения и пересечения множеств.
- •Определение.
- •Замечание.
- •Примеры.
- •Счётные множества. Теорема Кантора.
- •Определение.
- •Примеры счётных множеств.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Задачи для самостоятельного решения.
- •Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
- •Бинарные отношения в теории графов.
- •Например:
- •Матрицы смежности и инцидентности.
- •Пример.
- •Маршруты, цепи и простые цепи.
- •Определение
- •Расстояние и протяжённость в графе.
- •Деревья.
- •Примеры:
- •Например:
- •Помеченные графы. Перечисление помеченных деревьев.
- •Пример:
- •Теорема Келли.
- •Задача о кратчайшем соединении.
- •Задача о кратчайших путях.
- •Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
- •Доказательство:
- •Достаточность.
- •Индуктивный переход.
- •Гамильтовы циклы.
- •Пример:
- •Примеры задач и упражнений.
- •Решение.
- •Задачи для самостоятельного решения.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение группы.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение и способы описания формальных грамматик.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теория автоматов.
- •Основные понятия теории автоматов.
- •Определение.
- •Способы задания автоматов. Таблица переходов.
- •Определение.
- •Определение.
- •Способы задания автоматов. Граф автомата.
- •Определение.
- •Способы задания автоматов. Матрица переходов и выходов. Определение.
- •Машины Тьюринга и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Машины Тьюринга с двумя выходами.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматы с магазинной памятью и бесконтекстные языки.
- •Определение.
- •Определение.
- •Модель дискретного преобразователя Глушкова в. М. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Понятие об абстрактном автомате и индуцируемом им отображении. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматные отображения и события. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теорема.
- •Регулярные языки и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Правила подчинения мест в регулярных выражениях.
- •Определение.
- •Определение.
- •Правила построения основного алгоритма синтеза конечных автоматов.
- •Пример.
- •Автомат Мили.
- •Определение.
- •Определение.
- •Автомат Мура.
- •Определение.
- •Определение.
- •Теория булевых функций.
- •Связь булевых функций и схем из функциональных элементов и контактных схем. Определение.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Замечание.
- •Теорема. (Формулы разложения Клода Шеннона.)
- •Доказательство:
- •Замечания.
- •Основные свойства булевых функций. Замечание.
- •Определение.
- •Примеры задач и упражнений. Пример 1
- •Доказательство
- •Задачи для самостоятельного решения.
- •Элементы комбинаторики.
- •Основные понятия комбинаторики. Определение.
- •Определение.
- •Доказательство.
- •Теорема – правило включения-исключения.
- •Доказательство.
- •Доказательство.
- •8.2. Формулировка задания.
- •Определение.
- •Пример.
- •Переходы можно представить также с помощью таблицы и схематически:
- •Определение.
- •Последовательность выполнения.
- •Методический пример.
- •Контрольная распечатка.
- •Замечания.
- •Отчет по практической работе.
- •Контрольные вопросы
- •Варианты заданий.
- •Домашняя работа №1. По всей теории
- •Домашняя работа №2. Способы задания графов
- •8.03.2. Правила регулярного выражения.
- •Установка необходимого программного обеспечения.
- •Замечания.
- •Методический пример.
- •Контрольная распечатка.
- •Отчет по практической работе.
- •Контрольные вопросы.
- •Варианты заданий.
- •Дополнительные материалы.
- •Биография Георга Кантора (основатель теории множеств).
- •Город Калининград (Кёнигсберг).
- •Список литературы.
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ
Русаков Алексей Михайлович
RusakovAM.narod.ru
Лекции по дисциплине «Дискретная математика»
Москва 2011
Оглавление.
Введение. 3
Глава 1. Теория множеств. 4
Глава 2. Теория графов. 44
Глава 3. Основы теории формальных грамматик. 85
Глава 4. Теория автоматов. 101
Глава 5. Теория булевых функций. 152
Глава 6. Элементы теории доказательств. 172
Глава 7. Элементы комбинаторики. 186
Глава 8. Основная часть: практическая работа студентов 198
Практическое занятие №1. Разработка синтаксических анализаторов для регулярных языков. 198
Домашняя работа №1. По всей теории 213
Домашняя работа №2. Способы задания графов 214
Глава 9. Дополнительная часть: практическая работа студентов 280
Практическое занятие №1. Работа с регулярными выражениями на основе PERL . 280
Глава 10. Дополнительные материалы. 292
Глава 11. Список литературы. 295
Введение.
Дискретная математика — часть математики, которая зародилась в глубокой древности. В широком смысле этого слова к дискретной математике относятся как классические разделы математики: алгебра, теория чисел, теория множеств, математическая логика и т.д., так и новые разделы, которые возникли в середине прошлого столетия в связи с внедрением ЭВМ в практическую жизнь. В настоящее время понятие «дискретная математика» употребляется в узком смысле только для тех разделов современной математики, которые связаны с областью компьютерной науки. К ним относятся:
-
Теория множеств.
-
Теория графов.
-
Теория автоматов.
-
Теория формальных грамматик.
-
Теория булевых функций (переключательные функции).
-
Комбинаторика и другие разделы современной «компьютерной» математики.
Сегодня дискретная математика является важным звеном математического образования. Умение пользоваться «математическими аппаратами» дискретной математики является обязательным квалификационным требованием к специалистам в области информационных технологий.
-
Теория множеств.
-
Понятие множества. Операции над множествами.
-
В математике встречаются самые разнообразные множества. Можно говорить о множествах граней многогранника, точек, чисел и т.д.
Теория множеств, возникшая в конце XIX века, оказала и продолжает оказывать большое влияние на всю математику в целом.
По определению Георга Кантора (биография приведена в разделе дополнительные сведения), основоположника теории множеств, множество есть любое собрание определенных и различимых между собой объектов нашей интуиции или интеллекта, мыслимое нами как единое целое. Между отдельными объектами и множествами существует отношение принадлежности. Как правило, множества обозначают прописными буквами, а их элементы — малыми, которые перечисляются внутри фигурных скобок через запятую .
Определение.
Утверждение "элемент принадлежит множеству " символически записывается так: или , "элемент не принадлежит множеству " записывается так: или .
Определение.
Если все элементы, из которых состоит , входят и в , причем случай не исключается, то называется подмножеством .
Записывается это так: .
Например, целые числа образуют подмножество в множестве действительных чисел.
Иногда не известно заранее, содержит ли некое множество, например, множество действительных корней данного уравнения, хотя бы один элемент. Поэтому целесообразно ввести понятие пустого множества.
Определение.
Множество, не содержащее ни одного элемента, называется пустым множеством. Его обозначают символом .
Следствие из определения.
Любое множество содержит в качестве подмножества множество .
Определение.
Подмножества множества, отличные от него самого и от , называются собственными.
Определение.
Пусть и — множества. Тогда их суммой или объединением называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств или .
Рис. 1.1. .
Аналогично определяется сумма любого (конечного или бесконечного) числа множеств, а именно:
если — произвольное множество, то их сумма — есть совокупность элементов, каждый из которых принадлежит хотя бы одному из множеств .