Обсуждение участника:SergeyBud - История изменений

SergeyBud в 17:22, 22 мая 2015

2015-05-22T17:22:37Z

SergeyBud в 17:15, 22 мая 2015

2015-05-22T17:15:31Z

194.85.161.36 в 12:31, 22 мая 2015

2015-05-22T12:31:18Z

SergeyBud: Удалено содержимое страницы

2015-01-09T20:17:56Z

Удалено содержимое страницы

SergeyBud в 23:08, 8 января 2015

2015-01-08T23:08:26Z

Shersh в 10:34, 8 января 2015

2015-01-08T10:34:08Z

SergeyBud в 22:09, 7 января 2015

2015-01-07T22:09:06Z

Внесённые изменения

SergeyBud: /* Эффективность */

2014-06-12T11:54:41Z

‎Эффективность

SergeyBud: /* Расход памяти */

2014-06-12T11:50:35Z

‎Расход памяти

SergeyBud: /* Добавление элементов */

2014-06-12T11:43:16Z

‎Добавление элементов

← Предыдущая		Версия 17:22, 22 мая 2015
Строка 1:		Строка 1:
−	'''Формулировка задачи:''' По заданному слову ~~длины~~ <tex>m</tex> найти в тексте или словаре ~~размера~~ <tex>n</tex> все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом <tex>k</tex> возможных различий.	+	'''Формулировка задачи:''' По заданному слову <tex>X[0..m-1]</tex> найти в тексте или словаре <tex>Y[0..n-1]</tex> все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом <tex>k</tex> возможных различий.

	==Описание задачи с точки зрения динамического программирования==		==Описание задачи с точки зрения динамического программирования==

@@ Строка 1: / Строка 1: @@
 '''Формулировка задачи:''' По заданному слову длины <tex>m</tex> найти в тексте или словаре размера <tex>n</tex> все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом <tex>k</tex> возможных различий.
-==Алгоритм==
+==Описание задачи с точки зрения динамического программирования==
 Пусть <tex>d_{i,j}</tex> - расстояние между префиксами строк <tex>x</tex> и <tex>y</tex>, длины которых равны, соответственно, <tex>i</tex> и <tex>j</tex>, то есть
 <tex>d_{i,j} = d(x(1,i), y(1,j))</tex>.
@@ Строка 24: / Строка 22: @@
 <tex>d_{i,j} = min(d_{i-1,j} + w(x_i,{\varepsilon}), d_{i,j-1} + w({\varepsilon}, y_j), d_{i-1,j-1} + w(x_i, y_i))</tex>
-Теперь каждое значение, не превосходящее <tex>k</tex>, в конечной строке указывает позицию в тексте, в которой заканчивается строка, имеющая не больше <tex>k</tex> отличий от образца.
+Теперь каждое значение, не превосходящее <tex>k</tex>, в последней строке указывает позицию в тексте, в которой заканчивается строка, имеющая не больше <tex>k</tex> отличий от образца.
 [[Алгоритм_Укконена|Алгоритм Укконена]] говорит, что при вычисления расстояний между строками, диагонали матрицы можно пронумеровать целыми числами <tex>p {\in} [-m, n]</tex>, таким образом, чтобы диагональ <tex>p</tex> состояла из элементов <tex>(i, j)</tex>, у которых <tex>j - i = p</tex>. Пусть <tex>r_{p,q}</tex> представляет наибольшую строку <tex>i</tex>, у которой <tex>d_{i,j} = q</tex> и <tex>(i, j)</tex> лежит на диагонали <tex>p</tex>. Таким образом, <tex>q</tex> – это минимальное число различий между <tex>x(1, r_{p,q})</tex> и любой подстрокой текста, заканчивающейся <tex>y_{r_{p,q}+p}</tex>. Значение <tex>m</tex> в строке <tex>r_{p,q}</tex>, для <tex>q < k</tex>, указывает, что в тексте имеется вхождение образца с точностью до <tex>k</tex> отличий, заканчивающееся в <tex>y_{m+p}</tex>. Таким образом, чтобы решить задачу <tex>k</tex> различий, достаточно вычислить значения <tex>r_{p,q}</tex> для <tex>q < k</tex>.
-Рассмотрим алгоритм вычисления <tex>r_{p,q}</tex>, используя [[Динамическое_программирование|динамическое программирование]].
+Рассмотрим алгоритм вычисления <tex>r_{p,q}</tex>.
   '''for''' p = 0 '''to''' n
      r(p,-1) = -1
@@ Строка 45: / Строка 50: @@
        '''if''' r(p,q) = m
           имеется вхождение с k отличиями, заканчивающееся в y(p+m)
-Алгоритм вычисляет значения <tex>r_{p,t}</tex> на <tex>n+k+1</tex> диагоналях. Для каждой диагонали переменной строки <tex>r</tex> можно присвоить не больше <tex>m</tex> различных значений, что приводит к времени вычислений <tex>O(mn)</tex>. Рассмотрим как можно ускорить решение этой задачи, используя другие методы.
+Алгоритм вычисляет значения <tex>r_{p,q}</tex> на <tex>n+k+1</tex> диагоналях. Для каждой диагонали переменной строки <tex>r</tex> можно присвоить не больше <tex>m</tex> различных значений, что приводит к времени вычислений <tex>O(mn)</tex>. Рассмотрим как можно ускорить решение этой задачи, используя другие методы.
 ===Предварительные вычисления===

← Предыдущая	Версия 12:31, 22 мая 2015
Строка 1:	Строка 1:
	+	'''Формулировка задачи:''' По заданному слову длины <tex>m</tex> найти в тексте или словаре размера <tex>n</tex> все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом <tex>k</tex> возможных различий.

	+	==Алгоритм==
	+
	+	====Описание задачи с точки зрения динамического программирования====
	+	Пусть <tex>d_{i,j}</tex> - расстояние между префиксами строк <tex>x</tex> и <tex>y</tex>, длины которых равны, соответственно, <tex>i</tex> и <tex>j</tex>, то есть
	+	<tex>d_{i,j} = d(x(1,i), y(1,j))</tex>.
	+	Чтобы решить задачу <tex>k</tex> различий, [[wikipedia:ru:Матрица_расстояний\|матрицу расстояний]] надо преобразовать таким образом, чтобы <tex>d_{i,j}</tex> представлял минимальное расстояние между <tex>x(1, i)</tex> и любой подстрокой <tex>y</tex>, заканчивающейся символом <tex>y_j</tex>. Для этого достаточно ввести условие:
	+
	+	<tex>d_{0,j} = 0, 0 < j < n</tex> .
	+
	+	Оставшуюся часть матрицы вычислим с использованием цен редактирования расстояния Левенштейна и рекуррентного соотношения для <tex>d_{i,j}</tex>:
	+
	+	<tex>w(a,{\varepsilon}) = 1</tex>
	+
	+	<tex>w({\varepsilon}, b) = 1</tex>
	+
	+	<tex>w(a, b) = \left\{\begin{array}{llcl}
	+	0&,\ a{\ne}b\\
	+	1&,\ a=b\\
	+	\end{array}\right.
	+	</tex>
	+
	+	<tex>d_{i,j} = min(d_{i-1,j} + w(x_i,{\varepsilon}), d_{i,j-1} + w({\varepsilon}, y_j), d_{i-1,j-1} + w(x_i, y_i))</tex>
	+
	+	Теперь каждое значение, не превосходящее <tex>k</tex>, в конечной строке указывает позицию в тексте, в которой заканчивается строка, имеющая не больше <tex>k</tex> отличий от образца.
	+
	+	[[Алгоритм_Укконена\|Алгоритм Укконена]] говорит, что при вычисления расстояний между строками, диагонали матрицы можно пронумеровать целыми числами <tex>p {\in} [-m, n]</tex>, таким образом, чтобы диагональ <tex>p</tex> состояла из элементов <tex>(i, j)</tex>, у которых <tex>j - i = p</tex>. Пусть <tex>r_{p,q}</tex> представляет наибольшую строку <tex>i</tex>, у которой <tex>d_{i,j} = q</tex> и <tex>(i, j)</tex> лежит на диагонали <tex>p</tex>. Таким образом, <tex>q</tex> – это минимальное число различий между <tex>x(1, r_{p,q})</tex> и любой подстрокой текста, заканчивающейся <tex>y_{r_{p,q}+p}</tex>. Значение <tex>m</tex> в строке <tex>r_{p,q}</tex>, для <tex>q < k</tex>, указывает, что в тексте имеется вхождение образца с точностью до <tex>k</tex> отличий, заканчивающееся в <tex>y_{m+p}</tex>. Таким образом, чтобы решить задачу <tex>k</tex> различий, достаточно вычислить значения <tex>r_{p,q}</tex> для <tex>q < k</tex>.
	+
	+	Рассмотрим алгоритм вычисления <tex>r_{p,q}</tex>, используя [[Динамическое_программирование\|динамическое программирование]].
	+	'''for''' p = 0 '''to''' n
	+	r(p,-1) = -1
	+	'''for''' p = -(k+1) '''to''' -1
	+	r(p,\|p\|-1) = \|p\|-1
	+	r(p,\|p\|-2) = \|p\|-2
	+	'''for''' q = -1 '''to''' k
	+	r(n+1,q) = -1
	+	'''for''' q = 0 '''to''' k
	+	'''for''' p = -q '''to''' n
	+	r = max(r(p,q-1) + 1, r(p-1,q-1), r(p+1,q-1) + 1)
	+	r = min(r, m)
	+	'''while''' r < m '''and''' r + p < n '''and''' x(r+1) = y(r+1+p)
	+	r++
	+	r(p,q) = r
	+	'''if''' r(p,q) = m
	+	имеется вхождение с k отличиями, заканчивающееся в y(p+m)
	+	Алгоритм вычисляет значения <tex>r_{p,t}</tex> на <tex>n+k+1</tex> диагоналях. Для каждой диагонали переменной строки <tex>r</tex> можно присвоить не больше <tex>m</tex> различных значений, что приводит к времени вычислений <tex>O(mn)</tex>. Рассмотрим как можно ускорить решение этой задачи, используя другие методы.
	+	===Предварительные вычисления===
	+
	+	На этапе предварительной обработки, с помощью алгоритма Вейнера<ref>[http://europa.zbh.uni-hamburg.de/pubs/pdf/GieKur1997.pdf Giegerich R., Kurtz S. {{---}} From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction]</ref> строится [[wikipedia:ru:Суффиксное_дерево\|суффиксное дерево]] строки <tex>y{\#}x{\$}</tex>, где <tex>\#</tex> и <tex>\$</tex> – символы, не принадлежащие алфавиту, над которыми построены строки <tex>x</tex> и <tex>y</tex>. Этот алгоритм требует линейных затрат памяти, и, для алфавита фиксированного размера, линейного времени. Для неограниченных алфавитов этот алфавит можно преобразовать так, что он будет выполняться за время <tex>O(n\log{\sigma})</tex>, где <tex>\sigma</tex> – число различающихся символов образца. Стадия предварительной обработки требует время <tex>O(n)</tex> и <tex>O(n\log{m})</tex> для постоянного и неограниченного алфавитов, соответственно.
	+	===Модификация предыдущего алгоритма===
	+
	+	В приведенном выше алгоритме перед циклом <tex>while</tex> для диагонали <tex>p</tex>, переменной <tex>r</tex> было присвоено такое значение, что <tex>x(1, r)</tex> сопоставляется с точностью до <tex>k</tex> различий с некоторой подстрокой текста, заканчивающейся <tex>y_{r+p}</tex>. Тогда функция цикла <tex>while</tex> находит максимальное значение для которого <tex>x(r+1, r+h) = y(r+p+1, r+p+h)</tex>. Обозначим это значение как <tex>h</tex>. Это эквивалентно нахождению длины самого длинного общего префикса суффиксов <tex>x(r+1, m)\$</tex> и <tex>y(r+p+1,n){\#}x{\$}</tex> предварительно вычисленной конкатенированной строки. Символ <tex>\#</tex> используется для предотвращения ситуаций, в которых может ошибочно рассматриваться префикс, состоящий из символов как <tex>y</tex>, так и <tex>x</tex>. Обозначим <tex>lca(r,p)</tex> как самый низкий общий предок в суффиксном дереве с листьями, определенными вышеуказанными суффиксами, тогда нужное значение <tex>h</tex> задается <tex>length(lca(r,p))</tex>.
	+	===Оценка времени работы===
	+
	+	Суффиксное дерево имеет <tex>O(n)</tex> узлов. Для поддержки определения самого низкого общего предка за линейное время, алгоритмам <tex>LCA</tex> требуется преобразование дерева, проводимое за линейное время. Значения <tex>r_{p,q}</tex> вычисляются на <tex>n+k+1</tex> диагоналях. Более того, для каждой диагонали надо вычислить <tex>k+1</tex> таких значений, что в общей сложности дает <tex>O(kn)</tex> запросов. Таким образом, общее время работы алгоритма k различий составляет <tex>O(kn)</tex> для алфавитов фиксированного размера, и <tex>O(n * \log{m} + kn)</tex> для неограниченных алфавитов.
	+	===Параллельная версия алгоритма===
	+
	+	В 1989 году Ландау и Вишкин разработали параллельную версию алгоритма. Она позволяет уменьшить время работы до <tex>O(\log{n}+k)</tex>, при использовании одновременно <tex>n</tex> процессоров. Для данной оценки необходимо, чтобы каждый из процессоров выполнял последовательный запрос <tex>LCA</tex> за <tex>O(1)</tex>.
	+
	+	==Примечания==
	+	<references/>
	+
	+	==Источники информации==
	+	* [http://algolist.manual.ru/search/fsearch/k_razl.php k-различий - алгоритм Ландау-Вишкина]

← Предыдущая		Версия 20:17, 9 января 2015
Строка 1:		Строка 1:
−	~~{{Определение~~
−	~~\|definition =~~
−	Пусть задан граф <tex>G</tex>, тогда его рёберным графом <tex>L(G)</tex> называется [[Основные_определения_теории_графов\|граф]], для которого верны следующие утверждения
−	* любая вершина графа <tex>L(G)</tex> представляет ребро графа <tex>G</tex>,
−	* две вершины графа <tex>L(G)</tex> смежны тогда и только тогда, когда их соответствующие рёбра смежны в <tex>G</tex>.
−	}}

−	~~[[Файл:Line_graph_example.png\|400px\|thumb\|center\|Граф G и его реберный граф L(G)]]~~
−	~~==Свойства==~~
−	~~{{Утверждение~~
−	~~\|statement=Рёберный граф [[Отношение_связности,_компоненты_связности\|связного графа]] связен.~~
−	\|proof= Если G связен, он содержит [[Основные_определения_теории_графов\|путь]], соединяющий любые два его ребра, что переводится в путь графа L(G), содержащий любые две вершины графа L(G).
−	}}
−	~~{{Утверждение~~
−	\|statement=Задача о максимальном независимом множестве для рёберного графа соответствует задаче нахождения максимального паросочетания в исходном графе.
−	}}
−	~~{{Утверждение~~
−	\|statement=Рёберное [[Раскраска_графа#chromatic_number_difinition\|хроматическое число]] графа <tex>G</tex> равно вершинному хроматическому числу его рёберного графа <tex>L(G)</tex>.
−	}}
−	~~{{Утверждение~~
−	~~\|statement=Рёберный граф рёберно-транзитивного графа является вершинно-транзитивным графом.~~
−	}}
−	~~{{Утверждение~~
−	\|statement=Если граф <tex>G</tex> [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов\|Эйлеров граф]], то его рёберный граф является [[Гамильтоновы_графы\|Гамильтоновым графом]].
−	\|proof=Для доказательства приведем контрпример к обратному утверждению. На следующем рисунке граф <tex>L(G)</tex> {{---}} Гамильтонов граф, а граф <tex>G</tex> не является Эйлеровым графом.
−	~~[[Файл:Line_graph_gam_euler.PNG\|300px]]~~
−	}}
−	~~{{Утверждение~~
−	\|statement=Ребра графа <tex>G</tex> можно разбить на полные подграфы таким образом, чтобы ни одна из вершин не принадлежала более чем двум подграфам.
−	}}
−	~~{{Утверждение~~
−	~~\|statement=Реберный граф реберного графа <tex>L(G)</tex> '''не''' является исходным графом <tex>G</tex>.~~
−	}}
−
−
−	~~{{Теорема~~
−	~~\|id=Теорема1~~
−	\|statement=Если <tex>G</tex> {{---}} это <tex>(p,q)</tex>-граф с вершинами, имеющими степени <math>d_i</math>, то <tex>L(G)</tex> имеет <tex>q</tex> вершин и <math>q_L</math> ребер, где
−	~~<math>q_L = -q + {\dfrac{1}{2}}\sum\limits_i{d_{i}^{2}}</math>~~
−	\|proof=По определению реберного графа граф <tex>L(G)</tex> имеет <tex>q</tex> вершин. Каждые <math>d_i</math> ребер, инцидентных вершине <math>v_i</math>, дают вклад <math>\begin{pmatrix} d_i \\ 2 \end{pmatrix}</math> в число ребер графа <tex>L(G)</tex>, так что
−	<math>q_L = \sum\limits_i{\begin{pmatrix} d_i \\ 2 \end{pmatrix}} = \dfrac{1}{2}\sum\limits_i{d_i(d_i-1)} = \dfrac{1}{2}\sum\limits_i{d_i^2}-\dfrac{1}{2}\sum\limits_i{d_i} = \dfrac{1}{2}\sum\limits_i{d_i^2-q}</math>
−	}}
−
−	~~==Построение==~~
−	~~{\| cellpadding="0"~~
−	~~\| [[Файл:line_graph_build_1.png\|200px]] \|\| [[Файл:line_graph_build_2.png\|200px]] \|\| [[Файл:line_graph_build_3.png\|200px]] \|\| [[Файл:line_graph_build_4.png\|200px]]~~
−	\|-
−	~~\|Граф <tex>G</tex> \|\| Новые вершины <tex>L(G)</tex> \|\| Добавлены рёбра в <tex>L(G)</tex> \|\| Рёберный граф <tex>L(G)</tex>~~
−	\|}
−
−	~~==Источники информации==~~
−	*[[wikipedia:ru:Рёберный_граф \| Wikipedia {{---}} Реберные графы ]]
−	* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.(Глава 8: Реберные графы. стр. 91-104)
−
−
−	~~[[Категория: Алгоритмы и структуры данных]]~~
−	~~[[Категория: Основные определения теории графов]]~~

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition =
-Пусть задан граф <tex>G</tex>, тогда его рёберным графом <tex>L(G)</tex> называется граф, для которого верны следующие утверждения:
+Пусть задан граф <tex>G</tex>, тогда его рёберным графом <tex>L(G)</tex> называется [[Основные_определения_теории_графов|граф]], для которого верны следующие утверждения
 * любая вершина графа <tex>L(G)</tex> представляет ребро графа <tex>G</tex>,
 * две вершины графа <tex>L(G)</tex> смежны тогда и только тогда, когда их соответствующие рёбра смежны в <tex>G</tex>.
 }}
 ==Свойства==
-[[Файл:Line_graph_example.png|400px|thumb|right|Граф G и его реберный граф L(G)]]
+{{Утверждение
-* Рёберный граф связного графа связен.
+|statement=Рёберный граф [[Отношение_связности,_компоненты_связности|связного графа]] связен.
-* Задача о максимальном независимом множестве для рёберного графа соответствует задаче нахождения максимального паросочетания в исходном графе.
+|proof= Если G связен, он содержит [[Основные_определения_теории_графов|путь]], соединяющий любые два его ребра, что переводится в путь графа L(G), содержащий любые две вершины графа L(G).
-* Рёберное хроматическое число графа <tex>G</tex> равно вершинному хроматическому числу его рёберного графа <tex>L(G)</tex>.
+}}
-* Рёберный граф рёберно-транзитивного графа является вершинно-транзитивным графом.
+{{Утверждение
-* Если граф <tex>G</tex> имеет Эйлеров цикл, то есть <tex>G</tex> связен и имеет чётное число рёбер в каждой вершине, то его рёберный граф является Гамильтоновым графом.
+|statement=Задача о максимальном независимом множестве для рёберного графа соответствует задаче нахождения максимального паросочетания в исходном графе.
-*Ребра графа <tex>G</tex> можно разбить на полные подграфы таким образом, чтобы ни одна из вершин не принадлежала более чем двум подграфам.
+}}
 {{Теорема
 |id=Теорема1
-|statement=Если <tex>G</tex> {{---}} это <tex>(p,q)</tex> - граф с вершинами, имеющими степени <math>d_i</math>, то <tex>L(G)</tex> имеет <tex>q</tex> вершин и <math>q_L</math> ребер, где
+|statement=Если <tex>G</tex> {{---}} это <tex>(p,q)</tex>-граф с вершинами, имеющими степени <math>d_i</math>, то <tex>L(G)</tex> имеет <tex>q</tex> вершин и <math>q_L</math> ребер, где
-<math>q_L = -q + \frac{1}{2}\sum{d_{i}^{2}}</math>
+<math>q_L = -q + {\dfrac{1}{2}}\sum\limits_i{d_{i}^{2}}</math>
 |proof=По определению реберного графа граф <tex>L(G)</tex> имеет <tex>q</tex> вершин. Каждые <math>d_i</math> ребер, инцидентных вершине <math>v_i</math>, дают вклад <math>\begin{pmatrix} d_i \\ 2 \end{pmatrix}</math> в число ребер графа <tex>L(G)</tex>, так что
-<math>q_L = \sum{\begin{pmatrix} d_i \\ 2 \end{pmatrix}} = \frac{1}{2}\sum{d_i(d_i-1)} = \frac{1}{2}\sum{d_i^2}-\frac{1}{2}\sum{d_i} = \frac{1}{2}\sum{d_i^2-q}</math>
+<math>q_L = \sum\limits_i{\begin{pmatrix} d_i \\ 2 \end{pmatrix}} = \dfrac{1}{2}\sum\limits_i{d_i(d_i-1)} = \dfrac{1}{2}\sum\limits_i{d_i^2}-\dfrac{1}{2}\sum\limits_i{d_i} = \dfrac{1}{2}\sum\limits_i{d_i^2-q}</math>
 }}
 ==Построение==
-[[Файл:line_graph_build_1.png|200px]][[Файл:line_graph_build_2.png|200px]][[Файл:line_graph_build_3.png|200px]][[Файл:line_graph_build_4.png|200px]]
+{| cellpadding="0"
+| [[Файл:line_graph_build_1.png|200px]] || [[Файл:line_graph_build_2.png|200px]] || [[Файл:line_graph_build_3.png|200px]] || [[Файл:line_graph_build_4.png|200px]]
- Граф <tex>G \rightarrow </tex> Вершины <tex>L(G)</tex>, созданные из ребер графа <tex>G \rightarrow </tex> Добавлены рёбра в <tex>L(G) \rightarrow </tex> Рёберный граф <tex>L(G)</tex>
+|-
 ==Источники информации==
 *[[wikipedia:ru:Рёберный_граф | Wikipedia {{---}} Реберные графы ]]
-* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.
+* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.(Глава 8: Реберные графы. стр. 91-104)

@@ Строка 36: / Строка 36: @@
 ==Эффективность==
-Благодаря преимуществам, предоставляемыми HAT (так например вычисление адреса происходит приблизительно в 2 раза быстрее, чем в стандартном массиве C++ {{---}} для соответствующего <tex>power</tex> мы можем сделать предвычисление выражения <tex>(1<<power)-1</tex> тогда для вычисления адреса в обоих массивах потребуется всего одна битовая операция), ее можно использовать в любых программах, требующих работу с массивами переменной длинны, где использование других структур данных (например списков) не удобно. На многих алгоритмах HAT работает значительно быстрее стандартных массивов, дополнительно можно ознакомиться с результатами некоторых тестов<ref>[http://pmg.org.ru/ai/tree_hash.htm  Результаты тестов]</ref>.
+Благодаря тому, что копирования в HAT происходят реже, чем в других реализациях динамических массивов, и в худшем случае требуется <tex>O(\sqrt{N})</tex> памяти, ее можно использовать в любых программах, требующих работу с массивами переменной длинны, где использование других структур данных (например списков) не удобно. На многих алгоритмах HAT работает значительно быстрее стандартных массивов, дополнительно можно ознакомиться с результатами некоторых тестов<ref>[http://pmg.org.ru/ai/tree_hash.htm  Результаты тестов]</ref>.
 == Примечания ==

@@ Строка 33: / Строка 33: @@
 ===Расход памяти===
 HAT использует меньше дополнительной памяти, чем в стандартных подходах к расширению массивов, то есть полном перекопировании и перераспределении всего массива.
-Затраты дополнительной памяти (уже выделенной, но еще не используемой) в  самом плохом случае {{---}} <math>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</math> (этот случай при пустой HAT {{---}} в <tex>top</tex> один указатель на единственный пустой лист). Если в листе будет <tex>power/2</tex> элементов, то ожидаемая трата дополнительной памяти уменьшается до <math>(top + leaf/2) \approx 1.5\sqrt{N}</math>, а это все еще <math>O(\sqrt{N})</math>.
+Затраты дополнительной памяти (уже выделенной, но еще не используемой) в  самом плохом случае {{---}} <math>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</math> (этот случай при пустой HAT {{---}} в <tex>top</tex> один указатель на единственный пустой лист). Если в листе будет <tex>power/2</tex> элементов, то ожидаемая трата дополнительной памяти уменьшается до <math>(top + leaf/2) \approx 1.5\sqrt{N}</math>. Таким образом HAT использует <tex>\Theta(\sqrt{N})</tex> дополнительной памяти. Это лучше [[wikipedia:ru:Динамический массив |динамического массива]], который использует <tex>O(N)</tex> дополнительней памяти сразу после перекопирования элементов. И лучше [[wikipedia:ru:Список (информатика) |списка]].
 ==Эффективность==

@@ Строка 25: / Строка 25: @@
 ===Добавление элементов===
-[[Файл:AlgoF2.gif|400px|left]]
+*Чаще всего при добавлении элемента в одном из листьев (последнем незаполненном на данный момент) найдется свободное место, что позволит осуществить быструю вставку {{---}} <math>O(1)</math>.
-Чаще всего при добавлении элемента в одном из листьев (последнем незаполненном на данный момент) найдется свободное место, что позволит осуществить быструю вставку(<math>O(1)</math>).
+*Реже мы столкнемся со случаем, когда необходимо создать новый лист. Достаточно всего лишь добавить указатель в свободную ячейку главного массива, что также позволит произвести вставку элемента за <math>O(1)</math>.
-Реже мы столкнемся со случаем, когда необходимо создать новый лист. Достаточно всего лишь добавить указатель в свободную ячейку главного массива, что также позволит произвести вставку элемента за <math>O(1)</math>.
+*Самый интересный случай {{---}} когда главный массив и все листья заполнены. Cначала вычислим нужный размер (массивы <tex>top</tex> и <tex>leaf</tex> увеличиваются в <tex>2</tex> раза, то есть <math>power = power \cdot 2 </math>), затем скопируем элементы в новую структуру HAT, освобождая старые листья и распределяя новые листья(размер листа изменился, а значит количество элементов в листе и количество используемых листьев так же изменится).
-Самый интересный случай {{---}} когда главный массив и все листья заполнены. Cначала вычислим нужный размер (массивы <tex>top</tex> и <tex>leaf</tex> увеличиваются в 2 раза, то есть <math>power = power \cdot 2 </math>), затем скопируем элементы в новую структуру HAT, освобождая старые листья и распределяя новые листья(размер листа изменился, а значит количество элементов в листе и количество используемых листьев так же изменится).
+*Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивов переменной длины, потому что увеличения размеров всех массивов происходит редко (как будет видно ниже). Копировать элементы мы будем только тогда, когда главный массив полон (достигли соответствующей степени двойки, то есть <tex> N = (2 \cdot 2)^k</tex>, где <tex>k</tex> {{---}} натуральное число), тогда общая сумма перекопирования будет равна <math>1+4+16+64+256+...+N</math>. Воспользуемся тождеством: <math>(x^{n+1} -1)=(x-1)(1+x+x^2+x^3+... + x^k)</math>, тогда для нашего случая: <math>1 +4+4^2+4^3+...+4^k = (4^{k+1} -1)/(4-1) = (4N-1)/3</math>, или около <math>4N/3</math>. Это означает, что среднее число дополнительных операций копирования {{---}} <math>O(N)</math> для последовательного добавления N элементов, а не <math>O(N^2)</math>. Мы получили <math>4N/3</math> против <math>2N</math> в обычном динамическом массиве, то есть константа уменьшилась.
-Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивов переменной длины, потому что увеличения размеров всех массивов происходит редко (как будет видно ниже). Копировать элементы мы будем только тогда, когда главный массив полон (достигли соответствующей степени двойки, то есть <tex> N = (2 \cdot 2)^k</tex>, где <tex>k</tex> {{---}} натуральное число), тогда общая сумма перекопирования будет равна <math>1+4+16+64+256+...+N</math>. Воспользуемся тождеством: <math>(x^{n+1} -1)=(x-1)(1+x+x^2+x^3+... + x^k)</math>, тогда для нашего случая: <math>1 +4+4^2+4^3+...+4^k = (4^{k+1} -1)/(4-1) = (4N-1)/3</math>, или около <math>4N/3</math>. Это означает, что среднее число дополнительных операций копирования {{---}} <math>O(N)</math> для последовательного добавления N элементов, а не <math>O(N^2)</math>. Мы получили <math>4N/3</math> против <math>2N</math> в обычном динамическом массиве, то есть константа уменьшилась.
+[[Файл:AlgoF2.gif|400px]]
 ===Расход памяти===