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

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

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

Зміст

Введення

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

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

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

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

5. Матроїди

Висновок

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

Введення

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

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

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

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

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

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

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

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

На підставі поставлених цілей і задач кваліфікаційна робота розбивається на 5 параграфів.

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

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

Третій – присвячений транзитивним і кінцеве мірним просторам залежності. Тут розглянуті властивості транзитивних просторів залежності й доведені теореми, які підтверджують існування базису й інваріантність розмірності в будь-якому кінцеве мірному транзитивному просторі залежності.

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

П'ятий параграф присвячений матроїдам, прикладам матроїдів і їхньому застосуванню при вивченні теоретичною основою аналізу «жадібних» алгоритмів.

Основною літературою при написанні кваліфікаційної роботи стали монографії: Кона П. «Універсальна алгебра» [2] і Куроша О. Г. «Курс вищої алгебри» [3].

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

Визначення 1.

Множина Z підмножин множини A назвемо відношенням залежності на A, якщо виконуються наступні аксіоми:

Z₁ : Z ;

Z₂ : Z Z ;

Z₃ : Z ( Z - звичайно).

Підмножина множини A називається залежною , якщо вона належить Z, і незалежною у противному випадку.

Легко переконатися в незалежності аксіом Z₁ - Z₃ ..

Модель 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 називається лінійно залежної , якщо існують елементи поля одночасно не рівні нулю й такі, що лінійна комбінація . Множина лінійних комбінацій множини векторів векторного прост

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать