2 526
edições
m
→Tamanho do problema
| Linha 144: | Linha 144: | ||
Quantos códigos naturais de ''k'' bits deixam de ser representados na Base ''N''? | Quantos códigos naturais de ''k'' bits deixam de ser representados na Base ''N''? | ||
Na tabela abaixo foram avaliadas experimentalmente as taxas de ocupação para diversos valores de ''k'', | Avaliando a seguir apenas bases com ''N'' em {4, 8, 16, 32} da [https://datatracker.ietf.org/doc/html/rfc4648 RFC 4648] das aplicações da Internet e (base 4) das aplicações em [[geocódigos]]. São todas na forma <math>N=2^n</math>, com ''n'' variando de 2 (4=2<sup>2</sup>) a 5 (32=2<sup>5</sup>). O valor de ''n'' fornece também o número de bits por dígito da base, por exemplo base ''N''=8 temos ''n''=3, portanto cada dígito da base 8 tem 3 bits. | ||
Na tabela abaixo foram avaliadas experimentalmente as taxas de ocupação para diversos valores de ''k'', resultando em uma quantidade de códigos, <math>n\_codes=2^{k+1}-2</math>, e nas quantidades de representações válidas a cada base. | |||
{| class="wikitable" | {| class="wikitable" | ||
| | | | ||
| Linha 150: | Linha 153: | ||
| colspan="8" rowspan="1" | '''Base and occupancy rate of n_codes''' | | colspan="8" rowspan="1" | '''Base and occupancy rate of n_codes''' | ||
|- | |- | ||
|''' | |'''''k''''' (bits) | ||
|'''n_codes''' | |'''n_codes''' | ||
|'''base4''' | |'''base4''' | ||
| Linha 355: | Linha 358: | ||
|80% | |80% | ||
|} | |} | ||
Os valores percentuais foram calculados com relação a ''n_codes'', as médias finais de ''occupancy'' com relação aos ciclos. | |||
O comportamento da taxa de ocupação é cíclico e converge rapidamente, sendo destacado em negrito o primeiro ciclo estável de cada base. A média dentro do ciclo estável é a esperada pelo número de bits: em 2 bits (base 4) apenas os códigos de 1 bit deixam de ser representados, portanto 50%; em 3 bits (base 8) os códigos de 1 e 2 bits deixam de ser representados, portanto apenas 1/3 = 33% é representado; em 4 bits apenas 1/4=25% e em 5 bits apenas 1/5=20%. | O comportamento da taxa de ocupação é cíclico e converge rapidamente, sendo destacado em negrito o primeiro ciclo estável de cada base. A média dentro do ciclo estável é a esperada pelo número de bits: em 2 bits (base 4) apenas os códigos de 1 bit deixam de ser representados, portanto 50%; em 3 bits (base 8) os códigos de 1 e 2 bits deixam de ser representados, portanto apenas 1/3 = 33% é representado; em 4 bits apenas 1/4=25% e em 5 bits apenas 1/5=20%. | ||
Conclusão: | Conclusão: nas bases de aplicação mais frequente (as bases 8 e 16), entre 67% e 75% dos códigos naturais deixam de ser representados. É uma perda muito grande, vale a penas investir numa solução. | ||
== Inovação tecnológica nas representações == | == Inovação tecnológica nas representações == | ||