Вивчення поняття відносин залежності
Наш алгоритм буде працювати в такий спосіб:
0 крок:
;
1 крок: перевіряємо
для елемента
,
;
2 крок: для
,
;
3 крок: для
,
;
4 крок: для
,
;
5 крок: для
,
;
6 крок: для
,
;
7 крок: для
,
;
8 крок: для
,
;
9 крок: для
,
;
У результаті
одержали множину
,
.,
отриманий
результат
дійсно є рішенням
задачі.
Задача 2. Вибрати по одному елементі з кожного рядка, так щоб їхня сума була максимальна.
Тут функція
й множина
такі ж як і в
попередній
задачі, а сімейство
незалежних
підмножин
будуть утворювати
такі множини,
у яких всі елементи
з різних рядків
і порожня множина.
Використовуючи
наш алгоритм
одержимо наступне
рішення: множина
й
,
що так само є
вірним.
Задача 3. Вибрати по одному елементі з кожного стовпця й з кожного рядка, так щоб їхня сума була максимальною.
У цій задачі
функція
й множина
залишаються
колишніми, а
сімейство
незалежних
підмножин
будуть утворювати
такі множини,
у яких всі елементи
з різних стовпців
і різних рядків
і порожня множина.
Неважко бачити, що жадібний алгоритм вибере наступні елементи:
і
,
які не є рішенням
задачі, оскільки
існує краще
рішення -
і
.
Виникає питання, у яких же випадках жадібний алгоритм дійсно вирішує поставлену задачу? На поставлене питання допоможе відповісти теорема, сформульована й доведена в [4, с.75-76].
Теорема 7.
Для будь-якої
функції
жадібний алгоритм
знаходить
незалежну
множину
з найбільшою
вагою, тоді й
тільки тоді,
коли
є матроїдом.
Дійсно, у нашім
прикладі в
задачах 1 і 2
-
матроїд, а в
задачі 3 таким
не є, тому що
не виконується
аксіома М3.
Якщо розглянути
,
тоді
одержали протиріччя
з незалежністю
хоча б одного
із множин.
Висновок
У роботі були розглянуті такі питання, як:
Вивчення й визначення поняття відношення залежності.
Розглянуті деякі приклади відносин залежності.
Сформулювали й довели властивості теореми як для довільних, так і для транзитивних просторів залежності. Робота дала відповіді на всі питання, які були поставлені за мету.
Список літератури
1. Ван дер Варден Б.Л. Алгебра. – К., 2004
2. Кон П. Універсальна алгебра. – К., 2004.
3. Курош О. Г. Курс вищої алгебри. – К., 2003.
4. Новиков Ф. А. Дискретна математика для програмістів. – К., 2005
5. Фрид Е. Елементарне введення в абстрактну алгебру. – К., 2000