Lista de algoritmos - List of algorithms

A seguir está uma lista de algoritmos com descrições de uma linha para cada um.

Planejamento automatizado

Algoritmos combinatórios

Algoritmos combinatórios gerais

• Algoritmo de Brent : encontra um ciclo em iterações de valor de função usando apenas dois iteradores
• Algoritmo de localização de ciclo de Floyd : encontra um ciclo em iterações de valor de função
• Algoritmo de Gale-Shapley : resolve o problema do casamento estável
• Geradores de números pseudo-aleatórios (uniformemente distribuídos - ver também Lista de geradores de números pseudo-aleatórios para outros PRNGs com vários graus de convergência e qualidade estatística variável):
  • Gerador ACORN
  • Blum Blum Shub
  • Gerador Fibonacci retardado
  • Gerador congruencial linear
  • Mersenne Twister

Algoritmos de gráfico

• Algoritmo de coloração : algoritmo de coloração de gráfico.
• Algoritmo Hopcroft-Karp : converte um gráfico bipartido em uma correspondência de cardinalidade máxima
• Algoritmo húngaro : algoritmo para encontrar uma correspondência perfeita
• Codificação de Prüfer : conversão entre uma árvore rotulada e sua sequência de Prüfer
• Algoritmo de ancestrais comuns mais baixos off-line do Tarjan : calcula os ancestrais comuns mais baixos para pares de nós em uma árvore
• Classificação topológica : encontra a ordem linear dos nós (por exemplo, trabalhos) com base em suas dependências.

Desenho gráfico

• Algoritmos baseados em força (também conhecidos como algoritmos direcionados à força ou algoritmo baseado em mola)
• Layout espectral

Teoria da rede

• Análise de rede
  • Análise de link
    • Algoritmo Girvan – Newman : detectar comunidades em sistemas complexos
    • Análise de link da web
      • Pesquisa de tópico induzida por hiperlink (HITS) (também conhecido como Hubs e autoridades )
      • Ranking da página
      • TrustRank
• Redes de fluxo
  • Algoritmo de Dinic : é um algoritmo fortemente polinomial para calcular o fluxo máximo em uma rede de fluxo .
  • Algoritmo Edmonds – Karp : implementação de Ford – Fulkerson
  • Algoritmo Ford-Fulkerson : calcula o fluxo máximo em um gráfico
  • Algoritmo de Karger : um método de Monte Carlo para calcular o corte mínimo de um grafo conectado
  • Algoritmo push – relabel : calcula um fluxo máximo em um gráfico

Roteamento para gráficos

• Algoritmo de Edmonds (também conhecido como algoritmo Chu – Liu / Edmonds): encontre ramificações máximas ou mínimas
• Árvore geradora mínima euclidiana : algoritmos para calcular a árvore geradora mínima de um conjunto de pontos no plano
• Problema do caminho mais curto euclidiano : encontre o caminho mais curto entre dois pontos que não intercepta nenhum obstáculo
• Problema do caminho mais longo : encontre um caminho simples de comprimento máximo em um determinado gráfico
• Árvore de abrangência mínima
  • Algoritmo de Borůvka
  • Algoritmo de Kruskal
  • Algoritmo de Prim
  • Algoritmo de exclusão reversa
• Interruptor de alcance mínimo não bloqueante , digamos, para uma central telefônica
• Problema de caminho mais curto
  • Algoritmo Bellman-Ford : calcula os caminhos mais curtos em um gráfico ponderado (onde alguns dos pesos das arestas podem ser negativos)
  • Algoritmo de Dijkstra : calcula os caminhos mais curtos em um gráfico com pesos de aresta não negativos
  • Algoritmo Floyd – Warshall : resolve o problema do caminho mais curto de todos os pares em um gráfico direcionado e ponderado
  • Algoritmo de Johnson : algoritmo de caminho mais curto para todos os pares em gráfico direcionado de peso esparso
• Problema de fechamento transitivo : encontre o fechamento transitivo de uma dada relação binária
• Problema do caixeiro viajante
  • Algoritmo de Christofides
  • Algoritmo de vizinho mais próximo
• Regra de Warnsdorff : Um método heurístico para resolver o problema da excursão do Cavaleiro .

Pesquisa de gráfico

• A * : caso especial de melhor pesquisa que usa heurísticas para melhorar a velocidade
• B * : um algoritmo de busca de melhor primeiro gráfico que encontra o caminho de menor custo de um determinado nó inicial para qualquer nó de meta (de um ou mais objetivos possíveis)
• Backtracking : abandona as soluções parciais quando se constata que não satisfazem uma solução completa
• Pesquisa de feixe : é um algoritmo de pesquisa heurística que é uma otimização da melhor pesquisa que reduz o seu requisito de memória
• Pesquisa de pilha de feixe : integra backtracking com pesquisa de feixe
• Pesquisa melhor : percorre um gráfico na ordem de importância provável usando uma fila de prioridade
• Pesquisa bidirecional : encontre o caminho mais curto de um vértice inicial para um vértice objetivo em um gráfico direcionado
• Pesquisa abrangente: percorre um gráfico nível por nível
• Pesquisa de força bruta : Um método de pesquisa exaustivo e confiável, mas computacionalmente ineficiente em muitas aplicações.
• D * : um algoritmo de pesquisa heurística incremental
• Pesquisa em profundidade : atravessa um gráfico ramo por ramo
• Algoritmo de Dijkstra : Um caso especial de A * para o qual nenhuma função heurística é usada
• General Problem Solver : um algoritmo de prova de teoremas seminal que pretende funcionar como uma máquina universal de resolução de problemas.
• Pesquisa em profundidade de aprofundamento iterativo (IDDFS): uma estratégia de pesquisa em espaço de estado
• Pesquisa de ponto de salto : Uma otimização para A * que pode reduzir o tempo de computação em uma ordem de magnitude usando heurísticas adicionais.
• Pesquisa em amplitude lexicográfica (também conhecida como Lex-BFS): um algoritmo de tempo linear para ordenar os vértices de um gráfico
• Pesquisa de custo uniforme : uma pesquisa em árvore que encontra a rota de custo mais baixo onde os custos variam
• SSS * : pesquisa no espaço de estado percorrendo uma árvore do jogo da melhor maneira semelhante à do algoritmo de pesquisa A *
• F * : Algoritmo especial para mesclar as duas matrizes

Subgrafos

• Cliques
  • Algoritmo de Bron-Kerbosch : uma técnica para encontrar cliques máximos em um gráfico não direcionado
  • Algoritmo de clique máximo MaxCliqueDyn : encontre um clique máximo em um grafo não direcionado
• Componentes fortemente conectados
  • Algoritmo de componente forte baseado em caminho
  • Algoritmo de Kosaraju
  • Algoritmo de componentes fortemente conectados do Tarjan
• Problema de isomorfismo do subgrafo

Algoritmos de sequência

Correspondência aproximada de sequência

• Algoritmo bitap : algoritmo difuso que determina se as strings são aproximadamente iguais.
• Algoritmos fonéticos
  • Daitch – Mokotoff Soundex : um refinamento de Soundex que permite a combinação de sobrenomes eslavos e germânicos
  • Double Metaphone : uma melhoria na Metaphone
  • Abordagem de classificação de correspondência : um algoritmo fonético desenvolvido pela Western Airlines
  • Metaphone : um algoritmo para indexar palavras por seu som, quando pronunciado em inglês
  • NYSIIS : algoritmo fonético , melhora no Soundex
  • Soundex : um algoritmo fonético para indexar nomes por som, conforme pronunciado em inglês
• Métricas de string : calcula uma pontuação de similaridade ou dissimilaridade (distância) entre dois pares de strings de texto
  • Distância Damerau – Levenshtein : calcula uma medida de distância entre duas cordas, melhora a distância Levenshtein
  • Coeficiente de Dice (também conhecido como coeficiente de Dice): uma medida de similaridade relacionada ao índice de Jaccard
  • Distância de Hamming : soma o número de posições que são diferentes
  • Distância Jaro-Winkler : é uma medida de semelhança entre duas cordas
  • Levenshtein editar distância : calcula uma métrica para a quantidade de diferença entre duas sequências
• Pesquisa de trigrama : pesquisa por texto quando a sintaxe ou grafia exata do objeto de destino não é conhecida com precisão

Algoritmos de seleção

• Seleção rápida
• Introselect

Busca de sequência

• Pesquisa linear : localiza um item em uma sequência não classificada
• Algoritmo de seleção : encontra o k th maior item em uma seqüência
• Pesquisa ternária : uma técnica para encontrar o mínimo ou máximo de uma função que está estritamente aumentando e, em seguida, estritamente diminuindo ou vice-versa
• Listas classificadas
  • Algoritmo de busca binária : localiza um item em uma sequência ordenada
  • Técnica de pesquisa de Fibonacci : pesquisa uma sequência ordenada usando um algoritmo de divisão e conquista que restringe as localizações possíveis com a ajuda de números de Fibonacci
  • Pesquisa de salto (ou pesquisa de bloco): pesquisa linear em um subconjunto menor da sequência
  • Pesquisa preditiva : pesquisa do tipo binária que considera a magnitude do termo de pesquisa em comparação com os valores altos e baixos da pesquisa. Às vezes chamada de pesquisa de dicionário ou pesquisa interpolada.
  • Pesquisa binária uniforme : uma otimização do algoritmo de pesquisa binária clássico

Mesclagem de sequência

• Algoritmo de mesclagem simples
• algoritmo de fusão k-way
• União (mesclar, com elementos na saída não repetidos)

Permutações de sequência

• Fisher – Yates shuffle (também conhecido como Knuth shuffle): embaralhe aleatoriamente um conjunto finito
• Algoritmo de Schensted : constrói um par de tableaux de Young a partir de uma permutação
• Algoritmo Steinhaus-Johnson-Trotter (também conhecido como algoritmo Johnson-Trotter): gera permutações por elementos de transposição
• Algoritmo de geração de permutação de heap : elementos de intercâmbio para gerar a próxima permutação

Combinações de sequência

Alinhamento de sequência

• Time warping dinâmico : mede a similaridade entre duas sequências que podem variar no tempo ou na velocidade
• Algoritmo de Hirschberg : encontra o alinhamento de sequência de menor custo entre duas sequências, conforme medido por sua distância de Levenshtein
• Algoritmo Needleman-Wunsch : encontre o alinhamento global entre duas sequências
• Algoritmo Smith – Waterman : encontre o alinhamento da sequência local

Ordenação de sequência

• Troca de classificações
  • Classificação de bolha : para cada par de índices, troque os itens se estiverem fora de ordem
  • Classificação em coqueteleira ou classificação por bolha bidirecional, uma classificação por bolha que percorre a lista alternadamente da frente para trás e de trás para a frente
  • Tipo pente
  • Tipo gnomo
  • Tipo ímpar-par
  • Quicksort : divida a lista em duas, com todos os itens da primeira lista vindo antes de todos os itens da segunda lista .; em seguida, classifique as duas listas. Muitas vezes, o método de escolha
• Bem humorado ou ineficaz
  • Bogosort
  • Tipo pateta
• Híbrido
  • Flashsort
  • Introsort : comece com quicksort e mude para o heapsort quando a profundidade de recursão exceder um certo nível
  • Timsort : algoritmo adaptativo derivado da classificação por mesclagem e classificação por inserção. Usado em Python 2.3 e superior e Java SE 7.
• Classes de inserção
  • Classificação por inserção : determine onde o item atual pertence na lista de itens classificados e insira-o lá
  • Classificação de biblioteca
  • Classificação de paciência
  • Classificação Shell : uma tentativa de melhorar a classificação por inserção
  • Classificação por árvore ( classificação por árvore binária): construa uma árvore binária e, em seguida, atravesse-a para criar uma lista classificada
  • Classificação de ciclo : no local com número teoricamente ideal de gravações
• Mesclar classificações
  • Mesclar classificação : classifique a primeira e a segunda metade da lista separadamente e, em seguida, mescle as listas classificadas
  • Slowsort
  • Tipo de vertente
• Tipos de não comparação
  • Tipo de conta
  • Classificação de balde
  • Burstsort : construa um teste de burst compacto e eficiente em cache e, em seguida, atravesse-o para criar uma saída classificada
  • Classificação de contagem
  • Tipo de buraco de pombo
  • Classificação Postman : variante da classificação Bucket que aproveita a estrutura hierárquica
  • Classificação Radix : classifica strings letra por letra
• Tipos de seleção
  • Heapsort : converte a lista em um heap, continua removendo o maior elemento do heap e adicionando-o ao final da lista
  • Classificação por seleção : escolha o menor dos elementos restantes, adicione-o ao final da lista classificada
  • Smoothsort
• De outros
  • Classificador bitônico
  • Classificação de panqueca
  • Espaguete tipo
  • Classificação topológica
• Turma desconhecida
  • Samplesort

Subseqüências

• Algoritmo de Kadane : encontra submatriz máxima de qualquer tamanho
• Problema de subsequência comum mais longa : Encontre a subsequência mais longa comum a todas as sequências em um conjunto de sequências
• Problema de subsequência crescente mais longa : Encontre a subsequência crescente mais longa de uma determinada sequência
• Problema de supersequência comum mais curto : Encontre a supersequência mais curta que contém duas ou mais sequências como subsequências

Substrings

• Problema comum de substring mais longo: encontre a string (ou strings) mais longa que é uma substring (ou são substrings) de duas ou mais strings
• Pesquisa de substring
  • Aho-Corasick algoritmo cadeia correspondente : trie algoritmo baseado para encontrar todos os jogos substring para qualquer um de um conjunto finito de cordas
  • Algoritmo de busca de string de Boyer-Moore : algoritmo linear amortizado ( sublinear na maioria das vezes) para busca de substring
  • Algoritmo Boyer-Moore-Horspool : Simplificação de Boyer-Moore
  • Algoritmo Knuth – Morris – Pratt : pesquisa de substring que ignora o reexame de caracteres correspondentes
  • Algoritmo de pesquisa de string Rabin-Karp : pesquisa vários padrões de forma eficiente
  • Algoritmo de correspondência de strings Zhu – Takaoka : uma variante de Boyer – Moore
• O algoritmo de Ukkonen : um tempo linear , algoritmo on-line para a construção de árvores de sufixo
• Caracteres curinga correspondentes
  • Rich Salz ' wildmat : a amplamente utilizado open-source recursiva algoritmo
  • Algoritmo de correspondência de caracteres curinga de Krauss : um algoritmo não recursivo de código aberto

Matemática computacional

Álgebra abstrata

• Pesquisa de Chien : um algoritmo recursivo para determinar raízes de polinômios definidos sobre um corpo finito
• Algoritmo de Schreier-Sims : calculando uma base e um conjunto gerador forte (BSGS) de um grupo de permutação
• Algoritmo de Todd – Coxeter : Procedimento para gerar cosets .

Álgebra computacional

• Algoritmo de Buchberger : encontra uma base de Gröbner
• Algoritmo de Cantor-Zassenhaus : polinômios de fator sobre campos finitos
• Algoritmo Faugère F4 : encontra uma base de Gröbner (também menciona o algoritmo F5)
• Algoritmo de Gosper : encontre somas de termos hipergeométricos que são eles próprios termos hipergeométricos
• Algoritmo de conclusão Knuth – Bendix : para sistemas de regras de reescrita
• Algoritmo de divisão multivariada : para polinômios em vários indeterminados
• Algoritmo canguru de Pollard (também conhecido como algoritmo lambda de Pollard): um algoritmo para resolver o problema de logaritmo discreto
• Polinômio de divisão longa : um algoritmo para dividir um polinômio por outro polinômio de mesmo grau ou inferior
• Algoritmo de Risch : um algoritmo para a operação de cálculo de integração indefinida (ou seja, encontrar antiderivadas )

Geometria

• Problema de par mais próximo : encontre o par de pontos (de um conjunto de pontos) com a menor distância entre eles
• Algoritmos de detecção de colisão : verifique a colisão ou interseção de dois sólidos dados
• Algoritmo de cone : identificar pontos de superfície
• Algoritmos de casco convexo : determinação do casco convexo de um conjunto de pontos
  • Varredura de Graham
  • Quickhull
  • Algoritmo de embrulho ou marcha de Jarvis
  • Algoritmo de Chan
  • Algoritmo Kirkpatrick-Seidel
• Transformada de distância euclidiana : calcula a distância entre cada ponto em uma grade e uma coleção discreta de pontos.
• Hashing geométrico : um método para encontrar com eficiência objetos bidimensionais representados por pontos discretos que sofreram uma transformação afim
• Algoritmo de distância Gilbert – Johnson – Keerthi : determinando a menor distância entre duas formas convexas .
• Algoritmo Jump-and-Walk : um algoritmo para localização de pontos em triangulações
• Suavização Laplaciana : um algoritmo para suavizar uma malha poligonal
• Intersecção do segmento de linha : descobrir se as linhas se cruzam, geralmente com um algoritmo de linha de varredura
  • Algoritmo de Bentley-Ottmann
  • Algoritmo Shamos-Hoey
• Algoritmos de caixa delimitadora mínima : encontre a caixa delimitadora mínima orientada envolvendo um conjunto de pontos
• Pesquisa de vizinho mais próximo : encontre o ponto ou pontos mais próximos para um ponto de consulta
• Algoritmos de ponto em polígono : testa se um determinado ponto está dentro de um determinado polígono
• Algoritmos de registro de conjunto de pontos : encontra a transformação entre dois conjuntos de pontos para alinhá-los de maneira ideal.
• Pinças rotativas : determine todos os pares antípodas de pontos e vértices em um polígono convexo ou casco convexo .
• Algoritmo de cadarço : determine a área de um polígono cujos vértices são descritos por pares ordenados no plano
• Triangulação
  • Triangulação de Delaunay
    • Algoritmo de Ruppert (também conhecido como refinamento de Delaunay): crie triangulações de Delaunay de qualidade
    • Segundo algoritmo de Chew : criar triangulações de Delaunay com restrições de qualidade
  • Triângulos marchando : reconstruir geometria de superfície bidimensional de uma nuvem de pontos não estruturada
  • Algoritmos de triangulação de polígono : decompor um polígono em um conjunto de triângulos
  • Diagramas de Voronoi , dual geométrico de triangulação de Delaunay
    • Algoritmo Bowyer-Watson : crie o diagrama de voronoi em qualquer número de dimensões
    • Algoritmo da Fortune : criar diagrama de Voronoi
  • Quasitriangulação

Algoritmos teóricos dos números

• Algoritmo binário GCD : forma eficiente de calcular GCD.
• Algoritmo de multiplicação de Booth
• Método de Chakravala : um algoritmo cíclico para resolver equações quadráticas indeterminadas, incluindo a equação de Pell
• Logaritmo discreto :
  • Passo de bebê passo gigante
  • Algoritmo de cálculo de índice
  • Algoritmo rho de Pollard para logaritmos
  • Algoritmo Pohlig-Hellman
• Algoritmo Euclidiano : calcula o maior divisor comum
• Algoritmo Euclidiano estendido : também resolve a equação ax  +  by  =  c .
• Fatoração de inteiros : dividindo um inteiro em seus fatores primos
  • Congruência de quadrados
  • Algoritmo de Dixon
  • Método de fatoração de Fermat
  • Crivo de campo de número geral
  • Fatoração de curva elíptica Lenstra
  • De Pollard p  - 1 algoritmo
  • Algoritmo rho de Pollard
  • algoritmo de fatoração principal
  • Peneira quadrática
  • Algoritmo de Shor
  • Peneira de campo de número especial
  • Divisão de teste
• Algoritmos de multiplicação : multiplicação rápida de dois números
  • Algoritmo Karatsuba
  • Algoritmo Schönhage-Strassen
  • Multiplicação de Toom-Cook
• Raiz quadrada modular : calculando o módulo de raízes quadradas de um número primo
  • Algoritmo de Tonelli-Shanks
  • Algoritmo de Cipolla
  • Algoritmo de localização de raiz de Berlekamp
• Algoritmo Odlyzko-Schönhage : calcula zeros não triviais da função zeta de Riemann
• Algoritmo Lenstra – Lenstra – Lovász (também conhecido como algoritmo LLL): encontre uma base de rede curta, quase ortogonal em tempo polinomial
• Testes de primazia : determinar se um determinado número é primo
  • Teste de primalidade AKS
  • Teste de primalidade Baillie – PSW
  • Teste de primalidade de Fermat
  • Teste de primalidade de lucas
  • Teste de primalidade de Miller-Rabin
  • Peneira de Atkin
  • Peneira de Eratóstenes
  • Peneira de Sundaram

Algoritmos numéricos

Resolução de equação diferencial

• Método de Euler
• Método Backward Euler
• Regra trapezoidal (equações diferenciais)
• Métodos lineares de várias etapas
• Métodos Runge-Kutta
  • Integração Euler
• Métodos Multigrid ( métodos MG), um grupo de algoritmos para resolver equações diferenciais usando uma hierarquia de discretizações
• Equação diferencial parcial :
  • Método de diferença finita
  • Método de Crank-Nicolson para equações de difusão
  • Lax-Wendroff para equações de onda
• Integração Verlet ( pronunciação francesa: [vɛʁlɛ] ): integrar equações do movimento de Newton

Funções elementares e especiais

• Cálculo de π :
  • Algoritmo de Borwein : um algoritmo para calcular o valor de 1 / π
  • Algoritmo de Gauss-Legendre : calcula os dígitos de pi
  • Algoritmo de Chudnovsky : um método rápido para calcular os dígitos de π
  • Fórmula de Bailey – Borwein – Plouffe : (fórmula BBP) um algoritmo spigot para o cálculo do enésimo dígito binário de π
• Algoritmos de divisão : para calcular o quociente e / ou o resto de dois números
  • Divisão longa
  • Restaurando divisão
  • Divisão não restauradora
  • Divisão SRT
  • Divisão de Newton-Raphson : usa o método de Newton para encontrar o recíproco de D e multiplique esse recíproco por N para encontrar o quociente final Q.
  • Divisão Goldschmidt
• Funções hiperbólicas e trigonométricas:
  • Algoritmo BKM : calcula funções elementares usando uma tabela de logaritmos
  • CORDIC : calcula funções hiperbólicas e trigonométricas usando uma tabela de tangentes de arco
• Exponenciação:
  • Exponenciação de cadeia de adição : exponenciação por potências inteiras positivas que requerem um número mínimo de multiplicações
  • Exponenciando por quadrado : um algoritmo usado para o cálculo rápido de grandes potências inteiras de um número
• Redução de Montgomery : um algoritmo que permite que a aritmética modular seja realizada de forma eficiente quando o módulo é grande
• Algoritmos de multiplicação : multiplicação rápida de dois números
  • Algoritmo de multiplicação de Booth : um algoritmo de multiplicação que multiplica dois números binários com sinal em notação de complemento de dois
  • Algoritmo de Fürer : um algoritmo de multiplicação de inteiros para números muito grandes possuindo uma complexidade assintótica muito baixa
  • Algoritmo de Karatsuba : um procedimento eficiente para multiplicar grandes números
  • Algoritmo de Schönhage-Strassen : um algoritmo de multiplicação assintoticamente rápido para números inteiros grandes
  • Multiplicação de Toom-Cook : (Toom3) um algoritmo de multiplicação para números inteiros grandes
• Algoritmos multiplicativos inversos : para calcular o inverso multiplicativo de um número (recíproco).
  • Método de Newton
• Funções de arredondamento : as maneiras clássicas de arredondar números
• Algoritmo Spigot : uma maneira de calcular o valor de uma constante matemática sem saber os dígitos anteriores
• Raiz quadrada e enésima raiz de um número:
  • Algoritmo alfa máximo mais beta mínimo : uma aproximação da raiz quadrada da soma de dois quadrados
  • Métodos de cálculo de raízes quadradas
  • n º algoritmo de raiz
  • Mudando o algoritmo de raiz enésima : extração de raiz dígito a dígito
• Soma:
  • Divisão binária : uma técnica de dividir e conquistar que acelera a avaliação numérica de muitos tipos de séries com termos racionais
  • Algoritmo de soma de Kahan : um método mais preciso de somar números de ponto flutuante
• Algoritmo irrestrito

Geométrico

• Retroprojeção filtrada : calcula com eficiência a transformada de Radon bidimensional inversa .
• Método de definição de nível (LSM): uma técnica numérica para rastrear interfaces e formas

Interpolação e extrapolação

• Interpolação de Birkhoff : uma extensão da interpolação polinomial
• Interpolação cúbica
• Interpolação de Hermite
• Interpolação de Lagrange : interpolação usando polinômios de Lagrange
• Interpolação linear : um método de ajuste de curva usando polinômios lineares
• Interpolação cúbica monótona: uma variante da interpolação cúbica que preserva a monotonicidade do conjunto de dados que está sendo interpolado.
• Interpolação multivariada
  • Interpolação bicúbica , uma generalização da interpolação cúbica para duas dimensões
  • Interpolação bilinear : uma extensão da interpolação linear para funções de interpolação de duas variáveis ​​em uma grade regular
  • Reamostragem de Lanczos ("Lanzosh"): um método de interpolação multivariada usado para calcular novos valores para quaisquer dados amostrados digitalmente
  • Interpolação do vizinho mais próximo
  • Interpolação tricúbica , uma generalização da interpolação cúbica para três dimensões
• Interpolação de Pareto : um método de estimar a mediana e outras propriedades de uma população que segue uma distribuição de Pareto .
• Interpolação polinomial
  • Algoritmo de neville
• Interpolação de spline : Reduz o erro com o fenômeno de Runge .
  • Algoritmo De Boor : B-splines
  • Algoritmo de De Casteljau : curvas de Bézier
• Interpolação trigonométrica

Álgebra Linear

• Algoritmos de autovalor
  • Iteração de Arnoldi
  • Iteração inversa
  • Método Jacobi
  • Iteração Lanczos
  • Iteração de energia
  • Algoritmo QR
  • Iteração do quociente de Rayleigh
• Processo de Gram-Schmidt : ortogonaliza um conjunto de vetores
• Algoritmos de multiplicação de matrizes
  • Algoritmo de Cannon : um algoritmo distribuído para multiplicação de matrizes especialmente adequado para computadores dispostos em uma malha N × N
  • Algoritmo Coppersmith – Winograd : multiplicação de matriz quadrada
  • Algoritmo de Freivalds : um algoritmo aleatório usado para verificar a multiplicação da matriz
  • Algoritmo de Strassen : multiplicação de matriz mais rápida

• Resolvendo sistemas de equações lineares
  • Método do gradiente biconjugado : resolve sistemas de equações lineares
  • Gradiente conjugado : um algoritmo para a solução numérica de sistemas particulares de equações lineares
  • Eliminação gaussiana
  • Eliminação de Gauss-Jordan : resolve sistemas de equações lineares
  • Método de Gauss-Seidel : resolve sistemas de equações lineares iterativamente
  • Recursão de Levinson : resolve equação envolvendo uma matriz Toeplitz
  • Método de Stone : também conhecido como procedimento fortemente implícito ou SIP, é um algoritmo para resolver um sistema linear esparso de equações
  • Sobre-relaxação sucessiva (SOR): método usado para acelerar a convergência do método de Gauss-Seidel
  • Algoritmo de matriz tridiagonal ( algoritmo de Thomas): resolve sistemas de equações tridiagonais
• Algoritmos de matriz esparsa
  • Algoritmo de Cuthill-McKee : reduz a largura de banda de uma matriz esparsa simétrica
  • Algoritmo de grau mínimo : permute as linhas e colunas de uma matriz simétrica esparsa antes de aplicar a decomposição de Cholesky
  • Decomposição simbólica de Cholesky : maneira eficiente de armazenar matriz esparsa

Monte carlo

• Amostragem de Gibbs : gera uma sequência de amostras da distribuição de probabilidade conjunta de duas ou mais variáveis ​​aleatórias
• Monte Carlo híbrido : gera uma sequência de amostras usando a cadeia de Markov ponderada Hamiltoniana Monte Carlo , a partir de uma distribuição de probabilidade difícil de amostrar diretamente.
• Algoritmo Metropolis-Hastings : usado para gerar uma sequência de amostras a partir da distribuição de probabilidade de uma ou mais variáveis
• Algoritmo de Wang e Landau : uma extensão da amostragem do algoritmo Metropolis – Hastings

Integração numérica

• Algoritmo MISER : simulação de Monte Carlo, integração numérica

Descoberta de raiz

• Método de bissecção
• Método da posição falsa : aproxima as raízes de uma função
• Método ITP : convergência mín. Máx ótima e superlinar simultaneamente
• Método de Newton : encontra zeros de funções com cálculo
• Método de Halley : usa primeira e segunda derivadas
• Método de secante : 2 pontos, 1 lado
• Método da posição falsa e método de Illinois: 2 pontos, colchetes
• Método de Ridder : escala exponencial de 3 pontos
• Método de Muller : 3 pontos, interpolação quadrática

Algoritmos de otimização

• Poda alfa-beta : pesquisa para reduzir o número de nós no algoritmo minimax
• Ramificar e ligar
• Algoritmo de Bruss : veja o algoritmo de probabilidades
• Multiplicação da matriz da cadeia
• Otimização combinatória : problemas de otimização onde o conjunto de soluções viáveis ​​é discreto
  • Procedimento de pesquisa adaptativa gulosa aleatória (GRASP): construções sucessivas de uma solução aleatória gulosa e melhorias iterativas subsequentes através de uma pesquisa local
  • Método húngaro : um algoritmo de otimização combinatória que resolve o problema de atribuição em tempo polinomial.
• Satisfação de restrição
  • Algoritmos gerais para a satisfação da restrição
    • Algoritmo AC-3
    • Algoritmo de mapa de diferença
    • Algoritmo de conflito mínimo
  • Algoritmo de Chaff : um algoritmo para resolver instâncias do problema de satisfatibilidade booleana
  • Algoritmo Davis-Putnam : verifique a validade de uma fórmula lógica de primeira ordem
  • Algoritmo Davis-Putnam-Logemann-Loveland (DPLL): um algoritmo para decidir o satisfazibilidade de fórmula lógica proposicional em forma normal conjuntivo , ou seja, para resolver o CNF-SAT problema
  • Problema de capa exata
    • Algoritmo X : um algoritmo não determinístico
    • Dancing Links : uma implementação eficiente do Algoritmo X
• Método de entropia cruzada : uma abordagem geral de Monte Carlo para otimização combinatória e multi-extrema contínua e amostragem de importância
• Evolução diferencial
• Programação Dinâmica : problemas exibindo as propriedades de subproblemas sobrepostos e subestrutura ótima
• Método elipsóide : é um algoritmo para resolver problemas de otimização convexa
• Computação evolutiva : otimização inspirada em mecanismos biológicos de evolução
  • Estratégia de evolução
  • Programação de expressão gênica
  • Algorítmos genéticos
    • Seleção proporcional de condicionamento físico - também conhecida como seleção da roda de roleta
    • Amostragem universal estocástica
    • Seleção de truncamento
    • Seleção de torneio
  • Algoritmo memético
  • Inteligência de enxame
    • Otimização de colônia de formigas
    • Algoritmo de abelhas : um algoritmo de busca que simula o comportamento de alimentação de enxames de abelhas.
    • Enxame de partículas
• Algoritmo de Frank-Wolfe : um algoritmo de otimização iterativo de primeira ordem para otimização convexa restrita
• Pesquisa da seção áurea : um algoritmo para encontrar o máximo de uma função real
• Gradiente descendente
• Pesquisa de grade
• Busca de harmonia (HS): um algoritmo metaheurístico que imita o processo de improvisação de músicos
• Método de ponto interior
• Programação linear
  • Algoritmo de Benson : um algoritmo para resolver problemas de otimização de vetores lineares
  • Decomposição de Dantzig-Wolfe : um algoritmo para resolver problemas de programação linear com estrutura especial
  • Geração de coluna atrasada
  • Programação linear inteira : resolva problemas de programação linear onde algumas ou todas as incógnitas são restritas a valores inteiros
    • Ramifique e corte
    • Método de plano de corte
  • Algoritmo de Karmarkar : O primeiro algoritmo razoavelmente eficiente que resolve o problema de programação linear em tempo polinomial .
  • Algoritmo Simplex : Um algoritmo para resolver problemas de programação linear
• Pesquisa de linha
• Pesquisa local : uma metaheurística para resolver problemas de otimização computacionalmente difíceis
  • Subida de colina com reinício aleatório
  • Pesquisa tabu
• Minimax usado na programação de jogos
• Pesquisa de vizinho mais próximo (NNS): encontre os pontos mais próximos em um espaço métrico
  • Best Bin First : encontre uma solução aproximada para o problema de pesquisa do vizinho mais próximo em espaços de dimensões muito altas
• Método de Newton na otimização
• Otimização não linear
  • Método BFGS : um algoritmo de otimização não linear
  • Algoritmo de Gauss-Newton : Um algoritmo para resolver problemas de mínimos quadrados não lineares .
  • Algoritmo de Levenberg – Marquardt : Um algoritmo para resolver problemas de mínimos quadrados não lineares .
  • Método de Nelder-Mead ( método simplex downhill): Um algoritmo de otimização não linear
• Algoritmo de probabilidades ( algoritmo de Bruss): Encontra a estratégia ideal para prever um último evento específico em um evento de sequência aleatória
• Pesquisa Aleatória
• Recozimento simulado
• Tunelamento estocástico
• Algoritmo de soma de subconjunto

Ciência da computação

Astronomia

• Algoritmo do Juízo Final : dia da semana
• A congruência de Zeller é um algoritmo para calcular o dia da semana para qualquer data do calendário Juliano ou Gregoriano
• vários algoritmos de Páscoa são usados ​​para calcular o dia da Páscoa

Bioinformática

• Ferramenta Básica de Pesquisa de Alinhamento Local, também conhecida como BLAST: um algoritmo para comparar informações de sequência biológica primária
• Algoritmo de Kabsch : calcule o alinhamento ótimo de dois conjuntos de pontos para calcular o desvio médio quadrático médio entre duas estruturas de proteínas.
• Velvet : um conjunto de algoritmos de manipulação de gráficos de Bruijn para montagem de sequência genômica
• Classificando por reversões com sinais : um algoritmo para entender a evolução genômica.
• Parcimônia máxima (filogenética) : um algoritmo para encontrar a árvore filogenética mais simples para explicar uma dada matriz de caracteres.
• UPGMA : um algoritmo de construção de árvore filogenética baseado em distância.

Geociências

• Fórmulas de Vincenty : um algoritmo rápido para calcular a distância entre dois pontos de latitude / longitude em um elipsóide
• Geohash : um algoritmo de domínio público que codifica um par decimal de latitude / longitude como uma string hash

Linguística

• Algoritmo de Lesk : desambiguação do sentido da palavra
• Algoritmo de stemming : um método para reduzir palavras à sua forma radical, base ou raiz
• Algoritmo de Sukhotin : um algoritmo de classificação estatística para classificar caracteres em um texto como vogais ou consoantes

Medicina

• Algoritmo ESC para o diagnóstico de insuficiência cardíaca
• Critérios de Manning para síndrome do intestino irritável
• Algoritmos de diagnóstico de embolia pulmonar
• Projeto de Algoritmo de Medicação do Texas

Física

• Algoritmo de restrição : uma classe de algoritmos para satisfazer restrições para corpos que obedecem às equações de movimento de Newton
• Algoritmo Demon : um método de Monte Carlo para amostragem eficiente de membros de um conjunto microcanônico com uma determinada energia
• Algoritmo de Featherstone : calcula os efeitos das forças aplicadas a uma estrutura de juntas e ligações
• Aproximação do estado fundamental
  • Método variacional
    • Método Ritz
• problemas de n- corpo
  • Simulação de Barnes – Hut : Resolve o problema de n-corpos de uma forma aproximada que tem a ordem O ( n log n ) em vez de O ( n ² ) como em uma simulação de soma direta.
  • Método multipolar rápido (FMM): acelera o cálculo de forças de longo alcance
• Algoritmo de contagem de fluxo de chuva : reduz um histórico de estresse complexo a uma contagem de reversões de estresse elementares para uso em análise de fadiga
• Varredura e poda : um algoritmo de fase ampla usado durante a detecção de colisão para limitar o número de pares de sólidos que precisam ser verificados para colisão
• Algoritmo VEGAS : um método para reduzir o erro em simulações de Monte Carlo
• Dinâmica de Glauber : um método para simular o Modelo de Ising em um computador

Estatisticas

• Algoritmos para calcular a variância : evitando instabilidade e estouro numérico
• Algoritmo de contagem aproximada : Permite contar um grande número de eventos em um pequeno registro
• Estatísticas bayesianas
  • Algoritmo de amostragem aninhado : uma abordagem computacional para o problema de comparação de modelos em estatísticas Bayesianas
• Algoritmos de clustering
  • Agrupamento de ligação média : um algoritmo de agrupamento aglomerativo simples
  • Algoritmo de agrupamento Canopy : um algoritmo de pré-agrupamento não supervisionado relacionado ao algoritmo K-means
  • Clustering de ligação completa : um algoritmo de clustering aglomerativo simples
  • DBSCAN : um algoritmo de clusterização baseado em densidade
  • Algoritmo de maximização de expectativa
  • Clustering difuso : uma classe de algoritmos de clustering onde cada ponto tem um grau de pertencimento aos clusters
    • Fuzzy c significa
    • FLAME clustering (Fuzzy clustering por local Approximation of MEmberships): defina clusters nas partes densas de um conjunto de dados e execute a atribuição de cluster com base exclusivamente nas relações de vizinhança entre os objetos
  • Algoritmo de agrupamento KHOPCA : um algoritmo de agrupamento local, que produz clusters multi-hop hierárquicos em ambientes estáticos e móveis.
  • k-means clustering : objetos de cluster baseados em atributos em partições
  • k-means ++ : uma variação disso, usando sementes aleatórias modificadas
  • k-medoides : semelhante a k-means, mas escolhe pontos de dados ou medoides como centros
  • Algoritmo Linde-Buzo-Gray : um algoritmo de quantização vetorial para derivar um bom livro de código
  • Algoritmo de Lloyd (iteração ou relaxamento de Voronoi): agrupa pontos de dados em um determinado número de categorias, um algoritmo popular para agrupamento de k-means
  • ÓPTICA : um algoritmo de agrupamento baseado em densidade com um método de avaliação visual
  • Clustering de ligação única : um algoritmo de clustering aglomerativo simples
  • SUBCLU : um algoritmo de agrupamento de subespaço
  • Método de Ward : um algoritmo de agrupamento aglomerativo, estendido para algoritmos de Lance-Williams mais gerais
  • Algoritmo de agrupamento WACA : um algoritmo de agrupamento local com estruturas potencialmente multi-hop; para redes dinâmicas
• Teoria da Estimação
  • Algoritmo de maximização de expectativa Uma classe de algoritmos relacionados para encontrar estimativas de máxima verossimilhança de parâmetros em modelos probabilísticos
    • Maximização ordenada subconjunto expectativa (OSEM): utilizado em imagiologia médica para tomografia de emiss de positrs , tomografia computadorizada por emissão de fotão único e de raios-X de tomografia computadorizada.
  • Algoritmo de probabilidades ( algoritmo de Bruss) Pesquisa online ideal para valor distinto na entrada aleatória sequencial
  • Filtro de Kalman : estima o estado de um sistema dinâmico linear a partir de uma série de medições ruidosas
• O algoritmo do vizinho mais próximo falso (FNN) estima a dimensão fractal
• Modelo de Markov oculto
  • Algoritmo de Baum-Welch : calcula estimativas de máxima verossimilhança e estimativas de modo posterior para os parâmetros de um modelo de Markov oculto
  • Algoritmo para frente e para trás : um algoritmo de programação dinâmica para calcular a probabilidade de uma sequência de observação particular
  • Algoritmo de Viterbi : encontre a sequência mais provável de estados ocultos em um modelo de Markov oculto
• Regressão de mínimos quadrados parcial : encontra um modelo linear que descreve algumas variáveis ​​previstas em termos de outras variáveis ​​observáveis
• Teoria das filas
  • Algoritmo de Buzen : um algoritmo para calcular a constante de normalização G (K) no teorema de Gordon-Newell
• RANSAC (uma abreviatura para "RANdom SAmple Consensus"): um método iterativo para estimar parâmetros de um modelo matemático a partir de um conjunto de dados observados que contém outliers
• Algoritmo de pontuação : é uma forma do método de Newton usado para resolver equações de máxima verossimilhança numericamente
• Método Yamartino : calcula uma aproximação para o desvio padrão σθ da direção do vento θ durante uma única passagem pelos dados de entrada
• Algoritmo Zigurate : gera números aleatórios a partir de uma distribuição não uniforme

Ciência da Computação

Arquitetura de computador

• Algoritmo Tomasulo : permite que instruções sequenciais que normalmente seriam paralisadas devido a certas dependências sejam executadas de forma não sequencial

Gráficos de computador

• Clipping
  • Recorte de linha
    • Cohen – Sutherland
    • Cyrus – Beck
    • Recorte rápido
    • Liang – Barsky
    • Nicholl – Lee – Nicholl
  • Recorte de polígono
    • Sutherland – Hodgman
    • Vatti
    • Weiler – Atherton
• Linhas de contorno e isosuperfícies
  • Cubos marchando : extraia uma malha poligonal de uma isosuperfície de um campo escalar tridimensional (às vezes chamado de voxels)
  • Quadrados em marcha : gera linhas de contorno para um campo escalar bidimensional
  • Tetraedros em marcha : uma alternativa aos cubos em marcha
• Teorema de Green Discreto : é um algoritmo para calcular a integral dupla sobre um domínio retangular generalizado em tempo constante. É uma extensão natural do algoritmo da tabela de área somada
• Preenchimento : preenche uma região conectada de uma matriz multidimensional com um símbolo especificado
• Algoritmos de iluminação global : considera a iluminação direta e a reflexão de outros objetos.
  • Oclusão de ambiente
  • Traçado de feixe
  • Traçado de cone
  • Iluminação baseada em imagem
  • Transporte leve metrópole
  • Traçado de caminho
  • Mapeamento de fótons
  • Radiosidade
  • Rastreamento de raio
• Remoção de superfície oculta ou determinação de superfície visual
  • Algoritmo de Newell : elimine ciclos de polígonos na classificação de profundidade necessária na remoção de superfícies ocultas
  • Algoritmo do Painter : detecta partes visíveis de um cenário tridimensional
  • Renderização em linha de varredura : constrói uma imagem movendo uma linha imaginária sobre a imagem
  • Algoritmo Warnock
• Desenho de linha : algoritmo gráfico para aproximar um segmento de linha em mídia gráfica discreta.
  • Algoritmo de linha de Bresenham : plota pontos de uma matriz bidimensional para formar uma linha reta entre 2 pontos especificados (usa variáveis ​​de decisão)
  • Algoritmo de linha DDA : plota pontos de uma matriz bidimensional para formar uma linha reta entre 2 pontos especificados (usa matemática de ponto flutuante)
  • Algoritmo de linha de Xiaolin Wu : algoritmo para suavização de linha.
• Algoritmo de círculo de ponto médio : um algoritmo usado para determinar os pontos necessários para desenhar um círculo
• Algoritmo Ramer-Douglas-Peucker : Dada uma 'curva' composta de segmentos de linha para encontrar uma curva não muito diferente, mas que tem menos pontos
• Sombreamento
  • Sombreamento de Gouraud : um algoritmo para simular os diferentes efeitos de luz e cor na superfície de um objeto em computação gráfica 3D
  • Sombreamento Phong : um algoritmo para interpolar vetores normais de superfície para sombreamento de superfície em gráficos de computador 3D
• Slerp (interpolação linear esférica): interpolação de quatérnio com o objetivo de animar a rotação 3D
• Tabela de área somada (também conhecida como imagem integral): um algoritmo para calcular a soma dos valores em um subconjunto retangular de uma grade em tempo constante

Criptografia

• Criptografia assimétrica (chave pública) :
  • ElGamal
  • Criptografia de curva elíptica
  • MAE1
  • NTRUEncrypt
  • RSA
• Assinaturas digitais (autenticação assimétrica):
  • DSA e suas variantes:
    • ECDSA e ECDSA Determinístico
    • EdDSA (Ed25519)
  • RSA
• Funções criptográficas de hash (consulte também a seção sobre códigos de autenticação de mensagem):
  • BLAKE
  • MD5 - Observe que agora existe um método de geração de colisões para MD5
  • RIPEMD-160
  • SHA-1 - Observe que agora existe um método de geração de colisões para SHA-1
  • SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
  • SHA-3 (SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128, SHAKE256)
  • Tiger (TTH), geralmente usado em hashes de árvore Tiger
  • HIDROMASSAGEM
• Geradores de números pseudoaleatórios criptograficamente seguros
  • Blum Blum Shub - com base na dureza da fatoração
  • Fortuna , que pretende ser uma melhoria no algoritmo Yarrow
  • Registro de deslocamento de feedback linear (nota: muitos algoritmos baseados em LFSR são fracos ou foram quebrados)
  • Algoritmo Yarrow
• Troca de chave
  • Troca de chave Diffie-Hellman
  • Curva elíptica Diffie – Hellman (ECDH)
• Funções de derivação de chave , frequentemente usadas para hashing de senha e alongamento de chave
  • bcrypt
  • PBKDF2
  • escritura
  • Argon2
• Códigos de autenticação de mensagem (algoritmos de autenticação simétrica, que usam uma chave como parâmetro):
  • HMAC : autenticação de mensagem hash com chave
  • Poly1305
  • SipHash
• Compartilhamento de segredo , divisão de segredo, divisão de chave, algoritmos M de N
  • Esquema de Blakey
  • Esquema de Shamir
• Criptografia simétrica (chave secreta) :
  • Advanced Encryption Standard (AES), vencedor da competição NIST , também conhecido como Rijndael
  • Blowfish
  • Dois peixes
  • Threefish
  • Data Encryption Standard (DES), às vezes DE Algorithm, vencedor da competição de seleção NBS, substituído por AES para a maioria dos propósitos
  • IDEIA
  • RC4 (cifra)
  • Algoritmo de criptografia minúscula (TEA)
  • Salsa20 e sua variante atualizada ChaCha20
• Criptografia pós-quântica
• Algoritmos de prova de trabalho

Lógica digital

• Minimização booleana
  • Algoritmo Quine – McCluskey : Também chamado de algoritmo QM, método programável para simplificar as equações booleanas.
  • Método de Petrick : Outro algoritmo para simplificação booleana.
  • Minimizador lógico heurístico Espresso : Algoritmo rápido para minimização de função booleana.

Aprendizado de máquina e classificação estatística

• ALOPEX : um algoritmo de aprendizado de máquina baseado em correlação
• Aprendizagem de regras de associação : descubra relações interessantes entre variáveis, usadas na mineração de dados
  • Algoritmo a priori
  • Algoritmo Eclat
  • Algoritmo de crescimento FP
  • Regra de um atributo
  • Regra de atributo zero
• Boosting (meta-algoritmo) : use muitos alunos fracos para aumentar a eficácia
  • AdaBoost : aumento adaptativo
  • BrownBoost : um algoritmo de impulso que pode ser robusto para conjuntos de dados ruidosos
  • LogitBoost : aumento da regressão logística
  • LPBoost : impulso de programação linear
• Agregação de bootstrap (ensacamento): técnica para melhorar a estabilidade e a precisão da classificação
• Visão Computacional
  • Grabcut baseado em cortes do gráfico
• Árvores de decisão
  • Algoritmo C4.5 : uma extensão para ID3
  • Algoritmo ID3 (dicotomizador iterativo 3): use heurística para gerar pequenas árvores de decisão
• Clustering : uma classe de algoritmos de aprendizagem não supervisionados para agrupar e agrupar vetores de entrada relacionados.
  • k-vizinhos mais próximos (k-NN): um método para classificar objetos com base em exemplos de treinamento mais próximos no espaço de recursos
• Algoritmo Linde-Buzo-Gray : um algoritmo de quantização vetorial usado para derivar um bom livro de código
• Hash sensível à localidade (LSH): um método para realizar a redução da dimensão probabilística de dados de alta dimensão
• Rede neural
  • Retropropagação : um método de aprendizagem supervisionado que requer um professor que saiba, ou possa calcular, a saída desejada para qualquer entrada
  • Rede de Hopfield : uma rede neural recorrente em que todas as conexões são simétricas
  • Perceptron : o tipo mais simples de rede neural feedforward: um classificador linear .
  • Redes neurais acopladas a pulso (PCNN): modelos neurais propostos pela modelagem do córtex visual de um gato e desenvolvidos para processamento de imagem biomimética de alto desempenho .
  • Rede de função de base radial : uma rede neural artificial que usa funções de base radial como funções de ativação
  • Mapa de auto-organização : uma rede não supervisionada que produz uma representação de baixa dimensão do espaço de entrada das amostras de treinamento
• Floresta aleatória : classifique usando muitas árvores de decisão
• Aprendizagem por reforço :
  • Q-learning : aprende uma função de valor de ação que dá a utilidade esperada de realizar uma determinada ação em um determinado estado e seguir uma política fixa daí em diante
  • Estado-Ação-Recompensa-Estado-Ação (SARSA): conheça uma política de processo de decisão Markov
  • Aprendizagem de diferença temporal
• Máquina de vetor de relevância (RVM): semelhante ao SVM, mas fornece classificação probabilística
• Aprendizagem supervisionada : aprendizagem por exemplos (conjunto de dados rotulado dividido em conjunto de treinamento e conjunto de teste)
• Support-Vector Machine (SVM): um conjunto de métodos que dividem dados multidimensionais, encontrando um hiperplano divisor com a margem máxima entre os dois conjuntos
  • SVM estruturado : permite o treinamento de um classificador para rótulos de saída estruturados gerais.
• Algoritmo Winnow : relacionado ao perceptron, mas usa um esquema multiplicativo de atualização de peso

Teoria da linguagem de programação

• Linearização C3 : um algoritmo usado principalmente para obter uma linearização consistente de uma hierarquia de herança múltipla em programação orientada a objetos
• Algoritmo de Chaitin : um algoritmo de alocação de registro de coloração de gráfico de baixo para cima que usa custo / grau como sua métrica de derramamento
• Algoritmo de inferência de tipo Hindley-Milner
• Algoritmo Rete : um algoritmo de correspondência de padrões eficiente para implementar sistemas de regras de produção
• Algoritmo Sethi-Ullman : gera código ideal para expressões aritméticas

Análise

• Algoritmo CYK : Um algoritmo O (n ³ ) para analisar gramáticas livres de contexto na forma normal de Chomsky
• Earley parser : Outro algoritmo O (n ³ ) para analisar qualquer gramática livre de contexto
• Analisador GLR : Um algoritmo para analisar qualquer gramática livre de contexto por Masaru Tomita . Ele é ajustado para gramáticas determinísticas, nas quais executa um tempo quase linear e O (n ³ ) no pior caso.
• Algoritmo interno-externo : Um algoritmo O (n ³ ) para re-estimar probabilidades de produção em gramáticas probabilísticas livres de contexto
• Analisador LL : um algoritmo de análise de tempo linear relativamente simples para uma classe limitada de gramáticas livres de contexto
• Analisador LR : Um algoritmo de análise de tempo linear mais complexo para uma classe maior de gramáticas livres de contexto . Variantes:
  • Analisador LR canônico
  • Analisador LALR (look-ahead LR)
  • Analisador de precedência de operador
  • Analisador SLR (Simple LR)
  • Analisador de precedência simples
• Analisador de pacotes : um algoritmo de análise de tempo linear que suporta algumas gramáticas livres de contexto e gramaticais de expressão de análise
• Analisador descendente recursivo : um analisador descendente adequado para gramáticas LL ( k )
• Algoritmo de jarda de manobra : converte uma expressão matemática de notação infixa em pós-fixada
• Analisador Pratt
• Análise lexical

Algoritmos quânticos

• Algoritmo Deutsch-Jozsa : critério de equilíbrio para função booleana
• Algoritmo de Grover : fornece aceleração quadrática para muitos problemas de pesquisa
• Algoritmo de Shor : fornece aceleração exponencial (em relação aos algoritmos não quânticos atualmente conhecidos) para fatorar um número
• Algoritmo de Simon : fornece uma aceleração exponencial comprovada (em relação a qualquer algoritmo não quântico) para um problema de caixa preta

Teoria da computação e autômatos

• O algoritmo do Hopcroft , o algoritmo de Moore , e o algoritmo de Brzozowski : algoritmos para minimizar o número de estados em um autômato finito determinístico
• Construção de Powerset : Algoritmo para converter autômato não determinístico em autômato determinístico .
• Algoritmo de Tarski – Kuratowski : um algoritmo não determinístico que fornece um limite superior para a complexidade das fórmulas na hierarquia aritmética e na hierarquia analítica

Teoria da informação e processamento de sinais

Teoria da codificação

Detecção e correção de erros

• Códigos BCH
  • Algoritmo Berlekamp-Massey
  • Algoritmo Peterson-Gorenstein-Zierler
  • Correção de erro Reed – Solomon
• Algoritmo BCJR : decodificação de códigos de correção de erros definidos em treliças (principalmente códigos convolucionais)
• Continue Correção de Erro
• Código cinza
• Códigos de Hamming
  • Hamming (7,4) : um código de Hamming que codifica 4 bits de dados em 7 bits adicionando 3 bits de paridade
  • Distância de Hamming : soma o número de posições que são diferentes
  • Peso de Hamming (contagem da população): encontre o número de 1 bits em uma palavra binária
• Verificações de redundância
  • Adler-32
  • Verificação de redundância Cíclica
  • Algoritmo Damm
  • Checksum de Fletcher
  • Verificação de redundância longitudinal (LRC)
  • Algoritmo de Luhn : um método de validação de números de identificação
  • Algoritmo Luhn mod N : extensão de Luhn para caracteres não numéricos
  • Paridade : técnica de detecção de erros simples / rápida
  • Algoritmo Verhoeff

Algoritmos de compressão sem perdas

• Transformação de Burrows-Wheeler : pré-processamento útil para melhorar a compressão sem perdas
• Ponderação da árvore de contexto
• Codificação delta : ajuda à compressão de dados em que os dados sequenciais ocorrem com frequência
• Compactação Markov dinâmica : compactação usando codificação aritmética preditiva
• Codificadores de dicionário
  • Codificação de par de bytes (BPE)
  • Esvaziar
  • Lempel – Ziv
    • LZ77 e LZ78
    • Lempel – Ziv Jeff Bonwick (LZJB)
    • Algoritmo de cadeia Lempel-Ziv-Markov (LZMA)
    • Lempel – Ziv – Oberhumer (LZO): orientado para a velocidade
    • Lempel – Ziv – Stac (LZS)
    • Lempel – Ziv – Storer – Szymanski (LZSS)
    • Lempel – Ziv – Welch (LZW)
    • LZWL : variante baseada em sílaba
    • LZX
    • Lempel – Ziv Ross Williams (LZRW)
• Codificação de entropia : esquema de codificação que atribui códigos a símbolos de modo a combinar os comprimentos de código com as probabilidades dos símbolos
  • A codificação aritmética : avançado entropia codificação
    • Codificação de intervalo : igual à codificação aritmética , mas vista de uma forma ligeiramente diferente
  • Codificação de Huffman : compressão simples sem perdas aproveitando as frequências relativas de caracteres
    • Codificação Huffman adaptativa : técnica de codificação adaptativa baseada na codificação Huffman
    • Algoritmo de fusão de pacotes : Otimiza a codificação de Huffman sujeito a uma restrição de comprimento nas strings de código
  • Codificação Shannon-Fano
  • Codificação Shannon – Fano – Elias : precursora da codificação aritmética
• Codificação de entropia com características de entropia conhecidas
  • Codificação de Golomb : forma de codificação de entropia que é ideal para alfabetos seguindo distribuições geométricas
  • Codificação de arroz : forma de codificação de entropia que é ideal para alfabetos seguindo distribuições geométricas
  • Codificação binária truncada
  • Codificação unária : código que representa um número n com n uns seguidos de um zero
  • Códigos universais : codifica inteiros positivos em palavras de código binário
    • Codificação Elias delta , gama e ômega
    • Codificação Exponencial-Golomb
    • Codificação Fibonacci
    • Codificação Levenshtein
• Sistema de compressão de imagem rápido, eficiente e sem perdas (FELICS): um algoritmo de compressão de imagem sem perdas
• Codificação incremental : codificação delta aplicada a sequências de strings
• Predição por correspondência parcial (PPM): uma técnica de compressão de dados estatísticos adaptativos com base na modelagem e previsão de contexto
• Codificação de comprimento de execução : compactação de dados sem perdas aproveitando cadeias de caracteres repetidos
• Algoritmo SEQUITUR : compressão sem perdas por inferência gramatical incremental em uma string

Algoritmos de compressão com perdas

• 3Dc : um algoritmo de compressão de dados com perdas para mapas normais
• Compressão de áudio e fala
  • Algoritmo lei-A : algoritmo de compressão / expansão padrão
  • Predição linear excitada por código (CELP): compressão de voz com baixa taxa de bits
  • Codificação preditiva linear (LPC): compressão com perdas, representando o envelope espectral de um sinal digital de fala em forma comprimida
  • Algoritmo Mu-law : compressão de sinal analógico padrão ou algoritmo de compressão / expansão
  • Codificação preditiva linear distorcida (WLPC)
• Compressão de imagem
  • Block Truncation Coding (BTC): um tipo de técnica de compressão de imagem com perdas para imagens em tons de cinza
  • Wavelet Zerotree incorporado (EZW)
  • Algoritmos Fast Cosine Transform ( algoritmos FCT): calcula a Discrete Cosine Transform (DCT) de forma eficiente
  • Compressão fractal : método usado para comprimir imagens usando fractais
  • Definir particionamento em árvores hierárquicas (SPIHT)
  • Compressão wavelet : forma de compressão de dados adequada para compressão de imagem (às vezes também compressão de vídeo e compressão de áudio)
• Transformar codificação : tipo de compressão de dados para dados "naturais", como sinais de áudio ou imagens fotográficas
• Compressão de vídeo
• Quantização vetorial : técnica frequentemente usada na compressão de dados com perdas

Processamento de sinal digital

• Algoritmo adaptativo-aditivo ( algoritmo AA): encontre a fase de frequência espacial de uma fonte de onda observada
• Transformada discreta de Fourier : determina as frequências contidas em um (segmento de) sinal
  • Algoritmo FFT de Bluestein
  • Algoritmo FFT de Bruun
  • Algoritmo Cooley – Tukey FFT
  • Transformação rápida de Fourier
  • Algoritmo FFT de fator principal
  • Algoritmo FFT de Rader
• Algoritmo de dobramento rápido : um algoritmo eficiente para a detecção de eventos aproximadamente periódicos em dados de série temporal
• Algoritmo Gerchberg-Saxton : algoritmo de recuperação de fase para planos ópticos
• Algoritmo de Goertzel : identifica um determinado componente de frequência em um sinal. Pode ser usado para decodificação de dígitos DTMF .
• Síntese de cordas Karplus-Strong : síntese de modelagem física para simular o som de uma corda martelada ou dedilhada ou alguns tipos de percussão

Processamento de imagem

• Aprimoramento de contraste
  • Equalização do histograma : use o histograma para melhorar o contraste da imagem
  • Equalização adaptativa do histograma : equalização do histograma que se adapta às mudanças locais de contraste
• Rotulagem de componentes conectados : encontre e rotule regiões disjuntas
• Dithering e meio-tom
  • Difusão de erro
  • Floyd – Steinberg hesitação
  • Dithering ordenado
  • Riemersma hesitando
• Algoritmo de mapa de diferenças de Elser : um algoritmo de busca para problemas gerais de satisfação de restrições. Originalmente usado para microscopia de difração de raios-X
• Detecção de recursos
  • Detector de bordas Canny : detecta uma ampla gama de bordas em imagens
  • Transformada de Hough generalizada
  • Transformada de Hough
  • Algoritmo Marr-Hildreth : um algoritmo de detecção de borda precoce
  • SIFT (Scale-invariant feature transform): é um algoritmo para detectar e descrever características locais em imagens.
  • SURF ( Speeded Up Robust Features ) : é um detector de recurso local robusto, apresentado pela primeira vez por Herbert Bay et al. em 2006, que pode ser usado em tarefas de visão computacional, como reconhecimento de objetos ou reconstrução 3D. É parcialmente inspirado no descritor SIFT. A versão padrão do SURF é várias vezes mais rápida do que o SIFT e afirmado por seus autores ser mais robusta contra diferentes transformações de imagem do que o SIFT.
• Deconvolução de Richardson-Lucy : algoritmo de desfoque de imagem
• Desconvolução cega : algoritmo de desfoque de imagem quando a função de difusão de pontos é desconhecida.
• Filtragem de mediana
• Seam carving : algoritmo de redimensionamento de imagem com reconhecimento de conteúdo
• Segmentação : particionar uma imagem digital em duas ou mais regiões
  • Algoritmo GrowCut : um algoritmo de segmentação interativo
  • Algoritmo de caminhante aleatório
  • Região crescendo
  • Transformação de bacias hidrográficas : uma classe de algoritmos baseados na analogia de bacias hidrográficas

Engenharia de software

• Algoritmos de cache
• Conversão CHS : conversão entre sistemas de endereçamento de disco
• Double dabble : Converta números binários em BCD
• Função hash : converte uma grande quantidade de dados, possivelmente de tamanho variável, em um pequeno datum, geralmente um único inteiro que pode servir como um índice em uma matriz
  • Função hash Fowler – Noll – Vo : rápido com baixa taxa de colisão
  • Hash de Pearson : calcula apenas o valor de 8 bits, otimizado para computadores de 8 bits
  • Hash de Zobrist : usado na implementação de tabelas de transposição
• Algoritmo de agrupamento Unicode
• Algoritmo de troca Xor : troca os valores de duas variáveis ​​sem usar um buffer

Algoritmos de banco de dados

• Algoritmos de Semântica de Exploração de Recuperação e Isolamento (ARIES): recuperação de transação
• Algoritmos de junção
  • Loop aninhado de bloco
  • Hash join
  • Junção de loop aninhado
  • Sort-Merge Join

Algoritmos de sistemas distribuídos

• Sincronização de relógio
  • Algoritmo de Berkeley
  • Algoritmo de Cristian
  • Algoritmo de interseção
  • Algoritmo de Marzullo
• Consenso (ciência da computação) : concordar com um único valor ou histórico entre processadores não confiáveis
  • Algoritmo de consenso Chandra – Toueg
  • Algoritmo Paxos
  • Raft (ciência da computação)
• Detecção de rescisão de processo
  • Algoritmo de Dijkstra-Scholten
  • Algoritmo de Huang
• Ordenação de Lamport : uma ordenação parcial de eventos com base na relação acontecido antes
• Eleição do líder : um método para selecionar dinamicamente um coordenador
  • Algoritmo de intimidação
• Exclusão mútua
  • Algoritmo de exclusão mútua distribuída de Lamport
  • Algoritmo de log (n) de Naimi-Trehel
  • Algoritmo de Maekawa
  • Algoritmo de Raymond
  • Algoritmo Ricart-Agrawala
• Algoritmo de instantâneo : registra um estado global consistente para um sistema assíncrono
  • Algoritmo Chandy – Lamport
• Relógios de vetor : geram uma ordem parcial de eventos em um sistema distribuído e detectam violações de causalidade

Algoritmos de alocação e desalocação de memória

• Alocação de memória camarada : Algoritmo para alocar memória de forma que a fragmentação seja menor.
• Coletores de lixo
  • Algoritmo de Cheney : uma melhoria no coletor de semi-espaço
  • Coletor de lixo geracional : coletores de lixo rápidos que segregam a memória por idade
  • Algoritmo Mark-compact : uma combinação do algoritmo mark-sweep e o algoritmo de cópia de Cheney
  • Marcar e varrer
  • Coletor de semi-espaço : um coletor de cópias antigo
• Contagem de referência

Networking

• Algoritmo de Karn : aborda o problema de obter estimativas precisas do tempo de ida e volta para mensagens ao usar TCP
• Algoritmo de Luleå : uma técnica para armazenar e pesquisar tabelas de roteamento de internet de forma eficiente
• Congestionamento de rede
  • Retirada exponencial
  • Algoritmo de Nagle : melhore a eficiência das redes TCP / IP unindo pacotes
  • Backoff exponencial binário truncado

Algoritmos de sistemas operacionais

• Algoritmo do banqueiro : Algoritmo usado para evitar deadlock.
• Algoritmos de substituição de página : Selecionando a página da vítima em condições de pouca memória.
  • Cache de substituição adaptável : melhor desempenho do que LRU
  • Relógio com substituição adaptativa (CAR): é um algoritmo de substituição de página que tem desempenho comparável ao cache de substituição adaptável

Sincronização de processos

• Algoritmo de Dekker
• Algoritmo de padaria de Lamport
• Algoritmo de Peterson

Agendamento

• Prazo mais cedo primeiro agendamento
• Programação de participação justa
• Menor folga na programação
• Lista de programação
• Fila de feedback multinível
• Agendamento monotônico de taxa
• Programação round-robin
• Trabalho mais curto próximo
• Menor tempo restante
• Algoritmo de nós principais : gerenciamento de calendário de recursos

Agendamento de I / O

Agendamento de disco

• Algoritmo de elevador : algoritmo de escalonamento de disco que funciona como um elevador.
• Busca mais curta primeiro : algoritmo de agendamento de disco para reduzir o tempo de busca .

Veja também

• Lista de estruturas de dados
• Lista de algoritmos de aprendizado de máquina
• Lista de algoritmos de pathfinding
• Lista de tópicos gerais do algoritmo
• Lista de termos relacionados a algoritmos e estruturas de dados
• Heurística

Referências