Algoritmo

Os fluxogramas são muitas vezes utilizados para representar graficamente algoritmos.

Em matemática , computação, lingüística e disciplinas afins, um algoritmo é um tipo de método eficaz no qual uma lista definitiva de instruções bem definidas para completar uma tarefa, quando dado um estado inicial, irá prosseguir através de uma série bem definida de estados sucessivos, acabou terminando em um estado final. A transição de um estado para o outro não é necessariamente determinista; alguns algoritmos conhecidos, como algoritmos probabilísticos, incorporar a aleatoriedade.

O conceito de um algoritmo originou-se como um meio de gravação procedimentos para a resolução de problemas matemáticos, tais como encontrar o comum divisor de dois números ou multiplicar dois números; tais algoritmos estavam em uso pelos babilônios tão cedo quanto 1600 aC.

A formalização parcial do conceito começou com tentativas de resolver o Entscheidungsproblem (o "problema de decisão") que David Hilbert posou em 1928. formalizações subsequentes foram enquadrados como tentativas de definir " calculabilidade efetiva "(Kleene 1943: 274) ou" método eficaz "(Rosser 1939: 225); essas formalizações incluiu a Gödel-Herbrand-Kleene funções recursivas de 1930, 1934 e 1935, Alonzo Church de lambda cálculo de 1936, De Emil Post "Formulação I" de 1936, e Alan Turing 's As máquinas de Turing de 1936-7 e 1939.

Etimologia

Al-Khwarizmi , persa astrônomo e matemático , escreveu um tratado em árabe em 825 dC, sobre o cálculo com numerais hindus. (Ver algorism). Foi traduzido para o latim no século 12 como Algoritmi de numero Indorum (al-Daffa 1977), cujo título foi provavelmente a intenção de significar "[Livro de] Algoritmus sobre os números dos índios", onde "Algoritmi" foi capitulação do tradutor do nome do autor no caso genitivo; mas as pessoas mal-entendido o título tratados Algoritmi como um plural Latina e isso levou à palavra "algoritmo" (Algorismus Latina) que vem a significar "método de cálculo". O "th" intruso é muito provavelmente devido a uma falso cognato com os gregos αριθμος (arithmos) que significa "número".

Por que são necessários algoritmos: uma definição informal

Sem definição formal geralmente aceite de "algoritmo" existe ainda. Podemos, no entanto, obter pistas sobre as questões envolvidas e um significado informal da palavra a partir da seguinte citação de Boolos & Jeffrey (1974, 1999) (negrito acrescentado):

Nenhum ser humano pode escrever rápido o suficiente, ou o tempo suficiente, ou pequeno o suficiente para listar todos os membros de um conjunto infinito enumerably escrevendo os seus nomes, um após o outro, em alguma notação. Mas os seres humanos podem fazer algo igualmente útil, no caso de certos conjuntos infinitos enumerably: Eles podem dar instruções explícitas para a determinação do enésimo membro do conjunto, para arbitrário finito n. Tais instruções devem ser dadas de forma bastante explícita, de uma forma em que eles poderiam ser seguido por uma máquina de computação, ou por um ser humano que é capaz de realizar apenas operações muito elementares sobre os símbolos (Boolos & Jeffrey 1974, 1999, p. 19 )

As palavras "enumerably infinito" significa "contável usando números inteiros, talvez, que se estendem ao infinito". Assim Boolos e Jeffrey estão dizendo que implica um algoritmo de instruções para um processo que "cria" inteiros a partir de uma "entrada" inteiro arbitrário ou números inteiros que, em teoria, podem ser escolhidos a partir de 0 até ao infinito de saída. Assim, poderíamos esperar um algoritmo para ser uma equação algébrica, como y = m + n - dois "variáveis de entrada" arbitrárias m e n que produzem uma saída y. Como podemos ver na Caracterizações algoritmo - o algoritmo palavra implica muito mais do que isso, algo na ordem de (para nosso exemplo disso):

Instruções precisas (em linguagem compreendida por "o computador") para uma "rápida e eficiente bom," processo que especifica os "movimentos" de "o computador" (máquina ou humano, equipado com as informações e capacidades necessárias internamente-suficiente) para encontrar, decodificar e depois arrebentar arbitrárias inteiros de entrada / símbolos m e n, símbolos + e = ... e (de forma confiável, corretamente, "efetivamente") produzem, em um "razoável" de tempo , saída de integer y num determinado local e num formato especificado.

O conceito de algoritmo também é usado para definir o conceito de decidibilidade (lógica). Essa noção é central para explicar como sistemas formais passam a existir a partir de um pequeno conjunto de axiomas e regras. Em lógica , o tempo que requer um algoritmo para completar não pode ser medida, uma vez que não está aparentemente relacionada com a dimensão física habitual. A partir de tais incertezas, que caracterizam os trabalhos em curso, decorre a indisponibilidade de uma definição de algoritmo que se adapta tanto concreto (em algum sentido) e uso abstrato do termo.

Para uma apresentação detalhada dos vários pontos de vista em torno da definição de "algoritmo" ver Caracterizações algoritmo. Para exemplos de algoritmos simples adição especificados na forma detalhada descrito em Caracterizações algoritmo, ver Exemplos algoritmo.

Formalização de algoritmos

Algoritmos são essenciais para a forma como os computadores processam informações, porque uma programa de computador é essencialmente um algoritmo que diz ao computador que medidas específicas a realizar (em que ordem específica), a fim de realizar uma tarefa específica, como o cálculo 'contracheques ou imprimir alunos dos trabalhadores cartões de relatório. Assim, um algoritmo pode ser considerado como sendo qualquer sequência de operações que podem ser executadas por um Turing-completa do sistema. Os autores que afirmam esta tese incluem Savage (1987) e Gurevich (2000):

... Argumento informal de Turing em favor de sua tese justifica uma tese mais forte: cada algoritmo pode ser simulado por uma máquina de Turing (Gurevich 2000: 1) ... de acordo com Savage [1987], um algoritmo é um processo computacional definido por uma máquina de Turing. (Gurevich 2000: 3)

Tipicamente, quando um algoritmo está associada com o processamento de informação, os dados são lidos a partir de uma fonte de entrada ou dispositivo, escrito para uma pia ou dispositivo de saída, e / ou armazenada para posterior processamento. Os dados armazenados são considerados como parte do estado interno da entidade que executa o algoritmo. Na prática, o estado é armazenado numa estrutura de dados, mas um algoritmo requer os dados internos apenas para os conjuntos de operação específicos chamados tipos de dados abstratos.

Para qualquer processo computacional, o algoritmo deve ser rigorosamente definido: especificado na forma como ele se aplica em todas as circunstâncias possíveis que possam surgir. Ou seja, todas as medidas condicionais devem ser sistematicamente tratados, caso a caso; os critérios para cada caso deve ser clara (e computável).

Porque um algoritmo é uma lista precisa de passos precisos, a fim de computação quase sempre será crítico para o funcionamento do algoritmo. As instruções são geralmente assumido coletados explicitamente, e são descritas como de partida "de cima" e ir "até o fundo", uma idéia que é descrita mais formalmente por fluxo de controle.

Até agora, esta discussão sobre a formalização de um algoritmo assumiu as instalações da programação imperativa. Esta é a concepção mais comum, e ele tenta descrever uma tarefa em discretos, meios "mecânicos". Exclusivo para esta concepção de algoritmos formalizados é o operação de atribuição, estabelecendo o valor de uma variável. Ela deriva da intuição de " memória "como um rascunho. Há um exemplo abaixo de tal atribuição.

Para algumas concepções alternativas sobre o que constitui um algoritmo see programação funcional e lógica de programação.

Terminação

Alguns escritores restringir a definição de algoritmo para procedimentos que, eventualmente, terminar. Em tal categoria Kleene coloca o "método de procedimento de decisão, decisão ou algoritmo para a questão" (Kleene 1952: 136). Outros, incluindo Kleene, incluir procedimentos que poderiam funcionar para sempre sem parar; tal procedimento tem sido chamado de "método computacional" (Knuth 1997: 5) ou "procedimento de cálculo ou algoritmo" (Kleene 1952: 137); no entanto, Kleene observa que tal método deve, eventualmente, apresentar "um objeto" (Kleene 1952: 137).

Minsky faz a observação pertinente, no que diz respeito a determinar se um algoritmo acabará por terminar (a partir de um estado inicial específico):

Mas, se a duração do processo não é conhecido antecipadamente, em seguida, 'tentando' pode não ser decisiva, porque se o processo não durar para sempre -, em seguida, em nenhum momento nós nunca vai ter a certeza da resposta (Minsky, 1967: 105) .

Como acontece, nenhum outro método pode fazer melhor, como foi mostrado por Alan Turing com seu resultado comemorado no indecidibilidade do chamado problema da parada. Não existe um procedimento algorítmico para a determinação de algoritmos arbitrários ou não encerrar a partir de determinados estados de partida. A análise de algoritmos para a sua probabilidade de extinção é chamado análise rescisão.

Veja os exemplos de (im -) subtração "adequada" no função parcial para saber mais sobre o que pode acontecer quando um algoritmo falhar por alguns dos seus números de entrada - por exemplo, (i) não-terminação, (ii) produção de "lixo" (saída no formato errado para ser considerado um número) ou nenhuma número (s) de todo (halt encerra a computação sem saída), (iii) número errado (s), ou (iv) uma combinação destes. Kleene proposto que a produção de "lixo" ou a incapacidade de produzir um número é resolvido fazendo com que o algoritmo de detectar esses casos e produzir, por exemplo, uma mensagem de erro (ele sugeriu "0"), ou de um modo preferido, o algoritmo de forçar a entrar num ciclo infinito ( Kleene 1952: 322). Davis faz isso para seu algoritmo de subtração - ele corrige seu algoritmo em um segundo exemplo de modo que é a subtração correta (Davis 1958: 12-15). Juntamente com os resultados lógicos "verdadeiro" e "falso" Kleene também propõe o uso de um terceiro símbolo lógico "u" - indecisos (Kleene 1952: 326) -, assim, um algoritmo irá sempre produzir algo quando confrontados com uma "proposição". O problema de respostas erradas deve ser resolvido com uma "prova" independente do algoritmo por exemplo, usando indução:

Nós normalmente exigem provas auxiliar para isso (que o algoritmo define corretamente um mu função recursiva), por exemplo, sob a forma de uma prova indutiva que, para cada valor de argumento, a computação termina com um valor único (Minsky 1967: 186).

Expressando algoritmos

Os algoritmos podem ser expressos em diversos tipos de notação, incluindo linguagens naturais, pseudocódigo, fluxogramas, e linguagens de programação . Expressões de linguagem natural de algoritmos tendem a ser detalhado e ambígua, e raramente são utilizados para algoritmos complexos ou técnicos. Pseudocódigo e fluxogramas são formas estruturadas para expressar algoritmos que evitam muitas das ambiguidades comuns em declarações linguagem natural, mantendo-se independente de uma linguagem de implementação particular. As linguagens de programação são destinados principalmente para expressar algoritmos em uma forma que pode ser executado por um computador , mas são muitas vezes utilizados como uma maneira de definir ou algoritmos de documentos.

Existe uma grande variedade de representações possíveis e pode-se expressar um dado Turing programa da máquina como uma seqüência de tabelas de máquina (veja mais em máquina de estados finitos e tabela de transição de estado), como fluxogramas (veja mais em diagrama de estado), ou como uma forma de rudimentar código de máquina ou código de montagem chamado de "conjuntos de quádruplos" (veja mais em Máquina de Turing).

Às vezes é útil na descrição de um algoritmo para complementar pequenos "fluxogramas" (diagramas de estado) com linguagem natural e / ou expressões aritméticas escritas dentro " diagramas de blocos "para resumir o que os" diagramas de fluxo "estão realizando.

Representações de algoritmos são geralmente classificados em três níveis aceitos de Turing descrição máquina (Sipser 2006: 157):

• 1 descrição de alto nível:

"... Prosa para descrever um algoritmo, ignorando os detalhes de implementação. A este nível não precisamos de mencionar como a máquina controla sua fita ou a cabeça"

• Descrição 2 Implementação:

"... Prosa usado para definir a forma como a máquina de Turing usa sua cabeça e da maneira que ele armazena dados em sua fita. A este nível não damos detalhes de estados ou função de transição"

• 3 Formal descrição:

Mais detalhado, "nível mais baixo", dá a "tabela de estado" da máquina de Turing.

Implementação

A maior parte dos algoritmos destinam-se a ser implementada como programas de computador. No entanto, os algoritmos são também implementado por outros meios, tais como numa biológica rede neural (por exemplo, a cérebro humano implementar aritmética ou um inseto que procura o alimento), em um circuito eléctrico, ou num dispositivo mecânico.

Exemplo

Um dos algoritmos mais simples é encontrar o maior número em uma lista (indiferenciados) de números. A solução exige necessariamente olhando para cada número na lista, mas apenas uma vez em cada um. A partir deste segue um algoritmo simples, que pode ser indicado em uma descrição de alto nível Inglês prosa, como:

Descrição de alto nível:

1. Suponha que o primeiro item é maior.
2. Olhe para cada um dos itens restantes na lista e se ele é maior do que o maior item, até agora, fazer uma nota do mesmo.
3. O último item observado é o maior na lista quando o processo estiver concluído.

(Quasi-) descrição formal: Escrito em prosa, mas muito mais próximo da linguagem de alto nível de um programa de computador, o seguinte é a codificação mais formal do algoritmo em pseudocódigo ou pidgin código:

 Algoritmo LargestNumber
   Entrada: Uma lista não-vazio de números L.
   Saída: O maior número na lista L.

   O maior ← L 0
   para cada item na lista L ≥1, fazer
     se o item> O maior, em seguida,
       O maior ← o item
   retornar maior

Para um exemplo mais complexo de um algoritmo, ver O algoritmo de Euclides para o maior divisor comum , um dos primeiros algoritmos conhecidos.

Análise de algoritmos

Quando isso acontece, é importante saber quanto de um recurso específico (tais como o tempo de armazenamento ou a) é necessário para um determinado algoritmo. Foram desenvolvidos métodos para o análise de algoritmos para obter tais respostas quantitativas; por exemplo, o algoritmo acima tem um requisito de tempo de O (n), usando o notação S com n grande como o comprimento da lista. Em todas as vezes que o algoritmo só precisa se lembrar de dois valores: o maior número encontrado até agora, e de sua posição atual na lista de entrada. Portanto diz-se que tem um requisito de espaço de O (1), se o espaço necessário para armazenar os números de entrada não é contado, ou O (log n) se for contado.

Diferentes algoritmos podem completar a mesma tarefa com um conjunto diferente de instruções em menos ou mais tempo, espaço, ou esforço do que outros. Por exemplo, dado duas receitas diferentes para fazer salada de batata, pode-se ter descascar a batata antes de ferver a batata enquanto o outro apresenta as etapas na ordem inversa, ainda que ambos chamada para estes passos para ser repetido para todas as batatas e final, quando o salada de batata está pronto para ser comido.

O análise e estudo de algoritmos é uma disciplina de ciência da computação , e é muitas vezes praticado de forma abstrata, sem a utilização de uma específica linguagem de programação ou implementação. Neste sentido, a análise algoritmo assemelha outras disciplinas matemáticas em que ela incide sobre as propriedades subjacentes do algoritmo e não sobre as especificidades de qualquer implementação particular. Normalmente pseudocódigo é usado para análise, uma vez que é a representação mais simples e geral.

Classes

Existem várias maneiras de classificar algoritmos, cada um com seus próprios méritos.

Classificação por aplicação

Uma maneira de classificar os algoritmos é por meio de implementação.

• Recursão ou iteração: A algoritmo recursivo é aquele que invoca (faz referência a) próprio repetidamente até uma determinada condição partidas, o que é um método comum para programação funcional. Algoritmos iterativos usar construções repetitivas como loops e estruturas de dados adicionais, como, por vezes, pilhas para resolver os problemas indicados. Alguns problemas são naturalmente adequados para uma aplicação ou outro. Por exemplo, Torres de Hanói é bem compreendido na implementação recursiva. Cada versão recursiva tem um equivalente (mas possivelmente mais ou menos complexo) versão iterativa, e vice-versa.

• Lógico: Um algoritmo pode ser visto como controlada dedução lógica. Este conceito pode ser expresso como: Algoritmo + = lógica de controlo (Kowalski 1979). A componente lógica expressa o axioma que podem ser utilizados no cálculo e o componente de controlo determina a maneira pela qual é aplicada a dedução dos axiomas. Esta é a base para o paradigma de programação lógica. Em linguagens de programação lógica pura do componente de controle é fixo e algoritmos são especificados, fornecendo somente o componente de lógica. O apelo dessa abordagem é o elegante semântica: uma mudança nos axiomas tem uma mudança bem definida no algoritmo.

• De série ou paralela ou distribuída: algoritmos são geralmente discutido com a suposição de que os computadores executar uma instrução de um algoritmo de cada vez. Esses computadores são chamados às vezes os computadores de série. Um algoritmo concebido para tal ambiente é chamado um algoritmo de série, ao invés de algoritmos paralelos ou algoritmos distribuídos. Algoritmos paralelos tirar proveito de arquiteturas de computadores onde vários processadores podem trabalhar em um problema, ao mesmo tempo, enquanto algoritmos distribuídos utilizar várias máquinas conectadas com um rede. Algoritmos paralelos ou distribuídos dividir o problema em subproblemas mais simétricos ou assimétricos e recolher os resultados de volta juntos. O consumo de recursos em tais algoritmos não é apenas ciclos do processador em cada processador, mas também a sobrecarga de comunicação entre os processadores. Algoritmos de ordenação pode ser paralelizado de forma eficiente, mas o seu overhead de comunicação é caro. Algoritmos iterativos são geralmente paralelizável. Alguns problemas não têm algoritmos paralelos, e são chamados de problemas inerentemente seriais.

• Determinista ou não-determinístico: Algoritmos determinísticos resolver o problema com a decisão exata a cada passo do algoritmo enquanto algoritmo não-determinístico resolver problemas através supondo suposições, embora típicos são feitos mais preciso através da utilização de heurísticas.

• Exata ou aproximada: Embora muitos algoritmos alcançar uma solução exata, algoritmos de aproximação procuram uma aproximação que está perto da verdadeira solução. A aproximação pode usar tanto um determinante ou uma estratégia aleatória. Esses algoritmos têm valor prático para muitos problemas difíceis.

Classificação por paradigma de design

Outra forma de classificar os algoritmos é por sua metodologia de projeto ou paradigma. Há um certo número de paradigmas, diferentes uns dos outros. Além disso, cada uma destas categorias incluem muitos tipos diferentes de algoritmos. Alguns paradigmas comumente encontrados incluem:

• Dividir e conquistar. A dividir para conquistar algoritmo reduz repetidamente um exemplo de um problema com uma ou mais ocorrências menores do mesmo problema (geralmente recursivamente), até que os exemplos são suficientemente pequenas para resolver facilmente. Um exemplo de dividir e conquistar é mesclar classificação. A selecção pode ser feita em cada segmento de dados depois de dividir os dados em segmentos e triagem de dados inteiras podem ser obtidas em fase conquista através da sua fusão. Uma variante mais simples de dividir e conquistar é chamado diminuição e conquistar algoritmo, que resolve um subproblema idêntica e usa a solução deste subproblema para resolver o problema maior. Dividir e conquistar divide o problema em vários subproblemas e assim conquistar fase será mais complexo do que diminuição e conquistar algoritmos. Um exemplo de algoritmo de redução e conquista é algoritmo de busca binária.
• A programação dinâmica. Quando um problema mostra subestrutura óptimo, ou seja, a solução ideal para um problema pode ser construído a partir de soluções óptimas para subproblems, e subproblems sobrepostas, ou seja, os mesmos subproblems são usados para resolver muitos casos de problemas diferentes, uma abordagem mais rápida chamada programação dinâmica evita soluções recomputing que já tenham sido computados. Por exemplo, o caminho mais curto para um gol de um vértice em um ponderado gráfico pode ser encontrado usando o caminho mais curto para o objectivo de todos os vértices adjacentes. A programação dinâmica e memoização caminham juntos. A principal diferença entre a programação dinâmica e dividir e conquistar é que subproblemas são mais ou menos independente em dividir e conquistar, enquanto subproblemas se sobrepõem na programação dinâmica. A diferença entre a programação dinâmica e recursão direta está em cache ou memoization de chamadas recursivas. Quando subproblemas são independentes e não há repetição, memoization não ajuda; portanto, a programação dinâmica não é uma solução para todos os problemas complexos. Ao utilizar memoização ou a manutenção de um mesa de subproblemas já resolvido, programação dinâmica reduz a natureza exponencial de muitos problemas a complexidade polinomial.
• O método guloso. A algoritmo ganancioso é similar a um algoritmo de programação dinâmica, mas a diferença é que as soluções para os subproblems não tem que ser conhecida em cada fase; em vez de uma escolha "ganancioso" podem ser feitas de o que parece melhor para o momento. O método guloso estende a solução com a melhor decisão possível (nem todas as decisões viáveis) numa fase algorítmica com base na atual ótimo local ea melhor decisão (nem todas as decisões possíveis) feito em fase anterior. Ele não é exaustiva, e não dá resposta precisa a muitos problemas. Mas quando funciona, ele vai ser o método mais rápido. O algoritmo guloso mais popular é encontrar a árvore geradora mínima como dado por Kruskal.
• A programação linear. Ao resolver um problema usando programação linear, específico desigualdades envolvendo as entradas encontram-se e, em seguida, é feita uma tentativa para maximizar (ou minimizar) alguma função linear das entradas. Muitos problemas (tais como o fluxo máximo para dirigida gráficos) pode-se afirmar de uma forma de programação linear, e, em seguida, ser resolvidos através de um algoritmo de "genérico", como o algoritmo simplex. Uma variante mais complexa de programação linear é chamado programação inteira, onde o espaço de solução é restrito aos números inteiros .
• Redução. Esta técnica envolve a solução de um problema difícil, transformando-o em um problema mais conhecido para o qual temos (espero) algoritmos assintoticamente óptimos. O objetivo é encontrar um algoritmo de redução cujas complexidade não é dominada pelos resultantes da redução algoritmo. Por exemplo, uma algoritmo de seleção para encontrar a mediana de uma lista não ordenada envolve primeira triagem da lista (a parte caro) e, em seguida, puxando para fora o elemento do meio na lista ordenada (a porção barato). Essa técnica também é conhecida como transformar e conquistar.
• Pesquise e enumeração. Muitos problemas (tais como jogar xadrez ) podem ser modelados como problemas no gráficos. A algoritmo de exploração gráfico especifica regras para mover-se em torno de um gráfico e é útil para tais problemas. Esta categoria inclui também algoritmos de busca, ramo e enumeração ligado e retrocesso.
• O paradigma probabilística e heurística. Algoritmos que pertencem a esta classe enquadra na definição de um algoritmo mais frouxamente.

1. Algoritmos probabilísticos são aqueles que fazer algumas escolhas de forma aleatória (ou pseudo-aleatoriamente); para alguns problemas, que pode ser, de facto, provado que as soluções mais rápidas deve envolver algum aleatoriedade.
2. Algoritmos genéticos tentar encontrar soluções para os problemas imitando biológicos evolutivas processos, com um ciclo de mutações aleatórias produzindo sucessivas gerações de "soluções". Assim, eles emular reprodução e "sobrevivência do mais apto". Em programação genética, esta abordagem é estendido para algoritmos, por sobre o próprio algoritmo como uma "solução" a um problema.
3. Algoritmos heurísticos, cujo objetivo geral não é encontrar uma solução óptima, mas uma solução aproximada em que o tempo ou os recursos são limitados. Eles não são práticos para encontrar soluções perfeitas. Um exemplo disto seria busca local, busca tabu, ou algoritmos de recozimento simulado, uma classe de algoritmos probabilísticos heurísticos que variam a solução de um problema por um valor aleatório. O nome " recozimento simulado "faz alusão ao termo metalúrgico ou seja, o aquecimento e arrefecimento de metal para conseguir a liberdade de defeitos. O objetivo da variação aleatória é encontrar perto de globalmente as melhores soluções, em vez de simplesmente aqueles localmente ótimas, a idéia é que o elemento aleatório vontade ser diminuída como o algoritmo estabelece-se a uma solução.

Classificação por área de estudo

Cada campo da ciência tem seus próprios problemas e precisa de algoritmos eficientes. Problemas relacionados em um campo são frequentemente estudadas em conjunto. Algumas classes de exemplo são algoritmos de busca, algoritmos de ordenação, mesclar algoritmos, algoritmos numéricos, algoritmos de grafos, algoritmos de cordas, algoritmos computacionais geométricas, algoritmos combinatórios , aprendizado de máquina, criptografia , algoritmos de compressão de dados e técnicas de análise.

Campos tendem a sobrepor-se uns com os outros, e um algoritmo avanços na área pode melhorar as do outro, por vezes, completamente independentes, campos. Por exemplo, a programação dinâmica foi originalmente inventado para a otimização do consumo de recursos na indústria, mas agora é usado na resolução de uma ampla gama de problemas em muitos campos.

Classificação por complexidade

Os algoritmos podem ser classificados pela quantidade de tempo necessário para completar a sua comparação com o tamanho da entrada. Existe uma grande variedade: alguns algoritmos completas em tempo linear em relação ao tamanho da entrada, alguns fazem isso de uma quantidade exponencial de tempo, ou mesmo pior, e alguns nunca parar. Além disso, alguns problemas podem ter vários algoritmos de diferentes complexidade, enquanto outros problemas podem não ter algoritmos ou não há algoritmos eficientes conhecidos. Existem também alguns problemas de mapeamentos a outros problemas. Devido a isto, verificou-se ser mais apropriado para classificar os próprios problemas, em vez de os algoritmos em classes de equivalência com base na complexidade dos melhores algoritmos possível para eles.

Classificação por poder de computação

Outra forma de classificar os algoritmos é pelo poder de computação. Isso normalmente é feito considerando-se alguma coleção (classe) de algoritmos. Uma classe de algoritmos recursivo é aquele que inclui algoritmos para todas as funções computáveis de Turing. Olhando para as classes de algoritmos permite a possibilidade de restringir os recursos computacionais disponíveis (tempo e memória) usados em um cálculo. Uma classe de algoritmos subrecursive é aquele em que nem todas as funções calculáveis Turing pode ser obtido. Por exemplo, os algoritmos que funcionam tempo polinomial suficiente para muitos tipos importantes de computação, mas não esgotam todas as funções computáveis de Turing. Os algoritmos implementados pela classe funções recursivas primitivas é outra classe subrecursive.

Burgin (2005, 24 p.) Utiliza uma definição generalizada de algoritmos que relaxa o requisito comum que a saída do algoritmo que calcula uma função deve ser determinada após um número finito de passos. Ele define aa classe super-recursiva de algoritmos como "uma classe de algoritmos no qual é possível calcular funções não calculável por qualquer máquina de Turing" (Burgin 2005, p. 107). Isto está intimamente relacionado com o estudo de modos de hypercomputation.

Questões legais

Algoritmos, por si só, geralmente não são patenteáveis. No Estados Unidos , uma reivindicação constituído exclusivamente por manipulações simples de conceitos abstratos, números ou sinais não constituem "processos" (USPTO 2006) e, portanto, os algoritmos não são patenteáveis (como em Gottschalk v. Benson). No entanto, as aplicações práticas de algoritmos são, por vezes, patenteável. Por exemplo, em Diamante v. Diehr, a aplicação de uma simples algoritmo de retorno para ajudar na cura de borracha sintética foi considerado patenteável. O patenteamento de software é altamente controversa, e existem patentes altamente criticados envolvendo algoritmos, especialmente algoritmos de compressão de dados, tais como Unisys ' LZW patente.

Além disso, alguns algoritmos criptográficos têm restrições à exportação (ver exportação de criptografia).

História: Desenvolvimento da noção de "algoritmo"

Origem da palavra

O algoritmo palavra vem do nome do 9o século Matemático persa Abu Abdullah Muhammad ibn Musa al-Khwarizmi cujas obras introduzidas numerais indianos e conceitos algébricos. Ele trabalhou em Bagdá no momento em que ele era o centro de estudos científicos e comércio. A palavra algorism originalmente se referia apenas às regras de execução de aritmética usando Algarismos arábicos, mas evoluiu via tradução latina Europeia do nome de al-Khwarizmi em algoritmo do século 18. A palavra evoluiu para incluir todos os procedimentos definidos para resolver problemas ou executar tarefas.

Símbolos discretos e distinguíveis

Tally-marcas: Para manter o controle de seus rebanhos, os seus sacos de grãos e seu dinheiro os antigos usavam computação: acumulação de pedras ou marcas raspadas em varas, ou fazer símbolos discretos em argila. Através do uso babilônico e egípcio das marcas e símbolos, eventualmente, numerais romanos eo ábaco evoluiu (Dilson, p.16-41). Marcas de registro, bem visível em aritmética sistema de numeração utilizado na unária Máquina de Turing e Post-Turing máquina cálculos.

Manipulação de símbolos como "lugar" para os detentores números: álgebra

O trabalho dos antigos geômetras gregos, matemático persa Al-Khwarizmi (muitas vezes considerado como o "pai da álgebra "), e os matemáticos da Europa Ocidental culminou com Leibniz noção de 's ratiocinator cálculo (ca 1680):

"Um bom século e meio à frente do seu tempo, Leibniz propôs uma álgebra da lógica, uma álgebra que especificar as regras para a manipulação de conceitos lógicos da maneira que álgebra comum especifica as regras para a manipulação de números" (Davis 2000: 1)

Invenções mecânicas com estados discretos

O relógio: Bolter credita a invenção do peso-driven relógio como "A invenção tecla [da Europa na Idade Média]", em particular a beira escapamento <(Bolter, 1984: 24) que nos proporciona o carrapato e tock de um relógio mecânico. "A máquina automática precisas" (Bolter, 1984: 26) levou imediatamente a "mecânica autômatos "a partir do século XIII e, finalmente, para" máquinas computacionais "- o motor de diferença e motores de análise de Charles Babbage e condessa Ada Lovelace (p.33-34 Bolter, p.204-206).

Tear Jacquard, Hollerith de cartões perfurados, telegrafia e telefonia - o relé eletromecânico: Bell e Newell (1971) indicam que a Tear Jacquard (1801), precursor Hollerith cartões (cartões perfurados, 1887), e "tecnologias de comutação telefónicas" foram as raízes de uma árvore que conduz ao desenvolvimento dos primeiros computadores (Bell e Newell diagrama p. 39, cf Davis, 2000). Em meados de 1800 o telégrafo, o precursor do telefone, estava em uso em todo o mundo, sua codificação discreto e distinguível de letras como "pontos e traços" um som comum. Ao final de 1800 o ticker tape (1870 ca) estava em uso, como foi o uso de Cartões de Hollerith no censo de 1890 dos EUA. Então veio a Teletipo (ca 1910) com o seu uso em papel perfurado de Código Baudot em fita.

Telefone-redes de comutação de eletromecânica relés (inventado 1835) estava por trás do trabalho de George Stibitz (1937), o inventor do dispositivo adicionando digital. Enquanto ele trabalhava em Bell Laboratories, ele observou a "utilização" onerosa de calculadoras mecânicas com engrenagens. "Ele foi para casa uma noite em 1937 com a intenção de testar a sua ideia .... Quando a mexer acabou, Stibitz tinha construído um dispositivo de adição binária". (Valley News, p. 13).

Davis (2000) observa a importância particular do relé eletromecânico (com seus dois "estados binários"abertosefechados):

Foi somente com o desenvolvimento, começando na década de 1930, de calculadoras eletromecânicos usando relés elétricos, que as máquinas foram construídas tendo o âmbito Babbage tinha imaginado. "(Davis, p. 14).

Matemática durante os anos 1800 até meados de 1900

Símbolos e regras : Em rápida sucessão, a matemática de George Boole (1847, 1854), Gottlob Frege (1879), e Giuseppe Peano (1888-1889) reduziu aritmética a uma sequência de símbolos manipulados por regras. De Peano Os princípios da aritmética, apresentados por um novo método (1888) foi "a primeira tentativa de uma axiomatização da matemática em uma linguagem simbólica" (van Heijenoort: 81ff).

Mas Heijenoort dá Frege (1879) esta elogios: Frege é "talvez a obra mais importante já escrita na lógica ... em que vemos um." "Linguagem de fórmula ', que é umcharacterica língua, uma língua escrita com símbolos especiais , "para o pensamento puro", ou seja, livre de enfeites retóricos ... construída a partir de símbolos específicos que são manipulados de acordo com as regras definidas "(van Heijenoort: 1). O trabalho de Frege foi ainda mais simplificada e amplificada porAlfred North Whitehead eBertrand Russell, em seuPrincipia Mathematica (1910-1913).

Os paradoxos : Ao mesmo tempo um número de paradoxos perturbadoras apareceu na literatura, em especial o paradoxo Burali-Forti (1897), o paradoxo de Russell (1902-1903), e o Richard Paradox (Dixon 1906, cf Kleene 1952: 36 -40). As considerações resultantes levaram ao papel de Kurt Gödel (1931) - ele cita especificamente o paradoxo do mentiroso - que reduz completamente regras de recursão para números.

Calculabilidade efetiva : Em um esforço para resolver o Entscheidungsproblem definido precisamente por Hilbert em 1928, os matemáticos primeiro começou a definir o que se entende por um "método eficaz" ou "cálculo eficaz" ou "calculabilidade efetiva" (isto é, um cálculo que teria sucesso ). Em rápida sucessão, a seguinte apareceu: Alonzo Church, Stephen Kleene e de JB Rosser λ-cálculo, (nota cf em Alonzo Church 1936a: 90, 1936b: 110) uma definição finamente afiada de "recursão geral" a partir do trabalho de Gödel agindo em sugestões de Jacques Herbrand (Princeton palestras cf de Gödel de 1934) e simplificações subsequentes por Kleene (1935-6: 1943: 237ff, 255ff). Prova da Igreja (1936: 88ff) que o Entscheidungsproblem era insolúvel, definição de Emil Post dos calculabilidade efetiva como um trabalhador sem pensar seguir uma lista de instruções para mover para a esquerda ou para a direita através de uma sequência de quartos e, embora existam ou marca ou apagar um papel ou observar o papel e fazer um sim-não decisão sobre a próxima instrução (cf "Formulação I", Pós 1936: 289-290). Alan Turing prova de 's que o Entscheidungsproblem era insolúvel por uso de sua "a- [Automatic] máquina "(Turing 1936-7: 116ff) - com efeito quase idêntico ao do Post" formulação ", J. Definição de Barkley Rosser de "método eficaz" em termos de "uma máquina" (Rosser 1939: 226). A proposta da SC Kleene de um precursor da " tese de Church ", que ele chamou de" Tese I "(Kleene 1943: 273-274), e alguns anos mais tarde Kleene de renomear sua tese "Tese de Church" (Kleene 1952: 300, 317) e propor "Tese de Turing" (Kleene 1952: 376).

Emil Post (1936) e Alan Turing (1936-7, 1939)

Aqui está uma notável coincidência de dois homens não conhecendo um ao outro, mas descrevendo um processo de homens-como-computadores que trabalham em cálculos - e eles produzem definições praticamente idênticos.

Emil Post (1936) descreveu as ações de um "computador" (ser humano) como segue:

"... Dois conceitos estão envolvidos: a de umespaço símboloem que o trabalho que conduz do problema para responder é para ser levada a cabo, e uma inalterável fixaconjunto de instruções.

Seu espaço símbolo seria

"Uma sequência infinita de duas vias de espaços ou caixas ... O solucionador de problemas ou trabalhador é mover-se e trabalhar neste espaço símbolo, sendo capaz de estar em, e operando em apenas uma caixa de cada vez .... uma caixa é para admitir, mas duas condições possíveis, ou seja, sendo vazia ou sem marcação, e com uma única marca em que, digamos, um traço vertical.

"Uma caixa é para ser escolhido e chamado o ponto de partida. ... Um problema específico deve ser dada de forma simbólica por um número finito de caixas [ie, INPUT] sendo marcados com um acidente vascular cerebral. Da mesma forma, a resposta [isto é, OUTPUT], deve ser dada de forma simbólica por um tal configuração de caixas marcadas ....

"Um conjunto de instruções aplicáveis ​​a um problema geral define-se um processo determinista, quando aplicado a cada problema específico. Este processo irá terminar apenas quando se trata de direcção do tipo (C) [ou seja, STOP]." (U p. 289-290) Veja mais na máquina de Turing Pós-

Alan Turing trabalho 's (1936, 1939: 160) precedeu o de Stibitz (1937); não se sabe se Stibitz sabia do trabalho de Turing. O biógrafo de Turing acredita que o uso de Turing de um modelo de máquina de escrever do tipo derivado de um interesse juvenil: "Alan tinha sonhado de inventar máquinas de escrever como um menino; Sra Turing teve uma máquina de escrever; e ele poderia muito bem ter começado por perguntar a si mesmo o que significava chamar uma máquina de escrever 'mecânica' "(Hodges, p. 96). Dada a prevalência de código Morse e telegrafia, máquinas de fita ticker, e Teletypes podemos conjecturar que todos eram influências .

Turing - seu modelo de computação é agora chamado uma máquina de Turing - começa, como fez Post, com uma análise de um computador humano que ele whittles baixo para um simples conjunto de movimentos básicos e "estados de espírito". Mas ele continua um passo além e cria uma máquina como um modelo de computação de números (Turing 1936-7: 116).

"Computing é normalmente feito por escrito determinados símbolos no papel. Podemos supor que este trabalho está dividido em quadrados como o livro de aritmética de uma criança .... Presumo então que o cálculo é realizado em papel unidimensional, ou seja, em uma fita dividida em quadrados. Também deve supor que o número de símbolos que podem ser impressos é finito ....

"O comportamento do computador a qualquer momento é determinado pelos símbolos que ele está observando, e seu" estado de espírito "naquele momento. Podemos supor que há um limite B para o número de símbolos ou quadrados qual o computador pode observar em um momento. Se ele deseja observar mais, ele deve usar observações sucessivas. Vamos também supor que o número de estados de espírito que precisa ser levado em conta é finito ...

"Vamos imaginar que as operações realizadas pelo computador para ser dividida em 'operações simples", que são tão elementar que não é fácil imaginá-los ainda mais dividida "(Turing 1936-7: 136).

Redução de Turing produz o seguinte:

"As operações simples deve, portanto, incluir:

"(A) Alterações do símbolo em uma das praças observados

"(B) As mudanças de uma das praças observados para outra casa dentro L quadrados de uma das praças anteriormente observados.

"Pode ser que algumas destas mudanças necessariamente invocar uma mudança de estado de espírito A única operação mais geral deve, portanto, ser considerado como sendo uma das seguintes opções.:

"(A) Uma possível mudança (a) de símbolo juntamente com uma possível mudança de estado de espírito.

"(B) Uma mudança possível (b) de quadrados observados, juntamente com uma possível mudança de estado de espírito"

"Podemos agora construir uma máquina para fazer o trabalho deste computador." (Turing 1936-7: 136)

Alguns anos mais tarde, Turing expandiu sua análise (tese, definição) com esta expressão contundente do mesmo:

"A função está a ser dito" Effectivey calculável "se os seus valores podem ser encontrados por algum processo puramente mecânico. Embora seja bastante fácil de obter uma compreensão intuitiva dessa idéia, é neverthessless desejável ter alguns, exprimível definição matemática mais definida ... [ele discute a história da definição muito bonito, tal como apresentado acima, com relação a Gödel, Herbrand, Kleene, Church, Turing e Post]... Podemos tomar essa afirmação literalmente, a compreensão por um processo puramente mecânico que podia ser efectuado por uma máquina. É possível dar uma descrição matemática, numa certa forma normal, as estruturas destas máquinas. O desenvolvimento destas ideias leva à definição do autor de uma função calculável, e uma identificação de computability † com calculabilidade efetiva....

"† Vamos usar a expressão" função computável "para significar uma função calculável por uma máquina, e nós vamos" efetivamente calculabile (Turing 1939: 160) "se referem à idéia intuitiva sem especial, a identificação com qualquer uma dessas definições."

Rosser JB (1939) e SC Kleene (1943)

J. Barkley Rossercorajosamente definiu um "método [matemático] efectiva» da seguinte forma (negrito acrescentado):

"" Método eficaz 'é usado aqui no sentido bastante especial de um método cada etapa que é precisamente determinadas e que é certo para produzir a resposta em um número finito de passos. Com este significado especial, três definições precisas diferentes foram dados até à data [sua nota de rodapé nº 5; ver a discussão imediatamente abaixo]. A mais simples delas para o estado (devido à Post e Turing) diz essencialmente que. um método eficaz de resolver determinados conjuntos de problemas existe se se pode construir uma máquina que será, em seguida, resolver qualquer problema do conjunto sem intervenção humana para além de inserir a questão e (mais tarde) a leitura da resposta . Todas as três definições são equivalentes, de modo que não importa qual deles é usado. Além disso, o fato de que todos os três são equivalentes é um argumento muito forte para a exatidão de qualquer um. " (Rosser 1939: 225-6)

Rosser de nota # 5 referências do trabalho de (1) Church e Kleene e sua definição de λ-definibilidade, em uso particular da Igreja de que em seu um problema insolúvel de Elementary Number Theory (1936); (2) Herbrand e Gödel e seu uso de recursão em uso particular de Gödel em seu papel famoso On Formally indecidíveis Proposições de Principia Mathematica e sistemas relacionados I (1931); e (3) Post (1936) e Turing (1936-7) em suas mecanismo de modelos de computação.

Stephen C. Kleene definido como seu agora famoso "Tese I" conhecida como "a tese de Church-Turing ". Mas ele fez isso no seguinte contexto (em negrito no original):

"12.teorias Algorithmic... Na criação de uma teoria algorítmica completa, o que fazemos é para descrever um procedimento, performable para cada conjunto de valores das variáveis ​​independentes, qual o procedimento termina, necessariamente e de tal forma que, o resultado que pudermos leia uma resposta definitiva, "sim" ou "não" à pergunta, "é o valor de predicado é verdade?" "(Kleene 1943: 273)

História depois de 1950

Uma série de esforços têm sido direcionados para aperfeiçoamento da definição de "algoritmo", ea atividade está em curso por causa de questões que envolvem, nomeadamente, fundamentos da matemática (especialmente a tese de Church-Turing) e filosofia da mente (especialmente argumentos em torno de inteligência artificial). Para mais, veja caracterizações algoritmo.