Quais algoritmos mais importantes do mundo contribuíram mais para a humanidade nas últimas décadas?
Eu pensei que este é um bom conhecimento geral para um desenvolvedor conhecer.
Atualização:
Se possível, mantenha a resposta para um algoritmo de programação específico .
Gostaria de obter uma lista dos mais importantes, apenas um algoritmo por resposta.
Por favor, considere indicar por que o algoritmo é significativo e importante ...
algorithms
problem-solving
knowledge
Amir Rezaei
fonte
fonte
Respostas:
A criptografia de chave pública / privada é muito importante. O comércio na Internet não seria tão onipresente sem ele.
fonte
Algoritmo de Dijkstra
O algoritmo existe em todos os roteadores do mundo, para identificar a melhor rota entre dois nós em uma rede.
fonte
Transformada rápida de Fourier (FFT)
O FFT é um método extremamente importante e amplamente utilizado para extrair informações úteis de sinais amostrados .
fonte
Ranking da página
fonte
Algoritmos de compactação de dados
fonte
Smith-Waterman (e Needleman-Wunsch)
Isso pode ser muito buscado, por favor, comente.
Smith-Waterman: O Algoritmo de Alinhamento de Sequência
Penso que um desses exemplos são os algoritmos de Smith-Waterman e Needleman-Wunsch e suas aproximações. Todos eles estão essencialmente fazendo a mesma coisa: alinham duas ou mais seqüências de caracteres . Há um significado na biologia. Quando as seqüências de DNA ou proteína são alinhadas - regiões de similaridade estrutural, funcional e evolutiva são reveladas.
BLAST como descendente de Smith-Waterman
Uma heurística que se aproxima de Smith-Waterman é BLAST. Permite pesquisar sequências de grandes bancos de dados quanto à similaridade biológica. A popularidade do BLAST é realmente grande - é muito provavelmente o algoritmo mais usado em Biologia. As áreas mais recentes de Bioinformática e Genômica têm aproximações melhores e mais novas dos algoritmos Smith-Waterman / Needleman-Wunsch, que são mais precisos que o BLAST.
Assembléia do Genoma como descendente de Smith-Waterman
As aproximações de alto rendimento de Smith-Waterman e Needleman-Wunsch, que são mais rápidas que o BLAST, são usadas para montar os genomas a partir do sequenciamento de espingarda - onde o produto da máquina sequenciadora é uma quantidade enorme de leituras de DNA (bilhões) de partes arbitrárias do genoma. muito curto (50 a 100 nucleotídeos). A abordagem foi usada para concluir o Projeto Genoma Humano. Todo o seqüenciamento moderno é feito dessa maneira.
Alinhamento de Seqüências Múltiplas uma extensão de Smith-Waterman
Existem numerosos algoritmos de alinhamento de múltiplas seqüências - eles estão se aproximando de uma versão de várias seqüências do Smith-Waterman / Needleman-Wunsch. Várias sequências são alinhadas como um grupo simultaneamente entre si. É um problema muito mais difícil do que o equivalente aos pares, mas as soluções fornecem muito mais informações sobre a função biológica, a estrutura e a história evolutiva das seqüências relacionadas.
fonte
Siam nomeou os seguintes como os algoritmos mais importantes do século XX:
1946: O algoritmo da metrópole para Monte Carlo . Através do uso de processos aleatórios, esse algoritmo oferece uma maneira eficiente de encontrar respostas para problemas que são muito complicados para resolver exatamente.
1947: Método Simplex para Programação Linear . Uma solução elegante para um problema comum no planejamento e tomada de decisão.
1950: Método de Iteração do Subespaço de Krylov . Uma técnica para resolver rapidamente as equações lineares que abundam na computação científica.
1951: A Abordagem Decompositiva para Computações Matrix . Um conjunto de técnicas para álgebra linear numérica.
1957: O Fortran Optimizing Compiler . Transforma código de alto nível em código legível por computador eficiente.
1959: Algoritmo QR para computação de autovalores . Outra operação crucial da matriz tornada rápida e prática.
1962: Algoritmos de classificação rápida para classificação . Para o manuseio eficiente de grandes bancos de dados.
1965: Transformação rápida de Fourier . Talvez o algoritmo mais onipresente em uso hoje em dia, quebre formas de onda (como som) em componentes periódicos.
1977: Detecção de relação de número inteiro . Um método rápido para identificar equações simples satisfeitas por coleções de números aparentemente não relacionados.
1987: Método Multipolar Rápido . Uma inovação ao lidar com a complexidade dos cálculos de n corpos, aplicada em problemas que vão da mecânica celeste à dobragem de proteínas.
Pessoalmente, eu substituiria a Integer Relation Detection pelo PageRank .
fonte
PageRank, ame ou odeie, mas afeta as decisões e ações de milhões de pessoas no mundo todo pesquisando diariamente no Google.
fonte
Se eu tivesse que listar os três principais algoritmos mais importantes em uso hoje em computadores, eu diria:
O algoritmo de busca binária é usado constantemente para restringir um item em uma lista classificada, a maioria das pesquisas de índice usará algo nesse sentido em algum momento. Esse algoritmo fornece uma pesquisa de uma lista ordenada em o (log n).
O algoritmo Quicksort finalmente conseguiu classificar para O (n log n) caso médio e O (n ^ 2) caso pior. A classificação é uma das tarefas de dados mais comuns em um computador e uma das mais caras, pois melhorar a classificação média de casos foi um grande avanço em termos de eficiência.
O algoritmo de Dijkstra, como já foi dito, produz um caminho mais curto entre os pontos dentro de um gráfico. Isso é amplamente utilizado para todos os tipos de aplicativos de roteamento, mais amplamente em relação à própria Internet, garantindo que o caminho mais rápido através da rede emaranhada de roteadores interconectados seja usado.
fonte
Teorema de Bayes
Provavelmente, contribuiu mais para manter a quantidade de spam que desperdiçou tempo na minha caixa de entrada em um nível gerenciável.
É claro que sou usado em várias outras aplicações que valem a pena, mas matar SPAM é o meu favorito.
fonte
TimSort
Este é o algoritmo de classificação agora usado em Python , Java 7 e Android
Basicamente:
N-1
exatamente na lista já classificada)E a beleza disso? É estável ! E, portanto, adequado para a classificação multipass de acordo com vários critérios.
A propósito, se alguém tiver uma implementação C ++ otimizada disponível ...
fonte
Todos os algoritmos usados para resolver o problema de visibilidade na animação por computador em 3D parecem cruciais para mim.
Algoritmo do pintor
Z-buffering
Determinação de superfície oculta
fonte
Qualquer um que você precise para resolver seu problema atual.
fonte
Soundex é um algoritmo fonético para indexar nomes por som.
fonte
Algoritmo de Viterbi
Originalmente usado para decodificar códigos de correção de erros convolucionais, agora é usado para resolver uma ampla classe de problemas de reconhecimento (variando de reconhecimento de fala a bioinformática). Você pode encontrá-lo em vários dispositivos de comunicação e armazenamento.
fonte
MP3
Embora seja um termo mais geral do que um algoritmo específico, eu mencionaria o MP3 como a agregação dos diferentes algoritmos e técnicas que trabalham em cooperação para gerar esse formato de áudio com perdas.
Certamente foi muito significativo na "era digital".
fonte
Integração numérica Runge-Kutta . Sem ele, muitas simulações não seriam possíveis. Sem programa espacial, sem energia nuclear, sem balística, sem simulações esportivas, sem coletes à prova de balas, sem simulação de teste de colisão, sem simulação de movimento de fluidos, sem simulações de interação química, sem edifícios resistentes a terremotos ... a lista continua.
fonte
Algoritmo de classificação.
fonte
Ordenação rápida
fonte
Classificação de inserção
Fácil de implementar, muito rápido em pequenas listas e usado nas implementações Merge Sort / Quicksort para agilizá-las. É estável e opera em O (n) em listas classificadas (quando classificadas em ordem crescente).
fonte
Gauss-Jordan em computação matricial
fonte
Kalman Filter
Ele é muito usado na navegação e no rastreamento de alvos (para praticamente qualquer sensor: radar, sonar, FLIR, ladar). Um livro mostra um aplicativo em um controlador de unidade de disco. Os sistemas de controle robótico freqüentemente usam filtros Kalman.
fonte
Linguagem falada e escrita.
Atualmente, eles são um dos algoritmos mais eficientes para transferir conhecimento de uma coisa para outra. Sem linguagem, a sociedade civil não poderia existir e a informação não poderia ser transmitida.
fonte
A estrutura de dados do heap e seus algoritmos associados para construção e manutenção de heap.
E mostre algum respeito pelo quicksort. Mesmo que nem sempre seja o tipo de escolha, é um dos algoritmos fundamentais no desenvolvimento histórico da ciência da computação e é um ótimo veículo para entender a recursão e a análise de algoritmos. É lindo, e sim, eu amo isso.
fonte
Algoritmos de indexação como árvore B, árvore B +, índice de hash, índice de árvore binária etc. Para indexar uma enorme quantidade de dados.
fonte
MapReduce como uma maneira de dividir, conquistar e paralelizar o processamento de grandes conjuntos de dados.
fonte
Algoritmo de força bruta!
Muitas pessoas subestimam esse algoritmo de força bruta. Na verdade, é usado principalmente para resolver problemas sem padrão. Eu amo muito isso!
fonte
Tipo de bolha !
O tipo de bolha não é tão ruim quanto o Bogosort . É por isso que voto no tipo de bolha.
fonte