Algoritmos principais implantados

Para demonstrar a importância dos algoritmos (por exemplo, para estudantes e professores que não fazem teoria ou são de campos totalmente diferentes), às vezes é útil ter à mão uma lista de exemplos em que os algoritmos principais foram implantados em setores comerciais, governamentais, ou software / hardware amplamente utilizado.

Estou procurando exemplos que atendam aos seguintes critérios:

1. O software / hardware que usa o algoritmo deve estar em uso amplo no momento.

2. O exemplo deve ser específico. Por favor, dê uma referência a um sistema específico e um algoritmo específico.
   Por exemplo, no "algoritmo X é útil para o processamento de imagens", o termo "processamento de imagens" não é suficientemente específico; em "A pesquisa do Google usa algoritmos gráficos", o termo "algoritmos gráficos" não é suficientemente específico.

3. O algoritmo deve ser ensinado na graduação típica ou no doutorado. classes em algoritmos ou estruturas de dados. Idealmente, o algoritmo é abordado em manuais típicos de algoritmos. Por exemplo, "o conhecido sistema X usa o algoritmo pouco conhecido Y" não é bom.

Atualizar:

Obrigado novamente pelas ótimas respostas e links! Algumas pessoas comentam que é difícil satisfazer os critérios porque os algoritmos principais são tão difundidos que é difícil apontar para um uso específico. Eu vejo a dificuldade. Mas acho que vale a pena apresentar exemplos específicos porque, em minha experiência, digo às pessoas: "Veja, algoritmos são importantes porque estão em quase todos os lugares !" não funciona.

Algoritmos que são o principal fator por trás de um sistema são, na minha opinião, mais fáceis de encontrar em cursos que não são de algoritmos, pela mesma razão que teoremas com aplicações imediatas são mais fáceis de encontrar em matemática aplicada do que em cursos de matemática pura. É raro um problema prático ter a estrutura exata do problema abstrato em uma palestra. Para ser argumentativo, não vejo razão para o fato de algoritmos da moda cursarem o material, como a multiplicação de Strassen, o teste de primalidade AKS ou o algoritmo Moser-Tardos, ser relevante para problemas práticos de baixo nível da implementação de um banco de dados de vídeo, um compilador de otimização, um sistema operacional , um sistema de controle de congestionamento de rede ou qualquer outro sistema. O valor desses cursos é aprender que existem maneiras complexas de explorar a estrutura de um problema e encontrar soluções eficientes. Algoritmos avançados também é onde encontramos algoritmos simples cuja análise não é trivial. Por esse motivo, eu não descartaria algoritmos aleatórios simples ou o PageRank.

Eu acho que você pode escolher qualquer software grande e encontrar algoritmos básicos e avançados implementados nele. Como um estudo de caso, eu fiz isso para o kernel Linux e mostrei alguns exemplos do Chromium.

Estruturas básicas de dados e algoritmos no kernel do Linux

Os links são para o código fonte no github .

1. Lista vinculada , lista duplamente vinculada , lista vinculada sem bloqueio .

2. Árvores B + com comentários dizendo o que você não consegue encontrar nos livros didáticos.

   Uma implementação B + Tree relativamente simples. Eu o escrevi como um exercício de aprendizado para entender como as árvores B + funcionam. Acabou sendo útil também.

   ...

   Foi utilizado um truque que não é comumente encontrado em livros didáticos. Os valores mais baixos estão à direita, não à esquerda. Todos os slots usados ​​em um nó estão à esquerda, todos os slots não utilizados contêm valores NUL. A maioria das operações simplesmente executa o loop uma vez em todos os slots e termina na primeira NUL.

3. Listas ordenadas por prioridade usadas para mutexes , drivers , etc.

4. Árvores Red-Black são usadas para agendamento, gerenciamento de memória virtual, para rastrear descritores de arquivos e entradas de diretório, etc.
5. Árvores de intervalo

6. As árvores Radix são usadas para gerenciamento de memória , pesquisas relacionadas ao NFS e funcionalidade relacionada à rede.

   Um uso comum da árvore radix é armazenar ponteiros para estruturar páginas;

7. O heap de prioridade , que é literalmente, uma implementação de livro didático, usado no sistema de grupo de controle .

   Heap de prioridade de tamanho estático simples, apenas para inserção, contendo ponteiros, com base no CLR, capítulo 7

8. Funções de hash , com uma referência a Knuth e a um artigo.

   Knuth recomenda números primos aproximadamente na proporção áurea ao número máximo máximo representável por uma palavra-máquina para hash multiplicativo. Chuck Lever verificou a eficácia dessa técnica:

   http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

   Esses números primos são escolhidos para serem pouco esparsos, ou seja, as operações neles podem usar turnos e adições em vez de multiplicações para máquinas nas quais as multiplicações são lentas.

9. Algumas partes do código, como este driver , implementam sua própria função de hash.

   função hash usando um algoritmo de Rotating Hash

   Knuth, D. A Arte da Programação por Computador, Volume 3: Classificação e Pesquisa, Capítulo 6.4. Addison Wesley, 1973

10. Tabelas de hash usadas para implementar inodes , verificações de integridade do sistema de arquivos etc.

11. Matrizes de bits , usadas para lidar com sinalizadores, interrupções etc., e são apresentadas no Knuth Vol. 4)

12. Semáforos e fechaduras giratórias

13. A pesquisa binária é usada para manipulação de interrupções , pesquisa de cache de registro etc.

14. Pesquisa binária com árvores B

15. Primeira pesquisa profunda e variante usada na configuração de diretório .

    Executa uma caminhada modificada em profundidade da árvore do namespace, iniciando (e finalizando) no nó especificado por start_handle. A função de retorno de chamada é chamada sempre que um nó que corresponde ao parâmetro type é encontrado. Se a função de retorno de chamada retornar um valor diferente de zero, a pesquisa será encerrada imediatamente e esse valor será retornado ao chamador.

16. A primeira pesquisa de largura é usada para verificar a correção do bloqueio em tempo de execução.

17. A classificação de mesclagem nas listas vinculadas é usada para coleta de lixo , gerenciamento do sistema de arquivos etc.

18. O tipo de bolha também é incrivelmente implementado em uma biblioteca de drivers.

19. Correspondência de cordas de Knuth-Morris-Pratt ,

    Implementa um algoritmo de correspondência de cadeia de tempo linear devido a Knuth, Morris e Pratt [1]. O algoritmo deles evita a computação explícita da função de transição DELTA. Seu tempo de correspondência é O (n), por n ser comprimento (texto), usando apenas uma função auxiliar PI [1..m], por m ser comprimento (padrão), pré-computado do padrão no tempo O (m). O array PI permite que a função de transição DELTA seja computada eficientemente "on the fly", conforme necessário. Grosso modo, para qualquer estado "q" = 0,1, ..., m e qualquer caractere "a" no SIGMA, o valor PI ["q"] contém as informações independentes de "a" e são necessárias para calcular DELTA ("q", "a") 2. Como o PI da matriz possui apenas m entradas, enquanto DELTA possui entradas O (m | SIGMA |), salvamos um fator de | SIGMA | no tempo de pré-processamento, computando PI em vez de DELTA.

    [1] Cormen, Leiserson, Rivest, Stein Introdução aos algoritmos, 2ª edição, MIT Press.

    [2] Ver teoria da automação finita

20. Correspondência de padrões de Boyer-Moore com referências e recomendações para quando preferir a alternativa.

    Implementa o algoritmo de correspondência de string de Boyer-Moore:

    [1] Um algoritmo de pesquisa rápida de cadeias, RS Boyer e Moore. Comunicações da Association for Computing Machinery, 20 (10), 1977, pp. 762-772. http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

    [2] Manual de algoritmos de correspondência exata de cordas, Thierry Lecroq, 2004 http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf

    Nota: Como Boyer-Moore (BM) realiza buscas por correspondências da direita para a esquerda, ainda é possível que uma correspondência possa ser espalhada por vários blocos; nesse caso, esse algoritmo não encontrará nenhuma coincidência.

    Se você deseja garantir que isso nunca aconteça, use a implementação Knuth-Pratt-Morris (KMP). Em conclusão, escolha o algoritmo de pesquisa de string adequado, dependendo da sua configuração.

    Digamos que você esteja usando a infraestrutura de pesquisa de texto para filtragem, NIDS ou
    qualquer outro objetivo semelhante focado na segurança e, em seguida, acesse o KMP. Caso contrário, se você realmente se preocupa com o desempenho, diga que está classificando pacotes para aplicar políticas de Qualidade de Serviço (QoS) e não se importa com possíveis correspondências espalhadas por vários fragmentos, e então vá em BM.

Estruturas de dados e algoritmos no navegador Chromium

Os links são para o código fonte no código do Google . Eu só vou listar alguns. Eu sugeriria o uso do recurso de pesquisa para procurar seu algoritmo favorito ou estrutura de dados.

1. Espalhe árvores .

   A árvore também é parametrizada por uma política de alocação (Alocador). A política é usada para alocar listas no armazenamento gratuito C ou na zona; veja zone.h.

2. Os diagramas de Voronoi são usados ​​em uma demonstração.
3. Tabulação baseada no algoritmo de Bresenham .

1. Árvores binárias
2. Árvores vermelho-pretas

   Conclusão de Julian Walker

   Árvores negras vermelhas são bestas interessantes. Acredita-se que sejam mais simples que as árvores AVL (seu concorrente direto) e, à primeira vista, esse parece ser o caso, porque a inserção é fácil. No entanto, quando alguém começa a brincar com o algoritmo de exclusão, as árvores vermelhas e pretas se tornam muito complicadas. No entanto, o contrapeso a essa complexidade adicional é que a inserção e a exclusão podem ser implementadas usando um algoritmo de passagem única, de cima para baixo. Esse não é o caso das árvores AVL, onde apenas o algoritmo de inserção pode ser escrito de cima para baixo. A exclusão de uma árvore AVL requer um algoritmo de baixo para cima.

   ...

   Árvores negras vermelhas são populares, como a maioria das estruturas de dados com um nome extravagante. Por exemplo, em Java e C ++, as estruturas de mapas da biblioteca geralmente são implementadas com uma árvore preta e vermelha. As árvores vermelhas e pretas também são comparáveis ​​em velocidade às árvores AVL. Embora o equilíbrio não seja tão bom, o trabalho necessário para manter o equilíbrio geralmente é melhor em uma árvore vermelha e preta. Existem alguns conceitos errados, mas na maioria das vezes o hype sobre as árvores negras vermelhas é preciso.

3. Árvores AVL
4. A correspondência de sequência Rabin-Karp é usada para compactação.
5. Calcule os sufixos de um autômato .
6. Filtro Bloom implementado pela Apple Inc.
7. Algoritmo de Bresenham .

Bibliotecas de Linguagem de Programação

Eu acho que vale a pena considerar. Os projetistas das linguagens de programação pensaram que valia a pena o tempo e o esforço de alguns engenheiros para implementar essas estruturas e algoritmos de dados, para que outros não precisassem. A existência de bibliotecas é parte do motivo pelo qual podemos encontrar estruturas básicas de dados reimplementadas em software escrito em C, mas menos para aplicativos Java.

1. O C ++ STL inclui listas, pilhas, filas, mapas, vetores e algoritmos para classificação, pesquisa e manipulação de heap .
2. A API Java é muito extensa e cobre muito mais.
3. A biblioteca Boost C ++ inclui algoritmos como Boyer-Moore e Knuth-Morris-Pratt.

Algoritmos de alocação e programação

Acho isso interessante porque, embora sejam chamadas heurísticas, a política usada determina o tipo de algoritmo e estrutura de dados necessários, portanto é preciso saber sobre pilhas e filas.

1. Menos usado recentemente pode ser implementado de várias maneiras. Uma implementação baseada em lista no kernel do Linux.
2. Outras possibilidades são Primeiro a entrar, Menos usado com freqüência e Round Robin.
3. Uma variante do FIFO foi usada pelo sistema VAX / VMS.
4. O algoritmo Clock de Richard Carr é usado para substituição de quadros de página no Linux.
5. O processador Intel i860 usou uma política de substituição aleatória.
6. O Cache de Substituição Adaptativa é usado em alguns controladores de armazenamento IBM e foi usado no PostgreSQL, embora apenas brevemente devido a preocupações com patentes .
7. O algoritmo de alocação de memória Buddy , discutido por Knuth no TAOCP vol. 1 é usado no kernel Linux e no alocador simultâneo jemalloc usado pelo FreeBSD e no facebook .

Utilitários principais em sistemas * nix

1. grep e awk implementam a construção de NFAs Thompson-McNaughton-Yamada a partir de expressões regulares, o que aparentemente até supera a implementação do Perl .
2. tsort implementa classificação topológica.
3. O fgrep implementa o algoritmo de correspondência de strings Aho-Corasick.
4. GNU grep , implementa o algoritmo Boyer-Moore de acordo com o autor Mike Haertel.
5. O crypt (1) no Unix implementou uma variante do algoritmo de criptografia na máquina Enigma.
6. O diff Unix implementado por Doug McIllroy, baseado em um protótipo co-escrito com James Hunt, tem um desempenho melhor que o algoritmo de programação dinâmica padrão usado para calcular as distâncias de Levenshtein. A versão Linux calcula a menor distância de edição.

Algoritmos criptográficos

Esta poderia ser uma lista muito longa. Algoritmos criptográficos são implementados em todos os softwares que podem executar comunicações ou transações seguras.

1. As árvores Merkle , especificamente a variante Tiger Tree Hash, foram usadas em aplicativos ponto a ponto, como GTK Gnutella e LimeWire .
2. O MD5 é usado para fornecer uma soma de verificação para pacotes de software e é usado para verificações de integridade em sistemas * nix ( implementação Linux ) e também é suportado no Windows e no OS X.
3. O OpenSSL implementa muitos algoritmos criptográficos, incluindo AES, Blowfish, DES, SHA-1, SHA-2, RSA, DES, etc.

Compiladores

1. A análise LALR é implementada pelo yacc e pelo bison.
2. Os algoritmos Dominator são usados ​​na maioria dos otimizadores de compilação baseados no formato SSA.
3. lex e flex compilam expressões regulares em NFAs.

Compressão e Processamento de Imagem

1. Os algoritmos Lempel-Ziv para o formato de imagem GIF são implementados em programas de manipulação de imagens, iniciando a partir do utilitário * nix convertido em programas complexos.
2. A codificação de duração da execução é usada para gerar arquivos PCX (usados ​​pelo programa Paintbrush original), arquivos BMP compactados e arquivos TIFF.
3. A compactação Wavelet é a base do JPEG 2000, portanto, todas as câmeras digitais que produzem arquivos JPEG 2000 implementarão esse algoritmo.
4. A correção de erros Reed-Solomon é implementada no kernel Linux , unidades de CD, leitores de código de barras e foi combinada com a convolução para transmissão de imagens da Voyager.

Aprendizagem de Cláusulas Conduzidas por Conflitos

Desde o ano 2000, o tempo de execução dos solucionadores SAT em benchmarks industriais (geralmente da indústria de hardware, embora também sejam usadas outras fontes) diminuiu quase exponencialmente a cada ano. Uma parte muito importante desse desenvolvimento é o algoritmo de Aprendizagem de Cláusulas Conduzidas por Conflitos , que combina o algoritmo de Propagação de Restrições Booleanas no artigo original de Davis Logemann e Loveland com a técnica de aprendizado de cláusulas que se originou na programação de restrições e na pesquisa de inteligência artificial. Para modelagem industrial específica, o SAT é considerado um problema fácil ( consulte esta discussão) Para mim, essa é uma das maiores histórias de sucesso dos últimos tempos, porque combina avanços algorítmicos espalhados por vários anos, idéias inteligentes de engenharia, avaliação experimental e um esforço comum da comunidade para resolver o problema. O artigo do CACM de Malik e Zhang é uma boa leitura. Esse algoritmo é ensinado em muitas universidades (participei de quatro onde foi o caso), mas normalmente em uma aula de lógica ou de métodos formais.

As aplicações dos solucionadores SAT são numerosas. IBM, Intel e muitas outras empresas têm suas próprias implementações de solucionadores SAT. O gerenciador de pacotes no OpenSUSE também usa um solucionador SAT.

PageRank é um dos algoritmos mais conhecidos. Desenvolvido pelo co-fundador do Google, Larry Page, e co-autores, ele formou a base do mecanismo de pesquisa original do Google e é amplamente creditado por ajudá-lo a alcançar melhores resultados de pesquisa do que seus concorrentes na época.

Imaginamos um "surfista aleatório" começando em alguma página da Web e clicando repetidamente em um link aleatório para levá-lo a uma nova página. A pergunta é: "Qual fração do tempo o surfista gastará em cada página?" Quanto mais tempo o surfista passa em uma página, mais importante ela é considerada.

$M$

$M^k \pi_0$$k$$\pi_0$$M$

Eu mencionaria a implementação amplamente utilizada do software CPLEX (ou similar) do método / algoritmo Simplex para resolver problemas de programação linear. É o algoritmo (?) Mais utilizado na pesquisa de economia e operações.

"Se alguém fizer estatísticas sobre qual problema matemático está consumindo a maior parte do tempo do computador no mundo, então (sem contar os problemas de manipulação de banco de dados, como classificação e pesquisa), a resposta provavelmente será a programação linear. " (L. Lovász, novo algoritmo de programação linear - melhor ou pior do que o método simplex? Math. Intelligencer 2 (3) (1979/80) 141-146.)

O algoritmo Simplex também tem grande influência na teoria; veja, por exemplo, a conjectura (polinomial) de Hirsch .

Eu acho que um estudante de graduação ou doutorado típico A classe em algoritmos lida com o algoritmo Simplex (incluindo algoritmos básicos de álgebra linear como o Gauss Elimination Method).

(Outros algoritmos bem-sucedidos, incluindo o Quicksort para classificação, estão listados em Algoritmos do livro .)

Pelo que entendi, o National Resident Matching Program foi por muito tempo apenas uma aplicação direta do algoritmo Gale-Shapley para o problema estável do casamento. Desde então, foi ligeiramente atualizado para lidar com alguns detalhes extras, como tarefas de cônjuge (também conhecido como "problema de dois corpos"), etc ...

Se você também inclui material de nível de doutorado, muitos programas de pós-graduação (a maioria?) Incluem algum curso de teoria de codificação. Se você tem um curso de teoria de codificação, definitivamente abordará o código Reed-Solomon, essencial para o funcionamento dos discos compactos e a codificação Huffman, usada nos formatos de arquivo JPEG, MP3 e ZIP. Dependendo da orientação do curso, você também pode cobrir o Lempel-Ziv, que é usado no formato GIF. Pessoalmente, adquiri Lempel-Ziv em um curso de graduação em algoritmos, mas acho que isso pode ser atípico.

O GNU grep é uma ferramenta de linha de comando para pesquisar um ou mais arquivos de entrada por linhas contendo uma correspondência com um padrão especificado. É sabido que o grep é muito rápido! Aqui está uma citação de seu autor Mike Haertel (extraído daqui ):

GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the
final letter of the target string, and uses a lookup table to tell it how far
ahead it can skip in the input whenever it finds a non-matching character.

De maneira mais geral, o prêmio Kanellakis é concedido pela ACM por precisamente essas descobertas teóricas que tiveram um grande impacto na prática.

o prêmio de 2012 é para hash sensível à localidade , que se tornou um método de redução de dimensionalidade na mineração de dados para problemas de vizinhos próximos (e é relativamente fácil de ensinar - pelo menos o próprio algoritmo)

$\varepsilon$

Alguns exemplos de usos industriais dessas estruturas de dados são:

• O sistema Sawzall do Google para análise de dados não estruturados usa o Sketch Sketch para implementar uma função dos 'itens mais populares'
• O sistema de banco de dados de fluxo Gigascope da AT&T para monitoramento de tráfego de rede implementa o esboço CountMin.
• O sistema de monitoramento contínuo (CMON) da Sprint implementa o CountMin.

Aqui também é um site que coleta informações sobre aplicativos do CountMin.

Quanto ao ensino, sei que as técnicas básicas de desenho são ensinadas em Princeton nos cursos de graduação em matemática. Foi-me ensinado o esboço CountMin no meu primeiro curso de algoritmos. De qualquer forma, a análise do CountMin é mais simples do que a análise para quase qualquer outro algoritmo aleatório: é uma aplicação direta da independência por pares e da desigualdade de Markov. Se esse material não é padrão na maioria dos cursos de algoritmos, acho que é por razões históricas.

Na última década, algoritmos foram usados ​​para aumentar o número (e a qualidade, eu acho?) De transplantes de rim através de vários programas de correspondência de doadores de rim. Estou com problemas para encontrar as últimas notícias sobre isso, mas aqui estão pelo menos algumas dicas:

• Em 2007, a Aliança para Doação Pareada usava um algoritmo de Abraham, Blum e Sandholm . Eles ainda podem estar usando, mas não consegui descobrir pesquisando on-line. Embora esse algoritmo quase certamente não seja abordado em cursos "padrão", ele combina várias idéias fundamentais que certamente são ensinadas em tais cursos para fornecer um algoritmo suficientemente bom para um problema que é, em geral, NP-completo (uma variante do Cycle Cover )

• O National Kidney Registry também usa alguns algoritmos padrão, incluindo (em um ponto) o CPLEX. Isso levou a uma cadeia de transplantes realmente realizada , ligando 60 pessoas .

Este é um dos meus exemplos favoritos, não apenas do sucesso de algoritmos, mas da importância de estudar algoritmos para problemas completos de NP. Eles podem literalmente salvar vidas , e já o fizeram!

O algoritmo de Viterbi, que ainda é amplamente usado no reconhecimento de fala e em várias outras aplicações: http://en.wikipedia.org/wiki/Viterbi_algorithm O algoritmo em si é uma programação dinâmica básica.

Da Wikipedia: "O algoritmo Viterbi foi proposto por Andrew Viterbi em 1967 como um algoritmo de decodificação para códigos convolucionais através de links ruidosos de comunicação digital. [1] O algoritmo encontrou aplicação universal na decodificação dos códigos convolucionais usados ​​no celular digital CDMA e GSM, modems dial-up, satélite, comunicações no espaço profundo e LANs sem fio 802.11. Agora também é comumente usado em reconhecimento de voz, síntese de fala, localização de palavras-chave, linguística computacional e bioinformática. Por exemplo, em fala para texto (fala reconhecimento acústico), o sinal acústico é tratado como a sequência de eventos observada e uma sequência de texto é considerada a "causa oculta" do sinal acústico. O algoritmo Viterbi encontra a sequência de texto mais provável, dado o sinal acústico ".

1. A * é usado em muitos dispositivos de navegação pessoal (também conhecidos como unidades de GPS)
2. A * é muito bem definido e foi implementado de maneira bastante direta.
3. A * não é inteiramente trivial, mas não é necessário um doutorado. para entender isso.

Confira o projeto de Jens Vygen BonnTools para Chip Design. http://www.or.uni-bonn.de/~vygen/projects.html Eu ouvi algumas conversas sobre isso e também observei alguns de seus artigos. Eles usam o arredondamento aleatório no estilo Raghavan-Thompson, bem como o método de atualização de peso multiplicativo para resolver LPs de fluxo multicomodidade em larga escala. No entanto, como qualquer grande projeto, eles também precisam fazer alguma engenharia, mas a metodologia é muito baseada em algoritmos conhecidos.

Engraçado que eu vi essa pergunta hoje e, por coincidência, cliquei neste link nos muitos usos da Transformada de Fourier .

Estou bastante surpreso que, com todos os algoritmos sofisticados acima, ninguém mencionou a venerável família de algoritmos de compressão Lempel-Ziv (inventada em 1977/78).

1. Esses são usados ​​em qualquer lugar - texto para imagem e processamento de fluxo. É bem possível que LZ * seja uma única família de algoritmos mais usada existente.
2. A compactação de dicionário foi um avanço considerável na teoria de compactação e um afastamento da abordagem ao estilo de Shannon-Fano.
3. Os algoritmos da família são bastante diretos e fáceis de compreender.

Atualizar

Aparentemente, isso já foi mencionado brevemente.

a decomposição de valor singular (SVD) tem uma forte conexão com a análise fatorial estatística ou análise de componentes principais e é compreensível em uma álgebra linear de graduação ou classe estatística e possui muitas propriedades teóricas importantes. Ele também desempenha um papel nos algoritmos de compactação de imagem. desempenhou um elemento-chave nas entradas vencedoras no concurso de premiação da Netflix de US $ 1 milhão (uma das maiores competições de datamining do mundo na história) e agora está implementado em seu site para prever as classificações dos usuários. também é conhecido por ser altamente relacionado às redes neurais auto-organizadas de Hebbian que se originam na teoria biológica.

existe alguma conexão também com a descida do gradiente, que é amplamente utilizada no aprendizado de máquina e nas redes neurais artificiais e como uma técnica de otimização aplicada universalmente, caso em que o método de Newton é uma forma 2D básica. existe um algoritmo de descida gradiente para obter o SVD.

Encontrar um caminho euleriano está na base da montagem do genoma - uma tarefa comumente executada ao trabalhar com genomas completos (em bioinformática, medicina, forense, ecologia).

ATUALIZAÇÃO Esqueceu esta óbvia: a UPS, a FedEx, a USPS precisam resolver grandes instâncias do problema do vendedor ambulante todas as noites. Economiza muito tempo e dinheiro para que eles enviem os motoristas em uma rota ideal.

UPDATE2 O problema do conjunto de vértices com feedback mínimo é usado para a resolução de conflitos em muitos sistemas operacionais.

Eu gosto deste sistema para salvar o número máximo de vidas no Reino Unido com transplantes de rim, com base em algoritmos de correspondência máxima: Doação de rim emparelhado e altruísta . Eles combinam pessoas que precisam de rins que tenham um amigo / parente não correspondente disposto a doar, com outras pessoas na mesma situação, de uma maneira máxima. Então, no dia da doação, todos os doadores doam ao mesmo tempo, seguidos por um rápido transporte de rins pelo país para os destinatários.

vale a pena considerar este livro relativamente novo como uma resposta completa / detalhada para a pergunta de forma conveniente, estendida / coletada e que pode ser usada como material suplementar para uma classe de algoritmos. [alguns deles já foram mencionados; a forte sobreposição em si é notável.]

• Nove algoritmos que mudaram o futuro: as idéias engenhosas que impulsionam os computadores de hoje por MacCormick

  • indexação de mecanismos de pesquisa
  • Ranking da página
  • criptografia de chave pública
  • códigos de correção de erros
  • reconhecimento de padrões
  • compressão de dados
  • bases de dados
  • assinaturas digitais
  • teoria da computabilidade

• outra referência um tanto semelhante, mas mais teórica, Os Melhores do Século 20: Os Editores Nomeiam os 10 Melhores Algoritmos Cipra / SIAM.

  • Método de Monte Carlo
  • algoritmo simplex
  • Iryation do subespaço de Krylov
  • computação matricial decompositiva
  • Compilador Fortran
  • Algoritmo de matriz QR
  • ordenação rápida
  • FFT
  • detecção de relação de número inteiro
  • algoritmo multipolar rápido

A busca por string de Knuth-Morris-Pratt é amplamente usada, específica e ensinada na graduação / pós-graduação em CS.

Pensando em algoritmos muito básicos

1. Geradores de números aleatórios são encontrados em todos os lugares e especificamente em todos os jogos.
2. Os bancos de dados são compostos de muitos algoritmos, incluindo B +, Hashes, filas prioritárias, expressão regular, criptografia, classificação, etc. Um amigo meu diz que os SGBDs estão no topo da cadeia alimentar de computação.
3. A classificação é usada em qualquer lugar, por exemplo, no Excel. Na verdade, é usado o tempo todo na vida real, mas geralmente os humanos usam algoritmos ad-hoc
4. Os bits de paridade são usados ​​em toda a volta
5. A codificação Huffman está no software de compressão e transmissão
6. Pilhas (LIFO) são usadas em todos os lugares. Linguagens de programação internas, em CPUs, etc ...

É bom mostrar que eles aparecem na vida real:

A. Muitos grupos usam um tipo de algoritmo de árvore de cobertura para se comunicar, dividindo as listas telefônicas de maneira hierárquica entre as pessoas. B. Os carros em um cruzamento geralmente usam um algoritmo de rodízio (de forma voluntária). hospital, organizam seus clientes em um algoritmo FIFO

Um problema algorítmico fascinante surge na aplicação médica da tomografia computadorizada. Na tomografia computadorizada (TC), o corpo é exposto a raios-X de diferentes ângulos. Em uma extremidade do scanner estão os transmissores de raios-X e na outra extremidade os sensores. A partir de uma série de exames, uma imagem é reconstruída para o médico examinar!

O algoritmo de retroprojeção filtrada é a base para a reconstrução de uma imagem a partir de um conjunto de digitalizações. Esse algoritmo é realmente uma forma de um problema de aproximação no qual o "sinal" é amostrado abaixo da taxa de Nyquist. Esse algoritmo está em uso "nos bastidores" em todos os hospitais e a projeção traseira filtrada básica utiliza matemática de graduação, como as transformadas de Fourier para alcançar o Teorema da Fatia de Fourier .

Um exemplo de FFT

Certa vez, ajudei a portar um algoritmo FFT para um idioma de sistema diferente.

O algoritmo estava sendo usado para determinar quebras de linha na entrega coaxial de tv a cabo / internet / telefone. Basicamente, um técnico solicita que um sinal seja enviado à caixa do cliente, ao mesmo tempo em que exibe uma exibição em tempo real das estatísticas para um cliente específico, como QoS, dB, ... O técnico pode usar os dados e um gráfico para determinar a poucos metros entre a casa e o poste onde houve uma interrupção parcial (ou várias interrupções, como me disseram).

Como mencionado acima, a FFT é amplamente usada, mas essa foi uma das mais flagrantes e óbvias (em termos de por que e como) que eu vi na prática.

Desculpe, tive que manter um nível alto.

O algoritmo de linha de Bresenham é o algoritmo mais útil que encontrei. Fácil de entender Eu o usei para muitas aplicações, desde desenho de linhas a um spliner complexo para mecanismo de fundição 3D até renderizador de polígonos complexo, além de animações complexas e usos de escala.

Planejamento de rota personalizável (Daniel Delling, Andrew V. Goldberg, Thomas Pajor e Renato F. Werneck) http://research.microsoft.com/apps/pubs/default.aspx?id=145688

habilita o Bing Maps: http://www.bing.com/blogs/site_blogs/b/maps/archive/2012/01/05/bing-maps-new-routing-engine.aspx

A Wikipedia possui uma coleção decente de algoritmos / aplicativos classificados mais ou menos em uma lista . A Microsoft fornece os principais artigos citados, mas sem nenhuma explicação explícita da área de ciência da computação nem do aplicativo. Há também uma lista cronológica de diferentes conferências de CS _http: //jeffhuang.com/best_paper_awards.html_ compilada pelo Prof. Huang.

O Spectral Clustering é um algoritmo de cluster elegante, conhecido como algoritmo de cortes normalizados , introduzido por Jianbo Shi e Jitendra Malik para segmentação de imagens. Também foi bem desenvolvido em aplicativos de cluster de dados, sendo uma boa interseção entre as duas comunidades.

dois outros exemplos favoritos pessoais firmemente enraizados na ciência da computação, mas talvez facilmente ignorados pelos teóricos abstracionistas, que passaram por enormes / transformadores avanços e tiveram um impacto prático / aplicado de grande a grande massa na vida cotidiana nas últimas décadas. já uma geração inteira cresceu sem conhecer o mundo sem eles. basicamente a categoria de modelagem e simulação .

• algoritmos de simulação física . principalmente usando leis de Newton, mas usando outras leis (como dinâmica de fluidos). usado em uma ampla variedade de aplicativos, desde aplicativos de engenharia, videogames e, às vezes, filmes. este também é responsável por melhorar significativamente a segurança, eficiência ou confiabilidade de, por exemplo, carros e aviões, submetendo os projetos virtuais / de teste a tensões simuladas. uma importante área de pesquisa em andamento relacionada à bioinformática com implicações maciças na biologia, por exemplo, design de medicamentos, prevenção de doenças, etc: dobragem de proteínas / previsão de estruturas . Observe também que este ano o Prêmio Nobel de Química foi concedido por simulação química, a Karplus, Levitt, Warshel. algoritmos de simulação física estão altamente envolvidos na segurança / teste de armas nucleares por exemplo, nos laboratórios de Los Alamos.

• algoritmos de raytracing / CGI . isso começou como um tópico de pesquisa há apenas algumas décadas [um amigo obteve seu diploma de mestrado em algoritmos de rastreamento de raios-X por CS], mas se tornou muito aplicado em, por exemplo, jogos e negócios de produção de filmes, atingindo níveis extraordinários de verossimilhança, responsável por grandes quantidades de efeitos especiais em filmes. essas indústrias têm literalmente bilhões de dólares investidos e utilizam esses algoritmos e grandes corporações inteiras se baseiam em aproveitá-las, como a Pixar . principalmente usada inicialmente em, por exemplo, filmes scifi, a técnica agora é tão difundida que é usada rotineiramente, mesmo em filmes "típicos". por exemplo recentemente The Great Gatsby dependia fortemente de efeitos CGI para desenhar ambientes convincentes ou estilizados, retocar o filme / personagens etc.

O Código Rosetta lista os algoritmos aplicados pela Tarefa de Programação (692) e pela Linguagem de Programação (518) com o Semantic MediaWiki.

talvez todos os principais / preferidos algoritmos de interesse para esse público tenham sido mencionados neste momento. no entanto, mais alguns merecem menção pela integridade. & alguma análise do que é considerado um algoritmo significativo é relevante aqui.

nos campos de CS e TI, parece haver um fenômeno observado há muito tempo na IA chamado "mover as traves do gol" . esse é um fenômeno psicológico em que o campo avança relativamente rápido, mas as pessoas rapidamente se ajustam mentalmente ao "novo normal" e consideram os avanços reais ou mesmo revolucionários como mundanos ou não-observáveis ​​em retrospecto, depois de realizados, ou seja, subestimados ou minimizados. isso é altamente capturado nesta questão da maneira como os algoritmos passam da P&D para a "implantação". citando o autor da pergunta em comentários posteriores:

De fato, uma fração desprezível de todo o código que é escrito está implementando qualquer coisa interessante do ponto de vista algorítmico.

mas isso é problemático e basicamente uma redefinição centrada no TCS da palavra "algoritmo". presumivelmente, os algoritmos interessantes são avançados. isso significa que, se um problema é reduzido a um algoritmo avançado, ele não é mais "interessante"? e "avançado" é claramente um alvo em movimento. portanto, existe uma maneira de definir "algoritmos" de maneira restrita ou ampla . parece que a definição do TCS muda de contexto, mas note que, mesmo no TCS, há uma tendência em direção à definição ampla, por exemplo, nas chamadas "lentes algorítmicas" .

Às vezes, os algoritmos mais onipresentes também são os mais ignorados! a internet e a WWW são um ambiente amplo / quase ecológico para algoritmos. ainda relativamente jovem, com apenas 2 décadas de idade (inventado ~ 1991), cresceu maciça e exponencialmente em um curto período de tempo. O crescimento do site WWW provavelmente superou a famosa lei exponencial de Moores.

Internet / WWW são suportados por muitos algoritmos sofisticados. a internet possui algoritmos complexos de roteamento incorporados aos roteadores (alimentando novamente empresas de bilhões de dólares, como a Cisco). alguma teoria avançada é aplicável lá, por exemplo, em algoritmos de roteamento . Esses algoritmos foram objeto de pesquisas emergentes e avançadas / de ponta décadas atrás, porém agora são tão afinados e bem compreendidos que são um tanto invisíveis.

não devemos esquecer tão cedo que décadas atrás, os principais pesquisadores nem sequer tinham certeza se o mundo da Internet funcionava ou era possível (visto em pesquisas anteriores de troca de pacotes, um novo padrão radical de design no momento em que a troca de circuitos anterior) e mesmo alguns anos atrás, havia o receio de que ele não chegasse a ser dimensionado em algum momento e começaria a falhar devido a picos esmagadores de volume.

Ele também usa detecção / correção sofisticada de erros . a internet provavelmente é o maior sistema mais tolerante a falhas já construído por humanos, ainda em crescimento.

a seguir, há um argumento forte para fazer com que os algoritmos que alimentam a WWW sejam avançados. Os servidores HTTP e da Web são altamente ajustados / otimizados e também usam protocolos avançados de segurança / criptografia (HTTPS). a lógica de renderização de uma página da Web tornou-se extremamente avançada em HTML5 e CSS3 , junto com a linguagem de programação Javascript .

o CSS relativamente novo possui vários princípios semelhantes à programação OOP , como reutilização e herança. por falar em tipografia, o TeX é um sistema de tipografia científica importante e complexo internamente (não tão diferente de uma linguagem de programação) inventado por Knuth que agora pode ser renderizado em páginas da web (e usado em centenas de milhares de artigos científicos ou mais).

outra área relativamente nova de algoritmos construídos na internet, ainda emergentes, aqueles baseados em inteligência coletiva . O software stackexchange em si é um exemplo de um sofisticado sistema de inteligência coletiva. as redes sociais também exibem os principais recursos da inteligência coletiva e os recursos são continuamente adicionados para aumentar essa inteligência (por exemplo, os "likes" do facebook têm apenas alguns anos). o campo dos sistemas de classificação é baseado em algoritmos de filtragem colaborativa e ainda está evoluindo com base em novas pesquisas e aplicações.

portanto, em resumo, todos os sucessos revolucionários que transformam a experiência humana diária, na verdade, muito além de meramente "objetivos de campo". como afirma o título da pergunta, todos os principais algoritmos foram implantados . agora tão onipresente e invisível que parece algo como a expressão de TI, "parte do encanamento".

Um algoritmo incrivelmente bem-sucedido (hardware) é a redefinição de inicialização.

Sem um sistema no qual um computador esteja em um estado conhecido quando a energia é aplicada, nada mais acontece corretamente .

A redefinição de inicialização é o motivo pelo qual tudo funciona com uma CPU, seja ela incorporada ou não.

Da próxima vez que você estiver no regador para programadores e cientistas da computação, levante seu copo de refrigerante de cereja para a redefinição de inicialização.