Um paradigma é um conjunto de práticas que definem os modos de fazer de uma disciplina científica durante um certo período de tempo. Um paradigma é definido por:
– o que é para ser observado e avaliado
– as questões que devem ser feitas acerca de um tema de pesquisa
– como essas questões são estruturadas
– como os resultados das investigações científicas devem ser analisados
Em computação, do ponto de vista estrutural existem paradigmas racionalistas (tem origem na teoria da computação), tecnocráticos (origem na engenharia de software) e científicos (origem na teoria de algoritmos).
Existem, também, paradigmas de linguagens: orientadas a objetos, procedurais, lógicas, etc.
Alguns paradigmas de projeto de algoritmos:
● Recursividade: chama a si mesmo, direta ou indiretamente
● Tentativa e erro – backtracking: decompor o processo em um número finito de subtarefas que devem ser exploradas exaustivamente. Backtracking: selecione um caminho que pode levar à solução; se a escolha não se mostrar adequada então os caminhos derivados daquela escolha são ignorados e a busca pela solução retorna a um estágio anterior (backtracking)
● Divisão e conquista: Consiste em dividir o problema em partes menores, encontrar
soluções para as partes, e combiná-las em uma solução global
● Balanceamento
● Programação dinâmica: Se o mesmo subproblema precisa ser resolvido muitas vezes, então a abordagem é resolvê-lo uma vez e armazenar sua solução para uso posterior
● Algoritmos gulosos: Fazem a escolha que parece ser a melhor no momento
● Algoritmos aproximados
● Programação paralela
domingo, 11 de agosto de 2013
Hashing
Hashing é uma técnica de busca para encontrar elementos a partir de uma chave em um grande conjunto previamente armazenado.
Essa técnica se baseia em criar tabelas e utilizar funções de transformações de chaves de forma a obter o índice do elemento na tabela. Podem ocorrer elementos com índice igual. Essas 'colisões' podem ser tratadas com listas encadeadas ou com encadeamento aberto, que será explicado mais adiante.
Tratamento de colisões:
As colisões podem ser tratadas por meio de listas encadeadas, ou seja, caso um elemento tenha um índice onde já há outro elemento, ele é inserido logo após a raíz da lista e aponta para o elemento seguinte.
Podem, também, ser tratadas por endereçamento aberto:
Essa técnica se baseia em criar tabelas e utilizar funções de transformações de chaves de forma a obter o índice do elemento na tabela. Podem ocorrer elementos com índice igual. Essas 'colisões' podem ser tratadas com listas encadeadas ou com encadeamento aberto, que será explicado mais adiante.
Como fazer uma tabela hash
a tabela tem um tamanho fixo M. Basta calcular, usando uma função hash, um índice para cada chave de forma a distribuí-los na tabela entre 0 e M-1.Tratamento de colisões:
As colisões podem ser tratadas por meio de listas encadeadas, ou seja, caso um elemento tenha um índice onde já há outro elemento, ele é inserido logo após a raíz da lista e aponta para o elemento seguinte.
Podem, também, ser tratadas por endereçamento aberto:
- Hashing linear: caso o índice definido para um elemento já esteja ocupado, ele será inserido na primeira posição vazia disponível a partir daquele índice. Só que é perigoso a tabela encher e os registros começarem a se agrupar.
- Hashing quadrático: o elemento é inserido na posição correspondente ao quadrado do primeiro índice encontrado.
- Hashing duplo: caso haja colisão, é aplicada outra função hash para obter outro índice.
Função hash:
A função hash mais comum para chaves inteiras é chave % M. Lembrando que caracteres podem ser transformados em inteiros utilizando seu código ascii.
Outros métodos de ordenação
Além dos métodos de ordenação interna vistos anteriormente, ainda existem outros que devem ser ressaltados. Normalmente, são melhores para conjuntos específicos de dados.
Ordenação digital: é adequada para conjuntos específicos de dados, como por exemplo CEP, porque tem o mesmo número de dígitos e seguem uma distribuição uniforme. Numa central de correios, por exemplo, as cartas poderiam ser separadas primeiro pelo primeiro dígito do CEP, e dentro dessa separação, pelo segundo dígito e assim por diante. Alguns algoritmos: radixsort, bucketsort.
Counting sort: ordenar um conjunto de N letras:
Contar as frequências de cada letra usando a chave como índice
Calcular a frequência acumulada
Ordenar no array temporário
Copiar no array original
Esse eu nem entendi muito bem, admito.
Ordenação parcial: ordenar parcialmente é pegar apenas os k primeiros registros de um conjunto de tamanho n em ordem. Mas esses k primeiros são ordenados de acordo com o total, só que depois deles o resto pode ficar tudo desordenado que não tem problema, a gente só queria os primeiros k mesmo.
Ordenação externa: a ordenação externa é efetuada quando o conjunto a ser ordenado não cabe na memória interna. São muito difíceis e exigem cuidado, pois o acesso a dados na memória externa é extremamente custoso e é apenas sequencial. Portanto, a complexidade é analisada de acordo com o número de transferências de dados entre memória externa ou secundária e a interna. Isso faz com que os métodos de ordenação externa variem de acordo com a tecnologia atual.
O método mais eficiente é a ordenação por intercalação. O algoritmo pega blocos de dados na memória externa, os ordena na memória interna e intercala esses blocos, fazendo várias passadas pelo arquivo. Eles são cada vez maiores, até que todo o arquivo esteja ordenado. To com preguiça de descrever o método das fitas, porque exige um exemplo. Caso um dia alguém precise, basta perguntar.
Ordenação digital: é adequada para conjuntos específicos de dados, como por exemplo CEP, porque tem o mesmo número de dígitos e seguem uma distribuição uniforme. Numa central de correios, por exemplo, as cartas poderiam ser separadas primeiro pelo primeiro dígito do CEP, e dentro dessa separação, pelo segundo dígito e assim por diante. Alguns algoritmos: radixsort, bucketsort.
Counting sort: ordenar um conjunto de N letras:
Contar as frequências de cada letra usando a chave como índice
Calcular a frequência acumulada
Ordenar no array temporário
Copiar no array original
Esse eu nem entendi muito bem, admito.
Ordenação parcial: ordenar parcialmente é pegar apenas os k primeiros registros de um conjunto de tamanho n em ordem. Mas esses k primeiros são ordenados de acordo com o total, só que depois deles o resto pode ficar tudo desordenado que não tem problema, a gente só queria os primeiros k mesmo.
Ordenação externa: a ordenação externa é efetuada quando o conjunto a ser ordenado não cabe na memória interna. São muito difíceis e exigem cuidado, pois o acesso a dados na memória externa é extremamente custoso e é apenas sequencial. Portanto, a complexidade é analisada de acordo com o número de transferências de dados entre memória externa ou secundária e a interna. Isso faz com que os métodos de ordenação externa variem de acordo com a tecnologia atual.
O método mais eficiente é a ordenação por intercalação. O algoritmo pega blocos de dados na memória externa, os ordena na memória interna e intercala esses blocos, fazendo várias passadas pelo arquivo. Eles são cada vez maiores, até que todo o arquivo esteja ordenado. To com preguiça de descrever o método das fitas, porque exige um exemplo. Caso um dia alguém precise, basta perguntar.
Algoritmos de ordenação eficientes
Algoritmos de ordenação eficientes são mais recomendados para arquivos muito grandes porque - adivinha - eles são eficientes. Tem 4 algoritmos eficientes: Quicksort, Shellsort, Heapsort e Mergesort.
Quicksort: o quicksort é baseado no bubble sort - ou seja, realiza trocas. Dado um conjunto inicial de dados, é escolhido aleatoriamente um índice cujo conteúdo será chamado pivô. Feita essa escolha, um contador i é iniciado do início para o fim, percorrendo os valores e comparando-os com o pivô. Ao achar um elemento maior ou igual ao pivô, o íncide i para e inicia-se um j, do fim para o início, percorrendo os valores e procurando um menor ou igual ao pivô. Quando esse elemento é encontrado, os valores das posições i e j são trocados e o processo recomeça. Quando os contadores i e j se cruzam (ou seja, i aponta para uma posição à direita de j), são definidas duas partições do vetor e são feitas duas chamadas recursivas do quicksort, uma para cada partição. Antes de prosseguir, note que ao formar partições, todos os elementos de uma delas serão menores ou iguais ao pivô e, da outra, maiores ou iguais ao mesmo.
O tempo de execução do algoritmo depende do bom balanceamento das partições, ou seja, se o número de elementos está bem distribuído dos dois lados do pivô. No caso de um bom balanceamento, o algoritmo é O(n logn). Porém, para o pior caso, o algoritmo é quadrático, o que o torna inviável devido às chamadas recursivas.
Shellsort: o shellsort é um melhoramento do insertion sort. Ele analisa o vetor como uma intercalação de conjuntos e ordena cada um desses conjuntos com o insertion sort. Uma vez ordenados, o processo se repete com conjuntos maiores e, para isso, menos espaçados. Explicando melhor, o shellsort faz passadas pelo vetor analisando elementos equidistantes entre si, com uma distância h dada por uma expressão no início do algoritmo. Ao ordenar os subconjuntos, que são formados por elementos com distância h entre si, o h diminui. Assim, os subconjuntos incluirão mais e diversificados elementos. O processo se repete até que h seja 1, ou seja, elementos adjacentes. O h=1 caracteriza o insertion sort, que é sensível à ordenação parcial do vetor e, portanto, muito eficiente.
Não existe análise de complexidade definida para o shellsort, porque o resultado depende da sequência h escolhida. Para algumas sequências, o algoritmo pode ser O(n^3/2), O(n^7/6), O(n^1,25) ou O(n*(log(n))2), como sugerem alguns experimentos.
Heapsort: o heapsort é um algoritmo baseado no selection sort. Ele organiza o vetor de forma que o elemento dos índices 2k e 2k+1 são sempre menores do que o do índice k. Fica mais fácil visualizar essa estrutura em forma de árvore, em que um elemento tem dois filhos e cada filho tem outros dois filhos e por aí vai. O pai sempre é maior que os filhos. Para montar o heap, inicia-se da metade do vetor (afinal, daí pra frente já não haverão mais filhos) e, para cada elemento, é selecionado o maior filho e comparado com o pai. Caso o maior filho seja maior do que o pai, os dois são trocados. Quando é analisado um elemento cujos filhos tem filhos e é feita uma troca, a análise segue a cadeia de filhos até o final para que o heap se mantenha correto. Quando ele estiver finalmente montado, o elemento da primeira posição é trocado com o da última e, como o atual topo é menor, o heap é corrigido. Ao final da correção, o mesmo é feito, porém com a penúltima posição e por aí vai, até sobrar apenas a posição do topo e aí o vetor estará o ordenado.
O algoritmo tem custo total da construção do heap e da ordenação, totalizando O(n log2n).
Mergesort: o mergesort é um algoritmo baseado em intercalação. Dado um vetor de tamanho n, ele vai separando em vetores menores cujo tamanho é metade do vetor anterior e por aí vai, até que cada vetor tenha tamanho 1. Em seguida, vai juntando pares de vetores intercalando-os de maneira ordenada. É um algoritmo recursivo. Como usa espaço extra, é aconselhado para situações de mesclar dois vetores já ordenados, por exemplo.
Tem custo O(nlogn) e usa espaço extra de tamanho proporcional a n para todos os casos (insensível a ordenação inicial do vetor).
Quicksort: o quicksort é baseado no bubble sort - ou seja, realiza trocas. Dado um conjunto inicial de dados, é escolhido aleatoriamente um índice cujo conteúdo será chamado pivô. Feita essa escolha, um contador i é iniciado do início para o fim, percorrendo os valores e comparando-os com o pivô. Ao achar um elemento maior ou igual ao pivô, o íncide i para e inicia-se um j, do fim para o início, percorrendo os valores e procurando um menor ou igual ao pivô. Quando esse elemento é encontrado, os valores das posições i e j são trocados e o processo recomeça. Quando os contadores i e j se cruzam (ou seja, i aponta para uma posição à direita de j), são definidas duas partições do vetor e são feitas duas chamadas recursivas do quicksort, uma para cada partição. Antes de prosseguir, note que ao formar partições, todos os elementos de uma delas serão menores ou iguais ao pivô e, da outra, maiores ou iguais ao mesmo.
O tempo de execução do algoritmo depende do bom balanceamento das partições, ou seja, se o número de elementos está bem distribuído dos dois lados do pivô. No caso de um bom balanceamento, o algoritmo é O(n logn). Porém, para o pior caso, o algoritmo é quadrático, o que o torna inviável devido às chamadas recursivas.
Shellsort: o shellsort é um melhoramento do insertion sort. Ele analisa o vetor como uma intercalação de conjuntos e ordena cada um desses conjuntos com o insertion sort. Uma vez ordenados, o processo se repete com conjuntos maiores e, para isso, menos espaçados. Explicando melhor, o shellsort faz passadas pelo vetor analisando elementos equidistantes entre si, com uma distância h dada por uma expressão no início do algoritmo. Ao ordenar os subconjuntos, que são formados por elementos com distância h entre si, o h diminui. Assim, os subconjuntos incluirão mais e diversificados elementos. O processo se repete até que h seja 1, ou seja, elementos adjacentes. O h=1 caracteriza o insertion sort, que é sensível à ordenação parcial do vetor e, portanto, muito eficiente.
Não existe análise de complexidade definida para o shellsort, porque o resultado depende da sequência h escolhida. Para algumas sequências, o algoritmo pode ser O(n^3/2), O(n^7/6), O(n^1,25) ou O(n*(log(n))2), como sugerem alguns experimentos.
Heapsort: o heapsort é um algoritmo baseado no selection sort. Ele organiza o vetor de forma que o elemento dos índices 2k e 2k+1 são sempre menores do que o do índice k. Fica mais fácil visualizar essa estrutura em forma de árvore, em que um elemento tem dois filhos e cada filho tem outros dois filhos e por aí vai. O pai sempre é maior que os filhos. Para montar o heap, inicia-se da metade do vetor (afinal, daí pra frente já não haverão mais filhos) e, para cada elemento, é selecionado o maior filho e comparado com o pai. Caso o maior filho seja maior do que o pai, os dois são trocados. Quando é analisado um elemento cujos filhos tem filhos e é feita uma troca, a análise segue a cadeia de filhos até o final para que o heap se mantenha correto. Quando ele estiver finalmente montado, o elemento da primeira posição é trocado com o da última e, como o atual topo é menor, o heap é corrigido. Ao final da correção, o mesmo é feito, porém com a penúltima posição e por aí vai, até sobrar apenas a posição do topo e aí o vetor estará o ordenado.
O algoritmo tem custo total da construção do heap e da ordenação, totalizando O(n log2n).
Mergesort: o mergesort é um algoritmo baseado em intercalação. Dado um vetor de tamanho n, ele vai separando em vetores menores cujo tamanho é metade do vetor anterior e por aí vai, até que cada vetor tenha tamanho 1. Em seguida, vai juntando pares de vetores intercalando-os de maneira ordenada. É um algoritmo recursivo. Como usa espaço extra, é aconselhado para situações de mesclar dois vetores já ordenados, por exemplo.
Tem custo O(nlogn) e usa espaço extra de tamanho proporcional a n para todos os casos (insensível a ordenação inicial do vetor).
sábado, 10 de agosto de 2013
Algoritmos de ordenação simples
Temos 4 algoritmos básicos de ordenação simples: Bubble Sort, Insertion Sort, Selection Sort e Enumeration Sort.
Bubble Sort: o bubble é um algoritmo baseado em trocas. Ele percorre o vetor do início ao final comparando pares de elementos e trocando-os caso seja necessário. Ele faz isso quantas vezes forem necessárias até que a ordenação esteja completa. A cada passada, o maior elemento analisado já fica no lugar.
O bubble sempre será O(n²) comparações. Para trocas, seu melhor caso é O(1), pois não faz trocas caso os elementos já estejam ordenados, e caso médio e pior caso são O(n²).
É um algoritmo amplamente utilizado didaticamente, porém é ineficiente.
Insertion Sort: o insertion analisa cada elemento e o insere na posição correta em relação aos elementos já ordenados. Ou seja, é um algoritmo que não realiza trocas, mas sim movimentações (cada troca é composta de 3 movimentações). Um bom exemplo: imagine que você está jogando cartas. Para organizá-las na sua mão, você pega a carta à direita e, a partir da esquerda, encontra seu lugar e a insere ali, não é mesmo? Isso é o insertion sort.
O algoritmo é sensível à ordenação inicial do arquivo: para o pior caso, é O(n²) comparações, mas para o melhor (arquivo ordenado) é O(n). Idem para o número de movimentações.
Caso se tenha um arquivo quase ordenado ou poucos registros para inserir num arquivo ordenado, o insertion sort é mais recomendado do que métodos sofisticados.
Selection Sort: o selection seleciona no conjunto de n elementos o maior (ou menor, dependendo da ordem desejada) e o troca com a primeira posição. A seguir, repete o processo para n-1 elementos. Assim, a cada passada um elemento estará na posição correta.
O número de comparações também é O(n²), porém para cada elemento é feita uma troca (a troca é realizada mesmo se ele já estiver na posição correta). Assim, é O(n) para trocas.
Enumeration Sort: ele percorre o vetor e armazena em outro vetor do mesmo tamanho a posição relativa daquele índice na ordenação. Por exemplo, se tem-se
|9|3|7|4|2|8|, o enumeration cria um outro vetor com os seguintes valores:
|5|1|3|2|0|4|, que correspondem à posição que o elemento de mesmo índice no vetor original ocuparia num vetor ordenado.
Além de não ordenar de fato, o algoritmo ainda ocupa um espaço adicional do tamanho do vetor original, tornando-se extremamente ineficiente.
Bubble Sort: o bubble é um algoritmo baseado em trocas. Ele percorre o vetor do início ao final comparando pares de elementos e trocando-os caso seja necessário. Ele faz isso quantas vezes forem necessárias até que a ordenação esteja completa. A cada passada, o maior elemento analisado já fica no lugar.
O bubble sempre será O(n²) comparações. Para trocas, seu melhor caso é O(1), pois não faz trocas caso os elementos já estejam ordenados, e caso médio e pior caso são O(n²).
É um algoritmo amplamente utilizado didaticamente, porém é ineficiente.
Insertion Sort: o insertion analisa cada elemento e o insere na posição correta em relação aos elementos já ordenados. Ou seja, é um algoritmo que não realiza trocas, mas sim movimentações (cada troca é composta de 3 movimentações). Um bom exemplo: imagine que você está jogando cartas. Para organizá-las na sua mão, você pega a carta à direita e, a partir da esquerda, encontra seu lugar e a insere ali, não é mesmo? Isso é o insertion sort.
O algoritmo é sensível à ordenação inicial do arquivo: para o pior caso, é O(n²) comparações, mas para o melhor (arquivo ordenado) é O(n). Idem para o número de movimentações.
Caso se tenha um arquivo quase ordenado ou poucos registros para inserir num arquivo ordenado, o insertion sort é mais recomendado do que métodos sofisticados.
Selection Sort: o selection seleciona no conjunto de n elementos o maior (ou menor, dependendo da ordem desejada) e o troca com a primeira posição. A seguir, repete o processo para n-1 elementos. Assim, a cada passada um elemento estará na posição correta.
O número de comparações também é O(n²), porém para cada elemento é feita uma troca (a troca é realizada mesmo se ele já estiver na posição correta). Assim, é O(n) para trocas.
Enumeration Sort: ele percorre o vetor e armazena em outro vetor do mesmo tamanho a posição relativa daquele índice na ordenação. Por exemplo, se tem-se
|9|3|7|4|2|8|, o enumeration cria um outro vetor com os seguintes valores:
|5|1|3|2|0|4|, que correspondem à posição que o elemento de mesmo índice no vetor original ocuparia num vetor ordenado.
Além de não ordenar de fato, o algoritmo ainda ocupa um espaço adicional do tamanho do vetor original, tornando-se extremamente ineficiente.
Assinar:
Postagens (Atom)