Lista de algoritmos

Lista de algoritmos


Origem: Wikipédia, a enciclopédia livre.

Ir para: navegação, pesquisa

Abaixo segue a lista de algoritmos, veja também a Lista de estruturas de dados e a Lista de termos relacionados aos Algoritmos e Estruturas de Dados.

Índice

[esconder]

• 1 Algorítmos Combinatórios

• 2 Algoritmos de Grafos

• 3 Algoritmos de Busca

• 4 Algoritmos de pesquisa em Strings

• 5 Algoritmos de Classificação

• 6 Algoritmos de Compressão

• 7 Geometria Computacional

• 8 Computação Gráfica

• 9 Algoritmos Criptográficos

• 10 Algoritmos de Sistemas Distribuídos

• 11 Algoritmos Numéricos

• 12 Processamento de sinais digitais

• 13 Algoritmos de números teóricos

• 14 Álgebra numérica

• 15 Otimização

• 16 Análise Gramatical

• 17 Algoritmos Quânticos

• 18 Algoritmos Evolutivos

• 19 Outros


[editar] Algorítmos Combinatórios

Algorítmos Combinatórios Gerais

• Algoritmo Busca-Cíclica de Floyd: encontra ciclos em iterações

• Geradores de Números Pseudo-aleatórios: produzem números estatísticamente aleatórios

o Blum Blum Shub: um gerador de números pseudo-aleatórios com prova de segurança

o Algoritmo de Yarrow

[editar] Algoritmos de Grafos

Veja artigo principal Teoria de Grafos

• Algoritmo de Bellman-Ford: calcula o caminho mais curto num grafo pesado (onde alguns dos pesos das extremidades podem ser negativos)

• Algoritmo de Dijkstra: calcula o caminho mais curto num grafo com peso absoluto das extremidades.

• Algoritmo de Floyd-Warshall: resolve o problema do caminho mínimo entre todos os partes de vértices em um grafo com direção e peso.

• Algoritmo de Kruskal: encontra a árvore de extensão mínima para um grafo.

• Algoritmo de Prim: encontra a árvore de extensão mínima para um grafo.

• Algoritmo de Boruvka: encontra a árvore de extensão mínima para um grafo.

• Algoritmo de Ford-Fulkerson: calcula o vazão máxima num grafo.

• Algoritmo de Edmonds-Karp: implementação de Ford-Fulkerson.

• Nonblocking Minimal Spanning Switch digamos, para um telephone exchange.

• Spring based algorithm: algoritmo para desenhar grafos.

• Algoritmo das economias: algoritmo para encontrar a menor rota em um grafo.

[editar] Algoritmos de Busca

• Busca linear: encontra um elemento numa lista não ordenada

• Busca binária: encontra um elemento numa lista ordenada

• Pesquisa binária numa sequência cíclica: encontra o menor elemento numa lista formada por elementos em sequencia de forma cíclica.

• Pesquisa binária em sequências de intervalo desconhecido: neste caso, não se sabe o tamanho da sequência. Encontra um intervalo onde está o elemento procurado, depois aplica busca binária.

• Busca em árvore binária

• Busca em largura: percorre uma árvore nível por nível

• Busca em profundidade: percorre um árvore galho por galho

• Busca pela melhor escolha: percorre uma árvore em uma ordem de provável importância, usando uma fila de prioridades.

• Busca A*: um caso especial da busca pela melhor escolha

• Busca Hash: encontra um elemento em uma lista indexada por uma tabela hash

• Predictive search: binary like search which factors in magnitude of search term versus the high and low values in the search. Sometimes called a dictionary search.

[editar] Algoritmos de pesquisa em Strings

• Algoritmo de Knuth-Morris-Pratt.

• Algoritmo de Rabin-Karp.

• Algoritmo de Boyer-Moore.

• Algoritmo de Boyer-Moore-Horspool.

• Algoritmo de Baeza-Yates-Gonnet. (Shift-And, Shift-Or ou Bitap)

[editar] Algoritmos de Classificação

• Bogosort: engraçado e lento.

• Classificação Bolha: para cada par de índices, mude os ítens de posição se fora de ordem.

• Bucket sort

• Classificação Pente: Parecido com o método Bolha.

• Cocktail sort: Bubble sort bidirecional

• Count sort: Ordena um arranjo posicionando o valor devido ao seu tamanho comparado aos outros.

• Counting sort

• Gnome sort

• Heapsort: converta a lista num heap, continue removendo o maior elemento do heap e adicionando-o no fim da lista.

• Ordenação por inserção: determina à qual posição o ítem atual pertence na lista dos classificados e o insere ali.

• Classificação Fusão: Classifique a primeira e a segunda metade da lista separadamente, e então junte as listas classificadas.

• Pancake sorting

• Pigeonhole sort

• Quicksort: divida a lista em dois, com todos os ítens da primeira lista sendo menores que os ítens da segunda e então classifique as duas listas. Certamente o método de escolha.

• Radix sort: classifica strings letra por letra.

• Ordenação por seleção: escolha o menor dos elementos restantes, adicione ao final/início da lista classificada.

• Shell sort: uma tentativa de otimização do insertion sort.

• Smoothsort: É um variação do Heap sort

• Stupid sort

• Topological sort

[editar] Algoritmos de Compressão

• Codificação aritmética: Codificação de Entropia (sempre alcança a entropia da fonte)

• Método de Burrows-Wheeler: preprocessamento útil para compressão sem perda de dados

• DEFLATE: compressão sem perda de dados

• Codificação Delta: apoio para compressão de dados na qual dados seqüênciais acorrem freqüentemente.

• Codificação de Huffman: Codificação de Entropia por Palavras-Código

• Incremental encoding: codificação delta aplicada à uma seqüencia de strings

• LZW: Codificaçao baseada em dicionário (Lempel, Ziv, Welch)

• LZ77: Codificaçao baseada em dicionário com "janela deslizante" (sliding window em inglês). A base do DEFLATE.

• LZ78: Codificaçao baseada em dicionário da qual evoluiu o LZW.

• Codificação Run-length: Codificaçao por Comprimento de Sequencia



Compressão de dados



Teoria

Com perda • Sem perda



Tipo de dados de origem

áudio • banda • imagens • vídeo



Métodos

Lista de algoritmos - Algoritmos de Compressão





[editar] Geometria Computacional

• Algoritmo Embrulho de Presente: determinando o envoltório convexo de um conjunto de pontos.

• Exame de Graham determina o envoltório convexo de um conjunto de pontos num plano.

• Teste Ponto no Polígono: testa se um dado ponto está ou não dentro de um polígono.

[editar] Computação Gráfica

• Algoritmo de linha de Bresenham: plota pontos de uma matriz bidimensional para traçar uma linha reta entre dois pontos especificos.

• Algoritmo do Pintor: detecta partes visíveis de um cenário tridimensional.

• Traçado de raios: interpretação de imagens reais.

[editar] Algoritmos Criptográficos

Veja também Tópicos de Criptografia para um 'glossário analítico'

• Criptografia de chave simétrica (chave secreta):

o Padrão de Criptografia Avançada (AES), vencedor da competição NIST

o Blowfish

o Padrão de Criptografia de Dados (DES), também chamado de DE, vencedor da competição NBS, substituído pelo AES para a maioria dos propósitos.

o IDEA

o RC4

• Criptografia assimétrica (de chave pública) ou Assinatura digital:

o DSA

o ElGamal

o RSA

o NTRUEncrypt

• Funções Criptográficas de Condensação de Mensagem:

o MD5

o MD4

o RIPEMD-160

o SHA-1

o HMAC: autenticação chaveada de mensagem codificada.

• Outros

o Diffie-Hellman: troca de chaves.

[editar] Algoritmos de Sistemas Distribuídos

• Lamport ordering: ordenação parcial de eventos baseado na relação dos acontecimentos passados

• Algoritmo Instantâneo: um instantâneo é o processo de captura do estado global de um sistema

• Ordenação de Vetor: uma ordenação total de eventos.

[editar] Algoritmos Numéricos

Veja também artigo principal Análise Numérica and Lista de tópicos de análise numérica

• Algoritmo de De Boor: calcula fendas.

• Algoritmo de De Casteljau: calcula as curvas de Bezier.

• Método da Falsa Posição: aproxima raízes de uma função.

• Eliminação de Gauss-Jordan: resolve sistemas de equações lineares.

• Algoritmo de Gauss-Legendre: calcula os dígitos de pi

• Método de Newton: encontra os zeros de uma função com cálculo

• Funções de Arredondamento: modos clássicos de arredondar números.

• Método da Secante: aproxima raízes de uma função.

• Shifting nth-root algorithm: extração da raiz dígito a dígito.

• Raiz Quadrada: aproxima a raiz quadrada de um número.

[editar] Processamento de sinais digitais

• CORDIC: técnica de cálculo rápido de função trigonométrica.

• Fast Fourier transform: determina as freqüencias contidas num (segmento de um) sinal.

o Algoritmo de Cooley-Tukey FFT

• Rainflow-counting algorithm: Reduz uma história de stress complexa em uma contagem de revezes de stress elementares para uso em análise de fadiga.

• Osem: algoritmo para processamento de imagens médicas.

[editar] Algoritmos de números teóricos

• Algoritmo de Euclides: calcula o MDC.

• Fatorização de Inteiros: quebra um inteiro em seus fatores primitivos.

o Divisão por tentativas

o Fatorização da curva elíptica de Lenstra

o Pollard's rho algorithm

o Pollard's p-1 algorithm

o Congruence of squares

o Quadratic sieve

o Special number field sieve

o General number field sieve

• Algoritmo de Multiplicação: rápida multiplicação de dois números.

• Teste de Primitividades: determina se um dado número é primitivo.

o Teste de primitividade de Miller-Rabin

o Sieve of Eratosthenes: produz uma lista dos primeiros primitivos

o AKS primality test

[editar] Álgebra numérica

• Algoritmo de Buchberger: encontra a base de Grobner.

• Algoritmo de Eigenvalue

• Exponentiating by squaring: calcula rápidamente a potência de matrizes e números.

• Processo de Gram-Schmidt: ortogonaliza um conjunto de vetores.

• Knuth-Bendix completion algorithm: para reescrita de sistemas de regras.

• Algoritmo de divisão multivariada: para polinomios em vários indeterminados

[editar] Otimização

• Simplex algorithm: um algoritmo para resolver o problema de programação linear.

• Simulated annealing

• (maiores detalhes em Otimização Combinatória)

==Reeditado até aqui== refazer o resto (a parte abaixo) de acordo com a página em inglês Nem tudo está verificado se em concordância.

[editar] Análise Gramatical

• Algoritmo CYK: decide se uma dada string pode ser gerada a partir de uma Gramática Livre de Contexto

• Algoritmo Earley: Também decide se uma dada string pode ser gerada a partir de uma Gramática Livre de Contexto

[editar] Algoritmos Quânticos

Veja artigo principal Computação Quântica

• Algoritmo de Grover: Providencia velocidade quadrática para muitos problemas de busca.

• Algoritmo de Shor: Providencia velocidade exponencial para fatorizar um número.

• Algoritmo de Deutsch-Jozsa: Critério de baleançeamento para funções booleanas.

[editar] Algoritmos Evolutivos

• Algoritmo Genético: Algoritmo evolutivo usado por regras de associação em mineração de dados.

[editar] Outros

• Subset-sum: Aceita a completa linguagem NP Subset-sum em polinominal.

• CORDIC: Técnica de computação função-rápida.

• Cyclic redundancy check: Cálculo de verificação de palavra.

• Halt: Ninguém sabe se este programa 43-byte C sempre pára.

• Knuth-Bendix completion algorithm: para reescrever regras de sistemas.

• Parity: Simples/rápida técnica de detecção de erros. É um número par ou ímpar?

• CHS conversion: Converte entre endereçmento de disco nos sistemas.

• Algoritmo Xor Swap: Troca os valores de duas variáveis sem o uso do buffer.

Obtido em "http://pt.wikipedia.org/wiki/Anexo:Lista_de_algoritmos"