lista4.md 10 KB
1. Escreva uma função que recebe um vetor com n letras A’s e B’s e, por meio de trocas, move todos os A’s para o início do vetor. Sua função deve consumir tempo $O(n)$.
A função vai receber o vetor C que possi n elementos.
OrdenaAB(C, n)
1. dir <- 1
2. esq <- n
3. enquanto dir < esq
4. se C[dir] igual 'A'
5. dir <- dir + 1
6 senão se C[esq] igual 'B'
7. esq <- esq + 1
8. senão
9. C[esq] <-> C[dir]
10. dir <- dir + 1
11. esq <- esq + 1
Note que em cada interação obrigatoriamente dir vai ser subtraído ou esq vai ser adicionado. Com isso o número máximo de vezes que a linha 3 pode ser executada é $O(n)$. Note que as linhas posteriores a essa vão ser executadas menos vezes que essa, portanto o código continuará $O(n)$.
2. Escreva uma função que rearranje um vetor v[p..r] de inteiros de modo que tenhamos v[p..j−1] ≤ 0 e v[j..r] > 0 para algum j em p..r+1. Faz sentido exigir que j esteja em p..r? Procure fazer uma função rápida que não use vetor auxiliar. Repita o exercício depois de trocar v[j..r] > 0 por v[j..r] ≥ 0. Faz sentido exigir que v[j] seja 0?
OrdenaZero(v, n)
1. dir <- 1
2. esq <- n
3. enquanto dir < esq
4. se C[dir] <= 0
5. dir <- dir + 1
6 senão se C[esq] > 0
7. esq <- esq + 1
8. senão
9. C[esq] <-> C[dir]
10. dir <- dir + 1
11. esq <- esq + 1
Não faz muito sentido exigir que j esteja em p..r, pois pense no caso em que temo o vetor completo de números negativas, nesse caso se j estiver em p..r, algum desses elemntos será > 0, criando uma contradição.
Para trocarmos v[j..r] > 0 por v[j..r] ≥ 0 basta alterar a linha 6 do programa. No entanto não faz sentido exigir que v[j] seja 0, pois dessa forma nunca saberíamos em qual parte do vetor encontramos os zeros.
3. Sejam X[1..n] e Y [1..n] dois vetores, cada um contendo n números ordenados. Escreva um algoritmo $O(lg n)$ para encontrar uma das medianas de todos os 2n elementos nos vetores X e Y .
Vamos tentar usar o método de divisão e consquista. Vamos supor que temos os seguintes vetores:
1 2 3 4 5 6 7 1 2 3 5 8 9 9
É claro que a mediana deles é 4 e 5. Vamos pegar a mediana do vetores:
1 2 3 (4) 5 6 7 1 2 3 (5) 8 9 9
O vetor em qual a mediana for menor deve ser aquele em que vamos pegar a parte da direita, o que a mediana for maior pegamos a da esquerda.
4 5 6 7 -> 4 (5) 6 7 -> 4 5 -> (4) 5 -> 4
1 2 3 5 -> 1 2 (3) 5 -> 3 5 -> 3 (5) -> 5
Na nossa função vamos ter dois vetores v1 e v2 com n elementos. Suponha que 3/2 = 1
Mediana(v1, v2, p1, q1, p2, q2)
1. se q1-p1 = 1
2. tmp <- [v1[p1], v1[q1], v2[p2], v2[q2]]
3. tmp <- ordena tmp
2. retorna tmp[3]
3.
4. j1l <- p1+(q1-p1)/2
5. j2l <- p2+(q2-p2)/2
6. j1u <- p1+(q1-p1+1)/2
7. j2u <- p2+(q2-p2+1)/2
8.
9. tmpv1 <- v1[j1l] + v1[j1u]
10. tmpv2 <- v2[j2l] + v2[j2u]
11.
12. se tmpv1 > tmpv2
13. retorna Mediana(v1, v2, p1, j1u, j2l, q2)
15. senão
16. retorna Mediana(v1, v2, j1l, q1, p2, j2u)
def Mediana(v1, v2, p1, q1, p2, q2)
if q1-p1 == 1
return (v1[p1,2] + v2[p2,2]).sort[1 , 2].join(" ")
end
j1l = p1+(q1-p1)/2
j2l = p2+(q2-p2)/2
j1u = p1+(q1-p1+1)/2
j2u = p2+(q2-p2+1)/2
tmpv1 = v1[j1l] + v1[j1u]
tmpv2 = v2[j2l] + v2[j2u]
if tmpv1 > tmpv2
return Mediana(v1, v2, p1, j1u, j2l, q2)
else
return Mediana(v1, v2, j1l, q1, p2, j2u)
end
end
size = 30
v1 = Array.new(size) { rand(10...50) }.sort!
v2 = Array.new(size) { rand(10...50) }.sort!
puts v1.join(" ")
puts v2.join(" ")
puts Mediana(v1, v2, 0, size-1, 0, size-1)
sorted = (v1+v2).sort
puts [sorted[(2*size - 1) / 2], sorted[(2*size) / 2]].join(" ")
Vamos provar que é $O(lg{} n)$.
$$T(1) = 1$$ $$T(n) = T(\lceil x/2 \rceil) + O(1)$$ $$T(n) = T(\lceil x/2^i \rceil) + i$$
Vamos supor que $x$ é potencia de 2, ou seja, $x = 2^i$
$$T(x) = T(2^i/2^i) + i$$ $$T(x) = T(1) + i$$ $$T(x) = 1 + lg \space x$$
Vamos provar por indução:
BASE: $x = 1, T(1) = 1$ e $1 + lg \space 1 = 1$
HIPÓTESE: $T(x/2) = 1 + lg \space x/2 = lg \space x$
$$T(x) = T(x/2) + 1 = (pela HI) = lg \space x + 1 $$
Que é o que queríamos provar.
4. Para esta questão, vamos dizer que a mediana de um vetor A[p..r] com número inteiros é o valor que ficaria na posição A[b(p + r)/2c] depois que o vetor A[p..r] fosse ordenado. Dado um algoritmo linear “caixa-preta” que devolve a mediana de um vetor, descreva um algoritmo simples, linear, que, dado um vetor A[p..r] de inteiros distintos e um inteiro k, devolve o k-ésimo mínimo do vetor. (O k-ésimo mínimo de um vetor de inteiros distintos é o elemento que estaria na k-ésima posição do vetor se ele fosse ordenado).
Kesimo(A, p, r, k)
m <- mediana(A, p, r)
part <- particiona_com_elemento(A, p, r, m)
se p > k
retorna Kesimo(A, p, part, k)
senao se p < k
retorna Kesimo(A, part, r, k)
retorna A[part]
Note, o particiona é $O(n)$, assim como a mediana. Portanto o tempo de consumo desse algorítmo será $T(n) = T(n/2) + O(n) = T(n/2) + an $. Vamos provar que é $O(n)$. Note que $T(1) = 1$
BASE: $T(1) = 1 \leq c * 1 $
HIPÓTESE: $T(n/2) \leq cn/2 x$
$$ T(n) = T(n/2) + O(n) \leq c * n/2 + a * n \leq (c/2+a) n = c * n - n * c/2 + a * n$$
Só falta peovar que:
$$ - nc/2 + a * n \leq 0 $$ $$ a * n \leq n * c/2 $$ $$ 2 * a \leq c $$
Como $a$ é uma contante que depende do particiona e da mediana e existe, logo existe $c$.
5. (CLRS 8.3-2) Quais dos seguintes algoritmos de ordenação são estáveis: insertionsort, mergesort, heapsort, e quicksort. Descreva uma maneira simples de deixar qualquer algoritmo de ordenação estáavel. Quanto tempo e/ou espaçco adicional a sua estratégia usa?
São estáveis os seguintes: insertionsort, mergesort. Uma maneira de deixar eles eles estáveis é mapear ele em um segundo vetor somando sua posição vezes um numero, por exemplo:
A[1..n] = 5, 4, 2, 4, 6, 5, 4, 1
p = ((n+1) * max(A))
A = 5 + 1 * p, 4 + 2 * p, 2 + 3 * p, 4 + 4 * p, 6 + 5 * p, 5 + 6 * p, 4 + 7 * p, 1 + 8 * p
Ordena o vetor e depois faz elemento % p.
6. Qual a diferença de consumo de tempo entre uma busca binária em um vetor com n elementos e uma busca binária em um vetor com $n^2$ elementos?
A busca binária consome tempo $O(lg \space n)$. Ou seja, $T(n) \leq c * lg \space n$. Queremos descobrir a proporção $\frac{c * lg \space n^2}{c * lg \space n} = 2 * \frac{c * lg \space n^2}{c * lg \space n} = 2$, ou seja vai levar o dobro do tempo.
7. Desenhe a árvore de decisão do algoritmo de ordenação por seleção aplicado a um vetor A com 3 elementos distintos.
Temos tres elementos a, b, c. Nessa árvore em primiro está a comparação e segundo o momento que o nó é explorado no algorítmo (direita sim, esquerda não). Acho que é isso...
A < B
/ \
/ \
B < C A < C
/ \ / \
A<B<C \ B<A<C \
A<C B<C
/ \ / \
A<C<B C<A<B B<C<A C<B<A
8. Considere a árvore de decisão que descreve um algoritmo de ordenação baseado em comparações. Qual a menor profundidade que uma folha pode ter nessa árvore? Justifique detalhadamente.
Vejamos pela figura da imagem acima. A menor profundidade que algo pode ter é qunado o vetor já está ordenado, ou seja todas as comparações retornam verdade e não é preciso se aprofundar. Então, a menor profundidade dessa árvore será $n$.
9. Simule a execução do CountingSort usando como entrada o vetor A[1..11] = (7, 1, 3, 1, 2, 4, 5, 7, 2, 4, 3).
C[1..7] será o nosso vetor auxiliar e B[1..11] também.
B[1..11] = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
C[1..7] = (0, 0, 0, 0, 0, 0, 0)
C[1..7] = (0, 0, 0, 0, 0, 0, 1)
C[1..7] = (1, 0, 0, 0, 0, 0, 1)
C[1..7] = (1, 0, 1, 0, 0, 0, 1)
C[1..7] = (2, 0, 1, 0, 0, 0, 1)
C[1..7] = (2, 1, 1, 0, 0, 0, 1)
C[1..7] = (2, 1, 1, 1, 0, 0, 1)
C[1..7] = (2, 1, 1, 1, 1, 0, 1)
C[1..7] = (2, 1, 1, 1, 1, 0, 2)
C[1..7] = (2, 2, 1, 1, 1, 0, 2)
C[1..7] = (2, 2, 1, 2, 1, 0, 2)
C[1..7] = (2, 2, 2, 2, 1, 0, 2)
C[1..7] = (2, 4, 2, 2, 1, 0, 2)
C[1..7] = (2, 4, 6, 2, 1, 0, 2)
C[1..7] = (2, 4, 6, 8, 1, 0, 2)
C[1..7] = (2, 4, 6, 8, 9, 0, 2)
C[1..7] = (2, 4, 6, 8, 9, 9, 2)
C[1..7] = (2, 4, 6, 8, 9, 9, 11)
B[1..11] = (0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0); C[1..7] = (2, 4, 5, 8, 9, 9, 11); i = 11
B[1..11] = (0, 0, 0, 0, 0, 3, 0, 4, 0, 0, 0); C[1..7] = (2, 4, 5, 7, 9, 9, 11); i = 10
B[1..11] = (0, 0, 0, 2, 0, 3, 0, 4, 0, 0, 0); C[1..7] = (2, 3, 5, 7, 9, 9, 11); i = 9
B[1..11] = (0, 0, 0, 2, 0, 3, 0, 4, 0, 0, 7); C[1..7] = (2, 3, 5, 7, 9, 9, 10); i = 8
B[1..11] = (0, 0, 0, 2, 0, 3, 0, 4, 5, 0, 7); C[1..7] = (2, 3, 5, 7, 8, 9, 10); i = 7
B[1..11] = (0, 0, 0, 2, 0, 3, 4, 4, 5, 0, 7); C[1..7] = (2, 3, 5, 6, 8, 9, 10); i = 6
B[1..11] = (0, 0, 2, 2, 0, 3, 4, 4, 5, 0, 7); C[1..7] = (2, 2, 5, 6, 8, 9, 10); i = 5
B[1..11] = (0, 1, 2, 2, 0, 3, 4, 4, 5, 0, 7); C[1..7] = (1, 2, 5, 6, 8, 9, 10); i = 4
B[1..11] = (0, 1, 2, 2, 3, 3, 4, 4, 5, 0, 7); C[1..7] = (1, 2, 4, 6, 8, 9, 10); i = 3
B[1..11] = (1, 1, 2, 2, 3, 3, 4, 4, 5, 0, 7); C[1..7] = (0, 2, 4, 6, 8, 9, 10); i = 2
B[1..11] = (1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 7); C[1..7] = (0, 2, 4, 6, 8, 9, 9); i = 1
10. Mostre como ordenar n inteiros no intervalo de 0 até $n^2 − 1$ em tempo $O(n)$.
Somente aplicar o CountingSort e pinba. Putra maneira elegante é pensar no binário, se os número vão de 0 até $n^2 − 1$, eles terão no máximo n dígitos, podemos aplicar o BuketSort onde é ordenado dígito a dígito com o CountingSort(que somente pode ser 0 ou 1). Sendo assim teremo $ O(n) * O(2) = O(n)$.
11. Mostre como multiplicar dois números complexos a + bi e c + di usando apenas três multiplicações reais. O seu algoritmo deve receber como entrada os números a, b, c e d e devolver ac − bd (parte real do produto) e ad + bc (parte imaginária).
v1 = d(a - b)
v2 = a(c - d)
v3 = b(c + d)
ac − bd = v1 + v2 = d(a - b) + a(c - d) = ad - bd + ac - ad = ac - bd
ad + bc = v1 + v3 = d(a - b) + b(c + d) = ab - bd + bc + bd = ad + bc