Lista de algoritmos

Abaixo segue a lista de algoritmos:

Algoritmos combinatórios
 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

Algoritmos gerais 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 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
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
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

 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

 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

Geometria computacional

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

 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

 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

 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

Algoritmos numéricos para uso geral
 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
 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
 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

 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
 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

 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

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

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-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
 Lista de estruturas de dados 
 Lista de termos relacionados aos algoritmos e às estruturas de dados
 Compressão de dados

algoritmos