86278 (Вивчення поняття відносин залежності), страница 4
Описание файла
Документ из архива "Вивчення поняття відносин залежності", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "математика" в общих файлах.
Онлайн просмотр документа "86278"
Текст 4 страницы из документа "86278"
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