Абстрактное отношение зависимости

Целью квалификационной работы является изучение понятия отношения зависимости, рассмотрение отношения зависимости на различных множествах.
Поставленная цель предполагает решение следующих задач:
1. Изучить и дать определение понятию отношение зависимости.
2. Рассмотреть некоторые примеры отношения зависимости.
3. Сформулировать и доказать свойства и теоремы как для произвольных, так и для транзитивных пространств зависимости.
4. Рассмотреть теорему о связи транзитивного отношения зависимости и алгебраического оператора замыкания.
5. Изучить понятие матроида, привести примеры матроидов.
6. Рассмотреть жадный алгоритм и его связь с матроидами.
На основании поставленных целей и задач квалификационная работа разбивается на 5 параграфов.
В первом параграфе приведены основные определения и рассмотрены некоторые примеры отношения зависимости.
Во втором – рассматриваются произвольные пространства зависимости, их свойства и некоторые теоремы.
Третий – посвящен транзитивным и конечномерным пространствам зависимости. Здесь рассмотрены свойства транзитивных пространств зависимости и доказаны теоремы, которые подтверждают существования базиса и инвариантность размерности в любом конечномерном транзитивном пространстве зависимости.
В четвертом параграфе формулируются основные определения касающиеся оператора замыкания и рассмотрена теорема о представлении транзитивного отношения зависимости с помощью алгебраического оператора замыкания.
Пятый параграф посвящен матроидам, примерам матроидов и их применению при изучении теоретической основой анализа «жадных» алгоритмов.

Список библиографии

1. Ван дер Варден Б.Л. Алгебра. – М.: Наука, 1976. – 648 с.
2. Кон П. Универсальная алгебра. – М.: Мир, 1968. – 352 с.
3. Курош А. Г. Курс высшей алгебры. – СПб: Лань, 2006. – 432 с.
4. Новиков Ф. А. Дискретная математика для программистов. – Спб: Питер, 2001. – 304 с.
5. Фрид Э. Элементарное введение в абстрактную алгебру. – М.: Мир, 1974. – 260 с.