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

Вещественный двоичный поиск

2012-06-13T16:32:13Z

Zakirzyanov:

'''Вещественный двоичный поиск''' {{---}} алгоритм поиска аргумента для заданного значения монотонной вещественной функции.

== Формулировка задачи ==
Пусть нам задана монотонная функция. Необходимо найти значение аргумента <tex>x</tex> этой функции, в которой она принимает определенное значение <tex>C</tex>.

[[Файл:Function.png]]

== Решение задачи ==
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.

== Способы закончить поиск ==
* Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
: '''+''' Алгоритм с большой точностью найдет значение аргумента

: – Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
* Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.
: '''+''' В отличии от предыдущего, не зацикливается при больших значениях функции.

: – Возможна большая погрешность, если функция будет очень медленно возрастать
* Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка {{---}} два соседних по представлению значения в типе данных. Утверждается, что два числа {{---}} соседние, если середина их отрезка совпадает или с левой, или с правой границей.
: '''+''' Алгоритм найдет число с максимально возможной точностью.
: – Возможно плохое поведение, если искомый аргумент равен 0.
* Итеративный способ. В этом способе выполнится только конечное число число итераций.
: '''+''' Плюсом этого способа является фиксированная погрешность.
: – Довольно плохая точность, если границы отрезка находятся на большом расстоянии.
== Выбор границы отрезка для поиска==
Для начала найдем правую границу. Выберем произвольную положительную точку (например <tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.

== Псевдокод ==
<pre>
findLeft(c)
x = -1;
while f(x) > c
x = x * 2;
return x;
</pre>
<pre>
findRight(c)
x = 1;
while f(x) < c
x = x * 2;
return x;
</pre>
<pre>
binSearch(c)
left = findLeft(с);
right = findRight(с);
while left < right - eps //Здесь можно использовать другое условие выхода
mid = (left + right) / 2;
if f(mid) == c //**
return mid; //**
else if f(mid) < c
left = mid;
else
right = mid;
return l;
</pre>
== Примеры использования ==
* Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x \ge 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней {{---}} <tex>x</tex>.
* Если функция нестрого монотонна, то, убрав из приведенного выше алгоритма строки, отмеченные <tex>(**)</tex>, мы получим алгоритм, который будет находить <tex>x</tex> такой, что <tex>f(x) = c</tex> и <tex>f(x - \epsilon) < c</tex>.
== Замечания ==
* Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.
* Важным отличием от целочисленного поиска является то, что мы передвигаем границу ровно в середину отрезка (<tex>left = mid</tex>), а не со смещением внутрь отрезка (<tex>left = mid + 1</tex>).
== Источники ==
* [http://www.intuit.ru/department/algorithms/basicalgos/2/ Интернет университет, лекция сортировка и поиск]

Вещественный двоичный поиск

2012-06-12T19:59:27Z

Zakirzyanov:

'''Вещественный двоичный поиск''' {{---}} алгоритм поиска аргумента для заданного значения монотонной вещественной функции.

== Формулировка задачи ==
Пусть нам задана монотонная функция. Необходимо найти значение аргумента <tex>x</tex> этой функции, в которой она принимает определенное значение <tex>C</tex>.

[[Файл:Function.png]]

== Решение задачи ==
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.

== Способы закончить поиск ==
* Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
: '''+''' Алгоритм с большой точностью найдет значение аргумента

: – Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
* Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.
: '''+''' В отличии от предыдущего, не зацикливается при больших значениях функции.

: – Возможна большая погрешность, если функция будет очень медленно возрастать
* Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка {{---}} два соседних по представлению значения в типе данных. Утверждается, что два числа {{---}} соседние, если середина их отрезка совпадает или с левой, или с правой границей.
: '''+''' Алгоритм найдет число с максимально возможной точностью.
: – Возможно плохое поведение, если искомый аргумент равен 0.
* Итеративный способ. В этом способе выполнится только конечное число число итераций.
: '''+''' Плюсом этого способа является фиксированная погрешность.
: – Довольно плохая точность, если границы отрезка находятся на большом расстоянии.
== Выбор границы отрезка для поиска==
Для начала найдем правую границу. Выберем произвольную положительную точку (например <tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.

== Псевдокод ==
<pre>
findLeft(c)
x = -1;
while f(x) > c
x = x * 2;
return x;
</pre>
<pre>
findRight(c)
x = 1;
while f(x) < c
x = x * 2;
return x;
</pre>
<pre>
binSearch(c)
left = findLeft(с);
right = findRight(с);
while left < right - eps //Здесь можно использовать другое условие выхода
mid = (left + right) / 2;
if f(mid) < c
left = mid;
else
right = mid;
return l;
</pre>
== Пример использования ==
Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x \ge 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней {{---}} <tex>x</tex>.
== Замечания ==
Необходимо отметить, то функция должна быть строго монотонна, иначе данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным. Важным отличием от целочисленного поиска является то, что мы передвигаем границу ровно в середину отрезка (<tex>left = mid</tex>), а не со смещением внутрь отрезка (<tex>left = mid + 1</tex>).
== Источники ==
* [http://www.intuit.ru/department/algorithms/basicalgos/2/ Интернет университет, лекция сортировка и поиск]

Вещественный двоичный поиск

2012-06-12T19:52:27Z

Zakirzyanov:

'''Вещественный двоичный поиск''' - алгоритм поиска аргумента для заданного значения монотонной вещественной функции.

== Формулировка задачи ==
Пусть нам задана монотонная функция. Необходимо найти значение аргумента <tex>x</tex> этой функции, в которой она принимает определенное значение <tex>C</tex>.

[[Файл:Function.png]]

== Решение задачи ==
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.

== Способы закончить поиск ==
* Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
: '''+''' Алгоритм с большой точностью найдет значение аргумента

: – Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
* Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.
: '''+''' В отличии от предыдущего, не зацикливается при больших значениях функции.

: – Возможна большая погрешность, если функция будет очень медленно возрастать
* Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних по представлению значения в типе данных. Утверждается, что два числа - соседние, если середина их отрезка совпадает или с левой, или с правой границей.
: '''+''' Алгоритм найдет число с максимально возможной точностью.
: – Возможно плохое поведение, если искомый аргумент равен 0.
* Итеративный способ. В этом способе выполнится только конечное число число итераций.
: '''+''' Плюсом этого способа является фиксированная погрешность.
: – Довольно плохая точность, если границы отрезка находятся на большом расстоянии.
== Выбор границы отрезка для поиска==
Для начала найдем правую границу. Выберем произвольную положительную точку (например <tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.

== Псевдокод ==
<pre>
findLeft(c)
x = -1;
while f(x) > c
x = x * 2;
return x;
</pre>
<pre>
findRight(c)
x = 1;
while f(x) < c
x = x * 2;
return x;
</pre>
<pre>
binSearch(c)
left = findLeft(с);
right = findRight(с);
while left < right - eps //Здесь можно использовать другое условие выхода
mid = (left + right) / 2;
if f(mid) < c
left = mid;
else
right = mid;
return l;
</pre>
== Пример использования ==
Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x \ge 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней - <tex>x</tex>.
== Замечания ==
Необходимо отметить, то функция должна быть строго монотонна, иначе данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным. Важным отличием от целочисленного поиска является то, что мы передвигаем границу ровно в середину отрезка (<tex>left = mid</tex>), а не со смещением внутрь отрезка (<tex>left = mid + 1</tex>).
== Источники ==
* [http://www.intuit.ru/department/algorithms/basicalgos/2/ Интернет университет, лекция сортировка и поиск]

Вещественный двоичный поиск

2012-06-12T19:51:15Z

Zakirzyanov:

'''Вещественный двоичный поиск''' - алгоритм поиска аргумента для заданного значения монотонной вещественной функции.

== Формулировка задачи ==
Пусть нам задана монотонная функция. Необходимо найти значение аргумента <tex>x</tex> этой функции, в которой она принимает определенное значение <tex>C</tex>.

[[Файл:Function.png]]

== Решение задачи ==
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.

== Способы закончить поиск ==
* Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
: '''+''' Алгоритм с большой точностью найдет значение аргумента

: – Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
* Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.
: '''+''' В отличии от предыдущего, не зацикливается при больших значениях функции.

: – Возможна большая погрешность, если функция будет очень медленно возрастать
* Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних по представлению значения в типе данных. Утверждается, что два числа - соседние, если середина их отрезка совпадает или с левой, или с правой границей.
: '''+''' Алгоритм найдет число с максимально возможной точностью.
: – Возможно плохое поведение, если искомый аргумент равен 0.
* Итеративный способ. В этом способе выполнится только конечное число число итераций.
: '''+''' Плюсом этого способа является фиксированная погрешность.
: – Довольно плохая точность, если границы отрезка находятся на большом расстоянии.
== Выбор границы отрезка для поиска==
Для начала найдем правую границу. Выберем произвольную положительную точку (например <tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.

== Псевдокод ==
<pre>
findLeft(c)
x = -1;
while f(x) > c
x = x * 2;
return x;
</pre>
<pre>
findRight(c)
x = 1;
while f(x) < c
x = x * 2;
return x;
</pre>
<pre>
binSearch(c)
left = findLeft(с);
right = findRight(с);
while left < right - eps //Здесь можно использовать другое условие выхода
mid = (left + right) / 2;
if f(mid) < c
left = mid;
else
right = mid;
return l;
</pre>
== Пример использования ==
Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x >= 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней - <tex>x</tex>.
== Замечания ==
Необходимо отметить, то функция должна быть строго монотонна, иначе данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным. Важным отличием от целочисленного поиска является то, что мы передвигаем границу ровно в середину отрезка (<tex>left = mid</tex>), а не со смещением внутрь отрезка (<tex>left = mid + 1</tex>).
== Источники ==
* [http://www.intuit.ru/department/algorithms/basicalgos/2/ Интернет университет, лекция сортировка и поиск]

Вещественный двоичный поиск

2012-06-12T19:41:28Z

Zakirzyanov:

'''Вещественный двоичный поиск''' - алгоритм поиска аргумента для заданного значения монотонной вещественной функции.

== Формулировка задачи ==
Пусть нам задана монотонная функция. Необходимо найти значение аргумента <tex>x</tex> этой функции, в которой она принимает определенное значение <tex>C</tex>.

[[Файл:Function.png]]

== Решение задачи ==
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.

== Способы закончить поиск ==
* Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
: '''+''' Алгоритм с большой точностью найдет значение аргумента

: – Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
* Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.
: '''+''' В отличии от предыдущего, не зацикливается при больших значениях функции.

: – Возможна большая погрешность, если функция будет очень медленно возрастать
* Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних по представлению значения в типе данных. Утверждается, что два числа - соседние, если середина их отрезка совпадает или с левой, или с правой границей.
: '''+''' Алгоритм найдет число с максимально возможной точностью.
: – Возможно плохое поведение, если искомый аргумент равен 0.
* Итеративный способ. В этом способе выполнится только конечное число число итераций.
: '''+''' Плюсом этого способа является фиксированная погрешность.
: – Довольно плохая точность, если границы отрезка находятся на большом расстоянии.
== Выбор границы отрезка для поиска==
Для начала найдем правую границу. Выберем произвольную положительную точку (например </tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.

== Псевдокод ==
<pre>
findLeft(c)
x = -1;
while f(x) > c
x = x * 2;
return x;
</pre>
<pre>
findRight(c)
x = 1;
while f(x) < c
x = x * 2;
return x;
</pre>
<pre>
binSearch(c)
left = findLeft(с);
right = findRight(с);
while left < right - eps //Здесь можно использовать другое условие выхода
mid = (left + right) / 2;
if f(mid) < c
left = mid;
else
right = mid;
return l;
</pre>
== Пример использования ==
Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x >= 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней - <tex>x</tex>.
== Замечания ==
Необходимо отметить, то функция должна быть строго монотонна, иначе данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным. Важным отличием от целочисленного поиска является то, что мы передвигаем границу ровно в середину отрезка (<tex>left = mid</tex>), а не со смещением внутрь отрезка (<tex>left = mid + 1</tex>).
== Источники ==
* [http://www.intuit.ru/department/algorithms/basicalgos/2/ Интернет университет, лекция сортировка и поиск]

Вещественный двоичный поиск

2012-06-12T19:25:18Z

Zakirzyanov:

'''Вещественный двоичный поиск''' - алгоритм поиска аргумента для заданного значения монотонной вещественной функции.

== Формулировка задачи ==
Пусть нам задана монотонная функция. Необходимо найти значение аргумента <tex>x</tex> этой функции, в которой она принимает определенное значение <tex>C</tex>.

[[Файл:Function.png]]

== Решение задачи ==
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.

== Способы закончить поиск ==
* Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
: '''+''' Алгоритм с большой точностью найдет значение аргумента

: <tex>-</tex> Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
* Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.
: '''+''' В отличии от предыдущего, не зацикливается при больших значениях функции.

: <tex>-</tex> Возможна большая погрешность, если функция будет очень медленно возрастать
* Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних по представлению значения в типе данных. Утверждается, что два числа - соседние, если середина их отрезка совпадает или с левой, или с правой границей.
: '''+''' Алгоритм найдет число с максимально возможной точностью.
: <tex>-</tex> Возможно плохое поведение, если искомый аргумент равен 0.
* Итеративный способ. В этом способе выполнится только конечное число число итераций.
: '''+''' Плюсом этого способа является фиксированная погрешность.
: <tex>-</tex> Довольно плохая точность, если границы отрезка находятся на большом расстоянии.
== Выбор границы отрезка для поиска==
Для начала найдем правую границу. Выберем произвольную положительную точку (например </tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.

== Псевдокод ==
<pre>
findLeft(c)
x = -1;
while f(x) > c
x = x * 2;
return x;
</pre>
<pre>
findRight(c)
x = 1;
while f(x) < c
x = x * 2;
return x;
</pre>
<pre>
binSearch(c)
left = findLeft(с);
right = findRight(с);
while left < right - eps //Здесь можно использовать другое условие выхода
mid = (left + right) / 2;
if f(mid) < c
left = mid;
else
right = mid;
return l;
</pre>
== Пример использования ==
Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x >= 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней - <tex>x</tex>.
== Замечания ==
Необходимо отметить, то функция должна быть строго монотонна, иначе данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным. Важным отличием от целочисленного поиска является то, что мы передвигаем границу ровно в середину отрезка (<tex>left = mid</tex>), а не со смещением внутрь отрезка (<tex>left = mid + 1</tex>).
== Источники ==
* [http://www.intuit.ru/department/algorithms/basicalgos/2/ Интернет университет, лекция сортировка и поиск]

Вещественный двоичный поиск

2012-06-12T19:09:38Z

Zakirzyanov:

'''Вещественный двоичный поиск''' - алгоритм поиска аргумента для заданного значения монотонной вещественной функции.

== Формулировка задачи ==
Пусть нам задана монотонная функция. Необходимо найти значение аргумента <tex>x</tex> этой функции, в которой она принимает определенное значение <tex>C</tex>.

[[Файл:Function.png]]

== Решение задачи ==
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.

== Способы закончить поиск ==
* Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
: '''+''' Алгоритм с большой точностью найдет значение аргумента

: '''-''' Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
* Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.
: '''+''' В отличии от предыдущего, не зацикливается при больших значениях функции.

: '''-''' Возможна большая погрешность, если функция будет очень медленно возрастать
* Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних по представлению значения в типе данных. Утверждается, что два числа - соседние, если середина их отрезка совпадает или с левой, или с правой границей.
: '''+''' Алгоритм найдет число с максимально возможной точностью.
: '''-''' Возможно плохое поведение, если искомый аргумент равен 0.
* Итеративный способ. В этом способе выполнится только конечное число число итераций.
: '''+''' Плюсом этого способа является фиксированная погрешность.
: '''-''' Довольно плохая точность, если границы отрезка находятся на большом расстоянии.
== Выбор границы отрезка для поиска==
Для начала найдем правую границу. Выберем произвольную положительную точку (например </tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.

== Псевдокод ==
<pre>
findLeft(c)
x = -1;
while f(x) > c
x = x * 2;
return x;
</pre>
<pre>
findRight(c)
x = 1;
while f(x) < c
x = x * 2;
return x;
</pre>
<pre>
binSearch(c)
left = findLeft(с);
right = findRight(с);
while left < right - eps //Здесь можно использовать другое условие выхода
mid = (left + right) / 2;
if f(mid) < c
left = mid;
else
right = mid;
return l;
</pre>
== Пример использования ==
Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x >= 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней - <tex>x</tex>.
== Замечания ==
Необходимо отметить, то функция должна быть строго монотонна, иначе данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным. Важным отличием от целочисленного поиска является то, что мы передвигаем границу ровно в середину отрезка (<tex>left = mid</tex>), а не со смещением внутрь отрезка (<tex>left = mid + 1</tex>).
== Источники ==
* [http://www.intuit.ru/department/algorithms/basicalgos/2/ Интернет университет, лекция сортировка и поиск]

Вещественный двоичный поиск

2012-06-12T17:34:45Z

Zakirzyanov:

'''Вещественный двоичный поиск''' - алгоритм поиска аргумента для заданного значения монотонной вещественной функции.

== Формулировка задачи ==
Пусть нам задана монотонная функция. Необходимо найти значение (<tex>c</tex>) этой функции в заданной точке (<tex>x</tex>).

[[Файл:Function.png]]

== Решение задачи ==
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.

== Способы закончить поиск ==
* Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
: <tex>\oplus</tex> Алгоритм с большой точностью найдет значение аргумента

: <tex>\ominus</tex> Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
* Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.
: <tex>\oplus</tex> В отличии от предыдущего, не зацикливается при больших значениях функции.

: <tex>\ominus</tex> Возможна большая погрешность, если функция будет очень медленно возрастать
* Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних по представлению значения в типе данных. Утверждается, что два числа - соседние, если середина их отрезка совпадает или с левой, или с правой границей.
: <tex>\ominus</tex> Возможно плохое поведение, если искомый аргумент равен 0.
* Итеративный способ. В этом способе выполниться только конечное число число итераций.
: <tex>\oplus</tex> Плюсом этого способа является фиксированная погрешность.

== Выбор границы отрезка для поиска==
Для начала найдем правую границу. Выберем произвольную положительную точку (например </tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.

== Псевдокод ==
<pre>
findLeft(c)
x = -1;
while f(x) > c
x = x * 2;
return x;
</pre>
<pre>
findRight(c)
x = 1;
while f(x) < c
x = x * 2;
return x;
</pre>
<pre>
binSearch(c)
left = findLeft(с);
right = findRight(с);
while left < right - eps //Здесь можно использовать другое условие выхода
mid = (left + right) / 2;
if f(mid) < c
left = mid;
else
right = mid;
return l;
</pre>
== Пример использования ==
Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x >= 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней - <tex>x</tex>.
== Источники ==
* [http://www.intuit.ru/department/algorithms/basicalgos/2/ Интернет университет, лекция сортировка и поиск]

Файл:Function.png

2012-06-12T17:15:10Z

Zakirzyanov:

Вещественный двоичный поиск

2012-06-12T15:40:34Z

Zakirzyanov:

'''Вещественный двоичный поиск''' - алгоритм поиска аргумента для заданного значения монотонной вещественной функции.

== Формулировка задачи ==
Пусть нам задана монотонная функция. Необходимо найти место, где значение функции становится меньше, чем какое-то заданное значение.
<br>
[[Файл:Functsia.GIF]]

== Решение задачи ==
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.

== Выбор границы ==
Для начала найдем правую границу. Выберем произвольную положительную точку (например 1). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку. Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.

== Способы закончить поиск ==
# Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
#* Алгоритм с большой точностью найдет значение аргумента
#* Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
# Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.
#* В отличии от предыдущего, не зацикливается при больших значениях функции.
#* Возможна большая погрешность, если функция будет очень медленно возрастать
# Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних по представлению значения в типе данных. Утверждается, что два числа - соседние, если середина их отрезка совпадает или с левой, или с правой границей.
#* Возможно плохое поведение, если искомый аргумент равен 0.
# Итеративный способ. В этом способе выполниться только конечное число число итераций.
#* Плюсом этого способа является фиксированная погрешность.

== Псевдокод ==
<pre>
findLeft(c)
x = -1;
while f(x) > c
x = x * 2;
return x;
</pre>
<pre>
findRight(c)
x = 1;
while f(x) < c
x = x * 2;
return x;
</pre>
<pre>
binSearch(c)
left = findLeft(с);
right = findRight(с);
while left < right - eps //Здесь можно использовать другое условие выхода
mid = (left + right) / 2;
if f(mid) < c
l = mid;
else
r = mid;
return l;
</pre>
== Источники ==
* [http://www.intuit.ru/department/algorithms/basicalgos/2/ Интернет университет, лекция сортировка и поиск]

Дискретная математика, алгоритмы и структуры данных

2012-06-12T11:14:45Z

Zakirzyanov: /* Амортизационный анализ */

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

Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].

= Первый семестр =

== Отношения ==
*[[Определение отношения]]
*[[Степень отношений]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Композиция отношений|Композиция отношений. Обратное отношение]]
*[[Транзитивное отношение]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Транзитивный остов]]
*[[Отношение порядка]]
*[[Отношение эквивалентности]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]

== Булевы функции ==
*[[Определение булевой функции]]
*[[Суперпозиции]]
*[[ДНФ]]
*[[КНФ]]
*[[Полином Жегалкина]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Сокращенная и минимальная ДНФ]]
*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]
*[[Представление функции класса DM с помощью медианы]]
*[[Пороговая функция]]

== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Реализация вычитания сумматором]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]

== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]

== Алгоритмы сжатия ==
*[[Алгоритм Хаффмана]]
*[[Алгоритм LZW]]
*[[Алгоритмы LZ77 и LZ78]]
*[[Преобразование Барроуза-Уиллера]]
*[[Обратное преобразование Барроуза-Уиллера]]
*[[Преобразование MTF]]
*[[Расстояние Хэмминга]]
*[[Избыточное кодирование, код Хэмминга]]
*[[Неравенство Крафта]]
*[[Неравенство Макмиллана]]

== Комбинаторика ==
*[[Комбинаторные объекты]]
*[[Лексикографический порядок]]
*[[Формула включения-исключения]]
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Получение номера по объекту]]
*[[Получение объекта по номеру]]
*[[Получение следующего объекта]]
*[[Коды Грея]]
*[[Коды Грея для перестановок]]
*[[Цепные коды]]
*[[Правильные скобочные последовательности]]
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
*[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
*[[Таблица инверсий]]
*[[Умножение перестановок, обратная перестановка, группа перестановок]]
*[[Теорема Кэли]]
*[[Матричное представление перестановок]]
*[[Задача о минимуме/максимуме скалярного произведения]]
*[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
*[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
*[[Производящая функция]]

== [[Динамическое программирование]] ==
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о порядке перемножения матриц]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
*[[Метод четырех русских для умножения матриц]]
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
*[[Задача о расстоянии Дамерау-Левенштейна]]
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]

== Теория вероятностей ==
*[[Вероятностное пространство, элементарный исход, событие]]
*[[Независимые события]]
*[[Условная вероятность]]
*[[Формула Байеса]]
*[[Формула полной вероятности]]
*[[Дискретная случайная величина]]
*[[Независимые случайные величины]]
*[[Математическое ожидание случайной величины]]
*[[Ковариация случайных величин]]
*[[Дисперсия случайной величины]]
*[[Энтропия случайного источника]]
*[[Симуляция одним распределением другого]]
*[[Арифметическое кодирование]]
*[[Задача о двух конвертах]]

== Марковские цепи ==

* [[Марковская цепь]]
* [[Теорема о поглощении]]
* [[Фундаментальная матрица]]
* [[Математическое ожидание времени поглощения]]
* [[Расчет вероятности поглощения в состоянии]]
* [[Эргодическая марковская цепь]]
* [[Регулярная марковская цепь]]

= Второй семестр =

== Амортизационный анализ ==
* [[Амортизационный анализ]]
* [[Саморасширяющийся массив]]
* [[Массив с увеличением/уменьшением размера]]
* [[Список]]
* [[Стек]]
* [[Очередь]]
* [[Персистентный стек]]
* [[Персистентный дек]]

== Приоритетные очереди ==

* [[Двоичная куча]]
* [[Биномиальная куча]]
* [[Фибоначчиева куча]]

== Система непересекающихся множеств ==
* [[СНМ (наивные реализации) | Наивные реализации]]
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]

== Поисковые структуры данных ==
* [[Упорядоченное множество]]
* [[Дерево поиска, наивная реализация]]
* [[АВЛ-дерево]]
* [[2-3 дерево]]
* [[B-дерево]]
* [[Красно-черное дерево]]
* [[Декартово дерево]]
* [[Splay-дерево]]
* [[Декартово дерево по неявному ключу]]
* [[Дерево ван Эмде Боаса]]
* [[Рандомизированное бинарное дерево поиска]]
* [[Список с пропусками]]

== Дерево отрезков ==

* [[Статистики на отрезках. Корневая эвристика]]
* [[Дерево отрезков. Построение]]
* [[Реализация запроса в дереве отрезков сверху]]
* [[Реализация запроса в дереве отрезков снизу]]
* [[Несогласованные поддеревья. Реализация массового обновления]]
* [[Многомерное дерево отрезков]]
* [[Сжатое многомерное дерево отрезков]]

== Дерево Фенвика ==
* [[Дерево Фенвика]]
* [[Встречное дерево Фенвика]]
* [[Дерево Фенвика для некоммутативных операций]]
* [[Многомерное дерево Фенвика]]

== Хеширование ==
* [[Хеш-таблица]]
* [[Хеширование]]
* [[Открытое и закрытое хеширование]]
* [[Поиск свободного места при закрытом хешировании]]
* [[Хеширование кукушки]]
* [[Двойное хеширование]]
* [[Перехеширование. Амортизационный анализ]]
* [[Фильтр Блума]]
* [[Универсальное семейство хеш-функций]]

== [[Сортировка]] ==
* [[Сортировка выбором]]
* [[Сортировка пузырьком]]
* [[Сортировка слиянием]]
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
* [[Сортировка вставками]]
* [[Сортировка подсчетом]]
* [[Сортировка подсчетом сложных объектов]]
* [[Сортировка кучей]]
* [[Цифровая сортировка]]
* [[Поиск k-ой порядковой статистики]]
* [[Поиск k-ой порядковой статистики за линейное время]]
* [[Теорема о нижней оценке для сортировки сравнениями]]
* [[Быстрая сортировка]]
* [[Карманная сортировка]]

== Сортирующие сети ==
* [[Сортирующие сети]]
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
* [[Сортирующие сети для квадратичных сортировок]]
* [[Сеть Бетчера]]

== Алгоритмы поиска ==
* [[Троичный поиск]]
* [[Поиск с помощью золотого сечения]]
* [[Интерполяционный поиск]]
* [[Вещественный двоичный поиск]]
* [[Целочисленный двоичный поиск]]

== Связь между структурами данных ==
* [[Связь между структурами данных]]

= Третий семестр =

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]
* [[Фундаментальные циклы графа]]
* [[Дерево, эквивалентные определения]]

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Теорема Менгера, альтернативное доказательство]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]

== Остовные деревья ==
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* Следствия теоремы Хватала:
** [[Теорема Дирака]]
* [[Теорема Оре]]
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Двойственный граф планарного графа]]

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
* [[Формула Зыкова]]
* [[Формула Уитни]]

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Флойда]]
* [[Алгоритм A*]]
* [[Алгоритм Джонсона]]

== Остовные деревья ==
* [[Лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]

== Задача о паросочетании ==
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Циркуляция потока]]
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Алгоритм масштабирования потока]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]

= Четвертый семестр =

== Основные определения. Простые комбинаторные свойства слов ==
* [[Основные определения, связанные со строками]]
* [[Период и бордер, их связь]]
* [[Слово Фибоначчи]]
* [[Слово Туэ-Морса]]

== Поиск подстроки в строке ==
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Z-функция]]
* [[Автомат для поиска образца в тексте]]
* [[Бор]]
* [[Алгоритм Ахо-Корасик]]

== Суффиксное дерево ==
* [[Суффиксный бор]]
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]

=== Суффиксный массив ===
* [[Суффиксный массив]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
* [[Цифровая сортировка]]
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
* [[Алгоритм Касаи и др.]]
* [[Алгоритм Карккайнена-Сандерса]]
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]

== Задача о наименьшем общем предке ==
* [[Метод двоичного подъема]]
* [[Сведение задачи LCA к задаче RMQ]]
* [[Решение RMQ с помощью разреженной таблицы]]
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четверых русских)
* [[Сведение задачи RMQ к задаче LCA]]

== Матроиды ==
* [[Определение матроида]]
* [[Примеры матроидов]]
* [[Прямая сумма матроидов]]
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
* [[Жадный алгоритм поиска базы минимального веса]]
* [[Теорема о базах]]
* [[Аксиоматизация матроида базами]]
* [[Теорема о циклах]]
* [[Аксиоматизация матроида циклами]]
* [[Ранговая функция, полумодулярность]]
* [[Двойственный матроид]]
* [[Оператор замыкания для матроидов]]
* [[Пересечение матроидов, определение, примеры]]
* [[Лемма о паросочетании в графе замен]]
* [[Лемма о единственном паросочетании в графе замен]]
* [[Граф замен для двух матроидов]]
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
* [[Алгоритм построения базы в пересечении матроидов]]
* [[Теорема Эдмондса-Лоулера]]
* [[Объединение матроидов, проверка множества на независимость]]
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
* [[Алгоритм построения базы в объединении матроидов]]
==Теория расписаний==
* [[Классификация задач]]
* [[Методы решения задач теории расписаний]]
* [[Правило Лаулера]]
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]

Файл:Heap6.png

2012-06-10T16:38:24Z

Zakirzyanov: загружена новая версия «Файл:Heap6.png»

Файл:Heap5.png

2012-06-10T16:37:50Z

Zakirzyanov: загружена новая версия «Файл:Heap5.png»

Файл:Heap4.png

2012-06-10T16:35:23Z

Zakirzyanov: загружена новая версия «Файл:Heap4.png»

Файл:Heap3.png

2012-06-10T16:34:44Z

Zakirzyanov: загружена новая версия «Файл:Heap3.png»

Файл:Heap3.png

2012-06-10T16:34:22Z

Zakirzyanov: загружена новая версия «Файл:Heap3.png»

Файл:Heap2.png

2012-06-10T16:33:37Z

Zakirzyanov: загружена новая версия «Файл:Heap2.png»

Файл:Heap1.png

2012-06-10T16:32:21Z

Zakirzyanov: загружена новая версия «Файл:Heap1.png»

Сортировка кучей

2012-06-10T13:34:35Z

Zakirzyanov:

'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. '''Heapsort''') {{---}} алгоритм сортировки, использующий структуру данных [[Двоичная куча|двоичная куча]]. Это неустойчивый алгоритм сортировки с временем работы <tex>O(n\log{n})</tex> , где <tex>n</tex> {{---}} количество элементов для сортировки, и использующий <tex>O(1)</tex> дополнительной памяти.

== Алгоритм ==
Необходимо отсортировать массив <tex>A</tex>, размером <tex>n</tex>. Построим на базе этого массива за <tex>O(n)</tex> невозрастающую кучу. Так как по свойству кучи максимальный элемент находится в корне, то, поменявшись его местами с <tex>A[n - 1]</tex>, он встанет на свое место. Далее вызовем процедуру <tex>sift\_down(0)</tex>, предварительно уменьшив <tex>heap\_size</tex> на <tex>1</tex>. Она за <tex>O(\log{n})</tex> просеет <tex>A[0]</tex> на нужное место и сформирует новую кучу (так как мы уменьшили ее размер, то куча располагается с <tex>A[0]</tex> по <tex>A[n - 2]</tex>, а элемент <tex>A[n-1]</tex> находится на своем месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с <tex>A[n - 1]</tex>, а с <tex>A[n-2]</tex>. Делая аналогичные действия, пока <tex>heap\_size</tex> не станет равен <tex>1</tex>, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.

== Реализация ==
<tex>A</tex> {{---}} массив, который необходимо отсортировать; <tex>n</tex> {{---}} количество элементов в нем; <tex>build\_heap(A)</tex> - процедура, которая строит из передаваемого массива невозрастающую кучу в этом же массиве; <tex>sift\_down(A, i, len)</tex> {{---}} процедура, которая просеивает вниз элемент <tex>A[i]</tex> в куче из <tex>len</tex> элементов, находящихся в начале массива <tex>A</tex>.
<pre>
heapsort(A)
build_heap(A);
heap_size = A.size;
for i = 0 to n - 2
swap(A[0], A[n - 1 - i]);
heap_size--;
sift_down(A, 0, heap_size);
</pre>

== Сложность ==
Операция <tex>sift\_down</tex> работает за <tex>O(\log{n})</tex>. Всего цикл выполняется <tex>(n - 1)</tex> раз. Таким образом сложность сортировки кучей является <tex>O(n\log{n})</tex>.

== Пример ==

{|align="right"
|-valign="top"
|[[Файл:heap1.png|155px|thumb|Строим кучу]]
|[[Файл:heap2.png|155px|thumb|Первый проход]]
|[[Файл:heap3.png|155px|thumb|Строим новую кучу]]
|-
|[[Файл:heap4.png|155px|thumb|Второй проход]]
|[[Файл:heap5.png|155px|thumb|Третий проход]]
|[[Файл:heap6.png|155px|thumb|Четвертый проход]]
|}

Пусть дана последовательность из <tex>5</tex> элементов <tex>3, 2, 4, 1, 5</tex>.

{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Массив
!style="background-color:#EEE"| Описание шага
|-
|style="background-color:#FFF;padding:2px 10px"| 5 3 4 1 2
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из исходного массива
|-
|colspan=3|''Первый проход''
|-
|style="background-color:#FFF;padding:2px 10px"| '''2''' 3 4 1 '''5'''
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и последний элементы
|-
|style="background-color:#FFF;padding:2px 10px"| '''4''' 3 2 1 5
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых четырех элементов
|-
|colspan=3|''Второй проход''
|-
|style="background-color:#FFF;padding:2px 10px"| '''1''' 3 2 '''4''' 5
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и четвертый элементы
|-
|style="background-color:#FFF;padding:2px 10px"| '''3''' 1 2 4 5
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых трех элементов
|-
|colspan=3|''Третий проход''
|-
|style="background-color:#FFF;padding:2px 10px"| '''2''' 1 '''3''' 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и третий элементы
|-
|style="background-color:#FFF;padding:2px 10px"| '''2''' 1 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из двух элементов
|-
|colspan=3|''Четвертый проход''
|-
|style="background-color:#FFF;padding:2px 10px"| '''1''' '''2''' 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и второй элементы
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован
|}

== Ссылки ==
*[http://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D1%80%D0%B0%D0%BC%D0%B8%D0%B4%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 Пирамидальная сортировка - Википедия]
*[http://en.wikipedia.org/wiki/Heapsort Heapsort - Wikipedia]

== Литература ==
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4

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

Сортировка кучей

2012-06-10T13:31:40Z

Zakirzyanov:

'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. '''Heapsort''') {{---}} алгоритм сортировки, использующий структуру данных [[Двоичная куча|двоичная куча]]. Это неустойчивый алгоритм сортировки с временем работы <tex>O(n\log{n})</tex> , где <tex>n</tex> {{---}} количество элементов для сортировки, и использующий <tex>O(1)</tex> дополнительной памяти.

== Алгоритм ==
Необходимо отсортировать массив <tex>A</tex>, размером <tex>n</tex>. Построим на базе этого массива за <tex>O(n)</tex> невозрастающую кучу. Так как по свойству кучи максимальный элемент находится в корне, то, поменявшись его местами с <tex>A[n - 1]</tex>, он встанет на свое место. Далее вызовем процедуру <tex>sift\_down(0)</tex>, предварительно уменьшив <tex>heap\_size</tex> на <tex>1</tex>. Она за <tex>O(\log{n})</tex> просеет <tex>A[0]</tex> на нужное место и сформирует новую кучу (так как мы уменьшили ее размер, то куча располагается с <tex>A[0]</tex> по <tex>A[n - 2]</tex>, а элемент <tex>A[n-1]</tex> находится на своем месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с <tex>A[n - 1]</tex>, а с <tex>A[n-2]</tex>. Делая аналогичные действия, пока <tex>heap\_size</tex> не станет равен <tex>1</tex>, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.

== Реализация ==
<tex>A</tex> {{---}} массив, который необходимо отсортировать; <tex>n</tex> {{---}} количество элементов в нем; <tex>build\_heap(A)</tex> - процедура, которая строит из передаваемого массива невозрастающую кучу в этом же массиве; <tex>sift\_down(A, i, len)</tex> {{---}} процедура, которая просеивает вниз элемент <tex>A[i]</tex> в куче из <tex>len</tex> элементов, находящихся в начале массива <tex>A</tex>.
<pre>
heapsort(A)
build_heap(A);
heap_size = A.size;
for i = 0 to n - 2
swap(A[0], A[n - 1 - i]);
heap_size--;
sift_down(A, 0, heap_size);
</pre>

== Сложность ==
Операция <tex>sift\_down</tex> работает за <tex>O(\log{n})</tex>. Всего цикл выполняется <tex>(n - 1)</tex> раз. Таким образом сложность сортировки кучей является <tex>O(n\log{n})</tex>.

== Пример ==

{|align="right"
|-valign="top"
|[[Файл:heap1.png|180px|thumb|Строим кучу]]
|[[Файл:heap2.png|180px|thumb|Первый проход]]
|[[Файл:heap3.png|180px|thumb|Строим новую кучу]]
|-
|[[Файл:heap4.png|180px|thumb|Второй проход]]
|[[Файл:heap5.png|180px|thumb|Третий проход]]
|[[Файл:heap6.png|180px|thumb|Четвертый проход]]
|}

Пусть дана последовательность из <tex>5</tex> элементов <tex>3, 2, 4, 1, 5</tex>.

{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Массив
!style="background-color:#EEE"| Описание шага
|-
|style="background-color:#FFF;padding:2px 10px"| 5 3 4 1 2
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из исходного массива
|-
|colspan=3|''Первый проход''
|-
|style="background-color:#FFF;padding:2px 10px"| '''2''' 3 4 1 '''5'''
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и последний элементы
|-
|style="background-color:#FFF;padding:2px 10px"| '''4''' 3 2 1 5
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых четырех элементов
|-
|colspan=3|''Второй проход''
|-
|style="background-color:#FFF;padding:2px 10px"| '''1''' 3 2 '''4''' 5
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и четвертый элементы
|-
|style="background-color:#FFF;padding:2px 10px"| '''3''' 1 2 4 5
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых трех элементов
|-
|colspan=3|''Третий проход''
|-
|style="background-color:#FFF;padding:2px 10px"| '''2''' 1 '''3''' 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и третий элементы
|-
|style="background-color:#FFF;padding:2px 10px"| '''2''' 1 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из двух элементов
|-
|colspan=3|''Четвертый проход''
|-
|style="background-color:#FFF;padding:2px 10px"| '''1''' '''2''' 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и второй элементы
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован
|}

== Ссылки ==
*[http://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D1%80%D0%B0%D0%BC%D0%B8%D0%B4%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 Пирамидальная сортировка - Википедия]
*[http://en.wikipedia.org/wiki/Heapsort Heapsort - Wikipedia]

== Литература ==
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4

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

Файл:Heap6.png

2012-06-10T13:30:08Z

Zakirzyanov:

Файл:Heap5.png

2012-06-10T13:28:51Z

Zakirzyanov:

Файл:Heap4.png

2012-06-10T13:27:03Z

Zakirzyanov:

Файл:Heap3.png

2012-06-10T13:25:38Z

Zakirzyanov:

Файл:Heap2.png

2012-06-10T13:23:15Z

Zakirzyanov:

Файл:Heap1.png

2012-06-10T13:20:29Z

Zakirzyanov:

Список

2012-06-10T13:02:34Z

Zakirzyanov:

'''Связный список''' - структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.

==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

<pre>
insert(newHead)
newHead.next = head;
head = newHead;
</pre>
[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
<pre>
insertAfter(thisElement, thatElement)
thatElement.next = thisElement.next;
thisElement.next = thatElement;
</pre>
[[Файл:insertAfter.png|center|490px]]
===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
<pre>
Search(value)
node = head;
while node != NULL and value != node.value
node = node.next;
return node;
</pre>
===Удаление===
Для того, чтобы удалить голову списка - переназначим указатель на голову на второй элемент списка, а голову удалим.
<pre>
removeHead()
if head != NULL
tmp = head;
head = head.next;
delete tmp;
</pre>
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
<pre>
removeAfter(thisElement)
if thisElement.next != NULL
tmp = thisElement.next;
thisElement.next = thisElement.next.next;
delete tmp;
</pre>
[[Файл:removeAfter.png|center|550px]]
==См.также==
[[Массив с увеличением/уменьшением размера]]
==Ссылки ==
* [http://en.wikipedia.org/wiki/Linked_list Linked list - Wikipedia]

* [http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) Список - Википедия]

==Литература ==
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
* Д. Кнут: Искусство программирования том 1 глава 2.2

Список

2012-06-10T10:01:30Z

Zakirzyanov:

'''Связный список''' - структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:twiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.

==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

<pre>
insert(newHead)
newHead.next = head;
head = newHead;
</pre>
[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
<pre>
insertAfter(thisElement, thatElement)
thatElement.next = thisElement.next;
thisElement.next = thatElement;
</pre>
[[Файл:insertAfter.png|center|490px]]
===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
<pre>
Search(value)
node = head;
while node != NULL and value != node.value
node = node.next;
return node;
</pre>
===Удаление===
Для того, чтобы удалить голову списка - переназначим указатель на голову на второй элемент списка, а голову удалим.
<pre>
removeHead()//удаление головы
if head != NULL
tmp = head;
head = head.next;
delete tmp;
</pre>
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
<pre>
removeAfter(thisElement)
if thisElement.next != NULL
tmp = thisElement.next;
thisElement.next = thisElement.next.next;
delete tmp;
</pre>
[[Файл:removeAfter.png|center|550px]]
==См.также==
[[Массив с увеличением/уменьшением размера]]
==Ссылки ==
* [http://en.wikipedia.org/wiki/Linked_list Linked list - Wikipedia]

* [http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) Список - Википедия]

==Литература ==
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
* Д. Кнут: Искусство программирования том 1 глава 2.2

Файл:TwiceSpisok.png

2012-06-10T09:58:14Z

Zakirzyanov:

Файл:RemoveAfter.png

2012-06-10T09:44:33Z

Zakirzyanov:

Файл:RemoveHead.png

2012-06-10T09:38:09Z

Zakirzyanov:

Файл:InsertAfter.png

2012-06-10T09:27:52Z

Zakirzyanov:

Список

2012-06-10T00:27:54Z

Zakirzyanov:

'''Связный список''' - структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:simpleSpisok.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:Doubly linked list.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.

==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:circleSpisok.png|center|450px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

<pre>
insert(newHead)
newHead.next = head;
head = newHead;
</pre>
[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
<pre>
insertAfter(thisElement, thatElement)
thatElement.next = thisElement.next;
thisElement.next = thatElement;
</pre>
===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
<pre>
Search(value)
node = head;
while node != NULL and value != node.value
node = node.next;
return node;
</pre>
===Удаление===
Для того, чтобы удалить голову списка - переназначим указатель на голову на второй элемент списка, а голову удалим.
<pre>
removeHead()//удаление головы
if head != NULL
tmp = head;
head = head.next;
delete tmp;
</pre>
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
<pre>
removeAfter(thisElement)
if thisElement.next != NULL
tmp = thisElement.next;
thisElement.next = thisElement.next.next;
delete tmp;
</pre>
==См.также==
[[Массив с увеличением/уменьшением размера]]
==Ссылки ==
[http://en.wikipedia.org/wiki/Linked_list Linked list]

==Литература ==
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
* Д. Кнут: Искусство программирования том 1 глава 2.2

Файл:CircleSpisok.png

2012-06-10T00:26:45Z

Zakirzyanov:

Файл:SimpleSpisok.png

2012-06-10T00:22:34Z

Zakirzyanov:

Файл:InsertHead.png

2012-06-10T00:16:55Z

Zakirzyanov:

Декартово дерево по неявному ключу

2012-06-10T00:02:12Z

Zakirzyanov:

==Основная идея==
Возьмем структуру данных [[Саморасширяющийся массив|вектор]]. В её стандартной реализации мы умеем добавлять элемент в конец вектора, узнавать значение элемента, стоящего на определенной позиции, изменять элемент по номеру и удалять последний элемент. Предположим, что нам необходима структура данных с вышеуказанными свойствами, а также с операциями: добавить элемент в любое место (с соответствующим изменением нумерации элементов) и удалить любой элемент (также с соответствующим изменением нумерации). Такая структура существует и называется ''декартово дерево по неявному ключу''.
===Ключ X===
Как известно, [[декартово дерево]] {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. При реализации же декартова дерева по неявному ключу модифицируем эту структуру. А именно, оставим в нем только приоритет <tex>Y</tex>, а вместо ключа <tex>X</tex> будем использовать следующую величину: '''количество элементов в нашей структуре, находящихся левее нашего элемента'''. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.

Заметим, что при этом сохранится структура [[Дерево_поиска,_наивная_реализация|двоичного дерева поиска]] по этому ключу (то есть модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} количество элементов в дереве.

===Вспомогательная величина С===
Решается эта проблема довольно просто. Основная идея заключается в том, что такой ключ <tex>X</tex> сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину <tex>C</tex>: '''количество вершин в поддереве нашей вершины''' (в поддерево включается и сама вершина). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути до некой вершины просуммировать все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ <tex>X</tex>.

[[Файл:DDpoNK.png|Пример описанного дерева с демонстрацией определения ключа <tex>X</tex>]]

==Операции, поддерживающие структуру декартова дерева==
Структура обычного декартова дерева поддерживается с помощью двух операций: <tex>split</tex> {{---}} разбиение одного декартова дерева на два таких, что в одном ключ <tex>X</tex> меньше, чем заданное значение, а в другом {{---}} больше, и <tex>merge</tex> {{---}} слияние двух деревьев, в одном из которых все ключи <tex>X</tex> меньше, чем во втором. С учетом отличий декартова дерева по неявному ключу от обычного, операции теперь будут описываться так: <tex>split(root, t)</tex> {{---}} разбиение дерева на два так, что в левом окажется ровно <tex>t</tex> вершин, и <tex>merge(root1, root2)</tex> {{---}} слияние двух любых деревьев, соответственно.

===Split===
Пусть процедура <tex>Split</tex> запущена в корне дерева с требованием отрезать от дерева <tex>t</tex> вершин. Также известно, что в левом поддереве вершины находится <tex>l</tex> вершин, а в правом <tex>r</tex>. Рассмотрим все возможные случаи:
* <tex>l = t</tex>. В этом случае процедура <tex>Split</tex> должна просто пометить, что у корня больше нет левого сына, и вернуть его бывшего левого сына в качестве левой части ответа, а сам корень {{---}} в качестве правой.
* Случай (<tex>t = l + 1</tex>) рассматривается аналогично предыдущему.
* <tex>t < l</tex>. В этом случае нужно рекурсивно запустить процедуру <tex>Split</tex> от левого сына с тем же параметром <tex>t</tex>, и левая часть сына станет левой частью ответа нашей процедуры, а правая часть сына станет левым сыном корня, после чего корень станет правой частью ответа.
* Случай <tex>t > l + 1</tex> рассматривается аналогично предыдущему, с той лишь разницей, что от правого сына отрезается <tex>t - l - 1</tex> вершин.

===Merge===
Посмотрим любую из [[Декартово дерево#Операция merge|реализаций]] процедуры <tex>Merge</tex>. Заметим, что в ней программа ни разу не обращается к ключу <tex>X</tex>. Поэтому реализация процедуры <tex>Merge</tex> для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.

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

==Применение описанного дерева==
Таким образом, описана структура, от которой можно отрезать слева часть произвольной длины и слить две любые части в одну в нужном порядке. Теперь мы имеем возможность:
* вставить элемент в любое место (отрежем нужное количество элементов слева, сольем левое дерево с деревом из одного добавленного элемента и результат {{---}} с правым деревом);
* переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке);
* совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка.
* сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и нечетных на отрезке.
* с помощью декартова дерева по неявному ключу можно реализовать такую структуру как [http://en.wikipedia.org/wiki/Rope_(computer_science) - Rope]

==Ссылки==
* [http://habrahabr.ru/post/102364/ Habrahabr - Декартово дерево по неявному ключу]
* [http://e-maxx.ru/algo/treap#7 E-maxx - Неявные декартовы деревья]

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

Файл:DDpoNK.png

2012-06-09T23:59:00Z

Zakirzyanov: загружена новая версия «Файл:DDpoNK.png»

Список

2012-06-09T23:56:05Z

Zakirzyanov:

'''Связный список''' - структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].

__TOC__
==Односвязный список ==
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:Single linked list-1-.png|center|400px]]
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:Doubly linked list.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.

==Циклический список==
Первый элемент является следующим для последнего элемента списка.
[[Файл:Circurlar linked list.png (872×241).png|center|400px]]
==Операции на списке==
Рассмотрим базовые операции на примере односвязного списка.
===Вставка===
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.
<pre>
insert(newHead)
newHead.next = head;
head = newHead;
</pre>
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
<pre>
insertAfter(thisElement, thatElement)
thatElement.next = thisElement.next;
thisElement.next = thatElement;
</pre>
===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
<pre>
Search(value)
node = head;
while node != NULL and value != node.value
node = node.next;
return node;
</pre>
===Удаление===
Для того, чтобы удалить голову списка - переназначим указатель на голову на второй элемент списка, а голову удалим.
<pre>
removeHead()//удаление головы
if head != NULL
tmp = head;
head = head.next;
delete tmp;
</pre>
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
<pre>
removeAfter(thisElement)
if thisElement.next != NULL
tmp = thisElement.next;
thisElement.next = thisElement.next.next;
delete tmp;
</pre>
==См.также==
[[Массив с увеличением/уменьшением размера]]
==Ссылки ==
[http://en.wikipedia.org/wiki/Linked_list Linked list]

==Литература ==
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
* Д. Кнут: Искусство программирования том 1 глава 2.2

Список

2012-06-08T17:35:29Z

Zakirzyanov:

Декартово дерево по неявному ключу

2012-06-07T18:03:01Z

Zakirzyanov:

==Основная идея==
Возьмем структуру данных [[Саморасширяющийся массив|вектор]]. В её стандартной реализации мы умеем добавлять элемент в конец вектора, узнавать значение элемента, стоящего на определенной позиции, изменять элемент по номеру и удалять последний элемент. Предположим, что нам необходима структура данных с вышеуказанными свойствами, а также с операциями: добавить элемент в любое место (с соответствующим изменением нумерации элементов) и удалить любой элемент (также с соответствующим изменением нумерации). Такая структура существует и называется ''декартово дерево по неявному ключу''.
===Ключ X===
Как известно, [[декартово дерево]] {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. При реализации же декартова дерева по неявному ключу модифицируем эту структуру. А именно, оставим в нем только приоритет <tex>Y</tex>, а вместо ключа <tex>X</tex> будем использовать следующую величину: '''количество элементов в нашей структуре, находящихся левее нашего элемента'''. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.

Заметим, что при этом сохранится структура [[Дерево_поиска,_наивная_реализация|двоичного дерева поиска]] по этому ключу (то есть модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} количество элементов в дереве.

===Вспомогательная величина С===
Решается эта проблема довольно просто. Основная идея заключается в том, что такой ключ <tex>X</tex> сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину <tex>C</tex>: '''количество вершин в поддереве нашей вершины''' (в поддерево включается и сама вершина). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути до некой вершины просуммировать все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ <tex>X</tex>.

[[Файл:DDpoNK.png|Пример описанного дерева с демонстрацией определения ключа <tex>X</tex>]]

==Операции, поддерживающие структуру декартова дерева==
Структура обычного декартова дерева поддерживается с помощью двух операций: <tex>split</tex> {{---}} разбиение одного декартова дерева на два таких, что в одном ключ <tex>X</tex> меньше, чем заданное значение, а в другом {{---}} больше, и <tex>merge</tex> {{---}} слияние двух деревьев, в одном из которых все ключи <tex>X</tex> меньше, чем во втором. С учетом отличий декартова дерева по неявному ключу от обычного, операции теперь будут описываться так: <tex>split(root, t)</tex> {{---}} разбиение дерева на два так, что в левом окажется ровно <tex>t</tex> вершин, и <tex>merge(root1, root2)</tex> {{---}} слияние двух любых деревьев, соответственно.

===Split===
Пусть процедура <tex>Split</tex> запущена в корне дерева с требованием отрезать от дерева <tex>t</tex> вершин. Также известно, что в левом поддереве вершины находится <tex>l</tex> вершин, а в правом <tex>r</tex>. Рассмотрим все возможные случаи:
* <tex>l = t</tex>. В этом случае процедура <tex>Split</tex> должна просто пометить, что у корня больше нет левого сына, и вернуть его бывшего левого сына в качестве левой части ответа, а сам корень {{---}} в качестве правой.
* Случай (<tex>t = l + 1</tex>) рассматривается аналогично предыдущему.
* <tex>t < l</tex>. В этом случае нужно рекурсивно запустить процедуру <tex>Split</tex> от левого сына с тем же параметром <tex>t</tex>, и левая часть сына станет левой частью ответа нашей процедуры, а правая часть сына станет левым сыном корня, после чего корень станет правой частью ответа.
* Случай <tex>t > l + 1</tex> рассматривается аналогично предыдущему, с той лишь разницей, что от правого сына отрезается <tex>t - l - 1</tex> вершин.

===Merge===
Посмотрим любую из [[Декартово дерево#Операция merge|реализаций]] процедуры <tex>Merge</tex>. Заметим, что в ней программа ни разу не обращается к ключу <tex>X</tex>. Поэтому реализация процедуры <tex>Merge</tex> для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.

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

==Применение описанного дерева==
Таким образом, описана структура, от которой можно отрезать слева часть произвольной длины и слить две любые части в одну в нужном порядке. Теперь мы имеем возможность:
* вставить элемент в любое место (отрежем нужное количество элементов слева, сольем левое дерево с деревом из одного добавленного элемента и результат {{---}} с правым деревом);
* переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке);
* совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка.
* сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и нечетных на отрезке.

==Ссылки==
* [http://habrahabr.ru/post/102364/ Habrahabr - Декартово дерево по неявному ключу]
* [http://e-maxx.ru/algo/treap#7 E-maxx - Неявные декартовы деревья]

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

Файл:DDpoNK.png

2012-06-07T17:49:48Z

Zakirzyanov: загружена новая версия «Файл:DDpoNK.png»

Файл:DDpoNK.png

2012-06-07T17:44:44Z

Zakirzyanov:

Сортировка кучей

2012-06-03T20:51:50Z

Zakirzyanov:

'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. '''Heapsort''') {{---}} алгоритм сортировки, использующий структуру данных [[Двоичная куча|двоичная куча]]. Это нестабильный алгоритм сортировки с временем работы <tex>O(n\log{n})</tex> , где <tex>n</tex> {{---}} количество элементов для сортировки, и использующий <tex>O(1)</tex> дополнительной памяти.

== Алгоритм ==
Необходимо отсортировать массив <tex>A</tex>, размером <tex>n</tex>. Построим на базе этого массива за <tex>O(n)</tex> невозрастающую кучу. Так как по свойству кучи максимальный элемент находится в корне, то, поменявшись его местами с <tex>A[n - 1]</tex>, он встанет на свое место. Далее вызовем процедуру '''sift_down(0)''', предварительно уменьшив <tex>heap\_size</tex> на <tex>1</tex>. Она за <tex>O(\log{n})</tex> просеет <tex>A[0]</tex> на нужное место и сформирует новую кучу (так как мы уменьшили ее размер, то куча располагается с <tex>A[0]</tex> по <tex>A[n - 2]</tex>, а элемент <tex>A[n-1]</tex> находится на своем месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с <tex>A[n - 1]</tex>, а с <tex>A[n-2]</tex>. Делая аналогичные действия, пока <tex>heap\_size</tex> не станет равен <tex>1</tex>, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.

== Реализация ==
<tex>A</tex> {{---}} массив, который необходимо отсортировать; <tex>n</tex> {{---}} количество элементов в нем; '''build_heap(A)''' - процедура, которая строит из передаваемого массива невозрастающую кучу в этом же массиве; '''sift_down(A, i, len)''' {{---}} процедура, которая просеивает вниз элемент <tex>A[i]</tex> в куче из <tex>len</tex> элементов, находящихся в начале массива <tex>A</tex>.
<pre>
heapsort(A)
build_heap(A);
heap_size = A.size;
for i = 0 to n - 2
swap(A[0], A[n - 1 - i]);
heap_size--;
sift_down(A, 0, heap_size);
</pre>

== Сложность ==
Операция '''sift_down''' работает за <tex>O(\log{n})</tex>. Всего цикл выполняется <tex>(n - 1)</tex> раз. Таким образом сложность сортировки кучей является <tex>O(n\log{n})</tex>.

== Пример ==

{|align="right"
|-valign="top"
|[[Файл:Документ1.png|120px|thumb|Строим кучу]]
|[[Файл:Документ2.png|120px|thumb|Первый проход]]
|[[Файл:Документ3.png|120px|thumb|Строим новую кучу]]
|-
|[[Файл:Документ4.png|120px|thumb|Второй проход]]
|[[Файл:Документ5.png|120px|thumb|Третий проход]]
|[[Файл:Документ6.png|120px|thumb|Четвертый проход]]
|}

Пусть дана последовательность из <tex>5</tex> элементов <tex>3, 2, 4, 1, 5</tex>.

{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Массив
!style="background-color:#EEE"| Описание шага
|-
|style="background-color:#FFF;padding:2px 10px"| 5 3 4 1 2
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из исходного массива
|-
|colspan=3|''Первый проход''
|-
|style="background-color:#FFF;padding:2px 10px"| '''2''' 3 4 1 '''5'''
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и последний элементы
|-
|style="background-color:#FFF;padding:2px 10px"| '''4''' 3 2 1 5
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых четырех элементов
|-
|colspan=3|''Второй проход''
|-
|style="background-color:#FFF;padding:2px 10px"| '''1''' 3 2 '''4''' 5
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и четвертый элементы
|-
|style="background-color:#FFF;padding:2px 10px"| '''3''' 1 2 4 5
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых трех элементов
|-
|colspan=3|''Третий проход''
|-
|style="background-color:#FFF;padding:2px 10px"| '''2''' 1 '''3''' 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и третий элементы
|-
|style="background-color:#FFF;padding:2px 10px"| '''2''' 1 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из двух элементов
|-
|colspan=3|''Четвертый проход''
|-
|style="background-color:#FFF;padding:2px 10px"| '''1''' '''2''' 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и второй элементы
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован
|}

== Ссылки ==
*[http://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D1%80%D0%B0%D0%BC%D0%B8%D0%B4%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 Пирамидальная сортировка - Википедия]
*[http://en.wikipedia.org/wiki/Heapsort Heapsort - Wikipedia]

== Литература ==
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4

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

Файл:Документ6.png

2012-06-03T20:36:33Z

Zakirzyanov:

Файл:Документ5.png

2012-06-03T20:33:53Z

Zakirzyanov:

Файл:Документ4.png

2012-06-03T20:27:07Z

Zakirzyanov:

Файл:Документ3.png

2012-06-03T20:25:06Z

Zakirzyanov:

Файл:Документ2.png

2012-06-03T19:59:07Z

Zakirzyanov:

Файл:Документ1.png

2012-06-03T19:56:49Z

Zakirzyanov: