# 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