лекции по дм. лекции. Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4
 Скачать 1.51 Mb.
|
|
Содержание: Тема 1. Основные понятия теории множеств. Способы задания множеств. Диаграммы Венна. Операции над множествами. Свойства теоретико-множественных операций. Представление множеств в ЭВМ. 4 Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4 Операции над множествами. 5 Свойства теоретико-множественных операций. 6 Представление множеств в ЭВМ 6 Реализация операций над подмножествами заданного универсума в ЭВМ. 7 Тема 2. Упорядоченные пары. Прямое произведение множеств. Отношения. Многоместные отношения. Композиция отношений. Степень отношений. Ядро отношения. Свойства отношений. Представление отношений в ЭВМ. 8 Упорядоченные пары. Декартово (прямое) произведение множеств. Отношения. 8 Многоместные отношения. Композиция отношений. Степень и ядро отношений. 9 Свойства отношений. 9 Представление отношений в ЭВМ. 10 Тема 3. Специальные классы отношений. Отношение эквивалентности и разбиения. Отношения порядка. Минимальные элементы. Теорема о существовании минимального элемента. Алгоритм топологической сортировки. Операции над бинарными отношениями. 11 Специальные классы отношений. Отношение эквивалентности и разбиения. Отношения порядка. 11 Разновидности отношений порядка 13 Минимальные элементы. Теорема о существовании минимального элемента. 15 Алгоритм топологической сортировки 17 Операции над бинарными отношениями. 18 Тема 4. Замыкание отношений. Транзитивное замыкание, рефлексивное замыкание. Алгоритм Уоршалла вычисления транзитивного замыкания. 21 Замыкание отношений. 21 Транзитивное замыкание отношений 21 Рефлексивное замыкание отношений 22 Алгоритм Уоршалла. 22 Тема 5. Функции и отображения. Инъекция, сюръекция, биекция. Представление функций в ЭВМ. Операции. Свойства бинарных операций: ассоциативность, коммутативность, дистрибутивность слева и справа. Способы задания операций. Таблица Кэли. 25 Функции и отображения. Инъекция, сюръекция, биекция. 25 Представление функций в ЭВМ. 27 Операции 28 Свойства бинарных операций: 28 Способы задания операций. 29 Таблица Кэли 29 Тема 6. Алгебраическая система. Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр. 31 Алгебраическая система 31 Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр. 32 Тема 7. Нечеткие множества. Основные понятия и определения. Основные характеристики. Теоретико-множественные операции над нечеткими множествами. Графическое представление операций. 35 Нечеткие множества. Основные понятия и определения. 35 Основные характеристики нечетких множеств 36 Примеры нечетких множеств 36 Операции над нечеткими множествами 37 Графическое представление операций 38 Тема 8. Алгебраические операции над нечеткими множествами. 39 Тема 9. Основное определение графов. Смежность. Изоморфизм графов. Элементы графов. Подграфы. Валентность. Теорема Эйлера. 42 Основное определение. 42 Смежность. 42 Изоморфизм графов. 43 Элементы графов. Подграфы. Валентность. 44 Теорема Эйлера. 44 Тема 10. Маршруты в графах. Цепи. Циклы. Расстояние между вершинами. Связность. Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети. 45 Маршруты в графах. Цепи. Циклы. 45 Расстояние между вершинами. 45 Связность. 46 Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети. 46 Тема 11. Матрица смежности, матрица инцидентности. Операции над графами. Представление графов в ЭВМ. 48 Матрица смежности. Матрица инцедентности. 48 Операции над графами: 48 Объединение графов. 48 Пересечение графов 50 Композиция графов 52 Декартово произведение графов. 53 Операция произведения графов. 56 Представление графов в ЭВМ 58 Тема 12. Компоненты связности и объединение графов. Оценка числа ребер через число вершин и число компонентов связности. Вершинная и реберная связность. Мосты и блоки. 59 Объединение графов и компоненты связности. Оценка числа рёбер через число вершин и число компонентов связности. Вершинная и рёберная связность: мосты и блоки, меры связности. 59 Тема 13. Потоки в сетях. Определение потока. Разрезы. Пример сети с потоками. Теорема Форда и Фалкерсона. Алгоритм нахождения максимального потока. 61 Потоки в сетях. Примеры практических задач, определение потока, разрезы. 61 Теорема Форда - Фалкерсона. Алгоритм нахождения максимального потока. 64 Тема 14. Кратчайшие пути. Алгоритм Флойда. Алгоритм Дейкстры. 65 Кратчайшие пути 65 Рёбра отрицательного веса 66 Представление кратчайших путей в алгоритме 66 Алгоритм Флойда 67 Алгори́тм Де́йкстры 68 Пример 69 Сложность алгоритма 75 Тема 15. Свободные деревья. Основные свойства деревьев. Ориентированные, упорядоченные и бинарные деревья. Представление в ЭВМ свободных, ориентированных и упорядоченных деревьев. 77 Свободные деревья. Основные свойства деревьев. 77 Ориентированные, упорядоченные и бинарные деревья 78 Представление в ЭВМ свободных, ориентированных и упорядоченных деревьев. 79 Тема 16. Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья. Минимальный каркас. Схема алгоритма построения минимального каркаса. 81 Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья. 81 Минимальный каркас. Схема алгоритма построения минимальных каркасов. 83 Тема 17. Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака. Раскраска графов. Хроматическое число. Планарные графы. Укладка графов. Алгоритм раскрашивания. 85 21. Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака. 85 Раскраска графов. Хроматическое число. Планарность. Укладка графов. Алгоритмы раскрашивания. 86 Тема 18. Переключательные функции. Основные понятия и определения. Способы задания переключательных функций. Таблица истинности. Переключательные функции одного и двух аргументов. Специальные разложения ПФ. 88 Переключательные функции. Существенные и несущественные переменные. Булевы функции одной переменной. Булевы функции двух переменных. 88 f1(x) – нулевая функция. 89 Дизъюнктивная нормальная форма. 91 Конъюнктивная нормальная форма. 92 Тема 19. Неполностью определенные (частные) ПФ. Минимизация ПФ и неполностью определенных ПФ. 93 Понятие минимизации булевых функций. 93 Тема 20. Геометрическая интерпретация минимизации. Метод неопределенных коэффициентов. Метод карт Карно Метод Петрика для нахождения тупиковых ДНФ. 95 Геометрическая интерпретация минимизации функций алгебры логики. 95 Метод неопределённых коэффициентов. 95 Метод карт Карно 96 Метод Петрика 103 Тема 21. Пять классов переключательных функций: линейные переключательные функции; переключательные функции, сохраняющие нуль; переключательные функции, сохраняющие единицу; монотонные переключательные функции; самодвойственные переключательные функции. Теорема о функциональной полноте. Основная функционально полная система логических функций. Функционально полные системы логических функций. Примеры функционально полных базисов. 106 Теорема Поста 107 Тема 22. Законы алгебры логики в ОФПС и их следствия. Правило выполнения совместных логических действий, правило склеивания, правило поглощения, правило развертывания. 110 Тема 23. Задача анализа и синтеза логических схем 115 Тема 24. Элементы теории алгоритмов. Цели и задачи теории алгоритмов. Формализация понятия алгоритмов: определение Колмогорова, определение Маркова 117 |