O algoritmo são as regras e técnicas de projeto e produção que estão envolvidas na definição e projeto de algoritmos , ou seja, o processo sistemático de resolução de um problema para descrever precisamente as etapas para resolver um problema algorítmico .
A palavra "algoritmo" vem do nome do matemático Al-Khwarizmi (latinizado para os Idade Média em Algoritmi ), que na IX th século escreveu o primeiro trabalho sistemático fornecimento de soluções para equações lineares e quadrática . O silencioso h, não justificado pela etimologia, vem de uma deformação em comparação com o grego ἀριθμός (arithmós). "Algoritmo" deu "algorítmico". O sinônimo "algoritmo", uma palavra antiga usada por exemplo por Wronski em 1811, ainda é usado algumas vezes.
Os primeiros algoritmos que foram encontrados descrições datam dos babilônios , o III º milênio aC. AD . Eles descrevem métodos de cálculo e soluções de equações usando exemplos.
Um algoritmo famoso é o encontrado no Livro 7 dos Elementos de Euclides , e denominado algoritmo de Euclides . Ele encontra o maior divisor comum, ou GCD , de dois números. Um ponto particularmente notável é que ele contém explicitamente uma iteração e que as proposições 1 e 2 demonstram sua correção .
Foi Arquimedes quem primeiro propôs um algoritmo para o cálculo de π .
O primeiro a ter algoritmos sistematizados é o matemático persa Al-Khwârizmî , ativo entre 813 e 833. Em sua obra Abrégé du computation by restoration and compare , ele estuda todas as equações quadráticas e dá sua resolução por algoritmos gerais. Ele usa métodos semelhantes aos dos babilônios , mas difere em suas explicações sistemáticas, onde os babilônios deram apenas exemplos.
O Andaluzia estudante averroes ( 1126 - 1198 ) evoca um método de raciocínio onde a tese é refinado passo a passo, de forma iterativa, até uma certa convergência e isto de acordo com o progresso de um algoritmo. Ao mesmo tempo, na XII th século , o monge Adelardo de Bath introduziu o termo latino para Algorismus , com o nome de Al Khwarizmi. Esta palavra fornece um algoritmo em francês em 1554 .
No XVII th século , alguma alusão podia vislumbrar o método algorítmica para René Descartes na abordagem geral proposta pela Discurso do Método ( 1637 ), especialmente quando, na sua segunda parte, o matemático francês propôs a "dividir cada dificuldade que eu examine, em tantas partes quanto possível, e conforme necessário para melhor resolvê-los. “ Sem evocar explicitamente a iteração ou dicotomia dos conceitos de loop , a abordagem de Descartes predispõe a lógica para acomodar o conceito de programa , palavra nasce em francês em 1677 .
Em 1843, a matemática e pioneira da informática Ada Lovelace , filha de Lord Byron e assistente de Charles Babbage, realizou a primeira implementação de um algoritmo em forma de programa (cálculo dos números de Bernoulli ).
O décimo problema de Hilbert, que faz parte da lista de 23 problemas apresentada por David Hilbert em 1900 em Paris, é claramente um problema algorítmico. Nesse caso, a resposta é que não há algoritmo respondendo ao problema apresentado.
O algorítmica XX th e XXI ª séculos por base matemática do formalismo, por exemplo o de máquinas de Turing , que permitem definir com precisão o que se entende por "passos" por "específica" e "inequívoco" e que fornecem um quadro científico para estudar a propriedades dos algoritmos. Porém, de acordo com o formalismo escolhido, obtém-se diferentes abordagens algorítmicas para resolver o mesmo problema. Por exemplo , algoritmos recursivos , algoritmos paralelos ou computação quântica dão origem a apresentações de algoritmos que são diferentes dos algoritmos iterativos.
Algorithmics desenvolveu principalmente na segunda metade do XX ° século, como suporte conceitual de programação de computadores no desenvolvimento de TI durante este período. Donald Knuth , autor do tratado The Art of Computer Programming, que descreve um grande número de algoritmos, ajudou, com outros, a lançar as bases matemáticas de sua análise.
O substantivo algorítmico designa todos os métodos usados para criar algoritmos. O termo também é usado como adjetivo.
Um algoritmo apresenta uma solução para um problema na forma de uma cadeia de operações a serem realizadas .
Os cientistas da computação freqüentemente usam o anglicismo de implementação para se referir à implementação do algoritmo em uma linguagem de programação . Essa implementação realiza a transcrição das operações constituintes do algoritmo e especifica a maneira como essas operações são chamadas. Essa escrita em linguagem de computador também é freqüentemente designada pelo termo “ codificação ”. Falamos de " código-fonte " para designar o texto, constituindo o programa, realizando o algoritmo. O código é mais ou menos detalhado dependendo do nível de abstração da linguagem utilizada, assim como uma receita culinária deve ser mais ou menos detalhada de acordo com a experiência do cozinheiro.
Muitas ferramentas formais ou teóricas foram desenvolvidas para descrever algoritmos, estudá-los, expressar suas qualidades e ser capaz de compará-los:
Os conceitos implementados em algoritmos, por exemplo de acordo com a abordagem de N. Wirth para as linguagens mais difundidas (Pascal, C, etc. ), são em número reduzido. Eles pertencem a duas classes:
Esta divisão é por vezes difícil de perceber para certas linguagens ( Lisp , Prolog …) mais baseada na noção de recursão onde certas estruturas de controle estão implícitas e, portanto, parecem desaparecer.
Essas três noções "correção", "completude" e "finalização" estão relacionadas e suponha que um algoritmo seja escrito para resolver um problema.
A terminação é a garantia de que o algoritmo termina em um tempo finito. As provas de término geralmente envolvem uma função de número inteiro positivo estritamente decrescente em cada "etapa" do algoritmo.
Dada a garantia de que um algoritmo terminará, a prova de correção deve fornecer a garantia de que, se o algoritmo terminar dando um resultado, então esse resultado é de fato uma solução para o problema proposto. As provas de correção geralmente envolvem uma especificação lógica que deve ser verificada por soluções para o problema. A prova de correção consiste, portanto, em mostrar que os resultados do algoritmo atendem a esta especificação.
A prova de completude garante que, para um dado espaço de problema, o algoritmo, se terminar, dará o conjunto de soluções do espaço de problema. As provas de integridade requerem a identificação do espaço do problema e do espaço da solução para então mostrar que o algoritmo de fato produz o segundo a partir do primeiro.
As principais noções matemáticas no cálculo do custo de um algoritmo preciso são as noções de dominação (denotado O (f (n)) , "o grande"), onde f é uma função matemática de n , variável que designa a quantidade de informação (em bits , número de registros, etc. ) usado no algoritmo. Em algoritmos, muitas vezes encontramos complexidades do tipo:
Avaliação | Tipo de complexidade |
---|---|
complexidade constante (independente do tamanho dos dados) | |
complexidade logarítmica | |
complexidade linear | |
complexidade quase linear | |
complexidade quadrática | |
complexidade cúbica | |
complexidade polinomial | |
complexidade quase polinomial | |
complexidade exponencial | |
complexidade do fator |
Sem entrar em detalhes matemáticos, calcular a eficiência de um algoritmo (sua complexidade algorítmica ) consiste em encontrar duas quantidades importantes. A primeira quantidade é a evolução do número de instruções básicas de acordo com a quantidade de dados a serem processados (por exemplo, para um algoritmo de classificação , este é o número de dados a serem classificados), que terá preferência no tempo de execução medido em segundos (porque o último depende da máquina na qual o algoritmo é executado). A segunda quantidade estimada é a quantidade de memória necessária para realizar os cálculos. Basear o cálculo da complexidade de um algoritmo no tempo ou na quantidade efetiva de memória que um determinado computador leva para executar o referido algoritmo não leva em consideração a estrutura interna do algoritmo, nem a peculiaridade do algoritmo. Computador: de acordo com sua carga de trabalho, a velocidade de seu processador, a velocidade de acesso aos dados, a execução do algoritmo (que pode envolver acaso) ou sua organização de memória, o tempo de execução e a quantidade de memória não serão os mesmos.
Freqüentemente, o desempenho é examinado "na pior das hipóteses", ou seja, em configurações como o tempo de execução ou o espaço de memória é maior. Há também outro aspecto da avaliação da eficiência de um algoritmo: desempenho “médio”. Isso supõe ter um modelo da distribuição estatística dos dados do algoritmo, enquanto a implementação das técnicas de análise implica métodos bastante refinados de combinatória e avaliação assintótica , utilizando em particular as séries geradoras e métodos avançados de análise complexa . Todos esses métodos são agrupados sob o nome de combinatória analítica .
Outras avaliações de complexidade que geralmente vão além dos valores propostos acima e que classificam problemas algorítmicos (ao invés de algoritmos) em classes de complexidade podem ser encontradas no artigo sobre a teoria da complexidade dos algoritmos .
Algumas indicações sobre a eficiência dos algoritmos e seus viesesFreqüentemente, a eficiência do algoritmo só é conhecida assintoticamente, ou seja, para grandes valores do parâmetro n . Quando este parâmetro é pequeno o suficiente, um algoritmo de maior complexidade assintótica pode, na prática, ser mais eficiente. Assim, para classificar uma matriz de 30 linhas (este é um pequeno parâmetro), é desnecessário usar um algoritmo avançado, como classificação rápida (um dos algoritmos de classificação assintoticamente mais eficientes em média): l O algoritmo de classificação mais fácil de escrever irá ser suficientemente eficiente.
Entre dois algoritmos de computador de complexidade idêntica, usaremos aquele com menos ocupação de memória. A análise da complexidade algorítmica também pode ser usada para avaliar a ocupação da memória de um algoritmo. Finalmente, a escolha de um algoritmo em vez de outro deve ser feita de acordo com os dados que se espera fornecer como entrada. Assim, a classificação rápida , quando escolhemos o primeiro elemento como um pivô, se comporta desastrosamente se a aplicarmos a uma lista de valores já ordenada. Portanto, não é judicioso usá-lo se for esperado que o programa receba como entradas listas que já estão quase classificadas, ou você terá que escolher o pivô aleatoriamente.
Outros parâmetros a serem considerados incluem:
O algorítmico desenvolveu algumas estratégias para resolver os problemas:
Para alguns problemas, os algoritmos são muito complexos para obter um resultado em um tempo razoável, mesmo que se possa usar um poder de computação fenomenal. Somos, portanto, levados a buscar a solução de forma não sistemática ( algoritmo de Las Vegas ) ou a nos contentar com uma solução o mais próxima possível de uma solução ótima, procedendo-se de testes sucessivos ( algoritmo de Monte-Carlo ). Uma vez que nem todas as combinações podem ser tentadas, algumas escolhas estratégicas devem ser feitas. Essas escolhas, geralmente muito dependentes do problema tratado, constituem o que se denomina heurística . O objetivo de uma heurística não é, portanto, tentar todas as combinações possíveis, mas encontrar uma solução em um tempo razoável e por outros meios, por exemplo, realizando sorteios aleatórios. A solução pode ser exata (Las Vegas) ou aproximada (Monte-Carlo). Os algoritmos de Atlantic City , por outro lado, provavelmente fornecem efetivamente uma resposta provavelmente correta (digamos, com uma chance em cem milhões de estar errado) à pergunta feita.
É assim que os programas de jogo de xadrez ou go (para citar apenas alguns) usam heurísticas que modelam a experiência do jogador com frequência. Alguns softwares antivírus também contam com heurísticas para reconhecer vírus de computador não listados em seu banco de dados, contando com semelhanças com vírus conhecidos, este é um exemplo de um algoritmo de Atlantic City. Da mesma forma, o problema SAT, que é o arquétipo do problema NP-completo e, portanto, muito difícil, é resolvido de maneira prática e eficiente pelo desenvolvimento de heurísticas .
Existem vários algoritmos clássicos, usados para resolver problemas ou, mais simplesmente, para ilustrar métodos de programação. Consulte os artigos a seguir para obter mais detalhes (consulte também a lista de algoritmos ):