ANÁLISE E COMPLEXIDADE DE ALGORITMOSarieldias.com/material/2019-1/ACA/Aula1n.pdf · Análise e Complexidade de Algoritmos Professor Ariel da Silva Dias Introdução Professor Ariel

Análise e Complexidade de AlgoritmosProfessor Ariel da Silva DiasIntrodução

Professor Ariel da Silva Dias - www.arieldias.com

Apresentação Professor

▪ Professor Ariel Dias


Apresentação Disciplina

▪ O que veremos?

▪ www.arieldias.com

▪ BlackBoard


http://www.arieldias.com/

Apresentação

▪ Turma Noite

▪ Continuada I – 18/03 1 Ponto

▪ Continuada II – 20/05 1 Ponto

▪ Atividades 1 Ponto

▪ Regimental – 03/06 7 Pontos

▪ Total 10 Pontos


Apresentação

▪ Turma Manhã

▪ Continuada I – 20/03 1 Ponto

▪ Continuada II – 22/05 1 Ponto

▪ Atividades 1 Ponto

▪ Regimental – 05/06 7 Pontos

▪ Total 10 Pontos


Análise de Algoritmo

▪ Antes...

▪ Existe diferença entre Algoritmo, Código Fonte, Processo, Programa, Software, App?

▪ Um programa não roda...

▪ Um programa não tem performance...


Algoritmo

▪ Algoritmos são projetados para resolver problemas

▪ Problema: encontrar a melhor rota, em termos de tempo de entrega, dos produtosdas Casas Ceará em Ermelino Matarazzo;

▪ Solução: algoritmo para descoberta da melhor rota tendo como entrada os locais deentrega.

▪ Informalmente, um algoritmo é um procedimento computacional bem definidoque:▪ Recebe um conjunto de valores como entrada e

▪ Produz um conjunto de valores como saída.


Algoritmo

Segundo Dijkstra, um algoritmo corresponde a uma descrição de um padrão decomportamento, expresso em termos de um conjunto finito de ações.

Segundo Terada, um algoritmo é, em geral, uma descrição passo a passo de comoum problema é solucionável. A descrição deve ser finita, e os passos devem serbem definidos, sem ambiguidades, e executáveis computacionalmente.


Algoritmo

Consequências:

▪ Deve-se ter um repertório finito de regras

▪ Linguagem de programação;

▪ A maior parte dos algoritmos utilizam métodos de organização de dadosenvolvidos na computação▪ Estrutura de dados;


Algoritmo

Consequências:

▪ Tempo finito não é uma eternidade

▪ A maior parte das pessoas não está interessada em algoritmos que levam anos,décadas, séculos, milênios para executarem;

▪ Existem diferentes tipos de computadores▪ Logo, existem diferentes modelos computacionais.


Algoritmo – Problema x Instância

Problema: rearranjar um vetor A[1...n] em ordem crescente.

Entrada:

Saída:

Instância: O vetor é uma instância do problema de ordenação.

32 25 64 18 10 41 44 50 16 1

1 10 16 18 25 32 41 44 50 64

1 n

1 n



Todo problema computacional é uma coleção de instância. Cada instância é definida por um conjunto particular de dados.



Tamanho da instância

▪ No problema de ordenação de vetores visto anteriormente, podemos dizer que otamanho da instância é 10 e que, em geral, o tamanho de uma instância A[1...n]é n;


Projeto de Algoritmo

Projetar algoritmos implica estudar seu comportamento no tempo e no espaço:

▪ No tempo: quanto tempo vai demorar para encontrar a solução do problema

▪ No espaço: quanto de memória será necessário para encontrar a solução



Dois problemas distintos

1. Análise de um algoritmo particular

▪ Qual é o custo de usar um dado algoritmo para resolver um problema específico?

▪ Quantas vezes cada parte desse algoritmo vai ser executada?

▪ Quanto de memória será necessária?



Dois problemas distintos

2. Análise de uma classe de algoritmos

▪ Qual é o algoritmo de menor custo possível para resolver um problema específico?

▪ Isto implica investigar toda uma família de algoritmo?

▪ Para realizar esta investigação limites podem ser impostos:

▪ Exemplo: número mínimo de comparações necessárias para ordenar n números por meiode comparações sucessivas (teremos o pior e melhor caso).



Em análise de algoritmos buscamos responder a seguinte pergunta: “podemos fazer um algoritmo mais eficiente?”



Lembre-se que podemos resolver um mesmo problema de várias maneirasdiferentes, ou seja, utilizamos algoritmos diferentes para o mesmo problema.

Algoritmos diferentes para um mesmo problema, não necessariamente terão amesma eficiência!



Essas diferenças de eficiência podem ser

▪ Irrelevantes para uma instância pequena (n pequeno);

▪ Crescer proporcionalmente com o tamanho da instância (n muito grande);



▪ Podemos determinar se um algoritmo é o mais eficiente utilizando duasabordagens:

▪ Análise Empírica: comparação entre os programas;

▪ Análise Matemática: estudo das propriedades dos algoritmos;



▪ Análise Empírica

▪ Avalia o custo de um algoritmo já implementado e em execução;

▪ Logo, é analisado o programa!

▪ Considera custos não aparentes;

▪ Utilizado para comparar computadores e linguagens;

▪ Resultado pode ser injusto;



▪ Análise Matemática

▪ Permite um estudo formal do algoritmo;

▪ Considera somente os custos dominantes do algoritmo;

▪ A medição do tempo (custo) é feita de maneira independente do hardware ou dalinguagem de programação utilizada;

▪ Permite compreender o comportamento de um algoritmo à medida que a instânciado problema (conjunto de dados de entrada n) cresce.


Análise Matemática – Contando Instruções do Algoritmo

▪ Vamos contar quantas instruções simples o algoritmo executa;

▪ Tipos de instrução:▪ Atribuição de valor à uma variável;▪ Acesso ao valor de um elemento do vetor;▪ Comparação entre variáveis;▪ Incremento/decremento de variáveis;▪ Operações aritméticas básicas;

▪ Contrato inicial:▪ Vamos assumir que as instruções possuem o mesmo custo;▪ Comandos de seleção possuem custo zero;



int m = 10;

int n = 20;

int o = m + n;



int a = 10

int b = 0

if(a<8)

b = 4;

if(a>8)

b = 6;

if(a==8)

b = 3;



int a = 10

int b = 0

if(a<8)

b = 4;

else if(a>8)

b = 6;

else

b = 3;



int M = v[0];

for(i = 0; i< n; i++){

if(v[i] >= M)

M = v[i];

}



▪ Vamos ignorar por enquanto os comandos dentro do laço for;

▪ Assim, temos que o algoritmos precisa executar quantas instruções?

▪ 3 antes de iniciar o laço for e

▪ 2 ao final de cada laço for que será executado n vezes;

▪ Logo, se o laço estiver vazio, definimos uma função matemática para o cálculo do custo do algoritmo em relação ao tamanho do vetor de entrada: f(n) = 2n + 3

▪ E se considerarmos o conteúdo do laço for?



▪ PROBLEMA

▪ Algumas instruções dentro do for podem ou não serem executadas;

▪ Antes bastava saber o tamanho do vetor para definir a função de custo f(n);

▪ Agora temos que considerar o conteúdo do vetor;



▪ EXEMPLOS:▪ V1 = {1, 2, 3, 4};▪ V2 = {4, 3, 2, 1};

1. int M = v[0];

2. for(i = 0; i< n; i++){

3. if(v[i] >= M)

4. M = v[i];

5. }



▪ EXEMPLOS:

▪ V1 = {1, 2, 3, 4};

▪ V2 = {4, 3, 2, 1};

▪ Considerações▪ V1: o comando if é sempre verdadeiro, logo, teremos mais instruções;

▪ V2: o comando if é sempre falso, a atribuição nunca é executada, logo, teremos menos instruções.



▪ EXEMPLOS:

▪ V1 = {1, 2, 3, 4};

▪ V2 = {4, 3, 2, 1};

▪ Considerações▪ Para nosso azar, V1 vai executar mais instruções, terá um custo maior;

▪ Para nossa sorte, V2 vai executar menos instruções, terá um custo menor;


Documents

ANÁLISE E COMPLEXIDADE DE ALGORITMOSarieldias.com/material/2019-1/ACA/Aula1n.pdf · Análise e Complexidade de Algoritmos Professor Ariel da Silva Dias Introdução Professor Ariel