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

  • Просмотров 4526
  • Скачиваний 66
  • Размер файла 765
    Кб

Содержание Введение 3 §1.Определения и примеры 5 §2. Пространства зависимости 12 §3. Транзитивность 16 §4. Связь транзитивных отношений зависимости с операторами замыкания 23 §5. Матроиды 27 Список библиографии 32 Введение Целью квалификационной работы является изучение понятия отношения зависимости, рассмотрение отношения зависимости на различных множествах. Поставленная цель предполагает решение следующих задач: Изучить и

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

матроидами. На основании поставленных целей и задач квалификационная работа разбивается на 5 параграфов. В первом параграфе приведены основные определения и рассмотрены некоторые примеры отношения зависимости. Во втором – рассматриваются произвольные пространства зависимости, их свойства и некоторые теоремы. Третий – посвящен транзитивным и конечномерным пространствам зависимости. Здесь рассмотрены свойства

транзитивных пространств зависимости и доказаны теоремы, которые подтверждают существования базиса и инвариантность размерности в любом конечномерном транзитивном пространстве зависимости. В четвертом параграфе формулируются основные определения касающиеся оператора замыкания и рассмотрена теорема о представлении транзитивного отношения зависимости с помощью алгебраического оператора замыкания. Пятый параграф

посвящен матроидам, примерам матроидов и их применению при изучении теоретической основой анализа «жадных» алгоритмов. Основной литературой при написании квалификационной работы стали монографии: Кона П. «Универсальная алгебра» [2] и Куроша А. Г. «Курс высшей алгебры» [3]. §1.Определения и примеры Определение 1. Множество Z подмножеств множества A назовем отношением зависимости на A, если выполняются следующие аксиомы: Z1: Z ; Z2: Z Z ;