Алгоритмы на основе систем счисления? [закрыто]

87

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

  • Биномиальные кучи основаны на двоичных числах, а более сложные косые биномиальные кучи основаны на косых двоичных числах.
  • Некоторые алгоритмы генерации лексикографически упорядоченных перестановок основаны на факторадической системе счисления.
  • Попытки можно рассматривать как деревья, которые просматривают одну цифру строки за раз для соответствующей базы.
  • Деревья кодирования Хаффмана предназначены для того, чтобы каждое ребро в дереве кодировало ноль или единицу в некотором двоичном представлении.
  • Кодирование Фибоначчи используется в поиске Фибоначчи и для инвертирования определенных типов логарифмов.

Мой вопрос: какие еще существуют алгоритмы, которые используют умную систему счисления в качестве ключевого шага своей интуиции или доказательства? . Я думаю о том, чтобы составить доклад на эту тему, поэтому чем больше примеров я буду использовать, тем лучше.

templatetypedef
источник
5
Мне тоже нравится вопрос, но как выбрать «правильный» ответ? Это должно быть вики сообщества?
Влад
14
Это должна быть вики сообщества
BlueRaja - Danny Pflughoeft
18
@close voter: Если вопрос об алгоритмах не по теме в SO, я не знаю, что здесь по теме. Идиотские вопросы новичков о CSS? "Могу ли я использовать регулярное выражение, пожалуйста"? "Пожалуйста, отправьте электронное письмо с кодом 4 mi hoemwok"?
MAK
2
Автостопом по галактике: каков ответ на жизнь, вселенную и все остальное? Ответ Deep Thought: 42. Земля как машина, чтобы найти вопрос: что такое 9 x 6? и поэтому все так пиздец. На футболке: 9 (основание 13) x 6 (основание 13) = 42 (основание 13). QED.
Крис Уолтон,
"Какие еще существуют алгоритмы, которые используют умную систему счисления в качестве ключевого шага своей интуиции или доказательства?" Stack Overflow - это не механизм рекомендаций , список всего или ферма ссылок . Алгоритмы для решения практических вопросов программирования, абсолютно. Информационные центры для умных алгоритмов, нет. Возможно, вы захотите спросить у мета-журнала Mathematics, хотят ли они этого.

Ответы:

39

У Криса Окасаки есть очень хорошая глава в своей книге « Чисто функциональные структуры данных», в которой обсуждаются «Числовые представления»: по сути, возьмите некоторое представление числа и преобразуйте его в структуру данных. Чтобы дать представление, вот разделы этой главы:

  1. Системы позиционных чисел
  2. Двоичные числа (двоичные списки с произвольным доступом, представления без нуля, ленивые представления, сегментированные представления)
  3. Перекос двоичных чисел (перекос двоичных списков произвольного доступа, перекос биномиальных куч)
  4. Тройные и четвертичные числа

Некоторые из лучших приемов дистилляции:

  • Различайте плотное и разреженное представление чисел (обычно вы видите это в матрицах или графиках, но это применимо и к числам!)
  • Полезны избыточные системы счисления (системы, которые имеют более одного представления числа).
  • Если вы сделаете первую цифру отличной от нуля или используете представление без нуля, получение заголовка структуры данных может быть эффективным.
  • Избегайте каскадных заимствований (из хвоста списка) и переносов (из списка в список) путем сегментации структуры данных

Вот также список ссылок к этой главе:

  • Гибас, МакКрайт, Пласс и Робертс: новое представление линейных списков.
  • Майерс: прикладной стек произвольного доступа
  • Карлссон, Манро, Поблете: неявная биномиальная очередь с постоянным временем вставки.
  • Каплан, Тарджан: чисто функциональные списки с цепочкой через рекурсивное замедление.
Эдвард З. Янг
источник
2
+1 У меня есть копия книги Окасаки ... Мне понравились эти главы, и отчасти именно поэтому я вообще задал этот вопрос (самонастраивающиеся косые биномиальные кучи действительно круты!) Я не прочитал их полностью, хотя возможно я должен. Также я проверю эти ссылки; они отлично выглядят.
templatetypedef
Полную версию тезиса Окасаки можно найти в Интернете: cs.cmu.edu/~rwh/theses/okasaki.pdf
Gigi,
20

«Тернарные числа могут использоваться для удобной передачи самоподобных структур, таких как треугольник Серпинского или множество Кантора». источник

«Четвертичные числа используются в представлении двумерных кривых Гильберта». источник

"Четвертимнимая система счисления была впервые предложена Дональдом Кнутом в 1955 году в ходе поиска научных талантов в средней школе. Это нестандартная позиционная система счисления, в которой в качестве основы используется мнимое число 2i. Она способна для представления каждого комплексного числа с использованием только цифр 0, 1, 2 и 3. " источник

«Римские цифры - это биполярная система». источник

«Senary может считаться полезным при изучении простых чисел, так как все простые числа, выраженные по основанию шесть, кроме 2 и 3, имеют 1 или 5 в качестве последней цифры». источник

«Шестидесятеричная система счисления (основание 60) - это система счисления, в основе которой лежит шестьдесят. Она возникла у древних шумеров в 3-м тысячелетии до нашей эры, она была передана древним вавилонянам и до сих пор используется - в измененной форме - для измерения время, углы и географические координаты, которые являются углами ". источник

так далее...

Этот список - хорошая отправная точка.

Бенджамин
источник
6
Ничего из этого не связано с алгоритмами ..
BlueRaja - Дэнни Пфлугофт
11
Конечно, есть. Построение треугольника Серпинского в троичной системе или вычисление географических координат в шестидесятеричной системе счисления. Как насчет алгоритма преобразования римских цифр в десятичные? Как насчет алгоритмов поиска простых чисел на основе сенарной системы?
Benjamin
9

На днях я прочитал ваш вопрос и сегодня столкнулся с проблемой: как сгенерировать все разбиения набора? Решение, которое пришло мне в голову и которое я использовал (возможно, из-за чтения вашего вопроса), было следующим:

Для набора с (n) элементами, где мне нужно (p) разделов, подсчитайте все (n) числовые числа в базе (p).

Каждое число соответствует разделу. Каждая цифра соответствует элементу в наборе, а значение цифры говорит вам, в какой раздел поместить элемент.

Это не удивительно, но аккуратно. Он полный, не вызывает избыточности и использует произвольные основания. База, которую вы используете, зависит от конкретной проблемы разделения.

Бен Хорнер
источник
3
Я думаю, что это полностью украдено из сообщения templatetypedef, должно быть, оно застряло в моем подсознании. Я оставил его только потому, что он говорит о большем количестве баз, чем просто двоичные.
Бен Хорнер
2
Это генерирует все разделы, содержащие не более p разделов, и имеет избыточность. Как 111222отличается от 222111?
Нулевой установлен
7

Недавно я наткнулся на классный алгоритм для генерации подмножеств в лексикографическом порядке на основе двоичных представлений чисел от 0 до 2 n - 1. Он использует биты чисел как для определения элементов, которые следует выбрать для набора, так и для локального изменения порядка. сгенерированные наборы, чтобы привести их в лексикографический порядок. Если вам интересно, у меня есть запись здесь .

Кроме того, многие алгоритмы основаны на масштабировании (например, слабо-полиномиальная версия алгоритма максимального потока Форда-Фулкерсона), который использует двоичное представление чисел во входной задаче для постепенного уточнения грубого приближения до полного решения.

templatetypedef
источник
2
Это самый простой способ создания подмножеств :)
st0le
Это самый простой способ счета в комбинаторных концепциях.
Саид Амири
@ st0le - Я думаю, что это немного сложнее, чем стандартная версия, потому что в этом списке наборы наборов в лексикографическом порядке, а не в обычном порядке, который вы получаете из взаимно-однозначного сопоставления между битами и включения набора.
templatetypedef
6

Не совсем умная базовая система, но умное использование базовой системы: последовательности Ван дер Корпута - это последовательности с низким расхождением, сформированные путем обращения представления чисел с основанием n. Они используются для построения 2- мерных последовательностей Холтона, которые выглядят примерно так .

мхам
источник
6

Я смутно помню кое-что о системах с двойным основанием для ускорения умножения матриц.

Система с двойной базой - это система с дублированием, в которой для одного номера используются две базы.

 n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}

Избыточность означает, что один номер можно указать разными способами.

Вы можете найти статью «Гибридный алгоритм вычисления матричного многочлена» Василия Димитрова, Тодора Куклева.

Пытаюсь дать краткий обзор как можно лучше.

Они пытались вычислить матричный полином G(N,A) = I + A + ... + A^{N-1}.

Supoosing N является составным G(N,A) = G(J,A) * G(K, A^J), если мы применим J = 2, мы получим:

         / (I + A) * G(K, A^2)        , if N = 2K
G(N,A) = |
         \ I + (A + A^2) * G(K, A^2)  , if N = 2K + 1

также,

         / (I + A + A^2) * G(K, A^3)           , if N = 3K
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3)     , if N = 3K + 1
         \ I + A * (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 2

Поскольку «очевидно» (в шутку), что некоторые из этих уравнений быстры в первой системе, а некоторые лучше - во второй, поэтому рекомендуется выбрать лучшее из них в зависимости от N. Но это потребует быстрой операции по модулю как для 2, так и для 3. Вот почему приходит двойное основание - вы можете быстро выполнить операцию по модулю для них обоих, давая вам комбинированную систему:

         / (I + A + A^2) * G(K, A^3)       , if N = 0 or 3 mod 6
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 1 or 4 mod 6
         | (I + A) * G(3K + 1, A^2)        , if N = 2 mod 6
         \ I + (A + A^2) * G(3K + 2, A^2)  , if N = 5 mod 6

Прочтите статью для лучшего объяснения, так как я не эксперт в этой области.

Эгон
источник
5

вот хороший пост об использовании троичных чисел для решения проблемы "поддельной монеты" (где вам нужно обнаружить одну поддельную монету в пакете обычных, используя баланс как можно меньше раз)

Мартин ДеМелло
источник
Это был потрясающий пост, и в итоге я использовал его в своем выступлении под названием «Развлечения с системами счисления». Большое спасибо за публикацию!
templatetypedef
добро пожаловать и рад, что вы смогли его использовать!
Мартин ДеМелло
5

Хеширование строк (например, в алгоритме Рабина-Карпа ) часто оценивает строку как число с основанием b, состоящее из n цифр (где n - длина строки, а b - некоторая выбранная база, которая достаточно велика). Например, строка «ABCD» может быть хеширована как:

'A'*b^3+'B'*b^2+'C'*b^1+'D'*b^0

Подставляя значения ASCII для символов и принимая b равным 256, получается,

65*256^3+66*256^2+67*256^1+68*256^0

Хотя в большинстве практических приложений результирующее значение берется по модулю некоторого числа разумного размера, чтобы результат оставался достаточно маленьким.

MAK
источник
4

В Hackers Delight (книге, которую каждый программист должен знать в моих глазах) есть полная глава о необычных основаниях, таких как -2 как основание (да, правильные отрицательные основания) или -1 + i (i как мнимая единица sqrt (-1)) как основание. Также мне приятно посчитать, какова лучшая база (с точки зрения дизайна оборудования, для всех, кто не хочет его читать: решение уравнения - e, поэтому вы можете выбрать 2 или 3, 3 будет немного лучше (коэффициент В 1.056 раза лучше, чем 2) - но технически практичнее).

Другие вещи, которые приходят мне на ум, - это счетчик серого (если вы считаете в этой системе только 1-битные изменения, вы часто используете это свойство в дизайне оборудования, чтобы уменьшить проблемы с метастабильностью) или обобщение уже упомянутой кодировки Хаффмана - арифметическое кодирование.

flolo
источник
3

Криптография широко использует целочисленные кольца (модульная арифматика), а также конечные поля, операции которых интуитивно основаны на поведении полиномов с целочисленными коэффициентами.

Нулевой набор
источник
1

Отличный вопрос. Список действительно длинный. Определение времени - это простой пример смешанного базиса (дни | часы | минуты | секунды | am / pm)

Я создал фреймворк n-tuple для перечисления мета-базы, если вам интересно о нем услышать. Это очень приятный синтаксический сахар для систем счисления. Он еще не выпущен. Напишите мое имя пользователя (на Gmail).

достаточно
источник
1
И любая календарная система - майя, лунная, вавилонская .... вместе с английской валютой до 1971 года (LSD). Как вы говорите, этот список можно продолжить.
Крис Уолтон,
1

Одно из моих любимых приложений с основанием 2 - это арифметическое кодирование . Это необычно, потому что суть алгоритма использует представление чисел от 0 до 1 в двоичном формате.

Майкл Андерсон
источник