293 lines
15 KiB
TeX
293 lines
15 KiB
TeX
\documentclass[12pt,a4paper,bibliography=totoc]{scrartcl}
|
||
\usepackage[affil-it]{authblk} % для указания ВУЗа
|
||
\usepackage{fontspec}
|
||
\usepackage{minted} % для включения исходников
|
||
\usemintedstyle{tango}
|
||
\defaultfontfeatures{Mapping=tex-text}
|
||
\usepackage{xunicode}
|
||
\usepackage{xltxtra}
|
||
|
||
\setsansfont{CMU Sans Serif}
|
||
\setmainfont{CMU Serif}
|
||
\setmonofont{Ubuntu Mono}
|
||
\newfontfamily{\cyrillicfonttt}{Iosevka}
|
||
|
||
\defaultfontfeatures{Scale=MatchLowercase,Mapping=tex-text}
|
||
\usepackage{polyglossia}
|
||
\setdefaultlanguage{russian}
|
||
\usepackage{amsmath}
|
||
\usepackage{amsfonts}
|
||
\usepackage{amssymb}
|
||
\usepackage{amsthm}
|
||
\usepackage{yfonts}
|
||
\usepackage{theoremref}
|
||
\usepackage{hyperref}
|
||
\usepackage{graphicx}
|
||
\usepackage{algorithm}
|
||
\usepackage{algpseudocode}
|
||
|
||
\newtheorem{stm}{Утверждение}
|
||
|
||
\author{Алексей Лобанов, 318 группа%
|
||
\thanks{E-mail: \texttt{i@likemath.ru}}}
|
||
\affil{факультет ВМК МГУ им. М.В.Ломоносова}
|
||
|
||
\author{Научный руководитель \\ доцент, д.ф.-м.н. С.Н.Селезнёва%
|
||
\thanks{E-mail: \texttt{selezn@cs.msu.ru}}}
|
||
\affil{ } % хак, чтобы не печатать ВУЗ дважды
|
||
|
||
\date{Москва, 2018}
|
||
\title{Нахождение минимальных клонов трёхзначных и четырёхзначных логик}
|
||
\addto\captionsrussian{\def\refname{Список используемых источников}}
|
||
|
||
\makeindex
|
||
\begin{document}
|
||
\thispagestyle{empty}
|
||
|
||
\begin{center}
|
||
\vspace{-3cm}
|
||
\includegraphics[width=0.5\textwidth]{img/msu_new.eps}\\
|
||
{Московский государственный университет имени М.В.~Ломоносова}\\
|
||
Факультет вычислительной математики и кибернетики\\
|
||
Кафедра математической кибернетики
|
||
|
||
\vspace{5cm}
|
||
|
||
{\Large Лобанов~Алексей~Андреевич}
|
||
|
||
\vspace{1cm}
|
||
|
||
{\Large\bfseries
|
||
Нахождение минимальных клонов двухзначных и трёхзначных логик\\}
|
||
|
||
\vspace{1cm}
|
||
|
||
{\large КУРСОВАЯ РАБОТА}
|
||
\end{center}
|
||
\vfill
|
||
\begin{flushright}
|
||
\textbf{Научный руководитель:}\\
|
||
доцент, д.ф.-м.н. \\
|
||
С.Н.~Селезнёва
|
||
\end{flushright}
|
||
\vfill
|
||
\begin{center}
|
||
Москва, 2018
|
||
\end{center}
|
||
\enlargethispage{4\baselineskip}
|
||
\newpage
|
||
%\maketitle
|
||
%\newpage
|
||
|
||
\tableofcontents
|
||
|
||
\newpage
|
||
\section{Введение}
|
||
В данной работе рассматривается задача построения всех минимальных замкнутых классов в трёхзначных и четырёхзначных логиках.
|
||
Ранее, в работе \cite{csakany} уже получены все такие классы для случая трёхзначной логики,
|
||
а в \cite{machida} эти функции записаны в форме полиномов над $\mathbb{E}^3$.
|
||
В \cite{scholzel} было указано сколько таких классов для случая четырёхзначной логики.
|
||
|
||
Эта задача интересна тем, что сложность проверки выполнимости системы ограничений например в коньюктивных запросов к БД зависит только от того, какие функции сохраняют все отношения этой системы
|
||
|
||
Например,
|
||
|
||
|
||
\newpage
|
||
\section{Постановка задачи}
|
||
\subsection{Основные определения}
|
||
Все определения: функция, формула, замкнутый класс, идемпотентная функция, функция большинства, полупроекция
|
||
|
||
\subsection{Формулировка задач}
|
||
В рамках данной курсовой работы рассматриваются следующие задачи:
|
||
\begin{enumerate}
|
||
\item Написать программу,
|
||
которая строит все минимальные клоны,
|
||
порождаемые какой-то идемпотентной двухместной функцией
|
||
$f$ трёхзначной логики.
|
||
Получить экспериментальный результат
|
||
в виде списка функций от двух переменных,
|
||
содержащихся в каждом таком клоне.
|
||
|
||
\item Написать программу,
|
||
которая строит все клоны,
|
||
порождаемые какой-то идемпотентной двухместной функцией
|
||
$f$ четырехзначной логики,
|
||
не содержащие функций большинства и полупроекций.
|
||
Получить экспериментальный результат
|
||
в виде списка функций двух переменных,
|
||
содержащихся в каждом таком клоне.
|
||
\end{enumerate}
|
||
|
||
\newpage
|
||
\section{Основная часть}
|
||
Введём некоторые обозначения:
|
||
$I_k^2$ -- все идемпотентные функции k-значной логики,
|
||
$f_k^x$, $f_k^y$ -- функции k-значной логики, тождественно равные своему первому и второму аргументу соответственно.
|
||
Назовём "плохими" функции $f\left( x, y\right)$ из $I_k^2$, которые точно не смогут породить минимальные классы.
|
||
|
||
Простейшая реализация алгоритма решения данной задачи может не приветси к успеху: для $k=4$ количество функций в $I_4^2 = 4^{4\cdot4 - 4} = 4^{12} = 16777216$. Построение класса по каждой из них слишком трудоёмко, если знать, что некоторая часть этих классов по размеру сопоставимы с самим $I_4^2$. Таким образом, уже для $k=4$ необходим более быстрый алгоритм.
|
||
|
||
Для написания алгоритма решения поставленной задачи, воспользуемся следующими утверждениями.
|
||
\begin{stm}
|
||
Любая функция из $I_k^2$, кроме, быть может, $f_k^x$ и $f_k^y$ встречается не более, чем в одном минимальном классе
|
||
\end{stm}
|
||
|
||
Если условия 1 2 4, то задача проверки выполнимости ограничений полиномиальна, например коньюктивные запросы к БД, если просто 5, то NP полна, а если 3, то непонятно.
|
||
|
||
|
||
Алгоритм представим в виде трёх частей:
|
||
\begin{enumerate}
|
||
\item \textbf{Генерация функций для перебора} В этой части мы должны оставить для рассмотрения только те функции $f\left( x, y\right)$ из $I_k^2$, которые удовлетворяют следующим свойствам:
|
||
\begin{enumerate}
|
||
\item $f\left( x, y\right) = f_k^x$ или $f\left( x, y\right) = f_k^y$
|
||
\item Из $f\left( x, y\right)$ можно получить $h(x, y, z)$, существенно зависящую от 3-х переменных, для которой $h(x, x, y) = h(x, y, x) = h(y, x, x) = x$
|
||
%\item Из $f\left( x, y\right)$ можно получить $h(x, y, z) = x - y + z$,
|
||
%где $+$ операция коммутативной группы на $\mathbb{E}_k$
|
||
\item Из $f\left( x, y\right)$ можно получить $h(x_1, \ldots, x_k)$, $k \ge 3$, не равную $x_1, ..., x_k$,
|
||
для которой верно: существует такое $i$, $1 \le i \le k$,
|
||
что если среди элементов $x_1, \ldots, x_k$ хотя бы два совпадающих,
|
||
то $f(x_1, \ldots, x_k) =x_i$. Такая функция называется \emph{полупроекцией}.
|
||
\end{enumerate}
|
||
Проверка каждого из этих свойств тривиальна, в том числе и вычислительно, относительно других частей.
|
||
|
||
Полученные функции мы кладём в очередь $d$.
|
||
\item \textbf{Расширение множеств функций} В этой части мы берём один элемент из очереди, производим "расширение" класса функций \ref{alg:extending} и кладём в конец очереди. Причём расширение происходит таким образом, что на каждом расширении для одного и того же множества, $\frac{\texttt{max}_{n+1}}{\texttt{max}_n} = \lambda$, где $1 < \lambda < 2$, а $n$ -- номер расширения. Это необходимого для экономного расхода памяти ЭВМ.
|
||
|
||
\item \textbf{Обработка множеств функций после расширения} В этой части мы должны рассмотреть все обработанные множества функций и обработать их, псевдокод ниже \ref{alg:queue}. Это самая концептуально сложная часть алгоритма.
|
||
\end{enumerate}
|
||
|
||
При такой декомпозиции возможно использовать многоядерность современных ЭВМ для распараллеливания расширения множеств функций, что позволяет почти линейно уменьшить время работы.
|
||
|
||
Опишем работу некоторых ключевых процедур.
|
||
Главной такой является "расширение" множества функций \ref{alg:extending}.
|
||
\begin{algorithm}
|
||
\caption{Расширение множества функций}\label{alg:extending}
|
||
\begin{algorithmic}
|
||
\Function{ExtendFunctionClass}{class, max}
|
||
\If {size(class) $\geq$ max}
|
||
|
||
\Return (class, False)
|
||
\EndIf
|
||
\State is\_finished $\gets$ False
|
||
\State last\_size $\gets$ 0
|
||
\While{True}
|
||
\State new\_funcs $\gets \{\}$
|
||
\Comment{Пустое множество}
|
||
\ForAll{$f_1 \in$ class}
|
||
\State new\_funcs.add(reversed($f_1$))
|
||
\Comment{Для всех $f_1(x,y)$ добавим $f_1'(y,x)$}
|
||
|
||
\ForAll{$f_2 \in$ class}
|
||
\State new\_funcs.add($f_1\left(f_2, y \right)$)
|
||
\EndFor
|
||
\EndFor
|
||
\State new\_funcs.remove($f_k^x$)
|
||
\State new\_funcs.remove($f_k^y$)
|
||
\Comment{Могли добавиться тождественные функции, их нужно убрать}
|
||
\If {size(new\_funcs) $=$ last\_size}
|
||
\State is\_finished $\gets$ True
|
||
\State \textbf{break}
|
||
\Comment{Мы закончили построение этого класса функций}
|
||
\EndIf
|
||
|
||
\State class $\gets$ class $\cup$ new\_funcs
|
||
\State last\_size $\gets$ size(new\_funcs)
|
||
|
||
\If {size(class) $>$ max}
|
||
\State \textbf{break}
|
||
\Comment{Класс стал достаточно большим -- нужно выходить}
|
||
\EndIf
|
||
\EndWhile
|
||
|
||
\Return (class, is\_finished)
|
||
|
||
\EndFunction
|
||
\end{algorithmic}
|
||
\end{algorithm}
|
||
|
||
Также важной функцией является обработка новых множеств \ref{alg:queue}.
|
||
|
||
\begin{algorithm}
|
||
\caption{Обработка расширенных множеств}\label{alg:queue}
|
||
\begin{algorithmic}
|
||
\Procedure{ProcessSets}{d, bad\_functions}
|
||
\While{Не все функции закончены}
|
||
\State local\_d $\gets$ d
|
||
\State d.clear()
|
||
\State local\_d сортируем по размеру множества
|
||
\State cur\_size $\gets \lambda^n$
|
||
\ForAll{task $\in$ local\_d}
|
||
\If {size(task) $>$ cur\_size}
|
||
\State \textbf{break}
|
||
\Comment{Текущие множетсва слишком большие, могут быть незаконченные}
|
||
\EndIf
|
||
\If {task не закончен}
|
||
\If {в нём есть хотя бы одна "плохая" функция}
|
||
\State completed $\gets$ completed + 1
|
||
\Comment{Текущий класс точно не минимальный}
|
||
\Else
|
||
\State d.add(task)
|
||
\Comment{Класс надо ещё расширить}
|
||
\EndIf
|
||
\Else
|
||
\State completed $\gets$ completed + 1
|
||
\If {в нём нет "плохих" функций}
|
||
\State положим класс в список минимальных классов
|
||
\EndIf
|
||
\State все функции task сделаем "плохими"
|
||
\Comment Ни одна из этих функций уже не сможем породить минимальный класс
|
||
\EndIf
|
||
\EndFor
|
||
\EndWhile
|
||
\EndProcedure
|
||
\end{algorithmic}
|
||
\end{algorithm}
|
||
Для реализации полученных алгоритмов для выполнения на ЭВМ был выбран язык программирования C++14.
|
||
|
||
\newpage
|
||
\section{Полученные результаты}
|
||
С помощью написанных программ для ЭВМ на языке программирования C++14 удалось получить решения поставленных задач.
|
||
|
||
Опишем кодирование решения. Пусть исходная функция имеет значения
|
||
$$
|
||
f\left( x, y \right) = \left( 0ab \: c1d \: et2 \right)
|
||
$$
|
||
тогда число $\overline{abcdet}$
|
||
рассмотрим в десятичной системе и назовём \emph{номером функции}.
|
||
|
||
Для трехзначной логике список номеров порождающих функций ниже:
|
||
|
||
0, 8, 10, 11, 16,
|
||
17, 20, 26, 33, 35,
|
||
36, 37, 38, 40, 41,
|
||
42, 43, 47, 53, 68,
|
||
71, 80, 116,122, 125,
|
||
178, 179, 188, 206, 215,
|
||
280, 281, 286, 287, 290,
|
||
296, 364, 368, 448, 449,
|
||
458, 528, 530, 557, 624,
|
||
692, 728. Всего 42 функции.
|
||
|
||
Для случая четырёхзначной логики таких функций 2279.
|
||
|
||
\newpage
|
||
\begin{thebibliography}{}
|
||
\bibitem{csakany} B.Csakany -- All minimal clones on three-element set
|
||
\bibitem{machida} Hajime Machida, Michael Pinsker -- Polynomials as Generators of Minimal Clones
|
||
\bibitem{scholzel} Karsten Schölzel -- The minimal clones generated by semiprojections on a four-element set
|
||
\end{thebibliography}
|
||
|
||
\newpage
|
||
\section*{Приложение А. Исходный код программы на C++14}
|
||
\addcontentsline{toc}{section}{Приложение А. Исходный код программы на C++14}
|
||
\subsection*{main.cpp}
|
||
\inputminted{C++}{main.cpp}
|
||
\subsection*{al\_utility.hpp}
|
||
\inputminted{C++}{al_utility.hpp}
|
||
\subsection*{al\_utility.cpp}
|
||
\inputminted{C++}{al_utility.cpp}
|
||
\subsection*{finite\_function.hpp}
|
||
\inputminted{C++}{finite_function.hpp}
|
||
|
||
\end{document} |