Lista de algoritmos

Abaixo segue a lista de algoritmos:

Algoritmos combinatórios[editar | editar código-fonte]

Algoritmo busca-ciclos de Floyd: encontra ciclos em iterações.
Geradores de números pseudoaleatórios: produzem números estatisticamente aleatórios.
- Blum Blum Shub: um gerador de números pseudoaleatórios com prova de segurança;
- Algoritmo Yarrow.

Algoritmos de busca[editar | editar código-fonte]

Algoritmos gerais de busca[editar | editar código-fonte]

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 sequência 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: encontra elemento 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.
Busca preditiva.

Busca em strings[editar | editar código-fonte]

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 Bitmap).

Busca em grafos[editar | editar código-fonte]

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 pares de vértices em um grafo com direção e peso.
Algoritmo de Kruskal; Algoritmo de Prim; Algoritmo de Boruvka: encontram 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.
Spring based algorithm: algoritmo para desenhar grafos.
Algoritmo das economias: algoritmo para encontrar a menor rota em um grafo.

Algoritmos de ordenação[editar | editar código-fonte]

Bogosort: ineficiente, mais utilizado para ensinar o funcionamento dos algoritmos de ordenação.
Classificação bolha: para cada par de índices, mude os itens de posição se estiverem fora de ordem.
Bucket sort.
Classificação pente: Parecido com o método bolha.
Cocktail sort.
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 deste e adicionando-o no fim da lista.
Ordenação por inserção: determina à qual posição o item 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 duas, com todos os itens da primeira lista sendo menores que os itens da segunda; e então classifique as duas listas. Certamente esse é o método de escolha mais rápido.
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.

Algoritmos de compressão[editar | editar código-fonte]

Codificação aritmética: Codificação de entropia (sempre alcança a entropia da fonte).
Método de Burrows-Wheeler: pré-processamento ú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 sequenciais acorrem frequentemente.
Codificação de Huffman: Codificação de entropia por palavras-código.
Incremental encoding: codificação delta aplicada à uma sequência de strings.
LZW: Codificação baseada em dicionário (Lempel, Ziv, Welch).
LZ77: Codificação baseada em dicionário com "janela deslizante" (sliding window em inglês). A base do DEFLATE.
LZ78: Codificação baseada em dicionário da qual evoluiu o LZW.
Codificação run-length: Codificação por comprimento de sequência.

Algoritmos de álgebra linear e geometria analítica[editar | editar código-fonte]

Geometria computacional[editar | editar código-fonte]

Algoritmo embrulho para presente: determina 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.

Computação gráfica[editar | editar código-fonte]

Algoritmo de linha de Bresenham: plota pontos de uma matriz bidimensional para traçar uma linha reta entre dois pontos específicos.
Algoritmo do pintor: detecta partes visíveis de um cenário tridimensional.
Traçado de raios: interpretação de imagens reais.

Algoritmos criptográficos[editar | editar código-fonte]

Criptografia de chave simétrica (chave secreta):
- Padrão de criptografia avançada (AES), vencedor da competição NIST.
- Blowfish.
- 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.
- IDEA.
- RC4.
Criptografia assimétrica (de chave pública) ou assinatura digital:
- DSA.
- ElGamal.
- RSA.
- NTRUEncrypt.
Funções criptográficas de condensação de mensagem:
- MD5.
- MD4.
- RIPEMD-160.
- SHA-1.
- HMAC: autenticação chaveada de mensagem codificada.
Outros:
- Diffie-Hellman: troca de chaves.

Algoritmos de sistemas distribuídos[editar | editar código-fonte]

Lamport ordering: ordenação parcial de eventos, baseada 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.

Algoritmos numéricos[editar | editar código-fonte]

Algoritmos numéricos para uso geral[editar | editar código-fonte]

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.
Algoritmo de Buchberger: encontra a base de Grobner.
Algoritmo de Eigenvalue.
Exponentiating by squaring: calcula rapidamente 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 polinômios em vários indeterminados.

Algoritmos teórico-matemáticos[editar | editar código-fonte]

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.
- Crivo de Eratóstenes: produz uma lista dos primeiros primitivos.
- AKS primality test.

Algoritmos de processamento de sinais digitais[editar | editar código-fonte]

CORDIC: técnica de cálculo rápido de função trigonométrica.
Fast Fourier transform: determina as frequências 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.

Algoritmos de otimização[editar | editar código-fonte]

Simplex algorithm: um algoritmo para resolver o problema de programação linear.
Simulated annealing: algoritmo de otimização que consiste numa técnica de busca local probabilística, fundamentado pela termodinâmica.

Análise gramatical[editar | editar código-fonte]

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.

Algoritmos quânticos[editar | editar código-fonte]

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 balanceamento para funções booleanas.

Algoritmos evolutivos[editar | editar código-fonte]

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

Outros[editar | editar código-fonte]

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-bytes C sempre para.
Knuth-Bendix completion algorithm: para reescrever regras de sistemas.
Parity: simples e rápida técnica de detecção de erros, com base num número par ou ímpar.
CHS conversion: conversão entre endereçamento de disco nos sistemas.
Algoritmo Xor Swap: troca os valores de duas variáveis sem o uso do buffer.

Veja também[editar | editar código-fonte]