Anexo:Lista de algoritmos

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.

Algorítmos Combinatórios

Algoritmos 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

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.

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.

Algoritmos de Pesquisa 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 Bitap)

Algoritmo de Ordenaçã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

Algoritmos de Compressão

• Codificação aritmética: Codificação de Entropia (sempre alcança a entropia da fonte)
• Método de Burrows-Wheeler: preprocessamento ú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 seqüênciais acorrem freqüentemente.
• Codificação de Huffman: Codificação de Entropia por Palavras-Código
• Incremental encoding: codificação delta aplicada a uma seqüencia de strings
• LZW: Codificaçao baseada em dicionário (Lempel, Ziv, Welch)
• LZ77: Codificaçao baseada em dicionário com "janela deslizante" (sliding window em inglês). A base do DEFLATE.
• LZ78: Codificaçao baseada em dicionário da qual evoluiu o LZW.
• Codificação Run-length: Codificaçao por Comprimento de Sequencia

Compressão de dados
Teoria
Com perda · Sem perda
Tipo de dados de origem
áudio · banda · imagens · vídeo
Métodos
Lista de algoritmos - Algoritmos de Compressão

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.

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.

Algoritmos Criptográficos

Veja também Tópicos de Criptografia para um 'glossário analítico'

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

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.

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.

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

Á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

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.

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

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.

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