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

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

залежності" width="672" height="25" border="0" />Вивчення поняття відносин залежності.

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

Доказ: випливає із властивості 40;

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

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

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


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


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

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

Множина E підмножин множини A називається системою замикань, якщо Вивчення поняття відносин залежності E і система E замкнута щодо перетинань, тобто ∩D Вивчення поняття відносин залежностіE для кожної непустої підмножини D Вивчення поняття відносин залежностіE

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

Оператором замикання на множині A називається відображення J множини B (A) у себе, що володіє наступними властивостями:


J. 1. Якщо Вивчення поняття відносин залежності, то J(X)Вивчення поняття відносин залежності J(Y);

J. 2. XВивчення поняття відносин залежності J(X);

J. 3. JJ(X) = J(X), для всіх X, Y Вивчення поняття відносин залежностіB (A).


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

Оператор замикання J на множині A називається алгебраїчним, якщо для будь-яких Вивчення поняття відносин залежності і Вивчення поняття відносин залежності Вивчення поняття відносин залежності тягне Вивчення поняття відносин залежності для деякої кінцевої підмножини Вивчення поняття відносин залежності множини Вивчення поняття відносин залежності.

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

Система замикань називається алгебраїчної, якщо тільки відповідний оператор замикання є алгебраїчним

Слід зазначити теорему про взаємозв'язок між системами замикань і операторами замикань.

Теорема 5.

Кожна система замикань E на множині Вивчення поняття відносин залежності визначає оператор замикання J на Вивчення поняття відносин залежності за правилом J(X) = ∩{Y Вивчення поняття відносин залежностіE | YВивчення поняття відносин залежності X}. Обернено, кожний оператор замикання J на Вивчення поняття відносин залежності визначає систему замикань E Вивчення поняття відносин залежності JВивчення поняття відносин залежності .

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

Теорема 6.

Для будь-якого транзитивного відношення залежності Вивчення поняття відносин залежності ZВивчення поняття відносин залежності відображення Вивчення поняття відносин залежності є алгебраїчним оператором замикання на А із властивістю заміщення.

Обернено, будь-який алгебраїчний оператор замикання на А із властивістю заміщення виходить таким способом з деякого транзитивного відношення залежності Z на А.

Доказ:

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

Покажемо спочатку, що замкнуті підмножини утворять систему замикань. Якщо Вивчення поняття відносин залежності, де Вивчення поняття відносин залежності - сімейство замкнутих множин, то нехай Вивчення поняття відносин залежності - така незалежна підмножина множини B, що Вивчення поняття відносин залежності залежно; оскільки Вивчення поняття відносин залежності для всіх Вивчення поняття відносин залежності, маємо Вивчення поняття відносин залежності, звідки Вивчення поняття відносин залежності, тобто В замкнуто.

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

Цим доведено, що замкнуті підмножини утворять алгебраїчну систему замикань.

Виконання властивості заміщення потрібне з відповідної властивості просторів залежності.

Обернено, нехай Вивчення поняття відносин залежності - алгебраїчний оператор замикання із властивістю заміщення.

Будемо вважати Вивчення поняття відносин залежності залежним, якщо Вивчення поняття відносин залежності для деякого Вивчення поняття відносин залежності, і незалежним у противному випадку.

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

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

Обернено, якщо Вивчення поняття відносин залежності, те знову Вивчення поняття відносин залежності для деякої кінцевої незалежної підмножини Вивчення поняття відносин залежності множини Вивчення поняття відносин залежності. Це означає, що Вивчення поняття відносин залежності залежно, тобто Вивчення поняття відносин залежності для якогось Вивчення поняття відносин залежності.

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

Зауваження. Існують алгебраїчні оператори замикання, що не володіють властивістю заміщення. Для приклада візьмемо нескінченну циклічну напівгрупу Вивчення поняття відносин залежності.

Нехай Вивчення поняття відносин залежностіВивчення поняття відносин залежностіі Вивчення поняття відносин залежності. Тоді Вивчення поняття відносин залежності, Вивчення поняття відносин залежності, але Вивчення поняття відносин залежності.


5. Матроїди


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

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

Матроїдом Вивчення поняття відносин залежності називається кінцева множина й сімейство його підмножин Вивчення поняття відносин залежності, таке що виконується три аксіоми:

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

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

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


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

Елементи множини Вивчення поняття відносин залежності називаються незалежними, а інші підмножини Вивчення поняття відносин залежності Вивчення поняття відносин залежності - залежними множинами.

Відповідно до уведеного раніше аксіомами простору залежності бачимо, що матроїди - це в точності кінцеві транзитивне простори залежності.

Розглянемо наступні приклади матроїдів:

Приклад 1.

Сімейство всіх лінійно незалежних підмножин будь-якої кінцевої множини векторів довільного непустого векторного простору є матроїдом.

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

Приклад 2.

Вільні матроїди. Якщо Вивчення поняття відносин залежності - довільна кінцева множина, то Вивчення поняття відносин залежності - матроїд. Такий матроїд називається вільним. У вільному матроїді кожна множина незалежно, А є базисом і Вивчення поняття відносин залежності.

Приклад 3.

Матроїд трансверсалей. Нехай Вивчення поняття відносин залежності - деяка кінцева множина, і Вивчення поняття відносин залежності - деяке сімейство підмножин цієї множини. Підмножина Вивчення поняття відносин залежності називається часткової трансверсалью сімейства Вивчення поняття відносин залежності, якщо Вивчення поняття відносин залежності містить не більш ніж по одному елементі кожної підмножини із сімейства Вивчення поняття відносин залежності. Часткові трансверсали над Вивчення поняття відносин залежності утворять матроїд на А.

Перейдемо до розгляду жадібного алгоритму. Для початку потрібно сформулювати задачу, що будемо вирішувати з його використанням.

Нехай є кінцева множина Вивчення поняття відносин залежності, Вивчення поняття відносин залежності, вагова функція Вивчення поняття відносин залежності й сімейство Вивчення поняття відносин залежності.

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

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

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

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

Алгоритм такого типу називається «жадібним». Зовсім очевидно, що по побудові остаточна множина Вивчення поняття відносин залежності, тобто незалежно. Також очевидно, що жадібний алгоритм є надзвичайно ефективним: кількість кроків становитьВивчення поняття відносин залежності, тобто жадібний алгоритм є лінійним. (Не вважаючи витрат на сортування множини Вивчення поняття відносин залежності й перевірку незалежності Вивчення поняття відносин залежності.)

Приклад 4.

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

Задача 1. Вибрати по одному елементі з кожного стовпця, так щоб їхня сума була максимальна.

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

Множина Вивчення поняття відносин залежності в такий спосіб: Вивчення поняття відносин залежності

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

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

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

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

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

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