Introdução Conceitos Basicos

Análise de Algoritmos
Prof. Me. Marcos Alves

[email protected]
 Problemas:
 Ir de casa ao trabalho
 Analisar orçamento doméstico
 Simular o funcionamento de uma turbina de avião
 Cursar Engenharia
 Soluções:
 Receitas
 Procedimentos
 Descrição de processos – Algoritmos
Análise de Algoritmos Prof. Me. Marcos Alves 2

 Algoritmo
 A essência de um procedimento computacional, instrução passo-a-
passo detalhadas.
 Programa
 Implementação do algoritmo em uma linguagem de programação.
 Estrutura de dados
 Organização dos dados necessários para resolver o problema.

 Computador na solução de problemas
 Projetar
 Escrever
 Verificar
 Questões Importantes na projeção de algoritmos

 Correção
 Eficiência
 Robustez
 Reusabilidade

 Entrada: sequência <a1, a2, … , an> de n números
 Saída: permutação <a’1, a’2, …, a’n> de maneira que

a’1 ≤ a’2 … ≤ a’n
 Exemplo:
 Entrada: 31 41 59 26 41 58
 Saída: 26 31 41 41 58 59

 Algoritmo:
 Sequência de instruções sem ambiguidade para solucionar um
problema
 Obter uma saída exigida para qualquer entrada válida em um intervalo
de tempo finito.
 Tipos de problemas
 Projeto Genoma Humano
 Busca/Roteamento na Internet
 Comércio eletrônico
 Distância entre pontos (google maps)
 Alocação de recursos
 Multiplicação de matrizes

 Estrutura de dados
 Técnicas
 Problemas Difíceis
 Problemas NP-Completos
 Aplicações Reais
 Problema do Caixeiro-Viajante: Uma companhia de entregas carrega
um caminhão com mercadorias para serem entregues em diversos
pontos. No final do dia, o caminhão deve retornar à companhia para
ser recarregado. Determinar a rota de entregues com a menor
distância.
 Algoritmos de Aproximação

 Computador: Infinitamente rápido e com toda a memória
que necessitar:
 Será que mesmo assim precisamos estudar algoritmos ?
 É sempre interessante demonstrar que nossa solução está correta e
que nossa implementação usa boas técnicas de engenharia de
software.
 Realidade: Computadores não são infinitamente rápidos e

apesar da memória ser barata, ainda não se pode usá-la sem
restrições.

 Algoritmos que resolvem um mesmo problema pode ser
muito diferentes quanto a eficiência.
 Algoritmo A: f(n) = C1 n2
 Algoritmo B: g(n) = C2 n log n
 C1 < C2
 A partir de um certo valor de n, f(n) ≥ g(n)
 Computador A: Algoritmo A
▪ 1.000.000.000 de instruções por segundo: C1 = 2
 Computador B: Algoritmo B
▪ 10.000.000 de instruções por segundo: C2 = 50
 Ordenar 1.000 números
▪ Computador A: 2.000.000 instruções
▪ Computador B: 50.000 instruções

Tempo de Tamanho máximo do problema (n)
Execução 1 segundo 1 minuto 1 hora
400n 2500 150000 9000000
20 n log n 4096 166666 7826087
2 n2 707 5477 42426
n4 31 88 244
2n 19 25 31

 Problema
 Estratégia
 Algoritmo
 Entrada
 Saída
 Pré e Pós-Condições
 Passos
 Análise
 Correção
 Tempo e Espaço
 Eficiência
 Implementação
 Verificação
 Entrada: Sequência de números
 a1, a2, a3, a4, ..., an
 Saída: Uma permutação da sequência de números
 b1, b2, b3, b4, ..., bn
 Característica de Correção
 Para qualquer entrada dado o algoritmo termina com a saída:
▪ b1 < b2 < b3 < b4 < ...< bn
▪ b1, b2, b3, b4, ..., bn é uma permutação de a1, a2, a3, a4, ..., an
 Tempo de Execução
 Depende de:
▪ Número de elementos
▪ Quão (parcialmente) ordenados eles estão
▪ Algoritmo

 Estratégia:
 Inicie com a mão vazia.
 Insira uma carta no posição correta da mão já ordenada.
 Continue até que todas as cartas sejam inseridas/ordenadas.
8 2 4 9 3 6
8 2 4 9 3 6
1 i j 2 8 4 9 3 6
2 4 8 9 3 6
Ordenado Chave
2 4 8 9 3 6
2 3 4 8 9 6
2 3 4 6 8 9

Algoritmo ORDENA-POR-INSERÇÃO (A, n)
para j de 2 até n faça
chave = A[j];
i = j − 1;
enquanto i >= 1 e A[i] > chave faça
A[i + 1] = A[i]; //desloca valor
i = i − 1;
fimEnquanto
A[i + 1] = chave; // insere na posição correta
fimPara
fimAlgoritmo

 Correção de um algoritmo significa basicamente:
 mostrar de forma genérica que o algoritmo cumpre com os seus objetivos.
 Para tratar da correção de um algoritmo iterativo são necessárias 4 fases:

 Identificação: identifica a “propriedade” a ser analisada.
 Inicialização: Mostrar que a “propriedade” é verdadeira antes da primeira iteração.
 Manutenção: Mostrar que a “propriedade” é verdadeira antes da iteração corrente e
que permanece verdadeira antes da próxima iteração.
 Terminação: Quando o laço termina a “propriedade” é mantida.
 “propriedade” corresponde a uma invariante (característica relevante

para provar a correção).

 Invariante do Laço
 No início de cada loop for A[1...i-1] consiste de elementos originalmente em A[1...i-1],
mas ordenados.
 Inicialização
 Para i=2, o invariante se mantém já que A[1] está ordenado.
 Manutenção:
 O laço ENQUANTO interior move os elementos A[i-1], A[i-2], ..., A[i-k] uma posição para
direita sem mudar a ordem.
 Então o elemento A[i] (salvo) é inserido na posição k de forma que A[k-1] ≤ A[k] ≤A [k+1].
 A[1...i-1] estava ordenado + A[i] → A[1...i] ordenado.
 Terminação:
 O laço termina quando i=n+1. Então o invariante assegura que “A[1...n] consiste de
elementos de A[1...n] mas ordenados”

 É importante especificar as pré-condições e pós-condições de algoritmos:
 Entrada
 Especificações precisas de que o algoritmo recebe como entrada.
 Saída
 Especificações precisas do que o algoritmo produz com a entrada.
 As manipulações de casos especiais da entrada devem ser descritas.

 Eficiência
 Tempo de execução
 Espaço usado
 Eficiência como uma função do tamanho de entrada:

 Número de elementos (números)
 Melhor Caso
 Pior caso
 Caso médio

 Qual o desempenho do Insertion-Sort?
 Qual o melhor caso?
 Qual o pior caso?
Próxima Aula: crescimento de funções

Introdução Conceitos Basicos

Enviado por

Direitos autorais:

Formatos disponíveis

Introdução Conceitos Basicos

Enviado por

Dados do documento

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Introdução Conceitos Basicos

Enviado por

Direitos autorais:

Formatos disponíveis

Análise de Algoritmos

Prof. Me. Marcos Alves

Análise de Algoritmos Prof. Me. Marcos Alves 2

Análise de Algoritmos Prof. Me. Marcos Alves 3

 Questões Importantes na projeção de algoritmos

Análise de Algoritmos Prof. Me. Marcos Alves 4

 Saída: permutação <a’1, a’2, …, a’n> de maneira que

Análise de Algoritmos Prof. Me. Marcos Alves 5

Análise de Algoritmos Prof. Me. Marcos Alves 6

Análise de Algoritmos Prof. Me. Marcos Alves 7

 Realidade: Computadores não são infinitamente rápidos e

Análise de Algoritmos Prof. Me. Marcos Alves 8

Análise de Algoritmos Prof. Me. Marcos Alves 9

400n 2500 150000 9000000

20 n log n 4096 166666 7826087

2 n2 707 5477 42426

Análise de Algoritmos Prof. Me. Marcos Alves 10

Análise de Algoritmos Prof. Me. Marcos Alves 12

Análise de Algoritmos Prof. Me. Marcos Alves 13

Análise de Algoritmos Prof. Me. Marcos Alves 14

 Para tratar da correção de um algoritmo iterativo são necessárias 4 fases:

 “propriedade” corresponde a uma invariante (característica relevante

Análise de Algoritmos Prof. Me. Marcos Alves 15

Análise de Algoritmos Prof. Me. Marcos Alves 16

Análise de Algoritmos Prof. Me. Marcos Alves 17

 Eficiência como uma função do tamanho de entrada:

Análise de Algoritmos Prof. Me. Marcos Alves 18

 Qual o melhor caso?

 Qual o pior caso?

Próxima Aula: crescimento de funções

Análise de Algoritmos Prof. Me. Marcos Alves 19

Você também pode gostar