86278 (612707)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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

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

Зміст

Введення

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

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

Приклад 9.

Задамо на множині N натуральних чисел наступне відношення залежності:

Z .

Одержуємо нескінченну строго зростаючий ланцюжок оболонок в Z . При одержуємо

.

Таким чином, маємо .

Зауваження.

Поняття простору залежності можна й зручно визначати через базу залежності. Саме, множина B всіх мінімальних залежних множин простору залежності Z назвемо його базою. Ясно, що множини з B не порожні, кінцеві й не втримуються друг у другу. Крім того, будь-яка незалежна множина містить деяка множина бази B. Простір Z має єдину базу й однозначно визначається їй. Тому простору залежності можна задавати базами.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов курсовой работы