Disciplina: Análise de Sistemas

COMPUTAÇÃO

(Eficiência ou Ordem de Complexidade: Cota Superior e Cota Inferior)

1 - Cota Superior ou Limite Superior ("upper bound")

Seja dado um problema, por exemplo, multiplicação de duas matrizes quadradas de ordem n.

Conhecemos um algoritmo para resolver este problema (pelo método trivial) de complexidade            Sabemos assim que a complexidade deste problema não deve superar          ,  uma vez que existe um algoritmo desta complexidade que o resolve. Uma cota superior (ou "upper bound")

deste problema é      . A cota superior de um problema pode mudar se alguém descobrir um outro algoritmo melhor. Isso de fato aconteceu com o algoritmo de Strassen que é de         

Assim a cota superior do problema de multiplicação de matrizes passou a ser                 Outro pesquisadores melhoraram ainda este resultado. Atualmente o melhor resultado e o de Coppersmit e Winograd - de                 Notem que a cota superior de um problema depende do algoritmo.

 

A cota superior de um problema é parecida com o record mundial de uma modalidade do atletismo. Ela é estabelecida pelo melhor atleta (algoritmo) do momento. Assim como o record mundial, a cota superior pode ser melhorada por um algoritmo (atleta) mais veloz.

"Cota Superior" dos 100 metros rasos:

As Revistas Eletrônicas "ensinoeinformacao.com" e "Ensino&Informação" (do FaceBook)  publicam textos que julgam ser mais adequados em FORMA e CONTEÚDO sempre respeitando os direitos de Autoria: Citamos a Fonte bem como o nome do autor! Contudo, sempre que necessário, fazemos correções e adicionamos comentários e links para Tópicos pertinentes ao assunto que está sendo abordado!

OBSERVAÇÃO - Esclarecimento aos leitores: Aproveitamos este texto da página (desativada) do Site do IME-USP do ano de 2005 por ser simples, mas com conteúdo substancial. Notem que o exemplo prático aqui é o determinar a Ordem de Complexidade de Algoritmos que venham a ter um “Procedure” (em Português, Procedimento) para determinar o produto de duas matrizes quadradas de ordem n (n linhas por n colunas). Isto significa que estamos interessados em calcular o tempo computacional T(n) para cada n. Mas se as duas matrizes envolvidas no produto de matrizes não fossem quadradas! Teríamos que determinar a Ordem de Complexidade para este novo procedimento (produto de matrizes não quadradas).

 

Em breve, estaremos abordando com mais amplidão este exemplo e variações dele, fornecendo a resposta para a Determinação da Ordem de Complexidade em questão. Só para se ter idéia de como abordando um novo Procedimento e, por conseguinte o novo Algoritmo envolvido, o problema pode mudar significativamente. Pensemos em procedimentos sugeridos abaixo:

 

  1. Procedimento: Produto de duas (02) Matrizes quadradas de ordem n (n linhas e n colunas); T(n)=? , ou seja O(f(n))=? ou seja, qual é a expressão para f(n) - Um Polinômio, uma exponencial ou qual função envolvendo  a variável n é a mais apropriada?

  2. Procedimento: Produto de duas (02) Matrizes de ordem n x m (n linhas e m colunas);

     T(n,m)=? , ou seja O(f(n,m))=? ou seja, qual é a expressão para f(n,m) - Um Polinômio, uma exponencial ou qual função envolvendo duas variáveis n e m é a mais apropriada?

  1. Procedimento: Produtos de Matrizes A1, A2,...,Ap ou seja A1xA2x...xAp, onde cada matriz tem ordem, por exemplo nxm; mxq; qxr; ...e assim por diante até a ordem da matriz Ap - portanto, produtos sucessíveis de P matrizes.

    T(n,m,q,r,..,p)=? , ou seja O(f(n,m,q,r,...,P))=? ou seja, qual é a expressão para f(n,m,q,r,...,P) - Um Polinômio, uma exponencial ou qual função envolvendo as variáveis n,m,q,r,...,P é a mais apropriada? Bastante complexo este problema! Mas existe solução para ele – veja um pouco a respeito deste "procedure" no link:

           http://www.lia.ufc.br/~pargo/disciplinas/cana111/index.php/Manuscritos/Matrizes

 

  1. Procedimento: Dada uma matriz quadrada A de ordem n, e o procedimento de obter o produto de AxAxAx...xA com m parcelas aparecendo  a Matriz A neste produto, isto é      .

     T(n,m)=? , ou seja O(f(n,m))=? ou seja, qual á expressão para f(n,m) - Um Polinômio, uma exponencial ou qual função envolvendo duas variáveis n e m é a mais apropriada?

Cota Inferior ou Limite Inferior ("lower bound")

Às vezes é possível demonstrar que para um dado problema, qualquer que seja o algoritmo a ser usado, o problema requer pelo menos um certo número de operações. Essa complexidade é chamada Cota Inferior ou "lower bound" do problema. Veja que a Cota Inferior depende do problema, mas não do particular algoritmo. Usamos a letra     em lugar de O para denotar uma Cota Inferior.

 

Para o problema de multiplicação de matrizes (quadradas) de ordem (ordem da matriz!) n, apenas para ler os elementos (Entrada de Dados) da duas matrizes de entrada leva tempo             Assim, uma Cota Inferior trivial é      

 

Na analogia anterior, uma Cota Inferior de uma modalidade de atletismo não dependeria mais do atleta. Seria algum tempo mínimo que a modalidade exige, qualquer que seja o atleta. Um Cota Inferior trivial para os 100 metros rasos seria o tempo que a velocidade da luz leva para percorrer 100 metros no vácuo.

 

Se um algoritmo tem uma complexidade que é igual a Cota Inferior do problema, então ele é ótimo. O algoritmo de Coppersmith e Winograd é de               , mas a Cota Inferior é d  e              Portanto nâo podemos dizer que ele é ótimo. Pode ser que esta Cota Superior possa ainda ser melhorada. Pode, também, ser que a Cota Inferior de               possa ser melhorada (isto é, "aumentada"). Muitos pesquisadores desta área dedicam seu tempo tentando encurtar este intervalo ("gap") até encostar uma da outra.

 

  

(48) 8410.6510 /  faleconosco@ensinoeinformacao.com  /  Florianópolis - SC - Brasil

  • w-facebook
  • Twitter Clean
  • w-googleplus

® 2003 - 2018 Todos os direitos Reservados, ensinoeinformacao.com

Temos Uma versão desta Revista Especificamente para SmartPhones: Versão mais Enxuta somente com Vídeo Aulas e Eventos