Algoritmos principais implantados

307

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.

Manu
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Bjørn Kjos-Hanssen

Respostas:

473

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 .
Também existem estruturas e algoritmos de dados no código de terceiros incluído no código do Chromium.

  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.

Vijay D
fonte
5
@HuckBennett, CDCL é um algoritmo parametrizado por heurísticas, mas não é em si uma heurística. Ele tem um comportamento exponencial do pior caso, mas não é trivial mostrar isso. Além disso, não podemos ter um desempenho comprovadamente melhor, e é o melhor que podemos fazer na prática, então sinto que todos os cientistas da computação deveriam saber disso! Quanto ao LRU, FIFO etc., são heurísticas, mas, como no ARC, podem exigir algoritmos ou estruturas de dados inteligentes para implementar.
Vijay D
9
Esse comentário não se aplicaria ao Simplex: inicialmente não é bem entendido e mais tarde se mostra exponencial, mas funciona na prática e muito mais tarde se mostra com complexidade polinomial suavizada? O CDCL é interessante para a análise de algoritmos porque você precisa passar pela complexidade da prova para derivar famílias de fórmulas que exibem o pior comportamento e também para mostrar que pode ser exponencialmente mais sucinto do que algumas variantes de resolução. Existem várias extensões, como técnicas de quebra de simetria e autarquia, para as quais essa análise ainda está aberta.
Vijay D
28
Este é um tesouro para um estudante
neo1691
2
@EmanueleViola, adicionei mais alguns exemplos. A postagem está longa agora, então não quero estendê-la. Talvez você deva fazer uma nova pergunta especificamente sobre implementações de filtros Dijkstra, Simplex, Bloom como parte de um sistema real como Linux, Chrome, um servidor da web etc. Acho que é mais provável que você obtenha boas respostas se for específico.
Vijay D
4
Notícias do hacker er / programação.
precisa
40

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

Mkπ0kπ0M

Huck Bennett
fonte
7
Eu não acho que isso seja material típico de algoritmos.
Manu
14
Aliás, eu aprendi sobre o PageRank em uma classe de algoritmos. De fato, acho que o professor escolheu porque era um bom exemplo de "algoritmos usados ​​na prática". Se você limitar exemplos ao material do tipo "primeira metade do CLRS", a lista de exemplos será muito longa ou trivial - quicksort, árvores B e o algoritmo de Dijkstra são onipresentes.
Huck Bennett
2
Ensinamos o PageRank a estudantes de graduação.
Aaron Roth
6
Também o ensino para alunos de graduação (tanto na classe de algoritmos exigidos quanto em uma eletiva de algoritmos gráficos mais especializados).
9788 David Eppstein #
2
Eu aprendi PageRank como um estudante de graduação em uma eletiva.
Vijay D
33

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

vb le
fonte
"pesquisa de economia e operações" não é suficientemente específico. O CPLEX também não é o tipo de exemplo que eu estava procurando, pois é apenas uma implementação do algoritmo; seria diferente se, digamos, o compilador gcc usasse o método simplex.
Manu
12
Eu acho que "problemas de programação linear" são específicos o suficiente quando falamos de economia e OR. Além disso, com o CPLEX, eu quis dizer o algoritmo por trás da implementação.
vb le
16
"Hoje, a maioria das grandes empresas usa programação linear para precificar produtos e gerenciar cadeias de suprimentos. As empresas de transporte usam-na para escolher a maneira mais barata de consolidar, coordenar e encaminhar remessas de muitos produtos, de fornecedores distribuídos globalmente a mercados distantes, sujeitos a restrições de capacidade. A indústria o utiliza para avaliar minérios de ferro, explorar a adição de fornos de coque e selecionar produtos ... " news.stanford.edu/news/2005/may25/ dantzigobit-052505.html
Sasho Nikolov
Obrigado. Mas acho a citação terrivelmente vaga. Eu acho que se eu disser que na frente de uma turma de alunos, metade dela adormeceria ;-) Seria diferente se disséssemos algo como: a UPS usa LP para enviar pacotes da seguinte maneira ... Eu não estou dizendo tais exemplos são triviais de se encontrar, mas, como "a maioria das grandes empresas usa LP", espero que possamos ao menos apontar para uma .
Manu
10
Desde o início, desde 2007, o LAX (o aeroporto) usa software para resolver os jogos da Stackelberg para agendar o pessoal de segurança. A solução de LPs grandes faz parte de tudo, veja, por exemplo, teamcore.usc.edu/ARMOR-LAX . Além disso, gostaria de pedir a alguém do seu departamento de Pesquisa Operacional: eles normalmente teria muitas histórias de guerra sobre o uso de LP na vida real
Sasho Nikolov
30

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

mhum
fonte
Não tenho certeza se o casamento estável é material típico de algoritmos.
Manu
16
Está no livro de Design de Algoritmos de Tardos e Kleinberg, e também nos Algoritmos Aleatórios de Motwani, e ambos os livros são amplamente utilizados. O casamento estável pode não ser universalmente ensinado nos cursos de algoritmos, mas certamente é ensinado em muitos deles.
Sasho Nikolov
10
Uma rápida pesquisa revela que tem se manifestado em CS70 de Berkeley , MIT 6.042 , de UMD CMSC451 , etc ...
mhum
1
Curiosamente, quando você adiciona atribuições de cônjuge, o problema se torna NP-completo: arxiv.org/abs/1308.4534 . No entanto, na prática, isso não parece causar muito de um problema: en.wikipedia.org/wiki/...
Joshua Grochow
2
@EmanueleViola enquanto ele não pode ser coberto tradicionalmente, a sua inclusão no livro Kleinberg / Tardos tornou mais popular, (e se não deveria ser!)
Suresh Venkat
24

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.

mhum
fonte
1
E recebi uma palestra sobre a codificação Huffman como graduação, necessária para um projeto.
Brian S
Huffman está em um dos primeiros capítulos de CLRS, por isso deve definitivamente qualificar
Sasho Nikolov
21

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.
Dai Le
fonte
19

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)

Suresh Venkat
fonte
Eu acho que isso é ensinável, mas não é amplamente ensinado.
Manu
3
Infeliz, mas é verdade. No entanto, variantes do LSH (como o esboço Count-min e parentes) estão começando a aparecer nos cursos "dados grandes" ou "mineração de dados". Eu ensino filtros de bloom na minha classe de algoritmos, por exemplo.
precisa
Como experiência pessoal, o LSH não foi escalado para nós em uma instância de "big data" (itens de 100 mln).
Lynxoid
1
@lynxoid que é uma discussão / pergunta separada :). Existem exemplos suficientes de onde ele não trabalhar que eu acho que é relevante para esta questão particular.
Suresh Venkat
18

ε

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.

Sasho Nikolov
fonte
1
Bons exemplos (embora não seja algo muito básico no momento).
Manu
16

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!

Joshua Grochow
fonte
Além disso, uma versão mais simples destes algoritmos é usado para trocar jogos de tabuleiro: okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html
Radu Grigore
15

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

Grigory Yaroslavtsev
fonte
13
  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.
MSalters
fonte
A * também é frequentemente ensinado em design de jogos. Eu não acho que jogos 3D modernos geralmente usem A * para navegação NPC, mas jogos 2D / isométricos, bem como jogos antigos, fazem uso do algoritmo.
Brian S
@BrianS Você conhece exemplos de algoritmos de busca de caminhos usados ​​em jogos 3D, especificamente NPCs inimigos em jogos (como um atirador npc) Lembro-me de ler algo como ... dividir um mapa em setores hexagonais e usá-lo como nó, em vez de quadrados , e isso permitiu um movimento mais suave.
Goodwine
@ Goodwine, desculpe, não tenho exemplos reais de algoritmos de busca de caminhos em jogos 3D. Minha experiência pessoal foi em ambientes do tipo "cubo" (mapa feito de cubos, em que os personagens se sustentam - basicamente em 2D, apesar da renderização em 3D) e AIs fictícias usadas para testar os personagens dos jogadores.
Brian S
12

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.

Chandra Chekuri
fonte
Vou dar uma olhada, mas não soa como material típico de algoritmos.
Manu
8
Hmm, o arredondamento aleatório é normalmente ensinado nos cursos de algoritmos de nível de doutorado, não?
Chandra Chekuri
2
Por que apenas arredondamentos aleatórios? Sanjeev Arora, Elad Hazan e Satyen Kale acham que mesmo o método de atualização de pesos multiplicativos é básico o suficiente para ser ensinado no nível UG :) "Achamos que nosso meta-algoritmo e sua análise são simples e úteis o suficiente para que possam ser vistos como uma ferramenta básica ensinado a todos os alunos de algoritmos, juntamente com dividir e conquistar, programação dinâmica, amostragem aleatória e similares ". (cf. cs.princeton.edu/~arora/pubs/MWsurvey.pdf ).
Jagadish
10

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.

oakad
fonte
10

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.

vzn
fonte
10

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.

lince
fonte
Você tem certeza de que o TSP é o problema que as empresas de entrega de encomendas estão tentando resolver? Eu pensei que um desafio prático maior era a mochila e outros tipos de problemas de embalagem.
András Salamon
As atribuições dos motoristas mudam todos os dias (por exemplo, o funcionário da UPS não precisa visitar a mesma casa todos os dias), portanto, as rotas precisam ser atualizadas diariamente. Não é um TSP puro - há restrições adicionais, como ruas de mão única, sem inversões de marcha, entrega de pacotes em um lado da rua, mas não no outro.
Lynxoid
Tenho certeza de que a embalagem também é importante.
Lynxoid
9

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.

Alnitak
fonte
8

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

vzn
fonte
A segunda referência é originalmente da edição de janeiro / fevereiro de 2000 da Computing in Science & Engineering, uma publicação conjunta do Instituto Americano de Física e da IEEE Computer Society. compilada por editores convidados Jack Dongarra da Universidade do Tennessee e Laboratório Nacional de Oak Ridge e Francis Sullivan, do Centro de Ciências da Computação do Instituto de Análises de Defesa
vzn
7

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

Darth Egregious
fonte
2
Seria bom se você pudesse apontar para um uso específico. Algo como o MS Word usa KMP.
Manu
6

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

user19461
fonte
4
A classificação não é um algoritmo. É uma tarefa, ou seja, algo que você deseja executar, para o qual você deve projetar (ou, na prática, escolher) um algoritmo.
David Richerby
Estes não parecem ser exemplos específicos, conforme solicitado na pergunta.
Kaveh
SGBD == RDBMS FYI para quem não sabia.
Autodidata
6

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 .

Leeor
fonte
6

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.

ClericGunem
fonte
5

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.

TimRing
fonte
2

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.

Ravi Kiran
fonte
-2

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.

vzn
fonte
-3

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.

Wes Turner
fonte
Como isso é um exemplo de "algoritmos principais ... implantados em software / hardware comercial, governamental ou amplamente utilizado"?
David Richerby
Seria útil fazer referência cruzada das implementações de cada um dos excelentes algoritmos listados em outras respostas aqui para URIs da Wikipedia / DBpedia. Não há URIs da Wikipedia / DBpedia para todos esses algoritmos; mas há páginas do código Rosetta.
precisa
O bigocheatsheet.com também lista a complexidade do Big-O e links para artigos da Wikipedia para alguns algoritmos.
Wes Turner
A pergunta pede exemplos de algoritmos principais usados ​​em partes significativas de software. "Aqui está um site com algoritmos implementados em um milhão de idiomas" não responde a essa pergunta. De fato, é exatamente o oposto do que a pergunta está procurando.
David Richerby
Uma referência útil contextualmente relevante, no entanto.
Wes Turner
-5

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

vzn
fonte
muitas citações poderiam ser adicionadas a isso. aqui está uma para começar: DARPA ea revolução internet por Waldrop
vzn
outra referência na otimização internet, biografia de Danny Lewin , co-fundador da Akamai, "o gênio que transformou a internet"
vzn
-8

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.

Anon
fonte
5
A redefinição de inicialização não é um algoritmo. É uma tarefa, ou seja, algo que você deseja executar, para o qual você deve projetar um algoritmo.
David Richerby