86278 (612707), страница 4

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

Текст из файла (страница 4)

2 крок: для , ;

3 крок: для , ;

4 крок: для , ;

5 крок: для , ;

6 крок: для , ;

7 крок: для , ;

8 крок: для , ;

9 крок: для , ;

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

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

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

Використовуючи наш алгоритм одержимо наступне рішення: множина й , що так само є вірним.

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

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

Неважко бачити, що жадібний алгоритм вибере наступні елементи:

і , які не є рішенням задачі, оскільки існує краще рішення - і .

Виникає питання, у яких же випадках жадібний алгоритм дійсно вирішує поставлену задачу? На поставлене питання допоможе відповісти теорема, сформульована й доведена в [4, с.75-76].

Теорема 7.

Для будь-якої функції жадібний алгоритм знаходить незалежну множину з найбільшою вагою, тоді й тільки тоді, коли є матроїдом.

Дійсно, у нашім прикладі в задачах 1 і 2 - матроїд, а в задачі 3 таким не є, тому що не виконується аксіома М₃. Якщо розглянути , тоді одержали протиріччя з незалежністю хоча б одного із множин.

Висновок

У роботі були розглянуті такі питання, як:

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

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

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

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

1. Ван дер Варден Б.Л. Алгебра. – К., 2004

2. Кон П. Універсальна алгебра. – К., 2004.

3. Курош О. Г. Курс вищої алгебри. – К., 2003.

4. Новиков Ф. А. Дискретна математика для програмістів. – К., 2005

5. Фрид Е. Елементарне введення в абстрактну алгебру. – К., 2000

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

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