Melhor resposta
Classificação por propósito
Cada algoritmo tem um objetivo, por exemplo, o objetivo do algoritmo de Classificação rápida é classificar os dados em ordem crescente ou decrescente. Mas o número de objetivos é infinito e temos que agrupá-los por tipo de objetivo.
Classificação por implementação
Um algoritmo pode ser implementado de acordo com diferentes princípios básicos.
- Recursivo ou iterativo Um algoritmo recursivo é aquele que chama a si mesmo repetidamente até que uma determinada condição corresponda. É um método comum à programação funcional. Algoritmos iterativos usam construções repetitivas como loops. Alguns problemas são mais adequados para uma implementação ou outra. Por exemplo, o problema das torres de hanoi é bem compreendido na implementação recursiva. Cada versão recursiva tem um equivalente iterativo iterativo e vice-versa.
- Lógico ou procedural Um algoritmo pode ser visto como dedução lógica controlada. Um componente lógico expressa os axiomas que podem ser usados no cálculo e um componente de controle determina a maneira pela qual a dedução é aplicada aos axiomas. Esta é a base da programação lógica. Em linguagens de programação de lógica pura, o componente de controle é fixo e os algoritmos são especificados fornecendo apenas o componente lógico.
- Serial ou paralelo Os algoritmos são geralmente discutidos com a suposição de que os computadores executam uma instrução de um algoritmo por vez. Este é um algoritmo serial, em oposição aos algoritmos paralelos, que aproveitam as arquiteturas de computador para processar várias instruções de uma vez. Eles dividem o problema em subproblemas e os passam para vários processadores. Os algoritmos iterativos são geralmente paralelizáveis. Os algoritmos de classificação podem ser paralelizados de forma eficiente.
- Determinístico ou não determinístico Os algoritmos determinísticos resolvem o problema com um processo predefinido, enquanto o algoritmo não determinístico deve realizar suposições da melhor solução em cada etapa por meio do uso de heurísticas.
Classificação por paradigma de design
Um paradigma de design é um domínio em pesquisa ou classe de problemas que requer um tipo dedicado de algoritmo:
- Dividir e conquistar Um algoritmo de dividir e conquistar reduz repetidamente uma instância de um problema a uma ou mais instâncias menores do mesmo problema (geralmente recursivamente), até que as instâncias sejam pequenas o suficiente para resolver facilmente. Um exemplo de divisão para conquistar é a classificação por mesclagem. A classificação pode ser feita em cada segmento de dados depois de dividir os dados em segmentos e a classificação de dados inteiros pode ser obtida na fase de conquista, mesclando-os. O algoritmo de pesquisa binária é um exemplo de uma variante de dividir e conquistar chamado algoritmo de diminuir e conquistar , que resolve um subproblema idêntico e usa a solução deste subproblema para resolver o problema maior.
- Programação dinâmica O caminho mais curto em um gráfico ponderado pode ser encontrado usando o caminho mais curto para o objetivo de todos os vértices. Quando a solução ótima para um problema pode ser construída a partir de soluções ótimas para subproblemas, o uso de programação dinâmica evita soluções de recomputação que já foram computadas. – A principal diferença com a abordagem “dividir e conquistar” é que os subproblemas são independentes em dividir e conquistar, enquanto a sobreposição de subproblemas ocorre na programação dinâmica. – Programação dinâmica e memoization andam juntas. A diferença com a recursão direta está no armazenamento em cache ou na memoização de chamadas recursivas. Onde os subproblemas são independentes, isso é inútil. Usando memoização ou mantendo uma tabela de subproblemas já resolvidos, a programação dinâmica reduz a natureza exponencial de muitos problemas à complexidade polinomial.
- O método guloso Um algoritmo guloso é semelhante a um algoritmo de programação dinâmica, mas a diferença é que as soluções para os subproblemas não precisam ser conhecidas em cada estágio. Em vez disso, uma escolha “gananciosa” pode ser feita sobre o que parece ser a melhor solução para o momento. O algoritmo ganancioso mais popular é encontrar a árvore geradora mínima fornecida por Kruskal.
- Programação linear O problema é expresso como um conjunto de desigualdades e, em seguida, é feita uma tentativa de maximizar ou minimizar as entradas. Isso pode resolver muitos problemas, como o fluxo máximo para gráficos direcionados, principalmente usando o algoritmo simplex.Uma variante complexa da programação linear é chamada de programação inteira, onde o espaço de solução é restrito a todos os números inteiros.
- Redução também chamada de transformar e conquistar Resolva um problema transformando-o em outro problema. Um exemplo simples: encontrar a mediana em uma lista não classificada é primeiro traduzir este problema em problema de classificação e encontrar o elemento do meio na lista classificada. O principal objetivo da redução é encontrar a transformação mais simples possível.
- Usando gráficos Muitos problemas, como jogar xadrez, podem ser modelados como problemas em gráficos. Algoritmos de exploração de gráfico são usados. Esta categoria também inclui os algoritmos de pesquisa e retrocesso.
- O paradigma probabilístico e heurístico Probabilístico Aqueles que fazem algumas escolhas aleatoriamente. Genética Tentativa de encontrar soluções para problemas imitando processos evolutivos biológicos, com um ciclo de mutações aleatórias produzindo gerações sucessivas de “soluções”. Assim, eles emulam a reprodução e a “sobrevivência do mais apto”. Heurística cujo objetivo geral não é encontrar uma solução ótima, mas uma solução aproximada onde o tempo ou os recursos para encontrar uma solução perfeita não são práticos.
Classificação por complexidade
Alguns algoritmos são concluídos em tempo linear e outros em tempo exponencial e alguns nunca são concluídos.
Fonte: Classificação dos algoritmos
Aprendizagem supervisionada: classificação
Resposta
A seguir está outra maneira de classificar algoritmos.
Na programação competitiva, existem 4 problemas principais- resolvendo paradigmas.
Em outras palavras, dado um problema, aqui estão as diferentes abordagens / ferramentas que você deve usar para resolvê-lo.
- Força bruta / pesquisa completa: um método que examina todas as possibilidades e seleciona a melhor solução.
- Prós: simples, deve sempre encontrar a solução, pois você está olhando para todas as possibilidades
- Contras : inviável como o o número de possibilidades cresce exponencialmente conforme o número de itens aumenta
- Dividir e conquistar: Método que divide o problema em partes menores e, em seguida, resolve essas partes. Pense na pesquisa binária.
- Abordagem gananciosa: método que escolhe a melhor opção no momento atual, sem nenhuma consideração para o futuro.
- Prós: rápido, simples, pode obter a melhor solução ou chegar perto
- Contras: na maioria das vezes, não obteremos a melhor solução
- Programação dinâmica: Método que leva a uma solução usando sub-soluções encontradas anteriormente. Definitivamente uma das técnicas mais avançadas, mas extremamente poderosa e aplicável.
- Prós: encontra a solução ideal para muitos problemas em tempo polinomial ( considerando que a força bruta seria exponencial)
- Contras : difícil de entender e aplicar, leva tempo para entender os vários estados e recorrência
Fontes
Halim, Steven e Felix Halim. Programação competitiva: o novo limite inferior dos concursos de programação . Lulu, 2013.