Задача о поиске максимума последовательности верхняя и нижняя оценки (последняя через связность графа)

• Название: Задача о поиске максимума последовательности верхняя и нижняя оценки (последняя через связность графа)
• Дата: 05.10.2022
• Размер: 394.95 Kb.
• Имя файла: AIalg_lectures_2022.pdf
• Тип: Лекция; #716573

AI Masters. Алгоритмы п л а н - к о н с п е к т л е к ц и й
Александр Рубцов, Дмитрий Киранов, Кирилл Чеканов [e-mail]

Содержание
Об этом файле
3 0
Введение. Верхние и нижние оценки сложности алгорит- мов
5 0.1 Введение
6 0.1.1 Верхние и нижние оценки
8 0.2 Сложность алгоритмов
. . . . . . . . . . . . . . . . . . . . . 10 0.2.1 O-Ω-Θ-обозначения
. . . . . . . . . . . . . . . . . . . 10 0.2.2 Примеры и свойства
. . . . . . . . . . . . . . . . . . . 11 0.2.3 Эффективные алгоритмы
. . . . . . . . . . . . . . . . 12 0.2.4 Θ-эквивалентность и сравнение функций
. . . . . . . 13 1
Жадные алгоритмы
15 1.1 Пример
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2 Индуктивные функции
. . . . . . . . . . . . . . . . . . . . . 17 1.3 Онлайн-алгоритмы
. . . . . . . . . . . . . . . . . . . . . . . 19 1.4 Связь между ключевыми понятиями лекции
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2

Об этом файле
В этом файле будут приведены конспекты первых лекций, а далее будет приведён план-конспект остальных лекций. Файл будет обновляться каждую неделю.
В этом файле будут приведены конспекты первых лекций по курсу
«Алгоритмы», читаемому автором в AI Masters 2022, а далее будет приве- дён план-конспект остальных лекций. Файл будет обновляться каждую неделю. Курс ранее читался в Ozon Masters, а также близкий курс читал- ся на ФУПМ МФТИ; конспекты к последнему подготовлены совместно с
Дмитрием Кирановым и Кириллом Чекановым.
3

4

Лекция 0
Введение. Верхние и нижние оценки сложности алгоритмов
Литература:
[
ДПВ12
;
КЛРШ05
;
КЛР02
]
Содержание лекции
1. Язык Си как исполнители алгоритмов.
2. Сложность по времени и по памяти. Верхние и нижние оценки.
Примеры:
• Задача о поиске максимума последовательности: верхняя и нижняя оценки (последняя — через связность графа)
• Проверка числа n на простоту перебором делителей до
√
n
—
экспоненциальный алгоритм (сложность измеряется по длине входа.).
3. O, Ω, Θ обозначения — формальные определения.
• f(n) = Θ(g(n)) — отношение эквивалентности.
• Если P (n) — многочлен степени k, то P (n) = Θ(n k
)
• Сумма чисел от 1 до n есть Θ(n
2
)
• 1
k
+ 2
k
+ . . . + n k
= Θ(n k+1
)
• Оценка суммы через интеграл (без доказательства).
5

0.1
Введение
Курс «Алгоритмы» посвящен решению алгоритмических задач. Под решением мы понимаем построение алгоритма, решающего задачу, дока- зательство его корректности и получение верхних и нижних оценок на время его работы и используемую память — оценку сложности. Мы не будем уделять особое внимание формализации понятий «алгоритмическая задача» и даже «алгоритм» — дело это непростое, поэтому мы не будем тратить время на формализацию этих понятий. Тем более, что каждый из вас интуитивно понимает смысл этих понятий и вряд ли никогда не сталкивался с алгоритмами в современном мире.
Давайте проиллюстрируем описанные выше этапы решения задачи на примере простой и хорошо известной задачи — задачи о поиске максимума последовательности.
Пример 1. На вход задачи подаётся последовательность целых чисел x
1
, . . . , x n
, ввод которой оканчивается маркером конца строки. Необхо- димо найти наибольший элемент этой последовательности.
Сначала нам нужно убедиться, что задача алгоритмически разре- шима — увы, не все задачи имеют решение. Для этих целей достаточно построить даже не самый оптимальный алгоритм — приведём таковой.
Алгоритм.
Запишем все элементы последовательности в массив. Будем сравнивать все возможные пары x i
и x j
и хранить результат сравнения в матрице A (двумерном массиве): a i,j
= 1
, если x i
> x j
и a i,j
= 0
иначе.
Найдём в получившейся матрице строку, состоящую из одних единиц —
пусть её номер i. Выведем элемент x i
в качестве ответа.
После того как алгоритм описан, нужно доказать его корректность.
Корректность.
Поскольку элементов последовательности конечное чис- ло, значит найдётся элемент x k
, который не меньше всех остальных —
по построению матрицы A, все элементы k-ой строки будут тогда равны единице. Если алгоритм вывел элемент x k
, то он сработал корректно,
потому что x k
— максимум по определению; если же алгоритм вывел другой элемент — x i
, то x i
> x k
, поскольку a i,k
= 1
, а значит x i
также является максимумом.
Программисты часто считают, что если алгоритм описан, то это опи- сание и является доказательством его корректности, однако как легко видеть, длина предыдущего абзаца даже немного больше, чем длина описания самого алгоритма. Бесспорно, корректность этого алгоритма
6

очевидна, но мы здесь специально обращаем внимание на то, что до- казательство корректности является важным шагом в решении задачи,
которым нельзя пренебрегать.
После того как корректность алгоритма доказана, возникает вопрос о том, насколько этот алгоритм эффективен. В качестве основных пока- зателей эффективности чаще всего исследуют время работы алгоритма
(количество операций, которые он совершает) и размер потребляемой памяти. Для того, чтобы формально оценить эти показатели, требуется зафиксировать формальную модель вычислений — исполнителя алгорит- ма. Такими моделями как правила являются машина Тьюринга и разные вариации RAM-модели. Однако изучение этих моделей мы также оста- вим для второго курса. В качестве исполнителя алгоритма, мы будем использовать язык Си.
Чтобы оценить временную сложность алгоритма, достаточно записать его код на Си и посчитать количество операций, выполняемых програм- мой. Сложность оценивается от длины входа. В данном примере, чтобы оценить сложность, нам нужно наложить дополнительное условие на задачу: нужно договориться, считаем ли мы арифметические операции константными или зависящими от длины записи числа. На практике выбор условия зависит от задачи. Будем считать, что в нашем случае все числа x i
укладываются в диапазон Integer — выбираем первое условие.
Оценка сложности.
На вход программе из нашего примера подаётся n
чисел — длина входа порядка n. Программа сравнивает каждый элемент с каждым и заполняет матрицу — на это уходит порядка n
2
операций,
и потом ищет единичную строку — это тоже порядка n
2
операций за один проход по матрице. Выполнение каждой из упомянутых операций стоит некоторую константу (как и вспомогательных операций в процессе исполнения алгоритма), поэтому не говорят, что программа работает за n
2
, а говорят что время работы программы порядка n
2
или, что тоже самое — время работы алгоритма Θ(n
2
)
. Далее мы приведём формальное определение этого обозначения.
Со сложностью по памяти дело обстоит также: программа хранит массив из n элементов и матрицу из n
2
элементов, а значит использует
Θ(n
2
)
битов памяти. Обратим внимание, что тут мы считаем, что целые числа укладываются в диапазон Integer, и потому операции считывания,
присваивания и сравнения стоят константу. Фактически, этот выбор явля- ется нашим выбором модели вычислений, в которой и происходит оценка сложности работы алгоритма. Если бы мы считали, что числа могут быть
7

очень большими, то ни в один числовой тип языка Си такое бы число не поместилось, а значит нам бы пришлось считать сложность операций присваивания и сравнения не константной, а зависящей от длины записи чисел и тогда оценка времени работы алгоритма изменилась бы.
0.1.1
Верхние и нижние оценки
Мы оценили сложность по времени и по памяти только одного алго- ритма, решающего нашу задачу. Существование алгоритма гарантирует разрешимость задачи, а сложность алгоритма даёт верхнюю оценку на сложность задачи, под которой мы понимаем сложность самого лучшего алгоритма, решающего задачу. Заметим, что может так получиться, что один алгоритм может быть самым быстрым, в то время как минималь- ную память может использовать другой, не самый быстрый, алгоритм.
Поэтому мы всегда разделяем сложность задачи по времени и по памяти,
и наличие у задачи двух оценок на сложность по времени и сложность по памяти не влечёт существование алгоритма, для которого обе эти оценки выполняются.
Подобно символу Θ, который обозначает порядок роста, для обозначе- ния верхних оценок используют символ O: мы показали, что сложность задачи по времени и по памяти есть O(n
2
)
. Оценки только верхние, пото- му что могут быть алгоритмы, которые решают задачу лучше — и такой алгоритм есть для нашего примера.
Алгоритм.
Считаем первые два элемента и сравним их, запомнив максимальный из них, затем считаем третий элемент и сравним его с максимумом из первых двух и так далее:
m = max(x
1
, x
2
);
m = max(m, x
3
);
m = max(m, x n
).
В результате исполнения такого алгоритма (написать код на Си мы оставляем читателю) в переменной m очевидно окажется максимум по- следовательности. Такой алгоритм работает за время Θ(n), поскольку выполняет n − 1 операцию сравнения в процессе вычисления максимумов,
и требует константу памяти, то есть Θ(1) памяти. Итак, мы получили верхние оценки гораздо лучше: оценку по времени O(n) и оценку по памяти O(1)!
Насколько эти оценки хорошие? Понятно, что лучшая оценка по памяти невозможна: алгоритм должен хранить в памяти хотя бы макси- мальный элемент, чтобы его вывести. Но что насчёт оценки по времени?
8

Здравый смысл подсказывает, что лучше эту задачу не решить, но как это доказать? Почему не найдётся кто-то очень умный, который придумает алгоритм лучше?
Для того, чтобы это доказать нам нужна формализация как алгоритма,
так и задачи. От алгоритма нам потребуется свойство детерминирован- ности
: если в процессе вычислений на двух разных входах алгоритм выполнил одну и ту же последовательность действий первые n шагов и хранит в памяти одинаковые значения, то следующий шаг для обоих входов будет одинаковым. От задачи мы потребуем следующее: теперь алгоритму не будут сообщать значения самих чисел, но алгоритм может попросить сравнить два числа и получить в качестве ответа на вопрос x
i
?
> x j
один бит. Теперь задачу можно сформулировать так: есть n мо- нет разного веса и чашечные весы — необходимо найти самую тяжёлую монету, совершив как можно меньше взвешиваний.
Утверждение 1. Для поиска самой тяжёлой монеты необходимо со- вершить n − 1 взвешивание.
Доказательство.
Возьмём произвольный набор из n монет с весами x
1
, . . . , x n
(x i
> 0
) и отдадим их на вход алгоритму, который делает меньше, чем n − 1 взвешивание. Запомним какие монеты сравнивались между собой и построим граф, вершины которого — монеты, а ребро есть только между монетами, которые сравнивались между собой.
Поскольку всего было меньше, чем n − 1 взвешивание, то в графе меньше n − 1 ребра, а значит граф несвязен. Максимум x k
лежит в некоторой компоненте связности — назовём её первой. В качестве второй компоненты связности возьмём любую другую и пусть в ней максимум x
m
6 x k
Увеличим вес каждой монеты во второй компоненте связности на x k
Это не поменяет результатов сравнений, но максимумом теперь станет монета под номером m с весом x m
+ x k
. В силу детерминированности,
алгоритм на изменённом входе должен вернуть монету x k
как самую тяжёлую, но значит алгоритм решает задачу неверно.
Замечание 1. Детерминированности алгоритма чаще всего достаточ- но, чтобы доказать, что алгоритм не может работать сублинейное время
1
. Если алгоритм работает за сублинейное время в худшем случае,
1
Алгоритм работает сублинейное время, если совершает меньше, чем Cn опера- ций — например, порядка dlog ne.
9

то он не считывает некоторую часть входа, а чтобы решить зада- чу чаще всего нужно знать весь вход. Так, если алгоритм не узнал значение одного из x i
, то именно этот элемент может оказаться максимальным.
0.2
Сложность алгоритмов
Определим формально временную сложность работы алгоритмов
(сложность по памяти определяется аналогично). Временная сложность алгоритма — это количество операций, которые алгоритм выполняет в худшем случае на входе длины n, таким образом, это функция f : N
1
→ N
1
(под N
1
мы понимаем положительные целые числа). Поскольку нас инте- ресуют не численные значения этой функции, а порядок роста, то дабы упростить жизнь в случае функций вида f(n) = ndlog ne (здесь и далее dxe
— округленик числа x вверх до целого), мы будем рассматривать функции f : N
1
→ R
+
, где R
+
— это положительные вещественные числа.
Пример 2. На вход подаётся число N , необходимо проверить, является ли оно простым.
Задачу легко решить, деля с остатком N на каждое из чисел a 6
√
N
:
если один из остатков ноль, то число составное, иначе — простое. Этот алгоритм имеет сложность Θ(
√
N )
(мы считаем, что арифметические операции стоят константу), но N в данном примере не длина входа! Чтобы записать число N потребуется n = blog
2
N c + 1
битов, поэтому сложность алгоритма по длине входа есть Θ(2
n/2
)
— это экспоненциальный алгоритм!
Поэтому простые числа ищут нетривиальным вероятностным алгоритмом,
а полиномиальный детерминированный алгоритм является значимым результатом в Computer Science.
0.2.1
O-Ω-Θ-обозначения
Выше мы уже использовали обозначения Θ и O для оценки сложности алгоритмов. Дадим теперь формальное определение этим обозначениям.
Определение 1.
Говорят, что f(n) = O(g(n)), если f(n) 6 Cg(n) начиная с некоторого N; здесь C — положительная константа. Формально
∃C > 0, N ∈ N
1
∀n > N : f(n) 6 Cg(n).
10

Таким образом, функция g является верхней оценкой для функции f.
Заметим, что тогда f — это нижняя оценка для функции g. Для описания нижних оценок используют обозначение Ω. Формально,
g(n) = Ω(f (n))
, если f(n) = O(g(n)).
В случае, когда функция g является как верхней, так и нижней оценкой для функции f, используют обозначение Θ:
f (n) = Θ(g(n))
, если f(n) = O(g(n)) и f(n) = Ω(g(n)).
Упражнение 1.
Покажите, что если f(n) = Θ(g(n)), то g(n) = Θ(f(n)).
0.2.2
Примеры и свойства
Пример 3. Порядок роста многочлена степени k с неотрицательными коэффициентами — n k
:
P
k
(n) = a k
n k
+ a k−1
n k−1
+ . . . + a
1
n + a
0
= Θ(n k
).
Действительно, пусть a — максимальное число среди коэффициентов:
a = max i
a i
, тогда при n > 1, P
k
(n) 6 kan k
:
a k
n k
+ a k−1
n k−1
+ . . . + a
1
n + a
0 6 an k
+ an k−1
+ . . . + an + a 6 kan k
,
а значит P
k
(n) = O(n k
)
. А также, при достаточно больших n (например,
n > ka
), P
k
(n) >
1
a n
k и P
k
(n) = Ω(n k
)
Замечание 2. Естественно хочется заявить, что порядок роста про- извольного многочлена P
k степени k с положительным коэффициентом при старшем члене есть n k
. Формально, этого нельзя сделать в тех случаях, когда P
k
(n) < 0 для некоторого n — мы не рассматриваем функ- ции такого вида, согласно определению асимптотических обозначений.
Однако, незаконная промежуточная выкладка, подобная P
k
(n) = Θ(n k
),
часто удобна при оценке сложности алгоритмов. Чтобы узаконить её,
мы будем считать, что нам годятся не только функции из N
1
в R
+
,
но и функции из N
1
в R, которые начиная с некоторого n принимают только положительные значения.
Пример 4. Сумма чисел от 1 до n есть Θ(n
2
).
11

Действительно, согласно формуле арифметической прогрессии, данная сумма есть n(n + 1)
2
Обобщим этот пример.
Пример 5. 1
k
+ 2
k
+ . . . + n k
= Θ(n k+1
)
Оценим сверху каждый член суммы как n k
, получаем
1
k
+ 2
k
+ . . . + n k
6 n k
+ n k
+ . . . + n k
= n × n k
= O(n k+1
).
Отбросим из суммы первую половину членов и заметим, что каждый оставшийся член не меньше (n/2)
k
:
1
k
+ 2
k
+ . . . + n k
>

n
2

k
+

n
2

k
+ . . . +

n
2

k
|
{z
}
n
2
=
n
2
×

n
2

k
= Ω(n k+1
).
Приведённые примеры требуют некоторой изобретательности для до- казательства верхних и нижних оценок. Вместо них можно пользоваться фактом из математического анализа:
Утверждение 2. Пусть f : [0, +∞) → R
+
— монотонная и непрерывная функция и F (x) — её первообразная. Тогда n
X
k=0
f (k) = Θ(F (n)).
Так,
n
X
k=1 1
n
2
= Θ
 1
n

0.2.3
Эффективные алгоритмы
Определение 2.
Пусть f(n) — временная сложность работы алгоритма
(максимальное число шагов на входе длины n). Алгоритм называется полиномиальным
, если f(n) = O(n k
)
для некоторого k.
Мы будем считать алгоритм эффективным, если он полиномиален.
Так, приведённый в примере
2
алгоритм проверки числа на простоту не эффективен, поскольку экспоненциален.
12

0.2.4
Θ-эквивалентность и сравнение функций
Оставляем читателю проверить, что отношение « f(n) = Θ(g(n)) »
на множестве функций N
1
→ R
+
является отношением эквивалентности;
будем называть его Θ-эквивалентность. Если f(n) = Θ(g(n)), то часто можно в формуле заменить f(n) на g(n), не изменив при этом порядок роста функции, заданной формулой. Однако такая замена справедлива не для всех формул.
Упражнение 2.
Проверьте, что 2
n
6= Θ(2 2n
)
, хотя n = Θ(2n).
Упражнение 3.
Проверьте, что если f(n) = Θ(g(n)), то f(n) + h(n) =
Θ(g(n)+h(n))
и f(n)×h(n) = Θ(g(n)×h(n)) для произвольной функции h.
Знак равенства в обозначении f(n) = Θ(g(n)) возник при упроще- нии нотации. С формальной точки зрения, O(g(n)), Ω(g(n)) и Θ(g(n)) —
множества функций. Правильно было бы писать f(n) ∈ Θ(g(n)).
Θ
-эквивалентность функций означает их асимптотическое равенство,
если f(n) = O(g(n)), то g асимптотически не меньше f, а если f(n) =
Ω(g(n))
, то f асимптотически не больше g.
Множество функций разбивается на классы Θ-эквивалентности. Если f
и g лежат в разных классах и f(n) = O(g(n)), то отсюда следует что все функции эквивалентные f асимптотически меньше всех функций,
эквивалентных g. Таким образом определено отношение порядка на клас- сах эквивалентности. Однако отсюда не следует, что если функции f и g принадлежат разным классам, то одна из них асимптотически меньше другой. Например, функции n
2
и n
2+sin n несравнимы. Это отношение порядка отличается от порядка на числах: оно не линейно, то есть, не все элементы сравнимы.
13

14

Лекция 1
Жадные алгоритмы
Литература:
[
Шен04
;
КФ12
]
1. Пример: задача о поиске треугольника максимальной площади,
сторона которого лежит на оси Ox.
2. Жадные алгоритмы и индуктивные функции [
Шен04
].
• функции максимума и суммы — индуктивные
• индуктивное расширение на примере поиска максимума произ- ведения
3. Онлайн-алгоритмы
1.1
Пример
Программисты относят к жадным алгоритмам алгоритмы, подчи- няющиеся следующему принципу. На каждом шаге алгоритм находит локально-оптимальное решение задачи (то есть, лучшее на данный мо- мент), и хранит в памяти только его (возможно с небольшим объёмом вспомогательных данных). Алгоритм поиска максимума в последователь- ности с предыдущей лекции является классическим примером жадного алгоритма: на каждом шаге алгоритм помнит только максимум считан- ного начального отрезка последовательности и обновляет его по мере появления новых элементов последовательности.
Начнём с примера задачи, для которой жадный алгоритм устроен чуть более сложно.
15

Пример 6. На вход подаются координаты точек плоскости (x
0
, y
0
), . . . ,
(x n
, y n
); вход заканчивается маркером конца строки. Нужно найти треугольник максимальной площади, одна из сторон которого лежит на оси Ox (вершины треугольника присутствуют в последовательности).
Подобно задачам на построение в геометрии, начнём с анализа задачи.
Если треугольник уже найден, то его сторона, лежащая на оси Ox, самая длинная среди сторон на Ox по всем треугольникам. Действительно,
иначе можно заменить сторону треугольника на более длинную, не по- меняв высоту и увеличить тем самым площадь. Рассуждая аналогично заключаем, что вершина (x, y) треугольника, не лежащая на Ox имеет максимальное значение |y| — иначе можно заменить вершину и увеличить высоту.
Проведя анализ заключаем, что для решения задачи достаточно найти самую длинную сторону на оси Ox и точку, не лежащую на оси Ox с максимальным |y|. Чтобы найти сторону достаточно найти самую левую и самую правую точки: то есть точки (x min
, 0)
и (x max
, 0)
Для решения задачи можно воспользоваться «принципом чайника» —
так программисты называют использование уже готового решения. Со- гласно анекдоту, чтобы программисту вскипятить чайник, ему нужно взять чайник, налить в него воду и нажать на кнопку. Но если програм- мисту дать чайник с водой, то вместо того, чтобы нажать на кнопку, он выльет воду и сведёт тем самым задачу к предыдущей.
Итак, чтобы решить задачу, достаточно найти два максимума (среди точек вида (x, 0) и вида (x, y), y 6= 0 по y) и один минимум — ясно, что минимум можно искать также как и максимум. Для этих целей достаточно считать все координаты в массив и выполнить три линейных алгоритма.
Таким образом, мы получили линейный по времени алгоритм для решения задачи.
Этот алгоритм не считается жадным, потому что решение он находит только в самом конце и хранит много лишней информации в памяти —
Θ(n)
битов. Однако этот алгоритм легко преобразовать в жадный алго- ритм, линейный по времени и использующий константную память.
Вместо того, чтобы искать максимум и минимум последовательно,
будем искать их параллельно. Считав координаты (x, y) очередной точки,
определим, лежит ли она на оси Ox, и если да, то меньше ли x текущего минимума x min или больше ли x текущего максимума x max
; если же точка не лежит на оси Ox (т. е. y 6= 0), то проверим больше ли |y| текущего |y|
max
16

Заметим, что часть доказательства корректности была приведена выше при анализе задачи, а оставшаяся часть состоит в повторении доказательство корректности для алгоритма поиска максимума в после- довательности.
Пока мы используем неформальное понятие жадного алгоритма: алго- ритм жадный, если дня него выполняется принцип «дают бери, а бьют —
беги». Формальное определение опирается на понятие матроида, которое сложно для нашего курса. Мы рекомендуем познакомиться с ним толь- ко после изучения нашего курса, а пока рассмотрим один из способов формализации «жадности», не претендующий на полноту.
1.2
Индуктивные функции
Рассмотрим функции, которые определены на конечных последова- тельностях произвольной длины (x
1
, . . . x n
)
с элементами из множества A,
и принимают значение в множестве B. Функция f данного вида назы- вается индуктивной, если существует функция F : B × A → B, такая что f (x
1
, . . . , x n
, x n+1
) = F (f (x
1
, . . . , x n
), x n+1
).
Пример 7. Функции max и sum(x
1
, . . . , x n
) =
n
P
i=1
x i
являются индуктив- ными:
• max(x
1
, . . . , x n
, x n+1
) = max(max(x
1
, . . . , x n
), x n+1
)
• sum(x
1
, . . . , x n
, x n+1
) = sum(sum(x
1
, . . . , x n
), x n+1
)
Для каждой функции из примера f = F , но в общем случае это необязательно.
Жадный алгоритм можно получить для задачи, которая состоит в вычислении индуктивной функцию f, путём нахождения функции F .
Если F известна, то достаточно в цикле считывать следующий элемент последовательности и вычислять y i
= F (y i−1
, x i
)
, где значение y i−1
=
f (x
1
, . . . , x i
)
было вычислено на предыдущем шаге цикла.
Однако, часто бывает, что требуемая функция не является индуктив- ной, но если её чуть-чуть поправить, то она будет уже индуктивной.
Пример 8. Функция f (x
1
, . . . x n
) = max i6=j x
i
× x j
, определённая на положи- тельный целых числах, не индуктивная. Однако её можно превратить
17

в индуктивную, если хранить в памяти пару (m
1
, m
2
) из первого и второго максимума последовательности.
Этот приём называют индуктивным расширением. Формально, индук- тивная функция g : (x
1
, . . . , x n
) → Y
называется индуктивным расши- рением функции f : (x
1
, . . . , x n
) → B
, если существует такая функция t : Y → B
, что t(g(x
1
, . . . , x n
)) = f (x
1
, . . . , x n
).
Для примера с максимальным произведением можно, взять в каче- стве g функцию, возвращающую пару (m
1
, m
2
)
, тогда t(m
1
, m
2
) = m
1
×m
2
Пример 9
(продолжение примера
6
). Пусть f((x
1
, y
1
), (x
2
, y
2
), . . . , (x n
, y n
))
возвращает максимальную площадь треугольника, одна из сторон кото- рого лежит на оси Ox. Построим для неё индуктивное расширение g.
Функция g возвращает координаты трёх точек ((x max
, 0), (x min
, 0), (x, y))
,
которые являются вершинами треугольника максимальной площади. Что- бы определение g было формально корректным потребуем, что бы в случае, если одна из подходящих точек не была ещё считана, в этой ком- поненте было записано число −1, а не пара чисел. Функция g индуктивна:
построим для неё функцию G, такую что
G(g((x
1
, y
1
), (x
2
, y
2
), . . . , (x n−1
, y n−1
)), (x n
, y n
)) = g((x
1
, y
1
), . . . , (x n
, y n
)).
Функция G получат на вход выход ((x max
, 0), (x min
, 0), (x, y))
функции g
и точку (x n
, y n
)
. Если y n
= 0
, то в случае если x n
> x max
, x max меняется на x n
, а если x n
< x min
, то x min меняется на x n
. Если же y n
6= 0
, то если |y n
| > |y|
, то точка (x, y) меняется на (x n
, y n
)
. В остальных случаях,
выход функции g остаётся без изменений. Корректность такого пересчёта ясна из корректности исходного алгоритма; в этом примере мы просто формализовали его через индуктивные функции. Осталось определить функцию t(g(. . .)), которая возвращает искомую площадь
1 2
(x max
− x min
) y или −1, если одна из компонент входа равна −1.
Одним из подходов решения алгоритмических задач является выбор математического инварианта, который поддерживается в ходе исполне- ния программы. В случае жадных алгоритмов, такой инвариант часто получается найти, сформулировав задачу в терминах индуктивных функ- ций (возможно с расширением). Этот подход отражён в книге [
Шен04
], в которой индуктивные функции освящены более подробно.
18

1.3
Онлайн-алгоритмы
Индуктивные функции естественным образом применяются для реше- ния задач специального вида:
Вход:
последовательность x
1
, x
2
, . . . , x n
(n заранее не задано);
Выход: f (x
1
, x
2
, . . . , x n
)
Функция f является параметром и фактически определяет задачу. Тип элементов последовательности зависит от задачи. Обратим внимание,
что f определена для всех конечных последовательностях, или что то же самое на любом массиве.
Решение задачи состоит в вычислении f(x
1
, x
2
, . . . , x n
)
, но помимо итогового результата требуется вычислять значение f(x
1
, x
2
, . . . , x k
)
после обработки каждого элемента последовательности x k
на входе.
Такие задачи часто встречаются в реальной жизни. Например, при реализации электронной очереди в банке, заранее неизвестно кто из клиентов придёт по какому вопросу, и нужно распределять всех клиентов по сотрудникам по мере прихода. Другой пример, при работе агентства недвижимости, необходимо продавать квартиру первому покупателю,
пожелавшему её приобрести. Агентству было бы выгоднее подождать всех покупателей за год, узнать их предпочтения и только после этого продать максимальное число квартир по лучшим (для агентства) ценам.
Но покупателей приходится обслуживать в порядке их прихода.
Алгоритмы для таких задач называют онлайн-алгоритмами. То есть,
онлайн-алгоритм вычисляет значение f(x
1
, x
2
, . . . , x k
)
после считывания каждого элемента x k
Заметим, что если алгоритм на каждом шаге вычисляет индукитвную функцию, то это онлайн алгоритм. Если же он вычисляет индуктив- ное расширение g, то он не обязательно онлайн — для того, чтобы стать онлайн-алгоритмом, ему нужно ещё на каждом шаге вычислять и значе- ние t(g(x
1
, . . . , x i
))
Онлайн-алгоритмы возникают не только при изучении жадных задач.
Например, на практике бывают нужны онлайн-алгоритмы сортировки.
Такие алгоритмы на каждом шаге хранят в памяти отсортированный начальный отрезок последовательности. Представьте, что в библиотеку за неделю завозят несколько партий книг. Конечно, чтобы все их рас- ставить на полки лучше знать заранее какие книги и сколько привезут
(чтобы оставить нужное место на полках), но если этого не знать, то
19

книги всё равно нужно расставить на полки в отсортированном поряд- ке, дабы обслуживать читателей. Возможно, этот пример станет более убедительным, если мы заменим библиотеку на базу данных.
Офлайн-алгоритмами называют алгоритмы, которые решают задачи обработав весь вход. Ясно, что производительность офлайн-алгоритмов не хуже, чем онлайн (первые могут работать как онлайн). Для неко- торых практических задач нужны именно онлайн алгоритмы, поэтому в computer science исследуют отношение производительности онлайн- алгоритмам к офлайн для этих задач.
1.4
Связь между ключевыми понятиями лекции
У нас были формальные определения индуктивной функции (с расши- рением) и онлайн-алгоритмов. Мы не привели формального определения жадного алгоритма в силу его трудности для вводного курса. Заметим,
что эти понятия находятся в общем положении: жадные алгоритмы ис- пользуются для задач оптимизации (таких как поиск максимума какой-то функции), и эти задачи могут как иметь, так и не иметь формулировку,
требуемую для онлайн-алгоритмов. Онлайн-алгоритмы, в свою очередь,
могут применяться не для задач оптимизации: например, для задачи сортировки.
Индуктивные функции удобно использовать для поиска инварианта,
пересчёт которого по мере обработки данных приводит к решению задачи.
С их помощью легко найти жадный алгоритм для элементарных задач. В
то же время, в формулировке задач для онлайн-алгоритмов фактически используется индуктивная функция.
Мы будем использовать понятие жадного алгоритма неформально.
У студентов возникают сомнения: является ли алгоритм в их решении жадным? Если при решении задачи была получена индуктивная функция
(возможно с расширением), то мы считаем (для простоты), что в решении получился жадный алгоритм. Хотя жадными (с точки зрения математики)
бывают не только такие алгоритмы, а с точки зрения программистов,
жадность — понятие растяжимое.
20

Список литературы
[ДПВ12]
С. Дасгупта, Х. Пападимитриу и У. Вазирани. Алгоритмы.
М.: МЦНМО, 2012.
[КЛРШ05]
Т. Кормен, Ч. Лейзерсон, Р. Ривест и К. Штайн. Алго- ритмы: построение и анализ.
2-е. М.: Вильямс, 2005.
[КЛР02]
Т. Кормен, Ч. Лейзерсон и Р. Ривест. Алгоритмы: постро- ение и анализ.
М.: МЦНМО, 2002.
[Шен04]
А. Х. Шень. Программирование: теоремы и задачи. М.:
МЦНМО, 2004.
[КФ12]
Н .Н. Кузюрин и С .А. Фомин. Эффективные алгоритмы и сложность вычислений
. 2012.
[Вял и др.21] М. Вялый, В. Подольский, А. Рубцов, Д. Шварц и А.
Шень. Лекции по дискретной математике. ИД НИУ
ВШЭ. Черновик:
https://publications.hse.ru/mirror/
pubs/share/direct/393719078.pdf
, 2021.
[ЖФФ12]
Ю. И. Журавлёв, Ю. А. Флёров и О. С. Федько. Дискрет- ный Анализ. Комбинаторика. Алгебра логики. Теория графов
. М.: МФТИ, 2012.
[ЖФВ07]
Ю. И. Журавлёв, Ю. А. Флёров и М. Н. Вялый. Дис- кретный Анализ. Основы высшей алгебры
. М.: МЗ-пресс,
2007.
[Lei96]
Tom Leighton. “Notes on Better Master Theorems for Divide- and-Conquer Recurrences”. В: Lecture notes, MIT. 1996. url:
https : / / courses . csail . mit . edu / 6 . 046 / spring04 /
handouts/akrabazzi.pdf
21