ALGORITMOS DE ORDENAÇÃO – SORTING ALGORITHM

Oi pessoal! I’m back!

Aqui estou novamente com mais um post para o blog. Sei que faz muito tempo que não escrevo nada aqui, mas o tempo ta curto, muito curto!

Ontem na aula de Estrutura de dados II, tivemos uma aula sobre ordenação de vetores, ai me veio à idéia de colocar algo no blog sobre isso.

Irei apresentar pra vocês os métodos: Bubble Sort (bolha), Selection Sort (seleção), Insertion Sort (inserção), Merge Sort e Quick Sort.

Espero que gostem e ajudem vocês.

Abraços.

AGENDA

1. Introdução – Algoritmos de ordenação.

2. Características

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort

3. Tempo de ordenação

4. Implementações (Java)

5. Referências

1. INTRODUÇÃO – ALGORITMOS DE ORDENAÇÃO. [English]

Algoritmo de ordenação em ciência da computação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem, em outras palavras, efetua sua ordenação completa ou parcial. As ordens mais usadas são a numérica e a lexicográfica.

Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente.

Métodos simples

• Insertion sort
• Selection sort
• Bubble sort

Métodos sofisticados

• Quick sort
• Merge sort
• Heapsort
• Shell sort
• Radix sort
• Gnome sort
• Count sort
• Bogosort
• Bucket sort
• Cocktail sort

2. CARACTERÍSTICAS

Method Bubble – [English]

O bubble sort, ou ordenação por flutuação (literalmente “por bolha”), é um algoritmo de ordenação dos mais simples. A idéia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.

No melhor caso, o algoritmo executa n² / 2 operações relevantes, onde n representa o número de elementos do vetor. No pior caso é feitas 2n² operações. No caso médio, são feitas 5n² / 2 operações. A complexidade desse algoritmo é de Ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.

Method Selection – [English]

O selection sort ou ordenação por seleção, é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.

O algoritmo possui complexidade O(n²) enquanto que, por exemplo, os algoritmos Heapsort e Mergesort possuem complexidades O(nlogn).

Method Insert. – [English]

Insertion sort, ou ordenação por inserção, é um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer.

• Menor número de trocas e comparações entre os algoritmos de ordenação Ω(n) quando o vetor está ordenado.
• Pior caso O(n²)

Method Merge Sort – [English]

O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.

Sua idéia básica é que é muito fácil criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, ele divide a sequência original em pares de dados, ordena-as; depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.

Os três passos úteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:

1. Dividir: Dividir os dados em subsequências pequenas;
2. Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;
3. Combinar: Juntar as duas metades em um único conjunto já classificado.

• Complexidade de tempo: O(n log₂ n)
  Complexidade de espaço: O(n)

Method Quick Sort – [English]

O algoritmo Quicksort é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960, quando visitou a Universidade de Moscovo como estudante. Ele criou o ‘Quicksort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais fácil e rapidamente. Foi publicado em 1962 após uma série de refinamentos.

O Quicksort adota a estratégia de divisão e conquista. Os passos são:

1. Escolha um elemento da lista, denominado pivô;
2. Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sublistas não ordenadas. Essa operação é denominada partição;
3. Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;

A base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo é finito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.

• Complexidade de tempo: O(n lg₂ n) no melhor caso e no caso médio e O(n²) no pior caso;
• Complexidade de espaço: O(lg₂ n) no melhor caso e no caso médio e O(lg₂ n) no pior caso. R. Sedgewick desenvolveu uma versão do Quicksort com partição recursão de cauda que tem complexidade O(lg₂ n) no pior caso.

3.TEMPO DE ORDENAÇÃO

Bubble Sort

• Applied to 1 array containing 100000 items:
• Elapsed Time: 106.034 seconds
• Approximate Compute Time: 86.128 seconds
• Number of comparisons: 4999950000
• Number of copies: 7508838831

Selection Sort

• Applied to 1 array containing 100000 items:
• Elapsed Time: 63.782 seconds
• Approximate Compute Time: 51.856 seconds
• Number of comparisons: 4999950000
• Number of copies: 299997

Insertion Sort

• Applied to 1 array containing 100000 items:
• Elapsed Time: 40.360 seconds
• Approximate Compute Time: 32.878 seconds
• Number of comparisons: 2491283628
• Number of copies: 2491383637

Merge Sort

• Applied to 1 array containing 100000 items:
• Elapsed Time: 0.047 seconds
• Approximate Compute Time: 0.047 seconds
• Number of comparisons: 1566709
• Number of copies: 3400000

QuickSort

• Applied to 1 array containing 100000 items:
• Elapsed Time: 0.031 seconds
• Approximate Compute Time: 0.031 seconds
• Number of comparisons: 2099482
• Number of copies: 812876

4. IMPLEMENTAÇÕES (JAVA)

Method Bubble

public class Bubble {

public static void bubbleSort(int[] a) {

for (int i = 0; i < a.length – 1; i++) {

for (int j = 0; j < a.length – 1; j++) {

if (a[j] > a[j + 1]) {

swap(a, j, j + 1);

}

}

}

}

private static void swap(int[] a, int i, int j) {

int temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}

Method Selection Sort

public class Selection {

public static void SelectionSort(int[] v) {

int index_min, aux;

for (int i = 0; i < v.length; i++) {

index_min = i;

for (int j = i + 1; j < v.length; j++) {

if (v[j] < v[index_min]) {

index_min = j;

}

}

if (index_min != i) {

aux = v[index_min];

v[index_min] = v[i];

v[i] = aux;

}

}

}

}

Method Inserction Sort

public class Insertion {

public static void insertionSort(int[] numbers) {

for (int i = 0; i < numbers.length; i++) {

int copyNumber = numbers[i];

int j = i;

while (j > 0 && copyNumber < numbers[j - 1]) {

numbers[j] = numbers[j - 1];

j–;

}

numbers[j] = copyNumber;

}

}

}

Method Merge Sort

public class Merge {

/**

* Algoritmo Merge Sort.

*/

public static void mergeSort(Comparable[] a) {

Comparable[] tmpArray = new Comparable[a.length];

mergeSort(a, tmpArray, 0, a.length – 1);

}

/**

* Método interno que faz chamadas recursivas

*/

private static void mergeSort(Comparable[] a, Comparable[] tmpArray,

int left, int right) {

if (left < right) {

int center = (left + right) / 2;

mergeSort(a, tmpArray, left, center);

mergeSort(a, tmpArray, center + 1, right);

merge(a, tmpArray, left, center + 1, right);

}

}

/**

* Metódo interno que ordena duas partes de um subarray.

*/

private static void merge(Comparable[] a, Comparable[] tmpArray,

int leftPos, int rightPos, int rightEnd) {

int leftEnd = rightPos – 1;

int tmpPos = leftPos;

int numElements = rightEnd – leftPos + 1;

// loop principal

while (leftPos <= leftEnd && rightPos <= rightEnd)

if (a[leftPos].compareTo(a[rightPos]) <= 0)

tmpArray[tmpPos++] = a[leftPos++];

else

tmpArray[tmpPos++] = a[rightPos++];

while (leftPos <= leftEnd)

tmpArray[tmpPos++] = a[leftPos++];

while (rightPos <= rightEnd)

tmpArray[tmpPos++] = a[rightPos++];

// Copiando o array temporário de volta

for (int i = 0; i < numElements; i++, rightEnd–)

a[rightEnd] = tmpArray[rightEnd];

}

}

Method Quick Sort

import java.util.Arrays;

import java.util.Random;

public class QuickSort<E extends Comparable<? super E>> {

public static final Random RND = new Random();

private void swap(E[] array, int i, int j) {

E tmp = array[i];

array[i] = array[j];

array[j] = tmp;

}

private int partition(E[] array, int begin, int end) {

int index = begin + RND.nextInt(end – begin + 1);

E pivot = array[index];

swap(array, index, end);

for (int i = index = begin; i < end; ++i) {

if (array[i].compareTo(pivot) <= 0) {

swap(array, index++, i);

}

}

swap(array, index, end);

return (index);

}

private void qsort(E[] array, int begin, int end) {

if (end > begin) {

int index = partition(array, begin, end);

qsort(array, begin, index – 1);

qsort(array, index + 1, end);

}

}

public void sort(E[] array) {

qsort(array, 0, array.length – 1);

}

// Exemplo de uso

public static void main(String[] args) {

// Ordenando Inteiros

Integer[] l1 = { 5, 1024, 1, 88, 0, 1024 };

System.out.println(“l1  start:” + Arrays.toString(l1));

QuickSort<Integer> qs = new QuickSort<Integer>();

qs.sort(l1);

System.out.println(“l1 sorted:” + Arrays.toString(l1));

// Ordenando Strings

String[] l2 = { “gamma”, “beta”, “alpha”, “zoolander” };

System.out.println(“l2  start:” + Arrays.toString(l2));

QuickSort<String> qs2 = new QuickSort<String>();

qs2.sort(l2);

System.out.println(“l2 sorted:” + Arrays.toString(l2));

}

}

5. REFERÊNCIAS

[Br]

1. http://pt.wikipedia.org/wiki/Algoritmo_de_ordenação
2. http://pt.wikipedia.org/wiki/Bubble_sort
3. http://pt.wikipedia.org/wiki/Selection_sort
4. http://pt.wikipedia.org/wiki/Insertion_sort
5. http://pt.wikipedia.org/wiki/Merge_sort
6. http://pt.wikipedia.org/wiki/Quick_sort

[En]

1. http://en.wikipedia.org/wiki/Sorting_algorithm
2. http://en.wikipedia.org/wiki/Bubble_sort
3. http://en.wikipedia.org/wiki/Selection_sort
4. http://en.wikipedia.org/wiki/Insert_sort
5. http://en.wikipedia.org/wiki/Merge_Sort
6. http://en.wikipedia.org/wiki/Quick_Sort

Nestes dois sites vocês poderão ver animações em (Java Applet) dos métodos de ordenação apresentados aqui.

These two sites you may see an animation of the sorting algorithms presented here.

http://www.sorting-algorithms.com/

http://math.hws.edu/TMCM/java/xSortLab/

Warriors of the Net.

O filme ilustra por meio de animação 3D como a comunicação é feita entre do O filme ilustra por meio de animação 3D como a comunicação é feita entre dois comutadores na Internet. Hoje em dia é recomendado para todos em especial os profissionais da área de informática e tecnologia.

Este vídeo foi desenvolvido pela Metalab com o apoio da empresa Ericsson, o mesmo pode ser encontrado no site http://www.warriorsofthe.net/ o qual é recomendável para uma visita, é o mínimo que podemos fazer para apoiar o projeto.
Worriors of the net is © Copyright 2002 Gunilla Elam, Tomas Stephanson, Niklas Hanberger All rights reserved.

–

Did you ever wonder how the Internet works? How does a router look like? What color does a IP packet have? How does a IP packet travel through firewall. All the answers and many more can be found in the Warriors of the net move. It is available in many different languages. It is the prefect tool for introducing Internet to novice users. It helps the newcomers visualize how the Net works. It is free to download for non commercial use.

Fonte: warriorsofthe.net

Flash CS4 e pontos de fuga?

Eu, sempre preocupado com o mundo Apple, acabo nunca postando nada no TI Developer, mas ontem fiz umas pesquisas interessantes com Flash e resolvi compartilhar com os nobres leitores deste nobre blog.

Esse é um exemplo de um workflow de duas horas de trabalho com Flash CS4. Não funciona em CS3, nem pense nisso!

Ontem me deparei com uma situação interessante: a empresa onde trabalho está fazendo um layout mais arrojado para um desses sites cheios de flash e um dos recursos do layout envolve um quadrado que gira em torno do próprio eixo. Um lado do quadrado mostra um conteúdo, e outro lado mostra outro conteúdo. Simples, não? Não.
Um programador que trabalha comigo resolveu usar o Papervision 3D. A princípio ele fez 18 cubos com lateral 0. Os cubos eram idênticos a quadrados. A face da frente e a de trás possuiam um movieclip diferente cada. O efeito funcionou. Mas… (sempre tem um “mas”) o flash precisa renderizar quadro-a-quadro 18 cubos girando. Isso significa que o SWF ficou deveras pesadíssimo.

Como contornar isso? A primeira resolução foi acabar com essa folia de cubos. Cada “quadrado” tinha 4 faces inúteis e duas faces com movieclips quando poderíamos usar só uma. Acabar com esse POG deixou o negócio mais leve, mas ainda estava pesado demais para a web.

Então eu entrei na jogada. Por que usar Papervision? O flash CS4 já dá suporte a 3 dimensões. E girar uma droga dum quadradinho não deveria ser tão difícil! Girar 18 quadradinhos deveria dar no mesmo.
Eu sou um programador de ActionScript 2. Embora saiba programar em AS3, não gosto muito porque acho o AS3 muito enrolado com coisas óbvias. Mas enfim, resolvi fuçar os arquivos de ajuda atrás de uma solução mais simples.

Eis minha idéia:
Pegamos o conteúdo de cada face.
Criamos um MovieClip.
O MovieClip terá 2 quadros. Cada um vai comportar um dos dois conteúdos.
Quadrados são bidimensionais. Então sempre que girarmos o quadrado, poderemos nos deparar com 2 situações:
ou haverá um quadro em que ele ficará invisível ou, de um quadro para outro veremos uma e outra face, sem intermédios.
Justamente nessa mudança mudaremos do quadro 1 para o 2, dando a impressão que estamos vendo o verso do quadro, quando na verdade só vemos outro quadro. Entendeu? =D

Ok.. Você leu até aqui e não entendeu picas? Então vamos pôr a mão na massa e irás entender.

Estou usando Windows XP aqui no trabalho, então os atalhos de teclado aqui não valem para quem usa Mac, beleza?

Na maioria das vezes, quem usa mac só precisa trocar o [Ctrl] por [Command] e [Enter] por [Return]. Mas vá, se vc que lê isso tem flash, saberá se virar sozinho, certo?

1. Criando o MovieClip

Abri meu flash e criei um novo documento em AS3. Apertei [Ctrl+F8]. Dei o name de “bola”, type “MovieClip”. [Enter].
Apertei a tecla [R] do meu teclado para fazer um quadrado. No painel procurei o “fill and stroke” e deixei sem linhas, só preenchimento. Criei um retângulo. Cliquei depois nesse retângulo e deixei com H em -100, Y em -100 também, W em 200 e H em 200 também. Pronto. Um quadrado. Um quadrado chamado “bola”. “Quadrado” tem 8 letras. “Bola” tem 4 letras. Muito mais econômico.
Deixei meu quadrado vermelho “#FF0000″.
Então apertei [F6]. Meu quadro na linha do tempo foi duplicado. No quadro 2 deixei esse quadrado verde “#006600″.
Criei um novo layer na linha do tempo. Cliquei no quadro 1 desse novo layer, apertei [F9] e escrevi isso:

stop();

Pronto. Simples.

2. Posicionando o MovieClip

Voltei para o “Scene 1″. Apertei [Ctrl+L] para ver minha biblioteca e arrastei o MovieClip “bola” para o palco. Segurei [Ctrl+K]. Deixei a opção “To stage” acionada. Cliquei no MovieClip, apertei [Ctrl+Alt+2] e depois [Ctrl+Alt+5]. Agora meu quadrado está centralizado. Na janela properties eu instanciei ele como “bola”.
Criei um novo layer na linha do tempo. Cliquei no frame em branco desse layer. Apertei [F9] de novo. Agora… ActionScript!

3. Criando a animação

Primeiro vamos fuçar o método “Tween”.

Copiei e colei um código de animação e troquei o nome do MovieClip ali. Ficou assim:

import fl.transitions.*;
import fl.transitions.easing.*;

var t1:Tween=new Tween(bola,”x”,Regular.easeIn,0,100,2,true);

Vamos por partes então. Linhas 1 e 2 importam bibliotecas que vou usar no tween.
A linha 4 cria um objeto Tween. Ele vai incrementar a coordenada x do MovieClip chamado “bola”, de 0 a 100, em 2 segundos, usando uma suavização conhecida como “easeIn”. Ou seja, vai começar lento e terminar rápido.
Não quero esse ritmo, então trocarei por “None.easeNone”. Se eu der [Ctrl+Enter] eu verei meu quadrado percorrendo um certo espaço. Parece uma lesma.
Enfim… sei que posso usar qualquer propriedade do meu MovieClip na classe Tween. Vou substituir o “x” por “rotationY”, porque quero girá-lo. A propriedade “rotationY” usa o princípio de graus. Quero que meu quadrado vire ao contrário. Isso serão 180 graus. Então meu código ficou assim:

import fl.transitions.*;
import fl.transitions.easing.*;

var t1:Tween=new Tween(bola,”rotationY”,None.easeNone,0,180,2,true);

Girou! Aêê! Quem precisa de PaperVision pra fazer isso?
Continuemos. Eu preciso mudar a face do bagulho quando chegar a 90 graus. Para isso vou construir um listener. Não quero usar “onEnterFrame” porque fica lerdo e ocupa memória. Então vou fazer o listener sobre o Tween.

t1.addEventListener(TweenEvent.MOTION_CHANGE, teste);

Simples né? Não funciona, pois não existe a função “teste” ainda. Então criei uma função “teste”:

function teste(e:Event):void {
trace(1);
}

Pronto. Agora quando o quadrado girar receberei o valor “1″ no output. Isso serve para eu ver se o listener funciona direitinho.
Vamos fazer isso ficar mais útil e me informar a posição do quadrado.
Ao invés de:

trace(1);

vou usar

trace(e.target.obj.rotationY);

Veja que interessante: e.target aponta para meu Tween. “obj” é o objeto que o Tween está alterando, no caso, “bola”; e “rotationY” é propriedade de “bola”.
Agora posso mudar o quadro quando chegar em 90 graus. Meu código ficou assim:

import fl.transitions.*;
import fl.transitions.easing.*;

var t1:Tween=new Tween(bola,”rotationY”,None.easeNone,0,180,2,true);

t1.addEventListener(TweenEvent.MOTION_CHANGE, teste);

function teste(e:Event):void {
if (e.target.obj.rotationY>90) {
e.target.obj.gotoAndStop(2);
}
}

4. Corrigindo o ponto de fuga

Maravilha! Parece que mudou mesmo. Tudo certo? Então pronto.
Pronto nada. Tem um porém nessa coisa toda. Vamos mudar a posição desse MovieClip.
Ponho meu X em 434 e meu Y em 284. Agora vejamos. Percebe o que aconteceu? Não? Então vamos deixar mais lento.
Mude a linha 4 para ficar assim (olha o 5 ali):

var t1:Tween=new Tween(bola,”rotationY”,None.easeNone,0,180,5,true);

Agora execute de novo. Viu agora? O quadrado ficou verde antes dos 90 graus! Mas como isso!?
Muita calma nessa hora.
Em primeiro lugar o flash não mudou o quadro nem antes nem depois da hora que foi definida. Passou de 90 graus, é instantâneo. A pergunta não é “porque ele mudou antes dos 90 graus”, mas “por que os 90 graus não estão perpendiculares à ‘câmera’?”.
Simples: o Flash possui um ponto de fuga. Quando o MovieClip estava centralizado, o ponto de fuga ficava exatamente no meio do quadrado e ele mudava de cor exatamente no momento em que as face fica visível do lado oposto. Quando deslocamos o MovieClip para outro ponto no palco, o ponto de fuga mudou em relação a ele e a visão dos 90 graus mudou. Se você não entendeu isso, pegue uma carta de baralho e deixe-a na perpendicular até que ela pareça uma linha. Agora desloque o seu braço para a direita ou esquerda sem mudar a posição da carta em relação ao braço. Vê que uma face ficou mais visível né? Pois é. O flash simula perspectivas.

Meu POG falhou. Mas não desisto!
Pensando com meus botões concluí: deve existir um meio de mudar o ponto de fuga do movieclip!
E tem. Vamos lá:

Podemos declarar um objeto do tipo “PerspectiveProjection” (com p maiúsculo) e mudar o valor de seu “projectionCenter”.
O MovieClip ainda tem uma propriedade chamada “perspectiveProjection” (com p minúsculo). Se atribuirmos essa nova variável a seu resultado final, conseguimos mudar o ponto de fuga. Os novos valores serão o centro do objeto: as coordenadas x e y. Meu código ficou assim:

import fl.transitions.*;
import fl.transitions.easing.*;

var t1:Tween=new Tween(bola,”rotationY”,None.easeNone,0,180,5,true);

t1.addEventListener(TweenEvent.MOTION_CHANGE, teste);
var pp:PerspectiveProjection = new PerspectiveProjection();

function teste(e:Event):void {
pp.projectionCenter=new Point(e.target.obj.x,e.target.obj.y);
e.target.obj.transform.perspectiveProjection=pp;
if (e.target.obj.rotationY>90) {
e.target.obj.gotoAndStop(2);
}
}

Simples, apesar de tudo. Declarei uma variável, atribuí um valor e troquei uma propriedade. Só isso. Não se assuste com o tamanho do negócio, na verdade é só variáveis de nome grande, nada mais.

5. Corrigindo a inversão do MovieClip

Mas ainda não terminei. Preciso saber se meu MovieClip exibe o conteúdo corretamente.
Abrindo o MC “bola”, vou ao quadro 1 e ponho uma grande letra “R” no meio do quadrado. No quadro 2 eu ponho uma letra “K”.

Executando… Mas que diabos! A letra “K” inverteu!
É claro, eu girei o MC inteiro. Se houvesse só um quadro para ver, eu veria ele invertido, espelhado.
Eu pensei a princípio em fazer uma verificação do ângulo do quadrado e quando ele chegasse em 90 graus eu mudaria para -90 graus e terminaria em 0. Isso exigiria dois tweens diferentes. Mas tem uma solução muito mais simples. Vamos a ela:

No quadro 2, vou selecionar tudo. Quadrado e texto. Dou um [F8] para salvar como MovieClip. Ok. Voltano ao quadro 2… vamos dar um nome menos idiota a esse MC. Vou instanciá-lo como “mc”. Simples!
Agora dou um [F7] no quadro 2 do “Layer 2″. E agora [F9].
Escrevo assim ali:

this.mc.rotationY = 180;

Epa.. o quadrado verde foi pro outro lado. A solução também é simples. O “hotpoint” do MC está no topo, à esquerda. É só entrar no MC e alinhá-lo no meio.

Voilá.. um quadrado que gira e não ocupa muita memória e ainda funciona em todas as regiões do palco. =D

Divirtam-se com moderação.

Passos do Algoritmo de Huffman

David A. Huffman, nascido em Ohio, formou-se em Engenharia Elétrica em 1944, sua maior contribuição para a humanidade foi à técnica computacional conhecida como o Código de Huffman, o método para compactar informações que está presente neste momento no seu Ipod, na sua câmera digital, nos modems de Internet, nas TVs de alta definição e até em invenções mais antigas como o seu telefone ou fax do seu trabalho.

Este código foi desenvolvido durante seu doutorado, em 1951, no MIT (Massachussets Institute of Technology), uma das maiores universidades tecnológicas do mundo. Aos 26 anos, o genial Huffman superou o método ensinado em aula por seu autor, o professor Robert Fano, e criou seu proprio codigo para compactar dados.

Mas o que o algoritmo de Huffman faz ?

A compressão pelo algoritmo de Huffman reduz o tamanho do código usado para representar os símbolos de um alfabeto. Símbolos do alfabeto que ocorrem frequentemente são atribuídos por codigos mais curtos. A estratégia geral é permitir ao tamanho do código variar de caracter para caracter e de assegurar que o código utilizado seja menor.

A compressão de Huffman é feita através da construção de uma árvore binária usando um simples conjunto de exemplo. Isso é feito arranjando os símbolos do alfabeto em ordem decrescente de probabilidade. Então repetidamente adicionando duas menores probabilidades e reorganizando. Este processo se repete até a soma das probabilidades dos dois últimos símbolos ser igual a 1.

Se não for obtido uma probabilidade de 1 nos dois últimos símbolos, provavelmente existe um erro no processo.

Estes diagramas mostram como a árvore de codificação associada à codificação de Huffman é construída:

FFFFFAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAEEEEEEEEEDDDDDDDDDDDDDDDDBBBBBBBBBBBBBCCCCCCCCCC
CC

fonte:

wiki

books.google

SpeedTest (internet)

Se você já teve a duvida se seu provedor de internet está lhe dando toda velocidade que você contratou, esse site lhe ajuda a tirar essa duvida.

O SpeedTest verifca:
Download
A velocidade na qual os dados são enviados a partir da Internet para o seu computador

Upload
A velocidade na qual os dados são enviados do seu computador para à Internet ou outro computador.

Ping
O tempo que leva em milissegundos para um pequeno pedaço de dados serem enviados a partir do seu computador para a Internet e voltar

Faça o teste: SpeedTest

// ++++++++++++++++++++++++++++++++++++++++

Use Speedtest.net to test the speed of your Internet connection. See if you are getting what you pay for or share your results with others!

Download Speed
The speed at which data is sent from the Internet to your computer

Upload Speed
The speed at which data is sent from your computer to the Internet

Ping (Latency)
The time it takes in milliseconds for a small piece of data to be sent from your computer to the Internet and back

Do the test: SpeedTest