ANALISE DE ALGORITMO

Prévia do material em texto

Aula 1
Professor Ms Bruno Rocha
Recife, fevereiro 2019.1
(BV) ANÁLISE DE ALGORITMOS- CCO 4 NA
Apresentação
● Bruno do S. Rocha
● Mestre em engenharia de software (CESAR.EDU)
● Graduado em sistemas de informação (FIR)
● 15 anos de experiência em projetos de software
● Entusiasta da tecnologia da informação em saúde
Agenda
● Análise de algoritmos
● Conceitos
● Custo de um algoritmo
Análise de 
algoritmos
● Analisar o funcionamento de um algoritmo
● Calcular o custo de um algoritmo
● Escolher o algoritmo mais adequado para determinada classe de problemas
Objetivos macro
● Carga horária: 33h
● Prova
● Lista de exercícios
Aulas e avaliações
CORMEN, Thomas H., Algoritmos. Rio de Janeiro: Elsevier, 2012. 
 
TOSCANI, Laira Vieira., Complexidade de Algoritmos. Porto Alegre, 
Bookman, 2012. 3a ed. 
 
DOBRUSHKIN, Vladimir A., Métodos para Análise de Algoritmos. Rio de 
Janeiro: LTC, 2012. 
Bibliografia básica
DASGUPTA, Sanjoy, Algoritmos. Porto Alegre: AMGH, 2010. 
 
ASCENCIO, Ana F. Gomes, Estruturas de Dados: algoritmos, análise da 
complexidade e implementações em Java e C/C++. São Paulo: Pearson 
Prentice Hall, 2010. 
 
MENEZES, Paulo F. B., Linguagens Formais e Autômatos. Porto Alegre, 
Grupo A, 2011. 
 
TAMASSIA, Roberto; GOODRICH, Michael T., Estruturas de Dados e 
Algoritmos em Java. Porto Alegre: Grupo A, 2011. 
 
SZWARCFITER, Jayme Luiz, Estruturas de dados e seus algoritmos. Rio de 
Janeiro: LTC, 2015. 
Bibliografia complementar
Conceitos
➢ Conjunto das regras e procedimentos lógicos bem definidos que levam à 
solução de um problema em um número finito de etapas.
Algoritmo
Problema e instância
Um problema é definido por:
● Descrição dos parâmetros (entrada e saída)
● Descrição das propriedades que a resposta deve satisfazer
Uma instância de um problema é obtida quando fixamos valores para todos os parâmetros 
do problema.
Problema e instância
Problema: Ordenar uma sequência a1, a2, ..., an de maneira crescente
Entrada: a1, a2, …, an
Saída: a’1, a’2, …, a’n
Propriedades: a’1, a’2, …, a’n é uma permutação de a1, a2, …, an | a’1 <= a’2 <= … <= a’n
Instância: 10 20 5 40 4
 50 30 2 35 1
Corretude do algoritmo
O algoritmo é correto se, para toda instância de entrada, termina e produz uma saída que 
satisfaz às propriedades do problema.
➢ Para algoritmos iterativos, utiliza-se a técnica dos invariantes do laço
➢ Para algoritmos recursivos, a indução matemática no tamanho das instâncias
Corretude do algoritmo
Invariante de laço
O invariante de laço pode ser definido como uma relação entre as variáveis de um algoritmo (programa) 
que é verdadeira nas seguintes condições:
● antes do início do laço;
● durante a manutenção do laço;
● na saída do laço.
Um laço está correto se as seguintes 5 condições são satisfeitas:
● Início: O invariante é verdadeiro antes de entrar no laço.
● Invariância: O corpo do laço preserva o invariante.
● Progresso: O corpo do laço diminui a variante.
● Limitação: Quando a variante atinge certo valor, a guarda se torna falsa.
● Saída: A negação da guarda e o invariante descrevem o objetivo do laço.
Corretude do algoritmo
Indução matemática
A indução matemática é útil para provar asserções sobre a corretude e a eficiência de algoritmos, pois 
podemos inferir uma lei geral a partir de instâncias particulares.
Seja T um teorema que possua como parâmetro um número natural n. Para provarmos que T é verdadeiro 
para todos os possíveis valores de n, provamos que:
Base: T é válido para n = 1; 
Passo Indutivo: Para todo n > 1, se T é válido para n, então T é válido para n + 1.
Corretude do algoritmo
Indução matemática
 maxReg(A,n)
1. se n=1
2. então devolta A[1]
3. senão 
4. x = maxReg(A, n-1)
5. se x > A[n]
6. então devolva x
7. senão devolva A[n]
➢ Se n=1, o algoritmo devolve a resposta correta.
➢ Pode-se supor, por hipótese de indução, que para n >= 2 maxReg(A, n-1) produz o resultado 
esperado.
➢ Logo, no início da linha 5, x é o máximo dos elementos de A[1..n-1]. Considerando isso, as linhas 5 a 
7 calculam corretamente o máximo de A[1..n].
Custo de um 
algoritmo
Custo de um algoritmo
É fundamental que um programa produza a solução com dispêndio de tempo e de memória 
razoáveis. Daí se depreende a importância de projeto e análise de algoritmos.
A tabela abaixo mostra o desempenho desses dois algoritmos que calculam o determinante 
de uma matriz nxn, considerando tempos de operações de um computador real.
Como calcular o custo de um algoritmo?
➢ Análise empírica
➢ Análise teórica
Custo de um algoritmo
De maneira geral, deve-se contar:
➢ Quantidade de atribuições
➢ Quantidade de comparações
Custo de um algoritmo
Exemplo 1
int fatorial (int n){
int i, fat = 1;
for (i=1; i<=n; i++)
fat *= i;
return fat;
}
Custo de um algoritmo
Custo de um algoritmo
i = 1, 2, …, n+1
Resposta:
C(n)=1+2n+2+n+1 
C(n)=3n+4
Exemplo 1
int fatorial (int n){ //--> 0
int i, fat = 1; //--> 1
for (i=1; i<=n; i++) //--> 2(n+1)=2n+2
fat *= i; //--> n
return fat; //--> custo 1
}
Exemplo 2
int calculo(int [][] mat){
int i, j;
long temp = 0; 
for (i=0; i<mat.length; i++) 
for (i=0; i<mat.length; i++)
temp += mat[i][j];
return temp;
}
Custo de um algoritmo
Custo de um algoritmo
i = 0, 1, …, n 
j = 0, 1, …, n
Resposta:
C(n)=1+2n+2+2n²+2n+n²+1 
C(n)=3n²+4n+4
Exemplo 2
int calculo(int [][] mat){ //--> 0
int i, j;
long temp = 0; //--> 1
for (i=0; i<mat.length; i++) //--> 2(n+1)=2n+2
for (i=0; i<mat.length; i++) //--> n.2(n+1)=2n²+2n
temp += mat[i][j]; //--> n.n=n²
return temp; //--> 1
}
Exemplo 3
Custo de um algoritmo
void vetMaior(int[] vet, int [][] mat){
int i,j;
for (i=0; i<mat.length; i++){
vet[] = mat[i][0];
for (j=1; j<mat[i].length; j++){
if (mat[i][j] > vet[i]){
vet[i] = mat[i][j];
}
}
}
}
Exemplo 3
Custo de um algoritmo
i = 0, 1, …, n 
j = 1, 2, …, n
Melhor caso:
C(n)=2n+2+n+2n²+n²-n
C(n)=3n²+2n+2
void vetMaior(int[] vet, int [][] mat){
int i,j;
for (i=0; i<mat.length; i++){ //2n+2
vet[] = mat[i][0]; //n
for (j=1; j<mat[i].length; j++){ //2n²
if (mat[i][j] > vet[i]){ //n(n-1)
vet[i] = mat[i][j]; //n(n-1)
}
}
}
}
Pior caso:
C(n)=2n+2+n+2n²+n²-n+n²-n
C(n)=4n²+n+2
Contato
E-mail: brunodsr@hotmail.com
WhatsApp: (81) 9.8805-9960
mailto:brunodsr@hotmail.com