Оглавление
Пермь 2001г.
Конспект лекций
СПЕЦИАЛЬНАЯ МАТЕМАТИКА
Пермский Государственный Технический Университет
А. Е. СОЛОВЬЕВ
для студентов специальности АСУ
Введение......................................................................................................................... 5
1. Теория множеств................................................................................................................ 6
1.1 Понятие множества...................................................................................................... 6
1.2. Операции над множествами...................................................................................... 7
1.3. Диаграммы Эйлера - Венна....................................................................................... 7
1.4. Алгебра множеств....................................................................................................... 8
1.5. Кортеж. График.......................................................................................................... 9
1.6. Соответствия............................................................................................................. 12
1.7. Отношения................................................................................................................. 13
1.7.1 Отношение эквивалентности............................................................................ 13
1.7.2. Отношения порядка........................................................................................... 14
1.7.3. Морфизмы........................................................................................................... 14
1.8. Решетки...................................................................................................................... 15
1.8.1. Диаграммы Хассе............................................................................................... 15
1.8.2. Понятие решетки................................................................................................ 15
1.8.3. Алгебраическое представление решеток. Булевы решетки.......................... 16
1.8.4. Подрешетки........................................................................................................ 17
1.8.5. Морфизмы решеток............................................................................................ 18
1.9. Мощность множества............................................................................................... 18
1.9.1. Понятие мощности............................................................................................. 18
1.9.2. Аксиоматика Пеано.......................................................................................... 18
1.9.3. Сравнение мощностей....................................................................................... 19
1.9.4. Мощность множества R.. Теорема Кантора.................................................... 19
1.9.5. Арифметика бесконечного................................................................................ 20
1.9.6. Противопоставление системного и................................................................. 20
теоретико-множественного подходов................................................................... 20
2. Математическая логика................................................................................................... 21
2.1. Логика высказываний.............................................................................................. 21
2.1.1. Операции над высказываниями....................................................................... 21
2.1.2. Построение и анализ сложных высказываний............................................... 22
2.1.3. Алгебра высказываний...................................................................................... 23
2.1.4. Формы представления высказываний............................................................. 24
2.1.5. Преобразование высказываний........................................................................ 24
2.1.6. Минимизация высказываний методом Квайна.............................................. 26
2.1.7. Минимизация с помощью карт Вейча............................................................. 27
2.1.8. Функциональная полнота................................................................................. 28
2.2. Логика предикатов.................................................................................................... 29
2.2.1. Основные равносильности для предикатов.................................................... 30
2.2.2. Получение дизъюнктов..................................................................................... 31
2.3. Аксиоматические теории........................................................................................ 31
2.3.1. Аксиоматическая теория исчисления высказываний.................................... 31
2.3.2. Непротиворечивость и полнота аксиоматической теории исчисления высказываний 32
2.4. Аксиоматические теории первого порядка............................................................ 33
2.5. Метод резолюций...................................................................................................... 34
2.6. Система Генцена....................................................................................................... 36
2.7. Система Аристотеля................................................................................................. 38
2.8. Примеры неклассических логик............................................................................. 40
3. Теория Автоматов............................................................................................................ 42
3.1. Понятие автомата...................................................................................................... 42
3.2. Примеры автоматов.................................................................................................. 43
3.3. Минимизация автоматов.......................................................................................... 44
3.4. Особенности минимизации автомата Мура........................................................... 46
3.5. Переход от автомата Мура к автомату Мили и наоборот..................................... 46
4.Теория графов.................................................................................................................... 47
4.1. Понятие графа........................................................................................................... 47
4.2. Теорема Эйлера......................................................................................................... 50
4.3. Полные графы и деревья.......................................................................................... 52
4.4. Деревья....................................................................................................................... 53
4.5. Алгоритм Краскала................................................................................................... 54
4.6. Планарные графы...................................................................................................... 55
4.7. Задача о 4 красках..................................................................................................... 56
4.8. Определение путей в графе..................................................................................... 57
4.9. Приведение графа к ярусно-параллельной форме................................................. 58
4.10. Внутренняя устойчивость графа........................................................................... 59
4.11. Множество внешней устойчивости. Ядро графа................................................. 60
4.12. Клика........................................................................................................................ 61
5. Теория групп..................................................................................................................... 62
5.1. Понятие группы........................................................................................................ 62
5.2. Морфизмы групп....................................................................................................... 62
5.3. Инвариантные (нормальные) подгруппы.............................................................. 63
5.4. Группа Диэдра (D3 ).................................................................................................. 65
5.5. Смежные классы....................................................................................................... 66
5.6. Фактор-группы.......................................................................................................... 66
5.7. Группа Клейна четвертой степени.......................................................................... 67
6. Теория алгоритмов........................................................................................................... 67
6.1. Понятие алгоритма................................................................................................... 67
6.2. Конкретизация понятия алгоритма......................................................................... 68
6.3. Сложность вычислений............................................................................................ 68
6.4. Машины Тьюринга................................................................................................... 69
6.5. Нормальные алгорифмы Маркова........................................................................... 70
6.6. Рекурсивные функции.............................................................................................. 71
6.7. l-исчисление............................................................................................................. 73
7. Формальные грамматики................................................................................................ 75
7.1. Понятие формальной грамматики........................................................................... 75
7.2. Деревья вывода.......................................................................................................... 76
7.3. Классификация языков по Хомскому..................................................................... 77
7.4. Распознающие автоматы.......................................................................................... 78
7.5. Понятие транслятора................................................................................................ 79
7.6. Основные функции компилятора........................................................................... 80
Лексический анализ..................................................................................................... 80
7.7. Переход от недетерминированного распознающего автомата к......................... 80
детерминированному................................................................................................... 80
7.8. Переход от праволинейной грамматики к автоматной........................................ 81
7.9. LEX............................................................................................................................. 81
7.10. Детерминированные автоматы с магазинной памятью (МП-автоматы).......... 83
7.11. Транслирующие грамматики................................................................................. 85
7.12. S и q - грамматики................................................................................................... 85
7.13. LL(1) - грамматики.................................................................................................. 86
(left - leftmost)............................................................................................................... 86
7.14. Метод рекурсивного спуска................................................................................... 87
7.15. LR - грамматики...................................................................................................... 88
(left - rightmost)............................................................................................................. 88
7.16. Функции предшествования................................................................................... 91
7.17. Атрибутные грамматики........................................................................................ 92
7.18. YACC....................................................................................................................... 93
7.19. Область действия и передача параметров............................................................ 94
7.20. Генерация выходного текста. Польская инверсная запись................................ 95
7.21. Оптимизация программ.......................................................................................... 98
8. Функциональное программирование............................................................................ 99
9. Логическое программирование.................................................................................... 102
Язык Пролог................................................................................................................... 102
10. Объектно-ориентированное программирование...................................................... 103
Заключение......................................................................................................................... 107
Литература.......................................................................................................................... 108
Специальная математика – это некоторые разделы современной математики. Речь идет о математическом аппарате, который помогает расширить возможности математического описания или, выражаясь изящнее – математического моделирования, сложных систем. Далеко не все задачи, которые возникают в сложных системах, включающих человека, можно свести к задачам механики или математического анализа, традиционно называемого в технических вузах «высшей математикой».
Самостоятельное значение имеют математические проблемы теоретического и практического программирования.
Последние сто лет интенсивно развивались разделы математики, многие из которых часто объединяют общим названием дискретная математика, хотя деление на дискретную и непрерывную математику более чем условно. (Возьмите множество всех подмножеств эталонного дискретного множества – множества натуральных чисел, и вы получите мощность базового для традиционного математического анализа множества - множества действительных чисел).
Так что чисто формально нет непреодолимой пропасти и антагонизма между дискретной и непрерывной математикой. Всякий инструмент хорош для решения задач, на которые он ориентирован. Вопрос удобства, эффективности использования и адекватности того или иного математического аппарата вообще до определенной степени вопрос субъективный.
А что касается классификации, то относить ли, например, теорию графов к дискретной математике или к топологии – тоже вопрос. Отнесение к дискретной математике теории групп еще более условно.
Задача данного курса состоит в выработке навыков формализации физических сущностей с помощью различных «диалектов» современного математического языка. И наоборот, интерпретации полученных математических результатов.
Содержательный аспект обычно предшествует формализации и имеет для нас значение при осмыслении результатов математических манипуляций.
Так что акцент в большей степени сделан на понятийной, а не вычислительной стороне ряда разделов математики.
