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 utili-zação destas informações num computador. Conseqüentemente, é muito

importante para um estudante da ciência da computação entender os con-ceitos de organização e manipulação de informações para continuar o estudo

do campo.

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.

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