Добавление второй лабы и тестов к остальнымHEADmaster

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}