Конспект лекций для студентов специальности асу пермь, 2001г



страница1/42
Дата29.04.2013
Размер1.72 Mb.
ТипКонспект лекций
  1   2   3   4   5   6   7   8   9   ...   42



Пермский Государственный Технический Университет
А. Е. СОЛОВЬЕВ

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

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

Пермь, 2001г.

Оглавление


Введение 8

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

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

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

1. Объединение множеств A и B 10

5. Дополнение множества A 10

Пример. 10

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

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

Законы: 12

1. Коммутативный: 12

2. Ассоциативный: 12

3. Дистрибутивный: 12

4. Поглощения: 12

5. Идемпотентности: 12

6. Исключенного третьего: 12

6’. Противоречия: 12

7. A   = A A   =  12

8. A  U = U A  U = A 12

9. Де Моргана: 12

10. 12

11. Двойного отрицания: 12

12. 12

13. 12

Пример доказательства варианта дистрибутивного закона: 12

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

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

Свойства соответствий: 15

Пример: Соответствие "студенты сдавали экзамен" (Трифонов не пришел). 15

Пример: Соответствие "покупателей и купленных товаров". 15

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

Свойства отношений: 16

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

Свойства отношения эквивалентности: 16

P(M) – множество-степень множества М есть множество всех подмножеств множества М. 16

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

R(M) – разбиением множества М называется такое покрытие множества М, в котором элементы не пересекаются. 16

Свойства: 17

Теорема: Отношение эквивалентности разбивает множество, на котором оно определено на классы эквивалентности. 17

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

1.7.3. Морфизмы 17

Виды морфизмов: 17

1.8. Решетки 17

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

По умолчанию на диаграмме Хассе: 18

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

Наибольшим элементом аA называется элемент а, если ах, где хА. 18

Наименьшим элементом аA называется элемент а, если ах, где хА. 18

Теорема: Если в множестве A существует наибольший элемент, то он единственный. 18

Максимальным элементом множества A называется элемент аA, когда неверно, что ах, где хA. 18

Минимальным элементом множества A называется элемент аA, когда неверно, что ах, где хA. 18

Мажорантой множества B (такого, что BA) является элемент аA, такой что элемент a является наибольшим элементом для множества B.
18

Минорантой множества B (такого, что BA) является элемент аA, такой что элемент a является наименьшим элементом для множества В. 18

Множество мажорант множества B образует верхнюю грань множества B. 19

Множество минорант множества B образует нижнюю грань множества B. 19

Наименьший элемент верхней грани называется точной верхней гранью или Supremum (Sup). 19

Наибольший элемент нижней грани называется точной нижней гранью или Infimum (Inf). 19

Частично-упорядоченное множество, в котором любая пара элементов имеет Sup и Inf называется решеткой. 19

Примеры решеток: 19

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

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

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

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

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

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

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

1.9.4. Мощность множества R. Теорема Кантора 22

Теорема Кантора: 22

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

1.9.6. Противопоставление системного и теоретико-множественного подходов 23

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

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

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

Таблица истиности операций сведена в таблицу: 24

Соглашение о старшинстве некоторых операций (по силе связывания): 25

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

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

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

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

Преобразование КНФ в СКНФ. 27

Преобразование ДНФ в СДНФ. 28

Преобразование СДНФ в СКНФ. 28

Примеры: 28

Переход от СКНФ к СДНФ. 28

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

Пример 1: 29

Пример 2: 29

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

Пусть дана СДНФ импликации: , найти МДНФ. 30

Для СДНФ XYZ  XYZ  XYZ  XYZ  XYZ 30

Для СДНФ XYZ  XYZ  XYZ  XYZ  XYZ 30

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

Примеры линейных функций: 31

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

Операции: 32

Содержательные примеры предикатов : 32

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

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

Пример: 33

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

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

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

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

1. Язык : 36

2. Аксиомы: 36

3. Правила вывода: 36

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

Пример 1: Можно сказать, что это прообраз или предельно упрощенный вариант «системы искусственного интеллекта». 38

Пример 2: 38

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

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

Категорические высказывания. 41

Общеутвердительные Asp (Axy): 41

Общеотрицательные Esp (Exy): 41

Частично-утвердительные Isp (Ixy) : 41

: Частное отрицание Osp (Oxy) 41

Модус - структура умозаключения, которая определяет его истинность. 42

Модусы непосредственного заключения 42

Категорические силлогизмы. 42

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

Модальные логики. 43

Немонотонные логики. Кратко суть таких логик формулируется следующим образом: добавление в систему новых аксиом может привести к изменению уже существовавших…Они хороши тем, что часто следуют принципу: Если не нравится полученный в процессе вывода результат - можно изменить исходные посылки. 44

Два основных типа вопросов: 44

А ответы могут быть: 44

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

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

Будем иметь в виду две ключевые абстракции: 45

Законы функционирования автоматов 45

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

Пример 1 (автомат Мили): 46

Пример 2 (автомат Мура). 47

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

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

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

Теорема: (Глушкова) 50

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

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

Путем в орграфе называется последовательность дуг, такая, что каждое следующее ребро исходит из вершины, в которую заходит предыдущее. 52

Длина пути измеряется числом пройденных дуг. 52

Контур длиной в единицу - петля. 52

Путь называется простым, если каждое из ребер встречается на этом пути один раз. 52

Путь называется элементарным, если любая вершина на этом пути один раз. 52

Дуга, исходящая (или заходящая) в вершину называется инцидентной данной вершине (и наоборот вершина инцидентна дуге). 52

Вершины инцидентные одной дуге называются смежными. 52

Теорема: В любом графе число вершин с нечетной степенью четно. 53

Теорема: В графе без петель, где вершин больше двух всегда найдется пара вершин с одинаковой степенью. 53

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

Теорема: Для того чтобы связный граф был эйлеровым необходимо и достаточно, чтобы степени всех вершин его были четными. 53

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

4.4. Деревья 56

Теорема: В графе типа дерева с n вершинами n-1 ребер. 56

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

Теорема Кэли для раскрашенных деревьев. 57

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

Теорема (Эйлера для планарных графов): 58

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

Теорема: Трех красок мало. 59

Теорема: Для раскраски любого планарного графа достаточно 5-ти красок 59

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

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

Алгоритм приведения к ЯПФ: 61

Ширина яруса определяется числом вершин в ярусе. 62

Ширина графа в ЯПФ определяется шириной самого большого яруса. 62

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

Алгоритм Магу. 63

4.11. Множество внешней устойчивости. Ядро графа. 63

Алгоритм Магу. 63

Множества, одновременно внутренне и внешне устойчивые называются ядром графа. 64

4.12. Клика 64

Клика - максимально большой полный подграф данного графа. 64

Построение клики. 64

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

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

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

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

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

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

Теорема ( Лагранжа ) : Порядок конечной группы кратен порядку любой его подгруппы. 70

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

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

Свойства: 71

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

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

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

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

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

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

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

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

Язык состоит из: 78

-терм: 78

Формула - любое выражение вида M=N, где M и N -термы. 78

Аксиомы: 78

Правила вывода: 78

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

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

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

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

Тип 0 - формальная грамматика, на правила которой не накладывается никаких ограничений. Для исследования они интереса не представляют – поскольку режим «делай, что хочешь» для математики и для практики редко представляют интерес. 81

Тип 1 . К этому типу относятся грамматики, правила которых имеют вид: 82

Тип 2 . К этому типу относятся грамматики, правила которых имеют вид: 82

Тип 3 . К этому типу относятся грамматики, правила которых имеют один из двух видов: 82

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

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

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

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

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

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

7.9. LEX 86

Пример 1: 87

Пример 2: 88

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

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

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

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

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

(left - leftmost) 92

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

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

(left - rightmost) 94

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

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

7.18. YACC 100

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

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

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

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

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

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

Язык Пролог 109

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

Заключение 113

Литература 114



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

Похожие:

Конспект лекций для студентов специальности асу пермь, 2001г iconКонспект лекций для студентов специальности асу пермь, 2001г

Конспект лекций для студентов специальности асу пермь, 2001г iconКонспект лекций для студентов специальности асу пермь, 2001г
П(M) – покрытием множества м будем называть любое подмножество множества Р(М), такое, что объединение входящих в него элементов совпадает...
Конспект лекций для студентов специальности асу пермь, 2001г iconКонспект лекций для студентов специальностей асу, эвт, кзи пермь, 2007 г
Математическая логика это современный вид формальной логики. Логика – это наука правильно рассуждать, имея какие-то утверждения,...
Конспект лекций для студентов специальности асу пермь, 2001г iconКонспект лекций по специальности 3050305 Регионоведение США и Канады ббк 63. 3 (7Сое) Конспект лекций по дисциплине «История США и Канады»
Конспект лекций по дисциплине «История США и Канады» составлен в соответствии с требованиями государственного стандарта России. Предназначен...
Конспект лекций для студентов специальности асу пермь, 2001г iconВодозаборные сооружения
Конспект лекций для студентов 3-5 курсов дневной и заочной форм обучения, экстернов и иностранных студентов специальности 092600...
Конспект лекций для студентов специальности асу пермь, 2001г iconКонспект лекций по курсу нгииг л. В. Белозерцева, А. Г. Коробова, М. Н. Потапова
Конспект лекций предназначен для студентов механических специальностей заочной формы обучения
Конспект лекций для студентов специальности асу пермь, 2001г icon«международные валютно-кредитные отношения» конспект лекций бурлачков в. К
Конспект лекций предназначен для студентов экономических специальностей, аспирантов, преподавателей, практических работников внешнеэкономической...
Конспект лекций для студентов специальности асу пермь, 2001г iconКонспект лекций Челябинск Издательский центр юургу 2010
Конспект лекций предназначен для студентов очной формы обучения специальностей «Управление и информатика в технических системах»,...
Конспект лекций для студентов специальности асу пермь, 2001г iconКонспект лекций по курсу «Организация ЭВМ и систем» для студентов специальности 220100 Вычислительная техника, системы, комплексы и сети

Конспект лекций для студентов специальности асу пермь, 2001г iconКонспект лекций по дисциплине «Конфекционирование материалов» предназначен для студентов среднего специального образования по специальностям 2808 (260903) «Моделирование и конструирование швейных изделий»
Конфекционирование материалов: Конспект лекций – Владивосток: Издательство вгуэс, 2004
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org