path: root/lab2/report/lab2.tex

\documentclass[spec, och, labwork2]{SCWorks}
\usepackage{preamble}

\begin{document}
\include{titlepage.tex}
\tableofcontents

\section{Постановка задачи}

Цель работы "--- изучение основных свойств бинарных отношений и операций
замыкания бинарных отношений. Порядок выполнения работы:

\begin{enumerate}
  \item
    Разобрать определения отношения эквивалентности, фактор-множества.
    Разработать алгоритмы построения эквивалентного замыкания бинарного
    отношения и системы представителей фактор-множества.
  \item
    Разобрать определения отношения порядка и диаграммы Хассе. Разработать
    алгоритмы вычисления минимальных (максимальных) и наименьших (наибольших
    элементов  и построения диаграммы Хассе. 
  \item
    Разобрать определения контекста и концепта. Разработать алгоритм вычисления
    решетки концептов.
\end{enumerate}


\section{Теоретические сведения}

\subsection{Отношения эквивалентности и фактор"=множества}

Бинарное отношение $\varepsilon$ на множестве $A$ называется отношением
эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично
и транзитивно.

Для любого подмножества $X \subset A$ множество $\rho(X) = \{b \in B: (x, b) \in
\rho \text{ для некоторого } x \in X\}$ называется образом множества $X$
относительно отношения $\rho$.

Образ одноэлементного множества $X = \{a\}$ относительно отношения $\rho$
обозначается символом $\rho(a)$ и называется также образом элемента $a$ или
срезом отношения $\rho$ через элемент $a$. 

Срезы $\varepsilon(a)$ называются классами эквивалентности по отношению
$\varepsilon$ и сокращенно обозначаются символом $[a]$. Множество всех таких
классов эквивалентности $\{[a]: a \in A\}$ называется фактор"=множеством
множества $A$ по эквивалентности $\varepsilon$ и обозначается символом
$A/\varepsilon$.

\begin{lemma}[О замыканиях бинарных отношений]
  На множестве $P(A^2)$ всех бинарных отношений между элементами множества $A$
  следующие отображения являются операторами замыканий:
  \begin{enumerate}
    \item
      $f_r(\rho) = \rho \cup \triangle_A$ "--- наименьшее рефлексивное бинарное
      отношение, содержащее отношение $\rho \subset A^2$,
    \item
      $f_s(\rho) = \rho \cup \rho^{-1}$ "--- наименьшее симметричное бинарное
      отношение, содержащее отношение $\rho \subset A^2$,
    \item
      $f_t(\rho) = \bigcup^\infty_{n=1} \rho^{n}$ "--- наименьшее транзитивное
      бинарное отношение, содержащее отношение $\rho \subset A^2$,
    \item
      $f_{eq}(\rho) = f_t f_s f_r(\rho)$ "--- наименьшее отношение эквивалентности,
      на содержащее отношение $\rho \subset A^2$.
  \end{enumerate}        
\end{lemma}


\subsection{Отношения порядка}

Бинарное отношение $\omega$ на множестве $A$ называется отношением порядка (или
просто порядком), если оно рефлексивно, антисимметрично и транзитивно.

Поскольку отношение порядка интуитивно отражает свойство <<больше"=меньше>>, то
для обозначения порядка $\omega$ используется инфиксная запись с помощью символа
$\leq$: вместо $(a, b) \in \omega$ принято писать $a \leq b$ (читается <<a
меньше или равно b>>, <<a содержится в b>> или <<b больше или равно a>>, <<b
содержит a>>).

Запись $<$ означает, что $a \leq b$ и $a \neq b$.

Запись  $\lessdot$ означает, что $a \leq b$ и нет элементов $x$, удовлетворяющих
условию $a < x < b$. В этом случае говорят, что элемент $b$ покрывает элемент
$a$ или что элемент $a$ покрывается элементом $b$.

Элементы $a, b \in A$ называются сравнимыми, если $a \leq b$ или $b \leq a$, и
несравнимыми в противном случае.

Множество $A$ с заданным на нем отношением порядка $\leq$ называется
упорядоченным множеством и обозначается $A = (A, \leq)$ или просто $(A, \leq)$.

Элемент $a$ упорядоченного множества $(A, \leq)$ называется:
\begin{enumerate}
  \item Минимальным, если $(\forall x \in A) \text{ } x \leq a \implies x = a$;
  \item Максимальным, если $(\forall x \in A) \text{ } a \leq x \implies x = a$;
  \item Наименьшим, если $(\forall x \in A) \text{ } a \leq x$;
  \item Наибольшим, если $(\forall x \in A) \text{ } x \leq a$.
\end{enumerate}

\begin{lemma}
  Для любого конечного упорядоченного множества $A = (A, \leq)$ справедливы
  следующие утверждения:
  \begin{enumerate}
    \item
      Любой элемент множества $A$ содержится в некотором максимальном элементе и
      содержит некоторый минимальный элемент;
    \item
      Если упорядоченное множество $A$ имеет один максимальный (соответственно,
      минимальный) элемент, то он является наибольшим (соответственно,
      наименьшим) элементом этого множества.
  \end{enumerate}
\end{lemma}


\subsection{Диаграммы Хассе}

Упорядоченное множество $A = (A, \leq)$ наглядно представляется диаграммой
Хассе, которая представляет элементы множества $A$ точками плоскости и пары $a
<\cdot \text{ } b$ представляет линиями, идущими вверх от элемента $a$ к
элементу $b$.

Алгоритм построения диаграммы Хассе конечного упорядоченного множества $A = (A,
\leq)$.

\begin{enumerate}
  \item
    В упорядоченном множестве $A = (A, \leq)$ найти множество $A_1$ всех
    минимальных элементов и расположить их в один горизонтальный ряд (это первый
    уровень диаграммы).
  \item
    В упорядоченном множестве $A \setminus A_1$, найти множество $A_2$ всех
    минимальных элементов и расположить их в один горизонтальный ряд над первым
    уровнем (это второй уровень диаграммы). Соединить отрезками элементы этого
    ряда с покрываемыми ими элементами предыдущего ряда.
  \item
    В упорядоченном множестве $A \setminus (A_1 \cup A_2)$ найти множество $A_3$
    всех минимальных элементов и расположить их в один горизонтальный ряд над
    вторым уровнем (это третий уровень диаграммы).  Соединить отрезками элементы
    этого ряда с покрываемыми ими элементами предыдущих рядов.
  \item
    Процесс продолжается до тех пор, пока не выберутся все элементы множества
    $A$.
\end{enumerate}


\subsection{Определение контекста, концепта и решетки}

Контекстом называется алгебраическая система $K = (G, M, \rho)$, состоящая из
множества объектов $G$, множества атрибутов $M$ и бинарного отношения $\rho
\subset G \times M$, показывающего $(g, m) \in \rho$, что объект $g$ имеет
атрибут $m$.

Упорядоченная пара $(X, Y)$ замкнутых множеств $X \in Z_{f_G}, Y \in Z_{f_M}$,
удовлетворяющих условиям $\varphi(X) = Y$, $\psi(Y) = X$, называется концептом
контекста $K = (G, M, \rho)$. При этом компонента $X$ называется объемом и
компонента $Y$ "--- содержанием концепта $(X, Y)$.

Порядок $\leq$ на множестве $A$ называется решеточным, если $\forall a, b \in A$
существуют $sup \{a, b\}$ и $inf \{a, b\}$, которые обозначаются соответственно
$a \vee b$, $a \wedge b$ и называются также объединением и пересечением
элементов $a, b$. Множество с заданным на нем решеточным порядком называется
решеточно упорядоченным множеством или решеткой. 

Решетка $A$ называется полной, если любое ее подмножество $X \subset A$ имеет
точные грани $\text{inf} ~ X$ и $\text{sup} ~ X$.

\begin{theorem}[О полной решетке]
  Если в упорядоченном множестве $A$ каждое подмножество имеет точную верхнюю
  грань, то $A$ является полной решеткой.

  Множество всех концептов $C(K)$ так упорядочивается отношением $(X, Y) \leq
  (X_1, Y_1) \Leftrightarrow X \subset X_1$ (или равносильно $Y_1 \subset Y$),
  что $(C(K), \leq)$ является полной решеткой, которая изоморфна решетке
  замкнутых подмножеств множества $G$.

  Алгоритм вычисления системы замыканий на множестве $G$:
  \begin{enumerate}
    \item
      Рассматриваем множество $G \in Z_{f_G}$.
    \item
      Последовательно перебираем все элементы $m \in M$ и вычисляем для них
      $\psi(\{m\}) = \rho^{-1}(m)$.
    \item
      Вычисляем все новые пересечения множества $\psi(\{m\})$ с ранее
      полученными множествами и добавляем новые множества к $Z_{f_G}$.
      Аналогично вычисляется система замыканий на множестве $M$.
  \end{enumerate}
\end{theorem}


\section{Алгоритмы}

\input{tmp/algo.tex}


\section{Программная реализация}

\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{c}{../lab2.py}


\section{Результаты тестирования}

Результаты тестирования программы.

\begin{figure}[H]
  \centering
  \includegraphics[width=0.7\textwidth]{test1.png}
  \caption{Эквивалентное замыкание и фактор-множество}
\end{figure}

\begin{figure}[H]
  \centering
  \includegraphics[width=0.7\textwidth]{test2.png}
  \caption{Минимальные и максимальные элементы множества}
\end{figure}

\begin{figure}[H]
  \centering
  \includegraphics[width=0.7\textwidth]{test3.png}
  \caption{Построение диаграммы Хассе}
\end{figure}

\begin{figure}[H]
  \centering
  \includegraphics[width=0.7\textwidth]{hasse.png}
  \caption{Диаграмма Хассе}
\end{figure}

\begin{figure}[H]
  \centering
  \includegraphics[width=0.7\textwidth]{test4.png}
  \caption{Система замыканий и решётка концептов}
\end{figure}

\conclusion

В ходе выполнения данной лабораторной работы были изучены определения отношения
эквивалентности, фактор-множества, отношения порядка и диаграммы Хассе,
контекста и концепта. Были разработаны алгоритмы построения эквивалентного
замыкания бинарного отношения и системы представителей фактор-множества,
вычисления минимальных (максимальных) и наименьших (наибольших) элементов и
построения диаграммы Хассе, вычисления решетки концептов, а также были
произведена оценка сложности вычисления данных алгоритмов. Программная
реализация на языке Python с библиотекой numpy успешно прошла тестирование.

\end{document}