Algoritmos, estruturas de dados e programas

apítulo 1

Introdução

1.1 Algoritmos, Estruturas de Dados e Programas

Os algoritmos fazem parte do dia-a-dia das pessoas. As instruções para o uso

de medicamentos, as indicações de como montar um aparelho qualquer, uma

receita de culinária são alguns exemplos de algoritmos. Um algoritmo pode

ser visto como uma seqüência de ações executáveis para a obtenção de uma

solução para um determinado tipo de problema. Segundo Dijkstra (1971) um

algoritmo corresponde a uma descrição de um padrão de comportamento,

expresso em termos de um conjunto finito de ações. Ao executarmos a

operação a + b percebemos um mesmo padrão de comportamento, mesmo

que a operação seja realizada para valores diferentes de a e b.

Estruturas de dados e algoritmos estão intimamente ligados. Não se

pode estudar estruturas de dados sem considerar os algoritmos associados a

elas, assim como a escolha dos algoritmos em geral depende da representação

e da estrutura dos dados. Para resolver um problema é necessário

escolher uma abstração da realidade, em geral através da definição de um

conjunto de dados que representa a situação real. A seguir deve ser escolhida

a forma de representar estes dados.

A escolha da representação dos dados é determinada, entre outras, pelas

operações a serem realizadas sobre os dados. Considere a operação de adição.

Para pequenos números uma boa representação é através de barras

verticais, caso em que a operação de adição é bastante simples. Já a

representação através de dígitos decimais requer regras relativamente complicadas,

as quais devem ser memorizadas. Entretanto, a situação se inverte

quando consideramos a adição de grandes números, sendo mais fácil a representação

por dígitos decimais por causa do princípio baseado no peso relativo

da posição de cada dígito.

1

2 CAPíTULO 1. INTRODUÇÃO

Programar é basicamente estruturar dados e construir algoritmos. De

acordo com Wirth (1976, p.XII), programas são formulações concretas de

algoritmos abstratos, baseados em representações e estruturas específicas de

dados. Em outras palavras, programas representam uma classe especial de

algoritmos capazes de serem seguidos por computadores.

Entretanto, um computador só é capaz de seguir programas em linguagem

de máquina, que correspondem a uma seqüência de instruções obscuras

e desconfortáveis. Para contornar tal problema é necessário construir linguagens

mais adequadas para facilitar a tarefa de programar um computador.

Segundo Dijkstra (1976), uma linguagem de programação é uma técnica de

notação para programar, com a intenção de servir de veículo tanto para a

expressão do raciocínio algorítmico quanto para a execução automática de

um algoritmo por um computador.

1.2 Tipos de Dados e Tipos Abstratos de Dados

Em linguagens de programação é importante classificar constantes, variáveis,

expressões e funções de acordo com certas características, as quais indicam o

seu tipo de dados. Este tipo deve caracterizar o conjunto de valores a que

uma constante pertence, ou que podem ser assumidos por uma variável ou

expressão, ou que podem ser gerados por uma função (Wirth, 1976, pp.4–40).

Tipos simples de dados são grupos de valores indivisíveis, como os tipos

básicos integer, boolean, char, e real do Pascal. Por exemplo, uma variável

do tipo boolean pode assumir ou o valor verdadeiro ou o valor falso, e nenhum

outro valor. Os tipos estruturados em geral definem uma coleção de valores

simples, ou um agregado de valores de tipos diferentes. A linguagem Pascal

oferece uma grande variedade de tipos de dados, como será mostrado na

Seção 1.5.

Um tipo abstrato de dados pode ser visto como um modelo matemático,

acompanhado das operações definidas sobre o modelo. 0 conjunto

dos inteiros acompanhado das operações de adição, subtração e multiplicação

forma um exemplo de um tipo abstrato de dados. Aho, Hoperoft e Ullman (

1983), utilizam extensivamente tipos abstratos de dados como base para o

projeto de algoritmos. Nestes casos a implementação do algoritmo em uma

linguagem de programação específica exige que se encontre alguma forma

de representar o tipo abstrato de dados, em termos dos tipos de dados e dos

operadores suportados pela linguagem considerada. A representação do

modelo matemático por trás do tipo abstrato de dados é realizada através de

uma estrutura de dados.

Tipos abstratos de dados