Fig. 1
Arraste para girar · Shift + arraste para mover · clique para desmontar
Role para virar a página
Computer Science Principles · AP Computer Science Principles
bits, compressão e informação
Tudo o que um computador guarda, um número, um nome, uma foto, uma música, é, no fundo, um padrão de bits.
Um bit (abreviação de dígito binário, do inglês “binary digit”) é 0 ou 1. Os dispositivos computacionais representam os dados de forma digital: os componentes de mais baixo nível de qualquer valor são bits.
A figura conta em binário. Cada bloco é um bit, com o lado de papel para 0 e o lado vermelho para 1, sob o seu valor posicional, 128, 64, 32, 16, 8, 4, 2, 1. Cada passo soma 1: o bit mais à direita muda, e onde quer que um 1 vire 0 o vai-um se propaga uma casa para a esquerda, como quando 00000111 (7) vira 00001000 (8).
Os programas guardam valores de dados em variáveis, em listas de itens ou como constantes isoladas, passam esses valores como entrada para procedimentos e os recebem de volta como saída. Qualquer que seja a forma, os valores são armazenados como bits, e os programas os traduzem para uma forma que as pessoas conseguem ler.
Este capítulo é a Grande Ideia 2 do AP Computer Science Principles, Dados, 17–22% da prova de múltipla escolha: números binários (2.1), compressão de dados (2.2), extração de informação dos dados (2.3) e uso de programas com dados (2.4).
bits agrupados em abstrações
Um byte tem 8 bits. Sozinho, um byte não significa nada: o significado dele depende do que o programa que o lê considera que ele seja.
A abstração é o processo de reduzir a complexidade concentrando-se na ideia principal. Ao esconder detalhes irrelevantes para a questão em foco e reunir detalhes relacionados e úteis, a abstração permite pensar na ideia em vez de pensar nos bits.
Os bits são agrupados para representar abstrações, entre elas (mas não só) números, caracteres e cor. A figura lê um byte, 01000001, de três maneiras:
| lido como | significa |
|---|---|
| um número binário | 65 |
| um caractere (código ASCII e Unicode 65) | a letra A |
| o brilho de um pixel, de 0 (preto) a 255 (branco) | um cinza escuro |
Assim, a mesma sequência de bits pode representar tipos de dados diferentes em contextos diferentes. Uma imagem colorida costuma guardar três desses números por pixel, um para vermelho, um para verde e um para azul: 3 bytes, 24 bits.
valores posicionais, numerados a partir de 0 na direita
As bases numéricas, entre elas a binária e a decimal, são usadas para representar dados. O decimal (base 10) usa apenas os dígitos 0–9; o binário (base 2) usa apenas 0 e 1.
Como no decimal, a posição de um dígito define o seu valor: o valor numérico é o dígito vezes o valor posicional da sua posição. O valor posicional é a base elevada à potência da posição, e as posições são numeradas a partir do 0 na extrema direita, aumentando de 1 em 1 para a esquerda. No decimal, 305 = 3 × 102 + 0 × 101 + 5 × 100.
No binário, cada casa vale o dobro da que está à sua direita. Para 10110101:
| posição | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| valor posicional | 27 = 128 | 26 = 64 | 25 = 32 | 24 = 16 | 23 = 8 | 22 = 4 | 21 = 2 | 20 = 1 |
| bit | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
Some os valores posicionais onde o bit é 1: 128 + 32 + 16 + 4 + 1 = 181. Um bit 0 não soma nada. A figura lê da esquerda para a direita; cada 1 deixa cair o seu valor posicional na soma.
pegue o maior valor posicional que cabe
Para escrever um número inteiro positivo em binário, trabalhe do maior valor posicional para baixo: onde o valor posicional cabe no que sobra, escreva 1 e subtraia-o; onde não cabe, escreva 0.
Para 100 com oito bits:
| valor posicional | restante | cabe? | bit | sobra |
|---|---|---|---|---|
| 128 | 100 | no | 0 | 100 |
| 64 | 100 | yes | 1 | 36 |
| 32 | 36 | yes | 1 | 4 |
| 16 | 4 | no | 0 | 4 |
| 8 | 4 | no | 0 | 4 |
| 4 | 4 | yes | 1 | 0 |
| 2 | 0 | no | 0 | 0 |
| 1 | 0 | no | 0 | 0 |
Então 100 = 01100100: 64 + 32 + 4 = 100. Zeros à esquerda não mudam nada, portanto 01100100 e 1100100 são o mesmo número.
Um segundo método: divida por 2 repetidamente e leia os restos do último ao primeiro. 100 ÷ 2 = 50 resto 0; 50 ÷ 2 = 25 resto 0; 25 ÷ 2 = 12 resto 1; 12 ÷ 2 = 6 resto 0; 6 ÷ 2 = 3 resto 0; 3 ÷ 2 = 1 resto 1; 1 ÷ 2 = 0 resto 1. Lendo de baixo para cima: 1100100.
Na figura, a barra azul é o que sobra de 100; cada 1 arranca o seu valor posicional da barra e deixa o seu bloco vermelho.
e comparação de números binários
Um bit tem 2 padrões. Cada bit extra dobra a quantidade: cada padrão antigo uma vez com um 0 na frente e outra com um 1. Portanto n bits têm 2n padrões.
A figura os constrói: 1 bit, 2; 2 bits, 4; 3 bits, 8; 4 bits, 16. Um byte tem 28 = 256 padrões, os números inteiros de 0 a 255. O maior número de n bits é formado só por 1s: 2n − 1.
Quantos bits são necessários para dar a cada uma de 26 letras o seu próprio padrão? 24 = 16 é pouco; 25 = 32 é suficiente: 5 bits.
Comparar e ordenar. Dê aos dois números a mesma quantidade de bits (complete com zeros à esquerda) e percorra da esquerda para a direita. A primeira posição em que diferem decide: o número que tem o 1 ali é o maior, porque esse único valor posicional vale mais que todas as casas à sua direita juntas (2p > 2p − 1).
01101100 e 01011111 diferem pela primeira vez na posição 5, a casa dos 32, onde o primeiro tem o 1: 108 > 95, quaisquer que sejam os bits seguintes.
estouro e erro de arredondamento
Em muitas linguagens de programação, os inteiros são representados por uma quantidade fixa de bits. Isso limita o intervalo dos valores inteiros e as contas feitas com eles, e pode causar estouro (overflow) ou outros erros.
O contador da figura (hipotético) tem 4 bits: guarda de 0 a 15. Somar 1 a 15 (1111) exige um quinto bit; o vai-um não tem para onde ir, e o contador mostra 0. Isso é estouro.
Outras linguagens oferecem uma abstração em que o tamanho dos inteiros é limitado apenas pelo tamanho da memória do computador. A linguagem da folha de referência da prova é uma delas: seus inteiros não estouram.
Os números reais (com parte fracionária) também são armazenados em uma quantidade fixa de bits, o que limita o seu intervalo e as contas feitas com eles e pode causar erro de arredondamento e outros erros: alguns números reais são armazenados apenas de forma aproximada. Com 3 bits de fração (a figura, hipotética), existem apenas múltiplos de 1/8 = 0.125; 0.1 é armazenado como 0.125, com diferença de 0.025.
As linguagens reais usam muito mais bits, então o erro é bem menor, mas não desaparece: em muitas delas, 0.1 + 0.2 resulta em 0.30000000000000004. Os limites específicos de intervalo dos números reais estão fora do escopo do curso e da prova.
uma aproximação digital
Os dados analógicos têm valores que mudam de forma contínua, e não em intervalos discretos, ao longo do tempo: a altura e o volume de uma música, as cores de uma pintura, a posição de um velocista durante uma corrida.
Um computador guarda bits, então só consegue aproximar dados analógicos. Usar dados digitais para aproximar dados analógicos do mundo real é um exemplo de abstração.
Os dados analógicos podem ser aproximados digitalmente com grande proximidade por amostragem: medir os valores do sinal analógico em intervalos regulares, chamados de amostras. Cada amostra é medida para se descobrir os bits exatos necessários para armazená-la.
A figura amostra o mesmo sinal suave duas vezes. Primeiro 8 amostras, cada uma arredondada para um de 4 níveis (2 bits): 8 × 2 = 16 bits, uma escada grosseira. Depois 16 amostras com 8 níveis (3 bits): 16 × 3 = 48 bits, e a escada acompanha a curva mais de perto (a distância média até o sinal cai 43%).
Mais amostras e mais bits por amostra dão uma aproximação melhor, e custam mais bits para armazenar ou enviar. Nenhuma quantidade finita de amostras a torna exata.
menor, e de volta exatamente
A compressão de dados pode reduzir o tamanho (o número de bits) dos dados transmitidos ou armazenados. Um algoritmo sem perdas geralmente consegue reduzi-lo e ainda garante a reconstrução completa dos dados originais.
A fileira da figura tem 20 pixels, um byte cada: 20 bytes (hipotético). A codificação por comprimento de sequência (“run-length encoding”) guarda cada sequência de uma cor como uma contagem e uma cor: 7W 4R 6W 3B, 4 sequências × 2 bytes = 8 bytes.
A decodificação escreve 7 white, 4 red, 6 white, 3 blue: exatamente a fileira original, pixel por pixel. Nada se perdeu, portanto menos bits não significa necessariamente menos informação.
A quantidade de redução de tamanho depende tanto da quantidade de redundância nos dados originais quanto do algoritmo de compressão aplicado. Sequências longas comprimem bem. Uma fileira que alterna as cores a cada pixel (WRWRWR…) tem 20 sequências de 1: codificada, ocupa 40 bytes, mais que os 20 do começo.
menor ainda, mas só uma aproximação
Um algoritmo com perdas pode reduzir bastante o número de bits armazenados ou enviados, mas permite reconstruir apenas uma aproximação do original.
Os 16 pixels da figura (brilhos hipotéticos, um byte cada) guardam apenas a média de cada par: 8 bytes, metade do tamanho. A decodificação dá a cada pixel a média do seu par: 14 dos 16 voltam diferentes, em até 10. Os fantasmas cinzentos são os originais, e nada nos 8 bytes consegue trazê-los de volta: os pares 200, 180 e 190, 190 têm ambos média 190.
Os algoritmos com perdas costumam reduzir o número de bits mais que os sem perdas. Qual escolher depende da situação:
| o que mais importa | escolha típica |
|---|---|
| qualidade, ou a capacidade de reconstruir o original exatamente (um arquivo de programa, um documento de texto) | sem perdas |
| minimizar o tamanho dos dados ou o tempo de transmissão (vídeo em streaming em uma conexão lenta) | com perdas |
padrões, e o que eles não provam
A informação é o conjunto de fatos e padrões extraídos dos dados. Os dados oferecem oportunidades de identificar tendências, estabelecer conexões e resolver problemas.
A figura mostra 24 dias hipotéticos em uma cidade de praia: sorvetes vendidos contra casos de queimadura de sol. Quando um sobe, o outro também: uma forte correlação (o coeficiente de correlação r = 0.86; 1 seria uma reta perfeita).
Sorvete não causa queimadura de sol. Pinte os dias pela temperatura e o motivo aparece: os 7 dias quentes (vermelhos, 27 °C ou mais) trazem mais sorvete e mais sol. Uma correlação encontrada nos dados não indica necessariamente que existe uma relação de causa e efeito; é preciso mais pesquisa para entender a natureza exata da relação.
Aqui, só os registros de vendas não poderiam mostrar isso. Muitas vezes, uma única fonte não contém os dados necessários para chegar a uma conclusão, e dados de várias fontes (vendas, atendimentos em postos de saúde, registros do tempo) precisam ser combinados.
dados sobre dados
Os metadados são dados sobre dados. A foto é o dado; seus metadados podem incluir a data de criação, o tamanho do arquivo, as dimensões e as etiquetas.
Alterações e exclusões feitas nos metadados não mudam os dados primários. Na figura, a etiqueta “pôr do sol” é excluída; nenhum dos 64 pixels muda.
Os metadados servem para encontrar, organizar e gerenciar informações: uma biblioteca de fotos pode listar todas as fotos tiradas em 14 de junho, ou todas as marcadas com “praia”, sem olhar para um único pixel. Os metadados aumentam o uso eficaz dos dados ao fornecer informação adicional, e permitem que os dados sejam estruturados e organizados.
Na prova, um cenário apresenta os dados e os metadados coletados e pergunta o que se pode descobrir. Pergunte o que cada campo registra. Uma biblioteca com apenas datas e etiquetas consegue responder “quantas fotos foram tiradas em junho?”, mas não “onde esta foto foi tirada?”: nenhum campo registra um lugar.
uniformes, sem mudar o significado
Os conjuntos de dados trazem desafios, seja qual for o tamanho: a necessidade de limpar os dados, dados incompletos, dados inválidos e a necessidade de combinar fontes de dados. A capacidade de processar dados depende das capacidades dos usuários e de suas ferramentas.
Dependendo de como os dados foram coletados, eles podem não ser uniformes. Quando os usuários digitam em um campo aberto, a maneira de abreviar, escrever e usar maiúsculas varia de usuário para usuário. O formulário de inscrição da figura (hipotético) tem 7 grafias diferentes de 3 cidades.
A limpeza torna os dados uniformes sem mudar o seu significado, substituindo todas as abreviações, grafias e usos de maiúsculas equivalentes pela mesma palavra: 4 entradas são reescritas, e 7 grafias viram 3. Agora um programa que conta inscrições por cidade conta corretamente.
A limpeza não consegue inventar o que falta. Uma linha não tem idade (incompleta) e outra informa −4 (inválida); elas são sinalizadas, para serem verificadas ou deixadas de fora da análise, e não adivinhadas.
mais dados não são dados melhores
Os problemas de viés costumam ser criados pelo tipo ou pela fonte dos dados coletados. O viés não é eliminado simplesmente coletando mais dados.
A pesquisa da figura (hipotética) só alcança o lado esquerdo da população, digamos, quem lê um determinado site. Na população inteira, 41% têm a opinião vermelha. Depois de 30 respostas, a pesquisa diz 80%; depois de 60, 78%. O dobro de respostas, o mesmo retrato errado, porque todas as respostas vêm da mesma fonte não representativa.
O tamanho ainda importa: o tamanho de um conjunto de dados afeta a quantidade de informação que se pode extrair dele. Mas conjuntos de dados grandes são difíceis de processar em um único computador e podem exigir sistemas paralelos, muitos processadores trabalhando ao mesmo tempo em partes dos dados.
A escalabilidade dos sistemas é uma consideração importante ao trabalhar com conjuntos de dados, pois a capacidade computacional de um sistema afeta como os conjuntos de dados podem ser processados e armazenados.
programas que processam listas
Os programas podem ser usados para processar dados e obter informação. As ferramentas de busca são úteis para encontrar informação com eficiência, e os sistemas de filtragem de dados são ferramentas importantes para encontrar informação e reconhecer padrões nos dados.
A filtragem mantém apenas os elementos que atendem a uma condição, como manter só os números positivos de uma lista, ou só os estudantes que se inscreveram na banda:
data ← [4, -2, 7, 0, -5, 3] positives ← [] FOR EACH n IN data { IF(n > 0) { APPEND(positives, n) } } A figura executa o código com a linha em execução em vermelho. Cada n é testado; só os que têm n > 0 são acrescentados. positives termina como [4, 7, 3]; o 0 não é mantido, porque 0 > 0 é falso.
A transformação muda cada elemento, como dobrar todos os elementos de uma lista, ou acrescentar o e-mail do responsável a cada registro de estudante. Com doubled ← [] antes:
FOR EACH n IN data { APPEND(doubled, 2 * n) } doubled termina como [8, −4, 14, 0, −10, 6]. Entender algo novo pode vir de traduzir e transformar dados, e padrões podem surgir quando os dados são transformados por programas. Quem programa também usa programas para filtrar e limpar dados.
um número a partir de muitos, e um gráfico
Combinar ou comparar dados reduz muitos valores a uma resposta: somar uma lista de números, ou encontrar o estudante com a maior média. A visualização mostra um conjunto de dados como um gráfico ou outra representação visual.
Um clube registra as inscrições de 6 semanas (hipotético): signups ← [12, 18, 9, 22, 15, 20].
total ← 0 most ← signups[1] FOR EACH n IN signups { total ← total + n IF(n > most) { most ← n } } DISPLAY(total) DISPLAY(most) Ele exibe 96 22: 6 semanas, 96 inscrições no total, 22 na melhor semana. most começa em signups[1], o primeiro valor, e não em 0, de modo que continuaria funcionando mesmo que todos os valores fossem negativos. Enquanto roda, a figura desenha cada semana como uma barra: o gráfico se forma à medida que os dados são lidos.
Tabelas, diagramas, texto e outras ferramentas visuais podem ser usados para comunicar o entendimento e o conhecimento obtidos a partir dos dados. Programas como as planilhas ajudam a organizar e encontrar tendências nas informações com eficiência.
Os programas são usados de modo iterativo e interativo: veja o gráfico, faça uma nova pergunta, filtre ou transforme de novo. Combinar fontes de dados, agrupar dados (“clustering”, reunir itens parecidos) e classificar dados (separar itens em categorias) fazem parte do uso de programas para obter entendimento e conhecimento a partir dos dados.