Вивчення поняття відносин залежності (стр. 1 из 8)
Курсова робота
Вивчення поняття відносин залежності
Зміст
Введення
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.
Транзитивним простором залежності назвемо простір залежності, у якому відношення залежності має властивість транзитивності.
Як теоретико-множинний постулат будемо використовувати наступний принцип, еквівалентний відомій аксіомі вибору.
Лема Цорна.
Непуста впорядкована множина, у якому кожне лінійно впорядкована підмножина має верхню грань, має максимальний елемент.
Далі доцільно розглянути деякі приклади відносини залежності:
Приклад 1.
Поняття лінійної залежності у векторному просторі V над полем
. Система векторів векторного простору V називається лінійно залежної, якщо існує кінцева лінійно залежна її підсистема, у противному випадку – лінійно незалежної.Поняття лінійної залежності в кінцеве мірних векторних просторах дається в курсі алгебри. Кінцева система векторів 
V називається лінійно залежної, якщо існують елементи поля 
одночасно не рівні нулю й такі, що лінійна комбінація 
. Множина лінійних комбінацій множини векторів векторного простору V з коефіцієнтами з поля P називається лінійною оболонкою цих векторів і позначається 
. При цьому - є підпростором у просторі V, породженим
. Одержуємо транзитивне відношення залежності.Приклад 2.
Нехай поле
є розширенням основного поля Р, а 
мінімальне підкольце утримуючі елементи 
й поле Р. Підкольце складається із всіх елементів поля , які виражаються через елементи 
й елементи поля Р за допомогою додавання, вирахування й множення: це будуть усілякі багаточлени від з коефіцієнтами з поля Р. Тоді, якщо для всякого елемента 
існує єдиний запис у вигляді багаточлена від як невідомих з коефіцієнтами з поля Р, тобто якщо різні багаточлени від будуть різними елементами підкольца 
, те система елементів , буде називатися алгебраїчно незалежної над полем Р, у противному випадку алгебраїчно залежної. Довільна множина елементів поля Р називається залежним, якщо воно містить кінцеву залежну підмножину. У першому випадку кільце 
ізоморфно кільцю багаточленів 
. Відношення алгебраїчної залежності над полем Р є транзитивним відношенням залежності.