Introdução a Algoritmos

Algoritmos, Estruturas de Dados e Programas

Algoritmos

Um algoritmo é uma sequência finita de ações executadas para obter a solução de um determinado problema.

Estrutura de Dados

Uma estrutura de dados é uma forma de representar uma situação real de maneira abstrata.

Programas

Programas representam uma classe especial de algoritmos que são capazes de serem seguidos por um computador.

Tipos de Dados e Tipos Abstratos de Dados

Tipo de Dados

Tipo de dados são características que determinam o tipo de valores que uma variável, constante, expressão e função podem receber. Tipos básicos como int, char, float, boolean, são exemplos de tipo de dados.

Tipo de Abstrato de Dados

Tipo abstrato de dados pode ser considerado uma generalização de tipos primitivos de dados. Um conjunto de inteiros que realiza alguma operação matemática pode ser considerado um tipo abstrato de dados.

Medida do Tempo de Execução de um Programa

Na área de análise de algoritmos, existem dois tipos de problemas apontados por Knuth (1971):

1. Análise de um algoritmos particular. Visa descobrir o custo de usar um dado algoritmo para resolver um problema específico. Geralmente se faz uma análise do número de vezes que cada parte do algoritmo é executada e depois um estudo da quantidade de memória necessária.

2. Análise de uma classe de algoritmos. Visa descobrir o algoritmo de menor custo possível para resolver um problema em particular. Nesse caso uma família de algoritmos é investigava para determinar qual algoritmo é o melhor possível

O custo de utilização de um algoritmo pode ser medido de diversas maneiras. Porém, medir o tempo de execução de um programa em um computador real não é a mais adequada, pois o tempo de execução pode sofrer interferência de outros fatores, como o compilador, a concorrência de outros processos em execução, etc.

Para medir o custo de execução de um algoritmo de forma adequada, utiliza-se um modelo matemático. Para isso é comum definir uma função de complexidade f, onde f(n) é a medida de tempo necessário para executar um algoritmo para um problema de tamanho n.

Continua....

Referências

• ZIVIANI, Nivio. Projeto de algoritmos : com implementações em Pascal e C. 3. ed. rev. e ampl. São Paulo: Cengage Learning, 2011.