INFORMAÇÃO E VALOR

Introdução às Estruturas de Dados

Um computador é uma máquina que manipula informações. O estudo da

ciência da computação inclui o exame da organização, manipulação e utilização

destas informações num computador. Conseqüentemente, é muito

importante para um estudante da ciência da computação entender os conceitos

de organização e manipulação de informações para continuar o estudo

do campo.

1.1 INFORMAÇÕES E SIGNIFICADO

Se a ciência da computação é fundamentalmente o estudo da informação, a

primeira pergunta que surge é: o que significa a informação? Infelizmente,

embora o conceito de informação seja a base do campo inteiro, essa pergunta

não pode ser respondida com exatidão. Por um lado, o conceito de informação

na ciência da computação é semelhante aos conceitos de ponto, linha e plano,

na geometria: todos eles são termos indefinidos sobre os quais podem ser

feitas afirmações, mas eles podem ser explicados em termos de conceitos

elementares.

1

2 Estruturas de Dados Usando C Cap. 1

Na geometria, é possível discutir sobre o tamanho de uma linha

independentemente do fato de o conceito de uma linha ser ele mesmo

indefinido. O tamanho de uma linha é uma medida de quantidade. De modo

semelhante, na ciência da computação, podemos avaliar quantidades de

informações. A unidade básica da informação é o bit, cujo valor compreende

uma entre duas possibilidades mutuamente exclusivas. Por exemplo, se um

interruptor de luz pode estar em uma das duas posições, mas não em ambas

simultaneamente, o fato de ele estar na posição de "ligado" ou na posição de

"desligado" é um bit de informação. Se um dispositivo pode estar em mais de dois

estados possíveis, o fato de ele estar em determinado estado representa mais de

um bit de informação. Por exemplo, se um dial tem oito posições possíveis, o fato

de ele estar na posição 4 exclui sete outras possibilidades, enquanto o fato de um

interruptor estar ligado exclui somente outra possibilidade.

Você pode visualizar esse fenômeno sob outro prisma. Vamos supor

que tivéssemos chaves de duas alternativas, mas pudéssemos usar quantas

delas precisássemos. Quantas chaves desse tipo seriam necessárias para

representar um dial com oito posições? Evidentemente, uma chave só pode

representar duas posições (Figura 1.1.1a). Duas chaves podem representar

quatro posições diferentes (Figura 1.1.1b) e são necessárias três chaves para

representar oito posições diferentes (Figura 1.1.1c). Em geral, n chaves

podem representar 2n possibilidades diferentes.

Os dígitos binários 0 e 1 são usados para representar os dois possíveis

estados de determinado bit (na realidade, a palavra "bit" é uma contração

das palavras "binary digit"). Dados n bits, uma string de n ls e 0s é usada

para representar seus valores. Por exemplo, a string 101011 representa seis

chaves, estando a primeira delas "ativada" (1), a segunda "desativada" (0),

a terceira ativada, a quarta desativada, a quinta e a sexta ativadas.

Verificamos que são suficientes três bits para representar oito

possibilidades. As oito possíveis configurações desses três bits (000, 001, 010,

011, 100, 101, 110 e 111) podem ser usadas para representar os inteiros de

0 a 7. Entretanto, não há nada nas definições desses bits que implique

intrinsecamente que determinada definição representa determinado inteiro.

Qualquer atribuição de valores inteiros às definições de bits é válida desde

que não sejam atribuídos dois inteiros à mesma definição de bits. Assim que

ocorrer uma atribuição desse tipo, determinada definição de bit poderá ser

interpretada com ambigüidade como um inteiro específico. Examinemos

vários métodos amplamente usados para interpretar definições de bits como

inteiros.

Cap. 1 Introdução às estruturas de dados 3

(c) Três chaves (oito possibilidades).

Figura 1.1.1

Chave 1

Desligado

Ligado

(a) Uma chave (duas possibilidades).

Chave 1 Chave 2

Desligado Desligado

Desligado Ligado

Ligado Desligado

Desligado Ligado

(b) Duas chaves (quatro possibilidades).

Chave 1 Chave 2 Chave 3

Desligado Desligado Desligado

Desligado Desligado Ligado

Desligado

Desligado