\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 \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}