Bom pessoal, a partir de agora também darei aqui no blog algumas dicas de programação que serão úteis para quem usa alguma distribuição baseada no Unix como Debian, Ubuntu e outros.
domingo, 30 de dezembro de 2012
terça-feira, 17 de julho de 2012
Quick-Sort: Uma abordagem indutiva.
Neste post, vamos fazer uma análise indutiva do método de ordenação que na prática é o mais rápido. O quick-sort demostra a eficiência do paradigma "dividir e conquistar".
O primeiro passo do quick-sort é escolher aleatoriamente um elemento x que será chamado de pivô. Em seguida, o vetor será particionado de forma que os elementos a esquerda do pivô sejam menores que ele, e os elementos a direita sejam maiores ou iguais a ele. A Figura 1 apresenta uma partição cujo pivô é 4.
![]() |
| Figura 1. Vetor particionado |
Descrição indutiva da "partição": Para construir o nosso algoritmo vamos utilizar a abordagem indutiva, detalhando o caso base, a hipótese de indução e o caso geral..
Idéia indutiva:
- Caso Base: o vetor possui apenas 1 elemento, então ele já está particionado!
- Hipótese de Indução: vamos supor que o problema da partição já está resolvido para n - 1 elementos e que sabemos onde termina a lista de elementos menores que o pivô.
- Caso Geral: é quase trivial, pois basta verificar se o último elemento do vetor é menor ou maior que o pivô. Caso o último elemento seja menor que o pivô, então basta colocá-lo no final da lista de elementos menores que o pivô.
Implementação da partição: Seguindo o esquema indutivo apresentado, podemos implementar um método de forma simples. Nessa implementação, o pivô escolhido é o primeiro elemento do vetor.
- Implementação em C++:
int partition(int X[], int left, int right) {
int pivot = X[left];
int i = left;
for (int j = left; j <= right; j++)
if (X[j] < pivot)
swap(X, j, ++i);
swap(X, left, i);
return i;
}
Após a execução do método "partition", apenas o pivô estará na posição correta. Precisamos ordenar os elementos que estão à esquerda e à direita do pivô. No entanto, podemos assumir que a hipótese de indução fará esse trabalho, como podemos ver na Figura 2.![]() |
| Figura 2. |
- Caso Base: um vetor com 1 elemento já está ordenado.
- Hipótese de Indução: após a execução do método "partition", vamos assumir que a hipótese de indução sabe como ordenar todos os elemento que estão à esquerda e à direita do pivô.
- Caso Geral: simplesmente já temos o vetor ordenado!
Na Figura 3, apresentamos o resultado final, um vetor ordenado!
![]() |
| Figura 3. Vetor ordenado. |
- Implementação em Haskell: por se tratar de uma linguagem funcional, Haskell permite que o programador implemente uma solução enxuta, sem se preocupar com detalhes.
quickSort :: [Int] -> [Int]
quickSort [] = []
quickSort [x] = [x]
quickSort (x:xs) = quickSort menores ++ [x] ++ quickSort maiores
where
menores = [p | p <- xs, p <= x]
maiores = [p | p <- xs, p > x]
- Implementação em C++
void quickSort(int A[], int left, int right){
if(left < right){
int middle = partition(A, left, right);
quickSort(A, left, middle - 1);
quickSort(A, middle + 1, right);
}
}
- Implementação em Python
def quickSort(lista): if lista == []: return [] else: pivot = lista[0] menores = [x for x in lista[1::] if x < pivot] maiores = [x for x in lista[1::] if x >= pivot] return quickSort(menores) + [pivot] + quickSort(maiores)
Complexidade do Quick-Sort: A complexidade do algoritmo depende da escolha do pivô, caso o pivô escolhido divida o vetor em duas partes com tamanhos iguais ou similares, a sua complexidade será O(n log n).
Caso os elementos do vetor já estejam ordenados, a complexidade do Quick-Sort no pior caso será descrita pela recorrência $T(n) = T(n - 1) + O(n) = O(n^2)$. Na prática, como o pior caso raramente acontece, a literatura reconhece que o Quick-Sort é o melhor algoritmo de ordenação, e por isso ele é utilizado em uma grande variedade de aplicações.
sábado, 7 de julho de 2012
Particionando em pares e ímpares
Agora, vamos utilizar indução para resolver um problema fácil, que com indução ficou mais fácil ainda.
Problema:
- Dada uma sequência de n valores inteiros, rearranjar os elementos de forma que os valores pares apareçam antes dos ímpares.
- Caso Base: uma lista com 1 elemento já está particionada em pares e ímpares.
- Hipótese de Indução: podemos assumir que o problema já foi resolvido para n-1 elementos, e que sabemos onde termina a lista de pares.
- Caso Geral: basta verificar se o último elemento é par ou ímpar, se ele for par basta inseri-lo no final da lista de pares, caso contrário, não fazemos nada.
- Situação inicial: Um vetor com valores pares e ímpares misturados.
- Hipótese de indução: agora vamos "imaginar" que o problema já foi resolvido para os primeiros n - 1 elementos, e que sabemos onde termina a lista de pares.
- Caso Geral: Pronto! Agora ficou muito fácil, podemos perceber que o último elemento é par, então vamos incrementar o final da lista de pares e trocar o último elemento da lista de pares com o último elemento do vetor.
- E assim chegamos a solução do problema.
O algoritmo segue exatamente a idéia apresentada acima. Vamos assumir que o problema já foi resolvido para os primeiros n - 1 elementos, e dentro do loop só escreveremos código para trocar o último elemento do vetor (caso ele seja par) com o último elemento da lista de pares. E não podemos esquecer do caso base!
- Implementação em C++ (versão iterativa)
fimPares = -1; // caso base
for(int i = 0; i < tamVetor; i++)
if(vetor[i] % 2 == 0){ // passo indutivo
fimPares++;
troca(vetor[i], vetor[fimPares]);
}
Complexidade do algoritmo: A relação de recorrência da nossa solução é T(n) = T(n - 1) + 1, ou seja, o tempo gasto pela hipótese de indução para separar os n - 1 elementos mais o tempo gasto para colocar o último elemento no final da lista de pares. Derivando T(n) temos:
$T(n) = T(n - 1) + 1$
$T(n) = T(n - 2) + 1 + 1$
$T(n) = T(n - 3) + 1 + 1 + 1$
$T(n) = T(n - 4) + 1 + 1 +1 +1$
...
$T(n) = 1 + 1 + 1 + 1 + 1 + 1 + ... + 1 + 1$
$T(n) = O(n)$
Logo, concluímos que o nossa solução tem complexidade linear.
Por que usar indução?
Em seu artigo, intitulado "Using induction to design algorithms", Udi Manber faz uma analogia entre a prova de teoremas matemáticos e a construção de algoritmos usando indução. E diz que embora esses dois processos sirvam para alcançar resultados diferentes, eles são muito similares. Além disso, Manber deixa claro que a indução não serve apenas para construir algoritmos recursivos, pois támbem podemos construir algoritmos iterativos pensando de forma indutiva.
"Although induction suggests implementation by recursion, this is not necessarily the case. (Indeed, we call this approach inductive rather than recursive to deemphasize recursive implementations.) In many cases, iterative implementation is just as easy, even if the algorithm was designed with induction in mind; iteration is also generally more efficient." Udi Manber
Então pessoal, não deixem de conferir as nossas postagens, e fiquem atentos ao trio: caso base, hipótese de indução e caso geral.
quinta-feira, 28 de junho de 2012
Torres de Hanói
Agora, vamos resolver indutivamente o problema das Torres de Hanói. Muita gente conhece o jogo, mas não sabe como resolvê-lo computacionalmente. As regras são as seguintes:
- Devemos mover um disco de cada vez.
- Um disco maior não pode ser colocado sobre um disco menor.
Idéia indutiva:
- Caso Base: para zero disco, o problema já está resolvido.
- Hipótese de Indução: vamos supor que o problema pode ser resolvido para n - 1 elementos. Esse truque libera o disco da base (maior disco).
- Caso Geral: basta invocar a hipótese de indução para mover os n- 1 discos e liberar o disco maior, e em seguida, invocamos a H.I. novamente para mover os n - 1 discos para o destino.
Situação inicial: todos os discos estão em A.
Hipótese de indução 1: vamos supor que os n - 1 discos iniciais serão movidos para o pino C.
Caso trivial: agora ficou fácil mover o disco maior para o destino, ou seja, para o pino B.
Hipótese de indução 2: agora vamos supor que os n - 1 discos que estão em C serão movidos para B.
E assim, chegamos a solução do problema!!!
As implementações decorrem da idéia apresentada acima.
- Implementação em Python
def hanoi(n, A, B, C):
if n > 0:
hanoi(n - 1, A, C, B)
print "Mova o disco " + str(n) + " de " + A + " para " + B
hanoi(n - 1, C, B, A)
- Implementação em Java
static void hanoi(int n, char A, char B, char C) {
if (n > 0) {
hanoi(n - 1, A, C, B);
System.out.println("Mova o disco " + n + " de " + A + " para " + B);
hanoi(n - 1, C, B, A);
}
}
Complexidade do algoritmo: vamos derivar a relação de recorrência T(n) = 2T(n - 1) + 1.
$T(n) = 2T(n - 1) + 1$
$T(n) = 2(2T(n - 2) + 1) + 1$
$T(n) = 4T(n - 2) + 2 + 1$
$T(n) = 4(2T(n - 3) + 1) + 2 + 1$
$T(n) = 8T(n - 3) + 4 + 2 + 1$
$...$
$T(n) = 2^n + 2^{n - 1} + 2^{n - 2} + ... + 2^2 + 2^1 + 2^0$
$T(n) = 2^n - 1$
$T(n) = O(2^n)$
Podemos concluir que a complexidade do algoritmo é limitada pela função exponencial. Na prática, se o número de discos for muito grande, a obtenção de uma solução torna-se inviável.
terça-feira, 26 de junho de 2012
Altura de Árvores Binárias: uma abordagem indutiva
Agora vamos criar um algoritmo que nos diz a altura de uma árvore binária. A altura de uma árvore binária pode ser definida como:
- Comprimento do maior caminho que vai da raiz até um nó folha. Onde o comprimento de um caminho é determinado pelo número de arestas que ele possui.
Idéia indutiva
- Caso Base: a altura de uma árvore vazia, ou com apenas um nó, é igual a zero.
- Hipótese de Indução: podemos assumir que já temos as alturas das subárvores esquerda e direita.
- Caso Geral: a altura da árvore será a maior dentre as alturas encontradas pela hipótese de indução mais 1.
A implementação a seguir decorre da idéia indutiva apresentada acima.
- Implementação em Python
def height(tree): if tree.left == tree.right: return 0 # arvore vazia if height(tree.left) > height(tree.right): return height(tree.left) + 1 return height(tree.right) + 1
- Implementação em C++
int height(ARVORE *t){
if(t == NULL || t->esq == t->dir)
return 0;
else
return max(height(t->esq), height(t->dir)) + 1;
}
domingo, 24 de junho de 2012
Palavras Palíndromas
Um palíndromo é uma palavra que pode ser lida tanto da esquerda para a direita como da direta para a esquerda. Por exemplo:
"A man, a plan, a canal, Panama!"
"Anotaram a data da maratona."
Vamos agora dar uma definição indutiva para o problema:
Idéia indutiva
- Caso Base: uma palavra com 1 caractere é um palíndromo.
- Hipótese de indução: vamos supor que a palavra sem o primeiro e o último caractere é um palíndromo.
- Caso Geral: Se o primeiro e o último caractere forem iguais e a hipótese de indução for verdadeira, então a palavra é um palíndromo.
- Implementação em Haskell
palindromo :: String -> Bool
palindromo [] = True
palindromo [a] = True
palindromo (x:xs) = (x == last xs) && (palindromo elem)
where
newlen = (length xs) – 1
elem = take newlen xs
- Implementação em C++ (versão iterativa)
bool palindromo(int n, char s[]){
int i = 0, j = n - 1;
while(i < j){
if(s[i] != s[j])
return false;
i++;
j--;
}
return true;
}
Assinar:
Postagens (Atom)











