Algoritmos e Estrutura de Dados

Quando escrevemos um programa, geralmente estamos implementando um método que foi criado anteriormente para resolver algum problema. Este método é frequentemente independente da linguagem de programação específica que está sendo usada — é provável que seja igualmente apropriado para muitos computadores e muitas linguagens de programação. É o método, e não o próprio programa de computador, que especifica as etapas que podemos seguir para resolver o problema. O termo algoritmo é usado em computação para descrever um método de solução de problemas adequado para implementação em um programa. Algoritmos são a "matéria-prima" da computação.

Podemos definir um algoritmo descrevendo um procedimento para resolver um problema em uma linguagem natural ou escrevendo um programa de computador que implementa o procedimento, como mostrado abaixo no Algoritmo de Euclides para encontrar o máximo divisor comum de dois números (uma variante do qual foi criada há mais de 2.300 anos).

int gcd(int p, int q) {
    if (q == 0) return p;
    int r = p % q;
    return gcd(q, r);
}

Após conhecer um exemplo comum de algoritmo, torna-se mais fácil compreender a sua definição formal:

A maioria dos algoritmos envolve a organização dos dados envolvidos na computação. Tal organização é chamada de estruturas de dados, que também são objetos centrais de estudo na computação. Algoritmos e estruturas de dados andam de mãos dadas. Nesta disciplina, consideramos que as estruturas de dados existem como subprodutos ou produtos finais de algoritmos e que, portanto, devemos estudá-las para compreender os algoritmos e vice-versa. Algoritmos simples podem dar origem a estruturas de dados complicadas e, inversamente, algoritmos complicados podem usar estruturas de dados simples.

Por que estudar Algoritmos e Eficiência?

Quando usamos um computador para nos ajudar a resolver um problema, normalmente nos deparamos com uma série de abordagens possíveis. Para pequenos problemas, pouco importa qual abordagem usamos, desde que tenhamos uma que resolva o problema corretamente. No entanto, para grandes problemas (ou aplicações em que precisamos resolver um grande número de pequenos problemas), nos motivamos rapidamente a desenvolver métodos que usem o tempo e o espaço com eficiência.

Suponha que os computadores fossem infinitamente rápidos e que a memória do computador fosse gratuita. Teríamos alguma razão para estudar algoritmos? A resposta é sim, ainda que apenas porque gostaríamos de demonstrar que o método de solução termina e o faz com a resposta correta.

Se os computadores fossem infinitamente rápidos, qualquer método correto para resolver um problema serviria. É provável que quiséssemos que sua implementação estivesse dentro dos limites da boa prática de engenharia de software (isto é, que ela fosse bem documentada e projetada) mas, na maior parte das vezes, utilizamos o método que fosse mais fácil e rápido de implementar.

É claro que os computadores podem ser rápidos, mas eles não são infinitamente rápidos. A memória pode ser de baixo custo, mas não é gratuita. Assim, o tempo de computação é um recurso limitado, bem como o espaço na memória. Esses recursos devem ser usados com sensatez e algoritmos eficientes em termos de tempo ou espaço nos ajudarão a usá-los.

A escolha do melhor algoritmo e estrutura de dados para uma tarefa específica pode ser um processo complicado, talvez envolvendo análises matemáticas sofisticadas. O ramo da ciência da computação que compreende o estudo de tais questões é denominado análise de algoritmos. Muitos dos algoritmos que estudaremos na disciplina demonstraram, por meio de análises, um excelente desempenho teórico; outros simplesmente funcionam bem com a experiência. Nosso objetivo principal é aprender estruturas de dados elementares para tarefas importantes, mas também iremos prestar muita atenção ao desempenho comparativo dos métodos. Não devemos usar um algoritmo ou estrutura de dados sem ter uma ideia de quais recursos ele pode consumir.

Estruturas de Dados Elementares

Arrays

Um array é uma coleção de elementos de dados semelhantes e de mesmo tipo de dados. Os elementos de um array são armazenados em locais de memória contíguos e são referenciados por um índice.

Em C, os arrays são declarados usando a seguinte sintaxe:

tipo nome[tamanho];

Exemplo:

double notas[10];

Os arrays geralmente são usados quando queremos armazenar uma grande quantidade de tipos de dados semelhantes. Contudo, eles possuem as seguintes limitações:

• Tamanho fixo: Não é possível redimensioná-los facilmente em tempo de execução.
• Locais contíguos de memória: Exigem um bloco contínuo que pode não estar sempre disponível na memória RAM.
• Inserção e remoção dispendiosas: Exigem o deslocamento (shift) de múltiplos elementos de suas posições.

Essas limitações podem ser resolvidas usando listas encadeadas.

Listas Encadeadas

Uma lista encadeada é uma estrutura de dados dinâmica e muito flexível na qual os elementos (chamados de nós) formam uma lista sequencial. Em contraste com arrays estáticos, o programador não precisa se preocupar antecipadamente com quantos elementos serão armazenados. Este recurso permite escrever programas robustos e de menor manutenção.

Em uma lista encadeada, cada nó recebe espaço alocado dinamicamente à medida que é adicionado. Cada nó contém:

1. O valor/informação a ser armazenada;
2. Um ponteiro (link) para o próximo nó da lista.

O último nó da lista contém um ponteiro NULL para indicar o fim da sequência.

A figura abaixo mostra uma lista encadeada com sete nós.

Pilhas

Uma pilha é uma estrutura de dados linear em que a inserção e a exclusão de elementos são feitas em apenas uma extremidade, conhecida como o topo da pilha.

A pilha é chamada de estrutura LIFO (Last-In, First-Out — Último a entrar, primeiro a sair) porque o último elemento adicionado é obrigatoriamente o primeiro a ser removido. Na memória do computador, pilhas podem ser implementadas utilizando arrays ou listas encadeadas.

Filas

Uma fila é uma estrutura de dados do tipo FIFO (First-In, First-Out — Primeiro a entrar, primeiro a sair), na qual o primeiro elemento inserido é o primeiro a ser retirado.

Os elementos em uma fila são adicionados em uma extremidade (fim/rear) e removidos na outra (início/front). Assim como as pilhas, as filas podem ser implementadas utilizando arrays ou listas encadeadas.

Árvores

Uma árvore é uma estrutura de dados não linear que consiste em uma coleção de nós organizados em uma estrutura hierárquica. Um dos nós é designado como o nó raiz e os nós restantes são particionados em subárvores.

A forma mais simples é a árvore binária. Uma árvore binária consiste em um nó raiz e duas subárvores (esquerda e direita), onde ambas também são árvores binárias. Cada nó contém:

• Um elemento de dados (informação);
• Um ponteiro para a subárvore esquerda;
• Um ponteiro para a subárvore direita.

A figura abaixo mostra uma árvore binária, onde é o nó raiz e e são as subárvores esquerda e direita de .

Referências

• Sedgewick, R.; Wayne, K. Algorithms. 4th ed. Addison-Wesley, 2011.
• Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. Introduction to Algorithms. 3rd ed. MIT Press, 2001.