% Original author: Sergey Lozhkin <lozhkin@cs.msu.su>
% Original URI:
%     http://mathcyb.ru/wiki/Основы_кибернетики_%28318-328_группы%29
%
% This document author: Alexander Turenko <totktonada.ru@gmail.com>
% This document URI:
%     http://cmcstuff.esyr.org/newstuff/6sem/Основы%20кибернетики/Теормин_по_методичке_2013.{tex,pdf}

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{indentfirst}

\usepackage{geometry}
\geometry{a4paper}
\sloppy

\usepackage[fleqn]{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[mathscr]{eucal}
\usepackage{amsthm}
\usepackage{misccorr}

\newtheorem*{theorems}{Теорема}
\newtheorem*{lemms}{Лемма}
\newtheorem*{defs}{Определение}
\newtheorem*{note}{Замечание}
\newtheorem*{stat}{Утверждение}
\newtheorem*{cons}{Следствие}
\newtheorem*{prop}{Свойство}

\newenvironment{compactlist}{
    \begin{list}{{$\bullet$}}{
            \setlength\partopsep{0pt}
            \setlength\parskip{0pt}
            \setlength\parsep{0pt}
            \setlength\topsep{0pt}
            \setlength\itemsep{0pt}
    }
}{
    \end{list}
}

\begin{document}

\part*{Теоретический минимум по «основам кибернетики», 3 курс, 6 семестр}

\part{Минимизация дизъюнктивных нормальных форм и связанные с ней задачи}

\section{Представление функций алгебры логики (ФАЛ) дизъюнктивными нормальными
формами (ДНФ) и его «геометрическая» интерпретация. Совершенная ДНФ и
критерий единственности ДНФ.}

См. \S 2 методички, он почти целиком состоит из определений. Список:

\begin{compactlist}
    \item единичный куб (гиперкуб) размерности $n$;
    \item $i$-й слой куба $B^n$;
    \item отношение лексикографического линейного порядка на множестве $B^n$;
    \item отрезок куба $B^n$;
    \item расстояние Хэмминга;
    \item противоположные, соседние (соседние по $i$-й переменной) наборы;
    \item сфера и шар радиуса $t$ с центром $\alpha$;
    \item отношение частичного порядка $\leqslant$ на $B^n$;
    \item сравнимые и несравнимые наборы;
    \item грань куба $B^n$, её размерность и ранг;
    \item обозначения $\mathscr{X}, P_2(\mathscr{X}) \textrm{ или } P_2, X
        \subset \mathscr{X}, P_2(X), P_2^m(X), X(n), P_2(n), P_2^m(n)$;
    \item таблица значений и столбец значений ФАЛ;
    \item характеристическое множество ФАЛ $f$ и характеристическая функция
        множества $N_f$;
    \item $P_2(1)$ и «основные» ФАЛ из $P_2(2)$, функция голосования;
    \item ассоциативность, коммутативность, дистрибутивность (в т.~ч. $\&$
        относительно $\lor$ и $\oplus$);
    \item тождества приведения подобных (в т.~ч. тождество поглощения);
    \item линейная функция;
    \item множество $\textrm{Б}_0$, буквы, ЭК и ЭД ранга $r$ от БП $X(n)$;
    \item ДНФ, КНФ, совершенные ДНФ и КНФ;
    \item длина ДНФ или КНФ $\mathfrak{A}$ ($\lambda(\mathfrak{A})$);
    \item разложение Шеннона;
    \item геометрическая интерпретация ДНФ и КНФ, а также совершенных ДНФ и КНФ.
\end{compactlist}

\begin{lemms}
    Совершенная ДНФ ФАЛ $f \in P_2(n)$ является единственной ДНФ от БП $X(n)$,
    которая реализует эту ФАЛ $\Leftrightarrow$ когда во множестве $N_f$ нет
    соседних наборов.
\end{lemms}

\begin{cons}
    Совершенные ДНФ ФАЛ $\ell_n$, $\overline \ell_n$ являются единственными ДНФ
    этих ФАЛ от БП $X(n)$.
\end{cons}

\section{Сокращённая ДНФ и способы её построения}

ФАЛ $f'$ \emph{имплицирует} ФАЛ $f''$ $((f' \rightarrow f'') \equiv 1)$, если
$N_{f'} \subseteq N_{f''}$.\\

ФАЛ $f''$ \emph{поглощает} ФАЛ $f'$, если $N_{f'} \subseteq N_{f''}$.\\

ФАЛ $f'$ имплицирует ФАЛ $f'' \Leftrightarrow f'' = f' \lor f''$ или $f' = f'
\cdot f''$.\\

ЭК $K'$ имплицирует ЭК $K'' \Leftrightarrow K' = K'' \cdot K$, где $K$ не имеет
общих букв с $K''$.\\

ЭК $K$ является \emph{импликантой} ФАЛ $f$, если $K$ имплицирует $f$.\\

ДНФ $\mathfrak{A}$ называется \emph{ДНФ без поглощений ЭК}, если ни одна из
граней $N_{K_1}, \ldots, N_{K_s}$ не содержится ни в одной из других граней
покрытия $N_f = N_{K_1} \cup \ldots \cup N_{K_s}$. Или, другими словами, ни
одна ЭК не является импликантой другой ЭК.\\

Импликанта $K$ ФАЛ $f$ называется \emph{простой импликантой} $f$, если она не
поглощается никакой другой отличной от неё импликантой $f$ (т.~е. не
имплицирует никакую другую импликанту $f$). С «геометрической» т.~з. простые
импликанты $f$ соответствуют максимальным по включению граням множества
$N_f$.\\

Дизъюнкция всех простых импликант ФАЛ $f$ называется её \emph{сокращённой
ДНФ}.\\

Сокращённая ДНФ является ДНФ без поглощений.

\begin{theorems}
    Пусть $\mathfrak{A}'$ и $\mathfrak{A}''$ — сокращённые ДНФ ФАЛ $f'$ и $f''$
    соответственно, а ДНФ $\mathfrak{A}$ без поглощений получается из формулы
    $\mathfrak{A}' \cdot \mathfrak{A}''$ в результате раскрытия скобок и
    приведения подобных. Тогда $\mathfrak{A}$ — сокращённая ДНФ ФАЛ $f = f'
    \cdot f''$.
\end{theorems}

\begin{cons}
    Если ДНФ $\mathfrak{A}$ без поглощений получается из КНФ $\mathfrak{B}$ ФАЛ
    $f$ в результате раскрытия скобок и приведения подобных, то $\mathfrak{A}$
    — сокращённая ДНФ ФАЛ $f$.
\end{cons}

Метод Блейка позволяет получить сокращённую ДНФ ФАЛ $f$ из произвольной ДНФ
$f$.\\

ДНФ $\mathfrak{A}'$ называется \emph{расширением} ДНФ $\mathfrak{A}$, если она
получена путём выделения с помощью тождеств ассоциативности и коммутативности
подформул вида $x_iK' \lor \overline x_iK''$, применением к ним \emph{тождества
обобщённого склеивания} ($x_iK' \lor \overline x_iK'' = x_iK' \lor \overline
x_iK'' \lor K'K''$) и последующим приведением подобных.\\

ДНФ $\mathfrak{A}'$ называется \emph{строгим расширением} ДНФ $\mathfrak{A}$,
если она является расширением $\mathfrak{A}$ и содержит ЭК, не являющуюся
импликантой ни одной ЭК из $\mathfrak{A}$.

\begin{theorems}
    ДНФ без поглощений ЭК является сокращённой ДНФ $\Leftrightarrow$ когда она
    не имеет строгих расширений.
\end{theorems}

\begin{cons}
    Из любой ДНФ $\mathfrak{A}$ ФАЛ $f$ можно получить сокращённую ДНФ этой ФАЛ
    в результате построения последовательных строгих расширений и приведения
    подобных до получения ДНФ без поглощений ЭК, не имеющей строгих расширений.
\end{cons}

\section{Тупиковая ДНФ, ядро и ДНФ пересечение тупиковых. ДНФ Квайна, критерий
вхождения простых импликант в тупиковые ДНФ и его локальность.}

ДНФ $\mathfrak{A}$, реализующая ФАЛ $f$, называется \emph{тупиковой ДНФ}, если
$f \neq \mathfrak{A}'$ для любой ДНФ $\mathfrak{A}'$, полученной из
$\mathfrak{A}$ в результате удаления некоторых букв или целых ЭК.\\

В тупиковую ДНФ ФАЛ $f$ могут входить только простые импликанты $f$. Она
является ДНФ без поглощений ЭК. С «геометрической» т.~з. тупиковая ДНФ ФАЛ $f$
задаёт тупиковое покрытие множества $N_f$ максимальными гранями $f$ и обратно.\\

Минимальная ДНФ — ДНФ, имеющая минимальный ранг среди ДНФ реализующих $f$.\\

Кратчайшая ДНФ — ДНФ, имеющая минимальную длину среди ДНФ реализующих $f$.\\

Минимальная ДНФ всегда является тупиковой, среди кратчайших обязательно найдётся тупиковая.\\

Набор $\alpha$ называется \emph{ядровой точкой} ФАЛ $f$, если $\alpha \in N_f$
и $\alpha$ входит только в одну максимальную грань ФАЛ $f$. При этом грань
$N_K$, являющаяся максимальной гранью ФАЛ $f$ и содержащая точку $\alpha$,
называется \emph{ядровой гранью} ФАЛ $f$. Совокупность всех различных ядровых
граней ФАЛ $f$ называется \emph{ядром} ФАЛ $f$.

\begin{lemms}
    ДНФ $\cap T$ ФАЛ $f$ состоит из тех простых импликант ФАЛ $f$, которые
    соответствуют ядровым граням этой ФАЛ $f$.
\end{lemms}

ДНФ $\cap T$ в общем случае не реализует саму ФАЛ $f$ и может быть пустой. ДНФ
$\Sigma T$ всегда реализует ФАЛ $f$.\\

ФАЛ называется \emph{ядровой}, если все её максимальные грани являются
ядровыми.\\

\begin{cons}
    Сокращённая ДНФ ядровой ФАЛ является её единственной тупиковой ДНФ.
\end{cons}

ДНФ, получающаяся из сокращённой ДНФ ФАЛ $f$ удалением тех ЭК $K$, для которых
грань $N_K$ покрывается ядром ФАЛ $f$, но не входит в него, называется
\emph{ДНФ Квайна} этой ФАЛ.\\

ДНФ $\cap T \subseteq$ ДНФ $\Sigma T \subseteq$ ДНФ Квайна $\subseteq$
сокращённая ДНФ.\\

Для $\alpha \in N_f$ обозначим через $\Pi_\alpha(f)$ множество всех проходящих
через $\alpha$ максимальных граней ФАЛ $f$, будем называть его \emph{пучком ФАЛ
$f$ через точку $\alpha$}.\\

Точку $\alpha$ будем называть \emph{регулярной точкой} ФАЛ $f$, если найдётся
точка $\beta \in N_f$, для которой имеет место строгое включение $\Pi_\beta(f)
\subset \Pi_\alpha(f)$.\\

Грань $N_K$ ФАЛ $f$ называется \emph{регулярной гранью} этой ФАЛ, если все
точки $N_K$ регулярны.\\

Любая неядровая точка ядровой грани регулярна. Грань, которая не входит в ядро,
но покрывается им, регулярна.

\begin{theorems}
    Простая импликанта $K$ ФАЛ $f$ входит в ДНФ $\Sigma T \Leftrightarrow$
    когда грань $N_K$ \underline{не} является регулярной гранью этой ФАЛ.
\end{theorems}

Для каждой максимальной грани $\mathcal{N}$ ФАЛ $f$ положим $S_0(\mathcal{N},
f) = \{\mathcal{N}\}$, затем индукцией по $r$ определим \emph{окрестность
порядка $r$ грани $\mathcal{N}$ функции $f$} $S_r(\mathcal{N}, f)$ как множество
всех тех максимальных граней ФАЛ $f$, которые имеют непустое пересечение хотя
бы с одной гранью из $S_{r-1}(\mathcal{N}, f)$.\\

Вопрос о вхождении простой импликанты $K$ в ДНФ $\cap T$ (ДНФ $\Sigma T$) этой
ФАЛ можно решить, рассматривая окрестность $S_1(N_K, f)$ (соответственно
$S_2(N_K, f)$).

\section{Особенности ДНФ линейных и монотонных ФАЛ. Функция покрытия, таблица
Квайна и построение всех тупиковых ДНФ.}

ФАЛ $f$ \emph{линейно зависит от БП} $x_i$ ($x_i$ является \emph{линейной БП}
$f$), если $f(\alpha) \neq f(\beta)$ для любых соседних по $x_i$ наборов
$\alpha$ и $\beta$.\\

Равенство $f(x_1, \ldots, x_n) = x_i \oplus f(x_1, \ldots, x_{i-1}, 0, x_{i+1},
\ldots, x_n)$ равносильно линейности по БП $x_i$ ФАЛ $f$.\\

ФАЛ $f$ является линейной $\Leftrightarrow$ когда она линейно зависит от всех
своих существенных БП.\\

Если ФАЛ $f$ линейно зависит от БП $x_i$, то в любую импликанту этой ФАЛ входит
одна из букв $x_i$, $\overline x_i$.\\

ФАЛ $f$ называется \emph{монотонной}, если $f(\alpha) \leqslant f(\beta)$ для
любых наборов $\alpha$ и $\beta$ таких, что $\alpha \leqslant \beta$.\\

ФАЛ $f$ \emph{монотонно зависит от БП} $x_i$ ($x_i$ является \emph{монотонной
БП} ФАЛ $f$), если $f(\alpha) \leqslant f(\beta)$ для любых соседних по $x_i$
наборов $\alpha$ и $\beta$ таких, что $\alpha \leqslant \beta$.\\

ФАЛ является монотонной $\Leftrightarrow$ когда она монотонно зависит от всех
своих БП.\\

Если ФАЛ $f$ монотонно зависит от БП $x_i$, то ни одна из её простых импликант
не содержит букву $\overline x_i$.\\

Частные случаи монотонной зависимости $f$ от $x_i$: конъюнктивная ($f = x_i
\cdot g$) и дизъюнктивная ($f = x_i \lor g$), где ФАЛ $g$ получается
подстановкой вместо $x_i$ константы 1 или 0 соответственно.\\

При конъюнктивной зависимости буква $x_i$ входит в любую простую импликанту ФАЛ
$f$, в случае дизъюнктивной зависимости буква $x_i$ не входит ни в одну простую
импликанту $f$, отличную от $x_i$.\\

ФАЛ $f(x_1, \ldots, x_n)$ зависит от БП $x_i$ \emph{инмонотонно}
(\emph{инконъюнктивно}, \emph{индизъюнктивно}), если ФАЛ $f(x_1, \ldots,
x_{i-1}, \overline x_i, x_{i+1}, \ldots, x_n)$ зависит от $x_i$ монотонно
(соответственно конъюнктивно, дизъюнктивно).\\

Сопоставим каждому набору $\beta \in B^n$ монотонную ЭК $K_\beta^{+}$,
состоящую только из тех букв $x_j$, для которых $\beta\langle j\rangle = 1$.
Любая монотонная ЭК может быть представлена в таком виде.\\

Набор $\alpha$ называется \emph{нижней единицей} монотонной ФАЛ $f$, если
$\alpha \in N_f$ и $\forall \beta \neq \alpha, \beta \leqslant \alpha$
выполняется $f(\beta) = 0$. Множество всех нижних единиц монотонной ФАЛ $f$
обозначается $N_f^{+}$.

\begin{lemms}
    Сокращённая ДНФ $\mathfrak{A}$ монотонной ФАЛ $f$ является единственной
    тупиковой ДНФ этой ФАЛ и имеет вид
    \[\mathfrak{A} = \bigvee\limits_{\beta \in N_f^{+}} K_\beta^{+}.\]
    При этом все наборы из $N_f^{+}$ являются ядровыми точками ФАЛ $f$.\\
\end{lemms}

\begin{note}
    Можно сказать, что сокращённая ДНФ монотонной ФАЛ состоит из её простых
    импликант, не содержащих отрицаний и соответствующих нижним единицам.
\end{note}

\begin{cons}
    Монотонная ФАЛ является ядровой ФАЛ.
\end{cons}

Пусть $\mathcal{N} = \{\alpha_1, \ldots, \alpha_s\}$ — конечное множество, а
$\mathfrak{N} = \{\mathcal{N}_1, \ldots, \mathcal{N}_p\}$ — система его
подмножеств, образующих покрытие $\mathcal{N}$. Сопоставим паре ($\mathcal{N}$,
$\mathfrak{N}$) матрицу $M \in M^{p,s}$, для которой $M\langle i, j\rangle = 1
\Leftrightarrow \alpha_j \in \mathcal{N}_i$.\\

Считаем, что $i$-я строка соответствует подмножеству $\mathcal{N}_i$ системы
$\mathfrak{N}$, а $j$-й столбец — элементу $\alpha_i$ множества
$\mathcal{N}$.\\

$i$-я строка $M$ \emph{покрывает} её $j$-й столбец, если $M\langle i, j\rangle
= 1$.\\

Система строк с номерами из $I$ образует \emph{покрытие матрицы} $M$, если
каждый её столбец покрывается хотя бы одной строкой с номером из $I$.
Аналогично понимается покрытие одного множества строк $M$ другим множеством
строк.\\

Покрытие матрицы $M$, в котором ни одна строка не покрывается другой строкой
называется \emph{неприводимым}. Покрытие, не имеющее собственных подпокрытий,
называется \emph{тупиковым}.\\

ФАЛ $F(y)$ называется \emph{функцией покрытия} матрицы $M$ без нулевых
столбцов, если $F(\beta) = 1 \Leftrightarrow$ когда система строк матрицы $M$ с
номерами из $I(\beta) = \{i | \beta\langle i \rangle = 1\}$ образует её
покрытие.

\begin{lemms}
    Функция покрытия $F(y_1, \dots, y_p)$ матрицы $M \in B^{p,s}$ без нулевых
    столбцов задаётся КНФ вида
    \[F(y_1, \ldots, y_p) =
    \bigwedge\limits_{j=1}^s\bigr(\bigvee\limits_{\substack{1\leqslant i
    \leqslant p\\ M\langle i,j\rangle = 1}} y_i\bigl).\]
\end{lemms}

\begin{cons}
    В результате раскрытия скобок и приведения пободных из КНФ для $F$ (см.
    лемму) можно получить сокращённую ДНФ ФАЛ $F(y)$, простые импликанты
    которой взаимно однозначно соответствуют тупиковым покрытиям матрицы $M$.
\end{cons}

Задача построения всех тупиковых ДНФ ФАЛ $f$ на основе её сокращённой ДНФ
сводится к рассмотренной выше задаче о покрытии, если $\mathcal{N} = N_f$, а
$\mathfrak{N}$ — система всех максимальных граней $f$.

\section{Градиентный алгоритм и оценка длины градиентного покрытия, лемма о
«протыкающих» наборах. Использование градиентного алгоритма для построения
ДНФ.}

\emph{Градиентный алгоритм} ориентирован на выделение из заданного покрытия
достаточно «коротких» подпокрытий или, иначе, на построение достаточно
«коротких» покрытий для заданной матрицы.\\

Шаг: в матрице выбирается и включается в покрытие такая строка, которая
покрывает наибольшее число ещё не покрытых столбцов (если таких строк
несколько, из них выбирается строка с наименьшим номером).\\

Останов: после того шага, на котором получилось покрытие.

\begin{theorems}
    Пусть для действительного $\gamma$, $0 < \gamma \leqslant 1$, в каждом
    столбце матрицы $M \in M^{p,s}$ имеется не меньше чем $\gamma \cdot p$
    единиц. Тогда покрытие матрицы $M$, получаемое с помощью градиентного
    алгоритма, имеет длину не больше чем $\lceil\frac{1}{\gamma}ln^{+}(\gamma
    s)\rceil + \frac{1}{\gamma}$, где $ln^{+}(x) = 0$ при $0 < x < 1$ и
    $ln^{+}(x) = ln(x)$ при $x \geqslant 1$.
\end{theorems}

Задача о «протыкании» системы $\mathfrak{N}$, состоящей из подмножеств
$\mathcal{N}_1, \ldots, \mathcal{N}_p$ множества $\mathcal{N} = \{\alpha_1,
\ldots, \alpha_s\}$, заключается в нахождении такого подмножества множества
$\mathcal{N}$, в котором $\forall i \in [1, p]$ имеется хотя бы один элемент из
$\mathcal{N}_i$.

\begin{lemms}
    $\forall m,n \in \mathbb{N}$, $m \leqslant n$ в кубе $B^n$ всегда найдётся
    подмножество мощности не более чем $n \cdot 2^m$, протыкающее все грани
    ранга $m$.
\end{lemms}

\section{Задача минимизации ДНФ. Поведение функции Шеннона и оценки типичных
значений для ранга и длины ДНФ.}

На множестве ДНФ задаётся неотрицательный \emph{функционал сложности} $\psi$,
обладающий свойством \emph{монотонности}, т.~е. $\forall \textrm{ДНФ }
\mathfrak{A}\quad \exists \psi(\mathfrak{A}) \geqslant 0: \psi(\mathfrak{A}')
\geqslant \psi(\mathfrak{A}'')$, если ДНФ $\mathfrak{A}''$ получается из ДНФ
$\mathfrak{A}'$ удалением букв или ЭК.\\

Примеры: длина $\lambda(\mathfrak{A})$, ранг $R(\mathfrak{A})$, «формульная»
сложность $L(\mathfrak{A})$.\\

\emph{Задача минимизации ДНФ} относительно функционала сложности $\psi$ состоит
в нахождении для заданной ФАЛ $f$ ДНФ $\mathfrak{A}$, такую что
$\psi(\mathfrak{A}) = \min \psi(\mathfrak{A}')$, где минимум берётся по всем
ДНФ $\mathfrak{A}'$ ФАЛ $f$.\\

При этом ДНФ $\mathfrak{A}$ называется \emph{минимальной относительно
функционала} $\psi$ или \emph{$\psi$-минимальной} ДНФ. Значение
$\psi(\mathfrak{A})$ называется \emph{сложностью ФАЛ $f$ относительно
функционала} $\psi$ или \emph{$\psi$-сложностью ФАЛ} $f$ в классе ДНФ.\\

$\lambda$-минимальную (по длине) ДНФ будем называть \emph{кратчайшей}, а
$R$-минимальную (по рангу) — просто \emph{минимальной}.\\

\emph{Функция Шеннона} для класса ДНФ относительно функционала $\psi$:
\[\psi(n) = \max\limits_{f \in P_2(n)} \psi(f).\]

\begin{lemms}
    $\forall n \in \mathbb{N}$ имеют место соотношения $\lambda(n) = 2^{n-1}$,
    $R(n) = n \cdot 2^{n-1}$.
\end{lemms}

Рассмотрим отрезок $[\psi'(n)$, $\psi''(n)]$, в который попадают значения
$\psi(n)$ для почти всех ФАЛ $f \in P_2(n)$. Если границы $\psi'(n)$ и
$\psi''(n)$ асимптотически равны $\psi(n)$, то говорят, что для параметра
$\psi$ имеет место \emph{эффект Шеннона}.\\

Для параметров $\lambda$ и $R$ эффект Шеннона отсутствует.

\begin{flushleft}
\hbox{%
\vrule\hspace{1em}\parbox{0.95\textwidth}{
    \textbf{Попытка интерпретации стр. 50—51. Вообще, вряд ли это будет в
    теормине на «3».}\\

    Введём дискретную векторную случайную величину $\xi$ состоящую из $2^n$
    случайных величин, принимающих с равной вероятностью значение 0 или 1.
    Введём дискретную случайную величину $\widetilde \xi$, равную сумме
    элементов $\xi$.\\

    Каждая реализация $\xi$ соответствует какой-либо ФАЛ $f$ от $n$ переменных
    (равна её вектору значений). Если зафиксировать реализацию $\xi$ и
    соответствующую ФАЛ $f$, то соответствующая реализация $\widetilde \xi$
    будет равна мощности множества $N_f$ для ФАЛ $f$.\\

    $\mathbb{E} \widetilde \xi = 2^{n-1}$, отступим влево и вправо на $t =
    \lceil n \cdot 2^{n/2} \rceil$, получим интервал $I = (2^{n-1} - t, 2^{n-1}
    + t)$.\\

    Применяем к случайной величине $\widetilde \xi$ неравенство Чебышева и
    устанавливаем, что доля тех ФАЛ $f \in P_2(n)$, для которых $|N_f| \not\in
    I$ стремится к 0 при $n \rightarrow \infty$.\\

    Это означает, что для почти всех ФАЛ $f \in P_2(n)$ выполнено (для проверки
    раскрыть скобки)
    \[|N_f| = 2^{n-1}\bigl(1 \pm O\bigl(n \cdot 2^{-n/2}\bigr)\bigr).\]

    То есть длина совершенной ДНФ у почти всех ФАЛ из $P_2(n)$ асимптотически
    равна $2^{n-1}$.}}
\end{flushleft}

\begin{lemms}
    Для почти всех ФАЛ $f \in P_2(n)$ выполняются неравенства
    \[\lambda(f) \leqslant \frac{3}{4} \cdot 2^{n-1} \bigl(1 + O\bigl(n \cdot
    2^{-n/2}\bigr)\bigr),\]
    \[R(f) \leqslant \frac{3}{4} n \cdot 2^{n-1} \bigl(1 + O\bigl(n \cdot
    2^{-n/2}\bigr)\bigr).\]
\end{lemms}

\section{Алгоритмические трудности минимизации ДНФ и оценки максимальных
значений некоторых связанных с ней параметров. Теорема Ю.~И. Журавлёва о
ДНФ сумма минимальных.}

\emph{Функция Шеннона} для параметра $\psi$ в классе ДНФ: $\psi(n) =
\max\limits_{f \in P_2(n)} \psi(f)$.\\

Обозначим значение функции Шеннона для следующих параметров: число тупиковых
ДНФ — $\tau(n)$, число минимальных ДНФ — $\mu(n)$ и длина сокращённой ДНФ у ФАЛ
из $P_2(n)$ — $\lambda_\textrm{сокр.}(n)$ (ДНФ рассматриваются с точностью до
перестановки ЭК и букв в них).

\begin{lemms}
    Для ФАЛ $f$ из $P_2(n)$, $n \geqslant 4$, вида $f(x_1, \ldots, x_n) =
    g(x_1, x_2, x_3) \cdot (x_4 \oplus \cdots \oplus x_n)$, где $\overline N_g
    = \{(000), (111)\}$, число тупиковых (минимальных) ДНФ равно $5^{2^{n-4}}$
    (соответственно $2^{2^{n-4}}$).
\end{lemms}

\begin{cons}
    $\tau(n) \geqslant 5^{2^{n-4}}$, $\mu(n) \geqslant 2^{2^{n-4}}$.
\end{cons}

Выберем множество номеров $I \subseteq [0, n]$, зафиксируем объединение всех
слоёв куба $B^n$ с номерами из $I$, обозначим характеристичесую функцию этого
объединения как $\mathfrak{s}_n^I$. Числа из $I$ назовём \emph{рабочими
числами} ФАЛ $\mathfrak{s}_n^I$.\\

ФАЛ $\mathfrak{s}_n^I$ является \emph{симметрической}, т.~е. не изменяет своё
значение при любой перестановке аргументов. Наоборот тоже верно: любая
симметрическая ФАЛ совпадает с одной из ФАЛ вида $\mathfrak{s}_n^I$.\\

Симметрическая ФАЛ, отличная от константы, является существенной. Рабочими
числами симметрических ФАЛ $\ell_n$ и $\overline \ell_n$ являются все нечётные
и все чётные числа отрезка $[0, n]$ соответственно.\\

Симметрическая ФАЛ является \emph{поясковой}, если её рабочие числа образуют
отрезок. Вид её сокращённой ДНФ:
\[\mathfrak{s}_n^{[r, p]}(x_1, \ldots, x_n) = \bigvee\limits_{\substack{1
\leqslant i_1 < \cdots < i_{n+r-p} \leqslant n\\\sigma_1 + \cdots +
\sigma_{n+r-p} = r}} x_{i_1}^{\sigma_1} \cdots
x_{i_{n+r-p}}^{\sigma_{n+r-p}}.\]

\begin{lemms}
    $\lambda_\textrm{сокр.}(n) \geqslant e_1 \frac{3^n}{n}$, где $e_1$ —
    некоторая константа.
\end{lemms}

Функция $f(x_1, \ldots, x_n)$ называется \emph{цепной} (\emph{циклической})
\emph{функцией длины $t$}, если её сокращённая ДНФ с «геометрической» т.~з.
представляет собой цепь (соответственно цикл) из $t$ последовательно
соединённых рёбер $\mathcal{N}_1, \ldots, \mathcal{N}_t$ куба $B^n$.

\begin{theorems}
    $\forall n \in \mathbb{N}, n \geqslant 3$, в $P_2(n)$ существуют ФАЛ $f'$ и
    $f''$, имеющие общую простую импликанту $K$, которая входит в ДНФ $\Sigma
    M$ одной, но не входит в ДНФ $\Sigma M$ другой из этих ФАЛ и для которой
    $S_{n-3}(N_K, f') = S_{n-3}(N_K, f'')$.
\end{theorems}

\part*{Недостающее}

\begin{compactlist}
    \item Часть II (вопросы 8—16) в данном файле отсутствует.
    \item Вопрос 16 не должен быть в билетах (только как дополнительный
        вопрос).
\end{compactlist}

\setcounter{part}{2}
\setcounter{section}{16}
\part{Синтез и сложность управляющих систем}

\section{Задача синтеза. Методы синтеза схем на основе ДНФ и связанные с ними
верхние оценки сложности функций.}

Введём обозначения: $\mathscr{U}$ — некоторый полный класс схем (из
рассмотренных во II части), $\Psi \geqslant 0$ — функционал сложности схем
класса $\mathscr{U}$ со свойством монотонности.\\

Сложность системы ФАЛ $F$ относительно функционала $\Psi$ в классе
$\mathscr{U}$: $\Psi(F) = \min\limits_{\Sigma \in \mathscr{U} \textrm{ реализ.
} F} \Psi(\Sigma)$. При этом схема $\Sigma$, реализующая $F$, для которой
$\Psi(\Sigma) = \Psi(F)$, называется \emph{минимальной схемой} в классе
$\mathscr{U}$ относительно $\Psi$.\\

Если функционал $\Psi$ совпадает с $L$, $D$, $R$ (введены во II части), будем
называть его \emph{сложностью}, \emph{глубиной}, \emph{рангом} системы ФАЛ $F$
соответсвенно.\\

\emph{Функция Шеннона} для класса $\mathscr{U}$ относительно функционала
сложности $\Psi$: $\Psi(n) = \max\limits_{f \in P_2(n)} \Psi(f)$.\\

Будем обозначать сложность и функцию Шеннона для некоторого класса $A$ как
$\Psi_\textrm{Б}^A(F)$ и $\Psi_\textrm{Б}^A(n)$ соответственно, будем опускать
нижний индекс $\textrm{Б}$, если $\textrm{Б} = \textrm{Б}_0$.\\

Если $\mathscr{U}' \supseteq \mathscr{U}''$, то $\Psi'(F) \leqslant \Psi''(F)$.
В частности $\Psi_\textrm{Б}^\textrm{С}(F) \leqslant
\Psi_\textrm{Б}^\textrm{Ф}(F)$ и $\Psi_\textrm{Б}^\textrm{К}(F) \leqslant
\Psi_\textrm{Б}^\pi(F)$.\\

Для сложности системы ФАЛ $F = (f_1, \ldots, f_m)$ в любом из рассматриваемых
классов схем выполняется $\max\limits_{1 \leqslant i \leqslant m} L(f_i)
\leqslant L(F) \leqslant \sum\limits_{i=1}^m L(f_i)$.

\begin{lemms}[моделирование совершенной ДНФ]
    $\forall \textrm{ ФАЛ } f(x_1, \ldots, x_n) \not\equiv 0\quad \exists
    \textrm{ формула } \mathscr{F}_f \in \mathscr{U}^\textrm{Ф}$ и $\pi$-схема
    $\Sigma_f \in \mathscr{U}^\pi$, реализующие ФАЛ $f$, для которых
    выполняется \[L(\mathscr{F}_f) \leqslant 2n \cdot |N_f| - 1,\]
    \[L(\Sigma_f) \leqslant n \cdot |N_f|.\]
\end{lemms}

\begin{cons}
    Если учесть, что ФАЛ 0 можно реализовать $\pi$-схемой и формулой из
    $\mathscr{U}^\textrm{Ф}$, имеющими сложность 2, то выполняется
    \[L^\textrm{С}(n) \leqslant L^\textrm{Ф}(n) \leqslant n \cdot 2^{n+1} -
    1,\]
    \[L^\textrm{К}(n) \leqslant L^\pi(n) \leqslant n \cdot 2^n.\]
\end{cons}

\begin{cons}
    $D(n) \leqslant n + \lceil \log_2(n) \rceil + 2$.

    Получается из доказанного в части II соотношения для подобных формул с
    поднятыми отрицаниями $D(\mathscr{\breve F}) \leqslant \lceil
    \log_2(L(\mathscr{F}) + 1) \rceil + Alt(\mathscr{F})$.
\end{cons}

\begin{lemms}[моделирование совершенной ДНФ с использованием КД]
    $\forall \textrm{ ФАЛ } f(x_1, \ldots, x_n) \not\equiv 0\quad \exists
    \textrm{ формула } \mathscr{F}_f \in \mathscr{U}^\textrm{Ф}$ и $\pi$-схема
    $\Sigma_f \in \mathscr{U}^\pi$, реализующие ФАЛ $f$, для которых
    выполняется \[L(\mathscr{F}_f) \leqslant 2^{n+1} + |N_f| - 4,\]
    \[L(\Sigma_f) \leqslant 2^n + |N_f| - 2.\]
\end{lemms}

\begin{cons}
    \[L^\textrm{Ф}(n) \leqslant 3 \cdot 2^n - 4.\]
    \[L^\pi(n) \leqslant 2^{n+1} - 2,\]
\end{cons}

Результатом применения \emph{операции присоединения вершины $v$ к вершине $w$}
называется СФЭ $\Sigma'$, получаемая из СФЭ $\Sigma$ в результате удаления
вершины $v$, переноса начала исходивших из $v$ дуг в $w$ и переноса всех
выходных БП $v$ в $w$.\\

Две вершины СФЭ называются \emph{эквивалентными}, если в них реализуются равные
ФАЛ.\\

Приведённая (т.~е. без висячих вершин) схема называется \emph{строго
приведённой}, если в ней нет эквивалентных вершин. Из любой СФЭ можно получить
эквивалентную ей строго приведённую СФЭ с помощью операции присоединения
эквивалентных вершин и операции удаления висячих вершин.\\

Аналогичным образом определяется операция присоединения вершин в КС, с той лишь
разницей, что на неё не накладываются какие-либо ограничения, связанные с
достижимостью вершин.\\

Для множества ФАЛ $G \subseteq P_2(n)$ через $\overrightarrow G$ будем
обозначать систему, состоящую из различных ФАЛ множества $G$, упорядоченных в
соответствии с номерами их столбцов значений.\\

Обозначения дял некоторых функций порядка $n$:
\begin{compactlist}
    \item $\ell_n$ и $\overline \ell_n$ — линейные ФАЛ;
    \item $\mu_n$ — мультиплексорная ФАЛ;
    \item $\overrightarrow Q_n$ и $\overrightarrow J_n$ — дешифратор и
        дизъюнктивный дешифратор;
    \item $\overrightarrow P_2(n)$ — универсальная система.
\end{compactlist}

\begin{lemms}
    $\forall n \in \mathbb{N} \quad \exists \textrm{ СФЭ } U_n \in
    \mathscr{U}_\textrm{Б}^\textrm{С}$, которая реализует систему ФАЛ
    $\overrightarrow P_2(n)$, сложности $2^{2^n} - n$.
\end{lemms}

\begin{cons}
    $L_\textrm{Б}^\textrm{С}\bigl(\overrightarrow P_2(n)\bigr) \leqslant
    2^{2^n} - n$.
\end{cons}

\section{Нижние оценки сложности ФАЛ, реализация некоторых ФАЛ и минимальность
некоторых схем.}

\begin{lemms}
    Если ФАЛ $f(x_1, \dots, x_n)$ существенно зависит от всех своих БП, то
    \[L^\textrm{С}(f) \geqslant n - 1,\]
    \[L^\textrm{К}(f) \geqslant n.\]
    Если при этом ФАЛ $f$ не является монотонной ФАЛ, то
    \[L^\textrm{С}(f) \geqslant n,\]
    Если есть существенная зависимость от всех своих БП и каждая БП $x_i$, $i
    \in [1, k]$, не является ни монотонной, ни инмонотонной БП ФАЛ $f$, то
    \[L^\textrm{К}(f) \geqslant n + k.\]
\end{lemms}

\begin{cons}
    \[L^\textrm{С}(\ell_n) \geqslant n, \qquad L^\textrm{С}(\mu_n) \geqslant
    2^n + n,\]
    \[L^\textrm{К}(\ell_n) \geqslant 2n, \qquad L^\textrm{К}(\mu_n) \geqslant
    2^n + 2n.\]
\end{cons}

\begin{note}
    Формула $f = \overline{(x_1 \cdots x_n)}$ и $\pi$-схема, моделирующая ЭД $f
    = \overline x_1 \lor \cdots \lor \overline x_n$, являются минимальными в
    классах СФЭ и КС соответственно, при этом $L^\textrm{С}(f) = n$,
    $L^\textrm{К}(f) = n$.
\end{note}

\begin{lemms}
    Для системы $F = (f_1, \ldots, f_m)$, состоящей их попарно различных ФАЛ от
    переменных (от констант), справедливо
    \[L^\textrm{С}(F) \geqslant m \qquad (\textrm{соответственно }
    L^\textrm{К}(F) \geqslant m).\]
\end{lemms}

\begin{cons}
    \[L^\textrm{С}\bigl(\overrightarrow Q_n\bigr) \geqslant 2^n, \qquad
    L^\textrm{С}\bigl(\overrightarrow J_n\bigr) \geqslant 2^n, \qquad
    L^\textrm{С}\bigl(\overrightarrow P_2(n)\bigr) \geqslant 2^{2^n} - n,\]
    \[L^\textrm{К}\bigl(\overrightarrow Q_n\bigr) \geqslant 2^n, \qquad
    L^\textrm{К}\bigl(\overrightarrow J_n\bigr) \geqslant 2^n, \qquad
    L^\textrm{К}\bigl(\overrightarrow P_2(n)\bigr) \geqslant 2^{2^n} - 2.\]
\end{cons}

\begin{lemms}
    $\forall n \in \mathbb{N}$ выполняются неравенства [тут было много верхних
    оценок для $\overrightarrow Q_n$, $\overrightarrow J_n$, $\mu_n$,
    $\ell_n$ и $\overline \ell_n$ в разых классах, но формулировка билета
    не предусматривает верхних оценок.]
\end{lemms}

\begin{cons}
    $L^\textrm{С}(\overrightarrow Q_n) \sim L^\textrm{С}(\overrightarrow J_n)
    \sim 2^n$.
\end{cons}

\begin{lemms}
    Если система ФАЛ $F = (f_1, \ldots, f_m)$ состоит из попарно различных ФАЛ
    от БП $X(n)$, отличных от 0 и 1, то $L^\textrm{К}(F) \geqslant 2^{1-n}
    \sum\limits_{j=1}^m |N_{f_j}|$.
\end{lemms}

\begin{cons}
    $L^\textrm{К}(J_n) \geqslant 2^{n+1} - 2$.
\end{cons}

\begin{note}
    $(1, 4)$-КС с входом $a$ из двух непересекающихся $(a\textrm{—}a)$-цепей
    (т.~е.  циклов) с ЭК проводимости $\overline x_1 x_2 x_1$ и $\overline x_1
    \overline x_2 x_1$ является минимальным дизъюнктивным контактным
    дешифратором порядка 2.
\end{note}

\begin{lemms}
    Если для ФАЛ $f \in P_2(n)$ и $\forall \sigma \in \{0, 1\}$ ФАЛ
    $f_\sigma(x_1, \ldots, x_{n-1}, \sigma) \not\equiv const$, то $L_{\&,
    \lor}^\textrm{С}(f) = \min\{L_{\&, \lor}^\textrm{С}(f_0), L_{\&,
    \lor}^\textrm{С}(f_1)\} + 2$.
\end{lemms}

\begin{cons}
    $L^\textrm{С}(\mu_n) \geqslant 2^{n+1} + n - 1$.
\end{cons}

\begin{note}
    Формула $\overline x_1 y_0 \lor x_1 y_1$ является минимальной СФЭ,
    реализующей ФАЛ $\mu_1$ и $L^\textrm{С}(\mu_1) = 4$.
\end{note}

\begin{cons}
    $D(\mu_n) \geqslant n + 1$.
\end{cons}

\section{Метод каскадов для КС и СФЭ, примеры его применения. Метод Шеннона.}

\emph{Метод каскадов} позволяет строить КС и СФЭ, многократно использующие
«промежуточные результаты».

\begin{lemms}
    $\forall n \in \mathbb{N}$ и $\forall \sigma \in \{0, 1\}$ выполняются
    неравенства
    \[L^\textrm{К}(\ell_n^\sigma) \leqslant 4n - 4 + \left\lfloor \frac{1}{n}
    \right\rfloor,\]
    \[L^\textrm{К}(\overrightarrow P_2(n)) \leqslant 2 \cdot 2^{2^n},\]
    \[L^\textrm{К}(\overrightarrow J_n) \leqslant 2^{n+2} - 6.\]
\end{lemms}

\emph{Метод Шеннона} позволяет строить КС и СФЭ и установить порядок роста
функций Шеннона $L^\textrm{С}(n)$ и $L^\textrm{К}(n)$.\\

Метод Шеннона основан на разложении Шеннона по $q$ переменным. При этом мы
раскладываем функцию на подфункции от $q$ переменных, которые в разложении
домножаются на функции вида $x_{q+1}^{\sigma_{q+1}} \cdots x_n^{\sigma_n}$ от
$(n - q)$ переменных. Все указанные подфункции от $q$ переменных мы реализуем с
помощью универсального многополюсника порядка $q$ (т.~е. схемы, которая
реализует все функции от $q$ переменных). Потом присоединяем к выходам
универсального многополюсника, к $q$ информационным входам мультиплексора
порядка $(n-q)$, т.~е. у него $(n-q)$ адресных переменных, с помощью которых
«адресуются» конкретные функции, реализуемые универсальным многополюсником.\\

Полагаем $q = \left\lfloor \log_2(n - 2\log_2 n) \right\rfloor$.

\begin{theorems}
    Для функций Шеннона в классах СФЭ и КС выполяется:
    \[L^\textrm{С}(n) \lesssim 8 \frac{2^n}{n},\]
    \[L^\textrm{К}(n) \lesssim 4 \frac{2^n}{n}.\]
\end{theorems}

\section{Нижние мощностные оценки функций Шеннона}

\emph{Мощностной метод Шеннона} основан на том, что число ФАЛ от БП $x_1,
\ldots, x_n$ не меньше числа попарно неэквивалентных схем, сложность которых не
превосходит соответствующего значения функции Шеннона от $n$.\\

Обозначим через $\mathscr{U}(\Psi, n)$ множество тех схем $\Sigma \in
\mathscr{U}$, которые реализуют одну ФАЛ $f$ из $P_2(n)$ и для которых
$\Psi(\Sigma) \leqslant \Psi(f)$.\\

Имеет место «мощностное» равенство $\left|\left|\mathscr{U}(\Psi(n),
n)\right|\right| = 2^{2^n}$.\\

Верхние оценки, установленные ранее (в части II):
\[\left\| \mathscr{U}^\textrm{С}(L, n)\right\| \leqslant \left(8 \left(L +
n\right)\right)^{L+1},\]
\[\left\| \mathscr{U}^\textrm{Ф}(L, n)\right\| \leqslant
\left(8n\right)^{L+1},\]
\[\left\| \mathscr{U}^\textrm{К}(L, n)\right\| \leqslant \left(8nL\right)^L,\]
\[\left\| \mathscr{U}^\pi(L, n)\right\| \leqslant \left(12n\right)^L,\]
\[\left\| \mathscr{U}^\textrm{Ф}[D, n]\right\| \leqslant
\left(8n\right)^{2^D}.\]

\begin{lemms}
    $\forall a, y, q \in \mathbb{R}^{+} (\geqslant 0): a\log q > 1, (ay)^y
    \geqslant q \Rightarrow$
    \[y \geqslant \frac{\log q}{\log(a\log q)}\left(1 + \frac{\log\log(a\log
    q)}{\log(ae\log q)}\right),\]
    где $e$ — основание натурального логарифма.\\

    $\forall a, y, q \in \mathbb{R}^{+} (\geqslant 0): a > 1, a^y \geqslant q
    \Rightarrow$
    \[y \geqslant \frac{\log q}{\log a}.\]
\end{lemms}

\begin{theorems}
    Для некоторых последовательностей $\varepsilon_i = \varepsilon_i(n)$, где
    $i = \overline{1,5}$ и $n \in \mathbb{N}: (\varepsilon_i(n) \geqslant 0
    \textrm{ при } n \geqslant n_0), (\varepsilon_i(n) \to 0 \textrm{ при } n
    \to \infty)$ для почти всех ФАЛ $f \in P_2(n)$ выполняются неравенства
    \[L^\textrm{С}(f) \geqslant (1 + \varepsilon_1(n))\frac{2^n}{n},\]
    \[L^\textrm{Ф}(f) \geqslant (1 - \varepsilon_2(n))\frac{2^n}{\log n},\]
    \[L^\textrm{К}(f) \geqslant (1 - \varepsilon_3(n))\frac{2^n}{n},\]
    \[L^\pi(f) \geqslant (1 - \varepsilon_4(n))\frac{2^n}{\log n},\]
    \[D(f) \geqslant n - \log\log n - \varepsilon_5(n).\]
\end{theorems}

\begin{cons}
    \[L^\textrm{С}(n) \gtrsim \frac{2^n}{n},\]
    \[L^\textrm{Ф}(n) \gtrsim \frac{2^n}{\log n},\]
    \[L^\textrm{К}(n) \gtrsim \frac{2^n}{n},\]
    \[L^\pi(n) \gtrsim \frac{2^n}{\log n}.\]
\end{cons}

\section{Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучший
метод О.~Б. Лупанова для синтеза СФЭ в базисе $\textrm{Б}_0$.}

\emph{Метод О.~Б. Лупанова} позволяет строить СФЭ и установать асимптотику
функции Шеннона $L^\textrm{С}(n)$.\\

Множество ФАЛ $G \in P_2(m)$ называется \emph{дизъюнктивно-универсальным
множеством} (\emph{ДУМ}) порядка $m$ и ранга $p$, если любая ФАЛ $g \in P_2(m)$
м.~б. представлена в виде $g = g_1 \lor \cdots \lor g_p$, где $g_i \in G$.\\

Метод О.~Б. Лупанова также основан на разложении Шеннона по $q$ переменным и
также использует мультиплексор порядка $(n - q)$. Но подфункции от $q$
переменных из разложения реализуются \underline{не} универсальным
многополюсником, а как дизъюнкция функций из ДУМ порядка $q$.\\

%Стандартный способ построения ДУМ связан с разбиениями единичного куба. Пусть
%$\Pi = (\pi_1, \ldots \pi_p)$ — разбиение куба $B^n$, $\Psi = (\psi_1, \ldots,
%\psi_p)$ — множество характеристических ФАЛ элементов разбиения, $\psi_i$
%соответствует $\pi_i$

TODO: построение ДУМ, связанные определения, методичка III часть, стр. 35.

\begin{lemms}
    $\forall m, s \in \mathbb{N}$ и $p = \left\lceil \frac{2^m}{s}
    \right\rceil$ существует стандартное ДУМ порядка $m$ и высоты $s$, которое
    является ДУМ ранга $p$ и для которого:
    \begin{enumerate}
    \item $\lambda = \left|G\right| \leqslant p \cdot 2^s$;
    \item система из $p$ характеристических ФАЛ $\psi_1, \ldots, \psi_p$ ДУМ
        $G$ обладает тем свойством, что $\forall \textrm{ ФАЛ } g \in P_2(m)$ и
        соответствующих ФАЛ $g_1, \ldots, g_p$ из $G$ справедливо не только
        представление $g = g_1 \lor \cdots \lor g_p$, но и $g = \psi_1 g_1 \lor
        \cdots \lor \psi_p g_p$.
    \end{enumerate}
\end{lemms}

\begin{theorems}
    $\forall \textrm{ ФАЛ } f \in P_2(n) \quad \exists \textrm{ СФЭ } \Sigma_f
    \in \mathscr{U}^\textrm{С}$, реализующая $f$ и такая, что
    \[L(\Sigma_f) \leqslant \frac{2^n}{n} \left(1 + \frac{5\log n + O(1)}{n}
    \right).\]
\end{theorems}

\begin{cons}
    $L^\textrm{С} \sim \frac{2^n}{n}$.
\end{cons}

В классе СФЭ, в отличии от класса ДНФ, имеет место эффект Шеннона, т.~к.
сложность $L^\textrm{С}(f) \in P_2(n)$ для почти всех ФАЛ $f \in P_2(n)$
асимптотически равна функции Шеннона $L^\textrm{С}(n)$, то есть сложности самой
сложной ФАЛ из $P_2(n)$.

\part*{Недостающее}

\begin{compactlist}
    \item Вопросы 22—26 в данном файле отсутствуют.
    \item Вопросы 25—26 не должны быть в билетах (только как дополнительные
        вопросы).
    \item Частей IV и V (вопросы 27—30) в данном файле нет.
    \item Часть V (вопросы 29—30) не должна быть в билетах (только как
        дополнительные вопросы).
\end{compactlist}

\end{document}
