В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 22

Пусть ω - примитивный корень степени n +1 из 1. Тогдавыполнено:n + 1, если α ≡ 0(mod( n + 1)).=∑0,еслисравнениеневерноДоказательство. Если α ≡ 0(mod( n + 1)) ,то ω sα = 1 по определению.nsαωs=0Если сравнение неверно, то∑nω sαs=0=∑nt s t =ω αs=0t n+1 − 1=t -1t=ω α= 0 , т.к.t = ωα ≠ 1 иt n+1 = ω α ( n+1) = 1.

Утверждение доказано.Утверждение 3. Выберем точки xi = ω i , 0 ≤ i ≤ n , где ω - примитивныйкорень степени n +1 из 1. Тогда прямое и обратное преобразования полиномастепени n требует O(n log n) операций.Доказательство. Используем данные точки x0 ,..., xn для преобразованияnФурье. Пусть дан многочлен p(x)= ∑ j =0 a j x j и выполним прямое преобразованиеnp(x)= ∑ j =0 a j x jx= x jследующим образом:Считаем, что n +1= 2r . Имеем p( x) = a0 + a1 x+...+ an x n == (a0 + a2 x 2 +...+ an−1 x n−1 ) + (a1 x + a3 x 3 +...+ an x n ) == (a0 + a2 x 2 +...+ an−1 x n−1 ) + x(a1 + a3 x 2 +...+ an x n−1 ) .Положим y = x 2 .

Тогда имеемn−1y 2 )+p( x) = ( a0 + a2 y+...+ an−1x( a1 + a3 y+...+ ann −1где deg p1 = deg p2 == 2r −1 − 1.2n−1y 2 )= p1 ( y) + xp2 ( y) ,121Вычисление p(x) в точках x0 ,..., xn сводится к p1 ( y) и p2 ( y) в точкахy0 ,..., yn , где yi = xi2 , среди которыхn+1различных.2Данный процесс организуем рекурсивно, решая 2 задачи половиннойразмерности.Оценим сложность Т( 2r ) - число арифметических операций длявычисления многочлена∑2r −1a xii =0 i{}в выбранных 2r точках ω t 0 ≤ t ≤ 2r - 1 ,где ω - примитивный корень степени 2r из 1.

Тогда имеемT(2r ) = 2T(2r −1 ) + 2 ⋅ 2r ,где последний член представляет одно сложение и одно умножение для каждогоxi .Теперь заметим, что можно уменьшить число умножений в два раза,используя соотношение xi + 2r −1 = − xi .Значит можно записать T(2r ) = 2T(2r −1 ) +T(2r ) =3 r⋅ 2 ⋅ r . Значит T(n)=O(n log n).23 r⋅ 2 , T(1) = 0. Отсюда получаем2Найдем обратное преобразование: {< xi , yi >} → {ai } , где xi = ω i , где ω примитивный корень степени n +1 из 1.Организуем вычисление как умножение вектора на матрицу. Положим...

1 1 1 12n... ω 1 ω ωV = 1 ω 2 ω 4 ... ω 2n . . .1 ω n ω 2n ... ω n2 Тогда ( a0 ,..., an )V = ( y0 ,..., yn ) и ( a0 ,..., an ) = ( y0 ,..., yn )V −1 .ω − ij~ ~~. Имеем согласноОпределим ( n + 1 × n + 1)-матрицу V = ( vij ) , где vij =n+1 1, если i = j,~утверждению 2 V ⋅ V=ij 0, если i ≠ j.~и поэтому V −1 = V .Следовательно, ( a0 ,..., an ) = ( y0 ,..., yn )V −1 =()1221 1 ... 1 -1-n... ω  11 ω= ( y0 ,..., yn )=.

. .n1+21 ω -n ... ω -n n∑ i =0 yi t it =ω−j⋅1, (0 ≤ j ≤ n) .n+1Если ω - примитивный корень степени n +1 из 1, то это верно и для ω −1 , поэтомуобратное преобразование Фурье эквивалентно прямому преобразованию и,следовательно требует O(n log n) арифметических операций.Если n - не степень двойки, то заменяем ее ближайшей сверху степенью двойки.Ясно, что это сохраняет порядок оценки.Следствие.

Умножение двух многочленов степени n можно выполнить заO(n log n) операций в поле комплексных чисел.Заметим, что имеются алгоритмы БПФ с операциями в конечных полях. Длязнакомства с ними следует обратиться к журнальной литературе.123§ 19. Сложность алгоритмов выборана частично упорядоченном множестве и их оптимальность.Построение эффективных алгоритмов выбора элементов конечногомножества в соответствии с некоторым свойством возможно лишь в тех случаях,когда исходное множество наделено некоторой структурой, а соответствующиеалгоритмы опираются на данную структуру.

В данном разделе изучаетсясложность выбора элементов из частично упорядоченного множества с помощьюалгоритмов, опирающихся на отношение частичной упорядоченности ивыясняется их оптимальность. К задачам такого типа сводятся многиепереборные задачи, представляющие практический интерес,Пусть М - конечное множество, на элементах которого определенонекоторое свойство Р. Пусть f P - характеристическая функция тех элементов изМ, которые обладают свойством Р, т.е.

двоичная функция, для которой имеем 1, если а обладает Р,f P ( a) =  0, если а не обладает Р.Ясно, что задача перечисления элементов М, обладающих свойством Р,равносильна задаче выделения двоичной функции f P или задаче нахождения{разбиения ( М 1 , М 2 ), где М 1 = а ∈ Мf P ( a) = 1} .Пусть M(≤) - частично упорядоченное множество, а свойство Р согласованос отношением частичного порядка.

Свойство Р1 на множестве М называетсянаследственным влево, если из b ≤ a, f P1 ( b) = 1 следует f P1 ( a) = 1 .Соответственно, свойство P2 называется наследственным вправо, если изb ≤ a, f P2 ( a) = 1 следует f P2 ( b) = 1. Легко видеть, что наследственным влевосвойствам Р соответствуют монотонные функции f P , для которых справедливосоотношение:b ≤ a ⇒ f P ( b) ≤ f P ( a), ∀ a,b ∈ M .Наследственным вправо свойствам Р соответствуют инверсно монотонныефункции f P , для которых справедливо соотношение:b ≤ a ⇒ f P ( a) ≤ f P ( b), ∀ a,b ∈ M .Ясно, что достаточно ограничиться рассмотрением наследственных влево свойствР и соответственно задачей выделения монотонной функции f P на М , посколькудвойственный случай наследственного вправо свойства сводится переходом отмножества М к инверсно изоморфному множеству М’.

Нас будет интересоватьвопрос алгоритмической сложности выделения монотонной двоичной функцииf P на частично упорядоченном множестве М. Сложность алгоритмаопределяется положенной в основу вычислительной интерпретацией алгоритма,т.е. элементарным шагом алгоритма и его логической схемой.Под сложностью алгоритма А понимается число элементарных шагов,необходимое для получения окончательного результата. Пусть f - произвольная124монотонная двоичная функция на М, заданная в виде отображенияf : М → {0,1}. Пусть а={A} - множество алгоритмов, решающихпоставленную задачу, т.е. для произвольной монотонной функции на М любойалгоритм A∈а с помощью отображения f определяет соответствующее fразбиение ( М 1 , М 2 ) множества М.

Работа любого алгоритма A∈а протекаетследующим образом. Алгоритм А производит выбор некоторого элемента а ∈М ивычисляет значение f(a) .Если f(a)=1, то в список М 1 заносится a и все элементы b, b ≥ a . Если f(a)=0, то всписок М 2 заносится a и все элементы b, b ≤ a . Затем по некоторому правилувыбирается другой элемент из М и процесс повторяется. Это продолжается до техпор, пока разбиение ( М 1 , М 2 ) не будет определено полностью.В качестве элементарного шага алгоритма А возьмем вычисление значенияфункции f(a) для некоторого а ∈М с помощью отображения f : М → {0,1}.Для произвольного а ∈М определим множества V a = {b, b > a} иN a = {b, a > b} .

Тогда за один шаг алгоритма на элементе a значение fопределяется либо на всем V a , либо на всем N a . Любой паре - алгоритму А имонотонной функции f можно поставить в соответствие число ω(A,f) - количествообращений к отображению f : М → {0,1} в процессе определения разбиения( М 1 , М 2 ) для функции f при работе по алгоритму A. Сложность фиксированногоалгоритма А оценим функциейω ( A,M) = max ω ( A, f )f(максимум по всем монотонным функциям типа f : М → {0,1}).Сложность самой задачи выделения произвольной монотонной функции наМ будем характеризовать функциейω ( М) = min max ω ( A, f )Af(минимум по всем алгоритмам A∈а, решающим данную задачу).Функция ω(M) для частично упорядоченного множества оцениваетвозможности для сокращения числа опробований в переборных алгоритмах,использующих только структуру частичной упорядоченности на опробуемыхэлементах.По аналогии с терминологией, используемой в теории монотонных булевыхфункций, введем следующие определения.Пусть F - множество всех монотонных двоичных функций на M.Совокупность элементов N f ⊆ M называется определяющей совокупностью дляf∈F, если по значениям функции f на множестве N f однозначно определяютсязначения f на всем М.

Другими словами, определяющая совокупность N fхарактеризуется тем, что для любой функции g∈F из того, что f(a)=g(a), ∀a∈ N fследует f=g.125Определяющая совокупность называется тупиковой для f∈F, если никакоеее собственное подмножество не является определяющей совокупностью для f.Заметим, что для определения разбиения ( М 1 , М 2 ) множества М для f∈Fнеобходимо и достаточно определить значения f на некоторой ее определяющейсовокупности.Некоторый элемент а ∈М называется:-верхним нулем для f, если f(а)=0 и f(b)=1, ∀ b∈ V a ,-нижней единицей для f, если f(а)=1 и f(b)=0, ∀ b∈ N a . Обозначим через Z f множество верхних нулей, а через U f - множество всех нижних единиц дляфункции f.Теорема 1.

Множество D f = U f U Z f является единственной тупиковойопределяющей совокупностью для монотонной функции f.Доказательство. Действительно, по определению множества D f , позначениям функции f на множестве D f однозначно определяются значения f намножестве М и, значит, D f - определяющая совокупность для функции f.Далее, согласно определению, а∈ D f в том и только в том случае, когдазначение f(а) однозначно определяет значение f для всех b∈М, таких, что b∈ V a иb∈ N a . Поэтому никакое подмножество D f ’⊂ D f не может быть определяющейсовокупностью для f .Пусть теперь R - некоторая определяющая совокупность для функции f иz∈ Z f - некоторый верхний нуль для функции f .Предположим, что z∉R. Тогда имеем по определению f(z)=0.

Поскольку R определяющая совокупность, то по значениям f на множестве R однозначноопределяются значения f на всем М, в том числе и в точке z. Но f(z)=0 помонотонности может быть выведено только в том случае, когда имеется нулевоезначение для элемента, большего z. Значит, существует z1 ∈R, z< z1 и f( z1 )=0. Но z- верхний нуль для f, значит f( z1 )=1, что противоречит допущению z∉R.Следовательно, Z f ⊂ D f . Аналогично доказывается, что U f ⊂ D f . Значит, любаяопределяющая совокупность для функции f∈F содержит множество D f . Теоремадоказана.Обозначим d M = max D f , где максимум берется по всем f∈F.fТеорема 2. Для любого частично упорядоченного множества М имеютместо соотношенияi ≤ d M ≤ 2i ,где i - максимальное число попарно несравнимых элементов М.Доказательство.

Пусть {а1,...,аi } - множество попарно несравнимыхэлементов множества М. Определим двоичную функцию f следующим образом:f ( a1 ) = f ( a2 ) =... = f ( ai ) = 1126f ( a) = 1, если a ∈ V ak для некоторого к ∈1,i ,f ( a) = 0, если a ∈ N ak для некоторого к ∈1,i .Функция f имеет, очевидно, i нижних единиц, откуда и следует нижняяоценка.Для доказательства верхней оценки заметим, что любые две нижниеединицы попарно несравнимы. Значит, число элементов М, являющихся нижнимиединицами, не более, чем i - максимальное число попарно несравнимыхэлементов в М.