http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=VictorMinsky&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T17:30:46ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B5_%D0%BA%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B5_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D1%8B&diff=82330Квантовые конечные автоматы2022-05-24T23:19:44Z<p>VictorMinsky: small fix</p>
<hr />
<div>Неформально говоря квантовый конечный автомат {{---}} это квантовый аналог ''конечного автомата'', который использует [[Квантовые гейты | квантовые гейты]]. Такие автоматы позволяют допускать некотые языки, имея при этом экспоненциально меньший размер, чем обычные автоматы.<br />
<br />
== Определение ==<br />
<br />
{{Определение<br />
|definition=<br />
'''Квантовый конечный автомат (ККА)''' (англ. ''Quantum finite automata'', ''QFA'') {{---}} это кортеж : <tex>(Q,\Sigma, V, q_0, Q_a, Q_r)</tex>, где<br />
* <tex>Q</tex> — множество состояний автомата,<br />
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова,<br />
* <tex>V</tex> — функция перехода автомата,<br />
* <tex>q_0</tex> — начальное состояние автомата,<br />
* <tex>Q_a \subset Q</tex> — множество допускающих состояний,<br />
* <tex>Q_r \subset Q</tex> — множество опровергающих состояний,<br />
* <tex>Q_{non} = Q \setminus (Q_a \bigcup Q_r), Q_{non} \subset Q </tex> — множество промежуточных состояний.<br />
}}<br />
<br />
Кроме того, ККА является частным случаем ''Геометрического конечного автомата'' и ''Топологического конечного автомата''<ref>[https://en.wikipedia.org/wiki/Quantum_finite_automata#Geometric_generalizations Wikipedia {{---}} Geometric generalizations]</ref>. <br />
<br />
===Принцип работы=== <br />
* На вход подается строчка <tex> s = \langle a_0, a_1,\dots ,a_k \rangle, a_i \in \Sigma</tex>. <br />
* На выходе мы получаем число <tex> Pr(s)</tex>, являющееся вероятностью данного конечного автомата быть в допускающем состоянии.<br />
<br />
==Типы ККА==<br />
* Первый тип {{---}} '''односторонние''' ККА. Они двигают только в одном направлении. Главная особенность односторонних ККА {{---}} допускать большинство регулярных языков. Также односторонние ККА делятся на Одномерные ККА и Многомерные ККА.<br />
* Второй тип {{---}} '''двухсторонние''' ККА. По аналогии с односторонним, они могу двигаться в обоих направлениях и их свойство {{---}} допускать нерегулярные языкы.<br />
<br />
== Описание ==<br />
<br />
Для первоначального описание ККА воспользуемся следующим примером. Пусть у нас есть графовое представление [[Детерминированные конечные автоматы|ДКА]] и пусть в нем <tex>N</tex> вершин, и все вершины пронумерованы. Тогда для представления такого графа можно воспользоваться набором [[Матрица смежности графа|матриц смежности]] таких, что каждая матрица размера <tex>[N \times N]</tex> и что каждому символу <tex>c \in \Sigma</tex> сопоставляется единственная матрица из этого набора. Каждая матрица состоит из <tex>0</tex> и <tex>1</tex>, причём <tex>1</tex> означает переход из состояния <tex>i</tex> в <tex>j</tex> по символу <tex>c</tex>, а <tex>0</tex> {{---}} его отсутствие. В этом случае, текущее состояние автомата записывается как вектор, размерности <tex>N</tex>, в котором будет лишь одна единица, обозначающая текущее положение состояния. При помощи такого описания можно легко делать переходы из нынешнего состояние в новое состояние по символу <tex> c \in \Sigma</tex> обыкновенным ''умножением матриц''. <br />
<br />
Пусть у нас есть ДКА с <tex>N</tex> вершинами и его <tex>\Sigma=\{c_1, c_2, c_3, \dots\}</tex>. Тогда по описанному определению можно составить матрицы смежности <tex>\{U_\alpha \mid \alpha \in \Sigma \}</tex> размерности <tex>[N \times N]</tex>. Также введем <tex>N</tex>-размерный вектор <tex>q \in Q</tex>, описывающий состояние ДКА, a <tex>q_0</tex> {{---}} начальное состояние автомата. Тогда для перехода из состояния <tex>q_0</tex> в <tex>q</tex> по строчке <tex> s = \langle \alpha_0, \alpha_1,\dots \rangle</tex> нужно воспользоваться правилом умножения матриц из линейной алгебры : <tex>q = \cdots U_{\alpha_1} U_{\alpha_0} q_0.</tex><br />
<br />
Описанное выше по сути и является ККА, но в <tex>q</tex> записываются амплитуды вероятностей<ref>[https://en.wikipedia.org/wiki/Probability_amplitude Wikipedia {{---}} Probability amplitude]</ref> такие, что <tex>|q|^2 = 1</tex> , a матрицы <tex>\{U_\alpha\}</tex> {{---}} [[Унитарный и ортогональный операторы| унитарные матрицы]], причем такие матрицы могут не только состоять из <tex>0</tex> и <tex>1</tex>, но и состоять из комплексных чисел. <br />
Для ККА характерна геометрическая интерпретация в пространстве <tex>CP^N</tex>. С этой стороны вектор <tex>q</tex> является точкой, a <tex>\{U_\alpha\}</tex> {{---}} операторы эволюции в представлении Шредингера <ref>[https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%B4%D1%81%D1%82%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%A8%D1%80%D1%91%D0%B4%D0%B8%D0%BD%D0%B3%D0%B5%D1%80%D0%B0 Википедия {{---}} Представление Шрёдингера]</ref>.<br />
<br />
Кроме того, можно упомянуть несколько особенностей ККА: <br />
<br />
* НКА. Из-за свойства НКА в векторе <tex>q</tex> и в столбцах матриц <tex>\{U_\alpha\}</tex> может находиться несколько <tex>1</tex>. Если в этом случае рассмотреть [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона|алгоритм Томпсона]], то построенные на их основе Квантовые конечные автоматы не будут эквивалентны. Эта проблема является одной из научно-исследовательских задач в теории ККА.<br />
<br />
* Вероятностный конечный автомат. Для его построения нужно всего лишь в ККА использовать стохастические матрицы<ref>[https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%BE%D1%85%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0 Википедия {{---}} Стохастическая матрица]</ref> для <tex>\{U_\alpha\}</tex> и вектор вероятностей состояний для <tex>q</tex>. Одно из свойств <tex>q</tex> {{---}} сумма всех элементов равна <tex>1</tex>, и для того, чтобы во всех переходах сохранялось это свойство, и нужны стохастические матрицы.<br />
<br />
* Марковская цепь. При вводе строчек <tex>s^n</tex> при больших <tex>n</tex> одномерный ККА может быть эквивалентен [[Марковская цепь | марковской цепи]]<ref>[http://www.lu.lv/fileadmin/user_upload/lu_portal/projekti/datorzinatnes_pielietojumi/publikacijas/Ambainis_7_3.pdf QFAs and quantum Markov chains]</ref>.<br />
==Односторонние квантовые кончные автоматы==<br />
=== Одномерный квантовый конечный автомат===<br />
Авторы '''одномерного''' (англ. ''Measure-one'') ККА {{---}} Cris Moore и James P. Crutchfield (2000). Главное свойство одномерного ККА {{---}} допускать [[Регулярные языки: два определения и их эквивалентность | регулярный язык]].<br />
Автомат такого типа с <tex>N</tex> состояниями представляется в виде [[Кубит | кубита]] <tex>|\psi\rangle</tex> c <tex>N</tex> состояниями. <br />
:<tex>|\psi\rangle \in CP^N</tex>. <br />
<br />
Такой кубит приносит в пространство метрику Фубини-Штуди<ref>[https://en.wikipedia.org/wiki/Fubini%E2%80%93Study_metric Wikipedia {{---}} Fubini–Study metric]</ref> <tex>\Vert\cdot\Vert</tex>. <br />
Матрицы смежности остаются унитарными, а переход в новое сосояние по символу <tex>\alpha</tex> :<br />
:<tex>|\psi'\rangle = U_\alpha |\psi\rangle</tex>.<br />
Переход в допускающее состояние производится матрицей-проектором<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82%D0%BE%D1%80_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) Википедия {{---}} Проектор]</ref> <tex> P [N \times N]</tex>. <br />
<br />
Вероятность <tex>Pr(s)</tex>, где <tex>s = (a_0,a_1,\cdots,a_k) </tex> равна : <br />
<br />
:<tex>\operatorname{Pr}(s) = \Vert P U_{a_k} \cdots U_{a_1} U_{a_0}|\psi\rangle\Vert^2 </tex><br />
<br />
===Многомерный квантовый конечный автомат===<br />
{{Определение<br />
|definition=<br />
'''Многомерный квантовый конечный автомат''' (англ. ''Measure-many QFA'') {{---}} это кортеж : <tex>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</tex>, где<br />
* <tex>Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_Q</tex>,<br />
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова,<br />
* <tex>\delta : Q\times \Sigma \times Q \to \mathbb{C} </tex> — всюду определённая функция перехода автомата,<br />
* <tex>q_0</tex> — начальное состояние автомата,<br />
* <tex>Q_a \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_a</tex>,<br />
* <tex>Q_r \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_r</tex>.<br />
<br />
}}<br />
'''Многомерный''' ККА был введен Attila Kondacs и John Watrous в 1997. Его главное свойство {{---}} допускать регулярные языкы.<br />
<br />
Принципы многомерного ККА очень схожи с одномерными, за исключением измерения вероятности после каждого прочтения символа входящей строки, вместо единственного измерения вероятности целой строчки у одномерных ККА. Для формального определения понадобится [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <tex>\mathcal{H}_Q</tex> :<br />
<br />
<tex>\mathcal{H}_Q=\mathcal{H}_a \oplus \mathcal{H}_r \oplus \mathcal{H}_{non}</tex> , где <tex> \mathcal{H}_a </tex> {{---}} допускающее пр-во , <tex> \mathcal{H}_r </tex> {{---}} отвергающее пр-во , <tex> \mathcal{H}_{non} </tex> {{---}} промежуточное пр-во. Для каждого пр-ва существует набор базисных ортогональных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно : <br />
<br />
:<tex>\mathcal{H}_a=\operatorname{span} \{|q\rangle : |q\rangle \in Q_a \}, \mathcal{H}_r = \dots , \mathcal{H}_{non} = \dots </tex> , где <tex>\operatorname{span}</tex> {{---}} линейная оболочка<ref>[https://en.wikipedia.org/wiki/Linear_span Wikipedia {{---}} Lineal span]</ref> <br />
<br />
Так же в многомерном ККА присутствуют 3 матрицы-проектора : <tex>P_a</tex>, <tex>P_r</tex> и <tex> P_{non} </tex> для каждого гильбертово пр-ва :<br />
<br />
:<tex>P_a:\mathcal{H}_Q \to \mathcal{H}_a , P_r = \dots, P_{non} = \dots</tex><br />
<br />
Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из трёх гильбертовых пр-в <tex>\mathcal{H}_a, \mathcal{H}_r , \mathcal{H}_{non}</tex>. В таком случае вероятность автомата находиться в допускающем состоянии равна: <br />
<br />
:<tex>\operatorname{Pr}_a (s) = \Vert P_a |\psi\rangle \Vert^2</tex>, где <tex>s</tex> {{---}} входная строчка<br />
<br />
==Двухсторонние квантовые конечные автоматы==<br />
{{Определение<br />
|definition=<br />
'''Двухсторонний квантовый конечный автомат''' (англ. ''2-way QFA'') {{---}} это кортеж : <tex>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</tex>, где<br />
* <tex>Q</tex> — множество состояний автомата,<br />
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова,<br />
* <tex>\delta : Q\times \Sigma \times Q \to \mathbb{C} \times \{-1,0,1\}</tex> — всюду определённая функция перехода автомата,<br />
* <tex>q_0</tex> — начальное состояние автомата,<br />
* <tex>Q_a \subset Q</tex> — множество допускающих состояний,<br />
* <tex>Q_r \subset Q</tex> — множество опровергающих состояний.<br />
}}<br />
<br />
Отличия от одностороннего :<br />
* Головка может двигаться в обоих направлениях.<br />
* Может гарантированно разрешать регулярный язык.<br />
* Может за линейное время разрешать нерегулярный язык.<br />
<br />
==См. также==<br />
*[[Детерминированные конечные автоматы]]<br />
*[[Недетерминированные конечные автоматы]]<br />
*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]<br />
<br />
== Примечания ==<br />
<references/><br />
<br />
==Источники информации==<br />
* Andris Ambainis, [http://www.lu.lv/fileadmin/user_upload/lu_portal/projekti/datorzinatnes_pielietojumi/publikacijas/Ambainis_7_3.pdf QUANTUM FINITE AUTOMATA]<br />
* [[wikipedia:Quantum finite automata | Wikipedia {{---}} Quantum finite automata]]<br />
* SlideShare.net, [http://www.slideshare.net/ranjanphu/seminar-on-quantum-automata-complete Seminar on quantum automata (complete)]<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Автоматы и регулярные языки]]</div>VictorMinskyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D0%BE%D1%82%D0%B4%D0%B5%D0%BB%D0%B8%D0%BC%D1%8B%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0&diff=82278Неотделимые множества2022-05-04T01:28:08Z<p>VictorMinsky: tex fix</p>
<hr />
<div>{{Лемма<br />
|author=1<br />
|statement=<br />
Существует [[Вычислимые функции#Основные определения | вычислимая функция]], не имеющая всюду определенного вычислимого продолжения.<br />
|proof=<br />
Рассмотрим функцию <tex>f(n) = U(n, n) + 1</tex>, где <tex>U(n, n)</tex> {{---}} [[Диагональный метод|универсальная функция]].<br />
<br />
Предположим, у нее существует всюду определенное продолжение <tex>g(n) \Rightarrow f(n) \neq \bot \Rightarrow g(n) = f(n)</tex> и <tex> \forall n \in \mathbb{N} \ g(n) \neq \bot</tex>.<br />
<br />
По определению универсальной функции <tex>g(n) = U(i, n)</tex> для некоторого <tex>i \Rightarrow g(i) = U(i, i)</tex>. <br />
<br />
Поскольку <tex>g(n)</tex> всюду определена, то <tex>U(i, i) \neq \bot</tex>. Значит, определено значение <tex>f(i)</tex> и <tex>g(i) = f(i) = U(i, i) + 1</tex>. Получили противоречие.<br />
<br />
Таким образом, построенная функция <tex>f(n)</tex> не имеет всюду определенного вычислимого продолжения.<br />
}}<br />
<br />
{{Лемма<br />
|author=2<br />
|statement=<br />
Существует [[Вычислимые функции#Основные определения | вычислимая функция]], значения которой принадлежат множеству <tex>\{0, 1, \bot\}</tex>, не имеющая всюду определенного вычислимого продолжения.<br />
|proof=<br />
Рассмотрим функцию<br />
<tex>f(n) = \begin{cases}<br />
0 & U(n, n) \neq 0 \text{, }U(n, n) \neq \bot \\<br />
1 & U(n, n) = 0 \\<br />
\bot & U(n, n) = \bot<br />
\end{cases}</tex><br />
<br />
Предположим, у нее существует всюду определенное продолжение <tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>.<br />
<br />
Поскольку <tex>g(n)</tex> всюду определена, то <tex>g(i) = U(i, i) \neq \bot</tex> и определено значение <tex>f(i)</tex>. Но по построению функции <tex>f(n)</tex> видим, что <tex>f(i) \neq U(i, i)</tex>. Получили противоречие.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Существуют такие непересекающиеся перечислимые множества <tex>X'</tex> и <tex>Y'</tex>, что не существует таких разрешимых множеств <tex>X</tex> и <tex>Y</tex>, что <tex>X' \subset X</tex>, <tex>Y' \subset Y</tex>, <tex>X \cap Y = \varnothing</tex>, <tex>X \cup Y = \mathbb{N}</tex>. Такие множества <tex>X'</tex> и <tex>Y'</tex> называют '''неотделимыми''' (англ. ''inseparable sets'').<br />
|proof=<br />
Рассмотрим множества <tex>X' = \{n \mid f(n) = 0\}</tex> и <tex>Y' = \{n \mid f(n) = 1\}</tex>, где <tex>f(n)</tex> {{---}} функция из леммы 2.<br />
<br />
Пусть существуют <tex>X</tex> и <tex>Y</tex>, удовлетворяющие указанным свойствам, тогда вычислима характеристическая функция <tex>g(n) = \begin{cases}<br />
1, & n \in Y \\<br />
0, & n \notin Y (n \in X)<br />
\end{cases}</tex> множества <tex>Y</tex>.<br />
<br />
Заметим, что <tex>g(n)</tex> всюду определена и является продолжением <tex>f(n)</tex>, что противоречит лемме 2.<br />
}}<br />
<br />
Неотделимые множества используются в доказательстве других фактов<ref>[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 39, с. 63, c. 100. ISBN 5-900916-36-7]</ref>. <br />
<br />
== Примечания ==<br />
<br />
<references /><br />
<br />
== Источники информации ==<br />
<br />
* [http://en.wikipedia.org/wiki/Recursively_inseparable_sets Wikipedia {{---}} Recursively inseparable sets]<br />
* Gasarch, William (1998), "A survey of recursive combinatorics", Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math. 139, Amsterdam: North-Holland, pp. 1041–1176, MR 1673598<br />
* Smullyan, Raymond M. (1958), "Undecidability and recursive inseparability", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 4: 143–147<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Теория вычислимости]]</div>VictorMinskyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:VictorMinsky&diff=82217Участник:VictorMinsky2022-03-01T22:02:29Z<p>VictorMinsky: </p>
<hr />
<div>Панасюк Виктор M3236<br />
<br />
@VictorMinsky</div>VictorMinskyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0&diff=82216Заглавная страница2022-03-01T22:01:34Z<p>VictorMinsky: Отмена правки 82215, сделанной 185.220.102.249 (обсуждение)</p>
<hr />
<div>Добро пожаловать на сайт [[Викиконспекты:Описание|вики-конспектов]]!<br />
<br />
= Проверяемые конспекты =<br />
<br />
== [[Дискретная математика | Дискретная математика]]==<br />
* [[Дискретная математика#Отношения| Отношения]]<br />
* [[Дискретная математика#Булевы функции| Булевы функции]]<br />
* [[Дискретная математика#Схемы из функциональных элементов| Схемы из функциональных элементов]]<br />
* [[Дискретная математика#Представление информации| Представление информации]]<br />
* [[Дискретная математика#Алгоритмы сжатия| Алгоритмы сжатия данных]]<br />
* [[Дискретная математика#Комбинаторика| Комбинаторика]]<br />
* [[Дискретная математика#Производящая функция|Производящая функция]]<br />
<br />
==[[Теория вероятностей | Теория вероятностей]]==<br />
<br />
* [[Теория вероятностей # Теория вероятностей| Базовые определения и формулы расчета вероятности]]<br />
* [[Теория вероятностей #Марковские цепи| Марковские цепи]]<br />
<br />
==[[Теория формальных языков|Теория формальных языков]]==<br />
* [[Теория формальных языков#Автоматы и регулярные языки|Автоматы и регулярные языки]]<br />
* [[Теория формальных языков#Контекстно-свободные грамматики|Контекстно-свободные грамматики]]<br />
<br />
== [[Теория матроидов | Теория матроидов]]==<br />
<br />
* [[Теория матроидов#Основные факты теории матроидов | Основные факты]]<br />
* [[Теория матроидов#Пересечение матроидов | Пересечение матроидов]]<br />
* [[Теория матроидов#Объединение матроидов | Объединение матроидов]]<br />
<br />
== [[Теория расписаний | Теория расписаний]]==<br />
<br />
*[[Теория расписаний#Задачи с одним станком | Задачи с одним станком]]<br />
*[[Теория расписаний#Специальные случаи задач для двух станков | Специальные случаи задач для двух станков]]<br />
*[[Теория расписаний#Задачи для произвольного числа станков | Задачи для произвольного числа станков]]<br />
<br />
== [[Теория вычислимости | Теория вычислимости]]==<br />
* [[Теория вычислимости#Разрешимые и перечислимые языки | Разрешимые и перечислимые языки]]<br />
* [[Теория вычислимости#Вычислительные формализмы | Вычислительные формализмы]]<br />
* [[Теория вычислимости#Примеры неразрешимых задач | Примеры неразрешимых задач]]<br />
<br />
==[[Теория сложности | Теория сложности]]==<br />
* [[Теория сложности#Детерминированные и недетерминированные вычисления, сложность по времени и по памяти | Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]]<br />
* [[Теория сложности#Схемная сложность | Схемная сложность]]<br />
* [[Теория сложности#Вероятностные сложностные классы | Вероятностные сложностные классы]]<br />
<br />
== [[Алгоритмы и структуры данных | Алгоритмы и структуры данных]]==<br />
* [[Алгоритмы и структуры данных#Амортизационный анализ | Амортизационный анализ]]<br />
* [[Алгоритмы и структуры данных#Персистентные структуры данных | Персистентные структуры данных]]<br />
* [[Алгоритмы и структуры данных#Приоритетные очереди | Приоритетные очереди]]<br />
* [[Алгоритмы и структуры данных#Система непересекающихся множеств | Система непересекающихся множеств]]<br />
* [[Алгоритмы и структуры данных#Поисковые структуры данных | Поисковые структуры данных]]<br />
* [[Алгоритмы и структуры данных#Запросы на отрезках | Запросы на отрезках]]<br />
* [[Алгоритмы и структуры данных#Дерево Фенвика | Дерево Фенвика]]<br />
* [[Алгоритмы и структуры данных#Задача о наименьшем общем предке | Задача о наименьшем общем предке]]<br />
* [[Алгоритмы и структуры данных#Хеширование | Хеширование]]<br />
* [[Алгоритмы и структуры данных#Сортировки | Сортировки]]<br />
* [[Алгоритмы и структуры данных#Сортирующие сети | Сортирующие сети]]<br />
* [[Алгоритмы и структуры данных#Алгоритмы поиска | Алгоритмы поиска]]<br />
* [[Алгоритмы и структуры данных#Динамическое программирование | Динамическое программирование]]<br />
* [[Алгоритмы и структуры данных#Алгоритмы во внешней памяти | Алгоритмы во внешней памяти]]<br />
<br />
== [[Теория графов | Теория графов]]==<br />
* [[Теория графов#Основные определения теории графов | Основные определения теории графов]]<br />
* [[Теория графов#Связность в графах | Связность в графах]]<br />
* [[Теория графов#Остовные деревья | Остовные деревья]]<br />
* [[Теория графов#Обходы графов | Обходы графов]]<br />
* [[Теория графов# Укладки графов | Укладки графов]]<br />
* [[Теория графов#Раскраски графов | Раскраски графов]]<br />
* [[Теория графов#Обход в глубину | Обход в глубину]]<br />
* [[Теория графов#Кратчайшие пути в графах | Кратчайшие пути в графах]]<br />
* [[Теория графов#Задача о паросочетании | Задача о паросочетании]]<br />
* [[Теория графов#Задача о максимальном потоке | Задача о максимальном потоке]]<br />
* [[Теория графов#Задача о потоке минимальной стоимости | Задача о потоке минимальной стоимости]]<br />
* [[Теория графов#Cлучайные графы | Cлучайные графы]]<br />
<br />
== [[Алгоритмы на строках | Алгоритмы на строках]]==<br />
* [[Алгоритмы на строках# Поиск подстроки в строке | Поиск подстроки в строке]]<br />
* [[Алгоритмы на строках#Суффиксное дерево |Суффиксное дерево]]<br />
* [[Алгоритмы на строках#Суффиксный массив | Суффиксный массив]]<br />
<br />
== [[Методы трансляции | Методы трансляции]] ==<br />
* [[Методы трансляции#Нисходящий разбор|Нисходящий разбор]]<br />
* [[Методы трансляции#Восходящий разбор | Восходящий разбор]]<br />
<br />
== [[Вычислительная геометрия|Вычислительная геометрия ]]==<br />
* [[Вычислительная геометрия#Основание вычислительной геометрии|Основание вычислительной геометрии]]<br />
* [[Вычислительная геометрия#Вычисление геометрических предикатов|Вычисление геометрических предикатов]]<br />
* [[Вычислительная геометрия#Пересечение отрезков|Пересечение отрезков]]<br />
* [[Вычислительная геометрия#Выпуклые оболочки|Выпуклые оболочки]]<br />
* [[Вычислительная геометрия#Поиск|Поиск]]<br />
* [[Вычислительная геометрия#Триангуляция|Триангуляция]]<br />
* [[Вычислительная геометрия#ППЛГ и РСДС|ППЛГ и РСДС]]<br />
* [[Вычислительная геометрия#Алгоритмы локализации|Алгоритмы локализации]]<br />
* [[Вычислительная геометрия#Триангуляция Делоне и диаграмма Вороного|Триангуляция Делоне и диаграмма Вороного]]<br />
* [[Вычислительная геометрия#Планирование движения (Motion planning)|Планирование движения (Motion planning)]]<br />
<br />
== [[Язык программирования Java|Язык программирования Java]]==<br />
*[[Основная информация о языкe]]<br />
*[[Программирование по контракту]]<br />
*[[Обработка ошибок и исключения]]<br />
*[[Generics]]<br />
*[[Перечисления]]<br />
<br />
== [[Параллельное программирование|Параллельное программирование]]==<br />
*[[Очередь Майкла и Скотта]]<br />
<br />
== [[Машинное обучение|Машинное обучение]]==<br />
<br />
*[[Модель алгоритма и ее выбор]]<br />
*[[Переобучение]]<br />
*[[Кросс-валидация]]<br />
*[[Выброс]]<br />
*[[Машинное обучение|Другие темы]]<br />
<br />
= Непроверяемые конспекты =<br />
<br />
*[[Алгебра и геометрия 1 курс | Алгебра и геометрия — 1, 2 семестр]]<br />
*[[Математический анализ 1 курс | Математический анализ — 1, 2 семестр]]<br />
*[[Математический анализ 2 курс | Математический анализ — 3, 4 семестр]]<br />
*[[Математическая логика|Математическая логика — 3 семестр]]<br />
*[[Участник:Qwerty787788/плюсы3сем | С++ — 2, 3 семестр]]<br />
*[[Дифференциальные уравнения | Дифференциальные уравнения — 3 семестр]]<br />
*[[Assembler|Assembler — 4 семестр]]<br />
*[[Алгоритмы алгебры и теории чисел|Алгоритмы алгебры и теории чисел — 4 семестр]]<br />
*[[Функциональный_анализ_3_курс | Функциональный анализ — 5, 6 семестр]]<br />
*[[Параллельное программирование|Параллельное программирование — 6 семестр]]<br />
*[[Базы данных|Базы данных — 7 семестр]]<br />
*[[Компьютерные сети|Компьютерные сети — 7, 8 семестр]]<br />
*[[Эволюционные алгоритмы|Эволюционные алгоритмы — 10 семестр]]<br />
<br />
[[Категория:Всё]]</div>VictorMinskyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8,_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82%D1%8B_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8&diff=81148Отношение связности, компоненты связности2021-09-08T13:40:12Z<p>VictorMinsky: </p>
<hr />
<div>== Случай неориентированного графа ==<br />
<br />
{{Определение<br />
|definition=<br />
Две вершины <tex>u</tex> и <tex>v</tex> называются '''связанными''' ''(англ. adjacent)'', если в графе <tex>G</tex> существует [[Основные определения теории графов|путь]] из <tex>u</tex> в <tex>v</tex> (обозначение: <tex>u \rightsquigarrow v </tex>).}}<br />
<br />
{{Теорема<br />
|statement=<br />
Связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]''' ''(англ. equivalence relation)''.<br />
|proof=<br />
'''[[Рефлексивное_отношение|Рефлексивность]]''': <tex>\forall a \in V a \rightsquigarrow a</tex> (очевидно).<br />
<br />
'''[[Симметричное_отношение|Симметричность]]''': <tex>a\rightsquigarrow b \Rightarrow b\rightsquigarrow a</tex> (в силу неориентированности графа).<br />
<br />
'''[[Транзитивное_отношение|Транзитивность]]''': <tex>a\rightsquigarrow b \land b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</tex>. Действительно, сначала пройдем от <tex>a</tex> до <tex>b</tex>, затем от <tex>b</tex> до <tex>c</tex>, что и означает существования пути <tex>a \rightsquigarrow c</tex>.<br />
}}<br />
<br />
{{Определение<br />
|id = def2<br />
|definition=<br />
'''Компонентой связности''' ''(англ. connected component)'' называется класс эквивалентности относительно связности.}}<br />
<br />
{{Определение<br />
|id = connected_graph<br />
|definition=<br />
Граф <tex>G=(V, E)</tex> называется '''связным''' ''(англ. connectivity graph)'', если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''.}}<br />
<br />
== Случай ориентированного графа ==<br />
В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности.<br />
=== Слабая связность ===<br />
{{Определение<br />
|definition=<br />
Отношение $R(v, u)$ называется отношением '''слабой связности''' ''(англ. weak connectivity)'', если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Слабая связность '''является [[Отношение_эквивалентности|отношением эквивалентности]]'''.<br />
|proof=<br />
Аналогично доказательству соответствующей теоремы для неориентированного графа.<br />
}}<br />
[[Файл:components1.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами слабой связности.]]<br />
<br clear="all" /><br />
<br />
=== Сильная связность ===<br />
{{Определение<br />
|id=sc_def<br />
|definition=<br />
Отношение <tex>R(v, u) = v \rightsquigarrow u \land u \rightsquigarrow v</tex> на вершинах графа называется отношением '''сильной связности''' ''(англ. strong connectivity)''.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Сильная связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]'''.<br />
|proof=<br />
'''[[Рефлексивное_отношение|Рефлексивность]]''' и '''[[Симметричное_отношение|симметричность]]''' очевидны. Рассмотрим '''[[Транзитивное_отношение|транзитивность]]''': <br />
<tex>(a\rightsquigarrow b \land b\rightsquigarrow a) \land (b\rightsquigarrow c \land c\rightsquigarrow b)\Leftrightarrow (a\rightsquigarrow b \land b\rightsquigarrow c) \land (c\rightsquigarrow b \land b\rightsquigarrow a) \Leftrightarrow a\rightsquigarrow c \land c\rightsquigarrow a</tex><br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Пусть <tex>G = (V, E)</tex> — [[Основные_определения_теории_графов|ориентированный граф]]. '''Компонентой сильной связности''' ''(англ. strongly connected component)'' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}}<br />
[[Файл:Components2.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами сильной связности.]]<br />
{{Определение<br />
|definition=<br />
[[Основные_определения_теории_графов|Ориентированный граф]] <tex>G = (V, E)</tex> называется '''сильно связным''' ''(англ. strongly connected)'', если он состоит из одной компоненты сильной связности.}}<br />
<br />
<br clear="all" /><br />
<br />
==См. также==<br />
<br />
*[[Отношение рёберной двусвязности]]<br />
*[[Отношение вершинной двусвязности]]<br />
<br />
==Источники информации==<br />
* [http://xn--90abr5b.xn--p1ai/wiki/doku.php?id=examination:diskretka:question12 Отношения связности для вершин неорграфа на ivtb.ru]<br />
* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Связность в графах]]</div>VictorMinskyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B9_%D0%BE%D0%B1%D1%89%D0%B5%D0%B9_%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8&diff=81146Задача о наибольшей общей подпоследовательности2021-09-05T19:21:36Z<p>VictorMinsky: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
Последовательность <tex> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> является '''подпоследовательностью''' (англ. ''subsequence'') последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex>, если существует строго возрастающая последовательность <tex> \left \langle i_1, i_2, \dots, i_k \right \rangle </tex> индексов <tex> X </tex> таких, что для всех <tex> j = 1, 2, \dots, k </tex> выполняется соотношение <tex> x_{i_j} = z_j </tex>.<br />
}}<br />
Другими словами, подпоследовательность данной последовательности — это последовательность, из которой удалили ноль или больше элементов. Например, <tex> Z = \left \langle B, C, D, B \right \rangle </tex> является подпоследовательностью последовательности <tex> X = \left \langle A, B, C, B, D, A, B \right \rangle </tex>, а соответствующая последовательность индексов имеет вид <tex> \left \langle 2, 3, 5, 7 \right \rangle </tex>.<br />
{{Определение<br />
|definition=<br />
Последовательность <tex> Z </tex> является '''общей подпоследовательностью''' (англ. ''common subsequence'') последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> Z </tex> является подпоследовательностью как <tex> X </tex>, так и <tex> Y </tex>.<br />
}}<br />
{{Задача<br />
|definition=<br />
Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_n \right \rangle </tex>. Необходимо найти <tex>LCS(X,Y)</tex><br />
}}<br />
== Наивное решение ==<br />
Переберем все различные подпоследовательности обеих строк и сравним их. Тогда искомая <tex>LCS</tex> гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.<br />
<br />
== Динамическое программирование ==<br />
<br />
Для решения данной задачи используем [[Динамическое программирование#Принцип оптимальности на префиксе | Принцип оптимальности на префиксе]].<br />
<br />
=== Доказательство оптимальности ===<br />
{{<br />
Теорема|statement=<br />
Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_n \right \rangle </tex>, а <tex> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> — их <tex>LCS</tex>.<br />
<br />
# Если <tex> x_m = y_n </tex>, то <tex> z_k = x_m = y_n </tex> и <tex> Z_{k - 1} </tex> — <tex>LCS(X_{m - 1},Y_{n - 1})</tex><br />
# Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq x_m </tex> следует, что <tex> Z </tex> — <tex>LCS(X_{m - 1},Y)</tex><br />
# Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq y_n </tex> следует, что <tex> Z </tex> — <tex>LCS(X,Y_{n - 1})</tex><br />
<br />
|proof=<br />
# Если бы выполнялось <tex> z_k \neq x_m </tex>, то к <tex> Z </tex> можно было бы добавить элемент <tex> x_m = y_n </tex>, и тогда получилась бы общая подпоследовательность длины <tex> k + 1 </tex>, что противоречит предположению, что <tex> Z </tex> — <tex>LCS</tex>. Значит, выполняется <tex> z_k = x_m = y_n </tex>. Значит, <tex> Z_{k - 1} </tex> — общая подпоследовательность <tex> X_{m - 1} </tex> и <tex> Y_{n - 1} </tex>. Докажем от противного, что <tex> Z_{k - 1} </tex> — <tex>LCS</tex>: тогда есть общая подпоследовательность <tex> W </tex>, длина которой больше <tex> k - 1 </tex>. Добавив к <tex> W </tex> элемент <tex> x_m = y_n </tex>, получим <tex>LCS(X,Y)</tex>, длина которой больше <tex> k </tex> (т.е. больше длины <tex> Z </tex>), что приводит к противоречию.<br />
# Если <tex> z_k \neq x_m </tex>, то <tex> Z </tex> — общая подпоследовательность <tex> X_{m - 1} </tex> и <tex> Y </tex>. Пусть существует их общая подпоследовательность <tex> W </tex>, длина которой превышает <tex> k </tex>. Она также является общей подпоследовательностью <tex> X </tex> и <tex> Y </tex>, что противоречит предположению о том, что <tex> Z </tex> (длины <tex> k </tex>) — <tex>LCS(X,Y)</tex>.<br />
# Аналогично второму случаю.<br />
}}<br />
<br />
=== Решение ===<br />
Обозначим как <tex> lcs[i][j] </tex> <tex>LCS</tex> префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Получается следующее рекуррентное соотношение:<br />
<br />
<tex><br />
lcs[i][j] =<br />
\begin{cases}<br />
0, & i = 0\text{ or }j = 0 \\<br />
lcs[i - 1][j - 1] + 1, & x[i] = y[j] \\<br />
\max(lcs[i][j - 1],\ lcs[i - 1][j]), & x[i] \neq y[j]<br />
\end{cases}<br />
</tex><br />
<br />
Очевидно, что сложность алгоритма составит <tex> O(mn) </tex>, где <tex> m </tex> и <tex> n </tex> — длины последовательностей.<br />
<br />
=== Построение подпоследовательности ===<br />
Для каждой пары элементов помимо длины <tex>LCS</tex> соответствующих префиксов хранятся и номера последних элементов, участвующих в этой <tex>LCS</tex>.Таким образом, посчитав ответ, можно восстановить всю наибольшую общую подпоследовательность.<br />
<br />
=== Псевдокод ===<br />
<tex> x </tex>, <tex> y </tex> — данные последовательности; <tex> lcs[i][j] </tex> — <tex>LCS</tex> для префикса длины <tex> i </tex> последовательности <tex> x </tex> и префикса длины <tex> j </tex> последовательности <tex> y </tex>; <tex> prev[i][j] </tex> — пара индексов элемента таблицы, соответствующего оптимальному решению вспомогательной задачи, выбранной при вычислении <tex> lcs[i][j] </tex>.<br />
<br />
''<font color="green">// подсчёт таблиц</font>''<br />
'''int''' LCS(x: '''vector''', y: '''vector'''):<br />
m = length(x)<br />
n = length(y)<br />
'''for''' i = 1 '''to''' m<br />
lcs[i][0] = 0<br />
'''for''' j = 0 '''to''' n<br />
lcs[0][j] = 0<br />
'''for''' i = 1 '''to''' m<br />
'''for''' j = 1 '''to''' n<br />
'''if''' x[i] == y[j]<br />
lcs[i][j] = lcs[i - 1][j - 1] + 1<br />
prev[i][j] = pair(i - 1, j - 1)<br />
'''else'''<br />
'''if''' lcs[i - 1][j] >= lcs[i][j - 1]<br />
lcs[i][j] = lcs[i - 1][j]<br />
prev[i][j] = pair(i - 1, j)<br />
'''else'''<br />
lcs[i][j] = lcs[i][j - 1]<br />
prev[i][j] = pair(i, j - 1)<br />
<br />
''<font color="green">// вывод LCS, вызывается как printLCS(m, n)</font>''<br />
'''int''' printLCS(i: '''int''', j: '''int'''):<br />
'''if''' i == 0 '''or''' j == 0 ''<font color="green">// пришли к началу LCS</font>''<br />
'''return'''<br />
'''if''' prev[i][j] == pair(i - 1, j - 1) ''<font color="green">// если пришли в lcs[i][j] из lcs[i - 1][j - 1], то x[i] == y[j], надо вывести этот элемент</font>''<br />
printLCS(i - 1, j - 1)<br />
print x[i]<br />
'''else'''<br />
'''if''' prev[i][j] == pair(i - 1, j)<br />
printLCS(i - 1, j)<br />
'''else'''<br />
printLCS(i, j - 1)<br />
<br />
== Оптимизация для вычисления только длины <tex>LCS</tex> ==<br />
Заметим, что для вычисления <tex> lcs[i][j] </tex> нужны только <tex> i </tex>-ая и <tex> (i-1) </tex>-ая строчки матрицы <tex> lcs </tex>. Тогда можно использовать лишь <tex> 2 \cdot min(m, n) </tex> элементов таблицы:<br />
<br />
'''int''' LCS2(x: '''vector''', y: '''vector'''):<br />
'''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''<br />
swap(x, y)<br />
m = length(x)<br />
n = length(y)<br />
'''for''' j = 0 '''to''' n<br />
lcs[0][j] = 0<br />
lcs[1][j] = 0<br />
'''for''' i = 1 '''to''' m<br />
lcs[1][0] = 0<br />
'''for''' j = 1 '''to''' n<br />
lcs[0][j] = lcs[1][j] ''<font color="green">// элемент, который был в a[1][j], теперь в предыдущей строчке</font>''<br />
'''if''' x[i] == y[j]<br />
lcs[1][j] = lcs[0][j - 1] + 1<br />
'''else'''<br />
'''if''' lcs[0][j] >= lcs[1][j - 1]<br />
lcs[1][j] = lcs[0][j]<br />
'''else'''<br />
lcs[1][j] = lcs[1][j - 1]<br />
''<font color="green">// ответ — lcs[1][n]</font>''<br />
<br />
Также можно заметить, что от <tex> (i - 1) </tex>-ой строчки нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы:<br />
<br />
'''int''' LCS3(x: '''vector''', y: '''vector'''):<br />
'''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''<br />
swap(x, y)<br />
m = length(x)<br />
n = length(y)<br />
'''for''' j = 0 '''to''' n<br />
lcs[j] = 0<br />
d = 0 ''<font color="green">// d — дополнительная переменная, в ней хранится lcs[i - 1][j - 1]''<br />
''// в lcs[j], lcs[j + 1], …, lcs[n] хранятся lcs[i - 1][j], lcs[i - 1][j + 1], …, lcs[i - 1][n]''<br />
''// в lcs[0], lcs[1], …, lcs[j - 1] хранятся lcs[i][0], lcs[i][1], …, lcs[i][j - 1]</font>''<br />
'''for''' i = 1 '''to''' m<br />
'''for''' j = 1 '''to''' n<br />
tmp = lcs[j]<br />
'''if''' x[i] == y[j]<br />
lcs[j] = d + 1<br />
'''else'''<br />
'''if''' lcs[j] >= lcs[j - 1]<br />
lcs[j] = lcs[j] ''<font color="green">// в lcs[j] и так хранится lcs[i - 1][j]</font>''<br />
'''else'''<br />
lcs[j] = lcs[j - 1]<br />
d = tmp<br />
''<font color="green">// ответ — lcs[n]</font>''<br />
<br />
== Длина кратчайшей общей суперпоследовательности ==<br />
Для двух подпоследовательностей <tex>X_{m}</tex> и <tex>Y_{n}</tex> длина кратчайшей общей суперпоследовательности равна <br />
<tex><br />
|SCS(X,Y)| = n + m - |LCS(X,Y)|<br />
</tex><br />
<ref>[http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Relation_to_other_problems Wikipedia {{---}} Longest common subsequence problem]</ref><br />
<br />
== Решение для случая k строк ==<br />
Найдем решение для 3 строк.<br />
{{Задача<br />
|definition = Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex>, <tex> Y = \left \langle y_1, y_2, \dots, y_n \right \rangle </tex> и <tex>Z = \left \langle z_1, z_2, \dots, z_k \right \rangle</tex>. Необходимо найти <tex>LCS(X,Y,Z)</tex><br />
}}<br />
Наивное решение подсчёта <tex>LCS</tex> нескольких строк при помощи последовательного нахождения <tex>LCS</tex> двух строк и уменьшением набора строк на единицу, не срабатывает. Это доказывается следующим контрпримером.<br />
Даны три последовательности: <br />
<br />
<tex>X = \left \langle A, B, C, D, E\right \rangle </tex><br />
<br />
<tex>Y = \left \langle D, E, A, B, C\right \rangle </tex><br />
<br />
<tex>Z = \left \langle D, E, F, G, H\right \rangle </tex><br />
<br />
Подсчитаем <tex>V = LCS(X,Y) = \left \langle A, B, C \right \rangle</tex><br />
<br />
<tex>LCS(Z,V) = \emptyset</tex><br />
<br />
Это неверно, так как <tex>LCS(X,Y,Z) = \left \langle D, E \right \rangle</tex><br />
<br />
{{Теорема<br />
|statement = Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex>, <tex> Y = \left \langle y_1, y_2, \dots, y_n \right \rangle </tex> и <tex> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex>, а <tex> V = \left \langle v_1, v_2, \dots, v_h \right \rangle</tex> — их <tex>LCS</tex>.<br />
# Если <tex>z_k = x_m = y_n</tex>, то <tex>z_k = x_m = y_n = v_h</tex> и <tex> V_{h - 1} </tex> — <tex>LCS(X_{m - 1},Y_{n - 1},Z_{k - 1})</tex><br />
# Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>z_k \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_m,Y_n,Z_{k - 1})</tex><br />
# Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>y_n \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_m,Y_{n - 1},Z_k)</tex><br />
# Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>x_m \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_{m - 1},Y_n,Z_k)</tex><br />
|proof = Доказательство аналогично доказательству для двух последовательностей.<br />
}} <br />
===Решение===<br />
Обозначим как <tex> lcs[i][j][l] </tex> наибольшую общую подпоследовательность префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex>, <tex> j </tex> и <tex> l </tex> соответственно. Получается следующее рекуррентное соотношение:<br />
<br />
<tex><br />
lcs[i][j][l] =<br />
\begin{cases}<br />
0, & i = 0\text{ or }j = 0\text{ or }l = 0 \\<br />
lcs[i - 1][j - 1][l - 1] + 1, & x[i] = y[j] = z[l] \\<br />
\max(lcs[i][j - 1][l],\ lcs[i - 1][j][l],\ lcs[i][j][l - 1]), & x[i] \neq y[j] \neq z[l]<br />
\end{cases}<br />
</tex><br />
<br />
Очевидно, что сложность алгоритма составит <tex> O(mnk) </tex>, где <tex> m </tex>, <tex> n </tex> и <tex> k </tex> — длины последовательностей.<br />
<br />
Аналогичным образом задача решается для <tex>k</tex> строк. Заполняется <tex>k</tex>-мерная динамика.<br />
<br />
== Алгоритм Хиршберга ==<br />
<br />
{{Задача<br />
|definition = Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_n \right \rangle </tex>. Необходимо найти <tex>LCS(X,Y)</tex> за время <tex> O(nm) </tex> и <tex> O(n + m) </tex> памяти.<br />
}}<br />
<br />
=== Алгоритм ===<br />
<br />
Не теряя общности, будем считать, что <tex> m \geqslant n </tex>. Тогда разобьем последовательность <tex> X </tex> на две равные части <tex dpi="200"> x_1 \left [0 \dots \frac {m} {2} \right ] </tex> и <tex dpi="200"> x_2 \left [\frac {m} {2} + 1 \dots m \right ] </tex>. Найдем <tex> LCS </tex> для <tex> x_1 </tex> и всех префиксов последовательности <tex>Y</tex>, аналогично — для развернутых последовательностей <tex> x_2 </tex> и <tex> Y </tex>. Стоит отметить, что для нахождения <tex> LCS </tex> на всех префиксах достаточно одного квадратичного прохода, так как <tex>i</tex>-ый элемент последней строки результирующей матрицы есть не что иное, как <tex> LCS </tex> первой последовательности и префикса второй длины <tex>i</tex>. Затем выберем такой индекс <tex> j </tex>, что <tex> \left | LCS(x_1, y \left [0 \dots j \right ]) + LCS(reverse(x_2), reverse(y \left [j + 1 \dots n \right ])) \right | = max</tex>. Запустим алгоритм рекурсивно для пар <br />
<tex>(x_1, y \left [0 \dots j \right ])</tex> и <tex>(x_2, y \left [j + 1 \dots n \right ])</tex>. Будем продолжать до тех пор, пока в <tex>X</tex> не останется ровно <tex>1</tex> элемент, тогда достаточно проверить, входит ли он текущую часть <tex>Y</tex>, если входит, то добавим этот символ в ответ, если нет — вернем пустую строку. Таким образом, в результате работы алгоритма соберем последовательность, которая будет являться искомой.<br />
<br />
=== Псевдокод ===<br />
<br />
В данном примере <tex> x, y </tex> — последовательности, <tex> ans </tex> — вектор ответа. <tex> LCS </tex> — функция, возвращающая последнюю строку матрицы <tex> lcs </tex>, для определения ответа на всех префиксах. Важно отметить, что для ее вычисления необходимо и достаточно хранить лишь две соседние строки матрицы <tex> lcs </tex> в любой момент времени. Так как вопрос оптимальности используемой памяти является важным местом данного алгоритма, то передачу различных отрезков последовательностей стоит воспринимать, как скрытую передачу границ для хранящихся глобально данных. <br />
<br />
'''void''' hirschberg(x: '''vector''', y: '''vector'''):<br />
'''if''' y.size() <= 0<br />
return <br />
'''if''' x.size() == 1<br />
'''if''' y.contains(x[0]) <br />
ans.push(x[0]) ''<font color="green"> // сохранение очередного элемента lcs </font>''<br />
return<br />
mid = x.size() / 2<br />
f[] = LCS(x[0 .. mid], y)<br />
s[] = LCS(reverse(x[mid + 1 .. x.size()]), reverse(y)) <br />
''<font color="green">// s[i] хранит lcs для второй половины x и суффикса y[i..y.size()] ''<br />
''// это позволяет использовать общий индекс в качестве точки разделения</font>''<br />
max = s[0] <br />
it_max = -1<br />
'''for''' j = 0 '''to''' y.size()<br />
'''if''' f[j] + s[y.size() - (j + 1)] > max <br />
max = f[j] + s[y.size() - (j + 1)]<br />
it_max = j<br />
'''if''' f[y.size() - 1] > max<br />
it_max = y.size() - 1<br />
hirschberg(x[0 .. mid], y[0 .. it_max])<br />
hirschberg(x[mid + 1 .. x.size()], y[it_max + 1 .. y.size()])<br />
<br />
=== Доказательство корректности ===<br />
<br />
Осталось понять, что алгоритм находит нужную подпоследовательность. Не теряя общности, будем считать, что <tex> lcs </tex> единственная, так как нам не важно какую из равных по длине подпоследовательностей выбирать. Тогда рассмотрим разделение на две части <tex>X</tex>, <br />
часть символов LCS (возможно нулевая) попадет в первую половину, оставшаяся — во вторую. Пусть <tex> x_i </tex> последний символ из LCS в первой половине, тогда наш алгоритм выберет соответствующий ему <tex> y_i </tex> в качестве точки разделения. То есть символы из <tex> y </tex>, которые связаны<br />
со второй половиной <tex> x </tex>, лежат правее <tex> y_i </tex>, в противном случае, либо <tex> y_i </tex> не состоит в паре с <tex> x_i </tex>, либо <tex> x_i </tex> не последний символ из <tex> lcs </tex> в первой половине. Заметим, что если первая половина не содержит <tex> lcs </tex>, то <br />
точки разбиения не будет, для симметричного случая со второй половиной точкой разбиения будет <tex> y_i </tex>, которая включается в первую половину. Таким образом, мы свели поиск исходной <tex> lcs </tex> к поиску двух независимых частей. Когда в <tex> X </tex> останется <tex>1</tex> символ, то возможны два варинта, либо он входит в <tex> lcs </tex>, либо нет, в чем мы убеждаемся линейным поиском, случай, когда последний <tex> x </tex> не входит в <tex> lcs </tex>, возникает из-за того, что на каком-то шаге, вся подпоследовательность оказалась в одной из половин <tex> X </tex>.<br />
<br />
=== Асимптотика === <br />
<br />
Рассмотрим временные затраты алгоритма. Рекурсия представима в виде бинарного дерева высоты не более <tex> \log (m) </tex>, так как она основана на разделении первой последовательности на две равные части на каждом шаге алгоритма. <br />
Оценим время выполнения для произвольной глубины такого дерева и просуммируем результат по всем возможным значениям парметра. На глубине <tex> h </tex> находится <tex> 2^h </tex> вершин с частью последовательности <tex> x </tex> размера <tex dpi = "200">\displaystyle\frac{m}{2^h} </tex> <br />
и частью <tex> y </tex> длины <tex> k_i </tex>, где сумма семейства <tex> k_i </tex> равна <tex> n </tex>. Таким образом, получаем:<br />
<br />
* На глубине h: <tex dpi = "200">{\displaystyle \sum_{i = 0}^{2^h - 1} \limits\frac{m}{2^h} k_i = \frac{m}{2^h} \sum_{i = 0}^{2^h - 1} \limits k_i = \frac{mn}{2^h}}</tex> <br />
<br />
* Сумммируем по глубинам: <tex dpi = "200">{\displaystyle \sum_{i = 0}^{\log m}\limits\frac{mn}{2^i} = mn \sum_{i = 0}^{\log m}\limits \frac{1}{2^i} < mn \sum_{i = 0}^{\infty}\limits \frac{1}{2^i} = 2mn} </tex> <br />
<br />
* Итоговая асимптотика алгоритма: <tex> O(mn) </tex><br />
<br />
<br />
Проанализируем затраты на память. Три глобальные последовательности (две исходные и одна для ответа), к которым мы обращаемся внутри алгоритма, требуют <tex> m + n + \min (m, n) </tex> памяти. Дополнительно на каждом шаге рекурсии вызываются <tex>2</tex> функции <tex> LCS </tex>, которые суммарно требуют <tex> 4k_i </tex>, где <tex> k_i </tex> — длина части <tex> y </tex> в текущий момент, так как для нахождения <tex> LCS </tex> достаточно двух строк матрицы <tex> lcs </tex>. Вспомогательные массивы удаляются перед рекурсивным вызовом, таким образом, общие затраты равны сумме размеров массивов на одной глубине рекурсии, то есть: <br />
<br />
* На глубине h: <tex dpi = "200">{\displaystyle\sum_{i = 0}^{2^h - 1}\limits 4 k_i = 4 \sum_{i = 0}^{2^h - 1}\limits k_i = 4n} </tex> <br />
<br />
* Итого: <tex dpi = "200">{n + m + \min(m, n) + 4n = O(n + m)}</tex><br />
<br />
<br />
== См. также == <br />
*[[Задача о наибольшей возрастающей подпоследовательности]]<br />
*[[Наибольшая общая возрастающая подпоследовательность]]<br />
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<br />
<br />
== Примечания ==<br />
<references /><br />
<br />
== Список литературы ==<br />
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4<br />
* Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Commun. ACM 18, 341–343 (1975)<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Динамическое программирование]]</div>VictorMinskyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BD%D0%B0_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D1%8F%D1%85&diff=81142Алгоритмы на деревьях2021-08-25T20:16:51Z<p>VictorMinsky: /* Реализация */</p>
<hr />
<div>__TOC__<br />
<br />
== Диаметр дерева ==<br />
{{Определение<br />
|id = tree<br />
|definition =<br />
'''Диаметр дерева''' (англ. ''diameter of a tree'') — максимальная длина (в рёбрах) кратчайшего пути в дереве между любыми двумя вершинами.<br />
}}<br />
<br />
Пусть дан граф <tex>G = \langle V, E \rangle </tex>. Тогда диаметром <tex>d</tex> называется <tex>\max\limits_{u, v \in V} dist(v, u)</tex>, где <tex>dist</tex> — кратчайшее расстояние между вершинами.<br />
<br />
=== Алгоритм ===<br />
* Возьмём любую вершину <tex> v \in V </tex> и найдём расстояния до всех других вершин. <tex>d[i] = dist(v, i)</tex><br />
<br />
* Возьмём вершину <tex> u \in V </tex> такую, что <tex>d[u] \geqslant d[t]</tex> для любого <tex>t</tex>. Снова найдём расстояние от <tex>u</tex> до всех остальных вершин. Самое большое расстояние — диаметр дерева.<br />
Расстояние до остальных вершин будем искать [[Обход_в_ширину|алгоритмом <tex>BFS</tex>]].<br />
<br />
=== Реализация ===<br />
<span style="color:green">//граф g представлен списком смежности</span> <br />
'''int''' diameterTree('''list<list<int>>''' g): <br />
v = u = w = 0<br />
d = bfs(g, v)<br />
'''for''' i = 0, i < n, i++<br />
'''if''' d[i] > d[u]<br />
u = i<br />
d = bfs(g, u)<br />
'''for''' i = 0, i < n, i++<br />
'''if''' d[i] > d[w]<br />
w = i<br />
'''return''' d[w]<br />
<br />
=== Обоснование корректности ===<br />
Будем пользоваться свойством, что в любом дереве больше одного листа. Исключительный случай — дерево из одной вершины, но алгоритм сработает верно и в этом случае.<br />
<br />
{{Теорема<br />
|statement=<br />
Искомое расстояние — расстояние между двумя листами.<br />
|proof=<br />
Пусть искомое расстояние — расстояние между вершинами <tex>a, b</tex>, где <tex>b</tex> не является листом. Так как <tex>b</tex> не является листом, то её степень больше единицы, следовательно, из неё существует ребро в непосещённую вершину (дважды посетить вершину <tex>b</tex> мы не можем).<br />
}}<br />
<br />
После запуска алгоритма получим дерево <tex>BFS</tex>.<br />
<br />
{{Теорема<br />
|statement=<br />
В дереве <tex>BFS</tex> не существует ребер между вершинами из разных поддеревьев некоторого их общего предка.<br />
|proof=<br />
Предположим, существует ребро <tex>u, v</tex> между соседними поддеревьями:<br />
Рассмотрим первую вершину, в которую приведет наш алгоритм, пусть это вершина <tex>u</tex>, тогда в ходе рассмотрения всех смежных вершин <tex>u</tex> мы добавим в список вершину <tex>v</tex>, тем самым исключив возможность попадания их в разные поддеревья.<br />
}}<br />
<br />
<br />
Мы свели задачу к нахождению вершины <tex>w</tex>, такой что сумма глубин поддеревьев максимальна.<br />
<br />
Докажем, что одно из искомых поддеревьев содержит самый глубокий лист. <br />
Пусть нет, тогда, взяв расстояние от <tex>w</tex> до глубочайшего листа, мы можем улучшить ответ. <br />
<br />
Таким образом мы доказали, что нам нужно взять вершину <tex>u</tex> с наибольшей глубиной после первого <tex>BFS</tex>, очевидно, что ей в пару надо сопоставить вершину <tex>w</tex>, такую что <tex>dist(u, w)</tex> максимально. Вершину <tex>w</tex> можно найти запуском <tex>BFS</tex> из <tex>u</tex>. <br />
<br />
=== Оценка времени работы ===<br />
Все операции кроме <tex>BFS</tex> — <tex>O(1)</tex>.<br />
<tex>BFS</tex> работает за линейное время, запускаем мы его два раза. Получаем <tex>O(|V| + |E|)</tex>.<br />
<br />
== Центр дерева ==<br />
=== Определения ===<br />
{{Определение<br />
|id = tree<br />
|definition =<br />
'''Эксцентриситет вершины <tex>e(v)</tex>''' (англ. ''eccentricity of a vertex'') — <tex>\max\limits_{u\in V} dist(v, u)</tex>, где <tex>V</tex> — множество вершин связного графа <tex>G</tex>.<br />
}}<br />
{{Определение<br />
|id = tree<br />
|definition =<br />
'''Радиус <tex>r(G)</tex>''' (англ. ''radius'') — наименьший из эксцентриситетов вершин графа <tex>G</tex>.<br />
}}<br />
{{Определение<br />
|id = tree<br />
|definition =<br />
'''Центральная вершина''' (англ. ''central vertex'') — вершина графа <tex>G</tex>, такая что <tex>e(v) = r(G)</tex> <br />
}}<br />
{{Определение<br />
|id = tree<br />
|definition =<br />
'''Центр графа <tex>G</tex>''' (англ. ''center of a graph'') — множество всех центральных вершин графа <tex>G</tex>.<br />
}}<br />
[[Файл:Центральные_вершины.png|300px|thumb|left|Примеры деревьев с одной и двумя центральными вершинами]]<br />
[[Файл:Эксцентриситеты.png|400px|thumb|center|Графы, у которых показан эксцентриситет каждой вершины]]<br />
<br />
=== Алгоритм ===<br />
==== Наивный алгоритм ====<br />
Найдём центр графа исходя из его определения.<br />
* Построим матрицу <tex>A_{n \times n}</tex> (<tex>n</tex> — мощность множества <tex>V</tex>), где <tex>a_{ij} = d_{ij}</tex>, то есть матрицу кратчайших путей. Для её построения можно воспользоваться [[Алгоритм_Флойда|алгоритмом Флойда-Уоршелла]] или [[Алгоритм_Дейкстры|Дейкстры]].<br />
* Подсчитаем максимум в каждой строчке матрицы <tex>A</tex>. Таким образом, получим массив длины <tex>n</tex>.<br />
* Найдём наименьший элемент в этом массиве. Эта вершина и есть центр графа. В том случае, когда вершин несколько, все они являются центрами. <br />
Асимптотика зависит от используемого способа подсчета кратчайших путей. При Флойде это будет <tex>O(V^3)</tex>, а при Дейкстре — максимум из асимптотики конкретной реализации Дейкстры и <tex>O(V^2)</tex>, за которую мы находим максимумы в матрице.<br />
<br />
==== Алгоритм для дерева за O(n) ====<br />
<br />
{{Теорема<br />
|statement=<br />
Каждое дерево имеет центр, состоящий из одной вершины или из двух смежных вершин. <br />
|proof=<br />
Утверждение очевидно для деревьев с одной и двумя вершинами. Покажем, что у любого другого дерева <tex>T</tex> те же центральные вершины, что и у дерева <tex>T'</tex>, полученного из <tex>T</tex> удалением всех его висячих вершин. Расстояние от данной вершины дерева <tex>u</tex> до любой другой вершины <tex>v</tex> достигает наибольшего значения, когда <tex>v</tex> – висячая вершина. Таким образом, эксцентриситет каждой вершины дерева <tex>T'</tex> точно на единицу меньше эксцентриситета этой же вершины в дереве <tex>T</tex>, следовательно, центры этих деревьев совпадают. Продолжим процесс удаления и получим требуемое.<br />
}}<br />
<br />
Собственно, алгоритм нахождения центра описан в доказательстве теоремы.<br />
<br />
* Пройдёмся по дереву [[Обход_в_глубину,_цвета_вершин|обходом в глубину]] и пометим все висячие вершины числом <tex>0</tex>.<br />
* Обрежем помеченные вершины.<br />
* Образовавшиеся листья пометим числом <tex>1</tex> и тоже обрежем.<br />
* Будем повторять, пока на текущей глубине не окажется не более двух листьев, и при этом в дереве будет тоже не более двух листьев. <br />
<br />
Оставшиеся листья являются центром дерева.<br />
<br />
Для того, чтобы алгоритм работал за <tex>O(n)</tex>, нужно обрабатывать листья по одному, поддерживая в [[Очередь|очереди]] два последовательных по глубине слоя.<br />
<br />
== См. также ==<br />
*[[Дерево,_эквивалентные_определения|Дерево, эквивалентные определения]]<br />
*[[Дополнительный,_самодополнительный_граф|Дополнительный, самодополнительный граф]]<br />
<br />
== Источники информации ==<br />
* [[wikipedia:Distance_(graph_theory)|Wikipedia {{---}} Distance (graph theory)]]<br />
* ''Ф. Харари'': Теория графов<br />
* [http://rain.ifmo.ru/cat/data/theory/graph-location/centers-2006/article.pdf ''А. Клебанов'': Центры графов(нерабочая ссылка)]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Основные определения теории графов]]</div>VictorMinskyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:VictorMinsky&diff=80907Участник:VictorMinsky2021-05-23T23:11:00Z<p>VictorMinsky: Новая страница: «Панасюк Виктор M3136 @VictorMinsky»</p>
<hr />
<div>Панасюк Виктор M3136<br />
<br />
@VictorMinsky</div>VictorMinskyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%AD%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D1%81%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B9_%D0%94%D0%9A%D0%90&diff=80906Эквивалентность состояний ДКА2021-05-23T23:09:30Z<p>VictorMinsky: </p>
<hr />
<div>== Связь эквивалентности состояний и различимости состояний ==<br />
<br />
{{Определение<br />
|definition = Два автомата <tex> \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{1}, T_1\subseteq Q_1 \rangle </tex> и <tex>\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{2}, T_2\subseteq Q_2 \rangle </tex> называются '''эквивалентными''' (англ. ''equivalent''), если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>, то есть <tex>\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition = [[Основные определения, связанные со строками#string|Слово]] <tex>z \in \Sigma^*</tex> '''различает''' (англ. ''distinguish'') два состояния <tex>q_i</tex> и <tex>q_j</tex>, если <br />
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \notin T \Leftrightarrow t_2 \in T) </tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition = Два <em> состояния</em> <tex>q_i</tex> и <tex>q_j</tex> называются '''эквивалентными''' <tex>(q_i \sim q_j)</tex>, если не существует [[Основные определения, связанные со строками#string|строки]], которая их различает, то есть <tex>\forall z \in \Sigma^*</tex> верно, что<br />
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \in T \Leftrightarrow t_2 \in T) </tex>.<br />
}}<br />
<br />
Заметим, что эквивалентность состояний действительно является [[Отношение эквивалентности|отношением эквивалентности]]. Так как <tex> \Leftrightarrow </tex> (равносильность) является отношением эквивалентности и в детерминированном автомате всегда существует путь по любому слову, описанное нами отношение является отношением эквивалентности.<br />
<br />
{{Лемма<br />
|statement =<br />
<tex> \mathcal{A} = \langle Q, \Sigma, \delta, s, T \rangle </tex>, <tex> p_1, p_2, q_1, q_2 \in Q </tex>, <tex> q_i = \delta(p_i, c) </tex>, <tex> w \in \Sigma^*</tex> различает <tex> q_1 </tex> и <tex> q_2 </tex>. Тогда <tex>cw</tex> различает <tex> p_1 </tex> и <tex> p_2 </tex>.<br />
|proof = <br />
<tex> \langle p_i, cw \rangle \vdash \langle q_i, w \rangle \vdash^* \langle t_i, \varepsilon \rangle </tex><br />
А значит, по условию различимости для <tex> q_1 </tex> и <tex> q_2</tex> , <tex> t_1 \in T \Leftrightarrow t_2 \notin T </tex><br />
}}<br />
<br />
=== Пример ===<br />
[[Файл:avtomat2.png|200px]] [[Файл:avtomat3.png|200px]]<br />
<br />
Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <tex> \lbrace 0, 1\rbrace </tex>. Стартовые и все допускающие состояния автоматов эквивалентны между собой.<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Автоматы и регулярные языки]]<br />
<br />
== Проверка ДКА на эквивалентность ==<br />
Заданы два автомата: <tex> \mathcal{A}_1 </tex> со стартовым состоянием <tex> s_1 </tex> и <tex> \mathcal{A}_2 </tex> со стартовым состоянием <tex> s_2 </tex> соответственно. Нужно проверить их на эквивалентность.<br />
<br />
'''Замечание:''' для реализации оба автомата обязательно должны иметь [[Детерминированные_конечные_автоматы#допускает|дьявольские состояния]].<br />
=== Проверка через минимизацию ===<br />
Для этого построим автомат <tex> \mathcal{A} </tex>, содержащий все состояния обоих автоматов и изначальные переходы между ними. Стартовым состоянием в новом автомате можно сделать <tex> s_1 </tex> или <tex> s_2 </tex> — это не имеет значения. При этом состояния одного из автоматов станут недостижимыми из новой стартовой вершины в новом автомате, но для алгоритма это и не важно.<br><br />
[[Файл:auto_equiq.png|470px]]<br><br />
Осталось лишь проверить на эквивалентность состояния <tex> s_1 </tex> и <tex> s_2 </tex> в полученном автомате. Их эквивалентность совпадает с эквивалентностью автоматов <tex> \mathcal{A}_1 </tex> и <tex> \mathcal{A}_2 </tex>. Для этого можно применить [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|алгоритм минимизации ДКА]], который разбивает все состояния на классы эквивалентности. Если состояния <tex>s_1</tex> и <tex>s_2</tex> нового автомата в одном классе эквивалентности {{---}} исходные автоматы эквивалентны.<br />
<br />
Также можно минимизировать каждый автомат отдельно и проверить минимизированные версии на изоморфизм.<br />
<br />
=== Проверка через BFS ===<br />
Два автомата можно также проверить на эквивалентность, используя [[Обход в ширину | обход в ширину]]. Будем синхронно обходить два автомата, начиная со стартовых состояний, в поисках такой строки, которая различает два состояния этих автоматов. То есть она будет допускаться одним автоматом, но не будет принадлежать языку другого.<br />
<br />
Поскольку эквивалентные автоматы допускают один и тот же язык, при переходе по одним и тем же символам в обоих автоматах, слово должно приниматься обоими автоматами одновременно. То есть вершины, в которые мы перешли, должны быть либо одновременно терминальными, либо одновременно нетерминальными, что и проверяет приведённый алгоритм. <br />
==== Псевдокод ====<br />
<font color=green>// $\mathtt{aut}[i][c]$ {{---}} номер состояния, в которое есть переход из состояния $i$ по символу $c$</font><br />
'''boolean''' $\mathtt{bfsEquivalenceCheck}$($\mathtt{aut1}$ : '''int[][]''', $\mathtt{aut2}$ : '''int[][]'''):<br />
$Q.\mathtt{push}(\langle s_1, s_2 \rangle) $ <font color=green>// <tex> Q </tex> {{---}} очередь из пар состояний</font><br />
'''while''' $Q \ne \varnothing $ <br />
$u, v \leftarrow Q.\mathtt{pop}()$<br />
'''if''' $\mathtt{isTerminal1[u]} \ne \mathtt{isTerminal2[v]}$<br />
'''return''' ''false''<br />
$\mathtt{used[u][v]} \leftarrow $ ''true''<br />
'''for''' $c \in \Sigma$<br />
'''if''' '''not''' $\mathtt{used[aut1[u][c]][aut2[v][c]]}$<br />
$Q.\mathtt{push}(\langle \mathtt{aut1}[u][c], \mathtt{aut2}[v][c] \rangle)$<br />
'''return''' ''true''<br />
<br />
Корректность алгоритма следует из строго доказательства того факта, что если два состояния $u$ и $v$ различаются какой-то строкой, то они различаются строкой длины $O(n)$.<br />
<br />
Интуитивное понимание алгоритма такое: пусть по строке $w$ мы пришли в состояния $ \langle u, v \rangle $, и пусть они оба нетерминальные. После этого совершим переход по символу $c$ в состояния $ \langle u', v' \rangle $. <br />
<br />
Тогда если $\mathtt{isTerminal1[u']} \ne \mathtt{isTerminal2[v']}$, то строка $wc$ различает эти два состояния. А значит автоматы не эквивалентны.<br />
<br />
== См. также == <br />
* [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|Алгоритм минимизации ДКА]]<br />
* [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]<br />
<br />
== Источники информации ==<br />
* [http://stackoverflow.com/questions/6905043/equivalence-between-two-automata/12623361#12623361 StackOverflow {{---}} Equivalence between two automata]</div>VictorMinskyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%AD%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D1%81%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B9_%D0%94%D0%9A%D0%90&diff=80905Эквивалентность состояний ДКА2021-05-23T23:01:41Z<p>VictorMinsky: </p>
<hr />
<div>== Связь эквивалентности состояний и различимости состояний ==<br />
<br />
{{Определение<br />
|definition = Два автомата <tex> \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{1}, T_1\subseteq Q_1 \rangle </tex> и <tex>\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{2}, T_2\subseteq Q_2 \rangle </tex> называются '''эквивалентными''' (англ. ''equivalent''), если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>, то есть <tex>\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition = [[Основные определения, связанные со строками#string|Слово]] <tex>z \in \Sigma^*</tex> '''различает''' (англ. ''distinguish'') два состояния <tex>q_i</tex> и <tex>q_j</tex>, если <br />
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \notin T \Leftrightarrow t_2 \in T) </tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition = Два <em> состояния</em> <tex>q_i</tex> и <tex>q_j</tex> называются '''эквивалентными''' <tex>(q_i \sim q_j)</tex>, если не существует [[Основные определения, связанные со строками#string|строки]], которая их различает, то есть <tex>\forall z \in \Sigma^*</tex> верно, что<br />
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \in T \Leftrightarrow t_2 \in T) </tex>.<br />
}}<br />
<br />
Заметим, что эквивалентность состояний действительно является [[Отношение эквивалентности|отношением эквивалентности]]. Так как <tex> \Leftrightarrow </tex> (равносильность) является отношением эквивалентности и в детерминированном автомате всегда существует путь по любому слову, описанное нами отношение является отношением эквивалентности.<br />
<br />
{{Лемма<br />
|statement =<br />
<tex> \mathcal{A} = \langle Q, \Sigma, \delta, s, T \rangle </tex>, <tex> p_1, p_2, q_1, q_2 \in Q </tex>, <tex> q_i = \delta(p_i, c) </tex>, <tex> w \in \Sigma^*</tex> различает <tex> q_1 </tex> и <tex> q_2 </tex>. Тогда <tex>cw</tex> различает <tex> p_1 </tex> и <tex> p_2 </tex>.<br />
|proof = <br />
<tex> \langle p_i, cw \rangle \vdash \langle q_i, w \rangle \vdash^* \langle t_i, \varepsilon \rangle </tex><br />
А значит, по условию различимости для <tex> q_1 </tex> и <tex> q_2</tex> , <tex> t_1 \in T \Leftrightarrow t_2 \notin T </tex><br />
}}<br />
<br />
=== Пример ===<br />
[[Файл:avtomat2.png|200px]] [[Файл:avtomat3.png|200px]]<br />
<br />
Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <tex> \lbrace 0, 1\rbrace </tex>. Стартовые и все допускающие состояния автоматов эквивалентны между собой.<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Автоматы и регулярные языки]]<br />
<br />
== Проверка ДКА на эквивалентность ==<br />
Заданы два автомата: <tex> \mathcal{A}_1 </tex> со стартовым состоянием <tex> s_1 </tex> и <tex> \mathcal{A}_2 </tex> со стартовым состоянием <tex> s_2 </tex> соответственно. Нужно проверить их на эквивалентность.<br />
<br />
'''Замечание:''' для реализации оба автомата обязательно должны иметь [[Детерминированные_конечные_автоматы#допускает|дьявольские состояния]].<br />
=== Проверка через минимизацию ===<br />
Для этого построим автомат <tex> \mathcal{A} </tex>, содержащий все состояния обоих автоматов и изначальные переходы между ними. Стартовым состоянием в новом автомате можно сделать <tex> s_1 </tex> или <tex> s_2 </tex> — это не имеет значения. При этом состояния одного из автоматов станут недостижимыми из новой стартовой вершины в новом автомате, но для алгоритма это и не важно.<br><br />
[[Файл:auto_equiq.png|470px]]<br><br />
Осталось лишь проверить на эквивалентность состояния <tex> s_1 </tex> и <tex> s_2 </tex> в полученном автомате. Их эквивалентность совпадает с эквивалентностью автоматов <tex> \mathcal{A}_1 </tex> и <tex> \mathcal{A}_2 </tex>. Для этого можно применить [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|алгоритм минимизации ДКА]], который разбивает все состояния на классы эквивалентности. Если состояния <tex>s_1</tex> и <tex>s_2</tex> нового автомата в одном классе эквивалентности {{---}} исходные автоматы эквивалентны.<br />
<br />
Также можно минимизировать каждый автомат отдельно и проверить минимизированные версии на изоморфизм.<br />
<br />
=== Проверка через BFS ===<br />
Два автомата можно также проверить на эквивалентность, используя [[Обход в ширину | обход в ширину]]. Будем синхронно обходить два автомата, начиная со стартовых состояний, в поисках такой строки, которая различает два состояния этих автоматов. То есть она будет допускаться одним автоматом, но не будет принадлежать языку другого.<br />
<br />
Поскольку эквивалентные автоматы допускают один и тот же язык, при переходе по одним и тем же символам в обоих автоматах, слово должно приниматься обоими автоматами одновременно. То есть вершины, в которые мы перешли, должны быть либо одновременно терминальными, либо одновременно нетерминальными, что и проверяет приведённый алгоритм. <br />
==== Псевдокод ====<br />
<font color=green>// $\mathtt{aut}[i][c]$ {{---}} номер состояния, в которое есть переход из состояния $i$ по символу $c$</font><br />
'''boolean''' $\mathtt{bfsEquivalenceCheck}$($\mathtt{aut1}$ : '''int[][]''', $\mathtt{aut2}$ : '''int[][]'''):<br />
$Q.\mathtt{push}(\langle s_1, s_2 \rangle) $ <font color=green>// <tex>Q</tex> {{---}} очередь из пар состояний</font><br />
'''while''' $Q \ne \varnothing $ <br />
$u, v \leftarrow Q.\mathtt{pop}()$<br />
'''if''' $\mathtt{isTerminal1[u]} \ne \mathtt{isTerminal2[v]}$<br />
'''return''' ''false''<br />
$\mathtt{used[u][v]} \leftarrow $ ''true''<br />
'''for''' $c \in \Sigma$<br />
'''if''' '''not''' $\mathtt{used[aut1[u][c]][aut2[v][c]]}$<br />
$Q.\mathtt{push}(\langle \mathtt{aut1}[u][c], \mathtt{aut2}[v][c] \rangle)$<br />
'''return''' ''true''<br />
<br />
Корректность алгоритма следует из строго доказательства того факта, что если два состояния $u$ и $v$ различаются какой-то строкой, то они различаются строкой длины $O(n)$.<br />
<br />
Интуитивное понимание алгоритма такое: пусть по строке $w$ мы пришли в состояния $ \langle u, v \rangle $, и пусть они оба нетерминальные. После этого совершим переход по символу $c$ в состояния $ \langle u', v' \rangle $. <br />
<br />
Тогда если $\mathtt{isTerminal1[u']} \ne \mathtt{isTerminal2[v']}$, то строка $wc$ различает эти два состояния. А значит автоматы не эквивалентны.<br />
<br />
== См. также == <br />
* [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|Алгоритм минимизации ДКА]]<br />
* [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]<br />
<br />
== Источники информации ==<br />
* [http://stackoverflow.com/questions/6905043/equivalence-between-two-automata/12623361#12623361 StackOverflow {{---}} Equivalence between two automata]</div>VictorMinskyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=75142Системы счисления2020-11-26T10:02:07Z<p>VictorMinsky: /* Источники информации */ links fixed</p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Систе́ма счисле́ния''' (англ. ''numeral system'' или ''system of numeration'') — символический метод записи чисел, представление чисел с помощью письменных знаков.<br />
}}<br />
==Позиционные системы счисления==<br />
<br />
В '''позиционных системах счисления''' (англ. ''positional numeral systems'') один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен.<br />
<br />
Под позиционной системой счисления обычно понимается ''b''-ичная система счисления, которая определяется [https://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BB%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE целым числом] <tex>b>1</tex>, называемым основанием системы счисления.<br />
<br />
===Запись числа в ''b''-ичной системе счисления===<br />
<br />
Целое число ''x'' в ''b''-ичной системе счисления представляется в виде конечной линейной комбинации степеней числа ''b'':<br />
: <tex>x = \sum\limits_{k=0}^{n-1} a_k b^k</tex>, где <tex>a_k</tex> — это целые числа, называемые '''цифрами''', удовлетворяющие неравенству <tex>0 \leqslant a_k \leqslant (b-1)</tex>.<br />
Каждая степень <tex>b^k</tex> в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя <tex>k</tex> (номером разряда). Обычно для ненулевого числа <tex>x</tex> требуют, чтобы старшая цифра <tex>a_{n-1}</tex> в ''b''-ичном представлении <tex>x</tex> была также ненулевой.<br />
<br />
Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число <tex>x</tex> записывают в виде последовательности его ''b''-ичных цифр, перечисляемых по убыванию старшинства разрядов слева направо:<br />
: <tex>x = a_{n-1} a_{n-2}\dots a_0.</tex><br />
Например, число ''сто три'' представляется в десятичной системе счисления в виде:<br />
: <tex> 103 = 1 \cdot 10^{2} + 0 \cdot 10^{1} + 3 \cdot 10^{0}.</tex><br />
<br />
Наиболее употребляемыми в настоящее время позиционными системами являются:<br />
* <tex>1</tex> — единичная (как позиционная может и не рассматриваться; счёт на пальцах, зарубки, узелки «на память» и др.);<br />
* <tex>2</tex> — двоичная (в дискретной математике, информатике, программировании);<br />
* <tex>8</tex> — восьмеричная;<br />
* <tex>10</tex> — десятичная (используется повсеместно);<br />
* <tex>12</tex> — двенадцатеричная (счёт дюжинами);<br />
* <tex>16</tex> — шестнадцатеричная (используется в программировании, информатике).<br />
<br />
==Смешанные системы счисления==<br />
<br />
'''Смешанная система счисления''' (англ. ''mixed radix numeral systems'') является обобщением <tex>b</tex>-ичной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел <tex>\{b_k\}_{k=0}^{\infty}</tex> и каждое число <tex>x</tex> представляется как линейная комбинация:<br />
: <tex>x = \sum\limits_{k=0}^{n-1} a_{k}b_k</tex>, где на коэффициенты <tex>a_{k}</tex> (называемые как и прежде ''цифрами'') накладываются некоторые ограничения.<br />
Записью числа <tex>x</tex> в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса <tex>k</tex>, начиная с первого ненулевого.<br />
<br />
В зависимости от вида <tex>b_k</tex> как функции от <tex>k</tex> смешанные системы счисления могут быть степенными, показательными и т. п. Когда <tex>b_k=b^k</tex> для некоторого <tex>b</tex>, показательная смешанная система счисления совпадает с <tex>b</tex>-ичной системой счисления.<br />
<br />
Наиболее известным примером смешанной системы счисления являются представление времени в виде количества суток, часов, минут и секунд. При этом величина <tex>d</tex> дней, <tex>h</tex> часов, <tex>m</tex> минут, <tex>s</tex> секунд'' соответствует значению <tex>d\cdot 24\cdot 60\cdot 60 + h\cdot 60\cdot 60 + m\cdot 60 + s\ </tex><tex>\ </tex> секунд.<br />
<br />
==Фибоначчиева система счисления==<br />
<br />
{{Определение<br />
|definition=<br />
Последовательность чисел Фибоначчи <tex>\left\{F_n\right\}</tex> задается линейным рекуррентным соотношением:<br />
: <tex>F_0 = 0,\qquad F_1 = 1,\qquad F_{n+1} = F_n + F_{n-1}, \quad n\in\mathbb{N}.</tex><br />
}}<br />
<br />
'''Фибоначчиева система счисления''' основывается на [https://en.wikipedia.org/wiki/Fibonacci_number числах Фибоначчи].<br />
<br />
: <tex>x = \sum\limits_{k=0}^n f_k F_k</tex>, где <tex>F_k</tex> — числа Фибоначчи, <tex>f_k\in\{0,1\}</tex>, при этом в записи <tex>f_nf_{n-1}\ldots f_0</tex> не встречается две единицы подряд.<br />
<br />
Таким образом, любое неотрицательное целое число <tex>a = 0,\ 1,\ 2,\ldots </tex> можно единственным образом представить через последовательность битов …ε<sub>k</sub>…ε<sub>4</sub>ε<sub>3</sub>ε<sub>2</sub>: <tex>a = \sum\limits_k \varepsilon_k F_k,\ \varepsilon_k\in\{0,1\}</tex>, причём последовательность {ε<sub>k</sub>} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <tex>\forall k \geqslant 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</tex>.<br />
За исключением последнего свойства, данное представление аналогично двоичной системе счисления.<br />
<br />
{{Теорема<br />
|id=th1<br />
|author=Цекендорф<br />
|statement=<br />
Любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.<br />
|proof=<br />
Доказательство существования легко провести по индукции. Любое целое число <tex>a \geqslant 1</tex> попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого <tex>n \geqslant 2</tex> верно неравенство: <tex>F_n \leqslant a < F_{n+1}</tex>. Таким образом, <tex>a = F_n + a'</tex>, где <tex>a'=a-F_n\ <\ F_{n-1}</tex>, так что разложение числа <tex>a'</tex> уже не будет содержать слагаемого <tex>F_{n-1}</tex>.<br />
}}<br />
<br />
== См. также ==<br />
*[[Арифметика чисел в b-ичной системе счисления (Длинная арифметика) | Арифметика чисел в b-ичной системе счисления (Длинная арифметика)]]<br />
*[[Разложение на множители (факторизация) | Разложение на множители (факторизация)]]<br />
<br />
== Источники информации ==<br />
* [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F Системы счисления]<br />
* [https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F Фибоначчиева система счисления]<br />
* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A6%D0%B5%D0%BA%D0%B5%D0%BD%D0%B4%D0%BE%D1%80%D1%84%D0%B0 Теорема Цекендорфа]<br />
<br />
[[Категория: Теория чисел]]</div>VictorMinskyhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B0&diff=75085Отношение порядка2020-10-08T11:11:22Z<p>VictorMinsky: Коррекция ссылки</p>
<hr />
<div>== Определения ==<br />
{{Определение<br />
|definition =<br />
[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''отношением частичного порядка''' (англ. ''partial order relation''), если оно обладает следующими свойствами:<br />
* [[Рефлексивное отношение|Рефлексивность]] (англ. ''reflexivity''): <tex>\forall a \in X: aRa</tex>.<br />
* [[Антисимметричное отношение|Антисимметричность]] (англ. ''antisymmetry''): <tex>\forall a, b \in X:</tex> если <tex>aRb</tex> и <tex>bRa</tex>, то <tex> a = b </tex>.<br />
* [[Транзитивное отношение|Транзитивность]] (англ. ''transitivity''): <tex>\forall a, b, c \in X:</tex> если <tex>aRb</tex> и <tex>bRc</tex>, то <tex>aRc</tex>.<br />
}}<br />
Множество <tex>X</tex>, на котором введено отношение частичного порядка, называется '''частично упорядоченным'''.<br />
<br />
Отношение частичного порядка также называют '''нестрогим порядком''' (англ. ''non-strict order'').<br />
{{Определение<br />
|definition =<br />
[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''строгим отношением частичного порядка''' (англ. ''strict order relation''), если оно обладает следующими свойствами:<br />
* [[Рефлексивное отношение|Антирефлексивность]] (англ. ''irreflexivity''): <tex>\forall a \in X: aRa </tex> — не выполняется.<br />
* [[Антисимметричное отношение|Антисимметричность]] (англ. ''antisymmetry''): <tex>\forall a, b \in X:</tex> если <tex>aRb</tex> и <tex>bRa</tex>, то <tex> a = b </tex>.<br />
* [[Транзитивное отношение|Транзитивность]]: (англ. ''transitivity'') <tex>\forall a, b, c \in X:</tex> если <tex>aRb</tex> и <tex>bRc</tex>, то <tex>aRc</tex>.<br />
}}<br />
{{Определение<br />
|definition =<br />
[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''отношением линейного порядка''' (англ. ''total order relation''), если оно является отношением частичного порядка и обладает следующим свойством:<br />
<tex>\forall a \in X \forall b \in X</tex> либо <tex>aRb</tex>, либо <tex>bRa</tex>.<br />
}}<br />
Множество <tex>X</tex>, на котором введено отношение линейного порядка, называется '''линейно упорядоченным''' (англ. ''total order'').<br />
{{Определение<br />
|definition =<br />
[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''отношением полного порядка''' (англ. ''well-order relation''), если оно является отношением линейного порядка и обладает следующим свойством:<br />
<tex>\forall Y \subset X \exists a \in Y \forall b \in Y: aRb</tex>.<br />
}}<br />
Множество <tex>X</tex>, на котором введено отношение полного порядка, называется '''полностью упорядоченным''' (англ. ''well-order'').<br />
<br />
Отношение нестрогого порядка обозначают символом <tex>\leqslant</tex>. Запись вида <tex>a \leqslant b</tex> читают как «<tex>a</tex> меньше либо равно <tex>b</tex>».<br />
<br />
Отношение строгого порядка обозначают символом <tex><</tex>. Запись вида <tex>a < b</tex> читают как «<tex>a</tex> меньше <tex>b</tex>».<br />
<br />
== Примеры ==<br />
<br />
* На множестве вещественных чисел отношения «больше» и «меньше» являются отношениями строгого порядка, а «больше или равно» и «меньше или равно» — нестрогого, причем линейного порядка, но не полного.<br />
* Отношение «является делителем» на множестве натуральных чисел является отношением частичного порядка.<br />
* Отношение «меньше или равно» является отношением полного порядка на множестве натуральных чисел.<br />
* Отношение «лексикографически не меньше» на множестве всех возможных слов, составленных из букв русского алфавита, является отношением полного порядка.<br />
* Отношение «состоит в подчинении» на множестве работников компании является отношением нестрогого порядка. <br />
* Можно рассмотреть отношение «не младше» на множестве некоторой группы людей. Для соблюдения всех тонкостей скажем, что их даты рождения различны. Это отношение транзитивно (если ''человек A'' не младше ''человека B'', а ''человек B'' не младше ''человека C'', то ''человек A'' не младше ''человека C''), антисимметрично (если ''человек A'' не младше ''человека B'' и ''человек B'' не младше ''человека A'', то это один и тот же человек) и рефлексивно (каждый человек не младше самого себя). Из этого следует, что данное отношение является отношением частичного линейного порядка.<br />
<br />
* Отношение «является делителем» на множестве целых чисел не является отношением частичного порядка. Это легко видеть на следующем примере: <tex> 2 </tex> делится на <tex> -2 </tex>, а <tex> -2 </tex> делится на <tex> 2 </tex>. Однако <tex> 2 \neq -2</tex>.<br />
* Отношение «больше или равно по модулю» на множестве комплексных чисел не является отношением порядка. Из равенства модулей не следует равенство самих чисел, тем самым нарушается антисимметричность. Это демонстрирует данный пример: модули комплексных чисел <tex> 3 + 4i </tex> и <tex> 4 + 3i </tex> равны, но сами числа разные.<br />
<br />
==См. также==<br />
* [[Бинарное_отношение|Бинарное отношение]]<br />
* [[Композиция_отношений|Композиция отношений]]<br />
* [[Отношение_эквивалентности|Отношение эквивалентности]]<br />
<br />
== Источники информации ==<br />
* Новиков Ф. А. {{---}} Дискретная математика для программистов: Учебник для вузов. 3-е изд. {{---}} СПБ.: Питер, 2009 {{---}} 50 с.<br />
* [https://en.wikipedia.org/wiki/Total_order Wikipedia {{---}} Total order]<br />
* [https://ru.wikipedia.org/wiki/%D0%9E%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B0 Википедия {{---}} Отношение порядка]<br />
* [http://ru.math.wikia.com/wiki/%D0%9E%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B0 Wikia {{---}} Отношение порядка]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Отношения]]</div>VictorMinsky