Algoritmos baseados em sistemas de base numérica? [fechadas]

87

Percebi recentemente que existem muitos algoritmos por aí baseados em parte ou no todo em usos inteligentes de números em bases criativas. Por exemplo:

  • Os heaps binomiais são baseados em números binários, e os heaps binomiais skew mais complexos são baseados em números binários inclinados.
  • Alguns algoritmos para gerar permutações ordenadas lexicograficamente são baseados no sistema numérico fatorádico.
  • As tentativas podem ser pensadas como árvores que procuram um dígito da string por vez, em busca de uma base apropriada.
  • As árvores de codificação Huffman são projetadas para que cada aresta da árvore codifique um zero ou um em alguma representação binária.
  • A codificação de Fibonacci é usada na pesquisa de Fibonacci e para inverter certos tipos de logaritmos.

Minha pergunta é: que outros algoritmos existem que usam um sistema numérico inteligente como uma etapa-chave de sua intuição ou prova? . Estou pensando em fazer uma palestra sobre o assunto, então quanto mais exemplos eu tiver para tirar proveito, melhor.

templatetypedef
fonte
5
Eu também gosto da pergunta, mas como você escolhe a resposta 'correta'? Deve ser um wiki da comunidade?
vlad
14
Este deve ser wiki da comunidade
BlueRaja - Danny Pflughoeft
18
@close voter: Se uma pergunta sobre algoritmos está fora do assunto no SO, não sei o que está em questão aqui. Perguntas idiotas de novato sobre CSS? "posso haz regex plzz"? "plz email teh codez 4 mi hoemwok"?
MAK de
2
Guia do Mochileiro das Galáxias: Qual é a resposta para a Vida, o Universo e tudo? Resposta da Deep Thought: 42. A Terra como a máquina para encontrar a pergunta: o que é 9 x 6? e é por isso que tudo é tão fodido. Visto em uma camiseta: 9 (base 13) x 6 (base 13) = 42 (base 13). QED.
Chris Walton de
"Que outros algoritmos existem que usam um sistema numérico inteligente como uma etapa-chave de sua intuição ou prova?" Stack Overflow não é um Recommendation Engine , uma lista de todas as coisas ou um link farm . Algoritmos para resolver questões práticas de programação, com certeza. Câmaras de compensação para algoritmos inteligentes, não. Você pode querer perguntar no meta da Matemática se eles querem isso.

Respostas:

39

Chris Okasaki tem um capítulo muito bom em seu livro Purely Functional Data Structures que discute "Representações Numéricas": essencialmente, pegue alguma representação de um número e converta-a em uma estrutura de dados. Para dar uma ideia, aqui estão as seções desse capítulo:

  1. Sistemas de número posicional
  2. Números binários (listas binárias de acesso aleatório, representações sem zeros, representações lentas, representações segmentadas)
  3. Skew Binary Numbers (Skew Binary Random Access Lists, Skew Binomial Heaps)
  4. Números Trinário e Quaternário

Alguns dos melhores truques, destilados:

  • Distinguir entre denso e representações esparsas de números (geralmente você vê isso em matrizes ou gráficos, mas também se aplica a números!)
  • Os sistemas numéricos redundantes (sistemas que têm mais de uma representação de um número) são úteis.
  • Se você organizar o primeiro dígito para ser diferente de zero ou usar uma representação sem zero, recuperar o cabeçalho da estrutura de dados pode ser eficiente.
  • Evite emprestar em cascata (de pegar o final da lista) e transportar (de levar para a lista) segmentando a estrutura de dados

Aqui está também a lista de referência para esse capítulo:

  • Guibas, McCreight, Plass e Roberts: Uma nova representação para listas lineares.
  • Myers: uma pilha de acesso aleatório de aplicativos
  • Carlsson, Munro, Poblete: Uma fila binomial implícita com tempo de inserção constante.
  • Kaplan, Tarjan: Listas puramente funcionais com catenação via desaceleração recursiva.
Edward Z. Yang
fonte
2
+1 Eu tenho uma cópia do livro de Okasaki ... Eu adorei esses capítulos e eles são em parte o motivo de eu fazer essa pergunta (montes binomiais de skew bootstrapped são muito legais!) Eu não li tudo isso, no entanto talvez eu deva. Além disso, verificarei essas referências; Eles parecem ótimos.
templatetypedef de
A tese completa de Okasaky está disponível online: cs.cmu.edu/~rwh/theses/okasaki.pdf
Gigi
20

"Os números ternários podem ser usados ​​para transmitir estruturas semelhantes, como um triângulo de Sierpinski ou um conjunto de Cantor, convenientemente." fonte

"Os números quaternários são usados ​​na representação de curvas de Hilbert 2D." fonte

"O sistema numeral imaginário de um quarto foi proposto pela primeira vez por Donald Knuth em 1955, em uma submissão a uma pesquisa de talentos em ciências do ensino médio. É um sistema numeral posicional não padronizado que usa o número imaginário 2i como sua base. É capaz para representar cada número complexo usando apenas os dígitos 0, 1, 2 e 3. " fonte

"Os numerais romanos são um sistema biquinário." fonte

"O senário pode ser considerado útil no estudo de números primos, uma vez que todos os primos, quando expressos na base seis, exceto 2 e 3 têm 1 ou 5 como dígito final." fonte

"Sexagesimal (base 60) é um sistema numeral com sessenta como base. Ele se originou com os antigos sumérios no terceiro milênio aC, foi transmitido aos antigos babilônios e ainda é usado - em uma forma modificada - para medir tempo, ângulos e as coordenadas geográficas que são ângulos. " fonte

etc ...

Esta lista é um bom ponto de partida.

Benjamin
fonte
6
Nenhum deles está relacionado a algoritmos ..
BlueRaja - Danny Pflughoeft
11
Claro que estão. Construindo um triângulo de Sierpinski em ternário, ou calculando coordenadas geográficas em sexagesimal. Que tal um algoritmo para transformar numerais romanos em decimais? Que tal algoritmos de localização de números primos baseados no sistema senário?
Benjamin
9

Li sua pergunta outro dia e hoje me deparei com um problema: Como faço para gerar todas as partições de um conjunto? A solução que me ocorreu e que usei (talvez por ter lido sua pergunta) foi esta:

Para um conjunto com (n) elementos, onde preciso de (p) partições, conte todos os (n) números de dígitos na base (p).

Cada número corresponde a um particionamento. Cada dígito corresponde a um elemento do conjunto e o valor do dígito informa em qual partição colocar o elemento.

Não é incrível, mas é legal. É completo, não causa redundância e usa bases arbitrárias. A base que você usa depende do problema de particionamento específico.

Ben Horner
fonte
3
Eu acho que isso foi completamente roubado do post do templatetypedef, deve ter ficado preso no meu subconsciente. Só o deixei porque fala sobre mais bases do que apenas binárias.
Ben Horner,
2
Isso gera todas as partições com no máximo p partições e tem redundâncias. Como é 111222diferente de 222111?
Conjunto nulo em
7

Recentemente descobri um algoritmo legal para gerar subconjuntos em ordem lexicográfica com base nas representações binárias dos números entre 0 e 2 n - 1. Ele usa os bits dos números para determinar quais elementos devem ser escolhidos para o conjunto e para reordenar localmente os conjuntos gerados para colocá-los em ordem lexicográfica. Se você estiver curioso, tenho um artigo postado aqui .

Além disso, muitos algoritmos são baseados em escala (como uma versão fracamente polinomial do algoritmo de fluxo máximo de Ford-Fulkerson), que usa a representação binária dos números no problema de entrada para refinar progressivamente uma aproximação aproximada em uma solução completa.

templatetypedef
fonte
2
Esta é a maneira mais simples de gerar subconjuntos :)
st0le
Essa é a maneira mais simples de contar em conceitos combinatórios.
Saeed Amiri
@ st0le- Acho que isso é um pouco mais complicado do que a versão padrão porque lista os conjuntos em ordem lexicográfica, em vez da ordem normal que você obtém do mapeamento um-para-um entre os bits e a inclusão do conjunto.
templatetypedef de
6

Não é exatamente um sistema de base inteligente, mas um uso inteligente do sistema de base: as sequências de Van der Corput são sequências de baixa discrepância formadas pela inversão da representação de números base-n. Eles são usados ​​para construir as sequências Halton 2-d que se parecem com isso .

mhum
fonte
6

Lembro-me vagamente de algo sobre sistemas de base dupla para acelerar algumas multiplicações de matrizes.

O sistema de base dupla é um sistema redundante que usa duas bases para um número.

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

Redundante significa que um número pode ser especificado de várias maneiras.

Você pode procurar o artigo "Algoritmo Híbrido para a Computação do Polinômio Matricial", de Vassil Dimitrov, Todor Cooklev.

Tentando dar a melhor visão geral curta que posso.

Eles estavam tentando calcular o polinômio da matriz G(N,A) = I + A + ... + A^{N-1}.

Supondo que N é composto G(N,A) = G(J,A) * G(K, A^J), se aplicarmos J = 2, obteremos:

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

Além disso,

         / (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

Como é "óbvio" (brincando) que algumas dessas equações são rápidas no primeiro sistema e algumas melhores no segundo - é uma boa ideia escolher a melhor das que dependem N. Mas isso exigiria uma operação de módulo rápida para 2 e 3. Aqui está porque a base dupla entra - você pode basicamente fazer a operação de módulo rápido para ambos, dando-lhe um sistema combinado:

         / (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

Leia o artigo para uma melhor explicação, pois não sou um especialista nesta área.

Egon
fonte
5

aqui está uma boa postagem sobre o uso de números ternários para resolver o problema da "moeda falsa" (onde você deve detectar uma única moeda falsa em um saco de moedas normais, usando um saldo o mínimo de vezes possível)

Martin DeMello
fonte
Esta foi uma postagem incrível e acabei usando-a em uma palestra que dei chamada "Diversão com Sistemas Numéricos". Muito obrigado por publicá-la!
templatetypedef de
bem-vindo e feliz por você poder usá-lo!
Martin DeMello
5

Sequências de hash (por exemplo, no algoritmo Rabin-Karp ) geralmente avaliam a sequência como um número de base b consistindo de n dígitos (onde n é o comprimento da sequência e b é alguma base escolhida que é grande o suficiente). Por exemplo, a string "ABCD" pode ser hash como:

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

Substituindo valores ASCII por caracteres e considerando b como 256, isso se torna,

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

Porém, na maioria das aplicações práticas, o valor resultante é considerado módulo de algum número de tamanho razoável para manter o resultado suficientemente pequeno.

MAK
fonte
4

No Hackers Delight (um livro que todo programador deveria conhecer aos meus olhos), há um capítulo completo sobre bases nãousais, como -2 como base (sim, bases negativas direitas) ou -1 + i (i como unidade imaginária sqrt (-1)) como base. Também faço um bom cálculo de qual é a melhor base (em termos de design de hardware, para todos que não querem ler: a solução da equação é e, então você pode ir com 2 ou 3, 3 seria um pouco melhor (fator 1.056 vezes melhor que 2) - mas é técnico mais prático).

Outras coisas que me vêm à mente são o contador cinza (quando você conta neste sistema apenas mudanças de 1 bit, você costuma usar essa propriedade no design de hardware para reduzir problemas de metaestabilidade) ou a generalização da já mencionada codificação de Huffmann - a codificação aritmética.

flolo
fonte
3

A criptografia faz uso extensivo de anéis inteiros (aritmática modular) e também de campos finitos, cujas operações são intuitivamente baseadas no comportamento de polinômios com coeficientes inteiros.

Conjunto Nulo
fonte
1

Ótima pergunta. A lista é realmente longa. A hora de dizer é uma instância simples de bases mistas (dias | horas | minutos | segundos | manhã / tarde)

Eu criei uma estrutura de n-tupla de enumeração de meta-base se você estiver interessado em ouvir sobre isso. É um açúcar sintático muito doce para sistemas de numeração de base. Ainda não foi lançado. Email meu nome de usuário (no gmail).

suficiente
fonte
1
E qualquer sistema de calendário - maia, lunar, babilônico ... junto com a moeda inglesa antes de 1971 (LSD). Como você diz, a lista continua.
Chris Walton de
1

Um dos meus favoritos usando a base 2 é a codificação aritmética . É incomum porque a estrutura do algoritmo usa representações de números entre 0 e 1 em binário.

Michael Anderson
fonte
0

Pode ser que AKS seja o caso.

Saeed Amiri
fonte