MAC0338/lista3.md

3.

Qunado ele faz refeência a memória, ele está querendo dizer o tamanho da pilha de execução. Ou seja, cada vez que chammos a recursão uma nova função é achamada e o consumo de memória aumenta. Pra resolver esse problema, vamos sempre iniciar a recursão na menor parte:

QUICKSORTE2 (A, p, r)
    meio = (p+r)/2
    enqunato p < r
        q <- particiona(A, p, r)
        se q >= meio
            QUICKSORTE2 (A, p, q-1)
            p <- q + 1
        senao
            QUICKSORTE2 (A, q+1, r)
            r <- q - 1

Note que o pior caso para a memória com esse algorítmo não será quando q estiver na posição r-1. O pior caso vai se dar quando q se encontrar no meio. Nesse caso (M é a qunatida de memória):

$$M(1) = 1$$ $$M(n) = M(n/2)$$

Aviso, o particiona é $O(n)$, no entanto ele consome $O(1)$ em memória. Desenvolvendo pelo método da substitituição:

$$M(n) = a + M(n/2) = a + a + M(n/2) = ia + M(\frac{n}{2^i})$$

$$M(n) = ia + M(\frac{n}{2^i})$$

Suponha que n seja multiplo de 2, ou seja, $n = 2^i$. Dessa forma:

$$M(n) = ia + M(1) = ia + 1 = lg \space n + 1$$

Vaja que no pior caso o nosso consumo de memória $O(lg \space n)$.

Vamos provar por indução que estamos certo. Lembre que a nossa hiótese é: $M(n) =lg \space n + 1$. Para a base, a demonstração é trivial.

$$M(n) = M(n/2)$$

Pela hipótese de indução:

$$M(n) = lg \space \frac{n}{2} + 1 + 1 = lg \space n + 1 $$

7.

Seja $S$ a variável aleatória do valor soma de 1 execução. Seja $X$ a variável aleatória que representa cada número do nosso vetor. $$Y = \begin{cases} 1, & \text{se o número for somado} \\ 0, & \text{c.c.} \end{cases}$$

$$E[S] = \sum_{i=1}{10} i \cdot P(X = i \space \text{e} \space Y = 1) = \sum_{i=1}{10} i \cdot P(X = i)P(Y = 1 | X = i)$$

Note que $P(X=1) = 1/10$ para qualquer $i$.

$$E[S] = \frac{1}{10} \sum_{i=1}^{10} i \cdot P(Y = 1 | X = i) = \frac{1}{10} ( 1 \cdot 0 + 2 \cdot 1 + 3 \cdot 0 + 4 \cdot 1 + 5 \cdot 0 + 6 \cdot 1 + 7 \cdot 0 + 8 \cdot 1 + 9 \cdot 0 + 10 \cdot 1) = 3$$

Ou seja o valor esperado em uma rodada será $3$, em $n$ rodadas será $3n$, como foi verificado no programa em ruby abaixo:

def SomaPares (v)
    soma = 0
    v.each do |e|
        soma += e if e%2 == 0
    end
    return soma
end

n = 10000
v = Array.new(n) { rand(1...11) }

puts SomaPares (v)