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

Ver artigo principal: Algoritmo 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

Ver artigo principal: Algoritmo 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

Ver artigo principal: Compressão de dados

• 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

Ver artigo principal: 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

Ver artigo principal: 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

Ver artigo principal: Criptografia

• 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

Ver artigo principal: 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

Ver artigo principal: Otimização combinatória

• 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

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

Algoritmos evolutivos

Ver artigo principal: Algoritmo evolutivo

• 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