Introdução aos Algoritmos
Um algoritmo é uma sequência de etapas que descrevem como um problema pode ser resolvido. Todo programa de computador que termina com um resultado é basicamente baseado em um algoritmo. Os algoritmos, no entanto, não se limitam apenas ao uso em programas de computador, eles também podem ser usados para resolver problemas matemáticos e em muitos assuntos da vida cotidiana. Com base em como eles funcionam, podemos dividir os algoritmos em vários tipos. Vamos dar uma olhada em alguns dos mais importantes.
Tipos de algoritmo
Existem muitos tipos de algoritmos, mas os tipos fundamentais de algoritmos são:
1) Algoritmo Recursivo
Este é um dos algoritmos mais interessantes, pois se autodenomina com um valor menor como entrada, que é obtida após a resolução das entradas atuais. Em palavras mais simples, é um algoritmo que se chama repetidamente até que o problema seja resolvido.
Problemas como a Torre de Hanói ou DFS de um gráfico podem ser facilmente resolvidos usando esses algoritmos.
Por exemplo, aqui está um código que encontra um fatorial usando um algoritmo de recursão:
Fato (y)
Se y é 0
retorno 1
return (y * Fato (y-1)) / * é aqui que a recursão acontece * /
2) Algoritmo de divisão e conquista
Essa é outra maneira eficaz de resolver muitos problemas. Nos algoritmos Divide and Conquer, divida o algoritmo em duas partes, a primeira parte divide o problema em questão em subproblemas menores do mesmo tipo. Na segunda parte, esses problemas menores são resolvidos e depois somados (combinados) para produzir a solução final do problema.
A classificação por mesclagem e a classificação rápida podem ser feitas com algoritmos de divisão e conquista. Aqui está o pseudocódigo do algoritmo de classificação de mesclagem para dar um exemplo:
MergeSorting (ar (), l, r)
Se r> l
- Encontre o ponto médio para dividir a matriz especificada em duas metades:
m médio = (l + r) / 2
- Classificação para o primeiro semestre:
Classificação da chamada (ar, l, m)
- Classificação para o segundo semestre:
Classificação da chamada (ar, m + 1, r)
- Mesclar as metades classificadas na etapa 2 e 3:
Mesclagem de chamadas (ar, l, m, r)
3) Algoritmo de Programação Dinâmica
Esses algoritmos funcionam lembrando os resultados da execução passada e usando-os para encontrar novos resultados. Em outras palavras, o algoritmo de programação dinâmica resolve problemas complexos, dividindo-o em vários subproblemas simples e, em seguida, resolve cada um deles uma vez e os armazena para uso futuro.
A sequência de Fibonacci é um bom exemplo para algoritmos de Programação Dinâmica; você pode vê-la trabalhando no pseudo-código:
Fibonacci (N) = 0 (para n = 0)
= 0 (para n = 1)
= Fibonacci (N-1) + Finacchi (N-2) (para n> 1)
4) Algoritmo ganancioso
Esses algoritmos são usados para resolver problemas de otimização. Nesse algoritmo, encontramos uma solução local ótima (sem nenhuma consideração por qualquer consequência no futuro) e esperamos encontrar a solução ideal no nível global.
O método não garante que conseguiremos encontrar uma solução ideal.
O algoritmo possui 5 componentes:
- O primeiro é um conjunto de candidatos a partir do qual tentamos encontrar uma solução.
- Uma função de seleção que ajuda a escolher o melhor candidato possível.
- Uma função de viabilidade que ajuda a decidir se o candidato pode ser usado para encontrar uma solução.
- Uma função objetivo que atribui valor a uma solução possível ou a uma solução parcial
- Função de solução que informa quando encontramos uma solução para o problema.
Huffman Coding e o algoritmo de Dijkstra são dois exemplos principais em que o algoritmo Greedy é usado.
Na codificação de Huffman, o algoritmo passa por uma mensagem e, dependendo da frequência dos caracteres nessa mensagem, para cada caractere, atribui uma codificação de comprimento variável. Para fazer a codificação Huffman, primeiro precisamos criar uma árvore Huffman a partir dos caracteres de entrada e, em seguida, percorrer a árvore para atribuir códigos aos caracteres.
5) Algoritmo de força bruta
Este é um dos algoritmos mais simples do conceito. Um algoritmo de força bruta itera cegamente todas as soluções possíveis para pesquisar uma ou mais de uma solução que possa resolver uma função. Pense na força bruta usando todas as combinações possíveis de números para abrir um cofre.
Aqui está um exemplo de pesquisa seqüencial feita usando força bruta:
Algoritmo S_Search (A (0..n), X)
A (n) ← X
i ← 0
Enquanto A (i) ≠ X faz
i ← i + 1
se eu <n retornar i
else return -1
6) Algoritmo de retrocesso
O retorno é uma técnica para encontrar uma solução para um problema em uma abordagem incremental. Ele resolve problemas recursivamente e tenta chegar a uma solução para um problema, resolvendo uma parte do problema de cada vez. Se uma das soluções falhar, nós a removemos e voltamos atrás para encontrar outra solução.
Em outras palavras, um algoritmo de retrocesso resolve um subproblema e, se não conseguir resolver o problema, desfaz a última etapa e inicia novamente para encontrar a solução para o problema.
O problema do N Queens é um bom exemplo para ver o algoritmo de Backtracking em ação. O Problema da Rainha N declara que há N peças de rainhas em um tabuleiro de xadrez e temos que organizá-las para que nenhuma rainha possa atacar qualquer outra rainha no tabuleiro depois de organizada.
Agora, vamos dar uma olhada no algoritmo SolveNQ e nas funções Check Valid para resolver o problema:
CheckValid (tabuleiro de xadrez, linha, coluna)
Começar
Se houver uma rainha à esquerda da coluna atual, retorne false
Se a rainha estiver na diagonal superior esquerda, retorne false
Se a rainha estiver na diagonal inferior esquerda, retorne false
Return true
Fim
SolveNQ (Quadro, Coluna)
Começar
Se todas as colunas estiverem cheias, retorne true
Para cada linha presente no tabuleiro de xadrez
Faz
Se, CheckValid (quadro, x, coluna),
Coloque a rainha na célula (x, coluna) no quadro
Se SolveNQ (quadro, coluna + 1) = Verdadeiro, retorne verdadeiro.
Senão, remova a rainha da célula (x, coluna) do tabuleiro
Feito
Retorna falso
Fim
Conclusão - Tipos de algoritmos
Os algoritmos estão por trás da maioria das coisas impressionantes que os computadores podem fazer e estão no centro da maioria das tarefas de computação. Ser melhor com os algoritmos não apenas o ajudará a ser um programador de sucesso, mas você também se tornará mais eficiente.
Artigos recomendados
Este foi um guia para tipos de algoritmos. Aqui discutimos os 6 principais tipos importantes de algoritmos com suas funções. Você também pode consultar nossos outros artigos sugeridos para saber mais -
- Introdução ao algoritmo
- Algoritmo em Programação
- Perguntas da entrevista de algoritmo
- Fatorial em Python | Técnicas
- Algoritmos de classificação rápida em Java
- Os 6 principais algoritmos de classificação em JavaScript