Содержание

Введение. 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, что   зависимо, т.е. ............