Троичные алгоритмы

Троичные алгоритмы — алгоритмы, в которых применяется деление или умножение на 3 или на 3 в степени n и применяется троичная логика анализа результата. Хорошо подходят для реализации на троичных компьютерах, при эмуляции на двоичных компьютерах могут потерять свои преимущества.

Примеры

Троичный поиск

На троичных компьютерах могут быть реализованы алгоритмы троичного поиска, использующие разбиение области поиска (например, базы данных) на три части.

Также возможно построение троичного дерева поиска en:Ternary search tree, которое сочетает в себе свойства нескольких различных структур данных.

Троичный поиск корней уравнения

Алгоритм поиска корней уравнений путём деления отрезка (площади, объёма) на три части сходится быстрее алгоритма поиска корней уравнения путём деления отрезка (площади, объёма) на две части.

Троичные сортировки

Среди троичных сортировок можно отметить:

• Модификацию Ternary QuickSort с делением на три отрезка, а не на два, как в оригинальном QuickSort. Одна из версий предложена Bentley and McIlroy.^[1]
• В другой, популярной модификации QuickSort реализуется выбор среднего из 3 элементов или даже из 3 троек элементов.
• Для массивов, в которых имеются частые повторы элементов, предложен алгоритм Ternary Split Quick Sort, выделяющий на этапе разбиения в отдельную группу элементы, равные текущему "среднему"^[2]

Троичный алгоритм взвешивания на весах

Подобно «задаче с гирями», решённой Фибоначчи, троичный алгоритм взвешивания на весах применял Д. И.Менделеев («задача Баше-Менделеева»^[3]).

Троичные АЦП (аналогоцифровые преобразователи) и ЦАПы (цифроаналоговые преобразователи)

Во многих АЦП (ADC) и ЦАПах (DAC) применяются двоичные алгоритмы последовательного приближения («взвешивания» входного напряжения) с использованием матрицы сопротивлений «R-2R» с терминатором 2R. Как и в случае с весами, в них тоже можно применить троичные алгоритмы «взвешивания» входного напряжения. В троичном случае нужно применять матрицу сопротивлений 4R-3R c терминатором 6R. При управлении от троичного микропроцессора скорость преобразования будет быстрее, а время преобразования меньше, чем при двоичных алгоритмах.

Троичный делитель газа (газовый процессор)

Устройство последовательного деления количества газа при двоичном итерационном алгоритме деления объёма газа на две части состоит из четырёх клапанов и вакуумной линии.

Устройство последовательного деления количества газа при троичном итерационном алгоритме деления объёма газа на три части состоит из пяти клапанов и вакуумной линии, но деление происходит быстрее, чем в устройстве с двоичным алгоритмом. За два-три десятка итерационных циклов небольшие объёмы газа 1-10см³ можно разделить почти до молекул (атомов), затем молекулой (атомом), например паров золота, можно «стрельнуть» по мишени-подложке, например из кремния, и таким образом нанести проводник на подложку.

Троичное быстрое преобразование Фурье (БПФ, FFT)

В работе Цифровые процессоры сигналов. описывается троичная эмуляция троичного быстрого преобразования Фурье на двоичной основе.

Коды исправления ошибок

• Троичный код Голея см Двоичный код Голея и en:Ternary Golay code

См. также

• Троичные компьютеры

Ссылки

1. ↑ Bentley, J.L. and McIlroy, M.D. Engineering A SortFunction. Software-Practice and Experience 23, 1(1993), 1249-1265.
2. ↑ Large-scale genome sequence processing - Google Books
3. ↑ http://www.goldenmuseum.com/2015AMT_rus.html Задача Баше-Менделеева на сайте] Музей Гармонии и Золотого Сечения

Для улучшения этой статьи желательно?: Проставить для статьи более точные категории.