Обсуждение участника:Sancho20021 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема о нижней оценке на число элементов в схеме)
(Теорема о нижней оценке на число элементов в схеме)
Строка 8: Строка 8:
 
<tex>F_g = \{\text{Булевы функции, } size \leq g(n)\}</tex>
 
<tex>F_g = \{\text{Булевы функции, } size \leq g(n)\}</tex>
 
Тогда <tex>\frac{|F_g|}{2^{2^n}} \longrightarrow 0</tex>
 
Тогда <tex>\frac{|F_g|}{2^{2^n}} \longrightarrow 0</tex>
|proof=
+
}}
Алабудай балабулабудай. тудудум.
+
Для доказательства этой теоремы нам понадобится доказать несколько вспомогательных утверждений.
 +
{{Определение
 +
|definition=
 +
'''Линейная программа''' {{---}} список строк вида <tex>(a, (i_1, \ldots, i_k))</tex>, где <tex>a \in B</tex> (базис), <tex>a: \mathbb B^k \rightarrow \mathbb B</tex>, <tex>i_j</tex> {{---}} индексы переменных.
 +
}}
 +
'''Пример линейной программы'''
 +
 
 +
Линейная программа для функции <tex>x_1 \oplus x_2</tex> над базисом <tex>\{ \land, \lor, \lnot \}</tex>
 +
 
 +
<tex>y_1 = \lnot x_1</tex>
 +
 
 +
<tex>y_2 = \lnot x_2</tex>
 +
 
 +
<tex>y_3 = x_1 \land y_2</tex>
 +
 
 +
<tex>y_4 = x_2 \land y_1</tex>
 +
 
 +
<tex>y_5 = y_3 \lor y_4</tex>
 +
 
 +
'''Длина''' линейной программы {{---}} количество строк.
 +
{{Теорема
 +
|statement= Для булевой функции <tex>f \; \exists</tex> линейная программа длины <tex>r \Leftrightarrow \exists </tex> схема, использующая <tex>r</tex> функциональных элементов.
 +
|proof=Чтобы построить по схеме программу, можно занумеровать элементы схемы в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки#Топологическая_сортировка|топологической сортировки]], и для каждого элемента <tex>m</tex> с функцией <tex>a</tex> и входами <tex>i_1, \ldots, i_k</tex> сопоставить строчку линейной программы с номером <tex>m</tex> вида <tex>(a, (i_1, \ldots, i_k))</tex>.
 +
 
 +
Построение функциональной схемы по линейной программе очевидно.
 
}}
 
}}

Версия 19:24, 7 июня 2020

Теорема о нижней оценке на число элементов в схеме

Теорема:
Большинство булевых функций требуют для реализации порядка [math]\Omega(\frac{2^n}{n})[/math] функциональных элементов, где [math]n[/math] — количество аргументов функции.

Формальная запись теоремы: [math]f(n) = \frac{2^n}{n} \; \; \; g(n): \frac{g}{f} \longrightarrow 0[/math]

[math]F_g = \{\text{Булевы функции, } size \leq g(n)\}[/math]

Тогда [math]\frac{|F_g|}{2^{2^n}} \longrightarrow 0[/math]

Для доказательства этой теоремы нам понадобится доказать несколько вспомогательных утверждений.

Определение:
Линейная программа — список строк вида [math](a, (i_1, \ldots, i_k))[/math], где [math]a \in B[/math] (базис), [math]a: \mathbb B^k \rightarrow \mathbb B[/math], [math]i_j[/math] — индексы переменных.

Пример линейной программы

Линейная программа для функции [math]x_1 \oplus x_2[/math] над базисом [math]\{ \land, \lor, \lnot \}[/math]

[math]y_1 = \lnot x_1[/math]

[math]y_2 = \lnot x_2[/math]

[math]y_3 = x_1 \land y_2[/math]

[math]y_4 = x_2 \land y_1[/math]

[math]y_5 = y_3 \lor y_4[/math]

Длина линейной программы — количество строк.

Теорема:
Для булевой функции [math]f \; \exists[/math] линейная программа длины [math]r \Leftrightarrow \exists [/math] схема, использующая [math]r[/math] функциональных элементов.
Доказательство:
[math]\triangleright[/math]

Чтобы построить по схеме программу, можно занумеровать элементы схемы в порядке топологической сортировки, и для каждого элемента [math]m[/math] с функцией [math]a[/math] и входами [math]i_1, \ldots, i_k[/math] сопоставить строчку линейной программы с номером [math]m[/math] вида [math](a, (i_1, \ldots, i_k))[/math].

Построение функциональной схемы по линейной программе очевидно.
[math]\triangleleft[/math]