СодержаниеrnrnВведение 3rn§1.Определения и примеры 5rn§2. Пространства зависимости 12rn§3. Транзитивность 16rn§4. Связь транзитивных отношений зависимости с операторами замыкания 23rn§5. Матроиды 27rnСписок библиографии 32
Введение
Целью квалификационной работы является изучение понятия отношения зависимости, рассмотрение отношения зависимости на различных множествах. rnПоставленная цель предполагает решение следующих задач:rn1. Изучить и дать определение понятию отношение зависимости.rn2. Рассмотреть некоторые примеры отношения зависимости.rn3. Сформулировать и доказать свойства и теоремы как для произвольных, так и для транзитивных пространств зависимости.rn4. Рассмотреть теорему о связи транзитивного отношения зависимости и алгебраического оператора замыкания.rn5. Изучить понятие матроида, привести примеры матроидов.rn6. Рассмотреть жадный алгоритм и его связь с матроидами.rnНа основании поставленных целей и задач квалификационная работа разбивается на 5 параграфов.rnВ первом параграфе приведены основные определения и рассмотрены некоторые примеры отношения зависимости.rnВо втором – рассматриваются произвольные пространства зависимости, их свойства и некоторые теоремы.rnТретий – посвящен транзитивным и конечномерным пространствам зависимости. Здесь рассмотрены свойства транзитивных пространств зависимости и доказаны теоремы, которые подтверждают существования базиса и инвариантность размерности в любом конечномерном транзитивном пространстве зависимости.rnВ четвертом параграфе формулируются основные определения касающиеся оператора замыкания и рассмотрена теорема о представлении транзитивного отношения зависимости с помощью алгебраического оператора замыкания.rnПятый параграф посвящен матроидам, примерам матроидов и их применению при изучении теоретической основой анализа «жадных» алгоритмов.
Литература
Список библиографииrnrn1. Ван дер Варден Б.Л. Алгебра. – М.: Наука, 1976. – 648 с.rn2. Кон П. Универсальная алгебра. – М.: Мир, 1968. – 352 с.rn3. Курош А. Г. Курс высшей алгебры. – СПб: Лань, 2006. – 432 с.rn4. Новиков Ф. А. Дискретная математика для программистов. – Спб: Питер, 2001. – 304 с.rn5. Фрид Э. Элементарное введение в абстрактную алгебру. – М.: Мир, 1974. – 260 с.