Викиконспекты - Вклад участника [ru]

Лемма о дедукции, полнота исчисления высказываний

2016-09-08T16:48:05Z

5.18.154.236: /* Теорема о дедукции */

[[Категория: Математическая логика]]

[[Лекция 2 | <<]][[Лекция 4 | >>]]

==Теорема о дедукции==

Будем обозначать буквами <tex>\Gamma, \Delta, \Sigma</tex> списки формул (возможно, пустые).

{{Определение
|definition=
Пусть <tex>\Gamma</tex> - некоторый список высказываний, <tex>\alpha</tex> - некоторое высказывание в исчислении <tex>\langle L, A, R \rangle</tex>. Тогда будем говорить, что <tex>\alpha</tex> '''выводится''' из <tex>\Gamma</tex> (запись: <tex>\Gamma \vdash \alpha</tex>), если существует доказательство <tex>\alpha</tex> в исчислении <tex>\langle L, A_1, R \rangle</tex>, где <tex>A_1</tex> - это <tex>A</tex> с добавленными формулами из <tex>\Gamma</tex>. Элементы <tex>\Gamma</tex> называются допущениями, предположениями, или гипотезами.
}}

Замечание: в этом определении появляются дополнительные предположения, поэтому речь идет именно о ''выводе'', а не о ''доказательстве''. Очевидно, что, если <tex>\Gamma = \varnothing</tex>, то <tex>\Gamma \vdash \alpha</tex> соответствует <tex>\vdash \alpha</tex>.

{{Теорема
|statement=
Пусть справедливо <tex>\Gamma \vdash \alpha \rightarrow \beta</tex>. Тогда справедливо <tex>\Gamma \cup \{\alpha\} \vdash \beta</tex>
|proof=
Возьмем <tex>\delta_1, ..., \delta_m</tex> --- вывод формулы <tex>\alpha \rightarrow \beta</tex>. В ней <tex>\delta_m = \alpha \rightarrow \beta</tex>. Добавим <tex>\delta_{m+1} = \alpha</tex> --- это добавленная аксиома, и <tex>\delta_{m+2} = \beta</tex>, получим вывод <tex>\beta</tex> как М.Р. <tex>\delta_m</tex> и <tex>\delta_{m+1}</tex>.
}}

{{Лемма
|statement=
<tex>\vdash \alpha \rightarrow \alpha</tex>
|proof=
#<tex>\alpha \rightarrow (\alpha \rightarrow \alpha)</tex> (Сх. акс. 1)
#<tex>(\alpha \rightarrow (\alpha \rightarrow \alpha)) \rightarrow (\alpha \rightarrow ((\alpha \rightarrow \alpha) \rightarrow \alpha)) \rightarrow (\alpha \rightarrow \alpha)</tex> (Сх. акс. 2)
#<tex>(\alpha \rightarrow ((\alpha \rightarrow \alpha) \rightarrow \alpha)) \rightarrow (\alpha \rightarrow \alpha)</tex> (М.Р. 1, 2)
#<tex>(\alpha \rightarrow ((\alpha \rightarrow \alpha) \rightarrow \alpha))</tex> (Сх. акс. 1)
#<tex>\alpha \rightarrow \alpha</tex> (М.Р. 4, 3)
}}

{{Теорема
|about= о дедукции
|statement=
Пусть справедливо <tex>\Gamma \cup \{\alpha\} \vdash \beta</tex>. Тогда справедливо <tex>\Gamma \vdash \alpha \rightarrow \beta</tex>.
|proof=
Имеется вывод <tex>\delta_1, ..., \delta_{m-1}, \beta</tex>. Набросаем план вывода, формулы в нем занумеруем через 10 ('''<s>Ну да, логика же</s>'''):

<tex>(10)</tex> <tex>\Gamma \vdash \alpha \rightarrow \delta_1</tex>

...

<tex>(10m - 10)</tex> <tex>\Gamma \vdash \alpha \rightarrow \delta_{m-1}</tex>

<tex>(10m)</tex> <tex>\Gamma \vdash \alpha \rightarrow \beta</tex>

Дополним план до полноценного вывода. Рассмотрим формулу номер <tex>i</tex>. Возможны следующие варианты:
# <tex>\delta_i</tex> --- аксиома или предположение, входящее в <tex>\Gamma</tex>. Тогда вставим перед этой формулой <tex>\delta_i</tex> и <tex>\delta_i \rightarrow (\alpha \rightarrow \delta_i)</tex>, формула верна по M.P.
# <tex>\delta_i = \alpha</tex>. Тогда вставляем перед формулой 4 формулы из леммы.
# <tex>\delta_i</tex> выводится по M.P. из <tex>\delta_j</tex> и <tex>\delta_k</tex>, где <tex>j, k < i</tex>. Выведем <tex>\alpha \rightarrow \delta_i</tex>, добавив <tex>(\alpha \rightarrow \delta_j) \rightarrow ((\alpha \rightarrow (\delta_j \rightarrow \delta_i)) \rightarrow (\alpha \rightarrow \delta_i))</tex> (сх. акс. 2) и <tex>(\alpha \rightarrow (\delta_j \rightarrow \delta_i)) \rightarrow (\alpha \rightarrow \delta_i)</tex> (M.P. из <tex>j</tex> и предыдущей)
}}

{{Определение
|definition=
Высказывание <tex>\alpha</tex> следует из высказываний <tex>\Gamma</tex>, если при любой оценке пропозициональных переменных, входящих в высказывания, на которых все высказывания из <tex>\Gamma</tex> истинны, <tex>\alpha</tex> также истинно. Запись: <tex>\Gamma \models \alpha</tex>.
}}

==Теорема о полноте исчисления высказываний==

{{Лемма
|statement=
Если <tex>\Gamma \vdash \alpha</tex>, то <tex>\Gamma, \gamma \vdash \alpha</tex>. Если <tex>\Gamma_1, \Gamma_2 \vdash \alpha</tex>, то <tex>\Gamma_2, \Gamma_1 \vdash \alpha</tex>. Аналогично для следствия.
|proof=

'''КТО МОЖЕТ НАПИСАТЬ ЭТО ФОРМАЛЬНО?'''
}}

Лемма о дедукции, полнота исчисления высказываний

2016-09-08T16:46:04Z

5.18.154.236: /* Теорема о дедукции */ убрана возможно лишняя скобка в третьем пункте док-ва

[[Категория: Математическая логика]]

[[Лекция 2 | <<]][[Лекция 4 | >>]]

==Теорема о дедукции==

Будем обозначать буквами <tex>\Gamma, \Delta, \Sigma</tex> списки формул (возможно, пустые).

{{Определение
|definition=
Пусть <tex>\Gamma</tex> - некоторый список высказываний, <tex>\alpha</tex> - некоторое высказывание в исчислении <tex>\langle L, A, R \rangle</tex>. Тогда будем говорить, что <tex>\alpha</tex> '''выводится''' из <tex>\Gamma</tex> (запись: <tex>\Gamma \vdash \alpha</tex>), если существует доказательство <tex>\alpha</tex> в исчислении <tex>\langle L, A_1, R \rangle</tex>, где <tex>A_1</tex> - это <tex>A</tex> с добавленными формулами из <tex>\Gamma</tex>. Элементы <tex>\Gamma</tex> называются допущениями, предположениями, или гипотезами.
}}

Замечание: в этом определении появляются дополнительные предположения, поэтому речь идет именно о ''выводе'', а не о ''доказательстве''. Очевидно, что, если <tex>\Gamma = \varnothing</tex>, то <tex>\Gamma \vdash \alpha</tex> соответствует <tex>\vdash \alpha</tex>.

{{Теорема
|statement=
Пусть справедливо <tex>\Gamma \vdash \alpha \rightarrow \beta</tex>. Тогда справедливо <tex>\Gamma \cup \{\alpha\} \vdash \beta</tex>
|proof=
Возьмем <tex>\delta_1, ..., \delta_m</tex> --- вывод формулы <tex>\alpha \rightarrow \beta</tex>. В ней <tex>\delta_m = \alpha \rightarrow \beta</tex>. Добавим <tex>\delta_{m+1} = \alpha</tex> --- это добавленная аксиома, и <tex>\delta_{m+2} = \beta</tex>, получим вывод <tex>\beta</tex> как М.Р. <tex>\delta_m</tex> и <tex>\delta_{m+1}</tex>.
}}

{{Лемма
|statement=
<tex>\vdash \alpha \rightarrow \alpha</tex>
|proof=
#<tex>\alpha \rightarrow (\alpha \rightarrow \alpha)</tex> (Сх. акс. 1)
#<tex>(\alpha \rightarrow (\alpha \rightarrow \alpha)) \rightarrow (\alpha \rightarrow ((\alpha \rightarrow \alpha) \rightarrow \alpha)) \rightarrow (\alpha \rightarrow \alpha)</tex> (Сх. акс. 2)
#<tex>(\alpha \rightarrow ((\alpha \rightarrow \alpha) \rightarrow \alpha)) \rightarrow (\alpha \rightarrow \alpha)</tex> (М.Р. 1, 2)
#<tex>(\alpha \rightarrow ((\alpha \rightarrow \alpha) \rightarrow \alpha))</tex> (Сх. акс. 1)
#<tex>\alpha \rightarrow \alpha</tex> (М.Р. 4, 3)
}}

{{Теорема
|about= о дедукции
|statement=
Пусть справедливо <tex>\Gamma \cup \{\alpha\} \vdash \beta</tex>. Тогда справедливо <tex>\Gamma \vdash \alpha \rightarrow \beta</tex>.
|proof=
Имеется вывод <tex>\delta_1, ..., \delta_{m-1}, \beta</tex>. Набросаем план вывода, формулы в нем занумеруем через 10 ('''<s>Ну да, логика же</s>'''):

<tex>(10)</tex> <tex>\Gamma \vdash \alpha \rightarrow \delta_1</tex>

...

<tex>(10m - 10)</tex> <tex>\Gamma \vdash \alpha \rightarrow \delta_{m-1}</tex>

<tex>(10m)</tex> <tex>\Gamma \vdash \alpha \rightarrow \beta</tex>

Дополним план до полноценного вывода. Рассмотрим формулу номер <tex>i</tex>. Возможны следующие варианты:
# <tex>\delta_i</tex> --- аксиома или предположение, входящее в <tex>\Gamma</tex>. Тогда вставим перед этой формулой <tex>\delta_i</tex> и <tex>\delta_i \rightarrow (\alpha \rightarrow \delta_i)</tex>, формула верна по M.P.
# <tex>\delta_i = \alpha</tex>. Тогда вставляем перед формулой 4 формулы из леммы.
# <tex>\delta_i</tex> выводится по M.P. из <tex>\delta_j</tex> и <tex>\delta_k</tex>, где <tex>j, k < i</tex>. Выведем <tex>\alpha \rightarrow \delta_i</tex>, добавив <tex>(\alpha \rightarrow \delta_j) \rightarrow ((\alpha \rightarrow (\delta_j \rightarrow \delta_i)) \rightarrow (\alpha \rightarrow \delta_i))</tex> (сх. акс. 2) и <tex>((\alpha \rightarrow (\delta_j \rightarrow \delta_i)) \rightarrow (\alpha \rightarrow \delta_i)</tex> (M.P. из <tex>j</tex> и предыдущей)
}}

{{Определение
|definition=
Высказывание <tex>\alpha</tex> следует из высказываний <tex>\Gamma</tex>, если при любой оценке пропозициональных переменных, входящих в высказывания, на которых все высказывания из <tex>\Gamma</tex> истинны, <tex>\alpha</tex> также истинно. Запись: <tex>\Gamma \models \alpha</tex>.
}}

==Теорема о полноте исчисления высказываний==

{{Лемма
|statement=
Если <tex>\Gamma \vdash \alpha</tex>, то <tex>\Gamma, \gamma \vdash \alpha</tex>. Если <tex>\Gamma_1, \Gamma_2 \vdash \alpha</tex>, то <tex>\Gamma_2, \Gamma_1 \vdash \alpha</tex>. Аналогично для следствия.
|proof=

'''КТО МОЖЕТ НАПИСАТЬ ЭТО ФОРМАЛЬНО?'''
}}

Основные определения теории графов

2016-06-28T12:44:15Z

5.18.154.236: /* Пути в графах */ опечатка

==Ориентированные графы==

{{Определение
|id = oriented_grath
|definition =
'''Ориентированным графом''' (англ. ''directed graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (англ. ''vertices''), а <tex> E \subset V \times V </tex> {{---}} множество рёбер.
}}

{{Определение
|definition =
'''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
}}

{{Определение
|id = def_graph_edge_1
|definition =
'''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

{{Определение
|definition=
'''Изоморфные графы''' (англ. ''isomorphic graphs'') {{---}} два графа <tex>A</tex> и <tex>B</tex> называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v, v)</tex>, называется петлей (англ. ''loop'').

Два ребра, имеющие общую концевую вершину, то есть <tex>e_1=(v, u_1)</tex> и <tex>e_2=(v, u_2)</tex>, называются '''смежными''' (англ. ''adjacent'').

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''.
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.

'''Инцидентность''' (англ. ''incidence'') {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex>-графом. <tex> (1, 0) </tex>-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.
{{Определение
|id = def1
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, \operatorname{beg}, \operatorname{end})</tex> , где <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, а <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V</tex>.
}}
Данное определение разрешает соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Граф с кратными рёбрами принято называть '''мультиграфом''' (англ. ''multigraph''). Если в мультиграфе присутствуют петли, то такой граф называют '''псевдографом''' (англ. ''pseudograph'').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Graph_definition_1.png|thumb|210px|center|Красным выделено кратное ребро (6, 2) Синим обозначена петля (6, 6)]]
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]
|
|}

{{Определение
|definition=
Для ориентированных графов определяют '''полустепень исхода вершины''' (англ. ''outdegree'') <tex>\operatorname{deg}^+v_i = |\{e \mid \operatorname{beg(e)} = v_i\}|</tex> и '''полустепень захода вершины''' (англ. ''indegree'') <tex>\operatorname{deg}^-v_i = |\{e \mid \operatorname{end(e)} = v_i\}|</tex>.
}}

Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].

==Неориентированные графы==
{{Определение
|id = def_undirected_graph_1
|definition =
'''Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.
}}
{{Определение
|definition =
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
}}
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф ]]
Иное определение:
{{Определение
|id = def_undirected_graph_2
|definition =
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, \operatorname{ends})</tex> , где <tex>V</tex> {{---}} множество вершин, <tex>E</tex> {{---}} множество ребер, а <tex>\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}</tex>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными ребрами.
}}

{{Определение
|id = def_simple_graph
|definition =
'''Простым графом''' <tex>G</tex> называется граф, в котором нет петель и кратных ребер.
}}

{{Определение
|id = def_graph_degree_1
|definition =
'''Степенью''' (англ. ''degree'', ''valency'') вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>.
}}
Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

== Представление графов ==

=== Матрица и списки смежности ===

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены параллельные ребра).
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.

Если граф '''разрежен''' (англ. ''sparse graph''), <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному, его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, так как не придется хранить много нулей.

=== Пути в графах ===
{{Определение
|id = path
|definition =
'''Путём''' (маршрутом,англ. ''path'') в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i), k</tex> {{---}} '''длина''' (англ. ''length'') пути.
}}

{{Определение
|definition=
'''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}

{{Определение
|definition =
'''Циклическим путём''' (англ. ''closed walk'') в ''ориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>.
}}

{{Определение
|id = def_no_graph_path
|definition =
'''Циклическим путём''' в ''неориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>, а также <tex> e_i \ne e_{i \bmod k + 1}</tex>.
}}

{{Определение
|id = def_graph_cycle_1
|definition =
'''Цикл''' (англ. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \bmod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}

{{Определение
|definition=
'''Простой (вершинно-простой) путь''' (англ. ''simple path'') {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
}}

== Часто используемые графы ==
{{Определение
|definition=
'''Полный граф''' (англ. ''complete graph'') {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex> рёбер и обозначается <tex>K_n</tex>.
}}

{{Определение
|definition=
'''Двудольный граф''' или '''биграф''' (англ. ''bipartite graph'') {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.
}}

{{Определение
|definition=
'''Регулярный граф''' (англ. ''regular graph'') {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.
}}

{{main|Дерево, эквивалентные определения}}
{{Определение
|definition='''Дерево''' (англ. ''tree'') {{---}} связный ациклический граф.
}}

{{main|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов}}
{{Определение
|definition=
Граф называется '''эйлеровым''' (англ. ''eulerian graph''), если он содержит эйлеров цикл.
}}

{{main|Гамильтоновы графы}}
{{Определение
|definition=
Граф называется '''гамильтоновым''' (англ. ''hamiltonian graph''), если он содержит гамильтонов цикл.
}}

{{main|Укладка графа на плоскости}}
{{Определение
|definition=
Граф называется '''планарным''' (англ. ''planar graph''), если он обладает укладкой на плоскости. '''Плоским''' (англ. ''plane graph'', ''planar embedding of the graph'') называется граф уже уложенный на плоскости.
}}

{{main|Лемма о безопасном ребре}}
{{Определение
|definition=
'''Остовное дерево''' (англ. ''spanning tree'') {{---}} ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.
}}

==См. также==
* [[Лемма о рукопожатиях]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Источники информации==
* [[wikipedia:ru:Граф_(математика) | Википедия {{---}} Граф]]
* [[wikipedia:Graph_(mathematics) | Wikipedia {{---}} Graph]]
* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]

Получение следующего объекта

2016-04-21T19:18:08Z

5.18.154.236: /* Специализация алгоритма для генерации следующей перестановки */ исправление опечатки в алгоритме

== Алгоритм ==
{{Определение|definition= '''Получение следующего объекта''' {{---}} это нахождение объекта, следующего за данным в [[Лексикографический порядок|лексикографическом порядке]].
}}
Объект <tex>Q</tex> называется следующим за <tex>P</tex>, если <tex>P < Q</tex> и не найдется такого <tex>R</tex>, что <tex>P < R < Q</tex>.

Отсюда понятен алгоритм:
* находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта <tex>P</tex>,
* к оставшейся части дописываем минимальный возможный элемент (чтобы было выполнено правило <tex>P < Q</tex>),
* дописываем минимальный возможный хвост.
По построению получаем, что <tex>Q</tex> {{---}} минимально возможный.

== Специализация алгоритма для генерации следующего битового вектора ==
* Находим минимальный суффикс, в котором есть <tex>0</tex>, его можно увеличить, не меняя оставшейся части
* Вместо <tex>0</tex> записываем <tex>1</tex>
* Дописываем минимально возможный хвост из нулей
'''int[]''' nextVector('''int[]''' a): // <tex>n</tex> {{---}} длина вектора
'''while''' (n >= 0) '''and''' (a[n] != 0)
a[n] = 0
n--
'''if''' n == -1
'''return''' ''null''
a[n] = 1
'''return''' a
Приведённый алгоритм эквивалентен прибавлению единицы к битовому вектору.
=== Пример работы ===
{| class="wikitable" border = 1
|0||1||0||1||style="background:#FFCC00"|1||исходный битовый вектор
|-
| || || || ||^|| начинаем идти с конца
|-
|0||1||0||style="background:#FFCC00"|0||style="background:#FFCC00"|0|| пока элементы равны 1, заменяем их на 0
|-
|0||1||style="background:#FFCC00"|1||0||0|| меняем первый не удовлетворяющий условию цикла элемент на 1
|-
|'''0'''||'''1'''||'''1'''||'''0'''||'''0'''||следующий битовый вектор
|}

== Специализация алгоритма для генерации следующей перестановки ==
* Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример)
* Меняем его с минимальным элементом, большим нашего, стоящим правее
* Перевернем правую часть

'''int[]''' nextPermutation('''int[]''' a): // <tex>n</tex> {{---}} длина перестановки
'''for''' i = n - 2 '''downto''' 0
'''if''' a[i] < a[i + 1]
min = i
'''for''' j = i + 1 '''to''' n - 1
'''if''' (a[j] < a[min]) '''and''' (a[j] > a[i])
min = j
swap(a[i], a[min])
reverse(a, i + 1, n - 1)
'''return''' a
'''return''' ''null''

=== Пример работы ===
{| class="wikitable" border = 1
|1||3||style="background:#FFCC00"|2||5||style="background:#FFCC00"|4||исходная перестановка
|-
| || ||^|| || ||находим элемент, нарушающий убывающую последовательность
|-
| || || || ||^||минимальный элемент больше нашего
|-
|1||3||style="background:#FFCC00"|4||5||style="background:#FFCC00"|2||меняем их местами
|-
|1||3||4||style="background:#FFCC00"|2||style="background:#FFCC00"|5||разворачивам правую часть
|-
|'''1'''||'''3'''||'''4'''||'''2'''||'''5'''||следующая перестановка
|}

== Специализация алгоритма для генерации следующей мультиперестановки ==
* Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример).
* Меняем его с минимальным элементом, большим нашего, стоящим правее.
* Переворачиваем правую часть.
'''int[]''' nextMultiperm('''int[]''' b): // <tex>n</tex> {{---}} длина мультиперестановки
i = n - 2
'''while''' (i > 0) '''and''' (b[i] >= b[i + 1])
i--
'''if''' i >= 0
j = i + 1
'''while''' (j < n - 1) '''and''' (b[j + 1] > b[i])
j++
swap(b[i] , b[j])
reverse(b, i + 1, n - 1)
'''return''' b
'''else'''
'''return''' ''null''

=== Пример работы ===
{| class="wikitable" border = 1
|1||2||3||1||style="background:#FFCC00"|2||style="background:#FFCC00"|3||Исходная перестановка.
|-
| || || || ||^|| ||Находим элемент, нарушающий убывающую последовательность.
|-
| || || || || ||^||Минимальный элемент больше нашего.
|-
|1||2||3||1||style="background:#FFCC00"|3||style="background:#FFCC00"|2||Меняем их местами.
|-
|'''1'''||'''2'''||'''3'''||'''1'''||'''3'''||'''2'''||Следующая мультиперестановка.
|}

== Специализация алгоритма для генерации следующего сочетания ==

* Добавим в конец массива с сочетанием <tex>N+1</tex> – максимальный элемент.
* Пойдём справа налево. Будем искать номер элемента, который отличается от предыдущего на <tex>2</tex>.
* Увеличим найденный элемент на <tex>1</tex>, и допишем в конец минимально возможный хвост, если такого элемента нет – на вход было дано последнее сочетание.
'''int[]''' nextChoose('''int[]''' a, '''int''' n, '''int''' k): // <tex>n,k </tex> {{---}} параметры сочетания
'''for''' i = 0 '''to''' k - 1
b[i] = a[i]
b[k] = n + 1
i = n - 1
'''while''' (i >= 0) '''and''' (b[i + 1] - b[i]) < 2)
i--
'''if''' i >= 0
b[i]++
'''for''' j = i + 1 '''to''' k - 1
b[j] = b[j - 1] + 1
'''for''' i = 0 '''to''' k - 1
a[i] = b[i]
'''return''' a
'''else'''
'''return''' ''null''

=== Пример работы ===
{| class="wikitable" border = 1
|1||2||5||6||style="background:#FFCC00"|'''7'''||Дописываем 7 в конец сочетания.
|-
|1||style="background:#FFCC00"|2||5||6||'''7'''||
|-
| ||^|| || || ||Находим элемент i, a[i + 1] - a[ i ] >= 2
|-
|1||style="background:#FFCC00"|3||5||6||'''7'''||Увеличиваем его на 1.
|-
|1||3||style="background:#FFCC00"|4||style="background:#FFCC00"|5||style="background:#FFCC00"|'''6'''||Дописываем минимальный хвост.
|-
|'''1'''||'''3'''||'''4'''||'''5'''||''' '''||Следующее сочетание.
|}

== Специализация алгоритма для генерации следующего разбиения на слагаемые ==
Рассматриваемый алгоритм находит следующее [[комбинаторные объекты|разбиение на слагаемые]], при этом разбиение упорядоченно по возрастанию.
* Увеличим предпоследнее слагаемое на <tex>1</tex>, уменьшим последнее слагаемое на <tex>1</tex>.
** Если предпоследнее слагаемое стало больше последнего, то увеличиваем предпоследнее слагаемое на величину последнего.
** Если предпоследнее слагаемое меньше последнего, то разбиваем последнее слагаемое <tex>s</tex> на два слагаемых <tex>a</tex> и <tex>b</tex> таких, что <tex>a</tex> равно предпоследнему слагаемому, а <tex>b = s - a</tex>. Повторяем этот процесс, пока разбиение остается корректным, то есть предпоследнее слагаемое хотя бы в два раза меньше последнего.

<code>
// <tex>b</tex> {{---}} список, содержащий разбиение данного числа <tex>b.size</tex>{{---}} его размер 
'''list<int>''' nextPartition('''list<int>''' b):
b[b.size - 1]--
b[b.size - 2]++
'''if''' b[b.size - 2] > b[b.size - 1]
b[b.size - 2] += b[b.size - 1]
b.remove(b.size - 1)
'''else'''
'''while''' b[b.size - 2] * 2 <= b[b.size - 1]
b.add(b[b.size - 1] - b[b.size - 2])
b[b.size - 2] = b[b.size - 3]
'''return''' b
</code>

=== Пример работы ===
{| class="wikitable" border = 1
|1||style="background:#FFCC00"|1||style="background:#FFCC00"|7|| || ||Прибавим 1 + 1, вычтем 7 - 1.
|-
|1||style="background:#FFCC00"|2||style="background:#FFCC00"|6|| || ||Проверяем: 2 < 6, значит разбиваем 6 пока оно не станет меньше 4
|-
|1||2||style="background:#FFCC00"|2||style="background:#FFCC00"|4|| ||
|-
|1||2||2||style="background:#FFCC00"|2||style="background:#FFCC00"|2||
|-
|'''1'''||'''2'''||'''2'''||'''2'''||'''2'''||Следующее разбиение на слагаемые числа 9.
|}

{| class="wikitable" border = 1
|1||style="background:#FFCC00"|4||style="background:#FFCC00"|5||Прибавим 4 + 1, вычтем 5 - 1.
|-
|1||style="background:#FFCC00"|5||style="background:#FFCC00"|4||Проверяем: 5 > 4, значит прибавим к 5 + 4.
|-
|1||9||style="background:#FFCC00"|4||Удалим последний элемент.
|-
|'''1'''||'''9'''||||Следующее разбиение на слагаемые числа 10.
|}

== Специализация алгоритма для генерации следующего разбиения на подмножества ==

Рассмотрим множество первых n натуральных чисел:<tex>N_n = \{1, 2, ..., n\}</tex>

Упорядочим все разбиения на множества <tex>N_n</tex> лексикографически. Для этого, во-первых, в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество <tex> A \subset N_n </tex> лексикографически меньше подмножества <tex> B \subset N_n </tex> , если верно одно из следующих условий:

*существует <tex>i</tex> такое, что <tex>i \in A</tex> , <tex>i \notin B</tex>, для всех <tex>j < i: j \in A</tex> если и только если <tex>j \in B</tex> , и существует <tex>k > i</tex> такое что <tex>k \in B</tex>;
* <tex> A \subset B </tex> и <tex>i < j</tex> для всех <tex>i \in A</tex> и <tex>j \in B</tex> \ <tex> A </tex>.

Разбиения упорядочены лексикографически следующим образом. Разбиение <tex>N_n = A_1 \cup A_2 \cup . . . \cup A_k</tex> лексикографически меньше разбиения <tex>N_n = B_1 \cup B_2 \cup . . . \cup B_l</tex> если существует такое <tex>i</tex>, что <tex>A_1 = B_1, A_2 = B_2, . . . ,A_{i - 1} = B_{i - 1}, A_i < B_i</tex>.

'''Рассмотрим алгоритм нахождения лексикографически следующего разбиения на подмножества:'''
*Будем хранить подмножества в списке списков, например, разбиение <tex> \{1, 2, 3\}~ \{4, 5\}</tex> будет выглядеть так:

{| class="wikitable" border = 1
|1||2||3
|-
|4||5||
|}

* Двигаясь снизу вверх и справа налево, будем удалять элементы, записывая их в отдельный массив. Будем повторять эту операцию, пока не сможем выполнить одно из действий, описанных ниже:
** Заменить рассматриваемый элемент уже удаленным. Из всех подходящих элементов выбираем минимальный. '''Важное замечание''': мы не можем заменить первый элемент подмножества, мы можем только удалить его.
** Дополнить рассматриваемое подмножество уже удаленным элементом. Из всех подходящих элементов выбираем минимальный.
* Допишем лексикографически минимальный хвост подмножеств из оставшихся элементов.

<code>
'''list<list<int>>''' nextSetPartition('''list<list<int>>''' a):
// <tex>a</tex> {{---}} список, содержащий подмножества
// <tex>used</tex> {{---}} список, в котором мы храним удаленные элементы
used = '''list<int>'''
fl = ''false''
'''for''' i = a.size - 1 '''downto''' 0
'''if''' (used.size != 0) '''and''' (used[used.size - 1] > a[i][a[i].size - 1]) // если можем добавить в конец подмножества элемент из <tex>used</tex>
a[i].add(used[used.size - 1]) //добавляем
used.remove(used.size - 1)
'''break'''
'''for''' j = a[i].size - 1 '''downto''' 0
'''if''' (used.size != 0) '''and''' (j != 0) '''and''' (used[used.size - 1] > a[i][j]) //если можем заменить элемент, другим элементом из списка <tex>used</tex> 
a[i][j] = used[used.size - 1] //заменяем
fl = ''true''
'''break'''
'''if''' fl '''break'''
used.add(a[i][j]) //добавляем в <tex>used</tex> <tex>j</tex> элемент <tex>i</tex>-го подмножества
a[i].remove(j) //удаляем <tex>j</tex> элемент <tex>i</tex>-го подмножества
//далее выведем все получившиеся подмножества
sort(used)
'''for''' i = 0 '''to''' used.size - 1
a.add('''list<int>'''(used[i])) //добавляем лексикографически минимальных хвост
'''return''' a
</code>

=== Пример работы ===

'''Рассмотрим следующее разбиение:'''

{| class="wikitable" border = 1
|1||2||3
|-
|4||5||
|}

'''1 Шаг:'''

{| class="wikitable" border = 1
|1||2||3||
|-
|4||style="background:#FFCC00"|5||||
|-
| ||^|| ||Удалили элемент 5.
|-
| || || ||used
|}

'''2 Шаг:'''

{| class="wikitable" border = 1
|1||2||3||
|-
|style="background:#FFCC00"|4|| ||||
|-
|^|| || ||Удалили элемент 4. Так как он является первым в подмножестве, то мы не можем заменить его на другой.
|-
|5|| || ||used
|}

'''3 Шаг:'''

{| class="wikitable" border = 1
|1||2||3||style="background:#FFCC00"|4||
|-
| || || ||^||Дополнили первое подмножество элементом 4
|-
|5|| || || ||used
|}

'''4 Шаг:'''

{| class="wikitable" border = 1
|1||2||3||4||
|-
|style="background:#FFCC00"|5|| || || ||Дописали лексикографически минимальный хвост
|-
| || || || ||used
|}

== См.также ==
* [[Получение предыдущего объекта]]
* [[Получение объекта по номеру]]
* [[Получение номера по объекту]]

== Источники информации ==

* [http://rain.ifmo.ru/cat/view.php/vis/combinations/permutations-2000 Визуализатор перестановок]
* [http://cppalgo.blogspot.com/2011/02/episode-2.html Пример компактного кода для перестановок (С++)]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

СНМ (реализация с помощью леса корневых деревьев)

2016-01-24T17:29:54Z

5.18.154.236: /* Анализ реализации с ранговой эвристикой */

Данная реализация СНМ позволяет добиться наилучшей асимптотики при работе с этой структурой данных. А именно, обе операции (<tex>\mathrm{get}</tex> и <tex>\mathrm{union}</tex>) выполняются в среднем за практически константное время.
==Реализация==
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель {{---}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".

При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''<tex>\mathrm{union}</tex>''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''<tex>\mathrm{get}</tex>'').

Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где <tex>\mathrm{get}</tex> будет работать за линейное время, и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализацими]] не будет. Выигрыш в скорости можно получить, используя две эвристики: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).

===Объединение по рангу===
Эта эвристика аналогична [[СНМ(списки_с_весовой_эвристикой)|весовой эвристике у связных списков]]. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.

Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен <tex>0</tex>. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на <tex>1</tex>.

===Сжатие пути===
Эта эвристика несколько модифицирует операцию ''<tex>\mathrm{get}</tex>''. Операция <tex>\mathrm{get}</tex> вызывается для элемента <tex>x</tex>, проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и <tex>x</tex>. Поэтому мы можем подвесить (изменить ссылки) эти вершины напрямую к корню дерева и, таким образом, уменьшить его высоту. При нерекурсивной реализации операция ''<tex>\mathrm{get}</tex>'' становится двухпроходной.

===Псевдокод===
Для реализации СНМ будем поддерживать следующие массивы: <tex>p[x]</tex> {{---}} массив "родителей", <tex>r[x]</tex> {{---}} массив рангов.
===='''get'''====
'''function''' '''get'''(x: '''int'''): '''int'''
'''if''' p[x] != x
p[x] = get(p[x])
'''return''' p[x]

===='''union'''====
'''function''' '''union'''(x: '''int''', y: '''int'''):
x = get(x)
y = get(y)
'''if''' x == y
'''return'''
'''if''' r[x] == r[y]
r[x]++
'''if''' r[x] < r[y]
p[x] = y
'''else'''
p[y] = x

Также возможна реализация функции <tex>\mathrm{get}</tex> без использования <tex>\mathrm{O(\log n)}</tex> дополнительнй памяти.

===='''get'''====
'''function''' '''get'''(x: '''int'''): '''int'''
root = x
'''while''' p[root] != root
root = p[root]
i = x
'''while''' p[i] != i
j = p[i]
p[i] = root
i = j
'''return''' root

==Асимптотика==
:''см. также [[Анализ_реализации_с_ранговой_эвристикой|Анализ реализации с ранговой эвристикой]]''

{| class="wikitable" border = 1
|-
!Операция !! Истинное время !! Амортизированное время
|- style = "text-align = center"
| ''<tex>\mathrm{get}</tex>'' || <tex>\mathrm{O(\log n)}</tex> || <tex>\mathrm{O(\mathrm{\alpha(m, n)})}</tex>
|-
| ''<tex>\mathrm{union}</tex>'' || <tex>\mathrm{O(\log n)}</tex> || <tex>\mathrm{O(\mathrm{\alpha(m, n)})}</tex>
|}
Где <tex>m</tex> {{---}} общее количество операций, <tex>n</tex> {{---}} полное количество элементов, <tex>\mathrm{\alpha(m, n)}</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций <tex>\mathrm{get}</tex> и <tex>n</tex> элементов).

Докажем, что если глубина множества (т.е. его ранг) равна <tex>k</tex>, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с <tex>n</tex> элементами есть <tex>\mathrm{O(\log n)}</tex>, а значит и время работы операции <tex>\mathrm{get}</tex> является логарифмическим.

Будем доказывать данное свойство по индукции. Для <tex>k = 0</tex>, очевидно, в множестве содержится <tex>1</tex> вершина. Пусть для множеств ранга <tex>k - 1</tex> свойство выполняется. Как следует из ранговой эвристики, множество ранга <tex>k</tex> может получиться только при подвешивании множества ранга <tex>k - 1</tex> к множеству ранга <tex>k - 1</tex>. Но тогда из предположения индукции в новом множестве действительно будет <tex>2^k</tex> вершин, что и требовалось доказать.

===Функция Аккермана===

Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел <tex>m</tex> и <tex>n</tex>:

<tex>\mathrm{A(m, n)} = \begin{cases}
2^n, & m = 1 \\
2, & m > 1, n = 0 \\
\mathrm{A(m - 1, A(m, n - 1))}, & m > 1, n > 0
\end{cases} </tex>

Таблица значений функции Аккермана:

{| class="wikitable" border = 1
|-
!<tex>\mathbf{m \backslash n}</tex> !! <tex>\mathbf{0}</tex> !! <tex>\mathbf{1}</tex> !! <tex>\mathbf{2}</tex> !! <tex>\mathbf{3}</tex> !! <tex>\mathbf{4}</tex> !! <tex>\mathbf{5}</tex>
|-style = "text-align = center"
! <tex>\mathbf{1}</tex>
| <tex>1</tex> || <tex>2</tex> || <tex>4</tex> || <tex>8</tex> || <tex>16</tex> || <tex>32</tex>
|-
! <tex>\mathbf{2}</tex>
| <tex>2</tex> || <tex>4</tex> || <tex>16</tex> || <tex>65536</tex> || <tex>2^{2^{16}}</tex> || <tex>2^{2^{2^{16}}}</tex>
|-
! <tex>\mathbf{3}</tex>
| <tex>2</tex> || <tex>16</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{A(3, 2)}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>
|-
! <tex>\mathbf{4}</tex>
| <tex>2</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>
|}

Функция, обратная функции Аккермана <tex>\mathrm{\alpha(m, n)}</tex>, равна минимальному <tex>i</tex> такому, что <tex>\mathrm{A \left (i, \left [\dfrac{m}{n} \right ] \right )} \geqslant \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция <tex>\mathrm{get}</tex> выполняется за константное время.

===Анализ реализации с ранговой эвристикой===

Проведем анализ реализации с ранговой эвристикой. Будем доказывать, что амортизационная стоимость <tex> \mathrm{get} = \mathrm{O(\log^{*}n)} </tex>.
{{Определение
|definition='''Итерированный логарифм''' (англ. ''Iterated logarithm'') <tex>\mathrm{\log^*n}</tex> — минимальное число логарифмирований <tex>n</tex>, необходимое для получения значения, не превосходящего <tex>1</tex>.
}}
'''Пример''': <tex>\mathrm{\log^*_2 16} = 3</tex>

Рассмотрим <tex> n </tex> операций <tex> \mathrm{union} </tex> и <tex> m </tex> операций <tex> \mathrm{get} </tex>. Можем считать, что число операций <tex> \mathrm{union} </tex> равно числу элементов множества, так как количество операций <tex>\mathrm{union}</tex> не превосходит количество элементов множества <tex>n</tex>. Заметим, что <tex>m\geqslant n</tex>, так как при каждом вызове операции <tex>\mathrm{union}</tex> дважды вызывается операция <tex>\mathrm{get}</tex>.
Не теряя общности, будем считать, что <tex> \mathrm{union} </tex> принимает в качестве аргументов представителей,
то есть <tex> \mathrm{union(v_1,v_2)} </tex> заменяем на <tex> \mathrm{union(get(v_1),get(v_2))} </tex>.

Оценим стоимость операции <tex> \mathrm{get(v)} </tex>.
Обозначим <tex> \mathrm{R(v)} </tex> — ранг вершины, <tex>\mathrm{P(v)}</tex> — представитель множества, содержащего <tex>\mathrm{v}</tex>,
<tex> \mathrm{L(v)} </tex> — отец вершины,
<tex> \mathrm{K(v)} </tex> — количество вершин в поддереве, корнем которого является <tex>\mathrm{v}</tex>.

{{Утверждение
|statement=
<tex> \mathrm{R(P(v))} \geqslant \mathrm{R(v)} </tex>
|proof=
Если <tex>\mathrm{v}</tex> — представитель множества, то <tex>\mathrm{P(v)}=\mathrm{v}</tex> и <tex> \mathrm{R(P(v))} = \mathrm{R(v)} </tex>.

Иначе, из принципа работы функции <tex> \mathrm{union} </tex> следует:
#<tex> \mathrm{R(L(v))}>\mathrm{R(v)} </tex>.
#Между <tex> \mathrm{v} </tex> и <tex> \mathrm{P(v)} </tex> существует путь вида: <tex> \mathrm{v} \rightarrow \mathrm{L(v)} \rightarrow \mathrm{L(L(v))} \rightarrow \dots \rightarrow \mathrm{P(v)} </tex>.
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение
|statement=
<tex> \mathrm{R(v)} = i \Rightarrow {\mathrm{K(v)}} \geqslant {2^i}</tex>
|proof=
Докажем по индукции:

Для <tex>0</tex> равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>\mathrm{K(v)} \geqslant \mathrm{K(v_1)} + \mathrm{K(v_2)} \geqslant 2^{i-1}+2^{i-1} \geqslant 2^i </tex>.
}}

Из последнего утверждения следует:

{{Утверждение
|statement=
<tex> \mathrm{R(v)} \leqslant \log_2n </tex>
}}
{{Утверждение
|statement=
Количество вершин ранга <tex> i \leqslant \dfrac{n} {2^i} </tex>.
|proof=
Если бы это было не так, то просуммировав количество вершин всех рангов, мы получили бы число большее <tex>n</tex>. Это противоречит условию, по которому <tex>n</tex> — число всех вершин. Значит утверждение верно.
}}

{{Теорема
|statement=
Амортизационная стоимость <tex> \mathrm{get} = \mathrm{O(\log^{*}n)} </tex>
|proof=

Рассмотрим все вызовы функции <tex>\mathrm{get(u)}</tex>. В процессе выполнения каждой операции двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Если вершина <tex>u</tex> не корень и не сын корня, то во время рекурсивных вызовов функции <tex>\mathrm{get(u)}</tex> текущее значение <tex>\mathrm{R(L(u))}</tex> возрастает.
Пусть <tex>m</tex> — количество вызовов операции <tex>\mathrm{get(u)}</tex>, <tex>n</tex> — количество вызовов операции <tex>\mathrm{union(v, u)}</tex>, и <tex>m\geqslant n</tex>.
Разделим все вершины на <tex>4</tex> типа:

:1. <tex>u</tex> — корень. Таких вызовов <tex>\mathrm{get(u)}</tex> будет ровно <tex>m</tex>.
:2. <tex>u</tex> — сын корня. Таких вызовов <tex>\mathrm{get(u)}</tex> будет не больше чем <tex>m</tex>.
Оставшиеся вершины разделим на:
:3. Быстро растущие вызовы — такие что <tex>\mathrm{R(P(u))} \geqslant i^{\mathrm{R(u)}}</tex>, где <tex>i</tex> — число из диапазона <tex dpi="150">e ^{\frac{1}{e}} <tex dpi="150">(e ^{\frac{1}{e}}\approx </tex> <tex>1.44</tex><tex dpi="150">)</tex>.
:4. Медленно растущие вызовы — <tex>\mathrm{R(P(u))} < i^{\mathrm{R(u)}}</tex>.

Для первых двух типов вершин одна операция <tex>\mathrm{get(u)}</tex> работает за истинное время <tex>\mathrm{O(1)}</tex>, поэтому их суммарное время работы не превышает <tex>2\cdot m</tex>.

При каждом вложенном вызове функции <tex>\mathrm{get(u)}</tex> для вершин третьего типа ранг по условию возрастает до <tex>i^{\mathrm{R(u)}}</tex>. Ранг вершины может меняться в пределах от <tex>0</tex> до <tex>\log_2n</tex>. Значит количество рекурсивных вызовов равняется количеству возведений в степень <tex>\mathrm{R(n)}</tex> числа <tex>i</tex>,
необходимых для достижения числа <tex>\log_2n</tex>. Или что то же самое, количеству логарифмирований по основанию <tex>i</tex> числа <tex>\log_2n</tex> для получения <tex>1</tex> и еще одному логарифмированию для получения <tex>0</tex>. Количество логарифмирований описывается функцией <tex dpi="130">\log^*_{i} \left (\log_2 n \right )</tex>. С учетом последнего логарифмирования формула примет вид <tex dpi="130">\log^*_{i}n</tex>.
Тогда время работы <tex>m</tex> быстро растущих вызовов равно <tex>\mathrm{O(m\cdot \log^* n)}</tex>.

Поскольку количество вершин с рангом <tex>k</tex> не превышает число <tex>\dfrac{n}{2^k}</tex>, то суммарное время работы медленно растущих вызовов равно
<center>
<tex dpi="150">\sum_u \limits i^{\mathrm{R(u)}}=\sum_{k=0}^{\log n} \limits \sum_{\mathrm{{R(u)}=k}} \limits i^k \leqslant \sum_{k=0}^{\log n} \limits i^k \cdot \frac{n}{2^k} \leqslant n \cdot \sum_{k=0}^{\log n} \limits \dfrac{i^k}{2^k} = \mathrm{O(n)}</tex>
</center>
В итоге получаем, что суммарное время работы операции <tex>\mathrm{get(u)}</tex> равняется <tex>T = \mathrm{O(m)} + \mathrm{O(m\cdot \log^* n)} +\mathrm{O(n)} = \mathrm{O(m\cdot \log^*n + n)}</tex>.
С учетом того факта что <tex>m\geqslant n</tex>, амортизированное время работы равно <tex>\mathrm{O(\log^* n)}</tex>.
}}

== См. также ==
* [[СНМ (списки с весовой эвристикой)]]
* [[СНМ (наивные реализации)]]

==Источники информации==
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств {{---}} описание этой реализации на habrahabr.ru]
* [http://ru.wikipedia.org/wiki/Функция_Аккермана Функция Аккермана {{---}} Википедия]
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Вильямс, 2010. - стр 589. — ISBN 978-5-8459-0857-4

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]

СНМ (реализация с помощью леса корневых деревьев)

2016-01-24T17:07:13Z

5.18.154.236:

Данная реализация СНМ позволяет добиться наилучшей асимптотики при работе с этой структурой данных. А именно, обе операции (<tex>\mathrm{get}</tex> и <tex>\mathrm{union}</tex>) выполняются в среднем за практически константное время.
==Реализация==
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель {{---}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".

При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''<tex>\mathrm{union}</tex>''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''<tex>\mathrm{get}</tex>'').

Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где <tex>\mathrm{get}</tex> будет работать за линейное время, и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализацими]] не будет. Выигрыш в скорости можно получить, используя две эвристики: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).

===Объединение по рангу===
Эта эвристика аналогична [[СНМ(списки_с_весовой_эвристикой)|весовой эвристике у связных списков]]. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.

Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен <tex>0</tex>. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на <tex>1</tex>.

===Сжатие пути===
Эта эвристика несколько модифицирует операцию ''<tex>\mathrm{get}</tex>''. Операция <tex>\mathrm{get}</tex> вызывается для элемента <tex>x</tex>, проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и <tex>x</tex>. Поэтому мы можем подвесить (изменить ссылки) эти вершины напрямую к корню дерева и, таким образом, уменьшить его высоту. При нерекурсивной реализации операция ''<tex>\mathrm{get}</tex>'' становится двухпроходной.

===Псевдокод===
Для реализации СНМ будем поддерживать следующие массивы: <tex>p[x]</tex> {{---}} массив "родителей", <tex>r[x]</tex> {{---}} массив рангов.
===='''get'''====
'''function''' '''get'''(x: '''int'''): '''int'''
'''if''' p[x] != x
p[x] = get(p[x])
'''return''' p[x]

===='''union'''====
'''function''' '''union'''(x: '''int''', y: '''int'''):
x = get(x)
y = get(y)
'''if''' x == y
'''return'''
'''if''' r[x] == r[y]
r[x]++
'''if''' r[x] < r[y]
p[x] = y
'''else'''
p[y] = x

Также возможна реализация функции <tex>\mathrm{get}</tex> без использования <tex>\mathrm{O(\log n)}</tex> дополнительнй памяти.

===='''get'''====
'''function''' '''get'''(x: '''int'''): '''int'''
root = x
'''while''' p[root] != root
root = p[root]
i = x
'''while''' p[i] != i
j = p[i]
p[i] = root
i = j
'''return''' root

==Асимптотика==
:''см. также [[Анализ_реализации_с_ранговой_эвристикой|Анализ реализации с ранговой эвристикой]]''

{| class="wikitable" border = 1
|-
!Операция !! Истинное время !! Амортизированное время
|- style = "text-align = center"
| ''<tex>\mathrm{get}</tex>'' || <tex>\mathrm{O(\log n)}</tex> || <tex>\mathrm{O(\mathrm{\alpha(m, n)})}</tex>
|-
| ''<tex>\mathrm{union}</tex>'' || <tex>\mathrm{O(\log n)}</tex> || <tex>\mathrm{O(\mathrm{\alpha(m, n)})}</tex>
|}
Где <tex>m</tex> {{---}} общее количество операций, <tex>n</tex> {{---}} полное количество элементов, <tex>\mathrm{\alpha(m, n)}</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций <tex>\mathrm{get}</tex> и <tex>n</tex> элементов).

Докажем, что если глубина множества (т.е. его ранг) равна <tex>k</tex>, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с <tex>n</tex> элементами есть <tex>\mathrm{O(\log n)}</tex>, а значит и время работы операции <tex>\mathrm{get}</tex> является логарифмическим.

Будем доказывать данное свойство по индукции. Для <tex>k = 0</tex>, очевидно, в множестве содержится <tex>1</tex> вершина. Пусть для множеств ранга <tex>k - 1</tex> свойство выполняется. Как следует из ранговой эвристики, множество ранга <tex>k</tex> может получиться только при подвешивании множества ранга <tex>k - 1</tex> к множеству ранга <tex>k - 1</tex>. Но тогда из предположения индукции в новом множестве действительно будет <tex>2^k</tex> вершин, что и требовалось доказать.

===Функция Аккермана===

Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел <tex>m</tex> и <tex>n</tex>:

<tex>\mathrm{A(m, n)} = \begin{cases}
2^n, & m = 1 \\
2, & m > 1, n = 0 \\
\mathrm{A(m - 1, A(m, n - 1))}, & m > 1, n > 0
\end{cases} </tex>

Таблица значений функции Аккермана:

{| class="wikitable" border = 1
|-
!<tex>\mathbf{m \backslash n}</tex> !! <tex>\mathbf{0}</tex> !! <tex>\mathbf{1}</tex> !! <tex>\mathbf{2}</tex> !! <tex>\mathbf{3}</tex> !! <tex>\mathbf{4}</tex> !! <tex>\mathbf{5}</tex>
|-style = "text-align = center"
! <tex>\mathbf{1}</tex>
| <tex>1</tex> || <tex>2</tex> || <tex>4</tex> || <tex>8</tex> || <tex>16</tex> || <tex>32</tex>
|-
! <tex>\mathbf{2}</tex>
| <tex>2</tex> || <tex>4</tex> || <tex>16</tex> || <tex>65536</tex> || <tex>2^{2^{16}}</tex> || <tex>2^{2^{2^{16}}}</tex>
|-
! <tex>\mathbf{3}</tex>
| <tex>2</tex> || <tex>16</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{A(3, 2)}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>
|-
! <tex>\mathbf{4}</tex>
| <tex>2</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>
|}

Функция, обратная функции Аккермана <tex>\mathrm{\alpha(m, n)}</tex>, равна минимальному <tex>i</tex> такому, что <tex>\mathrm{A \left (i, \left [\dfrac{m}{n} \right ] \right )} \geqslant \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция <tex>\mathrm{get}</tex> выполняется за константное время.

===Анализ реализации с ранговой эвристикой===

Проведем анализ реализации с ранговой эвристикой. Будем доказывать, что амортизационная стоимость <tex> \mathrm{get} = \mathrm{O(\log^{*}n)} </tex>.
{{Определение
|definition='''Итерированный логарифм''' (англ. ''Iterated logarithm'') <tex>\mathrm{\log^*n}</tex> — минимальное число логарифмирований <tex>n</tex>, необходимое для получения значения, не превосходящего <tex>1</tex>.
}}
'''Пример''': <tex>\mathrm{\log^*_2 16} = 3</tex>

Рассмотрим <tex> n </tex> операций <tex> \mathrm{union} </tex> и <tex> m </tex> операций <tex> \mathrm{get} </tex>. Можем считать, что число операций <tex> \mathrm{union} </tex> равно числу элементов множества, так как количество операций <tex>\mathrm{union}</tex> не превосходит количество элементов множества <tex>n</tex>. Заметим, что <tex>m\geqslant n</tex>, так как при каждом вызове операции <tex>\mathrm{union}</tex> дважды вызывается операция <tex>\mathrm{get}</tex>.
Не теряя общности, будем считать, что <tex> \mathrm{union} </tex> принимает в качестве аргументов представителей,
то есть <tex> \mathrm{union(v_1,v_2)} </tex> заменяем на <tex> \mathrm{union(get(v_1),get(v_2))} </tex>.

Оценим стоимость операции <tex> \mathrm{get(v)} </tex>.
Обозначим <tex> \mathrm{R(v)} </tex> — ранг вершины, <tex>\mathrm{P(v)}</tex> — представитель множества, содержащего <tex>\mathrm{v}</tex>,
<tex> \mathrm{L(v)} </tex> — отец вершины,
<tex> \mathrm{K(v)} </tex> — количество вершин в поддереве, корнем которого является <tex>\mathrm{v}</tex>.

{{Утверждение
|statement=
<tex> \mathrm{R(P(v))} \geqslant \mathrm{R(v)} </tex>
|proof=
Если <tex>\mathrm{v}</tex> — представитель множества, то <tex>\mathrm{P(v)}=\mathrm{v}</tex> и <tex> \mathrm{R(P(v))} = \mathrm{R(v)} </tex>.

Иначе, из принципа работы функции <tex> \mathrm{union} </tex> следует:
#<tex> \mathrm{R(L(v))}>\mathrm{R(v)} </tex>.
#Между <tex> \mathrm{v} </tex> и <tex> \mathrm{P(v)} </tex> существует путь вида: <tex> \mathrm{v} \rightarrow \mathrm{L(v)} \rightarrow \mathrm{L(L(v))} \rightarrow \dots \rightarrow \mathrm{P(v)} </tex>.
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}

{{Утверждение
|statement=
<tex> \mathrm{R(v)} = i \Rightarrow {\mathrm{K(v)}} \geqslant {2^i}</tex>
|proof=
Докажем по индукции:

Для <tex>0</tex> равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>\mathrm{K(v)} \geqslant \mathrm{K(v_1)} + \mathrm{K(v_2)} \geqslant 2^{i-1}+2^{i-1} \geqslant 2^i </tex>.
}}

Из последнего утверждения следует:

{{Утверждение
|statement=
<tex> \mathrm{R(v)} \leqslant \log_2n </tex>
}}
{{Утверждение
|statement=
Количество вершин ранга <tex> i \leqslant \dfrac{n} {2^i} </tex>.
|proof=
Если бы это было не так, то просуммировав количество вершин всех рангов, мы получили бы число большее <tex>n</tex>. Это противоречит условию, по которому <tex>n</tex> — число всех вершин. Значит утверждение верно.
}}

{{Теорема
|statement=
Амортизационная стоимость <tex> \mathrm{get} = \mathrm{O(\log^{*}n)} </tex>
|proof=

Рассмотрим все вызовы функции <tex>\mathrm{get(u)}</tex>. В процессе выполнения каждой операции двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Если вершина <tex>u</tex> не корень и не сын корня, то во время рекурсивных вызовов функции <tex>\mathrm{get(u)}</tex> текущее значение <tex>\mathrm{R(L(u))}</tex> возрастает.
Пусть <tex>m</tex> — количество вызовов операции <tex>\mathrm{get(u)}</tex>, <tex>n</tex> — количество вызовов операции <tex>\mathrm{union(v, u)}</tex>, и <tex>m\geqslant n</tex>.
Разделим все вершины на <tex>4</tex> типа:

:1. <tex>u</tex> — корень. Таких вызовов <tex>\mathrm{get(u)}</tex> будет ровно <tex>m</tex>.
:2. <tex>u</tex> — сын корня. Таких вызовов <tex>\mathrm{get(u)}</tex> будет не больше чем <tex>m</tex>.
Оставшиеся вершины разделим на:
:3. Быстро растущие вызовы — такие что <tex>\mathrm{R(L(u))} \geqslant i^{\mathrm{R(u)}}</tex>, где <tex>i</tex> — число из диапазона <tex dpi="150">e ^{\frac{1}{e}} <tex dpi="150">(e ^{\frac{1}{e}}\approx </tex> <tex>1.44</tex><tex dpi="150">)</tex>.
:4. Медленно растущие вызовы — <tex>\mathrm{R(L(u))} < i^{\mathrm{R(u)}}</tex>.

Для первых двух типов вершин одна операция <tex>\mathrm{get(u)}</tex> работает за истинное время <tex>\mathrm{O(1)}</tex>, поэтому их суммарное время работы не превышает <tex>2\cdot m</tex>.

При каждом вложенном вызове функции <tex>\mathrm{get(u)}</tex> для вершин третьего типа ранг по условию возрастает до <tex>i^{\mathrm{R(u)}}</tex>. Ранг вершины может меняться в пределах от <tex>0</tex> до <tex>\log_2n</tex>. Значит количество рекурсивных вызовов равняется количеству возведений в степень <tex>\mathrm{R(n)}</tex> числа <tex>i</tex>,
необходимых для достижения числа <tex>\log_2n</tex>. Или что то же самое, количеству логарифмирований по основанию <tex>i</tex> числа <tex>\log_2n</tex> для получения <tex>1</tex> и еще одному логарифмированию для получения <tex>0</tex>. Количество логарифмирований описывается функцией <tex dpi="130">\log^*_{i} \left (\log_2 n \right )</tex>. С учетом последнего логарифмирования формула примет вид <tex dpi="130">\log^*_{i}n</tex>.
Тогда время работы <tex>m</tex> быстро растущих вызовов равно <tex>\mathrm{O(m\cdot \log^* n)}</tex>.

Поскольку количество вершин с рангом <tex>k</tex> не превышает число <tex>\dfrac{n}{2^k}</tex>, то суммарное время работы медленно растущих вызовов равно
<center>
<tex dpi="150">\sum_u \limits i^{\mathrm{R(u)}}=\sum_{k=0}^{\log n} \limits \sum_{\mathrm{{R(u)}=k}} \limits i^k \leqslant \sum_{k=0}^{\log n} \limits i^k \cdot \frac{n}{2^k} \leqslant n \cdot \sum_{k=0}^{\log n} \limits \dfrac{i^k}{2^k} = \mathrm{O(n)}</tex>
</center>
В итоге получаем, что суммарное время работы операции <tex>\mathrm{get(u)}</tex> равняется <tex>T = \mathrm{O(m)} + \mathrm{O(m\cdot \log^* n)} +\mathrm{O(n)} = \mathrm{O(m\cdot \log^*n + n)}</tex>.
С учетом того факта что <tex>m\geqslant n</tex>, амортизированное время работы равно <tex>\mathrm{O(\log^* n)}</tex>.
}}

== См. также ==
* [[СНМ (списки с весовой эвристикой)]]
* [[СНМ (наивные реализации)]]

==Источники информации==
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств {{---}} описание этой реализации на habrahabr.ru]
* [http://ru.wikipedia.org/wiki/Функция_Аккермана Функция Аккермана {{---}} Википедия]
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Вильямс, 2010. - стр 589. — ISBN 978-5-8459-0857-4

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]

Алгоритм цифровой сортировки суффиксов циклической строки

2016-01-23T10:39:24Z

5.18.154.236: /* Описание алгоритма */ исправлена опечатка

{{Задача
|definition = Дана циклическая строка <tex>s[0 .. n - 1]</tex>. Суффиксом циклической строки <tex>s</tex> называется строка <tex>s[i .. n - 1] + s[0 .. i - 1], i < n </tex> (будем называть такую строкую суффиксом под номером <tex>i</tex>). Требуется отсортировать все её суффиксы в порядке лексикографической сортировки.
}}

== Решение ==
Рассматриваемый алгоритм состоит из <tex>\lceil\log n\rceil + 1</tex> итераций. На <tex>k</tex>-той итерации (<tex>k=0..\lceil\log n\rceil </tex>) сортируются циклические подстроки длины <tex>2^k</tex>. На последней, <tex>\lceil\log n\rceil</tex>-ой итерации, будут сортироваться подстроки длины <tex>2^{\lceil\log n\rceil} \geqslant n</tex>, что эквивалентно сортировке циклических сдвигов.

На каждой итерации будем хранить массив перестановки <tex>p[0 .. n - 1]</tex>, где <tex>p[i]</tex> — номер суффикса, занимающего позицию <tex>i</tex> в текущей перестановке. Также будем хранить массив классов эквивалентности <tex>c[0 .. n - 1]</tex>, где <tex>c[i]</tex> — класс эквивалентности, которому принадлежит префикс длины <tex>2^k</tex> суффикса под номером <tex>p[i]</tex>. При этом если префикс суффикса под номером <tex>p[i]</tex> лексикографически меньше префикса суффикса под номером <tex>p[j]</tex>, то <tex>c[i] < c[j]</tex>. Если же префиксы равны, то и их классы эквивалентности одинаковы. Так как мы вставили в строку символ <tex>\$</tex>, то к концу алгоритма каждый суффикс будет иметь уникальный класс эквивалентности, значит, мы установим порядок суффиксов.

== Описание алгоритма ==

На нулевой итерации отсортируем циклические подстроки длины <tex>1</tex>, т.е. первые символы строк, и разделим их на классы эквивалентности (одинаковые символы должны быть отнесены к одному классу эквивалентности). При помощи [[Сортировка подсчетом|сортировки подсчетом]] построим массив <tex>p</tex>, содержащий номера суффиксов, отсортированных в лексикографическом порядке. По этому массиву построим массив классов эквивалентности <tex>c</tex>.

На <tex>k</tex>-ом проходе имеем массивы <tex>p</tex> и <tex>c</tex>, вычисленные на предыдущей итерации. Приведем алгоритм, выполняющий <tex>k</tex>-ый проход за <tex>O(n)</tex>. Поскольку итераций всего <tex>O(\log n)</tex>, такой алгоритм имеет асимптотику <tex>O(n \log n)</tex>.

Заметим, что циклическая подстрока длины <tex>2^k</tex> состоит из двух подстрок длины <tex>2^{k-1}</tex>, которые мы можем сравнивать между собой за <tex>O(1)</tex>, используя информацию с предыдущей итерации — номера классов эквивалентности <tex>c</tex>. Таким образом, для подстроки длины <tex>2^k</tex>, начинающейся в позиции <tex>i</tex>, вся необходимая информация содержится в паре чисел <tex>\langle c[i], c[i + 2^{k-1}]\rangle </tex>.

[[Файл:Suff_array.png|350px|thumb|right|Циклическая подстрока длины <tex>2^k</tex> и порядок ее частей с прерыдущей итерации.]]

Отсортируем подстроки длины <tex>2^k</tex> по данным парам и запишем порядок в массив <tex>p</tex>. Воспользуемся здесь приёмом, на котором основана [[Цифровая сортировка| цифровая сортировка]]: отсортируем пары сначала по вторым элементам, а затем по первым (устойчивой сортировкой). Однако вторые элементы уже упорядочены — этот порядок задан в массиве от предыдущей итерации. Тогда, чтобы получить порядок пар по вторым элементам, надо от каждого элемента массива <tex>p</tex> отнять <tex>2^{k-1}</tex> (<tex>p</tex> даёт упорядочение подстрок длины <tex>2^{k-1}</tex>, и при переходе к строке вдвое большей длины эти подстроки становятся их вторыми половинками, поэтому от позиции второй половинки отнимается длина первой половинки).

Чтобы произвести устойчивую сортировку по первым элементам пар, воспользуемся сортировкой подсчетом, имеющую асимптотику <tex>O(n)</tex>.

Осталось пересчитать номера классов эквивалентности <tex>c</tex>, пройдя по новой перестановке <tex>p</tex> и сравнивая соседние элементы (как пары двух чисел).

==Пример==
<tex>
s = abacaba\$ \\
i' = i + 2^{k-1} \\
\\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
\multicolumn{3}{|l|}{0 iteration} & \multicolumn{4}{l|}{1 iteration} & \multicolumn{4}{l|}{2 iteration} & \multicolumn{4}{l|}{3 iteration} \\ \hline
p & & c & p & & $\langle c[i], c[i']\rangle$ & c & p & & $\langle c[i], c[i']\rangle$ & c & p & & $\langle c[i], c[i']\rangle$ & c \\ \hline
7 & \$ & 1 & 7 & \$a & $\langle1, 2\rangle$ & 1 & 7 & \$aba & $\langle1, 5\rangle$ & 1 & 7 & \$abacaba & $\langle1, 8\rangle$ & 1 \\ \hline
0 & a & 2 & 6 & a\$ & $\langle2, 1\rangle$ & 2 & 6 & a\$ab & $\langle2, 3\rangle$ & 2 & 6 & a\$abacab & $\langle2, 5\rangle$ & 2 \\ \hline
2 & a & 2 & 0 & ab & $\langle2, 3\rangle$ & 3 & 4 & aba\$ & $\langle3, 2\rangle$ & 3 & 4 & aba\$abac & $\langle3, 4\rangle$ & 3 \\ \hline
4 & a & 2 & 4 & ab & $\langle2, 3\rangle$ & 3 & 0 & abac & $\langle3, 4\rangle$ & 4 & 0 & abacaba\$ & $\langle4, 3\rangle$ & 4 \\ \hline
6 & a & 2 & 2 & ac & $\langle2, 4\rangle$ & 4 & 2 & acab & $\langle4, 3\rangle$ & 5 & 2 & acaba\$ab & $\langle5, 2\rangle$ & 5 \\ \hline
1 & b & 3 & 1 & ba & $\langle3, 1\rangle$ & 5 & 5 & ba\$a & $\langle5, 1\rangle$ & 6 & 5 & ba\$abaca & $\langle6, 7\rangle$ & 6 \\ \hline
5 & b & 3 & 5 & ba & $\langle3, 1\rangle$ & 5 & 1 & baca & $\langle5, 6\rangle$ & 7 & 1 & bacaba\$a & $\langle7, 6\rangle$ & 7 \\ \hline
3 & c & 4 & 3 & ca & $\langle4, 1\rangle$ & 6 & 3 & caba & $\langle6, 5\rangle$ & 8 & 3 & caba\$aba & $\langle8, 1\rangle$ & 8 \\ \hline
\end{tabular}
</tex>

==Псевдокод==
/* преобразует масив count, так что
теперь он содержит позиции в массиве suffs с которых
необходимо вставлять подстроки, начинающиеся с соответствующих символов */
'''int[]''' calc_positions('''int[]''' count)
count[0] = 0
'''for''' i = 2 .. count.length - 1
count[i] += count[i - 1]
'''return''' count

/* принимает строку, для которой требуется построить суффиксный массив
возвращает суффиксный массив */
'''int[]''' suff_array('''string''' str)
s += '$'

// нулевая итерация
count = '''int'''[max(<tex>|\Sigma|</tex>, str.length)]
'''fill'''(count, 0)
'''for''' ch '''in''' str
count[ch]++
count = '''calc_positions'''(count)
// suffs будет хранить индексы начал отсортированных подстрок текущей длины
suffs = '''int'''[str.length]
'''for''' ch '''in''' str
suffs[count[ch]++] = i
classes = '''int'''[str.length]
classesN = 0
last_char = '$'
'''for''' suf '''in''' suffs
'''if''' s[suf] <tex> \neq </tex> last_char
last_char = s[suf[i]]
classesN++
classes[suf] = classesN

// нулевая итерация завершена
// сортируем подстроки длиной 2 * cur_len = 2^k
cur_len = 1
'''while''' cur_len <tex> \leqslant </tex> str.length
// сортируем по второй половине подстроки
sorted_by2 = '''int'''[str.length]
'''for''' i = 0 .. str.length - 1
sorted_by2[i] = (suffs[i] + str.length - cur_len) '''mod''' str.length
// сортируем по первой половине
// сортировка устойчивая, значит получим целиком отсортированные подстроки
'''fill'''(count, 0)
'''for''' by2 '''in''' sorted_by2
count[classes[by2]]++
count = '''calc_positions'''(count)
'''for''' i = 0 .. str.length - 1
suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i]

new_classes = '''int'''[str.length]
classesN = 0
'''for''' i = 0 .. str.length - 1
mid1 = (suffs[i] + cur_len) '''mod''' str.length
mid2 = (suffs[i - 1] + cur_len) '''mod''' str.length
'''if''' classes[suffs[i]] <tex> \neq </tex> classes[suffs[i-1]] '''or''' classes[mid1] <tex> \neq </tex> classes[mid2]
classesN++
new_classes[suffs[i]] = classesN
classes = new_classes
cur_len *= 2
'''return''' suffs

== См. также ==
* [[Суффиксный массив]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]

== Источники информации ==
* [http://e-maxx.ru/algo/suffix_array MAXimal :: algo :: Суффиксный массив]
* [http://www.geeksforgeeks.org/suffix-array-set-2-a-nlognlogn-algorithm Suffix Array | Set 2 (nLogn Algorithm)]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Суффиксный массив]]
[[Категория: Структуры данных]]

Простейшие методы синтеза схем из функциональных элементов

2016-01-18T11:09:01Z

5.18.154.236: /* Метод синтеза схем К.Э.Шеннона */ Исправлена ссылка на Шеннона

{{Определение

|definition= Синтезом [[Реализация булевой функции схемой из функциональных элементов|схемы из функциональных элементов]] называется процедура получения логической схемы, реализующей заданную логическую функцию.
}}

Приведем несколько простейших алгоритмов синтеза схем, реализующих произвольную функцию от <tex> n </tex> аргументов <tex> f(x_{1}, ..., x_{n}) </tex>, в случае когда базис <tex> B = \{\neg, \lor, \land\} </tex>.

==Метод синтеза, основанный на [[СДНФ|совершенной ДНФ]]==

{{Лемма
|id = Lemma1
|about = 1
|statement =Любой конъюнкт в СДНФ можно представить не более, чем <tex> 2n-1 </tex> элементами.
|proof = [[Файл:Synschemes Lemma1.png|250px|thumb|right|Рис 1. Схема для <tex> \bar{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4}</tex>. Сложность построенной схемы <tex>size_{B}(f)=2+3=5\le 7</tex>.]]
Построим данную схему следующим образом: если <tex> i </tex>-й множитель равен <tex> \bar{x}_{i} </tex>, то присоединяем к выходу <tex> i </tex> элемент отрицания и последовательно присоединяем к элементу конъюнкции, иначе просто присоединяем к "свободному" входу элемента конъюнкции.

Очевидно, что сложность построенной схемы <tex> size_{B}(f)= n+n-1 = 2n-1 </tex>.

Поэтому <tex> size_{B}(f)\le 2n-1 </tex>.

Приведем пример для <tex> f=\bar{x}_{1}\wedge x_{2}\wedge x_{3} \wedge \bar{x}_{4}</tex> (рис. 1).

}}

{{Теорема
|id = Th1
|about = 1
|statement = Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex> имеет место неравенство <tex> size_{B}(f)\le n2^{n+1} </tex>
|proof = [[Файл:Synschemes Theorem1.png|250px|thumb|right|Рис. 2]]
Пусть <tex> f(x_{1},...,x_{n}) </tex> {{---}} произвольная [[Определение булевой функции|булева функция]].

Если <tex> f = 0 </tex>, то схема строится в соответствии с представлением <tex> 0=x_{1}\wedge\overline{x}_{1} </tex>, то есть <tex> size_{B}(0) \le 2</tex>.

Если <tex> f \ne 0 </tex>, то <tex> f </tex> может быть задана [[ДНФ|дизъюнктивной нормальной формой]]

::<tex> f(x_{1},...,x_{n}) = K_{1} \vee K_{2} \vee ... \vee K_{s} </tex>,

где <tex> s \le 2^{n} </tex> и каждая конъюнкция имеет вид

::<tex> K_{j}=x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{i} </tex>

Схема <tex> S </tex> для <tex> f </tex> состоит из конъюнкций <tex> K_{j} </tex> (каждая из них в соответствии с [[#Lemma1|леммой 1]] имеет сложность не более <tex> 2n-1 </tex>) и цепочки из <tex> s-1 </tex> элемента дизъюнкции с <tex> s </tex> свободными входами. Свободные входы этой цепочки присоединяются к выходам схем для конъюнкций <tex> K_{j} </tex>.(рис. 2) Имеем

::<tex> size_{B}(f)\le s\cdot(2n-1)+s-1 < s\cdot(2n-1)+s = 2ns \le n2^{n+1} </tex>.

Таким образом, для любой функции <tex> f(x_{1},...,x_{n}) </tex> выполняется неравенство

::<tex> size_{B}(f(x_{1},...,x_{n}))\le n2^{n+1} </tex>.

Поэтому <tex> size_{B}(f)\le n2^{n+1} </tex>.
}}

==Метод синтеза, основанный на более компактной реализации множества всех конъюнкций==

{{Определение

|definition= <tex> f(n) \sim g(n) </tex> означает, что <tex>f</tex> асимптотически эквивалентна <tex>g</tex>, то есть <tex>\lim\limits_{n \to \infty}\frac{f(n)}{g(n)} = 1</tex>
}}

{{Определение
|definition= <tex> f(n) \lesssim g(n) </tex> означает, что <tex>\varlimsup\limits_{n \to \infty}\frac{f(n)}{g(n)} \le 1</tex>
}}

{{Определение
|definition=
Пусть есть булева функция от <tex> n </tex> аргументов <tex> f : \lbrace0, 1\rbrace^n \rightarrow \lbrace0, 1\rbrace </tex> и набор из <tex> n </tex> булевых функций <tex> g_1 \dotsc g_n </tex>, таких что <tex> g_i :\lbrace0, 1\rbrace^{m_i} \rightarrow \lbrace0, 1\rbrace </tex>, где <tex> i=1,\dotsc, n</tex>. Тогда системой булевых функций называется функция <tex> S </tex> от всех аргументов функций <tex> g_i</tex>, которая определяется как

<tex> S(x_{11},\dotsc,x_{1(m_1)},x_{21},\dotsc,x_{2(m_2)}</tex><tex>,\dotsc,x_{n1},\dotsc,x_{n(m_n)})</tex><tex>=f(g_1(x_{11},\dotsc,x_{1(m_1)}),g_2(x_{21},\dotsc,x_{2(m_2}),\dotsc,g_n(x_{n1},\dotsc,x_{n(m_n)}))</tex>
}}
'''Примечание'''

Введем функцию

<tex> x^{\sigma} = \begin{cases}
x, \sigma =1;\\
\overline{x}, \sigma =0
\end{cases}</tex>

{{Лемма
|id = Lemma2
|about = 2
|statement = Пусть <tex> K_{n}(\lbrace x_{1}^{\sigma_{1}},\dotsc,x_{n}^{\sigma_{n}} \rbrace^{2^n}_{i=1}) </tex> {{---}} система всех <tex> 2^{n} </tex> конъюнкций <tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}}</tex>, где каждому <tex> i </tex> соответствует свой набор <tex> \lbrace \sigma_{1},\dotsc,\sigma_{n} \rbrace </tex>, тогда для <tex> K_{n} </tex> имеет место соотношение <tex> size_{B}(K_{n}) \sim 2^n </tex>
|proof = [[Файл:Synschemes Lemma2.png|250px|thumb|right|Рис. 3]]
Конъюнкции <tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}}</tex> соответствуют функциям <tex> g </tex> из определения функции,<tex> K_{n} </tex> соответствует функции <tex> S </tex>, а конъюнкция функций <tex> g </tex> соответствует функции <tex> f </tex>.

Заметим, что на вход схемы подается определенный набор аргументов <tex> x_{1}^{\sigma_{1}},\dotsc,x_{n}^{\sigma_{n}} </tex>, то есть на выходе схемы будет результат конъюнкции этих аргументов.

Разделим цепочки конъюнкций на две части. Каждая конъюнкция <tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}} </tex> может быть представлена в виде конъюнкции двух конъюнкций длины <tex> k </tex> и <tex> n-k </tex> (<tex> k </tex> мы выберем позже):

::<tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}} = (x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{k}^{\sigma_{k}})(x_{k+1}^{\sigma_{k+1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}}) </tex>.

Поэтому схема для <tex> K_{n} </tex> может быть образована из схем для <tex> K_{k}(x_{1}^{\sigma_{1}},\dotsc,x_{k}^{\sigma_{k}}) </tex> и <tex> K_{n-k}(x_{k+1}^{\sigma_{k+1}},\dotsc,x_{n}^{\sigma_{n}}) </tex> и системы из <tex> 2^n </tex> элементов конъюнкции, осуществляющих вышеприведенную операцию, как показано в [[#Th1|теореме 1]] (рис. 3). Левая часть схемы считает конъюнкцию переменных <tex> x_{1}^{\sigma_{1}},\dotsc,x_{k}^{\sigma_{k}} </tex>, а правая часть - переменных <tex> x_{k+1}^{\sigma_{k+1}},\dotsc,x_{n}^{\sigma_{n}}</tex>. Следовательно,

::<tex> size_{B}(K_{n}) \le size_{B}(K_{k}) + size_{B}(K_{n-k}) + 2^n </tex>.

Так как по [[#Th1|теореме 1]] <tex> size_{B}(K_{k}) \le k2^{k+1} </tex> , <tex> size_{B}(K_{n-k}) \le (n-k)2^{n-k+1} </tex>,то

::<tex> size_{B}(K_{n}) \le k2^{k+1} + (n-k)2^{n-k+1} + 2^n </tex>.

Положим <tex> k=[\frac{n}{2}]</tex>. Тогда <tex> k \le \frac{n}{2} </tex>, <tex> n-k \le \frac{n}{2}+1 </tex> и

::<tex> size_{B}(K_{n}) \le \frac{n}{2}2^{\frac{n}{2}+1} + (\frac{n}{2}+1)2^{\frac{n}{2}+2} + 2^n =2^n+O(n2^{\frac{n}{2}})</tex>.

С другой стороны, при <tex> n \ge 2 </tex> каждая конъюнкция реализуется на выходе некоторого элемента, то есть при <tex> n \ge 2 </tex> выполняется неравенство <tex> size_{B}(K_{n}) \ge 2^{n} </tex>. Таким образом,

::<tex> size_{B}(K_{n}) \sim 2^n </tex>.
}}

{{Теорема
|id = Th2
|about = 2
|statement =Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex> имеет место соотношение <tex> size_{B}(f)\lesssim 2^{n+1} </tex>.
|proof =
[[Файл:Synschemes_ NewTheorem2.png|400px|thumb|right|В верхней части схемы рис.2 все подсхемы, вычисляющие конъюнкции, заменили на <tex>K_n</tex>]]
Пусть <tex> f(x_{1},...,x_{n}) </tex> {{---}} произвольная булева функция, <tex> f \ne 0 </tex>. Заменим в схеме (рис. 2) верхнюю часть схемы, реализующую конъюнкции <tex> K_{1} \vee K_{2} \vee ... \vee K_{s} </tex>, схемой, реализующей все конъюнкции из <tex> K_{n} </tex>. Тогда для любой такой функции <tex> f(x_{1},...,x_{n}) </tex> (не равной нулю) имеем

::<tex> size_{B}(f) \le size_{B}(K_{n})+s-1 \le size_{B}(K_{n})+2^{n}-1 \lesssim 2^{n+1} </tex>

Таким образом,

::<tex> size_{B}(f)\lesssim 2^{n+1}. </tex>
}}

==Метод синтеза схем [http://en.wikipedia.org/wiki/Claude_Shannon К.Э.Шеннона]==

{{Теорема
|id = Th3
|about = 3
|statement =Для любой функции <tex> f(x_{1}, ..., x_{n}) </tex> имеет место соотношение <tex> size_{B}(f)\lesssim 12\frac {2^{n}}{n} </tex>.
|proof = [[Файл:Synschemes-Theorem2.png|300px|thumb|right|Рис. 4]]
Пусть <tex> f(x_{1},...,x_{n}) </tex> {{---}} произвольная булева функция. Рассмотрим разложение <tex> f </tex> по переменным <tex> x_{1},...,x_{m} </tex>, где <tex> 1 \le m \le n </tex>:

<tex>f(x_{1},...,x_{n})=\displaystyle\bigvee_{(\sigma_{1},\dotsc,\sigma_{m})}x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{m}^{\sigma_{m}}\wedge f(\sigma_{1},\dotsc,\sigma_{m},x_{m+1},\dotsc,x_{n}) </tex>.

'''Схема для функции <tex> f </tex> строится из трех подсхем: <tex> S_{1},S_{2},S_{3} </tex>. (рис. 4)'''

:1. Система <tex> K_{m} (x_{1}^{\sigma_{1}},\dotsc,x_{m}^{\sigma_{m}}) </tex> содержит всевозможные конъюнкции <tex>x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{m}^{\sigma_{m}}</tex>. И схема <tex> S_{1} </tex> реализует все эти конъюнкции. В силу [[#Lemma2|леммы 2]] выполняется неравенство

::<tex> size_{B}(S_{1}) \le size_{B}(K_{m}) \lesssim 2^{m} </tex>.

:2. Схема <tex> S_{2} </tex> реализует систему <tex> F(x_{m+1}^{\sigma_{m+1}},...,x_{n}^{\sigma_{n}}) </tex> всех булевых функций от всевозможных наборов переменных <tex> x_{m+1},...,x_{n} </tex>. Другими словами, подсхема <tex> S_{2} </tex> вычисляет все булевы функции, зависящие от последних <tex> n - m </tex> переменных. В силу [[#Th1|теоремы 1]]
::<tex> size_{B}(S_{2}) \le (n-m)2^{n-m+1}2^{2^{n-m}} </tex>.

:3. Схема <tex> S_{3} </tex> производит "сборку" в соответствии с разложением функции <tex> f </tex>: для каждого набора <tex> \widetilde{\sigma}=(\sigma_{1},\dotsc,\sigma_{m}) </tex> реализуется конъюнкция

::<tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{m}^{\sigma_{m}}\wedge f(\widetilde{\sigma},x_{m+1},\dotsc, x_{n}) </tex> (<tex> 2^{m} </tex> элементов конъюнкции) и образуется дизъюнкция таких конъюнкций (<tex> 2^{m}-1 </tex> элементов дизъюнкции).

Поэтому выполняется неравенство <tex> size_{B}(S_{3}) \le 2^{m} +2^{m} -1 </tex>. Таким образом,

::<tex> size_{B}(f) \le size_{B}(S_{1})+size_{B}(S_{2})+size_{B}(S_{3}) \lesssim 3 \cdot 2^{m} +(n-m)2^{n-m+1}2^{2^{n-m}} </tex>.

Положим <tex> k=n-m </tex>. Тогда

::<tex> size_{B}(f) \lesssim 3 \cdot 2^{n-k} +k2^{k+1}2^{2^{k}} </tex>.

Заметим, что второе слагаемое "очень быстро" растет с ростом <tex> k </tex>, а первое слагаемое убывает с ростом <tex> k </tex> медленней. Поэтому следует взять такое значение <tex> k </tex>, при котором первое и второе слагаемые приблизительно равны, и потом немного уменьшить <tex> k </tex>. Тогда второе слагаемое "сильно" уменьшится, а первое "не очень сильно" возрастет. Возьмем, например, <tex> k=\log_{2}n </tex>. Тогда

::<tex> 3 \cdot 2^{n-k} = 3 \cdot \frac{2^{n}}{n} </tex>,

::<tex> k \cdot 2^{k+1} \cdot 2^{2^{k}}=\log_{2}n\cdot (2n)\cdot 2^{n}</tex>,

то есть получили "слишком много". Возьмем <tex> k </tex> на единицу меньше: <tex> k=\log_{2}n-1 </tex>. Тогда

::<tex> 3 \cdot 2^{n-k} = 3 \cdot \frac{2^{n}}{n} \cdot 2 </tex>,

::<tex> k \cdot 2^{k+1} \cdot 2^{2^{k}}=(\log_{2}n-1)\cdot n\cdot 2^{\frac{n}{2}}</tex>.

Вспомним теперь, что <tex> k </tex> должно быть целым числом, и положим <tex> k=[\log_{2}n-1] </tex>. Тогда
<tex> n-k < n- \log_{2} + 2</tex>,

::<tex> 3 \cdot 2^{n-k} < 12 \cdot \frac {2^{n}}{n} </tex>,

::<tex> k\cdot 2^{k+1}\cdot 2^{2^{k}} \le (\log_{2}-1)\cdot n\cdot 2^{\frac{n}{2}} </tex>.

При этом выборе <tex> k </tex> окончательно имеем

::<tex> size_{B}(n)\lesssim 12\frac {2^{n}}{n} </tex>.
}}

== Литература ==
* Яблонский С.В. Введение в дискретную математику. — 4-е изд. — М.: Высшая школа, 2003. — 384 с. — ISBN 5-06-004681-8

[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Схемы из функциональных элементов ]]

Полином Жегалкина

2016-01-18T07:43:09Z

5.18.154.236: /* Преобразование Мёбиуса */ Так вроде понятней.

'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') — полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве средства для представления [[Определение булевой функции|функций булевой логики]]. Полином Жегалкина имеет следующий вид:

<tex>P = a_{000...000} \oplus a_{100...0} x_1 \oplus a_{010...0} x_2 \oplus ... \oplus a_{00...01} x_n \oplus a_{110...0} x_1 x_2 \oplus ... \oplus a_{00...011} x_{n-1} x_n \oplus ... \oplus a_{11..1} x_1 x_2 ... x_n </tex>

== Полнота ==

По [[Теорема Поста о полной системе функций|теореме Поста]], чтобы система булевых функций была полной, надо, чтобы в ней существовали

#Хотя бы одна функция, не сохраняющая <tex>0</tex>;
#Хотя бы одна функция, не сохраняющая <tex>1</tex>;
#Хотя бы одна нелинейная функция;
#Хотя бы одна немонотонная функция;
#Хотя бы одна несамодвойственная функция.

Исходя из этого, система функций <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex> является полной:

{| class="wikitable" style="width:8cm" border="1"
|-align="center" bgcolor=#EEEEFF
!<tex>x_0</tex>||<tex>x_1</tex>||<tex>\dots</tex>||<tex>x_n</tex>
|<tex>1</tex>||<tex>\land</tex>||<tex>\oplus</tex>
|-align="center"
!<tex>0</tex>||<tex>0</tex>||<tex>\dots</tex>||<tex>0</tex>
|<tex>1</tex>||<tex>0</tex>||<tex>0</tex>
|-align="center"
!<tex>1</tex>||<tex>0</tex>||<tex>\dots</tex>||<tex>0</tex>
|<tex>1</tex>||<tex>0</tex>||<tex>1</tex>
|-align="center"
!<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>
|<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>
|-align="center"
!<tex>1</tex>||<tex>1</tex>||<tex>\dots</tex>||<tex>1</tex>
|<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|Сохраняет 0
|<tex>0</tex>||<tex>1</tex>||<tex>1</tex>
|-align="center"
!colspan="4"|Сохраняет 1
|<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|Самодвойственная
|<tex>0</tex>||<tex>0</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|Монотонная
|<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|Линейная
|<tex>1</tex>||<tex>0</tex>||<tex>1</tex>
|}

На основе этой системы и строятся полиномы Жегалкина.

== Существование и единственность представления (теорема Жегалкина) ==
{{Теорема
|author=Жегалкина
|statement=
Каждая булева функция единственным образом представляется в виде полинома Жегалкина.
|proof=
Заметим, что различных булевых функций от <tex>n</tex> переменных <tex>2^{2^n}</tex> штук. При этом конъюнкций вида <tex>x_{i_1} \ldots x_{i_k}</tex> существует ровно <tex>2^n</tex>, так как из <tex>n</tex> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит <tex>0</tex> или <tex>1</tex>, то есть существует <tex>2^{2^n}</tex> различных полиномов Жегалкина от <tex>n</tex> переменных.

Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.
}}

== Построение полинома Жегалкина ==

Существует несколько способов построения полинома Жегалкина.

=== По таблице истинности ===
Пусть для функции <tex>f(x_1,x_2,\dots,x_n)</tex> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что <tex> a \oplus 1 = \bar{a}</tex>, а <tex> a \oplus 0 = a</tex>. За каждую подстановку находим только один коэффициент.

'''Пример:'''
Дана функция <tex>f(x_1,x_2,x_3,x_4)</tex> и её таблица истинности:

{| class="wikitable" style="width:8cm" border="1"
|-
!class="dark" style="font-weight:normal"| <tex>x_1</tex>
!class="dark" style="font-weight:normal"| <tex>x_2</tex>
!class="dark" style="font-weight:normal"| <tex>x_3</tex>
!class="dark" style="font-weight:normal"| <tex>x_4</tex>
!class="dark" style="font-weight:normal"| <tex>f(x_1,x_2,x_3,x_4)</tex>
|- align="center"
||0||0||0||0||0
|- align="center"
||0||0||0||1||0
|- align="center"
||0||0||1||0||0
|- align="center"
||0||0||1||1||0
|- align="center"
||0||1||0||0||0
|- align="center"
||0||1||0||1||0
|- align="center"
||0||1||1||0||1
|- align="center"
||0||1||1||1||0
|- align="center"
||1||0||0||0||1
|- align="center"
||1||0||0||1||0
|- align="center"
||1||0||1||0||0
|- align="center"
||1||0||1||1||1
|- align="center"
||1||1||0||0||1
|- align="center"
||1||1||0||1||0
|- align="center"
||1||1||1||0||1
|- align="center"
||1||1||1||1||0
|}
Построим для неё полином Жегалкина:

<tex>f(x_1,x_2,x_3,x_4) = a_{0000} \oplus a_{1000} x_1 \oplus a_{0100} x_2 \oplus a_{0010} x_3 \oplus a_{0001} x_4 \oplus a_{1100} x_1 x_2 \oplus a_{1010} x_1 x_3 \oplus a_{1001} x_1 x_4 \oplus a_{0110} x_2 x_3 \oplus a_{0101} x_2 x_4 \oplus a_{0011} x_3 x_4 \oplus a_{1110} x_1 x_2 x_3 \oplus a_{1101} x_1 x_2 x_4 \oplus a_{1011} x_1 x_3 x_4 \oplus a_{0111} x_2 x_3 x_4 \oplus a_{1111} x_1 x_2 x_3 x_4</tex>

Так как <tex>f(0,0,0,0) = 0</tex>, то <tex>a_{0000} = 0</tex>.
Далее подставляем все остальные наборы в порядке возрастания числа единиц, подставляя вновь полученные значения в следующие формулы:

<tex>f(1,0,0,0) = a_{0000} \oplus a_{1000} = 1 \Rightarrow a_{1000} = 1</tex>

<tex>f(0,1,0,0) = a_{0000} \oplus a_{0100} = 0 \Rightarrow a_{0100} = 0</tex>

<tex>f(0,0,1,0) = a_{0000} \oplus a_{0010} = 0 \Rightarrow a_{0010} = 0</tex>

<tex>f(0,0,0,1) = a_{0000} \oplus a_{0001} = 0 \Rightarrow a_{0001} = 0</tex>

<tex>f(1,1,0,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{1100} = 1 \Rightarrow a_{1100} = 0</tex>

<tex>f(1,0,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{1010} = 0 \Rightarrow a_{1010} = 1</tex>

<tex>f(1,0,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{1001} = 0 \Rightarrow a_{1001} = 1</tex>

<tex>f(0,1,1,0) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0110} = 1 \Rightarrow a_{0110} = 1</tex>

<tex>f(0,1,0,1) = a_{0000} \oplus a_{0100} \oplus a_{0001} \oplus a_{0101} = 0 \Rightarrow a_{0101} = 0</tex>

<tex>f(0,0,1,1) = a_{0000} \oplus a_{0010} \oplus a_{0001} \oplus a_{0011} = 0 \Rightarrow a_{0011} = 0</tex>

<tex>f(1,1,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{1100} \oplus a_{1010} \oplus a_{0110} \oplus a_{1110} = 1 \Rightarrow a_{1110} = 0</tex>

<tex>f(1,1,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0001} \oplus a_{1100} \oplus a_{1001} \oplus a_{0101} \oplus a_{1101} = 0 \Rightarrow a_{1101} = 0</tex>

<tex>f(1,0,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0010} \oplus a_{0001} \oplus a_{1010} \oplus a_{1001} \oplus a_{0011} \oplus a_{1011} = 1 \Rightarrow a_{1011} = 0</tex>

<tex>f(0,1,1,1) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{0111} = 0 \Rightarrow a_{0111} = 1</tex>

<tex>f(1,1,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{1100} \oplus a_{1010} \oplus a_{1001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{1110} \oplus a_{1101} \oplus a_{1011} \oplus a_{0111} \oplus a_{1111} = 0 \Rightarrow a_{1111} = 1</tex>

Таким образом, полином Жегалкина выглядит так:

<tex>f(x_1,x_2,x_3,x_4) = x_1 \oplus x_1 x_3 \oplus x_1 x_4 \oplus x_2 x_3 \oplus x_2 x_3 x_4 \oplus x_1 x_2 x_3 x_4</tex>

=== Преобразование [[Определение_булевой_функции#Дизъюнктивная нормальная форма (ДНФ)|дизъюнктивной нормальной формы]] ===
Этот способ основан на том, что <tex> X \oplus 1 = \bar{X} </tex>. Если функция задана в виде ДНФ, то можно сначала убрать дизъюнкцию, используя правило Де-Моргана, а все отрицания заменить прибавлением единицы по модулю два, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю (так как <tex> X \oplus X = 0 </tex>), а нечетное число одинаковых слагаемых равно одному такому слагаемому. Либо же можно заменить дизъюнкцию по следующему правилу:
<tex> A \lor B = AB \oplus A \oplus B </tex>   <tex> (1) </tex>.

Если функция задана в СДНФ, то так как при любых значениях входных переменных в единицу обращается не более одного члена выражения, то достаточно просто заменить все дизъюнкции исключающим ИЛИ.

'''Пример:'''
Дана функция в ДНФ <tex> f(x_1,x_2,x_3,x_4) = (x_1 \land x_2 \land \neg x_3 \land x_4) \lor (\neg x_1 \land \neg x_4) \lor (x_1 \land x_2) \lor x_2 </tex>, построим полином Жегалкина.

Запишем функцию так:

<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 + \neg x_1 \neg x_4 + x_1 x_2 + x_2</tex>;

Сгруппируем слагаемые и воспользуемся преобразованием (1):

<tex>f(x_1,x_2,x_3,x_4) = (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_1 x_2 \neg x_3 x_4 \neg x_1 \neg x_4) + (x_1 x_2 \oplus x_2 \oplus \oplus x_1 x_2 x_2)</tex>

Воспользуемся свойствами конъюнкции <tex>A \land A = A</tex> и <tex>\neg A \land A = 0</tex>, а также тем, что <tex>A \oplus A = 0</tex>, и упростим выражение:

<tex>f(x_1,x_2,x_3,x_4) = (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4) + x_2</tex>

Ещё раз воспользуемся преобразованием (1):

<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_2 \oplus (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4) x_2</tex>

Раскроем скобку по алгебраическим правилам:

<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_2 \oplus x_1 x_2 x_2 \neg x_3 x_4 \oplus \neg x_1 x_2 \neg x_4</tex>

Снова воспользуемся свойствами конъюнкции и исключающего ИЛИ:

<tex>f(x_1,x_2,x_3,x_4) = \neg x_1 \neg x_4 \oplus x_2 \oplus \neg x_1 x_2 \neg x_4</tex>

Заменим отрицание на прибавление <tex>1</tex>:

<tex>f(x_1,x_2,x_3,x_4) = (x_1 \oplus 1) (x_4 \oplus 1) \oplus x_2 \oplus (x_1 \oplus 1) x_2 (x_4 \oplus 1)</tex>

Раскроем скобки:

<tex>f(x_1,x_2,x_3,x_4) = x_1 x_4 \oplus x_1 \oplus x_4 \oplus 1 \oplus x_2 \oplus x_1 x_2 x_4 \oplus x_1 x_2 \oplus x_2 x_4 \oplus x_2</tex>

Выкинем парные слагаемые и получим окончательную формулу:

<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 \oplus x_4 \oplus 1</tex>

=== Метод треугольника === 
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
# Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от <tex>000\dots00</tex> до <tex>111\dots11</tex>.
# Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
# Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
# Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
# Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке <tex>111</tex> соответствует член <tex>ABC</tex>, ячейке <tex>101</tex> — член <tex>AC</tex>, ячейке <tex>010</tex> — член <tex>B</tex>, ячейке <tex>000</tex> — член <tex>1</tex> и т.д.
# Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.

Фактически, этот метод является модификацией метода построения по таблице истинности, описанного выше. По сравнению с ним он удобнее тем, что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций.

Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных <tex>P(A,B,C)</tex> показан на рисунке.

[[Файл:Преобразование таблицы истинности в полином Жегалкина методом треугольника.gif]]

Чтобы получить формулу, по которой рассчитывается какой-либо коэффициент, нужно из клетки, в которой он записан, пройтись всеми возможными путями влево, до столбца <tex>''P''</tex> таблицы истинности, делая ходы влево и влево-вниз, записать значения в конечных ячейках и сложить их все между собой по модулю 2.

Таким образом, в первом столбце сверху записан коэффициент <tex> a_0 = P(0,0,0) </tex>,

во втором — <tex> a_1 = P(0,0,0) \oplus P(0,0,1) </tex>,

в третьем — <tex> a_2 = P(0,0,0) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,1,0) = P(0,0,0) \oplus P(0,1,0) </tex>,

в четвёртом —

<tex> a_3 = P(0,0,0) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,1) = P(0,0,0) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,1), </tex>

и так далее, то есть при построении вспомогательной таблицы коэффициенты полинома просчитываются автоматически.

=== Преобразование Мёбиуса ===
Пусть задана [[Определение булевой функции|булева функция]] <tex>f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}</tex>.
Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.

Пусть <tex> i = (i_1, i_2, .. i_n), \;\; i_k \in \{0 ; 1\}</tex>, и введем обозначение <tex> x ^{i_k} \sim \left\{\begin{matrix} x, \;\; i_k=1
\\ 1, \;\; i_k=0
\end{matrix}\right. </tex>

Тогда полином Жегалкина можно записать как:
<tex> f(x) = \bigoplus\limits_i \alpha_i \cdot x_1^{i_1} \cdot x_2^{i_2} \cdot</tex><tex>\dots</tex><tex>\cdot x_n^{i_n}</tex>, где <tex>\alpha_i \in \{ 0; 1 \}</tex>.

Множество коэффициентов <tex>\{\alpha _i\}</tex> можно рассматривать как функцию <tex>\alpha</tex>, заданной на множестве индексов <tex> i = (i_1, i_2, \dots i_n)</tex>, то есть <tex>\alpha: i \mapsto \alpha_i</tex>.

Очевидно, функцию <tex> f </tex> можно записать и следующим образом: <tex> f(x) = \bigoplus \limits_i \alpha_i \cdot [x_1 , \; </tex> если <tex> \;\; i_1] \cdot [x_2 , \; </tex> если <tex> \;\; i_2] \cdot</tex><tex>\dots</tex><tex>\cdot [x_n , \; </tex> если <tex> \;\; i_n]</tex>.

Тут запись <tex>[x_k , \; </tex> если <tex> \; i_k]</tex> означает, что элелемент <tex> x_k </tex> присутствует в соответствующем члене полинома только если <tex> i_k = 1 </tex>.
Тогда если для какого-то <tex>x</tex>, <tex>i \succ x</tex>* ,то в слагаемом будет существовать хотя бы один множитель, равный нулю, и такое слагаемое на сумму не повлияет.
Отсюда ясно, что <tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha_i </tex>  <tex> (2) </tex>
Найдем отображение <tex> f \mapsto \alpha</tex> (То есть такое, которое по заданной функции вычисляет значения всех коэффициентов).

<tex>*</tex> <tex>i \succ x</tex> обозначает, что <tex>x</tex> "меньше" <tex>i</tex> как последовательность бит

{{Теорема
|statement=Пусть задана функция <tex> f </tex>. Тогда функцию <tex> \alpha_x </tex> можно найти по формуле: <tex>\alpha_x = \bigoplus \limits_{j\preceq x} f(j)</tex>     <tex> (3) </tex>.
||proof=Докажем при помощи индукции по количеству единиц в векторе <tex> x </tex> ( иначе говоря, по сумме <tex>x_1+x_2+</tex><tex>\dots</tex><tex>+x_n</tex> ) и для удобства обозначим это количество единиц(сумму) <tex> wt(x) </tex>.

'''1)''' База: если <tex> x = 0 </tex>, то, очевидно <tex> f(0) = \alpha_0 </tex>

'''2)''' Пускай теорема справедлива для всех сумм <tex>wt(x) < k</tex>. Покажем, что в таком случае она верна и для <tex>wt(x) = k</tex>. По <tex> (2) </tex>, а далее по предположению индукции видим: <tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha_i = \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] \oplus \alpha_x</tex> .

Рассмотрим сумму <tex> \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] </tex>. Каждый элемент <tex> f(j) </tex> содержится в ней, только если <tex> j \prec x </tex>, и для фиксированных <tex> j</tex> и <tex> x </tex> элемент <tex> f(j)</tex> встречается ровно столько раз, сколько существует <tex> i </tex> , таких, что <tex> j \prec i \prec x</tex>. Несложно увидеть, что таких <tex> i </tex> существует ровно <tex> 2^{wt(x)-wt(j)}-1 </tex>, то есть нечетное количество раз. Тогда <tex> \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] = \bigoplus \limits_{j\prec x} f(j) </tex>.
Но тогда <tex> f(x) = \left [ \bigoplus \limits_{j\prec x} f(j) \right ] \oplus \alpha_x \Leftrightarrow f(x) \oplus \bigoplus \limits_{j\prec x} f(j) = \alpha_x \Leftrightarrow \alpha_x = \bigoplus \limits_{j\preceq x} f(j)</tex>.
То есть при <tex>wt(x) = k</tex> формула также выполняется, значит при любых <tex> x </tex> выполняется <tex>\alpha_x = \bigoplus \limits_{j\preceq x} f(j)</tex>.

}}
Отображение <tex> f \rightarrow \alpha</tex> также называется преобразованием Мёбиуса.

Видно, что <tex> (2) </tex> и <tex> (3) </tex> — это одно и тоже преобразование. Значит, если применить преобразование Мёбиуса к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex>f</tex>. То есть преобразование Мёбиуса обратно самому себе, иными словами, является инволюцией.

== Источники информации ==

* [http://www.stat-mat.com/?p=330 Cтатистика | Математика НГУ]
* [http://ru.wikipedia.org/wiki/Полином_Жегалкина Википедия {{---}} Полином Жегалкина]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская, дискретная математика]
* Логачёв О.А, Сальников А.А., Ященко В.В. Булевы фунции в теории кодирования и криптологии — МЦНМО, 2004. - 470с. — ISBN 5-94057-117-4.

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции]]

Полные системы функций. Теорема Поста о полной системе функций

2016-01-18T06:01:18Z

5.18.154.236: Исправлена опечатка

== Полные системы функций ==
{{Определение
|definition=
Если любая [[Определение булевой функции|булева функция]], являющаяся [[Суперпозиции|суперпозицией]] функций некоторого множества, принадлежит этому множеству, то такое множество называют '''замкнутым''' (англ. ''closed set'').}}

{{Определение
|definition=
'''Замыканием''' (англ. ''сlosure'') множества функций называется такое подмножество всех булевых функций, что любую из этих функций можно выразить через функции исходного множества.}}

{{Определение
|id=def1
|definition=
Множество булевых функций называется '''полной системой''' (англ. ''complete set''), если замыкание этого множества совпадает с множеством всех функций.}}

{{Определение
|definition=
Полная система функций называется '''безызбыточной''' (англ. ''irredundant functions''), если она перестает быть полной при исключении из неё любого элемента.
}}

Американский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:
* Функции, сохраняющие константу <Tex>T_0</Tex> и <Tex>T_1</Tex>
* Самодвойственныые функции <Tex>S</Tex>
* Монотонные функции <Tex>M</Tex>
* Линейные функции <Tex>L</Tex>

== Замкнутые классы булевых функций ==
Класс функций сохраняющих ноль <tex>T_0</tex>.
{{Определение
|definition=Говорят, что функция '''сохраняет ноль''', если <tex>f(0, 0, \dots, 0) = 0</tex>.
}}

Класс функций сохраняющих единицу <tex>T_1</tex>.
{{Определение
|definition=Говорят, что функция '''сохраняет один''', если <tex>f(1, 1, \dots, 1) = 1</tex>.
}}

Класс самодвойственных функций <tex>S</tex>.
{{Определение
|definition=Говорят, что функция '''самодвойственна''' (англ. ''self-dual''), если <tex>f(\overline{x_1},\dots,\overline{x_n})=\overline{f(x_1,\dots,x_n)}</tex>. Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.
}}

Класс монотонных функций <tex>M</tex>.
{{Определение
|definition=Говорят, что функция '''монотонна''' (англ. ''monotonic function'') , если <tex>\forall i (a_i \leqslant b_i) \Rightarrow f(a_1,\dots,a_n)\leqslant f(b_1,\dots,b_n)</tex>.
}}

Класс линейных функций <tex>L</tex>.
{{Определение
|definition=Говорят, что функция '''линейна''' (англ. ''linear function''), если существуют такие <tex>a_0, a_1, a_2, \dots, a_n</tex>, где <tex>a_i \in \{0, 1\}, \forall i=\overline{1,n}</tex>, что для любых <tex>x_1, x_2, \dots, x_n</tex> имеет место равенство:
:<tex>f(x_1, x_2, \dots, x_n) = a_0\oplus a_1\cdot x_1\oplus a_2\cdot x_2 \oplus\dots\oplus a_n\cdot x_n</tex>.
}}
Количество линейных функций от <tex>n</tex> переменных равно <tex>~2^{n+1}</tex>.

Функция является линейной тогда, и только тогда, когда в ее [[Полином_Жегалкина|полиноме Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].

== Формулировка и доказательство критерия Поста ==
{{
Теорема|statement=
Набор булевых функций K является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

|proof=

===== Необходимость. =====

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор К не мог бы быть полным.

===== Достаточность. =====
# Рассмотрим функцию, не сохраняющую ноль {{---}} <tex>f_0</tex>. (<tex>f_0(0) = 1</tex>) <tex>f_0(1)</tex> может принимать два значения:
## <tex>f_0(1) = 1</tex>, тогда <tex>f_0(x, x, x, \ldots, x) = 1</tex>.
## <tex>f_0(1) = 0</tex>, тогда <tex>f_0(x, x, x, \dots, x) = \neg x</tex>.
# Рассмотрим функцию, не сохраняющую один {{---}} <tex>f_1</tex>. (<tex>f_1(1) = 0</tex>) <tex>f_1(0)</tex> может принимать два значения:
## <tex>f_1(0) = 0</tex>, тогда <tex>f_1(x, x, x, \ldots, x) = 0</tex>.
## <tex>f_1(0) = 1</tex>, тогда <tex>f_1(x, x, x, \ldots, x) = \lnot x</tex>.

''Таким образом, возможны четыре варианта:''

* Мы получили функцию <tex> \neg </tex>.
Используем несамодвойственную функцию <tex>f_s</tex>. По определению, найдется такой вектор <tex>x_0</tex>, что <tex>f_s(x_0) = f_s(\lnot x_0)</tex>. Где <tex>x_0 = (x_{01}, x_{02}, ..., x_{0k})</tex>.

Рассмотрим <tex>f_s(x^{x_{01}}, x^{x_{02}}, \ldots, x^{x_{0k}})</tex>, где либо <tex>x^{x_{0i}} = x</tex>, при <tex>x_{0i} = 1</tex>. Либо <tex>x^{x_{0i}} = \lnot x</tex>, при <tex>x_{0i} = 0 </tex>.
Нетрудно заметить, что <tex>f_s(0) = f_s(1) \Rightarrow f_s = \operatorname {const}</tex>.
Таким образом мы получили одну из констант.

*Мы получили <tex> \neg </tex> и <tex>0</tex>. <tex>\lnot 0 = 1</tex>.
*Мы получили <tex> \neg </tex> и <tex>1</tex>. <tex>\lnot 1 = 0</tex>.
*Мы получили <tex>1</tex> и <tex>0</tex>.

Рассмотрим немонотонную функцию <tex>f_m</tex>. Существуют такие <tex>x_1, x_2, \ldots, x_n</tex>, что <tex>f_m(x_1, x_2, \ldots, x_{i-1}, 0 , x_{i+1}, \ldots, x_n) = 1</tex>, <tex>f_m(x_1, x_2, \ldots, x_{i-1}, 1 , x_{i+1}, \ldots, x_n) = 0</tex>, зафиксируем все <tex>x_1, x_2, \ldots, x_n</tex>, тогда <tex>f_m(x_1, x_2, \ldots, x_{i-1}, x, x_{i+1}, \ldots, x_n)= \lnot x</tex>.

''В итоге имеем три функции:'' <tex> \neg </tex>, <tex>0</tex>, <tex>1</tex>.

Используем нелинейную функцию <tex>f_l</tex>. Среди нелинейных членов <tex>f_l</tex> (ее представления в виде [[Полином Жегалкина|полинома Жегалкина]]), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем <tex>x_1</tex> и <tex>x_2</tex>. Все элементы, не входящие в данный член, примем равными нулю.
Тогда эта функция будет представима в виде <tex>g_l = x_1 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus ~1]</tex>, где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).

''Рассмотрим несколько вариантов:''

# Присутствует член <tex>\oplus ~1</tex>. Возьмем отрицание от <tex>g_l</tex> и член <tex>\oplus ~1</tex> исчезнет.
# Присутствуют три члена, без <tex>\oplus ~1</tex>: <tex>g_l= x_1 \land x_2 \oplus x_1 \oplus x_2</tex>. Составив таблицу истинности для этой функции нетрудно заметить, что она эквивалентна функции <tex> \vee </tex>.
# Присутствуют два члена, без <tex>\oplus ~1</tex>. Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции <tex>g_l</tex> будет состоять только из одного члена. Если это так, то не составляет труда выразить <tex> \wedge </tex> через <tex> \neg </tex> и <tex>g_l</tex>. Например, если функция <tex>g_l(x_1, x_2, ..., x_n)</tex> принимает истинное значение, когда аргументы c номерами <tex>i_1, i_2, ..., i_m</tex> ложны, а все остальные истины, то функцию <tex> \wedge </tex> можно выразить как <tex>g_l([\lnot]x_1, [\lnot]x_2, ..., [\lnot]x_n)</tex>, где <tex>\lnot</tex> ставится перед аргументами с номерами <tex>i_1, i_2, ..., i_m</tex>.
# Присутствует один член. Выразим <tex> \wedge </tex> через <tex> \neg </tex> и <tex>g_l</tex> аналогично пункту 3.

В итоге получим функцию<tex> \neg </tex>, а также либо функцию <tex> \wedge </tex>, либо функцию <tex> \vee </tex>. Поскольку функцию <tex> \wedge </tex> можно выразить через <tex> \vee </tex> и <tex> \neg </tex>, а функцию <tex> \vee </tex> через <tex> \wedge </tex> и <tex> \neg </tex>, то мы получили базис <tex> \wedge </tex>, <tex> \vee </tex>, <tex> \neg </tex>. Любую булеву функцию, не равную тождественному нулю, можно представить в форме [[СДНФ]], то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде <tex>x \land \lnot x</tex>.

''Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K {{---}} полная система функций, что и требовалось доказать.''
}}

== Примеры ==
Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <tex>T_0</tex>, <tex>T_1</tex>, <tex>S</tex>, <tex>M</tex>, <tex>L</tex>.

В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать [[Определение_булевой_функции#.D0.91.D0.B8.D0.BD.D0.B0.D1.80.D0.BD.D1.8B.D0.B5_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B8|штрих Шеффера]] или [[Определение_булевой_функции#.D0.91.D0.B8.D0.BD.D0.B0.D1.80.D0.BD.D1.8B.D0.B5_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B8|стрелку Пирса]].

Широко известны такие полные системы булевых функций:
* <tex>\left\{\land,\lor,\neg\right\}</tex> (конъюнкция, дизъюнкция, отрицание);
* <tex>\left\{\land,\oplus,1\right\}</tex> (конъюнкция, сложение по модулю два, константа один).
Первая система используется, например, для представления функций в виде [[СДНФ|дизъюнктивных]] и [[СКНФ|конъюнктивных нормальных форм]], вторая — для представления в виде [[Полином Жегалкина|полиномов Жегалкина]].

Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты системы.

Максимально возможное число булевых функций в базисе — четыре.

Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций.

== Источники ==

* [http://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D1%82%D0%B5%D1%80%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0 Википедия — Критерий Поста]
* [http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BC%D0%BA%D0%BD%D1%83%D1%82%D1%8B%D0%B5_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D1%8B_%D0%B1%D1%83%D0%BB%D0%B5%D0%B2%D1%8B%D1%85_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9 Википедия — Замкнутые классы булевых функций]
* Образовательный сайт [http://mini-soft.ru/nstu/diskr/7_.php MiniSoft]
* [http://en.wikipedia.org/wiki/Post%27s_lattice Post's lattice]
* [http://www.mielt.ru/dir/cat14/subj266/file299/view1397.html Лекции по дискретной математике]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции]]