Алгебраические операции. Примеры операций. Арность операции. Способы задания.

Операция – функция все аргументы и значения которой принадлежат одному и тому же множеству. В общем случае n-местная f типа f: .

Арность операции – местность операции, количество аргументов функции. По арности операции подразделяются на:

1. Унарные. Унарной операцией на множестве М называется f типа f: M M или .

Например: дополнение, f(x)= , f(x)= (R₊), .

2. Бинарные. Бинарной операцией на множестве М называется f типа f: M² M или . Например: НОК, \, ,операции на множестве векторов,v,ʌ.

3. n-арные. N-арной опирацией на множестве М называется f типа f: .

Одним из способов задания бинарных операций на множестве является таблица Кэли.

16. Yandex.RTB R-A-252273-3
    Содержание

    • Множества. Элементы множеств. Интуитивный принцип объемности. Способы задания множества. Мощность множества.
    • Подмножества и их свойства.
    • Операции над множествами: объединение, пересечение, разность, дополнение. Диаграммы Эйлера-Венна.
    • Свойства операций над множествами (с доказательством).
    • Прямое произведение множеств. Бинарные отношения. Способы задания бинарных отношений.
    • Операции над бинарными отношениями: композиция отношений, степень отношения, обратное отношение, дополнение отношения, объединение, пересечение, разность отношений.
    • Свойства бинарных отношений: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность, связность.
    • Замыкания отношений. Транзитивное замыкание, рефлексивное транзитивное замыкание. Теоремы о транзитивном и рефлексивном транзитивном замыкании.
    • Операции над бинарными отношениями, заданными в матричной форме.
    • Алгоритм определения матрицы транзитивного замыкания бинарного отношения.
    • Отношение эквивалентности. Классы эквивалентности и их свойства. Разбиения множеств. Связь эквивалентности с разбиением (теоремы с доказательством).
    • Отношение порядка. Строгий и нестрогий порядок. Частичный и полный порядок. Упорядоченные множества.
    • Соответствия. Образ и прообраз. Свойства соответствий: всюду определенные, инъективные, сюръективные, функциональные, взаимнооднозначные соответствия.
    • Функции и отображения. Виды отображений. Обратные соответствия и функции. Способы задания функций.
    • Алгебраические операции. Примеры операций. Арность операции. Способы задания.
    • Свойства бинарных алгебраических операций: коммутативность, ассоциативность, дистрибутивность, поглощение, идемпотентность. Нейтральный и симметричный элементы.
    • Комбинаторные правила суммы и произведения. Выборки (упорядоченные, неупорядоченные, с повторениями и без).
    • Операции над графами.
    • Способы представления графов и орграфов на эвм: матрица смежности, матрица инцидентности, список смежности, массив ребер (дуг).
    • Маршруты в графах. Виды маршрутов: замкнутые и незамкнутые. Цепь. Простая цепь. Цикл. Простой цикл. Длина маршрута. Расстояние между вершинами. Диаметр графа.
    • Орграфы и бинарные отношения. Отношение достижимости вершин орграфа. Матрица достижимости. Связь между отношениями достижимости и смежности.
    • Определение матрицы достижимости орграфа как матрицы рефлексивного и транзитивного замыкания отношения смежности.
    • Алгоритм выделения компонент связности (сильной связности)
    • Нагруженные орграфы Длина пути в нагруженном орграфе. Минимальные пути в нагруженных орграфах.
    • Нагруженные орграфы. Алгоритм Форда-Беллмана выделения минимального пути в нагруженном орграфе.

    Yandex.RTB R-A-252273-4