Тестовая страница — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 8 промежуточных версий 4 участников)
Строка 1: Строка 1:
= Второй семестр =
+
<wikitex>
 +
{{TODO|t=НЕ ОЧЕНЬ ПОНИМАЮ, ЗАЧЕМ ВООБЩЕ ЭТО УТСВЕРЖДЕНИЕ ТУТ}}
 +
{{Теорема
 +
|statement=
 +
Если $f$ — функция ограниченной вариации ($f \in \bigvee(a, b)$), то ее можно представить в виде разности монотонно неубывающих функций ($f = f_1 - f_2$).
 +
|proof=
 +
Возьмем в качестве $f_1$ функцию $f_1(x) = \bigvee\limits_a^x (f)$, тогда по аддитивности она будет не убывать.
 +
Определим как $f_2$ функцию $f_2(x) = f_1(x) - f(x)$. Докажем, что она монотонно не убывает.
 +
$a < x_1 < x_2 < b$. Надо доказать, что $f_1(x_1) - f(x_1) \le f_1(x_2) - f(x_2)$, или что $f(x_2) - f(x_1) \le f_1(x_2) - f_1(x_1) = \bigvee\limits_{x_1}^{x_2} (f)$ (используем утверждение 1).
 +
Но действительно $f(x_2) - f(x_1) \le | f(x_2) - f(x_1) | \le \bigvee\limits_{x_1}^{x_2} (f)$, ч. т. д.
 +
}}
  
== Амортизационный анализ ==
+
</wikitex>
* [[Амортизационный анализ. Метод предоплаты]]
 
* [[Саморасширяющийся массив]]
 
* [[Массив с увеличением/уменьшением размера]]
 
* [[Стек]]
 
* [[Очередь]]
 
* [[Список]]
 
 
 
== Приоритетные очереди ==
 
* [[Двоичная куча|Двоичная куча]]
 
* [[Биномиальная куча|Биномиальная пирамида]]
 
* [[Фибоначчиевы кучи|Фибоначчиевы кучи]]
 
 
 
== Система непересекающихся множеств ==
 
* [[СНМ(наивные реализации) | Наивные реализации]]
 
* [[СНМ(списки с весовой эвристикой) | Списки с весовой эвристикой]]
 
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
 
* [[Анализ реализации с ранговой эвристикой  | Анализ реализации с ранговой эвристикой]]
 
 
 
== Деревья поиска ==
 
* [[Упорядоченное множество]]
 
* [[Дерево поиска, наивная реализация]]
 
* [[АВЛ-дерево]]
 
* [[2-3 дерево]]
 
* [[B-дерево]]
 
* [[Красно-черное дерево]]
 
* [[Декартово дерево]]
 
* [[Splay-дерево]]
 
* [[Декартово дерево по неявному ключу]]
 
* [[Дерево ван Эмде Боаса]]
 
 
 
== Дерево отрезков ==
 
* [[Статистики на отрезках. Корневая эвристика]]
 
* [[Дерево отрезков. Построение]]
 
* [[Реализация запроса в дереве отрезков сверху]]
 
* [[Реализация запроса в дереве отрезков снизу]]
 
* [[Несогласованные поддеревья. Реализация массового обновления]]
 
* [[Многомерное дерево отрезков]]
 
* [[Сжатое многомерное дерево отрезков]]
 
 
 
 
 
== Дерево Фенвика ==
 
* [[Дерево Фенвика]]
 
* [[Встречное дерево Фенвика]]
 
* [[Дерево Фенвика для некоммутативных операций]]
 
* [[Многомерное дерево Фенвика]]
 
 
 
== Хеширование ==
 
* [[Хеширование]]
 
* [[Различные алгоритмы хеширования]]
 
* [[Открытое и закрытое хеширование]]
 
* [[Поиск свободного места при закрытом хешировании]]
 
* [[Хеширование кукушки]]
 
* [[Двойное хеширование]]
 
* [[Перехеширование. Амортизационный анализ]]
 
* [[Фильтр Блума]]
 
* [[Универсальное семейство хеш-функций]]
 
 
 
== Сортировка ==
 
* [[Сортировка пузырьком]]
 
* [[Сортировка слиянием]]
 
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
 
* [[Сортировка вставками]]
 
* [[Сортировка подсчетом]]
 
* [[Сортировка подсчетом сложных объектов]]
 
* [[Цифровая сортировка]]
 
* [[Поиск k-ой порядковой статистики]]
 
* [[Поиск k-й порядковой статистики за линейное время]]
 
* [[Теорема о нижней оценке для сортировки сравнениями]]
 
* [[Быстрая сортировка]]
 
 
 
== [[Сортирующие сети]] ==
 
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
 
* [[Сортирующие сети для квадратичных сортировок]]
 
* [[Сеть Бетчера]]
 
 
 
== Алгоритмы поиска ==
 
* [[Троичный поиск]]
 
* [[Поиск с помощью золотого сечения]]
 
* [[Интерполяционный поиск]]
 
* [[Вещественный двоичный поиск]]
 

Текущая версия на 19:10, 4 сентября 2022

<wikitex>

TODO: НЕ ОЧЕНЬ ПОНИМАЮ, ЗАЧЕМ ВООБЩЕ ЭТО УТСВЕРЖДЕНИЕ ТУТ

Теорема:
Если $f$ — функция ограниченной вариации ($f \in \bigvee(a, b)$), то ее можно представить в виде разности монотонно неубывающих функций ($f = f_1 - f_2$).
Доказательство:
[math]\triangleright[/math]

Возьмем в качестве $f_1$ функцию $f_1(x) = \bigvee\limits_a^x (f)$, тогда по аддитивности она будет не убывать. Определим как $f_2$ функцию $f_2(x) = f_1(x) - f(x)$. Докажем, что она монотонно не убывает. $a < x_1 < x_2 < b$. Надо доказать, что $f_1(x_1) - f(x_1) \le f_1(x_2) - f(x_2)$, или что $f(x_2) - f(x_1) \le f_1(x_2) - f_1(x_1) = \bigvee\limits_{x_1}^{x_2} (f)$ (используем утверждение 1).

Но действительно $f(x_2) - f(x_1) \le
[math]\triangleleft[/math]

</wikitex>