FANDOM


AvaliaçãoEdit

3 Provas de mesmo peso

  • 23/set - P1
  • 28/out - P2
  • 09/dez - P3
  • 18/dez - PF

LinksEdit

Site Vignatti

EmentaEdit

  1. Conceitos básicos de análise de algoritmos
  2. Análise de Algoritmos de Ordenação
  3. Análise Probabilística
  4. Programação Dinâmica
  5. Reduções
  6. NP-Completude

MaterialEdit

Aulas

Exercícios

Aula 1

Exercício 1
Aula 2 Exercício 2
Aula 3 Exercício 3
Aula 4 Exercício 4

Conceitos básicos de análise de algoritmosEdit

  • Prova de corretude
  • Análise de complexidade
  • Modelos de algoritmos
    • Divisão-e-conquista
    • Programacão dinâmica
    • Algoritmos aleatorizados
  • Dificuldade instrínsica


Definição de algoritmoEdit

É uma ferramenta para resolver um problema computacional, em termo gerais, para todas as entradas do problema retorna uma saída esperada que é a solução do problema computacional.


Problemas NP-CompletosEdit

É um problema que não possui uma solução eficiente, mas que se encontrada a solução para um dos problemas, então todos são resolvidos


Algoritmos e tecnologiasEdit

Um problema pode ser resolvido por dois algoritmos diferentes em máquinas diferentes sobre circunstâncias diferentes, mas apenas o algoritmo é que determina a eficiência e não os outros fatores, e.g. um algoritmo eficiente numa máquina antiga resolve o problema antes que um algoritmo não-eficiente numa máquina atual.
Por esse motivo é bom desconsiderar esses fatores quando se está analisando um algoritmo.


Conceitos para a matériaEdit

  • Utilizado máquinas RAM.
  • Complexidade de tempo (eficiência) é o número de instruções básicas para cada entrada de certo tamanho
  • Adota-se uma “atitude pessimista” e faz-se uma análise do pior caso
  • É possível que o pior caso ocorra raramente na vida real
  • É difícil descobrir um "caso médio"


ExercíciosEdit

1. Que outras medidas de eficiência, além de velocidade, podem ser úteis no mundo real? Dê exemplos.

R: Acessos à memória, acessos ao disco, espaço em disco utilizado pelo algoritmo, dependências externas, etc.

2. Suponha a seguinte comparação das implementações do InsertionSort e do MergeSort na mesma máquina. Para entradas de tamanho $ n $, o InsertionSort executa em $ 8 n ^ 2 $ passos, enquanto o MergeSort executa em $ 64n \log n $ passos. Para quais valores de $ n $ o InsertionSort ganha do Merge- Sort?

R: Queremos IS > MS
PLOT EX2

Insertion Sort vs Merge Sort

Percebe-se que quando n=45, o Insertion sort começa a levar mais tempo que o Merge Sort, já que IS é uma curva quadrática e MS é uma curva logarítimica, ou seja, em algum ponto os dois algoritmos levarão o mesmo tempo para realizar as operações mas a partir desse ponto, a curva logarítimica estará sempre abaixo da quadrática.




3. Qual é o menor valor de $ n $ tal que um algoritmo com tempo de execução $ 100n^2 $ seja mais rapido que outro com tempo de execução $ 2^n $ na mesma máquina?

R: Plotando as fórmulas obtemos
PLOT EX3

Comparação dos algoritmos

Logo percebe-se que o algoritmo que tem $ 100n^2 $ tempo de execução é bem melhor a partir de $ n=15 $







Análise de Algoritmos IterativosEdit

Ordenação de vetoresEdit

Utilizaremos o Insertion Sort

Entrada: Um vetor $ A[1...n] $
Saída: Um vetor ordenado em ordem crescente $ A[1...n] $
1 i j n
20 25 35 40 44 55 38 99 10 65
1 i j n
20 25 35 40 44 55 99 10 65
1 i j n
20 25 35 40 44 55 99 10 65
1 i j n
20 25 35 40 44 55 99 10 65
1 i j n
20 25 35 38 40 44 50 99 10 65

Chave = 38

Pseudo-códigoEdit

OrdenaPorInsercao(A,n)


para j <- 2 até n faça
chave <- A[j]
  • Insere A[j] no subvetor ordenado A[1...j-1]
i <- j-1
enquanto i >= 1 e A[i] > chave faça
A[i+1] <- A[i]
i <- i-1
A[i+1] <- chave

O que é importante analisar?Edit

  1. Finitude : o algoritmo para?
    • No "enquanto" da linha 5 o valor de i diminui a cada iteração e o valor inicial é maior ou igual a 1, logo a condição sempre será alcançada.
    • O laço da linha 1 evidentemente para pois j aumenta a cada iteração até n, e começa com valor = 1, logo para todas as instâncias o algoritmo para. Já que não faz sentido pedir para que se ordene um vetor menor que 2 posições.
  2. Corretude : o algoritmos faz o que promete?
    • Descobrir a Invariante de um laço e prová-la. A invariante é uma propriedade útil que relaciona as variáveis de um algoritmo para mostrar a corretude de um algoritmo. Nesse caso dizemos que no começo do laço que contém as linhas de 1 a 8 temos um subvetor ordenado $ A[1... j-1] $.
    • Uma "receita de bolo" para mostrar a corretude de um algoritmo é achar uma invariante que vale no começo de uma certa iteração e então provar que ela vale no início da próxima, então conclua que se o algoritmo pára e vale no início da última iteração então o algoritmo está correto.
  3. Complexidade de tempo : quantas instruções são executadas no pior tempo?
    • Determinar um custo para cada linha e verificar quantas vezes ela é executada para cada instância de tamanho $ n $.
    • Calcular o custo para o pior caso, aqui seria um vetor inversamente ordenado.
    • Para o algorimo que temos, o custo no pior caso é da forma $ an^2+bn+c $, mais especificamente $ 3n^2+10n+50 $. Isso é uma função quadrática e na notação assintótica é $ n^2 $. Por que?
$ n $ $ 3n^2+10n+50 $ $ 3n^2 $
64 12978 12288
128 50482 49152
512 791602 786432
1024 3156018 3145728
2048 12603442 12582912
4096 50372658 50331648
8192 201408562 201326592
16384 805470258 805306368
32768 3221553202 3221225472
  • Podemos ver que com n grande, as funções tem pouca diferença, logo a parte mais significative é $ 3n^2 $. Mas como o 3 é dependente da implementação dizemos que na notação assintótica a complexidade desse algoritmo é $ \Theta(n^2) $

ExercíciosEdit

1. Expresse a função $ \frac{n^3}{1000} - 100n^2 - 100n + 3 $

R: Trocando valores por constantes temos $ \frac{1}{1000} * {n^3} - 100 * n^2 - 100 * n + 3 $
Obtendo assim: $ an^3 - bn^2 - cn + d $ onde $ a, b, c, d $ são $ \frac{1}{1000}, 100, 100, 3 $
Devemos considerar apenas a parte significativa, então a notação assintótica seria $ \Theta(n^3) $ pois a partir de um ponto, $ n^3 $ seria sempre maior que $ \frac{n^3}{1000} - 100n^2 - 100n + 3 $

2. Considere ordenar $ n $ núumeros armazenados num vetor $ A $ encontrando primeiramente o menor elemento de $ A $ e troque-o com o elemento em $ A[1] $. Em seguida, encontre o segundo menor elemento de $ A $, e troque-o com $ A[2] $. Continue usando a mesma idéia para os primeiros $ n-1 $ elementos de $ A $.
(a) Escreva um pseudo-código para este algoritmo (Selection Sort).
(b) Porque é preciso executar somente para os $ n-1 $ elementos ao invés de $ n $?.
(c) Dê o tempo de execução de melhor-caso e pior-caso do Selection Sort na notação $ \Theta $.

R(a):
01   SelectionSort(n, A){
02       para i de 1 até n-1 faça
03           menor ← i
04           para j de i+1 até n faça
05               se A[j] < A[i]
06                   menorj
07           troque A[i] por A[menor]
08   }
R(b): Só é preciso executar para os $ n-1 $ elementos pois após $ n-1 $ iterações teremos um subvetor ordenado $ A[1...n-1] $, porém o $ n $-ésimo elemento é o maior de todos os números, pois ele foi "empurrado" para o fim com a execução da linha 07, como $ n $ é o maior elemento e $ A[1...n-1] $ está ordenado então $ A[1...n] $ também está.
R(c): A seguir uma tabela com o número das linhas e quantas vezes elas serão executadas.
Worst-case scenario
Linha Execuções
2 $ c1 * (n-1) $
3 $ c2 * (n-1) $
4 $ c3 * (\frac{n^2+n}{2}) $
5 $ c4 * (\frac{n^2+n}{2}) $
6 $ c5 * (\frac{n^2+n}{2}) $
7 $ c6 * (n-1) $
Obtemos assim:$ (c1+c2+c6 * (n-1)) + (c3+c4+c5 * (\frac{n^2+n}{2})) $
Desprezando as constantes: $ (n-1) + (\frac{n^2+n}{2}) $
Podemos observar que $ n-1 $ pode ser desprezado e também $ \frac{1}{2} $ que multiplica $ n^2+n $ é desprezível.
Por fim temos $ n^2+n $ mas em comparação, $ n $ é bem menor que $ n^2 $, logo a parte significativa é $ n^2 $, em notação assintótica temos que o custo é $ \Theta(n^2) $
Best-case scenario

Análise de Algoritmos RecursivosEdit