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

Конкурс для более удачного URL сайта вики-конспектов

2012-02-02T13:13:17Z

ЗабылПароль: Поправил очепятку

Хочется избавиться от имени mediawiki, потому что это название вики-движка .

Предлагайте варианты URL для вики-конспектов на этой странице.
Подписывайтесь, бонусы возможны.

== Варианты ==

{| class="wikitable"
!Вариант!!Автор (<nowiki>~~~</nowiki>)
|-
|knowledge||[[Участник:Kirelagin|Кирилл Елагин]]
|-
|wikiconsp||[[Участник:Igor buzhinsky|Игорь Бужинский]]
|-
|wk ''(что бы это ни значило)''||[[Участник:Kirelagin|Кирилл Елагин]]
|-
|lectures||[[Участник:Igor buzhinsky|Игорь Бужинский]]
|-
|theory||[[Участник:Shevchen|Дмитрий Шевченко]]
|-
|outlines||[[Участник:Shevchen|Дмитрий Шевченко]]
|-
|wikikt||[[Участник:Mamoshkin.Arseny|Арсений Мамошкин]]
|-
|lecturenotes||[[Участник:Dgerasimov|Дмитрий Герасимов]]
|-
|ktlectures||[[Участник:SkudarnovYaroslav|Ярослав Скударнов]]
|-
|wiki||[[Участник:Андрей Шулаев|Андрей Шулаев]]
|-
|pediwikia||[[Участник:Pashkal|Павел Кротков]]
|-
|wikisynopses||[[Участник:Rybak|Андрей Рыбак]]
|-
|ctpedia||[[Участник:Borisov|Сергей Борисов]]
|-
|ctd||[[Участник:Borisov|Сергей Борисов]]
|-
|wikimath||[[Участник:Yurik|Александров Юрий]]
|-
|itmopedia||Марат Валиахметов
|-
|w||[[Участник:Tsar|Иоанн Волков]]
|-
|notes||[[Участник:Grechko|Гречко Владислав]]
|-
|medialibrary||[[Участник:Андреев Кирилл|Андреев Кирилл]]
|-
|algowiki||[[Участник:ЗабылПароль|Иванов Денис]]
|-
|wiki.ifmo.ru||[[Участник:Proshev|Прошев Семен]]
|-
|db.algowiki.ru||[[Участник:GeraltFromRivia|Завадский Дмитрий]]
|-
|wikicat ||[[Участник:Русин Никита|Русин Никита]]
|-
|algostore ||[[Участник:Русин Никита|Русин Никита]]
|-
|store ||[[Участник:Русин Никита|Русин Никита]]
|}
+1 за педивикию :D

Конкурс для более удачного URL сайта вики-конспектов

2012-01-24T00:27:04Z

ЗабылПароль: /* Варианты */

Хочется избавиться от имени mediawiki, потому что это название вики-движка .

Предлагайте варианты URL для вики-конспектов на этой странице.
Подписывайтесь, бонусы возможны.

== Варианты ==

{| class="wikitable"
!Вариант!!Автор (<nowiki>~~~</nowiki>)
|-
|knowledge||[[Участник:Kirelagin|Кирилл Елагин]]
|-
|wikiconsp||[[Участник:Igor buzhinsky|Игорь Бужинский]]
|-
|wk ''(что бы это ни значило)''||[[Участник:Kirelagin|Кирилл Елагин]]
|-
|lectures||[[Участник:Igor buzhinsky|Игорь Бужинский]]
|-
|theory||[[Участник:Shevchen|Дмитрий Шевченко]]
|-
|outlines||[[Участник:Shevchen|Дмитрий Шевченко]]
|-
|wikikt||[[Участник:Mamoshkin.Arseny|Арсений Мамошкин]]
|-
|lecturenotes||[[Участник:Dgerasimov|Дмитрий Герасимов]]
|-
|ktlectures||[[Участник:SkudarnovYaroslav|Ярослав Скударнов]]
|-
|wiki||[[Участник:Андрей Шулаев|Андрей Шулаев]]
|-
|pediwikia||[[Участник:Pashkal|Павел Кротков]]
|-
|wikisynopses||[[Участник:Rybak|Андрей Рыбак]]
|-
|ctpedia||[[Участник:Borisov|Сергей Борисов]]
|-
|wikimath||[[Участник:Yurik|Александров Юрий]]
|-
|itmopedia||Марат Валиахметов
|-
|w||[[Участник:Tsar|Иоанн Волков]]
|-
|notes||[[Участник:Grechko|Гречко Владислав]]
|-
|medialibrary||[[Участник:Андреев Кирилл|Андреев Кирилл]]
|-
|algowki||[[Участник:ЗабылПароль|Иванов Денис]]
|}
+1 за педивикию :D

Алгоритм A*

2011-12-31T07:13:47Z

ЗабылПароль:

Алгоритм '''А*'''("A star", "А звёздочка") {{---}} алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
==Описание==
В процессе работы алгоритма для вершин рассчитывается функция <tex>f(v) = g(v) + h(v)</tex>, где
*<tex>g(v)</tex> {{---}} наименьшая стоимость пути в <tex>v</tex> из стартовой вершины,
*<tex>h(v)</tex> {{---}} эвристическое приближение стоимости пути от <tex>v</tex> до конечной цели. <tex>h(v)</tex> должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели.
Чем меньше , тем раньше вершина будет открыта и исследована алгоритмом. Таким образом открытые алгоритмом вершины хранятся в очереди с приоритетом по значению <tex>f(v)</tex>. А* действует подобно [[Алгоритм Дейкстры | алгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации(эвристическая функция) в данный момент являются наилучшими, причем алгоритм учитывает путь уже пройденный до текущей вершины.

Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит[[Файл:Diagonal.png|thumb|right|Пример А* на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой [http://deep-beta.co.uk/wp-content/uploads/2010/11/terrain.0.3+grid.png координатной сеткой].

Если мы можем перемещаться в четырех направлениях, в качестве эвристики стоит выбрать [http://en.wikipedia.org/wiki/Manhattan_distance манхэттенское расстояние]
<tex>h(v) = |{v.x-goal.x}| + |{v.y-goal.y}|</tex>.

[http://ru.wikipedia.org/wiki/Расстояние_Чебышева Расстояние Чебышева] <tex>h(v) = \max{(|{v.x-goal.x}|, |{v.y-goal.y}|)}</tex> применяется когда к четырем направлениям добавляются диагонали.

Если передвижение не ограниченно сеткой, то можно использовать евклидово расстояние по прямой <tex>h(v) = \sqrt{(v.x-goal.x)^2 + (v.y-goal.y)^2}</tex>.

Также стоит обратить внимание на то как соотносятся <tex>f(v)</tex> и <tex>h(v)</tex>. Если они измеряются в разных величинах(Например, <tex>g(v)</tex> это расстояние в километрах, а <tex>h(v)</tex> {{---}} оценка времени пути в часах) А* может выдать некорректный результат.

==Псевдокод==

[[Файл:Astar_progress_animation.gif|thumb|right|Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.]]
void A*(start,goal)
{
closed := {}; // Множество вершин расстояние до которых мы уже оценили
open.push(start);// Очередь с приоритетом
f[start] = g[start] + h[start];
parent[start] = start;
while (open.size() != 0)
{
x := open.pop();
if (x == goal)
return succsess(x);// Кратчайший путь найден
closed.push(x);
for (y : xy in E)
{
if (y in closed)
continue;
tmp := g[x] + d[x,y] // Стоимость пути до y через х
if (y not in open)
{
open.push(y);
tentative_is_better = true;
}
else
if (tmp < g[y]) // можно улучшить расстояние до y
tentative_is_better = true
else
tentative_is_better = false
if (tentative_is_better == true) // найден новый, более короткий путь до y
{
parent[y] = x;
g[y] = tmp;
f[y] = g[y] + h[y];
}
}
}
return failure; // Наша цель недостижима из start
}
==Свойства==
===Корректность===
Если <tex>h(v)</tex> всегда меньше либо равна истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм.

===Оптимальность===
Любой другой алгоритм, использующий ту же эвристическую функцию <tex>h(v)</tex>, рассмотрит не меньше вершин, чем А*.
==Ссылки==
*[http://ru.wikipedia.org/wiki/Алгоритм_поиска_A* Википедия:Алгоритм_поиска_A*]
*[http://en.wikipedia.org/wiki/A*_search_algorithm Wikipedia:A*_search_algorithm]
*[http://theory.stanford.edu/~amitp/GameProgramming/ Статья о поиске кратчайших путей]
*[http://dl.acm.org/citation.cfm?id=3830&coll=portal&dl=ACM Generalized best-first search strategies and the optimality of A*]

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

Файл:Manhattan.png

2011-12-31T06:28:53Z

ЗабылПароль:

2011-11-02T16:15:24Z

ЗабылПароль: /* Доказательство оптимальности и корректности */

Алгоритм '''А*'''("A star", "А звёздочка") находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
==Эвристика==
Все вершины графа перевзвешиваются и f(v) = g(v) + h(v), где g(v) - наименьшая стоимость пути в v из стартовой вершины, h(v) - эвристическое приближение стоимости пути от v до конечной цели. h(v) должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторй картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку.
==Псевдокод==

==Доказательство оптимальности и корректности==
Алгоритм A* и допустим, и обходит при этом минимальное количество вершин, благодаря тому, что он работает с «оптимистичной» оценкой пути через вершину. Оптимистичной в том смысле, что, если он пойдёт через эту вершину, у алгоритма «есть шанс», что реальная стоимость результата будет равна этой оценке, но никак не меньше. Но, поскольку A* является информированным алгоритмом, такое равенство может быть вполне возможным.

Когда A* завершает поиск, он, согласно определению, нашёл путь, истинная стоимость которого меньше, чем оценка стоимости любого пути через любой открытый узел. Но поскольку эти оценки являются оптимистичными, соответствующие узлы можно без сомнений отбросить. Иначе говоря, A* никогда не упустит возможности минимизировать длину пути, и потому является допустимым.

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

==Оценка времени работы==
==Применение==
==Ссылки==
*[http://ru.wikipedia.org/wiki/Алгоритм_поиска_A* Алгоритм_поиска_A* Википедия]
*[http://en.wikipedia.org/wiki/A*_search_algorithm A*_search_algorithm Wikipedia]
*[http://theory.stanford.edu/~amitp/GameProgramming/ Статья о поиске кратчайших путей и различных оптимизациях А* в частности]

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

2011-06-15T17:25:06Z

ЗабылПароль: /* Ссылки */

{{В разработке}}
'''Быстрая сортировка'''(qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. В худшем случае работает за <Tex>O(n^2)</Tex>, среднее время работы <Tex>O(nlogn)</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении.

==Алгоритм==
* Выбираем опорный элемент.
* Разбиваем массив таким образом, что все элементы меньшие или равные опорному будут лежать левее опроного элемента, а большие или равные правее.
* Рекурсивно сотрируем "маленькие" и "большие" элементы.

var
a : array [ 1 . .N] of integer ;
procedure QSort ( left , right : integer ) ;
var
i , j : integer ;
key : integer ;
buf : integer ;
begin
key := a [ random ( right - left + 1) + left ] ;
i := left ;
j := right ;
repeat
while a [ i ] < key do
inc ( i ) ;
while key < a [ j ] do
dec ( j ) ;
if i <= j then begin
buf := a [ i ] ;
a [ i ] := a [ j ] ;
a [ j ] := buf ;
inc ( i ) ;
dec ( j ) ;
end ;
unti l i > j ;
if left < j then
QSort ( left , j ) ;
if i < right then
QSort ( i , right ) ;
end ;
begin
. . .
QSort ( 1 , N) ;
end .

===Оптимизация глубины рекурсии до O(logn) в худшем случае===
В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь <Tex>O(n)</Tex>. Этого можно избежать, если в цикле разбивать массив, но рекурсивно вызываться только от части, содержащей меньшее число элементов, а большую часть продолжать разбивать в цикле.

==Асимптотика==
Oh, boy, here we go!
===Худшее время работы===
Обозначим худшее время работы за <tex>T(n)</tex>. Получим рекуррентное соотношение
<tex>T(n) = Max(T(q-1)+T(n-q-1))+\Theta(n)</tex>

Предположим, что <tex>T(n) \leq cO(n^2)</tex>. Тогда получим
<tex>T(n) \leq Max(cq^2+c(n-q-1)^2)+\Theta(n) =
cMax(q^2+(n-q-1)^2)+\Theta(n)</tex>

<tex>Max(q^2+(n-q-1)^2) \leq (n-1)^2</tex>

<tex>T(n) \leq cn^2 - c(2n-1) + \Theta(n) \leq cn^2</tex>
Таким образом <tex>T(n) = O(n^2)</tex>
===Среднее время работы===

==Ссылки==
http://ru.wikipedia.org/wiki/Быстрая_сортировка

http://en.wikipedia.org/wiki/Quicksort

Быстрая сортировка

2011-06-15T15:57:09Z

ЗабылПароль: /* Алгоритм */

Быстрая сортировка

2011-06-15T15:55:45Z

ЗабылПароль:

{{В разработке}}
'''Быстрая сортировка'''(qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. В худшем случае работает за <Tex>O(n^2)</Tex>, среднее время работы <Tex>O(nlogn)</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении.

==Алгоритм==
* Выбираем опорный элемент.
* Разбиваем массив таким образом, что все элементы меньшие или равные опорному будут лежать левее опроного элемента, а большие или равные правее.
* Рекурсивно сотрируем "маленькие" и "большие" элементы.

var
a : array [ 1 . .N] of integer ;
procedure QSort ( left , right : integer ) ;
var
i , j : integer ;
key : integer ;
buf : integer ;
begin
key := a [ random ( right - left + 1) + left ] ;
i := left ;
j := right ;
repeat
while a [ i ] < key do
inc ( i ) ;
while key < a [ j ] do
dec ( j ) ;
if i <= j then begin
buf := a [ i ] ;
a [ i ] := a [ j ] ;
a [ j ] := buf ;
inc ( i ) ;
dec ( j ) ;
end ;
unti l i > j ;
if l e f t < j then
QSort ( l e f t , j ) ;
if i < r i g h t then
QSort ( i , r i g h t ) ;
end ;
begin
. . .
QSort ( 1 , N) ;
end .

===Оптимизация глубины рекурсии до O(logn) в худшем случае===
В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь <Tex>O(n)</Tex>. Этого можно избежать, если в цикле разбивать массив, но рекурсивно вызываться только от части, содержащей меньшее число элементов, а большую часть продолжать разбивать в цикле.
==Асимптотика==
Oh, boy, here we go!
===Худшее время работы===
Обозначим худшее время работы за <tex>T(n)</tex>. Получим рекуррентное соотношение
<tex>T(n) = Max(T(q-1)+T(n-q-1))+\Theta(n)</tex>

Предположим, что <tex>T(n) \leq cO(n^2)</tex>. Тогда получим
<tex>T(n) \leq Max(cq^2+c(n-q-1)^2)+\Theta(n) =
cMax(q^2+(n-q-1)^2)+\Theta(n)</tex>

<tex>Max(q^2+(n-q-1)^2) \leq (n-1)^2</tex>

<tex>T(n) \leq cn^2 - c(2n-1) + \Theta(n) \leq cn^2</tex>
Таким образом <tex>T(n) = O(n^2)</tex>
===Среднее время работы===

==Ссылки==
http://ru.wikipedia.org/wiki/Быстрая_сортировка

http://en.wikipedia.org/wiki/Quicksort

Так как некий ленивый за***нец не собирается делать вики-конспект я его внаглую беру себе =^-^=.

Дискретная математика и алгоритмы

2011-06-15T15:36:59Z

ЗабылПароль: /* Сортировка */

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

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

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

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

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

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

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

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

== [[Марковская цепь|Марковские цепи]] ==

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

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

== Приоритетные очереди ==
* [[Двоичная куча|Двоичная куча]]
* [[Биномиальная куча|Биномиальная пирамида]]
* [[Фибоначчиевы кучи|Фибоначчиевы кучи]]

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

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

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

== Дерево Фенвика ==
* [[Дерево Фенвика]]
* [[Встречное дерево Фенвика]]
* [[Дерево Фенвика, запрос изменения элемента]]
* [[Многомерное дерево Фенвика]]

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

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

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

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

Обсуждение:Теоретический минимум по математическому анализу за 2 семестр

2011-06-12T16:02:00Z

ЗабылПароль:

Вопрос №7. Признак типа Абеля-Дирихле

казалось бы, недостаточно, чтобы <tex>a_n(x)</tex> стремилась к нулю, нужно еще чтобы она это делала монотонно
:fixed

14, 15 вопрос, конечно, очень хотелось бы, что-бы запилили [[Участник:System29a|System29a]] 02:48, 12 июня 2011 (UTC)

Могу ошибаться но в 49 вопросе написан критерий существования первообразной, а нужно что-то вроде
ранг тау -> 0 предел разности верхних и нижних сумм дарбу ->0?

Быстрая сортировка

2011-06-07T18:09:51Z

ЗабылПароль:

{{В разработке}}
'''Быстрая сортировка'''(qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. В худшем случае работает за <Tex>O(n^2)</Tex>, среднее время работы <Tex>O(nlogn)</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении.

==Алгоритм==
* Выбираем опорный элемент.
* Разбиваем массив таким образом, что все элементы меньшие или равные опорному будут лежать левее опроного элемента, а большие или равные правее.
* Рекурсивно сотрируем "маленькие" и "большие" элементы.

===Оптимизация глубины рекурсии до O(logn) в худшем случае===
В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь <Tex>O(n)</Tex>. Этого можно избежать, если в цикле разбивать массив, но рекурсивно вызываться только от части, содержащей меньшее число элементов, а большую часть продолжать разбивать в цикле.
==Асимптотика==
Oh, boy, here we go!
===Худшее время работы===
Обозначим худшее время работы за <tex>T(n)</tex>. Получим рекуррентное соотношение
<tex>T(n) = Max(T(q-1)+T(n-q-1))+\Theta(n)</tex>

Предположим, что <tex>T(n) \leq cO(n^2)</tex>. Тогда получим
<tex>T(n) \leq Max(cq^2+c(n-q-1)^2)+\Theta(n) =
cMax(q^2+(n-q-1)^2)+\Theta(n)</tex>

<tex>Max(q^2+(n-q-1)^2) \leq (n-1)^2</tex>

<tex>T(n) \leq cn^2 - c(2n-1) + \Theta(n) \leq cn^2</tex>
Таким образом <tex>T(n) = O(n^2)</tex>
===Среднее время работы===

==Ссылки==
http://ru.wikipedia.org/wiki/Быстрая_сортировка

http://en.wikipedia.org/wiki/Quicksort

Так как некий ленивый за***нец не собирается делать вики-конспект я его внаглую беру себе =^-^=.