- •Русаков Алексей Михайлович
- •Лекции по дисциплине «Дискретная математика»
- •Введение.
- •Теория множеств.
- •Понятие множества. Операции над множествами.
- •Определение.
- •Определение.
- •Определение.
- •Пример.
- •Свойства операций сложения и пересечения множеств.
- •Определение.
- •Замечание.
- •Примеры.
- •Счётные множества. Теорема Кантора.
- •Определение.
- •Примеры счётных множеств.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Задачи для самостоятельного решения.
- •Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
- •Бинарные отношения в теории графов.
- •Например:
- •Матрицы смежности и инцидентности.
- •Пример.
- •Маршруты, цепи и простые цепи.
- •Определение
- •Расстояние и протяжённость в графе.
- •Деревья.
- •Примеры:
- •Например:
- •Помеченные графы. Перечисление помеченных деревьев.
- •Пример:
- •Теорема Келли.
- •Задача о кратчайшем соединении.
- •Задача о кратчайших путях.
- •Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
- •Доказательство:
- •Достаточность.
- •Индуктивный переход.
- •Гамильтовы циклы.
- •Пример:
- •Примеры задач и упражнений.
- •Решение.
- •Задачи для самостоятельного решения.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение группы.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение и способы описания формальных грамматик.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теория автоматов.
- •Основные понятия теории автоматов.
- •Определение.
- •Способы задания автоматов. Таблица переходов.
- •Определение.
- •Определение.
- •Способы задания автоматов. Граф автомата.
- •Определение.
- •Способы задания автоматов. Матрица переходов и выходов. Определение.
- •Машины Тьюринга и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Машины Тьюринга с двумя выходами.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматы с магазинной памятью и бесконтекстные языки.
- •Определение.
- •Определение.
- •Модель дискретного преобразователя Глушкова в. М. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Понятие об абстрактном автомате и индуцируемом им отображении. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматные отображения и события. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теорема.
- •Регулярные языки и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Правила подчинения мест в регулярных выражениях.
- •Определение.
- •Определение.
- •Правила построения основного алгоритма синтеза конечных автоматов.
- •Пример.
- •Автомат Мили.
- •Определение.
- •Определение.
- •Автомат Мура.
- •Определение.
- •Определение.
- •Теория булевых функций.
- •Связь булевых функций и схем из функциональных элементов и контактных схем. Определение.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Замечание.
- •Теорема. (Формулы разложения Клода Шеннона.)
- •Доказательство:
- •Замечания.
- •Основные свойства булевых функций. Замечание.
- •Определение.
- •Примеры задач и упражнений. Пример 1
- •Доказательство
- •Задачи для самостоятельного решения.
- •Элементы комбинаторики.
- •Основные понятия комбинаторики. Определение.
- •Определение.
- •Доказательство.
- •Теорема – правило включения-исключения.
- •Доказательство.
- •Доказательство.
- •8.2. Формулировка задания.
- •Определение.
- •Пример.
- •Переходы можно представить также с помощью таблицы и схематически:
- •Определение.
- •Последовательность выполнения.
- •Методический пример.
- •Контрольная распечатка.
- •Замечания.
- •Отчет по практической работе.
- •Контрольные вопросы
- •Варианты заданий.
- •Домашняя работа №1. По всей теории
- •Домашняя работа №2. Способы задания графов
- •8.03.2. Правила регулярного выражения.
- •Установка необходимого программного обеспечения.
- •Замечания.
- •Методический пример.
- •Контрольная распечатка.
- •Отчет по практической работе.
- •Контрольные вопросы.
- •Варианты заданий.
- •Дополнительные материалы.
- •Биография Георга Кантора (основатель теории множеств).
- •Город Калининград (Кёнигсберг).
- •Список литературы.
Определение.
Полностью отображение δ изображают с помощью диаграммы состояний, то есть ориентированного графа, вершинам которого поставлены в соответствие символы Q, а дугам – команды отображения δ.
Если автомат оказывается в ситуации (qj, xi), не являющейся левой частью какой-либо его команды, то он останавливается.
Определение.
Если управляющее устройство считает все символы цепочки α, записанной на ленту, и при этом перейдет в состояние qf ∈ F (заключительное состояние), то говорят, что цепочка α допускается автоматом А (автомат допускает цепочку α).
Определение.
Множество цепочек, допускаемых данным автоматом, называют языком этого автомата.
Отображение δ можно представить и в виде функции:
δ (q, x) = q′,
где q, q′∈ Q; x ∈ X.
Эта функция интерпретируется так же, как и команда (q, x) → q′. Её можно распространить с одного входного символа на цепочку следующим образом: δ(q, ε) = q, где ε – пустая цепочка;
δ(q, αx) = δ(δ(q, α), x), где х ∈ Х, α ∈ Х*.
Таким образом, можно сказать, что α допускается автоматом А, если δ(q0, α) = qf , где qf ∈ F, а язык, допускаемый автоматом А, это
L(A) = {α | δ(q0, α)∈ F}.
Пример.
Рассмотрим пример детерминированного конечного автомата
А = (X, Q, δ, q0, F),
где Х = {a, b}; Q = {S, Y, Z, T}; q0 = S; F = {T}, а δ задается диаграммой состояний, представленной на рис. 4.9.
Рис. 4.9. Диаграмма состояний детерминированного конечного автомата
Очевидно, что язык, допускаемый этим автоматом,
L(A) = {Mn | n ≥ 1},
где M = {aa, bb}.
Цепочка α1 = aabbaa, допускается данным автоматом, так как после ее просмотра автомат окажется в состоянии Т∈ F.
Цепочка aabba не допускается, так как после ее просмотра автомат окажется в состоянии Y, не являющемся заключительным.
Цепочка abb не допускается потому, что после считывания символа а автомат окажется в ситуации (Y, b), для которой нет команды.
Определение.
Недетерминированный конечный автомат – есть пятерка того же вида. Единственное отличие заключается в том, что значениями функции переходов являются не состояния, а множество состояний (или, в терминах команд, возможны различные команды с одинаковыми левыми частями). Это соответствует тому факту, что в диаграмме состояний из одной вершины может исходить несколько дуг с одинаковой меткой.
-
Машины Тьюринга с двумя выходами.
С точки зрения лингвистики машины Тьюринга можно рассматривать как распознающие устройства, допускающие языки самого широкого из рассмотренных классов: языки типа 0 или рекурсивно-перечислимые множества.
Определение.
Машина Тьюринга состоит из конечного управляющего устройства, входной ленты и головки, которая в отличие от головки конечного автомата может не только считывать символы с ленты, но и записывать на нее новые символы.
Лента считается бесконечной. Перед началом работы n ячеек ленты содержат символы входной цепочки αi = xi1 , xi2 ,..., xin, все остальные ячейки считаются заполненными специальным символом В («пустое место»), который не является входным (рис. 4.10).
Рис. 4.10. Интерпретация машины Тьюринга