diff options
Diffstat (limited to 'lab2/report/lab2.tex')
| -rw-r--r-- | lab2/report/lab2.tex | 247 |
1 files changed, 247 insertions, 0 deletions
diff --git a/lab2/report/lab2.tex b/lab2/report/lab2.tex new file mode 100644 index 0000000..9ea1ffb --- /dev/null +++ b/lab2/report/lab2.tex @@ -0,0 +1,247 @@ +\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} |