Предмет и метод теории дискретных систем управления

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

«Тульский государственный университет»

Политехнический институт

Кафедра Автоматизированных станочных систем

Орлов А.Б.

Профессор, д.т.н.

КОНСПЕКТ ЛЕКЦИЙ

по дисциплине

ОСНОВЫ ТЕОРИИ ДИСКРЕТНЫХ СИСТЕМ УПРАВЛЕНИЯ

Направление подготовки: 220700 Автоматизация технологических процессов и производств

Профиль подготовки: Автоматизация технологических процессов и производств

Форма обучения: очная, заочная

Тула 2012 г.

Рассмотрено на заседании кафедры Автоматизированных станочных систем

протокол № ____ от «__» _____________ 2012 г.

Зав. кафедрой ____________________ А.Н.Иноземцев

Содержание

Содержание.. 3

1. Предмет и метод теории дискретных систем управления.. 5

1.1 Дискретные переменные 5

2 ОСНОВЫ ТЕОРИИ МНОЖЕСТВ.. 10

2.1 Понятие множества 10

2.2 Задание множеств. 13

3 ОСНОВЫ ТЕОРИИ ГРАФОВ.. 17

3.1 Происхождение понятия «граф». Определение графа 17

3.2 Инцидентность вершин графа. Изоморфизм. Маршруты на графах 22

4 ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ.. 30

4.1 Понятие логической функции 31

4.2 Булева алгебра 40

4.3 Тождественные преобразования 44

4.4 Упрощение формул 47

5. ОСНОВЫ ТЕОРИИ КОНЕЧНЫХ АВТОМАТОВ.. 58

5.1 Понятие конечного автомата 58

5.2 Анализ конечных автоматов 63

5.3 Пример реализации конечного автомата и комбинационной схемы с использованием ПЗУ 69

6 ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ И КОДИРОВАНИЯ.. 73

6.1 Дискретные и непрерывные сообщения. 73

6.2 Избыточность сообщений. 75

7 Основы теории алгоритмов.. 78

8. Основы теории формальных грамматик.. 84

8.1 Формальное определение грамматики. Форма Бэкуса - Наура 84

8.2 Принцип рекурсии в правилах грамматики 87

8.3 Запись правил грамматик с использованием метасимволов 88

8.4 Запись правил грамматик в графическом виде 90

8.5 Синтаксис вещественного числа 93

8.6 Грамматика математических выражений 94

8.7 Четыре типа грамматик по Хомскому 95

8.7 Классификация языков 97

БИБЛИОГРАФИЧЕСКИЙ СПИСОК.. 97

Предмет и метод теории дискретных систем управления