Análise de Algoritmos
Viviane Cristina Dias
Fev/2003
Análise de Algoritmos
1
Bibliografia
Bibliografia Básica:
ZIVIANI, Nívio, Projeto de Algoritmos com Implementação em Pascal e C, Livraria Pioneira.
Ed. (pioneira Informática), São Paulo, SP, 1993.
WIRTH, N. Algoritmos e Estruturas de Dados, Prentice Hall, 1989.
KNUTH D. E., The Art of Computer Programming, Vol 1 e 3, Addison-Wesley, 1973.
LAGES, N. A. Castilho, Algoritmos e Estruturas de Dados, LTC, 1994
PEREIRA, S. Lago, Estruturas de Dados Fundamentais Conceitos e Aplicações, São Paulo,
Érica, 1996,
SZWARCFITER, J. Luiz, Estruturas de Dados e seus Algoritmos, 2a. edição, LTC.
Bibliografia Complementar:
VILLAS, Marcos Vianna e Outros, Estrutura de Dados, Editora Campos, 1993.
MANBER Udi, Introduction to Algorithms: A Creative Approach. Addison-Wesley, Hardcover,
Published March 1989.
EDGEWICK, R., Algorithms, Addison-Wesley, 1998.
SIPSER, M. Introduction to the Theory of Compution. PWS Publishing Co., 1996.
Análise de Algoritmos
2
Revisão - Pascal
Variáveis:
Todo programa usa a memória do computador para armazenar
os dados com que lida;
Nome,Tipo;
Integer, Char, Double, String, Boolean e muitos outros;
Tipos estruturados definem uma coleção de valores
simples, ou um agregado de valores de tipos diferentes. Por
exemplo: um tipo estruturado arranjo:
Type cartão
Type matriz
Type coluna
Var x: coluna
= array [1..80] of char;
= array [1..5,1..5] of real;
= array [1..3] of real;
As atribuições x[1]:= 0.75
x[2]:= 0.85
x[1]:= 1.5
Análise de Algoritmos
3
Revisão - Pascal
Tipo estruturado registro é uma união de
valores de tipos quaisquer, cujos campos podem
ser acessados pelos seus nomes. Exemplo:
Type pessoa = record
PrimeiroNome: String[10];
Sobrenome
: Alfa;
Sexo
: (mas,fem);
End;
Declarada a variável
Var p: pessoa;
Atribuições:
p.Sobrenome
: = Duarte;
p.PrimeiroNome:
:= Marcos;
p.Sexo
:= mas;
Análise de Algoritmos
4
Revisão
Ponteiro:
Um ponteiro proporciona um modo de acesso a variáveis sem
referenciá-las diretamente.
O mecanismo usada para isto é o endereço da variável. De
fato, o endereço age como intermediário entre a variável e o
programa que a acessa.
Basicamente, um ponteiro é uma representação simbólica de
um endereço.
Uma das vantagens do uso de ponteiro é que notações de
ponteiros compilam mais rapidamente tornando o código
mais eficiente.
Análise de Algoritmos
5
Revisão
Ponteiro:
Um ponteiro proporciona um modo de acesso a variáveis sem
referenciá-las diretamente.
O mecanismo usada para isto é o endereço da variável. De
fato, o endereço age como intermediário entre a variável e o
programa que a acessa.
Basicamente, um ponteiro é uma representação simbólica de
um endereço.
Uma das vantagens do uso de ponteiro é que notações de
ponteiros compilam mais rapidamente tornando o código
mais eficiente.
Análise de Algoritmos
6
Introdução à Análise e Síntese de Algoritmos
Modularização: possibilidade de compor uma
ação a partir de outras ainda mais primitivas,
agrupando-as em unidades sintaticamente
fechadas e logicamente relacionadas, isto pode
trazer uma série de vantagens a um algoritmo:
aumentar a legibilidade, a eficiência e portabilidade;
facilitar a execução de testes e sua manutenção;
permitir o isolamento de erros e corrigi-los;
permitir
compartilhamento
de
desenvolvimento
paralelo;
Vantagens da Independência entre as partes
Análise de Algoritmos
7
Introdução à Análise e Síntese de Algoritmos
Acoplamento: Grau de interdependência das
partes; quanto menor, mais fácil manutenção.
Serve como fator de medida de qualidade.
Na prática, o ideal é que cada módulo seja
relativamente
simples,
responsável
pela
consecução de um objeto bem definido e
executado o mais independente possível de
outros módulos.
A comunicação entre módulos deve se dar
através de interfaces bem definidas, capazes de
transmitir dados de maneira eficiente, reforçando
uma boa escolha de suas definições.
Análise de Algoritmos
8
Introdução à Análise e Síntese de Algoritmos
Depuração e Validação
Não basta ao processo de desenvolvimento
apenas produzir soluções modulares. É
necessário que cada módulo funcione
M1
corretamente.
M2
M3
Depuração :Atividade de teste e verificação de um
módulo.
Os teste devem ser previstos durante a etapa de
concepção do próprio módulo e deve anteceder
a sua integração com os outros.
Análise de Algoritmos
9
Introdução à Análise e Síntese de
Algoritmos
M2
M1
Teste
M1
M3
Testes de Integração
Objetivo verificar o funcionamento harmônico dos
módulos e garantir que a comunicação entre eles
se dê conforme o projetado.
Testes de Validação
Nesta etapa que dados conhecidos do problema
original são submetidos à avaliação e
certificados ao atingir soluções esperadas,
previamente estabelecidas.
Análise de Algoritmos
10
Introdução à Análise e Síntese de Algoritmos
Testes durante o período de implantação poderão
mostrar eventuais falhas, principalmente aquelas
relacionadas com os aspectos específicos dos
equipamentos envolvidos e da comunicação com
o usuário.
Análise de Algoritmos
11
Introdução à Análise e Síntese de Algoritmos
Estruturas
Algoritmos
Estruturas
De
Dados
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.
A escolha da representação dos dados é
determinada, entre outras, pelas operações a
serem realizadas sobre os dados.
Análise de Algoritmos
12
Análise de Algoritmos
Área da computação que visa a determinar a
complexidade(custo) de um algoritmo, o que
torna possível:
Comparar algoritmos: como existem muitos
algoritmos que resolvem uma mesma classe de
problemas, através dessa medida de
complexidade podemos compara-los entre si.
Determinar se um algoritmos é “ótimo”
Algortimo1
Algortimo2
Algortimo1
Algortimo2
Análise de Algoritmos
13
Algoritmos
Recursivos
Análise de Algoritmos
14
Recursão e Relação de Recorrência
Alguma coisa é recursiva quando é definida em termos
dela própria.
Uma definição na qual o item que está sendo definido
aparece como parte da definição;
Definição indutiva ou recursiva
O que eu devo ter?
Uma Base (Casos simples do item a ser definido, são
dados explicitamente); Ponto de Partida
Um Passo Recursivo (Casos do item a ser definido
são gerados a partir de casos anteriores); Gerar
novos casos
Análise de Algoritmos
15
Recursão e Relação de Recorrência
Relação de Recorrência
Exemplo:
F(1) = 2
para n > 1
F(n) = 2*F(n-1)+1
n=1 F(1) = 2
n=2F(2) = 2*F(n-1)+12*F(2-1)+12*[F(1)]+1 2*[2]+1 = 5
n=3 F(3) = 2*F(n-1)+12*F(3-1)+1 2*F(2)+12*[5]+1 = 11
n=4 F(4) = 2*F(n-1)+12*F(4-1)+12*F(3)+12*[11]+1= 23
Logo:
2, 5, 11, 23...
Análise de Algoritmos
16
Recursão e Relação de Recorrência
Exercício:
Qual a sequência considerando:
F(1) =2
para n > 1
F(n) = 2*F(n-1)
Sequência Fibonacci
F(1) = 1
F(2) = 2
F(n) = F(n-1)+F(n-2)
Considerando:
Para n > 2
F(1) =2
para n > 1
F(n) = 2*F(n-1)
Teremos:
Análise de Algoritmos
17
Recursão e Relação de Recorrência - Pascal
Escrever um Programa que gere a Série:
Function S (Var n:integer):Integer;
Var
i,valorcorrente:Integer;
Begin
If n = 1 Then
valorcorrente := 2;
else
Begin
i:=2;
valorcorrente :=2;
While i <= n do
Begin
valorcorrente := 2*valorcorrente;
i:= i+1;
end;
S := valorcorrente;
end;
end.
Análise de Algoritmos
18
Recursão e Relação de Recorrência - Pascal
Escrever um Programa Recursivo que gere a Série:
Function S (Var n:integer):Integer;
Var
resultado:Integer;
Begin
If n = 1 Then
resultado := 2;
else
Begin
resultado:= S(n-1)*2;
end;
S := resultado;
end;
Análise de Algoritmos
19
Recursão e Relação de Recorrência - C
Escrever um Programa Recursivo que gere a Série:
Int S (Int n)
{
int resultado;
If (n == 1)
resultado = 2;
else
resultado= S(n-1)*2;
return (resultado);
}
Exercício: Fazer um algoritmo que não use recursividade
para gerar a série.
Análise de Algoritmos
20
Recursão e Relação de Recorrência - Pascal
Escrever um Programa que gere a Série:
Int S (Int n )
{
int i,valorcorrente;
If (n == 1)
valorcorrente = 2;
else
{
i = 2;
valorcorrente = 2;
While i <= n
{
valorcorrente := 2*valorcorrente;
i++;
}
S = valorcorrente;
return (S);
}
}
Análise de Algoritmos
21
Recursão e Relação de Recorrência
Um exemplo ilustrativo é o cálculo de fatorial
A função fatorial é definida como:
0! = 1
para n>0: n! = n*(n-1)!
e pode ser implementada pelo seguinte algoritmo:
função fatorial(n:inteiro): inteiro
início
se n=0 então
retorne 1
senão
retorne n*fatorial(n-1)
fim {fatorial}
Análise de Algoritmos
22
Download
