2 – Dando a partida – Problemas

2.1 – Ordenação por inserção para arranjos pequenos na ordenação por intercalação

Embora a ordenação por intercalação funcione no tempo de pior caso Θ(nlgn) e a ordenação por inserção funcione no tempo de pior caso Θ(n²), os fatores constantes na ordenação por inserção podem torná-la mais rápida para n pequeno em algumas máquinas. Assim, faz sentido adensar as folhas da recursão usando a ordenação por inserção dentro da ordenação por intercalação quando os subproblemas se tornam suficientemente pequenos. Considere uma modificação na ordenação por intercalação, na qual n/k sublistas de comprimento k são ordenadas usando-se a ordenação por inserção e depois intercalados com a utilização do mecanismo-padrão de intercalação, onde k é um valor a ser determinado.

a) Mostre que a ordenação por inserção pode ordenar as n/k sublistas, cada uma de comprimento k, em Θ(nk) tempo do pior caso.

Para cada vetor de tamanho k o insertion-sort vai demorar Θ(k²), então para cada n/k sublistas teremos:

$\theta(n/k \times k^2) = \theta(nk)$

b) Mostre como intercalar as sublistas em tempo do pior caso Θ(nlg(n/k)).

Se já temos as n/k sublistas (i.e o processo de divisão já foi realizado), então só precisamos continuar dividindo-as até terem tamanho 1. O merge-sort demora lgn para dividir uma lista de comprimento n. Sendo assim, para dividir n/k listas, vai demorar lg(n/k). Por fim, basta intercalar as n/k listas e o tempo final será de Θ(nlg(n/k)).

Prova:

número de níveis:
$\frac{n}{k \times 2^i} = 1 \\ \frac{n}{k} = 2^i \\ i = lg(\frac{n}{k})$

no último nível:
$2^{lg(\frac{n}{k})} = (\frac{n}{k})^{lg(2)} = \theta(\frac{n}{k})$

custo:
$\sum_{i=0}^{lg(n/k)} 2^i\left(\frac{cn}{2^i}\right) + \theta(\frac{n}{k}) \\ \sum_{i=0}^{lg(n/k)} cn\left(\frac{2^i}{2^i}\right) + \theta(\frac{n}{k}) \\ cn \sum_{i=0}^{lg(n/k)} \left(\frac{2}{2}\right)^i + \theta(\frac{n}{k}) \\ cn \sum_{i=0}^{lg(n/k)} 1 + \theta(\frac{n}{k}) \\ cnlg(n/k) + \theta(\frac{n}{k}) \\ \theta(nlg(n/k))$

O que fiz foi uma árvore de recursão, já que na minha opinião é o método mais fácil de visualizar isso, dá para provar via indução, entretanto fiquei meio confuso durante a prova e optei por fazer desse modo, que é ensinado no capítulo 4.

c) Dado que o algoritmo modificado é executado em tempo do pior caso Θ(nk + nlg(n/k)), qual é o menor valor de k em função de n para qual o algoritmo modificado tem o mesmo tempo de execução que a ordenação por intercalação-padrão, em termos da notação Θ.

É pedido um valor de k tal que o tempo do pior caso vá de Θ(nk + nlg(n/k)) para Θ(nlg(n)). É facilmente visto um valor de k tal que a fórmula se adapte, então vamos algebrar para isolar o k.

$nk + nlg(n/k) = nlg(n) \\ nk = nlg(n) - nlg(n/k) \\ k = lg(n) - lg(n/k) \\ k = lg(n/n/k) \\ k = lg(nk/n) \\ k = lg(k)$

Substituindo na fórmula original vamos encontrar:
$2nlg(n) - nlg(lg(n)) = \theta(nlg(n))$

d) Como k deve ser escolhido na prática?

Depende dos valores da entrada, não tem como saber diretamente. Entretanto, poderiamos gastar Θ(n) para analisar a entrada e escolher um k a partir da análise feita.

2.2 – Correção do bubblesort

O bubblesort é um algoritmo de ordenação popular, porém ineficiente. Ele funciona permutando repetidamente elementos adjacentes que estão fora de ordem.

Bubble-Sort(A):
for i=1 to A.comprimento
for j=A.comprimento downto i+1
if A[j] < A[j-1]
swap(A[j], A[j-1])

a) Seja A’ um valor que denota a saída de Bubblesort(A). Para provar que Bubblesort é correto, precisamos provar que ele termina e que

A'[1] ≤ A'[2] ≤ … ≤ A'[n], (2.3)

onde n = A.comprimento. O que mais deve ser provado para mostrar que Bubblesort realmente realiza a ordenação.

Acho que é provar que todos elementos de A esteja em A’, ou seja, que A’ é uma permutação de A.

b) Enuncie com precisão um invariante de laço para o laço for das linhas 2 a 4 e prove que esse invariante de laço é valido. Sua prova deve usar a estrutura da prova do invariante de laço apresentada nesse capítulo.

Invariante: A primeira posição da lista A'[j .. n] possui o menor elemento após o término do segundo laço (L2).

Inicialização: Inicialmente o j é igual a n, então A[j .. n] = A[n], onde o menor elemento é o único da lista.

Manutenção: Para a próxima iteração (j = j-1), a lista vai ser A'[j-1 .. n], e já que é verificado se A[j] < A[j-1] e trocado caso verdadeiro, o valor de A[j-1] vai ser o menor dessa lista.

Finalização: O loop termina quando j=i+1, então o menor elemento vai estar na posição i+1-1 da lista A[i .. n].

Resposta obtida em conjunto com a análise feita em [2] .

c) Usando a condição de término do invariante de laço demonstrado na parte b), enuncie um invariante de laço para o laço for das linhas 1 a 4 que permita provar a desigualdade (2.3). Sua prova deve empregar a estrutura da prova do invariante de laço apresentada nesse capítulo.

Invariante: No fim de cada iteração i, o vetor A[1 .. i] está ordenado de forma crescente.

Inicialização: Se i=1, então o invariante da questão anterior nos garante que o menor elemento vai estar na posição A[j], sendo que j=i e i=1, o elemento estará na posição 1 da lista.

Manutenção: Para i=i+1, o término do invariante anterior nos garante que o i-ésimo menor elemento vai estar na posição i da lista A’. Ou seja, o vetor A[1 .. i] está ordenado crescentemente.

Finalização: Quando i=n, o vetor A[1 .. n] vai estar ordenado crescentemente.

Resposta obtida em conjunto com a análise feita em [2] .

d) Qual é o tempo de execução do pior caso de bubblesort? Como ele se compara com o tempo de execução da ordenação por inserção?

Para todos os casos: repete n vezes o loop da linha 1 e (n-i) vezes o loop da linha 2, então:

$n(n-i) = n^2 - ni = \theta(n^2)$

Tem a mesma complexidade que o insertion-sort no pior caso.

2.3 – Correção da regra de Horner

O fragmento de código a seguir implementa a regrar de Horner para avaliar um polinômio

$\displaystyle \begin{array}{lcl} P(x) & = & \sum\limits_{k=0}^{n} a_kx^k \\ & = & a_0 + x(a_1 + x(a_2 + ... + x(a_{n-1} + xa_n)...)), \end{array}$

dados os coeficiente a0, a1, … , an e um valor para x:

Horner(A, x):
y = 0
for i=n downto 0
y = A[i] + x*y

a) Qual é o tempo de execução desse framento de código em termos de notação Θ para a regrar de Horner?

Repete n+1 vezes o laço, então é: Θ(n).

b) Escreva pseudocódigo para implementar o algoritmo ingênuo de avaliação polinomial que calcula cada termo no polinômio desde o início. Qual é o tempo de execução desse algoritmo? Como ele se compara com a regra de Horner?

Horner-Ingenuo(A, x):
total = A[0]
for i=1 to 0
total += A[i]*pow(x, i)

Tempo de execução depende da função pow():

Θ(n), se tiver os valores de x^i pré calculados.
Θ(n²), se tiver que calcular x^i usando o método da exponenciação simples.
Θ(nlgn), se tiver que calcular x^i usando o método da exponenciação rápida.

c) Considere o seguinte invariante de laço:

$\displaystyle y = {\sum\limits_{k=0}^{n-(i+1)} } a_{k+i+1}x^k$

No início de cada iteração do laço for nas linhas 2-3,

Interprete como igual a zero um somatório que não tenha nenhum termo. Seguindo a estrutura do invariante de laço apresentado nesse capítulo, use esse invariante de laço para mostrar que, no término $y = \sum_{k=0}^{n} a_kx^k$ .

Inicialização: No início y=0 e i=n, então o somatório vai ir de k=0 até n-(i+1) = n-(n+1) = 1, sendo assim, não vai executar a primeira iteração e o y vai ficar igual a 0.

Manutenção: para i=i-1

$\displaystyle \begin{array}{lcl} y' & = & a_i + xy \\ & = & a_i + x\left(\sum_{k=0}^{n-(i+1)} a_{k+i+1}x^k \right) \\ & = & a_i + \left(\sum_{k=0}^{n-(i+1)} a_{k+i+1}x^{k+1} \right) \\ & = & {\sum\limits_{k=0}^{n-i} } a_{k+i}x^k \\ & = & {\sum\limits_{k=0}^{n} } a_{k}x^k \quad \text{ i=0 (ultima iteracao)} \end{array}$

Término: Quando i=0, podemos chegar na fórmula $\sum_{k=0}^{n} a_kx^k$

d) Conclua demonstrando que o fragmento de código avalia corretamente um polinômio caracterizado pelos coeficiente a0, a1, … , an.

De acordo com o que foi provado na questão anterior, quando o loop parar, o resultado final vai ser o polinômio calculado.

2.4 – Inversões

Seja A[1 .. n] um arranjo de n números distintos. Se i < j e A[i] > A[j], então o par (i, j) é denominado inversão de A.

a) Apresenta uma lista com as cinco inversões do arranjo {2, 3, 8, 6, 1}.

Inversões = {(1, 5), (2, 5), (3, 5), (4, 5), (3, 4)}

b) Qual arranjo com elementos do conjunto {1, 2, … , n} tem o maior número de inversões? Quantas inversões ele tem?

É o arranjo ordenado de forma decrescente. Tem

$\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}$ inversões.

c) Qual é a relação entre o tempo de execução da ordenação por inserção e o número de inversões? Quantas inversões ele tem?

Quanto mais inversões tiver, mais o insertion-sort vai demorar, pois seu laço interior troca elementos adjacentes até que o menor elemento esteja no começa da sublista. O insertion-sort tem exatamente n(n-1)/2 inversões no pior caso, que é igual ao custo do pior caso do algoritmo. Sendo assim, é possível afirmar que ele tira as inversões existentes da lista.

d) Dê um algoritmo que determine o número de inversões em qualquer permutação com os n elementos em tempo do pior caso Θ(nlgn). (Sugestão: Modifique a ordenação por intercalação).

A sugestão mata a charada. Podemos modificar o merge-sort para contar as inversões quando for fazer o merge da sublista da esquerda e da direita. Onde o número de inversões de uma subchamada é definido pelo somatório da quantidade de elementos remanescentes na sublista da esquerda, quando for coloca na lista conjunta um elemento da sublsita da direita.

| 02 | 08 | — | 07 | 12 | | 01 | 04 | — | 09 | 10 |
1/ 0/ 0/ 0/
| 02 | 07 | 08 | 12 | | 01 | 04 | 09 | 10 |
4/ 3/ 1/ 1/
| 01 | 02 | 04 | 07 | 08 | 09 | 10 | 12 |

Total = 1+4+3+1+1 = 10 inversões.

Código modificado:

Merge-Inversões(A, p, q, r)
n1 = p-q+1
n2 = r-q
L = [A[p+i] for i in range(n1)]
R = [A[q+1+i] for i in range(n2)]
L[n1] = ∞
R[n2] = ∞
i, j, inv = 0, 0, 0
for k=p to r
if L[i] < R[i]
A[k] = L[i]
i += 1
else
inv += (n1 – i)
A[k] = R[j]
j += 1

Implementação dos exercícios que exigem códigos: https://github.com/meitcher/mtcblog/blob/master/CLRS/Cap2/problemas.py

Referências:

[1] CORMEN, T.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Introdução à Algoritmos (Terceira Edição). MIT Press and McGraw-Hill. 2009.

[2] MANCINELLI. J. My answers CLRS 2e. Disponível em: http://answers-by-me.blogspot.com.br/2010/07/clrs-2e-problem-2-2.html.

mv.treviso

NLP, ML e etc.