EA-869 - Dúvidas Frequentes

Capítulo I (01.03.2006)

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:
1. 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;
2. O cálculo do fatorial de N tem o seu número de operações aumentado com o aumento de N;
3. 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
4. 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)

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.

Last modified: Tue Mar 10 21:37:19 BRA 1998

Sugestões para leopini@dca.fee.unicamp.br