- •Содержание:
- •Диаграммы Венна.
- •Операции над множествами.
- •Свойства теоретико-множественных операций.
- •Представление множеств в эвм
- •Реализация операций над подмножествами заданного универсума в эвм.
- •Многоместные отношения. Композиция отношений. Степень и ядро отношений.
- •Свойства отношений.
- •Представление отношений в эвм.
- •Минимальные элементы. Теорема о существовании минимального элемента.
- •Алгоритм топологической сортировки
- •Операции над бинарными отношениями.
- •Тема 4. Замыкание отношений. Транзитивное замыкание, рефлексивное замыкание. Алгоритм Уоршалла вычисления транзитивного замыкания. Замыкание отношений.
- •Транзитивное замыкание отношений
- •Рефлексивное замыкание отношений
- •Алгоритм Уоршалла.
- •Представление функций в эвм.
- •Операции
- •Свойства бинарных операций:
- •Способы задания операций.
- •Тема 6. Алгебраическая система. Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр. Алгебраическая система
- •Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр.
- •Основные характеристики нечетких множеств
- •Примеры нечетких множеств
- •Операции над нечеткими множествами
- •Графическое представление операций
- •Тема 8. Алгебраические операции над нечеткими множествами.
- •Тема 9. Основное определение графов. Смежность. Изоморфизм графов. Элементы графов. Подграфы. Валентность. Теорема Эйлера. Основное определение.
- •Смежность.
- •Изоморфизм графов.
- •Элементы графов. Подграфы. Валентность.
- •Теорема Эйлера.
- •Тема 10. Маршруты в графах. Цепи. Циклы. Расстояние между вершинами. Связность. Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети. Маршруты в графах. Цепи. Циклы.
- •Расстояние между вершинами.
- •Связность.
- •Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети.
- •Тема 11. Матрица смежности, матрица инцидентности. Операции над графами. Представление графов в эвм. Матрица смежности. Матрица инцедентности.
- •Операции над графами: Объединение графов.
- •Пересечение графов
- •Композиция графов
- •Декартово произведение графов.
- •Операция произведения графов.
- •Представление графов в эвм
- •V k1 k2
- •Теорема Форда - Фалкерсона. Алгоритм нахождения максимального потока.
- •Тема 14. Кратчайшие пути. Алгоритм Флойда. Алгоритм Дейкстры.
- •Кратчайшие пути
- •Рёбра отрицательного веса
- •Представление кратчайших путей в алгоритме
- •Алгоритм Флойда
- •Алгори́тм Де́йкстры
- •Сложность алгоритма
- •Ориентированные, упорядоченные и бинарные деревья
- •Представление в эвм свободных, ориентированных и упорядоченных деревьев.
- •Тема 16. Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья. Минимальный каркас. Схема алгоритма построения минимального каркаса.
- •Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья.
- •Минимальный каркас. Схема алгоритма построения минимальных каркасов.
- •Тема 17. Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака. Раскраска графов. Хроматическое число. Планарные графы. Укладка графов. Алгоритм раскрашивания.
- •21. Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака.
- •Раскраска графов. Хроматическое число. Планарность. Укладка графов. Алгоритмы раскрашивания.
- •F1(X) – нулевая функция.
- •Дизъюнктивная нормальная форма.
- •Конъюнктивная нормальная форма.
- •Тема 19. Неполностью определенные (частные) пф. Минимизация пф и неполностью определенных пф. Понятие минимизации булевых функций.
- •Метод неопределённых коэффициентов.
- •Метод карт Карно
- •Метод Петрика
- •Теорема Поста
- •Тема 22. Законы алгебры логики в офпс и их следствия. Правило выполнения совместных логических действий, правило склеивания, правило поглощения, правило развертывания.
- •Тема 23. Задача анализа и синтеза логических схем
- •Тема 24. Элементы теории алгоритмов. Цели и задачи теории алгоритмов. Формализация понятия алгоритмов: определение Колмогорова, определение Маркова
Представление функций в эвм.
Пусть , множествоАконечно и не очень велико, |A|=n.Наиболее общим представлением такой функции является массивarray[А]of B, где А- тип данных , значения которого представляют элементы множества В . Если среда программирования допускает массивы только с натуральными индексами , то элементы множества А нумеруются ( то есть) и функция представляется с помощью массиваarray[1…n] of B . Функция нескольких аргументов представляется многомерным массивом.
Отступление.
Представление функции с помощью массива является эффективным по времени, поскольку реализация массивов в большинстве случаев обеспечивает получение значения за постоянное время , не зависящее от размера массива и значения индекса.
Операции
Операцией называют функцию, все аргументы и значения которой принадлежат одному и тому же множеству. В общем случае n-местная функция типаφ:М×М×... ×М →М(иное обозначениеφ: Мⁿ → М) называетсяn-арнойоперацией на множествеМ. В таких случаях говорят, что множествоМ замкнуто относительно операцииφ (результат выполнения операцииφ наМпринадлежитМ).
В частности:
1. Функция одного аргумента φ(x) = у, имеющая типφ: М→ М,называетсяунарной операцией. Примеры унарных операций:
элементаные функции ех, log x, sin xи др.;
операция над множествами - дополнение Ā;
отображения типа А → А, такие как преобразования, перестановки;
операции над отношениями: дополнение , обратное отношениеR‾¹, составное отношениеR² = R° R, транзитивноеR°и рефлексивноеR*замыкания и др.
2. Функция двух аргументов φ(x, у) = z, имеющая типφ: М × М → М,называется бинарной операцией. Примеры бинарных операций:
• арифметические операции: сложение, вычитание, умножение, деление, возведение в степень;
• операции над множествами: пересечение , объединение, разность \;
• операция композиции функций, отображений, отношений и др. Если над элементами a,b Mвыполняется операцияφ, дающая результатz M, то это записывается часто кака φ b = z.
Свойства бинарных операций:
1) φ - ассоциативна, если для любыха, b, сизМ
(аφb)φс=аφ(bφс)
(арифметические операции сложения и умножения, операции пересечения и объединения множеств, композиция отображений - ассоциативные операции).
Выполнение этого условия (свойства ассоциативности) означает, что скобки в выражении а φ b φ сможно не расставлять;
2) φ - коммутативна, если для любыха, b, с
a φb=b φ а
(арифметические операции сложения и умножения, операции пересечения и объединения множеств - коммутативные операции; арифметические операции вычитания и деления, операция разности множеств, композиция перестановок и преобразований типа А Аконечного множества - некоммутативны);
3) φ -дистрибутивна слеваотносительно операции ψ, если для любыха, b, с
a φ (b ψ c) = (а φ b) ψ (a φ с)
и φ дистрибутивна справаотносительно операции ψ, если для любыха, b, с
(а ψ b) φ c = (а φ с) ψ (b φ с)
(арифметические операции умножения и деления дистрибутивны относительно операций сложения и вычитания слева и справа, но не наоборот: операции сложения и вычитания недистрибутивны относительно операции умножения и деления; операции объединения и пересечения множеств дистрибутивны относительно друг друга слева и справа).