lista5.md 7.3 KB
1. Mostre que lg (n!) ≥ (n/4) lg n para n ≥ 4 sem usar a formula de Stirling.
Vamos utilzar que $$2 lg \space (n!) \geq (n/2) lg \space n$$ e lebrem que $$ 2 lg \space (n!) = lg \space (n!^2) = lg \space(\prod_{i=0}^{n-1} (n-i) \cdot (i+1)) $$ $$ (n-i) \cdot (i+1) = ni+n-i^2-i$$
Se realizarmos primeira derivada dessa função em $i$ e igualarmos a 0, vamos obter que $n-2i-1 = 0$. Resolvendo essa equaçao e sabendo que a parábola da equação de segundo grau é voltada para baixo, descobrimos que o ponto máximo dessa equação é em $i = \frac{n-1}{2}$. Veja que $i \in [0, n-1]$, calculando o valor da equação nos tremos chegamos a $n$ em ambos o caso. Portanto como o máximo está entre os extremos e nelas o valor é $n$, podemos concluir que,
$$ (n-i) \cdot (i+1) \geq n $$
Usando isso,
$$ 2 \cdot lg \space (n!) \geq 2 \cdot lg \space (\prod_{i=0}^{n-1} n) = 2 \cdot lg \space (n^n) = 2 \cdot n \cdot lg \space (n)$$
$$ lg \space (n!) \geq n \cdot lg \space (n)$$
Se dividirmos a parte da direita dessa inequação por 4 ela continua sendo válida e chegamos onde queríamos.
2. (CLRS 8.1-3) Mostre que não há algoritmo de ordenação baseado em comparações cujo consumo de tempo é linear para pelo menos metade das n! permutações de 1 a n. O que acontece se trocarmos “metade” por uma fração de 1/n? O que acontece se trocarmos “metade” por uma fração de $\frac{1}{2^n}$?
Tenho $n!/2$ folhas na nossa árvore de decisão (note que é uma árvore binária), portanto não pode ter mais que $2^h$ folhas ($h$ é a altura da árvore e é ainda desconhecido). Portanto $$\frac{n!}{2} \leq 2^h$$ Aplicando o $lg$ em anbos os lados, $$h \geq lg \space (n!) - 1$$ E sabendo que $$ lg \space (n!) \geq n \cdot lg \space (n)$$ (pelo exercíco anterior), $$h \geq lg \space (n!) - 1 \geq n \cdot lg \space (n) - 1$$ Ou seja, o número mínimo de comparações será $h$ e como $h$ é limitado inferiormente por $n \cdot lg \space (n) - 1$, temos que o algorítimo irá realizar no mínimo $\Omega(n \cdot lg \space (n))$ comparações.
Vamos proceder da mesma forma para $\frac{n!}{n}$ comparações. $$\frac{n!}{n} \leq 2^h$$ $$h \geq lg \space (n!) - lg \space n$$ $$h \geq lg \space (n!) - lg \space n \geq n \cdot lg \space (n) - lg \space n = \Omega(n \cdot lg \space (n))$$
E o mesmo para $\frac{n!}{2^n}$, $$\frac{n!}{2^n} \leq 2^h$$ $$h \geq lg \space (n!) - n$$ $$h \geq lg \space (n!) - n \geq n \cdot lg \space (n) - n = \Omega(n \cdot lg \space (n))$$
3. (CLRS 8.2-4) Descreva um algoritmo que, dados n inteiros no intervalo de 1 a k, preprocesse sua entrada e então responda em O(1) qualquer consulta sobre quantos dos n inteiros dados caem em um intervalo [a..b]. O preprocessamento efetuado pelo seu algoritmo deve consumir tempo O(n + k).
$A$ é o vetor com os $n$ elementos.
Processa(A, n k)
B[1..k] <- 0
para i igual a 1 até n
B[A[n]] <- B[A[n]] + 1
para i igual a 2 até k
B[i] <- B[i] + B[i-1]
A linha 2 e 3 consome tempo proporcional a n e a 4 e 5 proporcional a k, portanto o tempo de execução será $O(kn)$.
Descobre(a, b, B)
return B[b]-B[a]
4. (CLRS 8.4-1) Simule a execução do BUCKETSORT com o vetor $A[1..10] = <0.79, 0.13, 0.16, 0.64, 0.39, 0.20, 0.89, 0.53, 0.71, 0.42>$.
B[1..10] = [[], [], [], [], [], [], [], [], [], []]
Para cada elemento de A vamos fazer \$\lceil\$ nA \$\rceil\$, vamos, na simulação guardar um A'
A'[1..0] = [7.9, 1.3, 1.6, 6.4, 3.9, 2.0, 8.9, 5.3, 7.1, 4.2]
A'[1..0] = [8.0, 2.0, 2.0, 7.0, 4.0, 2.0, 9.0, 6.0, 8.0, 5.0]
Inserimos A[i] em B[A'[i]]
B[1..10] = [[], [0.13, 0.16, 0.20], [], [0.39], [0.42], [0.53], [0.64], [0.79, 0.71], [0.89], []]
Ordenamos cada lista de B.
B[1..10] = [[], [0.13, 0.16, 0.20], [], [0.39], [0.42], [0.53], [0.64], [0.71, 0.79], [0.89], []]
Concatenamos as listas
B[1..10] = [0.13, 0.16, 0.20, 0.39, 0.42, 0.53, 0.64, 0.71, 0.79, 0.89]
5. (CLRS 8.4-2) Qual é o consumo de tempo de pior caso para o BUCKETSORT? Que simples ajuste do algoritmo melhora o seu pior caso para O(n lg n) e mantém o seu consumo esperado de tempo linear.
O pior caso no BUCKETSORT é quando todos os elementos da lista cairem na mesma sub-lista do vetor B. Nesse caso o nosso algorítimo vai levar tempo proporcional ao método de ordenação que utilizamos para ordenar essas sub-listas. No livro, ele escolhe o InsertionSort que posui pior caso $nˆ2$, se trocarmos por qualquer algorítmo de tempo máximo $O(n lg \space n)$, teremos o pior caso como $O(n lg \space n)$. Vamos averiguar se preserva o caso médio, $n_i$ será o número de elementos médio no sub vetor
$$E[T(n)] = E[\Theta (n) + \sum_{i = 1}^{n} O(n_i lg \space n_i)]$$ $$E[T(n)] = \Theta (n) + \sum_{i = 1}^{n} O(E[n_i lg \space n_i]) = \Theta (n) + O(n lg \space n)$$
6. (CLRS 28.2-5) Quão rápido você consegue multiplicar uma matriz kn × n por uma n × kn usando o algoritmo de Strassen como uma subrotina? Responda a mesma questão com a ordem das matrizes de entrada invertida.
Vamos supor que quermos multilicar $A_{kn*n}$ por $B_{n*Kn}$, note que vamos obter uma matriz $C$ de dimenções $kn*kn$. Vamos dividir $A$ em $k$ matrizes de dimenões $n*n$, sendo assim teremos $A=\begin{bmatrix} A_1 \\ A_2 \\ ... \\ A_n \end{bmatrix}$. O mesmo Vale para $B=\begin{bmatrix} B_1 & B_2 & ... & B_n \end{bmatrix}$ Veja que $C = \begin{bmatrix} A_1 \cdot B_1 & A_1 \cdot B_2 & ... & A_1 \cdot B_n \\ A_2 \cdot B_1 & A_2 \cdot B_2 & ... & A_2 \cdot B_n \\ ... & & & ... \\ A_n \cdot B_1 & A_n \cdot B_2 & ... & A_n \cdot B_n \end{bmatrix} $. Fazendo dessa maneiro o tempo esperado da multiplicação será $\Theta(k^2 \cdot n^{lg \space 7})$, pois termos $k^2$ multiplicações de matrizes de dimensões $n*n$ e o algoritmo de Strassen leva tempo proporcionar a $\Theta(n^{lg \space 7})$.
Invertendo a ordem e fazendo $B \cdot A$, vamos obter um $C$ de dimensões $n*n$. Veja que para esse caso $D = \begin{bmatrix} A_1 \cdot B_1 \\ A_2 \cdot B_2 \\ ... \\ A_n \cdot B_n \end{bmatrix} = \begin{bmatrix} D_1 \\ D_2 \\ ... \\ D_n \end{bmatrix}$ e $C = D_1 +D_2 + ... +D_n$, portanto para esse caso o tempo será $\Theta(k \cdot n^{lg \space 7})$.
7. No Select-BFPRT, os elementos do vetor são divididos em grupos de 5. O algoritmo continua linear se dividirmos os elementos em grupos de 7? E em grupos de 3? Justifique sua resposta.
Veja que nessa imagem há no máximo $\lceil \frac{n}{7} \rceil$ pontos em cada linha. Há $\lceil \frac{1}{2} \lceil \frac{n}{7} \rceil \rceil$ colunas a direita da mediana, incluindo ela, note que há duas dessas colunas em que o número de pontos é menor. Portanto há $5(\lceil \frac{1}{2} \lceil \frac{n}{7} \rceil \rceil-2)$ pontos menores que a mediana. Note que:
$5(\lceil \frac{1}{2} \lceil \frac{n}{7} \rceil \rceil-2) \geq \frac{n}{14} - 10$
Ou seja na prónima interação vamos calcular um número maior que $\frac{n}{14} - 10$ no melhor caso e um número menor que $n-\frac{n}{14} - 10$ no pior caso. Vamos assumir que vamos sempre pegar o pior caso para poder calcular o pior caso. Note também que en todos os casos vou ter que calcular a medina das medianas, que vai consumir tempo $T(\lceil \frac{n}{7} \rceil)$. Dessa maneira o tempo total será:
$$T(n) = T(\lceil \frac{n}{7} \rceil) + T(\frac{13n}{14} + 10)$$