Квазирешетки в прикладных задачах обработки цифровой информации
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
? вида
с номером N = 0,1, 2,... Получена верхняя оценка для количества шагов в алгоритме, из которой следует, что данный одномерный алгоритм является быстрым[5].
Определим отображение
(1.17)
обладающее свойствами , где , функция r(N) принимает значения из N = {0,1, 2,...}, J = [-1, ?) и черта обозначает замыкание множеств. Тогда [6]. Отображение можно записать в явном виде
(1.18)
Одномерная квазирешетка Фибоначчи F - это дискретное подмножество из R. Неопределяемое следующим образом (1.18):
,(1.19)
где для всех N ? Z. Заметим, что , при этом ' - сопряжение в квадратичном поле . Квазирешетка F обладает целым рядом интересных свойств. Так, например, успешно применяют ее к построению алгоритма деления с остатком в кольце O . Здесь же приведены некоторые простейшие свойства квазирешетки F.
Обозначим F+ подмножество из F, состоящее из точек вида ?(N) с параметрами N ? N. Разностная функция равна , если , и , если Отсюда заключаем, что множество F+ параметризуется вращениями окружности. Из [7] следует, что последовательность
(1.20)
где , является последовательностью Штурма. Последовательность и (1.20) полностью характеризует положительную часть F+ квазирешетки F, так как , если , и , если . Последовательность u инвариантна относительно подстановки, действующей на символы 0, 1 по правилу, и получается из 1 многократным применением подстановки ?. Длина последовательностей равна , где - числа Фибоначчи, определяемые рекуррентным соотношением Fm+2 = Fm+1 + Fm иначальным условием F1 = 1, F2 = 2. Так же, как и для чисел Фибоначчи Fm, для последовательностей выполняется свойство рекуррентности
(1.21)
где слева стоит последовательность, получающаяся последовательным продолжением элементами последовательности , т.е. это некоммутативная операция прикладывания одной последовательности к другой. Например, . Обозначим . Тогда из (1.21) вытекает
(1.22)
рекуррентное свойство конечных отрезков подрешетки . Таким образом, F+ можно получить с помощью операций сложения и предельного перехода из двух ее частей и .
Множество обладает центральной симметрией для любого N ? Z\ {-1}Используя формулу (1.18), можем записать i на языке параметров . Отсюда получаем, что проколотая квазирешетка центрально-симметрична
с центром симметрии , не являющимся элементом из .
Кроме симметрии i, квазирешетка F допускает богатую полугруппу подобий , - подмножество тех N ? Z, для которых |. Для любого N ? выполняется включение
.
Особый интерес представляет случай N =1, когда наблюдается подобие
(1.23)
с коэффициентом , являющимся основной единицей кольца Фибоначчи . В данном случае подобие (1.23) представляет собою инфляцию проколотой квазирешетки , соответствующую подстановке ?.
Квазирешетка F не является периодической, т.е. равенство F + t = F возможно только при t = 0. Это вытекает из аналогичного свойства множества параметров . Однако имеют место следующие два свойства:
(1.24)
где , означающие, что квазирешетка F почти замкнута относительно операций сложения и вычитания (свойство Мейера).
С целью расширить класс одномерных квазирешеток введем квадратную квазирешетку (рисунок 1.1)
(1.25)
Данную квазирешетку можно характеризовать как множество всех точек (x1, x2) из O2 с ограничением (x1, x2) ? J2 или более кратко -
.(1.26)
Пусть прямая L проходит через две точки из F2. Тогда будет одномерной квазирешеткой. В частности, если L - главная диагональ, то получаем квазирешетку L, подобную квазирешетке F .А если L - дополнительная диагональ, то L уже не будет подобна F, поскольку расстояния между соседними точками в L принимают три различных значения. Как например у квазирешетки L2,0 на рисунке 1.1.
Чтобы классифицировать возникающие таким способом одномерные квазирешетки L, нам потребуется детальное изучение разбиений Фибоначчи полуинтервала J.
По существу мы используем известный метод Cut and Project, выбирая в определении (1.26) в качестве окна или внутреннего пространства W квадрат J2. Если выбрать W произвольным выпуклым множеством, то новых типов квазирешеток L не добавится [2]. Если же допустить невыпуклые W, то могут возникнуть квазирешетки L получающиеся объединением предыдущих квазирешеток.
Отождествим полуинтервал I =[0,1) с единичной окружностью R/Z, и определим нанем сдвиг
,
где - золотое сечение. Поскольку сдвиг ? и 1 несоизмеримы, то можно для любого ? ? I определить индуцированное отображение (или отображение Пуанкаре)
, где (1.27)
интервал, на котором действует S?. Известно, что индуцированное отображение S?. изоморфно 1) нециклическому перекладыванию трех полуинтервалов из или 2) перекладыванию двух полуинтервалов из , что эквивалентно вращению единичной окружности на некоторый угол. Случай 2) возникает, когда параметр ? принимает значения
для (1.28)
Для таких е полуинтервал разбивается
(1.29)
на два полуинтервала с соотношением длин и для m четных и нечетных соответственно. В (1.29) обозначает некоммутативную операцию прикладывания одного полуинтервала к другому. Индуцированное отображение перекладывает
(1.30)
полуинтервалы из разбиения (1.29). При этом индуцированное отображение S(m) изоморфно
(1.31)
сдвигу S или ему обратному сдвигу S-1 для четных или н