Lista de algoritmos
Origem: Wikipédia, a enciclopédia livre.
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.
[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
- Blum Blum Shub: um gerador de números pseudo-aleatórios com prova de segurança
- 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
- Algorítmo de Knuth-Morris-Pratt.
- Algorítmo de busca de string de Rabin-Karp.
- Algorítmo de busca de string de Boyer-Moore.
[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)
- Transformação de Burrows-Wheeler: preprocessamento útil para compressão de baixa perda
- DEFLATE: compressão de dados de baixa perda
- Codificação Delta: apoio para compressão de dados na qual dados seqüênciais acorrem freqüentemente.
- Codificação de Huffman: Codificaçao de Entropia por Palavras-Código
- Incremental encoding: codificação delta aplicada à uma seqüencia de strings
- LZW: Codificaçao baseada em dicionario (Lev, Zempel, Welch)
- Codificação Run-length: Codificaçao por Comprimento de Sequencia
[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'
- Encriptação de chave simétrica (chave secreta):
- Padrão de Encriptação Avançada (AES), vencedor da competição NIST
- Blowfish
- Padrão de Encriptação de Dados (DES), também chamado de DE, vencedor da competição NBS, substituído pelo AES para a maioria dos propósitos.
- IDEA
- RC4 (cipher)
- Encriptação assimétrica (de chave pública) or digital signature:
- DSA
- ElGamal
- RSA
- Troca de Chaves de Diffie-Hellman
- NTRUEncrypt
- Funções Criptográficas de Condensação de Mensagem:
- Outros
- 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.
- 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.
- Divisão por tentativas
- Fatorização da curva elíptica de Lenstra
- Pollard's rho algorithm
- Pollard's p-1 algorithm
- Congruence of squares
- Quadratic sieve
- Special number field sieve
- 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.
- Teste de primitividade de Miller-Rabin
- Sieve of Eratosthenes: produz uma lista dos primeiros primitivos
- 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
[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: Algorítmo 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.
