Дискретная математика

Конспект лекций по дисциплине „Дискретная математика” для студентов направления подготовки

6.050102 “Компьютерная инженерия”

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.. 6

1 ТЕОРИЯ МНОЖЕСТВ.. 8

1.1 МНОЖЕСТВА И ПОДМНОЖЕСТВА.. 8

1.1.1 Элементы множества. 8

1.2 АКСИОМЫ ТЕОРИИ МНОЖЕСТВ.. 8

1.3 СПОСОБЫ ЗАДАНИЯ МНОЖЕСТВ.. 9

1.4 ОПЕРАЦИИ НАД МНОЖЕСТВАМИ.. 10

1.5 ЭЛЕМЕНТЫ АЛГЕБРЫ МНОЖЕСТВ.. 12

1.5.1 Определение алгебры множеств. 12

1.5.2 Основные законы алгебры множеств. 13

1.5.3 Принцип двойственности. 13

1.6 СПОСОБЫ ДОКАЗАТЕЛЬСТВА ТОЖДЕСТВ АЛГЕБРЫ МНОЖЕСТВ 14

1.6.1 По принадлежности элементов множеств. 14

1.6.2 Использование тождественных преобразований. 14

1.6.3 Четыре основных соотношения. 14

1.6.4 Решение системы уравнений в алгебре множеств. 14

2 МАТЕМАТИЧЕСКАЯ ЛОГИКА.. 16

2.1 ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ (БУЛЕВЫЕ ФУНКЦИИ) 16

2.1.1 Способы задания булевых функций. 16

2.1.2 Логические функции одной переменной. 18

2.1.3 Логические функции двух переменных. 18

2.2 СВОЙСТВА ЛОГИЧЕСКИХ ФУНКЦИЙ.. 19

2.2.1 Функции сохраняющие константу нуля. 19

2.2.2 Функции сохраняющие константу единицы.. 19

2.2.3 Самодвойственные булевые функции. 19

2.2.4 Линейные логические функции. 19

2.2.5 Монотонные логические функции. 20

2.2.6 Функционально полные системы булевых функций. 20

2.3 АЛГЕБРА БУЛЯ.. 21

2.3.1 Определение алгебры. Теорема Стоуна. 21

2.3.2 Законы алгебры логики. 22

2.3.3 Разложения функций по переменным.. 23

2.3.4 Приведение логических функций. 25

2.3.5 Импликанты и имплициенты булевых функций. 25

2.3.6 Методы минимизации логических функций. 27

2.4 АЛГЕБРА ЖЕГАЛКИНА.. 35

2.4.1 Преобразование функций в алгебре Жегалкина. 35

2.4.2 Переход от булевой алгебры к алгебре Жегалкина. 35

3 ФОРМАЛЬНЫЕ ТЕОРИИ.. 37

3.1 ОСНОВНЫЕ ПРИНЦИПЫ ПОСТРОЕНИЯ ФОРМАЛЬНЫХ ТЕОРИЙ ИСЧИСЛЕНИЯ.. 37

3.2 ОПРЕДЕЛЕНИЕ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ.. 38

3.2.1 Метатеоремы исчисления высказываний. 40

3.2.2 Схемы исчисления высказываний. 40

3.3 ИСЧИСЛЕНИЕ ПРЕДИКАТОВ.. 42

3.3.1 Определение формальной теории PL. 42

3.3.2 Принцип резолюции в исчислении предикатов. 46

3.3.3 Схемы доказательств в исчислении предикатов. 47

4 ТЕОРИЯ ГРАФОВ.. 49

4.1 ИСТОРИЯ ТЕОРИИ ГРАФОВ.. 49

4.2 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ.. 49

4.3 СПОСОБЫ ПРЕДСТАВЛЕНИЯ ГРАФОВ.. 51

4.3.1 Матрицей смежности. 52

4.3.2 Матрицей инцидентности. 52

4.4 ПУТИ В ГРАФАХ.. 53

4.4.1 Задача о кратчайшем пути. 53

4.4.2 Алгоритм Дейкстры нахождения кратчайшего пути в графе. 54

4.5 ТРАНСПОРТНЫЕ СЕТИ.. 55

4.5.1 Потоки в транспортных сетях. 55

4.5.2 Задача нахождения наибольшего потока в транспортной сети. 57

4.5.3 Алгоритм Форда и Фалкерсона нахождения максимального потока транспортной сети. 58

4.5.4 Транспортная задача. 60

4.6 ОБХОДЫ В ГРАФАХ.. 67

4.6.1 Эйлеровы графы.. 67

4.6.2 Алгоритм Флёри нахождения эйлерова цикла. 69

4.6.3 Гамильтоновы циклы.. 70

4.6.4 Метод ветвей и границ. 71

4.6.5 Метод ветвей и границ в задаче о коммивояжёре. 72

4.7 ДЕРЕВЬЯ.. 79

4.7.1 Построение экономического дерева. 80

4.7.2 Алгоритм Краскала. 81

5 ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ.. 83

5.1 Модулярная арифметика. 83

5.1.1 Алгоритм Евклида для нахождения наибольшего общего делителя. 85

5.1.2 Вычисление обратных величин. 86

5.1.3 Основные способы нахождения обратных величин. 88

5.1.4 Китайская теорема об остатках. 91

5.2 Кодирование. 92

5.2.1 Оптимальное кодирование. 92

5.3 Обнаружение и исправление ошибок. 97

5.3.1 Общие понятия. 97

5.3.2 Линейные групповые коды.. 99

5.3.2 Код Хэмминга. 105

5.3.3 Циклические коды.. 108

5.3.4 Построение и декодирование конкретных циклических кодов. 113

5.4 Сжатие информации. 120

5.4.1 Исключение повторения строк в последующих строках. 120

5.4.2 Алгоритм LZW... 122

6 ТЕОРИЯ АЛГОРИТМОВ.. 125

6.1. Основные понятия. 125

6.1.1 Основные требования к алгоритмам.. 125

6.1.2 Блок–схемы алгоритмов. 129

6.1.3 Представление данных. 130

6.1.4 Виды алгоритмов. 132

6.1.5 Правильность программ.. 133

6.1.6 Эффективность алгоритмов. 134

6.1.7 Сходимость, сложность, надежность. 136

6.2 Универсальные алгоритмы.. 139

6.2.1 Основные понятия. 139

6.2.2 Машины Тьюринга. 140

6.2.3 Рекурсивные функции. 143

6.2.4 ПР-операторы.. 144

6.2.5 Тезис Черча-Тьюринга. 146

6.2.6 Проблема самоприменимости. 147

6.3 Языки и грамматики. 149

6.3.1 Общие понятия. 149

6.3.2 Формальные грамматики. 151

6.3.3 Иерархия языков. 152

6.4 Параллельные вычисления. 152

РЕКОМЕНДОВАННАЯ ЛИТЕРАТУРА.. 155

Дата добавления: 2014-01-06