EA-869 - Dúvidas Frequentes
EA-869 - Dúvidas Frequentes
Capítulo I (01.03.2006)
(Ting - 2s97;
Léo - 1s98 / 1s2006)
O que é um problema computável?
Por que é importante a análise da complexidade
computacional de um algoritmo?
O que entendemos por tamanho de um problema?
O que é um problema polinomial (P)?
Quais são as funções limitantes
superiores mais conhecidas?
O que é um problema não-deterministicamente
polinomial (NP)?
O que é um problema NP-completo?
Dados dois algoritmos A e B para solucionar um
problema. O algoritmo A tem complexidade de
ordem quadrática (p.ex.,f(N)=N ²) e
o algoritmo B, de ordem linear (p.ex.,f(N)=aN;), para todos os
tamanhos N do problema. Pode-se concluir que B requer
menor tempo de execução do
que A para todos os tamanhos N?
O que é um problema computável?
(Ting - 2s97;
Léo - 1s98 / 1s2006)
Um problema é computável se existe um procedimento
que o resolve em um número finito de passos, ou seja
se existe um algoritmo que leve à sua
solução.
Observe que um problema considerado computável
pode não ser tratável
na prática, devido às limitações
dos recursos computacionais para executar o algoritmo
implementado.
Por que é importante a análise de complexidade
computacional de um algoritmo?
(Ting - 2s97)
A complexidade computacional de um algoritmo diz respeito
aos recursos computacionais - espaço de memória e
tempo de máquina - requeridos para solucionar
um problema.
Geralmente existe mais de um algoritmo para resolver um problema.
A análise de complexidade computacional é portanto
fundamental no processo de definição de algoritmos
mais eficientes para a sua solução.
Apesar de parecer contraditório, com o
aumento da velocidade dos computadores, torna-se cada vez mais
importante desenvolver algoritmos mais eficientes, devido ao aumento
constante do "tamanho" dos problemas a serem resolvidos.
O que entendemos por tamanho de um problema?
(Ting - 2s97;
Léo - 1s98)
O tamanho de um problema é o tamanho da entrada
do algoritmo que resolve o problema. Vejamos os seguintes
exemplos:
- A busca em uma lista de N elementos
ou a ordenação de uma lista de N elementos
requerem mais operações à medida que N
cresce;
- O cálculo do fatorial de N tem o seu
número de operações aumentado
com o aumento de N;
- A determinação do valor de F_N
na sequência de Fibonacci F_0, F_1,
F_2, F_3, ... envolve uma quantidade de
adições proporcional ao valor de N; e
- A determinação se um grafo tem um
ciclo hamiltoniano (um ciclo que usa cada vértice
do grafo) fica mais complicada à medida que o
número de vértices, N, cresce.
Dizemos que o tamanho destes problemas é N.
Tipicamente utilizamos
um número inteiro positivo, de forma que
as funções, f(N), que exprimem a complexidade
são funções de números inteiros
positivos, ou seja, f:Z+->R+ (Z+ representa o conjunto
dos números inteiros positivos e R+ o conjunto dos números reais
positivos).
O que é um problema polinomial (P)?
(Ting - 2s97)
Um problema polinomial tem solução de complexidade
até ordem polinomial.
Para entendermos melhor a ordem de grandeza de
uma função de complexidade de um problema,
vamos introduzir a seguinte definição:
Sejam f,g:Z+->R. Dizemos que g domina f (ou
f é dominada por g) se existe m pertencente a R e
k a Z+, tais que |f(N)| <= m|g(N)| para
todo N pertencente a Z+, onde N >=k.
Em outras palavras, f(N) é dita dominada por
g(N), se o limite de |f(N)|/|g(N)| com
N tendendo a infinito é igual a um valor real m.
Se f é dominada por g, dizemos ainda
que f é da ordem de grandeza
g, ou seja f pertence a O(g)
(lê-se big-Oh de g).
A ordem de grandeza das funções é
importante na análise de complexidade de algoritmos.
Ao invés de computarmos a função
exata do número de operações necessário,
f(N), é mais fácil e frequentemente válido
trabalharmos com a sua ordem de grandeza.
É claro que para uma mesma função f(N)
pode existir
uma infinidade de funções limitantes superiores; mas
o que se procura é a menor função limitante
superior para caracterizar a sua ordem de grandeza da complexidade.
Um algoritmo com complexidade
polinomial é aquele que tem a sua função
de comple- xidade, f(N), majorada por uma
função g(N) de ordem polinomial (p. ex,
g(N) = N ³).
Algoritmos com complexidade polinomial são
computacionalmente tratáveis, requerendo um tempo
de execução limitado por uma função
polinomial.
Quais são as funções limitantes
superiores mais conhecidas?
(Ting - 2s97)
big-Oh |
Designação |
O(1) |
Constante |
O(logn) |
Logarítmica |
O(n) |
Linear |
O(nlogn) |
nlogn |
O(n²) |
Quadrática |
O(n³) |
Cúbica |
O(nc), c número real |
Polinomial |
O(cn), c número real, maior que 1 |
Exponencial |
O(n!) |
Fatorial |
O que é um problema não-deterministicamente
polinomial (NP)?(Ting - 2s97)
Um problema não-deterministicamente polinomial é
um problema computável cujas soluções
até então conhecidas são
de ordem exponencial e não se sabe se existe
uma solução melhor, de complexidade
polinomial.
Observe que o termo "não-determinístico" não
implica aleatoridade, mas apenas não se pode
afirmar a existência de um algoritmo de complexidade
polinomial para o problema em consideração.
Outra observação interessante é que
a comprovação de uma solução correta
de um problema NP tem complexidade de ordem polinomial.
O que é um problema NP-completo?(Ting - 2s97), (Léo - 1s2007)
Um problema NP-completo é um problema "representante"
de uma classe de problemas NP, de tal sorte que
os problemas da classe (NP) são redutíveis
a ele em tempo polinomial. Por exemplo, o problema de
caixeiro-viajante é um poblema redutível ao
problema de ciclo hamiltoniano. Dizemos então que
o problema de ciclo hamiltoniano é um problema
NP-completo.
Foi demonstrado que, se um algoritmo de complexidade
polinomial puder ser encontrado para qualquer um dos
problemas NP-completos, então todos os problemas
NP-completos serão na verdade problemas P. Por
outro lado, se for provado que um deles requer
um algoritmo de solução que apresente
complexidade exponencial, então todos terão
complexidade exponencial.
Dados dois algoritmos A e B para solucionar um
problema. O algoritmo A tem complexidade de
ordem quadrática (p.ex.,f(N)=N ²) e
o algoritmo B, de ordem linear (p.ex.,f(N)=aN;), para todos os
tamanhos N do problema. Pode-se concluir que B requer
menor tempo de execução do
que A para todos os tamanhos N?(Ting - 2s97)
Não. Para analisar precisamente a eficiência de um
algoritmo devemos levar em consideração
o tamanho do problema.
Se esboçarmos as curvas das duas funções
acima, constataremos facilmente que até o tamanho
N menor que a o algoritmo com complexidade
de ordem quadrática é melhor. Só a partir
de N maior que a é que o segundo
algoritmo começa a superar o primeiro no desempenho.
Responsável atual:
leopini@dca.fee.unicamp.br
Atualizada: 01/03/2006
Last modified: Tue Mar 10 21:37:19 BRA 1998
Sugestões para leopini@dca.fee.unicamp.br