рефераты бесплатно
Рефераты бесплатно, курсовые, дипломы, научные работы, курсовые работы, реферат, доклады, рефераты, рефераты скачать, рефераты на тему, сочинения,рефераты литература, рефераты биология, рефераты медицина, рефераты право, большая бибилиотека рефератов, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент и многое другое.
ENG
РУС
 
рефераты бесплатно
ВХОДрефераты бесплатно             Регистрация

Абстрактное отношение зависимости  

Абстрактное отношение зависимости

Содержание


Введение. 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.

 Тогда оболочкой множества  будет множество всех элементов, находящихся в отношении сходства хотя бы с одним элементом из множества .

Введенное отношение зависимости будет транзитивным тогда и только тогда, когда соответствующее бинарное отношение  будет транзитивно, то есть является отношением эквивалентности на .

В случае, когда  - отношение эквивалентности  будет независимым тогда и  только тогда, когда  множество  содержит не более одного элемента. Любое максимальное независимое подмножество будет содержать ровно по одному элементу из каждого класса эквивалентности .

Пример 4.

Рассмотрим четырехэлементное множество .

Назовем подмножество  множества  зависимым тогда и только тогда, когда  или .

Z .

Рассмотрим подмножество  множества , по введенному определению оно будет независимо. Рассмотрим оболочку множества   и найдем оболочку оболочки нашего множества . Таким образом, мы получили , то есть рассмотренное нами отношение зависимости не является транзитивным.

Пример 5.

Рассмотрим произвольное множество  и . Множество  будем считать зависимым, если  B (А)\ B (В), то есть , но . Таким образом, получили следующее транзитивное пространство зависимости:  B (А)\ B (В. Оболочкой  будет множество .

В частности можно рассмотреть 2 случая:

1.                 , то есть все множества независимы, тогда   .

2.                  B (А), то есть все множества, кроме пустого, будут зависимыми, в этом случае  .


Пример 6.

Рассмотрим произвольное множество  и его непустое  конечное подмножество . Введем на множестве А следующее отношение зависимости

Z B (А).

Таким образом, зависимыми будут все надмножества множества .

          Если , то .

          Если , то .

          Если , то .

Получаем транзитивное пространство зависимости.

Пример 7.

Подпространство пространства зависимости  Z. Рассмотрим , где действует то же отношение зависимости Z. Тогда получим индуцированное пространство зависимости  Z  B . В этом случае зависимыми будут только те подмножества множества , которые были зависимы в пространстве  Z. И если пространство   Z транзитивно, то транзитивным будет и подпространство .

Пример 8.

Пусть  и Z = . Такое пространство зависимости  Z не транзитивно, так как   и . Пространство А имеет два базиса  и , которые являются и единственными минимальными порождающими множествами в .

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

Пример 9.

Зададим на множестве N натуральных чисел следующее отношение зависимости:

Z.

Получаем бесконечную строго возрастающую цепочку оболочек в  Z. При  получаем

.

Таким образом, имеем .

Замечание.

Понятие пространства зависимости можно и удобно определять через базу зависимости. Именно, множество B всех минимальных зависимых множеств пространства зависимости  Z назовем его базой. Ясно, что множества из B непусты, конечны и не содержатся друг в друге. Кроме того, любое независимое множество содержит некоторое множество базы B. Пространство  Z имеет единственную базу и однозначно определяется ей. Поэтому пространства зависимости можно задавать базами.

Легко видеть, что верно следующее утверждение:

Непустое множество B подмножеств множества  задает на  отношение зависимости тогда и только тогда, когда множества из B непусты, конечны и не включены друг в друга.

В терминах базы B можно сформулировать условие транзитивности соответствующего пространства зависимости.


§2. Пространства зависимости

 

Теорема 1.

Пусть  Z - произвольное пространство зависимости. Рассмотрим следующие три утверждения:

(i)                          X  базис в A;

(ii)                        X  —  максимальное независимое подмножество в A;

Страницы: 1, 2


© 2010.