Archive for the 'Análise Alg. 1218/32' Category

Page 3 of 3

Análise de Algorítimos 1218/32 – Aula 5 – 12/04/2010

Published on 13/04/2010 in Análise Alg. 1218/32. 0 Comments

Notas de Aula (Google Docs)

Exercícios: Indução
1. Demonstrar por inducao matematica que
\sum_{i=1}^{n}{\frac{1}{1i} < 1} ,   para r\succeq 1
2. Demonstrar por inducao matematica que 
n! \succ x^{n-1}  , para n>=2 
——————————————————————————
Análise de fragmentos de código

A
sum = =
for (i=1; i<=m; i++)                                          |
   for(j=1l j<=n; j++)                           | \Theta (n)    | \Theta (n^2)
      sum++;                     | \Theta (1)        |              |
Analise: Como operação SUM ++ é o(1), então a complexidade do codigo é equivalente ao numero de vezes  que a operação SUM ++ é O(n2)
Ou ainda: Temos dois lacos aninhados que executam r repetições cada um, com o corpo do laco interno com complexidade o(1). Assim, a complexidade total é n.nO(1)=O(n2)
B
SUM = 0;
for (i=1; c<=n; i++)
    for (j=1; i<=i; j++)
       sum++;
i         1        2           3                    n
1..1   1..2    1..3                             1..n
1   +   2    +   3                +               n
A linha 1 isoladamente tem complexidade \Theta (1)
A linha 4 isoladamente tem complexidade \Theta (1)
A Quantidade de vezes que a linha 4 é executada depende da quantidade de vezes que o laço
da linha 3-4 é executada. Para tal laço, seu conteudo é executado j vezesm conj=1..i
O laço das linhas 3-4 é dependente do laço das linhas 2-4 que é executado n vezes c/ assumindo os valores de 1..n
Logo a quantidade de vezes que a linha 4 é executada é dada por:
T(n) = \sum_{i=1}^{n}{}
T(n) =  \frac{ n(n-1)}{2}
T(n) = \frac{ n^{2} }{2} + \frac{ n }{2}     
Logo a complexidade é proposrcional a n^{2} , assim
T(n) = \Theta n^{2}
Demonstração pela definição assintótica:
T(n) =\frac{1}{2}\cdot n^{2} + \frac{1}{2}\cdot n  ;   T(n) = \Theta (n^2)  ?
\lim_{n \rightarrow \infty}{\frac{\frac{1}{2} \cdot n^{2}+ \frac{1}{2}\cdot n}{n^2} }
\lim_{n \rightarrow \infty}{(\frac{1}{2} \cdot n^{2}+ \frac{1}{2}\cdot n) \cdot \frac{1}{n^2} }
\lim_{n \rightarrow \infty }{\frac{1}{2} + \frac{1}{2^n} }    
L=\frac{1}{2}
Que é uma constante diferente de O logo,
T(n) = \Theta (n^2)
C
T(n) = \Theta (n^2)
sum=0                       \Theta (1)     Considerando que n seja uma potencia de 2
for (k=1; k<=n; k*=2               
  for(j=1; j<=n; j++)               | \Theta (n)
     sum ++;              | \Theta (1)   |
A linha 4 isoladamente é \Theta (1)
pelo laço das linhas 3-4 a linha 4 é executada N vezes. com as linhas 3-4 são n O(1) = O(n)
As linhas 3-4 são executadas uma quantidade de vezes depende do laço das linhas 2-4 onde tem-se
Iteração     1         2     3      4    ….    n
K               1        2     4      8    …..    n 
                2p0    2p1  2p2   2p3  …… 
Assim p/ saber quantas vezes seu conteudo é executado e necessario saber quantos valores diferente k assume até n(inclusive)
Supondo um índice i p/cada iteracao, dado pelo valor do expoente k em base 2, da forma
i = T +1
Para saber o valor de r na última iteracao, tem-se
2^{r} = n  logo   lg 2^r = lg n   logo  r lg2 = lg n +1 = lg n   
r = lg n
E p/ saber o valor de i na última iteração tem-se
i = lg n +1
Assim, o trecho 2-4 é executado
lgn +1    \Theta (n)m resultando em T(n) = \Theta (n lg n) 
D
sum = 0;
for (k=1; k<=n; k*=2);
   for (j=1; j<=k; j++);
        sum++;

Aviso 1218/31 – Análise de Algorítmos

Published on 01/04/2010 in Análise Alg. 1218/32. 0 Comments

Não haverá aula para turma 1218/31 hoje 01/04/2010.

Análise de Algorítimos 1218/32 – Aula 4 – 23/03/2010

Published on 26/03/2010 in Análise Alg. 1218/32. 0 Comments

AULA  04 – 23/03/2010


Análise de algoritmos normalmente é dividida em três casos:

  • Pior Caso
  • Melhor Caso
  • Caso Médio

Tópicos de Aula:


Requisitos mínimos para análise de algoritmos:


                        Indução Matemática e Recursão [PDF]




Exercício 2: Provar por indução matemática que:



Análise de Algorítimos 1218/32 – Aula 3 15/03/2010

Published on 17/03/2010 in Análise Alg. 1218/32. 0 Comments

AVISO: O Professor está refazendo a chamada oralmente no fim da aula e marcando falta para os que não permaneceram. Fiquem até o final da aula para garantir presença.

Tópicos da Aula:


Tipicas taxas de crescimento

Merge Sort [pdf ufam]

    Obs: Os links são exemplos de materiais encontrados e sugeridos pelo blog admin.
              Ler Cormem, Thomas H.


    2 – Análise de Algorítimos 1218/32 – Apresentação

    Published on 11/03/2010 in Análise Alg. 1218/32. 0 Comments

    Professor Mauro Henrique Mulati
    www.din.uem.br/~mhmulati
    mhmulati@din.uem.br
    mhmulati@gmail.com

    Bibliografia:
    Cormem, Thomas H.
    Algorítmos: Teoria e Prática
    2ª Ed. Rio de Janeiro: Editora Campus
    Elievier, 2002.

    Análise de Algorítimos 1218/32

    Published on 09/03/2010 in Análise Alg. 1218/32. 0 Comments

    Execícios 08/03/10

    1) Efetuar o somatório de todos os casos de INSERTION-SORT
    * Melhor Caso
    * Pior Caso
    * Médio Caso
    Obs: exemplo: T(n)=(C1+C2+C3+C4+C5+C6+C7).n – (C2+C3+C4+C7)
    T(n)=an+b “Para constantes a e b que dependem dos C i
    2) Análise da eficiência de tempo para o algoritmo BUBBLE-SORT
    Login