O que são paradigmas algorítmicos?

8

Geralmente falamos sobre paradigmas de programação como funcionais, procedurais, orientados a objetos, imperativos, etc. Mas o que devo responder quando me perguntam os paradigmas de algoritmos?

Por exemplo, o problema do vendedor ambulante, o algoritmo de caminho mais curto de Dijkstra, o algoritmo Euclid GCD, a pesquisa binária, a árvore de abrangência mínima de Kruskal, os paradigmas algorítmicos da Torre de Hanói? Ou talvez os paradigmas sejam as estruturas de dados que eu usaria para projetar esses algoritmos?

Vaibhav Agarwal
fonte

Respostas:

9

Os paradigmas algorítmicos são :

Abordagens gerais para a construção de soluções eficientes para problemas

Qualquer abordagem básica e comumente usada no design de algoritmos pode ser considerada um paradigma algorítmico :

Dividir e conquistar

Idéia: divida a instância do problema em sub-instâncias menores do mesmo problema, resolva-as recursivamente e, em seguida, monte as soluções em uma solução da instância especificada.

Exemplos: Mergesort, Quicksort, algoritmo de Strassen, FFT.

Algoritmos Gananciosos

Idéia: encontre a solução sempre fazendo a escolha ideal no momento - não olhe para frente, nunca volte atrás.

Exemplos: algoritmo de Prim, algoritmo de Kruskal.

Programaçao dinamica

Idéia: Vire a recursão de cabeça para baixo.

Exemplo: algoritmo de Floyd-Warshall para o problema de caminho mais curto de todos os pares.

A palavra paradigma se traduz em exemplo, mas não é assim que é usada em um contexto científico . Seus exemplos são todos exemplos de algoritmos (exceto o problema do vendedor ambulante, que é um problema difícil de NP), nenhum dos quais é trivial o suficiente para ser considerado um paradigma algorítmico.

yannis
fonte
Eu nunca vi alguém definir DP de uma maneira tão simples. Obrigado.
MT.
2

Paradigmas algorítmicos de projeto comum:

  • Dividir e conquistar : dividir recursivamente um problema em dois ou mais subproblemas do mesmo tipo (ou relacionados).
  • Programação dinâmica : dividindo-a em uma coleção de subproblemas mais simples. Exemplo: quebra-cabeça da Torre de Hanói
  • Algoritmo ganancioso : a heurística para solucionar problemas de fazer a escolha ideal localmente em cada estágio. Exemplo: problema do vendedor ambulante
  • Backtracking : é um algoritmo geral para encontrar todas (ou algumas) soluções para alguns problemas computacionais. Exemplo: quebra-cabeça do Sudoku resolvido pelo backtracking.
  • Força Bruta : uma técnica muito geral de solução de problemas que consiste em enumerar sistematicamente todos os possíveis candidatos à solução e verificar se cada candidato satisfaz a afirmação do problema.

Você pode encontrar vários exemplos em geeksforgeeks

Premraj
fonte