Xreferat.com » Рефераты по математике » Вивчення поняття відносин залежності

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

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

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


Зміст


Введення

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.

Нехай поле Вивчення поняття відносин залежності є розширенням основного поля Р, а Вивчення поняття відносин залежності мінімальне підкольце утримуючі елементи Вивчення поняття відносин залежності й поле Р. Підкольце Вивчення поняття відносин залежності складається із всіх елементів поляВивчення поняття відносин залежності, які виражаються через елементи Вивчення поняття відносин залежності й елементи поля Р за допомогою додавання, вирахування й множення: це будуть усілякі багаточлени від Вивчення поняття відносин залежності з коефіцієнтами з поля Р. Тоді, якщо для всякого елемента Вивчення поняття відносин залежності існує єдиний запис у вигляді багаточлена від Вивчення поняття відносин залежності як невідомих з коефіцієнтами з поля Р, тобто якщо різні багаточлени від Вивчення поняття відносин залежності будуть різними елементами підкольца Вивчення поняття відносин залежності, те система елементів Вивчення поняття відносин залежності, буде називатися алгебраїчно незалежної над полем Р, у противному випадку алгебраїчно залежної. Довільна множина елементів поля Р називається залежним, якщо воно містить кінцеву залежну підмножину. У першому випадку кільце Вивчення поняття відносин залежності ізоморфно кільцю багаточленів Вивчення поняття відносин залежності. Відношення алгебраїчної залежності над полем Р є транзитивним відношенням залежності.

Приклад 3.

Нехай на множині A задане рефлексивне й симетричне бінарне відношення Вивчення поняття відносин залежності (називане відношенням подібності). Підмножина X множини A будемо вважати залежним, якщо воно містить два різних елементи, що перебувають у відношенні Вивчення поняття відносин залежності.

Оболонкою множини Вивчення поняття відносин залежності служить множина


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


У цьому випадку можна підсилити аксіому Вивчення поняття відносин залежності відносини залежності в такий спосіб:


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


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

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

У випадку, коли Вивчення поняття відносин залежності - відношення еквівалентності Вивчення поняття відносин залежності буде незалежним тоді й тільки тоді, коли Вивчення поняття відносин залежності множина Вивчення поняття відносин залежності містить не більше одного елемента. Будь-яка максимальна незалежна підмножина буде містити рівно по одному елементі з кожного класу еквівалентності Вивчення поняття відносин залежності.

Приклад 4.

Розглянемо чотирьох елементну множину Вивчення поняття відносин залежності.

Назвемо підмножину Вивчення поняття відносин залежності множини Вивчення поняття відносин залежності залежним тоді й тільки тоді, коли Вивчення поняття відносин залежності або Вивчення поняття відносин залежності.


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


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

Приклад 5.

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

Зокрема можна розглянути 2 випадки:

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

Вивчення поняття відносин залежності B (А)Вивчення поняття відносин залежностіВивчення поняття відносин залежності , тобто всі множини, крім порожнього, будуть залежними, у цьому випадку Вивчення поняття відносин залежності Вивчення поняття відносин залежності.

Приклад 6.

Розглянемо довільну множину Вивчення поняття відносин залежності і його непусту кінцеву підмножину Вивчення поняття відносин залежності. Уведемо на множині А наступне відношення залежності


ZВивчення поняття відносин залежності B (А)Вивчення поняття відносин залежності .


Таким чином, залежними будуть всі надмножини множини Вивчення поняття відносин залежності.

Якщо Вивчення поняття відносин залежності, то Вивчення поняття відносин залежності.

Якщо Вивчення поняття відносин залежності, то Вивчення поняття відносин залежності.

Якщо Вивчення поняття відносин залежності, то Вивчення поняття відносин залежності.


Одержуємо транзитивний простір залежності.

Приклад 7.

Підпростір простору залежності Вивчення поняття відносин залежності ZВивчення поняття відносин залежності . Розглянемо Вивчення поняття відносин залежності, де діє те ж відношення залежності Z. Тоді одержимо індукований простір залежності Вивчення поняття відносин залежності Z Вивчення поняття відносин залежності B Вивчення поняття відносин залежності. У цьому випадку залежними будуть тільки ті підмножини множиниВивчення поняття відносин залежності, які були залежні в просторі Вивчення поняття відносин залежності ZВивчення поняття відносин залежності . І якщо простір Вивчення поняття відносин залежності ZВивчення поняття відносин залежності транзитивне, те транзитивним буде й підпростір Вивчення поняття відносин залежності.

Приклад 8.

Нехай Вивчення поняття відносин залежності і Z = Вивчення поняття відносин залежності. Такий простір залежності Вивчення поняття відносин залежності ZВивчення поняття відносин залежності не транзитивне, тому що Вивчення поняття відносин залежності й Вивчення поняття відносин залежності. Простір А має два

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: