Análise de Algoritmos1 Viviane Cristina Dias Fev/2003

Análise de Algoritmos 1

Análise de Algoritmos

Viviane Cristina Dias

Fev/2003


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.


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 = array [1..80] of char;Type matriz = array [1..5,1..5] of real;Type coluna = array [1..3] of real;Var x: coluna As atribuições x[1]:= 0.75

x[2]:= 0.85x[1]:= 1.5


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 = recordPrimeiroNome: 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;


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.


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.


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



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.


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

corretamente.

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.

M1

M2

M3



Testes de IntegraçãoObjetivo verificar o funcionamento harmônico dos

módulos e garantir que a comunicação entre eles se dê conforme o projetado.

Testes de ValidaçãoNesta etapa que dados conhecidos do problema original são submetidos à avaliação e certificados ao atingir soluções esperadas, previamente estabelecidas.

M1 Teste M1M2

M3



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.



Estruturas

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.

EstruturasDe

Dados

Algoritmos


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

Algortimo2

Algortimo1


AlgoritmosRecursivos


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


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...


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) Para n > 2

Considerando: F(1) =2 para n > 1

F(n) = 2*F(n-1)

Teremos:


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;

elseBegin

i:=2;valorcorrente :=2;While i <= n doBegin

valorcorrente := 2*valorcorrente;i:= i+1;

end;S := valorcorrente;

end;end.


Recursão e Relação de Recorrência - PascalEscrever 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;


Recursão e Relação de Recorrência - CEscrever 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.


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);

}}


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}

Documents

Análise de Algoritmos1 Viviane Cristina Dias Fev/2003