O conceito de um algoritmo foi formalizado em 1936 pela maquina de Turing de Alan Turing e pelo cálculo lambda de Alonzo Church, que formaram as primeiras fundações da Ciência da Computação.
As características de um algoritmo são:
Finitas – O algoritmo deve eventualmente resolver o problema;
Bem definidas –Os passos devem ser definidos de modo a serem entendidos;
Efetivas –deve sempre resolver o que tem para solucionar, antecipando falhas.
O conceito de algoritmo já existe há séculos e o uso desse conceito pode ser atribuído a matemáticos russos como, por exemplo, a Peneira de Eratóstenes e o algoritmo de Euclides. Um conceito que é bastante ilustrado de um algoritmo é uma receita culinária, embora existam muitos outros algoritmos mais complexos. Eles podem também fazer passos de iterações(que é um processo de repetir uma ou mais ações) ou necessitar de decisões como, comparações ou logicas até que a tarefa seja concluída, mas um algoritmo corretamente executada não irá resolver um problema se estiver implementado da forma incorreta ou se não for apropriado para aquele problema.
Não podemos dizer que um algoritmo representa necessariamente um programa de computador, e sim os passos necessários para a realização de uma tarefa, mas sua implementação pode ser feita através de um computador, pode outro tipo maquina (robô) ou mesmo por um ser humano. Diferente algoritmos podem realizar a mesma tarefa usando um conjunto diferenciado de instruções em mais tempo ou menos tempo, espaço ou esforço do que outros, a diferença pode ser reflexo da complexidade computacional aplicada, que depende de estruturas de dados adequadas ao algoritmo. Por exemplo, um algoritmo para se vestir pode especificar para você vestir primeiro o casaco e depois a camisa enquanto o outro algoritmo especifica para você vestir primeiro a camisa e depois o casaco, assim podemos observar que o primeiro algoritmo é mais complexo de executar que o segundo apesar de ambos levarem ao mesmo resultado.
Classificação por implementação:
Recursos ou iterativos – Um algoritmo recursivo possui característica de invocar a si mesmo repetidamente até que certa condição seja satisfeita e ele é terminado, que é um método comum em programação funcional. Algoritmos iterativos usam estruturas de repetição como laços, ou ainda estruturas de dados adicionais como pilhas, para resolver problemas. Cada algoritmo recursivo possui um algoritmo iterativo equivalente e vice-versa, mas o que pode ter mais ou menos complexidade em sua construção;
Lógico – Um algoritmo pode ser visto como uma dedução lógica controlada. O componente lógico expressa os axiomas usados na computação e o componente de controle determina a maneira como a dedução é aplicada aos axiomas. O conceito é uma base para a programação lógica;
Determinístico ou não-determinístico – Os algoritmos determinísticos resolvem o problema com uma decisão exata a cada passo enquanto os algoritmos não-determinísticos resolvem os problemas ao deduzir os melhores passos através de estimativas sob forma de heurísticas;
Exato ou aproximado – Enquanto alguns algoritmos encontram uma resposta exata, algoritmos de aproximação procuram uma resposta próxima à verdadeira solução, ou seja, através de estratégia determinística ou aleatória. Possuem aplicações práticas sobretudo para problemas muito complexos, do qual uma resposta correta é inviável devido à sua complexidade computacional;
Serial ou paralelo – Algoritmos são geralmente assumidos por serem executados instrução a instrução individualmente, como uma lista de execução, o que constitui um algoritmo serial. Tal conceito é base para a programação imperativa. Por outro lado, existem algoritmos executados paralelamente, que levam em conta as arquiteturas de computadores com mais de um processador para executar mais de uma instrução em simultâneo. Tais algoritmos dividem os problemas em subproblemas e o delegam a quantos processadores estiverem disponíveis, agrupando no final o resultado dos subproblemas em um resultado final ao algoritmo. Tal conceito é base para a programação paralela. De forma geral, algoritmos iterativos são paralelizáveis; por outro lado, existem algoritmos que não são paralelizáveis, chamados então problemas inerentemente seriais.
