Analise de Algoritmos resumo

Prévia do material em texto

Análise de Algoritmos Aulas NP2
- Complexidade de Algoritmo
Algoritmo 1
Por que se eu tenho um divisor diferente de 1 e do
próprio nº, significa dizer, pela definição
que ele não é primo.
Algoritmo 2
Dado um nº natural qualquer, podemos estudar dois algoritmos para determinar se o
mesmo é um número primo (são os nº naturais que tem apenas dois divisores diferentes,
0 1 e ele mesmo).
Alguns exemplos de nº primos
2,3,5,7,11,....
nº 1 não é primo só tem uma divisor
para i �� 2 até n - 1
se i é divisor de n
retornar n não é primo
retornar n é primo
No primeiro algoritmo, existe um contador que irá variar de 2 até n-1, ou seja, os nºs que
estão entre 1 e o nº que estamos querendo verificar se é primo
Logo após é feito a verificação, se alguns nºs começando de dois 2 até n-1 foi divisor de n
significa dizer que o nº não é primo
Se sair do laço, significa dizer que não encontramos nenhum divisor diferente de um e
dele mesmo, ou seja, o nº é primo
No segundo algoritmo, não foi checado o contador até n-1 é sim até o (√n)
Analise dos algoritmos
Números Primos n (n- 2) operações √n − 1
2 11 10 - 2 = 9ms 3,3 - 1 = 2,5ms
3 101 101 - 2 = 99ms 10,4 - 1 = 9,04ms
5 1010 + 19 1010 + 17 ≅107s ≅105ms 10,66min
7
11
10000000019 ou 1010 + 19
para i �� 2 até $\sqrt n$
se i é divisor de n
restornar n não é primo
retornar n é primo
No segundo algoritmo, não foi checado 0 contador até n-1 e sim até a √n.
as duas soluções estão corretas e resolvem o desafio
Vamos imaginar que cada operação d divisão demora 1 ms, para ser processado, No pior
caso o algoritmo nº 1 irá realizar (n-2) operação, isso irá acontecer quando o nº foi primo
contudo a solução do algoritmo 2 no pior caso vai realizar em √n − 1.
Tomando como exemplo o seguinte nº = 10000000019, passando para base dez para
facilitar a a visualização 1010 + 19. Logo realizado os mesmos cálculos no algoritmo 1
teríamos o resultado 1010 + 19 − 2 = (1010 + 17)ms ≅107s trazendo para segundos que
equivale a aproximadamente 115 dias.
No Algoritmo 2 105 ms = 1,66 min.
No algoritmo 1
O tempo cresce proporcionalmente a n; quanto mais o n sobe, mais tempo o algoritmo
leve, dizemos que a ordem é n, ou seja, O(n)
No algoritmo 2
Otempo de execução é proporcional a √n, logo dizemos que ele é O(√n)
Exemplos de código - Complexidade do algoritmo
Sentença simples
Laço simples
Laços aninhados
Possuem complexidade constante, ou seja O(1)
# sentença simples
s = "Brasil"
i = 42
i4 = 1
Possuem complexidade linear no tamanho de entrada, ou seja, O(n), em que n é o
tamanho da entrada.
# Laço simples
for i in range(n);
# sentenças simples
Possuem complexidade quadrática no tamanho da entrada, ou seja O(n2), em que o n é o
tamanho de entrada
# Laços aninhados
for i in range(n);
for j in range(n);
# Sentença simples
Veja o exemplo abaixo
O Professor citou um exemplo que vale a pena mensionar
...
i = n
while i > 1
i = i//2
print(i)
Qual a complexidade do seguinte trecho de código?
Para cada uma das n iterações dos laços mais externo, o laço mais intenso é exercitados log n
vezes.
Portanto, a complexidade do trecho de código acima é O(n log n)
Qual a complexidade do seguinte trecho de código?
A função fib calcula, de forma extremamente ineficiente, o n-ésimo número da sequência de
Fibonacci. Apesar de essa função possuir algumas em sua estrutura com a função fatorial, a
complexidade de função fib é muito maior.
Sua complexidade é O(2n). Isso ocorre pois são feitas muitas chamadas repetidas à função fib
- P, NP, ConP, NP Difícil e NP Completo - Classes
de Complexidade
Perceba que a variável i é decrementado no laço. A cada iteração do while, o valor
de i é dividido por 2
Assim para n = 64, o trecho de código imprime 32,16,8,4,2,1.
O laço foi executado uma vez para cada um dos números impressos, ou seja, para n
= 64, o laço executado 6 vezes
Se fizermos com valores diferentes de n veremos que o laço sempre executa log(n)
vezes
Logaritmos são comuns em análise de complexidade, e é importante darmos
atenção em nível especial às aparições deles.
Em geral, logaritmos aparecem, sempre que estamos repetidamente divido causas
pela metade ou dobrando o tamanho das coisas
for i in range
i = 1
while imas as soluções são fáceis de verificas.
Problemas NP podem ser verificados por uma Máquina de Turing em tempo polinomial.
Exemplo
1 - Problema do caminho hamiltoniano
2 - Problema de Josephus
3 - Problema de satisfatibilidade Booleana (SAT)
“Pasted image 20240517175510.png” could not be found.
Se um problema x está em NP, então sem complemento X também está em CO-NP.
Para um problema NP e CO-NP, não há necessidade de verificar todas as respostas de
uma vez em tempo polinomial, há necessidade de verificar apenas uma resposta "sim" ou
"não" em tempo polinomial par a que um problema esteja em NP ou CO-NP.
Alguns exemplos de problemas em NP-Hard/Difícil
Classe NP Completo
Um problema é NP-Completo se for NPs NP-Difícil. Problemas NP-Completo são os problemas
difíceis em NP.
Características
Alguns exemplos:
1 - Satisfatibilidade
2 - Cobertura de vértice
Classe de 
Complexidade
Característica
P Facilmente Solucionável em tempo polinomial.
NP Sim, as respostas podem ser verificados em tempo polinomial.
CO-NP Não, as respostas podem ser verificados em tempo polinomial.
NP-Difícil Todos os problemas NP-Difíceis não estão em NP e tem muito 
tempo para verifica-lo.
NP-Completo Um problema que é NP e NP-Difícil e NP-Completo.
um problema A está em NP-difícil se, para cada problema L em NP, existe uma redução
em tempo polinomial de L para A.
Problema da Parede.
Problema do cacheiro viajante.
Problema do mochileiro.
Um problema é NP-Completo são especiais porque qualquer problema de classe NP pode
ser transformados ou reduzidos em problemas NP-Completo em tempo polinomial.
Se alguém pudesse resolver um problema NP-Completo em tempo polinomial, então
também seria possível resolver qualquer problema NP em tempo polinomial.
A questão em aberto mais importante de CC e se P=NP
Isso significa que todos os problemas que podem ser verificados em tempo polinomial
também resolvidos em tempo polinomial.
Isso significa que todos os problemas que podem ser verificados em tempo polinomial,
também resolvidos em tempo polinomial.
Acredita-se que todos os problemas em P também estão em NP, mas não se sabe se
todos os problemas em NP também estão em P.
Exemplos (Caixeiro Viajante)
Exemplos (Problema da mochila-knopack)
Algumas Premissas
Se essa igualdade for verdadeira, teríamos algoritmos eficientes para resolver muitos
problemas difíceis e importantes como o problema do caixeiro viajante. No entanto,
atualmente não há provas conclusivas para a, igualdade ou as diferenças entre as
classes P e NP
Dado um conjunto de cidades e as distâncias entre elas, o problema é encontrar o menor
caminho que visite cada cidade exatamente uma vez e retorne a cidade inicial.
Dado um conjunto de itens, cada um com um peso e um valor e uma mochila com
capacidade limitada, o problema é selecionar um subconjunto de itens que caiba na
mochila e maximize o valor total de itens selecionados.
Problemas intratáveis ou difíceis são comuns na natureza e nas áreas do conhecimento.
Problemas "Fáceis": são resolvidos por algoritmos polinomiais.
Problemas "Difíceis": Somente possuem algoritmos exponenciais para resolvê-los
A Complexidade de tempo da maioria dos problemas é polinomial ou exponencial.
Polinomial: Função de complexidade é O(p(n)) onde p(n) é um polinômio.
Ex: Algoritmos com pesquisa
busca binária é O(log(n)),
pesquisa busca sequencial é O(n),
ordenação por inserção O(n²),
problemas de fatoração O(log(n)).
Exponencial: função de complexidade é O(cn), c > 1.
Ex: problema do caixeiro viajante (PCV) O(n!).
Mesmo problemas de tamanho pequeno o método não podem ser resolvidos por algoritmos
não-polinomiais.
Problemas NP-Completo
Classe NP - Problemas "Sim/Não"
A teoria de complexidade a ser apresentado não mostra como obter algoritmos
polinomiais para problemas que demandam algoritmos exponenciais, nem afirma que não
existe.
P=NP ou P!=NP
É possível mostrar que os problemas para os quais não há algoritmo polinomial
conhecido são computacionalmente relacionados.
Formam a classe conhecida como NP
Propriedade: um problema de classe NP poderá ser resolvido em tempo polinomial se e
somente se todos os outros problemas em NP também poderem.
Acredita-se que todos os problemas em P também estão um NP, mas nós se sabe se
todos os problemas em NP também estão em P.
Se essa igualdade for verdadeira, teremos algoritmos eficientes para resolver muitos
problemas difíceis e importantes, como o problema do caixeiro viajante. No entanto,
atualmente não há provas conclusivas para a igualdade ou diferença entre as classes P e
NP.
Para o estudo teórico da complexidade de algoritmos considera-se problemas cujo
resultado de computação seja "sim" ou "não".
Versão do PCV cujo resultado é do tipo "sim/não"
Dados: uma constante K1 um conjunto de cidades
C = {c1,c2,........,Cn} e uma distância d(Ci,Cj) para cada par de cidades Ci, Cj ∈ C
Característica de classe NP: Problemas "Sim/Não" para os quais uma dada solução pode
ser verificado facilmente.
→ A solução pode ser muito difícil ou impossível de ser obtido, mas uma vez conhecido
ele pode ser verificado em tempo polinomial
Caracterização das classes P e NP
Algoritmo determinista
O resultado de cada operação é definido de forma única.
Algoritmo não-deterministo
Capaz de escolher uma dentre as várias alternativas para cada passo
Contêm operações cujo resultado não é unicamente definido, ainda que limitado a um conjunto
especificado de possibilidades.
Existe diferença entre P e NP ?
Algoritmos de busca
P: Conjunto de todos os problemas que podem ser resolvidos por algoritmo determinista
em tempo polinomial
Np: Conjunto de todos os problemas que podem ser resolvidas por algoritmos não-
determinista em tempo polinomial.
Para mostrar que um determinado problema está em NP, basta apresentar um algoritmo
não determinista que execute um tempo polinomial para resolver o problema
P ⊆ NP, pois algoritmos deterministas são um caso especial dos não-deterministas.
A questão é se P = NP ou P ≠ NP.
Esse é o problema não resolvido mais famoso que existe no CC.
Se existem algoritmos polinomiais deterministas para todos os problemas em NP, então P
= NP.
Por outro lado, a prova de que P ≠ BO parece exigir técnicas ainda desconhecidas.
A classe P está contida em NP
Acredita-se que NP >> P pois para muitos problemas em NP, não existem algoritmos
polinomiais conhecidos.
- Busca Sequencial
Entrada: um vetor M1, M2......,Mn e um elemento x
Saída: ("Sim", i) ou "Não"
Qual é o tempo (pior caso) gasto pelo algoritmo
Resposta: O(n)
- Busca binária
Entrada: Um vetor M1, M2,....Mn de inteiros ordenados e um inteiro x
Saída("Sim", i) ou "Não"
Qual é o tempo (pior caso) gasto pelo algoritmo?
Início
i �� ;
Enquanto (i �� n) e (x�� Mi) faça i �� i + 1;
se (i �� n) então imprima ("Sim", i) senão imprima "não"
Fim
Início
L �� 1; r �� n; achou �� falso;
�� Enquanto (L �� r) e (não achou) faça
K �� [(L + r)/2];
se x = Mk então achaou �� verdadeiro
senão se x > Mk então L �� K + 1 senão r �� K - 1
Se achou então imprime ("Sim", K) senão imprima "Não"
Fim
- Ordenação - bubblesort
Entrada: Um vetor M = M1, M2, ...... Mn de inteiros
Saída: O vetor M ordenado em ordem não decrescente
Qual é o tempo (pior caso) gasto pelo algoritmo?
Resposta: O(n2)
Recursivade - Princípios Básicos
O tempo fasto pela busca binária é proporcional ao número de iterações do laço
"Enquanto...Faça".
O número de elemntos do vetor no início da
1ª iteração é W
2ª iteração é n/2
3ª iteração é n/22
.....
(i + 1)a iteração é n/2i
Na última iteração teremos n/2i = 1 o que resulta em i = logn portnato o tempo gasto pela
busca binária é O(logn)
Início
Para j �� i até n - 1 faça
Para l �� i até j faça
Se Mi > Mi + 1 então "troque Mi com Mi + 1"
Fim
Muitos problemas possuem a seguinte propriedade: uma solução pode ser obtido através
da solução de instâncias menores do mesmo problema. Dizemos que esses problemas
têm natureza recursiva.
Para resolver um tal problema podemos aplica o seguinte método:
Se a instância emquestão é pequena, resolva-o diretamente
Senão
Reduza o instâncias menores do mesmo problema
resolva os problemas menores recursivamente
resolva o problema original
Para começarmos o estudo sobre recursividade vamos ver o cálculo fatorial de um inteiro
como se sabe na matemática o fatorial de um número definido pelo produto de todos os
número inteiros entre o número e um vamos supor que temos o número n e desejamos
N ! = n × (n − 1) × (N − 2)×. . . ×1
Temos a multiplicação de n vezes n - 1 * n - 2 até chegar a multiplicação por um. Se pegarmos
do N - 1 até a área marcada temos a definição do fatorial de n -1
(N − 1) × (n − 2)×. . . . ×1
Logo a nossa equação pode ficar dessa forma
n! = n × (n − 1)!
Isso vai ser válido para todos os inteiros positivos maiores do que ∅, mas no caso n seja igual
a ∅ saberemos o valor igual a 1
n! = {nx (n-1)! Se >0}
n! = (1 Se n = ∅)
Na primeira chamada para calcular o n! estamos passando o número n. Já na chamada
recursiva estamos passando n - 1.
Isso é chamado de passo recursivo Se n > ∅
Vamos escrever o pseudocódigo para cálculo de fatorial
Para fixar entendimento vamos procurar saber como será processado o algoritmo.
chamada retorno estado
fatorial(3) 3×fatorial(2) P
fatorial(2) 2×fatorial(1) P
fatorial(1) 1×fatorial(0) P
calcular o seu fatorial (N!).
Teríamos uma equação dessa forma:
A segunda característica de uma função recursiva é que eles terá o passo base, ou seja,
que ela para onde eu não vou utilizar a recursividade.
Então neste caso do fatorial temos o cálculo do fatorial de ∅ que irá retornar como
resposta o búmero 1isso é chamado de Passo Base se n = ∅
fatorial n{
Se(n��0)
retornar 1 �� Passo base
senão
retornar n * fatorial(n-1) �� Passo recursivo
}
chamada retorno estado
Fatorial(0) 1 -
Chamada Retorno Estado
fatorial(3) 3× 2 = 6 R
fatorial(2) 2 × 1 = 2 R
fatorial(1) 1 × 1 = 1 R
fatorial(0) 1 -
Técnicas de projeto de algoritmo
Eurísticas
Dividir para conquistar(divide-and-conquer)
Programação dinâmica(otimização)
Procura ganânciosa-gulosa(Greedy-otimização)
Aprendizagem(Machine Learning)
Procura exaustivo ou força bruta(brute force ou backtraking)
Algoritmos genéticos
Colônia de formigas
CV(????)