- •Русаков Алексей Михайлович
- •Лекции по дисциплине «Дискретная математика»
- •Введение.
- •Теория множеств.
- •Понятие множества. Операции над множествами.
- •Определение.
- •Определение.
- •Определение.
- •Пример.
- •Свойства операций сложения и пересечения множеств.
- •Определение.
- •Замечание.
- •Примеры.
- •Счётные множества. Теорема Кантора.
- •Определение.
- •Примеры счётных множеств.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Задачи для самостоятельного решения.
- •Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
- •Бинарные отношения в теории графов.
- •Например:
- •Матрицы смежности и инцидентности.
- •Пример.
- •Маршруты, цепи и простые цепи.
- •Определение
- •Расстояние и протяжённость в графе.
- •Деревья.
- •Примеры:
- •Например:
- •Помеченные графы. Перечисление помеченных деревьев.
- •Пример:
- •Теорема Келли.
- •Задача о кратчайшем соединении.
- •Задача о кратчайших путях.
- •Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
- •Доказательство:
- •Достаточность.
- •Индуктивный переход.
- •Гамильтовы циклы.
- •Пример:
- •Примеры задач и упражнений.
- •Решение.
- •Задачи для самостоятельного решения.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение группы.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение и способы описания формальных грамматик.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теория автоматов.
- •Основные понятия теории автоматов.
- •Определение.
- •Способы задания автоматов. Таблица переходов.
- •Определение.
- •Определение.
- •Способы задания автоматов. Граф автомата.
- •Определение.
- •Способы задания автоматов. Матрица переходов и выходов. Определение.
- •Машины Тьюринга и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Машины Тьюринга с двумя выходами.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматы с магазинной памятью и бесконтекстные языки.
- •Определение.
- •Определение.
- •Модель дискретного преобразователя Глушкова в. М. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Понятие об абстрактном автомате и индуцируемом им отображении. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматные отображения и события. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теорема.
- •Регулярные языки и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Правила подчинения мест в регулярных выражениях.
- •Определение.
- •Определение.
- •Правила построения основного алгоритма синтеза конечных автоматов.
- •Пример.
- •Автомат Мили.
- •Определение.
- •Определение.
- •Автомат Мура.
- •Определение.
- •Определение.
- •Теория булевых функций.
- •Связь булевых функций и схем из функциональных элементов и контактных схем. Определение.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Замечание.
- •Теорема. (Формулы разложения Клода Шеннона.)
- •Доказательство:
- •Замечания.
- •Основные свойства булевых функций. Замечание.
- •Определение.
- •Примеры задач и упражнений. Пример 1
- •Доказательство
- •Задачи для самостоятельного решения.
- •Элементы комбинаторики.
- •Основные понятия комбинаторики. Определение.
- •Определение.
- •Доказательство.
- •Теорема – правило включения-исключения.
- •Доказательство.
- •Доказательство.
- •8.2. Формулировка задания.
- •Определение.
- •Пример.
- •Переходы можно представить также с помощью таблицы и схематически:
- •Определение.
- •Последовательность выполнения.
- •Методический пример.
- •Контрольная распечатка.
- •Замечания.
- •Отчет по практической работе.
- •Контрольные вопросы
- •Варианты заданий.
- •Домашняя работа №1. По всей теории
- •Домашняя работа №2. Способы задания графов
- •8.03.2. Правила регулярного выражения.
- •Установка необходимого программного обеспечения.
- •Замечания.
- •Методический пример.
- •Контрольная распечатка.
- •Отчет по практической работе.
- •Контрольные вопросы.
- •Варианты заданий.
- •Дополнительные материалы.
- •Биография Георга Кантора (основатель теории множеств).
- •Город Калининград (Кёнигсберг).
- •Список литературы.
Определение.
Местами в правильно записанном регулярном выражении R над алфавитом X = (x1,…,xn) условимся называть специально вводимые знаки раздела (вертикальные линии), ставящиеся между любыми двумя знаками этого выражения (знаками в выражении R являются буквы алфавита Х, символ пустого слова ε, знак дизъюнкции, итерационные и обычные скобки).
Определение.
Кроме этих так называемых разделяющих мест (знаков раздела) вводится еще два места – начальное и конечное. Первое их них располагается слева от самого левого знака выражения R, а второе – справа от самого правого знака.
Например, R = z ∨ x {y ∨ z}, где R – регулярное выражение.
Приведем это выражение к правильной форме R = (z ∨ x {y ∨ z}).
Проведем разметку
Из этого выражения видно, что регулярное выражение R имеет 11 мест.
Развернем данное регулярное выражение в слово, то есть последовательно, буква за буквой, выпишем какое-либо слово из представляемого им события. При этом развертывание, будем осуществлять переходя от одного места данного регулярного выражения к другому и от начального места к конечному месту. Такие переходы бывают двух видов – непосредственный переход и переход через букву основного алфавита Х, в котором задается представляемое выражением событие.
Например, рассмотрим процессы развертывания размеченного выше выражения R в принадлежащие представляемому им событию слова z и xyz.
При развертывании выражения в первое слово необходимо осуществить непосредственный переход от начального места 1 к месту 2, переход через букву z от места 2 к месту 3 и непосредственный переход от 3 к конечному месту 11.
При развертывании выражения в слово xyz порядок переходов будет следующий: непосредственный переход от места 1 к месту 4 переход через букву x – от 4 к 5, непосредственный переход – от 5 к 6, переход через букву у – от 6 к 7, непосредственный переход от 7 к 10, непосредственный переход от 10 к 8, переход через букву z – от 8 к 9, непосредственный переход от 9 к 10 и непосредственный переход от 10 к 11.
Пусть R – регулярное выражение, q = xi1 xi2 … xik произвольное слово во входном алфавите события, представляемого выражением R.
Условимся, что место α в выражении R связано словом q с местом β в том же выражении, если от места α к месту β можно перейти с помощью чередования любого числа непосредственных переходов и переходов через буквы xi1, xi2, …, xik слова q, взятых по одному разу в том порядке, в каком они входят в слово.
Это условие означает, что место β q–следует за местом α всякий раз, когда α связано с местом β словом q.
Также условимся говорить, что место β подчинено месту α, если от места α к месту β можно перейти с помощью одних лишь непосредственных переходов, т. е. если место α связано с местом β пустым словом ε.
-
Правила подчинения мест в регулярных выражениях.
1. Начальные места всех термов многочлена, помещенного в обычные или итерационные скобки, подчинены месту, находящемуся непосредственно слева от открывающей скобки из пары скобок, в которые заключен данный многочлен (многочлен по этому правилу может вырождаться в одночлен с обязательным заключением его в скобки).
2. Место, расположенное непосредственно справа от закрывающей (итерационной или обыкновенной) скобки подчинено конечным местам всех термов многочлена (в частном случае, одночлена), заключенного в соответствующие скобки, а в случае итерационных скобок – также месту, расположенному непосредственно слева от соответствующей открывающей скобки.
3. Начальные места всех термов многочлена (в частном случае, одночлена), заключенного в итерационные скобки, подчинены месту, расположенному непосредственно справа от соответствующей закрывающей скобки.
4. Место, расположенное непосредственно справа от символа пустого слова ε, подчинено месту, расположенному непосредственно слева от этого символа.
5. Если место γ подчинено месту β, а место β подчинено месту α, то место γ подчинено месту α (свойства транзитивности для отношения подчиненности мест).
6. Каждое место подчинено самому себе.
В качестве примера использования приведенной системы правил установим отношение подчиненности мест для рассмотренного выше регулярного выражения. Место 1 кроме самого себя не подчинено никаким другим местам. То же самое относится к местам 3, 5, 7, 9.
Места 2, 4 кроме самих себя, подчинены месту 1 (по правилу 1).
Место 6 и 8 – месту 5 (по правилу 1) и месту 10 (по правилу 3).
Место 10 подчинено (кроме самого себя) местам 5,7 и 9 (по правилу 2).
Место 11 подчинено (кроме самого себя) местам 3 и 10 (по правилу 2) и местам 5, 7 и 9 (по правилу 5).