Соловьев Е.А. Учебник по дискретной математике - файл n1.doc

приобрести
Соловьев Е.А. Учебник по дискретной математике
скачать (169 kb.)
Доступные файлы (1):
n1.doc939kb.28.06.2001 21:55скачать

n1.doc

  1   2   3   4   5   6   7   8   9   ...   29



Пермский Государственный Технический Университет

А. Е. СОЛОВЬЕВ
СПЕЦИАЛЬНАЯ МАТЕМАТИКА


конспект лекций
для студентов специальности АСУ

Пермь, 2001г.


Оглавление


Введение 5

1. Теория множеств 6

1.1 Понятие множества 6

1.2. Операции над множествами 7

1.3. Диаграммы Эйлера - Венна 7

U 8

1.4. Алгебра множеств 8

1.5. Кортеж. График 10

1.6. Соответствия 12

1.7. Отношения 13

1.7.1 Отношение эквивалентности 13

1.7.2. Отношения порядка 14

1.7.3. Морфизмы 15

1.8. Решетки 15

1.8.1. Диаграммы Хассе 15

1.8.2. Понятие решетки 16

1.8.3. Алгебраическое представление решеток. 17

Булевы решетки 17

1.8.4. Подрешетки 18

1.8.5. Морфизмы решеток 18

1.9. Мощность множества 19

1.9.1. Понятие мощности 19

1.9.2. Аксиоматика Пеано 19

1.9.3. Сравнение мощностей 19

1.9.4. Мощность множества R. 20

Теорема Кантора 20

1.9.5. Арифметика бесконечного 21

1.9.6. Противопоставление системного и 21

теоретико-множественного подходов 21

2. Математическая логика 21

2.1. Логика высказываний 21

2.1.1. Операции над высказываниями 22

2.1.2. Построение и анализ сложных высказываний 23

2.1.3. Алгебра высказываний 24

2.1.4. Формы представления высказываний 25

2.1.5. Преобразование высказываний 25

2.1.6. Минимизация высказываний методом Квайна 27

2.1.7. Минимизация с помощью карт Вейча 28

2.1.8. Функциональная полнота 29

2.2. Логика предикатов 30

2.2.1. Основные равносильности для предикатов 31

2.2.2. Получение дизъюнктов 32

2.3. Аксиоматические теории 32

2.3.1. Аксиоматическая теория исчисления высказываний 32

2.3.2. Непротиворечивость и полнота аксиоматической теории исчисления высказываний 34

2.4. Аксиоматические теории первого порядка 35

2.5. Метод резолюций 36

2.6. Система Генцена 38

2.7. Система Аристотеля 39

2.8. Примеры неклассических логик 41

3. Теория Автоматов 43

3.1. Понятие автомата 43

3.2. Примеры автоматов 44

3.3. Минимизация автоматов 46

3.4. Особенности минимизации автомата Мура 47

3.5. Переход от автомата Мура к автомату Мили и наоборот 48

4.Теория графов 49

4.1. Понятие графа 49

4.2. Теорема Эйлера 52

4.3. Полные графы и деревья 54

4.4. Деревья 55

4.5. Алгоритм Краскала 56

4.6. Планарные графы 57

4.7. Задача о 4 красках 58

4.8. Определение путей в графе 59

4.9. Приведение графа к ярусно-параллельной форме 60

4.10. Внутренняя устойчивость графа 61

4.11. Множество внешней устойчивости. 62

Ядро графа 62

4.12. Клика 63

5. Теория групп 64

5.1. Понятие группы 64

5.2. Морфизмы групп 64

5.3. Инвариантные (нормальные) подгруппы 66

5.4. Группа Диэдра (D3) 67

5.5. Смежные классы 68

5.6. Фактор-группы 68

5.7. Группа Клейна четвертой степени 69

6. Теория алгоритмов 69

6.1. Понятие алгоритма 69

6.2. Конкретизация понятия алгоритма 70

6.3. Сложность вычислений 71

6.4. Машины Тьюринга 71

6.5. Нормальные алгорифмы Маркова 72

6.6. Рекурсивные функции 73

6.7. -исчисление 75

7. Формальные грамматики 77

7.1. Понятие формальной грамматики 77

7.2. Деревья вывода 78

7.3. Классификация языков по Хомскому 79

7.4. Распознающие автоматы 80

7.5. Понятие транслятора 81

7.6. Основные функции компилятора. 82

Лексический анализ 82

7.7. Переход от недетерминированного распознающего автомата к 83

детерминированному 83

7.8. Переход от праволинейной грамматики к автоматной 83

7.9. LEX 84

7.10. Детерминированные автоматы с магазинной памятью 86

(МП-автоматы) 86

7.11. Транслирующие грамматики 88

7.12. s и q - грамматики 88

7.13. LL(1) - грамматики. 89

(left - leftmost) 89

7.14. Метод рекурсивного спуска 90

7.15. LR - грамматики 92

(left - rightmost) 92

7.16. Функции предшествования 94

7.17. Атрибутные грамматики 96

7.18. YACC 97

7.19. Область действия и передача параметров 98

7.20. Генерация выходного текста. 99

Польская инверсная запись 99

7.21. Оптимизация программ 101

8. Функциональное программирование 102

9. Логическое программирование. 106

Язык Пролог 106

10. Объектно-ориентированное программирование 107

Заключение 110

Литература 111


Введение



Специальная математика – это некоторые разделы современной математики. Речь идет о математическом аппарате, который помогает расширить возможности математического описания или, выражаясь изящнее – математического моделирования, сложных систем. Далеко не все задачи, которые возникают в сложных системах, включающих человека, можно свести к задачам механики или математического анализа, традиционно называемого в технических вузах «высшей математикой».

Самостоятельное значение имеют математические проблемы теоретического и практического программирования.

Последние сто лет интенсивно развивались разделы математики, многие из которых часто объединяют общим названием дискретная математика, хотя деление на дискретную и непрерывную математику более чем условно. (Возьмите множество всех подмножеств эталонного дискретного множества – множества натуральных чисел, и вы получите мощность базового для традиционного математического анализа множества - множества действительных чисел).

Так что чисто формально нет непреодолимой пропасти и антагонизма между дискретной и непрерывной математикой. Всякий инструмент хорош для решения задач, на которые он ориентирован. Вопрос удобства, эффективности использования и адекватности того или иного математического аппарата вообще до определенной степени вопрос субъективный.

А что касается классификации, то относить ли, например, теорию графов к дискретной математике или к топологии – тоже вопрос. Отнесение к дискретной математике теории групп еще более условно.

Задача данного курса состоит в выработке навыков формализации физических сущностей с помощью различных «диалектов» современного математического языка. И наоборот, интерпретации полученных математических результатов.

Содержательный аспект обычно предшествует формализации и имеет для нас значение при осмыслении результатов математических манипуляций.

Так что акцент в большей степени сделан на понятийной, а не вычислительной стороне ряда разделов математики.

1. Теория множеств

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



Множество - фундаментальное неопределяемое понятие. Множество понимается как объединение в одно целое объектов, хорошо различимых нашей интуицией или мыслью.
Теорию множеств можно подразделить на аксиоматическую и интуитивную (наивную).

Аксиоматическая теория исходит из того, что множество определяется совокупностью аксиом, записанных обычно на языке логики (предикатов). Интуитивная теория множеств апеллирует к интуиции, к базовому понятию принадлежности элемента множеству, то есть к интуитивной понятности отношения принадлежности  ( а A - элемент а принадлежит множеству A).

Для интуитивного понятия множества существенны два момента, следующие из "определения":

1. Различимость элементов.

2. Возможность мыслить их как нечто единое.

Студенты образуют группу. Деревья составляют лес.

Целые числа составляют множество целых чисел.

Жители Марса - множество марсиан.
Множество, не содержащее элементов, называется пустым множеством и обозначается  или . Обычно именно фигурные скобки используются для выделения множества (отсутствие элементов в скобках и говорит о том, что это пустое множество).

Множество, заведомо содержащее все рассматриваемые элементы, называется универсальным или универсумом - U.

Было бы опрометчиво говорить просто, что U содержит все элементы. К сожалению, имеют место так называемые парадоксы теории множеств. Самый знаменитый – парадокс Рассела, который показывает невозможность построить множество всех подмножеств, не содержащих себя в качестве элемента. Более прост в понимании парадокс брадобрея, которому приказано брить в тридевятом государстве всех тех и только тех, кто не бреется сам. Перед брадобреем неразрешимый вопрос:

Включать ли самого себя в множество тех, кого он обязан брить?!
Способы задания множеств:

A = {a, b, c, d} - задание множества явным перечислением элементов.

Например, гвардия = {Иванов, Петров, Сидоров}

B = {x | С(x)} - задание множества (характеристическим) свойством С(x).

Например, студенчество = {x | x - студент} - множество таких х, что х - студент.
Отношение включения . Множество А включено в множество В В) или А есть подмножество множества В, если из х  А следует х  В.

Например, студенческая группа студенты данной специальности

Отношение строгого включения : Если A  B и A  B , то можно написать

A  B.
Например: множество отличников

Кстати, на что намекает это отношение?
Свойства отношения включения:

1. Рефлексивность: A  A

2. Принцип объемности: A  B и B  A следует B = A (на основе этого принципа и доказывается равенство двух множеств).

3. Транзитивность: A  B и B  C следует A  C
Полезные соотношения:
{ }=  ; 1  { 1 } ; {{ 1 }}  { 1 } ; { а, в }  { в, а }

  1   2   3   4   5   6   7   8   9   ...   29


Пермский Государственный Технический Университет
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации