AEDs III 16/03/2011

Professor Marcos

Bibliografia: Livro do Nivio,

Blibliografia: Livro do Cormen e Rivers - Introduction to Algorithms

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

// Introdução de Ordem de complexidade

// Vale lembrar (ao leitor iniciante) que a complexidade de um programa é o numero de operações que ele realiza ate terminar de trabalhar.

// E que o conceito de ordem de complexidade é um meio de dividir os programas em classes de complexidade ou seja de tempo de execução.

--> O conceito da Ordem de Complexidade é usado para diferenciar grupos de algoritimos, e não para realçar pequenas diferenças entre eles.
  Portanto as diferenças entre ordens de complexidade desprezam tudo que possa ser expresso por um conjunto finito de somas.
  Ex: ordem de 12 = ordem 10 que é = ordem de 0 pois a diferenca é de +2 ou +(-10), e ordem de 14*2 é igual a ordem de 2 pois 14 é constante e pode ser expresso na forma de 14 somas consecutivas.

  Outro detalhe a ser observado nessa definição é que como a maioria dos programas cujo tempo de execução é preocupante usam entradas muito muito grandes, a definição de Ordem de Complexidade se aplica imaginando-se que o tamanho da entrada tende ao infinito.

Definição formal:
--> Ordem de f(x) é usado para se referir a algo que é menor (para valores tendendo ao infinito) que f(x)*c, sendo que c é uma constante arbitrariamente grande.

a Notação para isso é O(n) indicando que o programa tem complexidade n ou inferior para numeros grandes.

--> <ohm> de f(x) é usado para se referir a algo que é maior (para valores tendendo ao infinito) que f(x)*d, sendo que d é uma constante arbitrariamente pequena.

A notação para isso é <ohm>(n) indicando que o programa tem complexidade n ou superior ou seja que seu custo cresce mais rapido.

--> Um programa é assintoticamente <teta> sobre outro se for (para valores perto de infinito) sempre menor que f(n)*c e maior que f(n)*d, sendo c e d os mesmos descritos acima.

A notação para isso é <teta>(n) indicando que o programa tem complexidade aproximadamente igual ao outro.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

// Falamos um pouco sobre o que é entender a interação de um programa com o sistema sobre o qual ele funciona

// É importante considerar alguns fatores ao se programar um algoritimo real: É o tempo de execução, o numero de troca de menssagens com a memoria, e o gasto de energia.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

CONCEITO:

Um algoritmo off-line é que é previsivel, ou seja todas as entradas dele estão no poder do usuário.

Um algoritimo on-line não é previsivel e varia a cada vez que se usa, tipo a bolsa de valores por exemplo.
ou um site de internet, que voce não sabe o que vai ter lá a cada vez.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Relações de Recorrencia:

// Falamos de recusões simples nada de mais a principio.

// Nota pessoal: me lembrei dakele macete de resolver problemas tipo: f(n) = c + f(n-1) igualando um somatorio de cada lado para todos os valores de N. E a versão analoga disso usando um produtorio para f.n = c*f.n-1..

// Nota pessoal: Um macete para resolver somatorios é lembrar dakela regra de que:
" <sum> x*(q^i) " se q < 1 entao o numero converge para " x/(1-q) "

Tem um EXERCICIO PRA FAZER!! LEMBRE!! --> mais ou menos feito, porem não acompanhei a solução do professor no quadro.