Aula Complexidade Ziviane

∗
Projeto de Algoritmos

Introdução

Última alteração: 30 de Agosto de 2010

∗ Transparências

elaboradas por Charles Ornelas Almeida, Israel Guerra e Nivio Ziviani

Projeto de Algoritmos – Cap.1 Introdução

Conteúdo do Capítulo
1.1 Algoritmos, Estruturas de Dados e Programas
1.2 Tipos de Dados e Tipos Abstratos de Dados
1.3 Medida do tempo de Execução de um Programa
1.3.1 Comportamento Assintótico de Funções
1.3.2 Classes de Comportamento Assintótico
1.4 Técnicas de Análise de Algoritmos
1.5 Pascal

1

Projeto de Algoritmos – Cap.1 Introdução – Seção 1.1

Algoritmos, Estruturas de Dados e Programas
• Os algoritmos fazem parte do dia-a-dia das pessoas. Exemplos de algoritmos: – instruções para o uso de medicamentos,
– indicações de como montar um aparelho,
– uma receita de culinária.
• Sequência de ações executáveis para a obtenção de uma solução para um determinado tipo de problema.
• Segundo Dijkstra, um algoritmo corresponde a uma descrição de um padrão de comportamento, expresso em termos de um conjunto finito de ações.
– Executando a operação a + b percebemos um padrão de comportamento, mesmo que a operação seja realizada para valores diferentes de a e b.

2

Projeto de Algoritmos – Cap.1 Introdução – Seção 1.1

Estruturas de dados
• 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 mediante a definição de um conjunto de dados que representa a situação real.
• A seguir, deve ser escolhida a forma de representar esses dados.

3

Projeto de Algoritmos – Cap.1 Introdução – Seção 1.1

Escolha da Representação dos Dados
• A escolha da representação dos dados é determinada, entre outras, pelas operações a serem realizadas