Абстрактное отношение зависимости
Краткое сожержание материала:
2
Содержание
- Введение 3
- §1.Определения и примеры 5
- §2. Пространства зависимости 12
- §3. Транзитивность 16
- §4. Связь транзитивных отношений зависимости с операторами замыкания 23
- §5. Матроиды 27
- Список библиографии 32
Введение
Целью квалификационной работы является изучение понятия отношения зависимости, рассмотрение отношения зависимости на различных множествах.
Поставленная цель предполагает решение следующих задач:
1. Изучить и дать определение понятию отношение зависимости.
2. Рассмотреть некоторые примеры отношения зависимости.
3. Сформулировать и доказать свойства и теоремы как для произвольных, так и для транзитивных пространств зависимости.
4. Рассмотреть теорему о связи транзитивного отношения зависимости и алгебраического оператора замыкания.
5. Изучить понятие матроида, привести примеры матроидов.
6. Рассмотреть жадный алгоритм и его связь с матроидами.
На основании поставленных целей и задач квалификационная работа разбивается на 5 параграфов.
В первом параграфе приведены основные определения и рассмотрены некоторые примеры отношения зависимости.
Во втором - рассматриваются произвольные пространства зависимости, их свойства и некоторые теоремы.
Третий - посвящен транзитивным и конечномерным пространствам зависимости. Здесь рассмотрены свойства транзитивных пространств зависимости и доказаны теоремы, которые подтверждают существования базиса и инвариантность размерности в любом конечномерном транзитивном пространстве зависимости.
В четвертом параграфе формулируются основные определения касающиеся оператора замыкания и рассмотрена теорема о представлении транзитивного отношения зависимости с помощью алгебраического оператора замыкания.
Пятый параграф посвящен матроидам, примерам матроидов и их применению при изучении теоретической основой анализа «жадных» алгоритмов.
Основной литературой при написании квалификационной работы стали монографии: Кона П. «Универсальная алгебра» [2] и Куроша А. Г. «Курс высшей алгебры» [3].
§1.Определения и примеры
Определение 1.
Множество Z подмножеств множества A назовем отношением зависимости на A, если выполняются следующие аксиомы:
Z1: Z ;
Z2: Z Z ;
Z3: Z ( Z - конечно).
Подмножество множества A называется зависимым, если оно принадлежит Z, и независимым в противном случае.
Легко убедиться в независимости аксиом Z1 - Z3..
Модель 1: . Полагаем Z = B (А) для любого множества .
Модель 2: . Пусть Z = при .
Модель 3:. Пусть Z = для бесконечного множества .
Определение 2.
Пространством зависимости назовем пару Z, где Z - отношение зависимости на A.
Определение 3.
Элемент называется зависимым от множества , если а X или существует такое независимое подмножество Y множества X, что зависимо, т.е. Z Z ).
Из определения 1 вытекает, что если элемент зависит от множества , то он зависит от некоторого конечного подмножества .
Определение 4.
Множество всех элементов, зависящих от X, называется оболочкой множества X и обозначается через .
Ясно, что и включение влечет включение их оболочек: .
Определение 5.
Если = A, то X называется порождающим множеством множества A.
Определение 6.
Независимое порождающее подмножество множества A называется базисом множества A.
Определение 7.
Множество зависит от , если любой элемент из зависит от , то есть .
Определение 8.
Отношение зависимости Z на A будем называть транзитивным отношением зависимости, если .
Определение 9.
Транзитивным пространством зависимости назовем пространство зависимости, в котором отношение зависимости обладает свойством транзитивности.
В качестве теоретико-множественного постулата будем использовать следующий принцип, эквивалентный известной аксиоме выбора.
Лемма Цорна.
Непустое упорядоченное множество, в котором каждое линейно упорядоченное подмножество обладает верхней гранью, имеет максимальный элемент.
Далее целесообразно рассмотреть некоторые примеры отношения зависимости:
Пример 1.
Понятие линейной зависимости в векторном пространстве V над полем . Система векторов векторного пространства V называется линейно зависимой, если существует конечная линейно зависимая ее подсистема, в противном случае - линейно независимой.
Понятие линейной зависимости в конечномерных векторных пространствах дается в курсе алгебры. Конечная система векторов V называется линейно зависимой, если существуют элементы поля одновременно не равные нулю и такие, что линейная комбинация. Множество линейных комбинаций множества векторов векторного пространства V с коэффициентами из поля P называется линейной оболочкой этих векторов и обозначается . При этом - является подпространством в пространстве V, порожденным . Получаем транзитивное отношение зависимости.
Пример 2.
Пусть поле является расширением основного поля Р, а минимальное подкольцо содержащее элементы и поле Р. Подкольцо состоит из всех элементов поля , которые выражаются через элементы и элементы поля Р при помощи сложения, вычитания и умножения: это будут всевозможные многочлены от с коэффициентами из поля Р. Тогда, если для всякого элемента существует единственная запись в виде многочлена от как неизвестных с коэффициентами из поля Р, то есть если различные многочлены от будут различными элементами подкольца , то система элементов , будет называться алгебраически независимой над полем Р, в противном случае алгебраически зависимой. Произвольное множество элементов поля Р называется зависимым, если оно содержит конечное зависимое подмножество. В первом случае кольцо изоморфно кольцу многочленов . Отношение алгебраической зависимости над полем Р является транзитивным отношением зависимости.
Пример 3.
Пусть на множестве A задано рефлексивное и симметричное бинарное отношение (называемое отношением сходства). Подмножество X множества A будем считать зависимым, если оно содержит два различных элемента, находящихся в отношении .
Оболочкой множества служит множество
В этом случае можно усилить аксиому отношения зависимости следующим образом:
Z Z.
Тогда оболочкой множества будет...
Абстрактное отношение зависимости
Третий – посвящен транзитивным и конечномерным пространствам зависимости. Здесь рассмотрены свойства транзитивных пространств зависимости и доказаны т...
Математические методы и модели
Расчет коэффициента корреляции, определение вида зависимости, параметров линии регрессии и оценка точности аппроксимации. Построение матрицы прибыли в...
Факторы, формирующие отношение к труду работников промышленных предприятий
Характеристика понятия "Отношение к труду". Факторы, определяющие отношение к труду работников промышленных предприятий: объективные, субъективные. Ха...
Проблемы общения дошкольников в зависимости от влияния семьи
Психологические характеристики дошкольного детства. Родительское отношение как фактор, влияющий на тревожность детей. Особенности развития общения реб...
Эмпирическое исследование идентификации как механизма адаптации личности в пенсионном возрасте
Проявление идентификации, ее виды, положительные стороны для пожилого человека. Виды приспособления личности к условиям старости: конструктивное отнош...