Курсова робота

Вивчення поняття відносин залежності

Зміст

Введення

1. Визначення й приклади

2. Простір залежності

3. Транзитивність

4. Зв'язок транзитивних відносин залежності з операторами замикання

5. Матроїди

Висновок

Список літератури

Введення

Метою курсової роботи є вивчення поняття відносини залежності, розгляд відносини залежності на різних множинах.

Поставлена мета припускає рішення наступних задач:

Вивчити й дати визначення поняттю відношення залежності.

Розглянути деякі приклади відносини залежності.

Сформулювати й довести властивості й теореми як для довільних, так і для транзитивних просторів залежності.

Розглянути теорему про зв'язок транзитивного відношення залежності й алгебраїчного оператора замикання.

Вивчити поняття матроїда, привести приклади матроїдів.

Розглянути жадібний алгоритм і його зв'язок з матроїдами.

На підставі поставлених цілей і задач кваліфікаційна робота розбивається на 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.

 Транзитивним простором залежності назвемо простір залежності, у якому відношення залежності має властивість транзитивності.

Як теоретико-множинний постулат будемо використовувати наступний принцип, еквівалентний відомій аксіомі вибору. ............