Cadeia de bits: mudanças entre as edições
(revisando) |
|||
| Linha 3: | Linha 3: | ||
A noção de "cadeia de bits" ([[wikipedia:bit string|''bit string'']]) foi desenvolvida pela Lógica Matemática, principalmente no início dos anos 1900, e consagrada pelos trabalhos de Turing (1937) e Shannon (1948). | A noção de "cadeia de bits" ([[wikipedia:bit string|''bit string'']]) foi desenvolvida pela Lógica Matemática, principalmente no início dos anos 1900, e consagrada pelos trabalhos de Turing (1937) e Shannon (1948). | ||
Ela difere de um [[wikipedia:Natural number|número natural]] [[wikipedia:Binary number|binário]] por permitir zeros à esquerda. Por exemplo o número natural binário <code> | Ela difere de um [[wikipedia:Natural number|número natural]] [[wikipedia:Binary number|binário]] por permitir zeros à esquerda. Por exemplo o número natural binário <code>0001001</code> é equivalente a <code>1001</code>, mas se dizemos que <code>0001001</code> é uma ''cadeia de bits'', aí essa equivalência deixa de existir. | ||
A rigor, portanto, a cadeia de bits não | A rigor, portanto, a cadeia de bits não pode ser vista como número natural. Ela se mantém íntegra quando interpretada como um '''[[código natural]]'''. | ||
== | == Tamanho == | ||
Toda cadeia de bits pode ter seu tamanho medido: '''é a quantidade de bits na cadeia'''. Uma cadeia de zero bits é uma cadeia vazia. | |||
=== Números | A função ''lenght''(''x'') retorna a medida de tamanho da cadeia ''x''. Exemplos: ''lenght''(<code>00</code>)=2; ''lenght''(<code>11</code>)=2; ''lenght''(<code>010101001</code>)=9. | ||
O tamanho permite classificar cadeias: toda cadeia de tamanho ''k'' é elemento da "classe k", ou seja, o conjunto infinito de todas as cadeias de tamanho ''k''. | |||
=== Números naturais e tamanho fixo === | |||
Nos computadores, tradicionalmente, os números inteiros positivos são representados com zeros a esquerda para completar o número de bits desejado. | Nos computadores, tradicionalmente, os números inteiros positivos são representados com zeros a esquerda para completar o número de bits desejado. | ||
O conjunto <math> | O conjunto <math>C_k</math> de todas as cadeias possíveis de tamanho ''k'' pode ser expresso como conjunto de todos os números naturais de zero a <math>2_k-1</math>, acrescentando-se zeros à esquerda quando seu tamanho for menor que ''k''. | ||
Há um claro isomorfismo entre as cadeias de <math> | Há um claro isomorfismo entre as cadeias de <math>C_k</math> e os números naturais de zero a <math>2_k-1</math>. | ||
No computador, por tradição (ou culpa de softwares mal projetados), pode-se erroneamente forçar que uma cadeia de bits de tamanho fixo seja interpetada como um número. Com a promoção dos [[códigos naturais]] a [[wikipedia:First-class citizen|cidadões de primera classe]], esse erro pode ser evitado. | No computador, por tradição (ou culpa de softwares mal projetados), pode-se erroneamente forçar que uma cadeia de bits de tamanho fixo seja interpetada como um número. Com a promoção dos [[códigos naturais]] a [[wikipedia:First-class citizen|cidadões de primera classe]], esse erro pode ser evitado. | ||
== Referências == | == Referências == | ||
C. E. Shannon (1948), “A Mathematical Theory of Communication”. [https://doi.org/10.1002/j.1538-7305.1948.tb01338.x urn:doi:10.1002/j.1538-7305.1948.tb01338.x]. | Formalizações históricas: | ||
* A. M. Turing (1937), “On Computable Numbers, with an Application to the Entscheidungsproblem”. [https://doi.org/10.1112/plms/s2-42.1.230 urn:doi:10.1112/plms/s2-42.1.230]. | |||
* C. E. Shannon (1948), “A Mathematical Theory of Communication”. [https://doi.org/10.1002/j.1538-7305.1948.tb01338.x urn:doi:10.1002/j.1538-7305.1948.tb01338.x]. | |||
Uso prático: | |||
* https://www.postgresql.org/docs/current/datatype-bit.html | |||
* https://www.postgresql.org/docs/current/functions-bitstring.html | |||
[[Categoria:Conceitos]] | [[Categoria:Conceitos]] | ||
Edição das 08h02min de 31 de maio de 2023
A noção de "cadeia de bits" (bit string) foi desenvolvida pela Lógica Matemática, principalmente no início dos anos 1900, e consagrada pelos trabalhos de Turing (1937) e Shannon (1948).
Ela difere de um número natural binário por permitir zeros à esquerda. Por exemplo o número natural binário 0001001 é equivalente a 1001, mas se dizemos que 0001001 é uma cadeia de bits, aí essa equivalência deixa de existir.
A rigor, portanto, a cadeia de bits não pode ser vista como número natural. Ela se mantém íntegra quando interpretada como um código natural.
Tamanho
Toda cadeia de bits pode ter seu tamanho medido: é a quantidade de bits na cadeia. Uma cadeia de zero bits é uma cadeia vazia.
A função lenght(x) retorna a medida de tamanho da cadeia x. Exemplos: lenght(00)=2; lenght(11)=2; lenght(010101001)=9.
O tamanho permite classificar cadeias: toda cadeia de tamanho k é elemento da "classe k", ou seja, o conjunto infinito de todas as cadeias de tamanho k.
Números naturais e tamanho fixo
Nos computadores, tradicionalmente, os números inteiros positivos são representados com zeros a esquerda para completar o número de bits desejado.
O conjunto de todas as cadeias possíveis de tamanho k pode ser expresso como conjunto de todos os números naturais de zero a , acrescentando-se zeros à esquerda quando seu tamanho for menor que k.
Há um claro isomorfismo entre as cadeias de e os números naturais de zero a .
No computador, por tradição (ou culpa de softwares mal projetados), pode-se erroneamente forçar que uma cadeia de bits de tamanho fixo seja interpetada como um número. Com a promoção dos códigos naturais a cidadões de primera classe, esse erro pode ser evitado.
Referências
Formalizações históricas:
- A. M. Turing (1937), “On Computable Numbers, with an Application to the Entscheidungsproblem”. urn:doi:10.1112/plms/s2-42.1.230.
- C. E. Shannon (1948), “A Mathematical Theory of Communication”. urn:doi:10.1002/j.1538-7305.1948.tb01338.x.
Uso prático: