streams

Estruturas de Dados e Algoritmos

2001, Claudio Esperança

1

Introdução
 O que é um algoritmo?
• Processo sistemático para computar um resultado a partir de dados de entrada
 O que são estruturas de dados?
• Maneira de organizar dados e operar sobre eles
 Algoritmos + estruturas de dados = programas
• Um programa é a expressão em linguagem formal
(inteligível por um computador) de um algoritmo.

2

Projeto de Algoritmos
 Entender a entrada
 Entender o que se espera na saída
 Repetir:
• Bolar um método,
• Se o método é correto, então
– Analisar a complexidade do método,
– Se complexidade é aceitável, terminar.
 Implementar (programar)

3

Projeto de Estruturas de Dados




Uma modelagem abstrata dos objetos a serem manipulados e das operações sobre eles
• Tipo de Dados Abstrato (“Abstract Data Type”)
• Ex.: Uma “pilha”, com operações “push”, “pop” etc.
Uma modelagem concreta do TDA, isto é, como armazenar o TDA em memória/disco e que algoritmos devem ser usados para implementar as operações
• Ex.: Pilha armazenada como lista encadeada ou vetor ...

4

Projeto versus Implementação
 Um bom projeto leva a uma boa implementação
• Todas as idéias principais já foram estudadas
• A tradução do projeto em programa é quase mecânica
 (ou não)
• Programar é uma arte
• Um algoritmo inferior bem programado pode ser mais útil que um algoritmo eficiente mal programado
• Há considerações práticas quase tão importantes quanto um bom projeto, como por exemplo,
– Interfaces
– Manutenibilidade
– Documentação
5

Algoritmos e Complexidade
 Eficiência de um algoritmo
• Complexidade de tempo: quanto “tempo” é necessário para computar o resultado para uma instância do problema de tamanho n
– Pior caso: Considera-se a instância que faz o algoritmo funcionar mais lentamente
– Caso médio: Considera-se todas as possíveis instâncias e mede-se o tempo médio
 Eficiência de uma estrutura de dados
•