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

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.