algoritmo - Algorithm


Da Wikipédia, a enciclopédia livre

Fluxograma de um algoritmo ( algoritmo de Euclides ) para o cálculo do maior divisor comum (gcd) de dois números um e b em locais denominados A e B. O algoritmo procede de subtracções sucessivas em dois circuitos: se o teste B ≥ A produz "sim" (ou verdadeiro) (mais precisamente o número b de localização b é maior do que ou igual ao número um na localização a) em seguida, o algoritmo especifica b ← b - a (o que significa que o número b - um substitui o antigo b ). Da mesma forma, se um> B, então A ← A - B. O processo termina quando o conteúdo de (B) é de 0, obtendo-se o gcd em A. (Algoritmo derivado de Scott 2009: 13; os símbolos e estilo do desenho a partir de Tausworthe 1977) .

Em matemática e ciência da computação , um algoritmo ( / æ l ɡ ə r ɪ ð əm /  ( escute )Sobre este som ) é uma especificação inequívoca de como resolver uma classe de problemas. Algoritmos pode realizar o cálculo , processamento de dados e raciocínio automatizado tarefas.

Como um método eficaz , um algoritmo pode ser expresso dentro de uma quantidade finita de espaço e tempo e em uma linguagem formal bem definido para o cálculo de uma função . A partir de uma entrada inicial e estado inicial (talvez vazio ), as instruções de descrever um cálculo que, quando executado , prossegue através de um número finito de estados sucessivos bem definidas, produzindo eventualmente "saída" e terminando num estado de ponto final. A transição de um estado para o outro não é necessariamente determinista ; alguns algoritmos, conhecidos como algoritmos randomizados , incorporar entrada aleatória.

O conceito de algoritmo já existe há séculos. Matemáticos gregos usados algoritmos, por exemplo, a peneira de Eratóstenes para encontrar números primos e o algoritmo de Euclides para encontrar o máximo divisor comum de dois números.

A palavra algoritmo em si deriva do matemático do século 9 Al-Khwarizmi , latinizado Algoritmi . A formalização parcial do que se tornaria o conceito moderno de algoritmo começou com tentativas de resolver o Entscheidungsproblem (problema de decisão) colocada por David Hilbert em 1928. formalizações posteriores foram enquadrados como tentativas de definir " calculabilidade eficaz " ou "método eficaz". Esses formalizações incluiu a Gödel - Herbrand - Kleene funções recursivas de 1930, 1934 e 1935, Alonzo Church 's cálculo lambda de 1936, Emil Mensagem de Formulação 1 de 1936, e Alan Turing 's máquinas de Turing de 1936-1937 e 1939.

Etimologia

A palavra 'algoritmo' tem suas raízes na latinizing o nome de Al-Khwarizmi em um primeiro passo para Algorismus . Al-Khwarizmi ( persa : خوارزمی ., C 780-850) foi um persa matemático, astrônomo , geógrafo , e estudioso na Casa da Sabedoria , em Bagdá , cujo nome significa 'o nativo de Khwarezm ', uma região que fazia parte da maior Irã e está agora no Uzbequistão .

Cerca de 825, al-Khwarizmi escreveu um idioma árabe tratado sobre o sistema de numeração hindu-arábico , que foi traduzido para o latim durante o século 12 sob o título Algoritmi de numero Indorum . Este título significa "Algoritmi sobre os números dos índios", onde "Algoritmi" foi do tradutor latinização do nome de Al-Khwarizmi. Al-Khwarizmi foi o matemático mais lido na Europa no final da Idade Média, principalmente através de outro de seus livros, a Álgebra . No final da Idade Média Latina, Algorismus , Inglês ' algorism ', a corrupção de seu nome, significava simplesmente o "sistema de numeração decimal". No século 15, sob a influência da palavra grega ἀριθμός 'número' ( cf. 'aritmética'), a palavra latina foi alterado para algorithmus , eo correspondente Inglês termo 'algoritmo' é atestada primeiramente no século 17; no sentido moderno foi introduzido no século 19.

Em Inglês, foi usado pela primeira vez em cerca de 1230 e depois por Chaucer em 1391. Inglês adotou o termo francês, mas não foi até o final do século 19 que "algoritmo" assumiu o significado que tem em Inglês moderno.

Outro uso precoce da palavra é de 1.240, num manual intitulado Carmen de Algorismo composta por Alexandre de Villedieu . Começa assim:

HAEC Algorismus ars praesens dicitur, em qua / Talibus Indorum fruimur bis quinque figuris.

que se traduz por:

Algorism é a arte pelo que, actualmente, usamos esses números indianos, cujo número dois vezes cinco.

O poema é de algumas centenas de linhas de comprimento e resume a arte de cálculo com o novo estilo de dados Indiana, ou Talibus Indorum, ou numerais hindus.

definição informal

Uma definição informal poderia ser "um conjunto de regras que define precisamente uma seqüência de operações." que incluiria todos os programas de computador, incluindo programas que não executam cálculos numéricos. Geralmente, um programa é apenas um algoritmo de se parar eventualmente.

Um exemplo prototípico de um algoritmo é o algoritmo de Euclides para determinar o divisor comum máximo de dois inteiros; um exemplo (há outros) é descrita pelo fluxograma acima e como um exemplo de uma secção posterior.

Boolos, Jeffrey & 1974, 1999 oferta de um significado informal da palavra na seguinte citação:

Nenhum ser humano pode escrever rápido o suficiente, ou o tempo suficiente, ou pequeno o suficiente † († "cada vez menores, sem limite ... você estaria tentando escrever sobre moléculas, nos átomos, em elétrons") para listar todos os membros de uma enumerably infinita ajustada 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 enumerably infinitas: Eles podem dar instruções explícitas para determinar o n º membro do conjunto , por finita arbitrária n . Tais instruções são para ser dada bastante explicitamente, numa 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.

Um "set enumerably infinito" é um cujos elementos podem ser colocados em correspondência um-para-um com os números inteiros. Assim, Boolos e Jeffrey estão dizendo que um algoritmo implica instruções para um processo que "cria" inteiros saída de um arbitrário inteiro "input" ou inteiros que, em teoria, pode ser arbitrariamente grande. Assim, um algoritmo pode ser uma equação algébrica tal como y = m + n - duas variáveis de entrada "" arbitrários m e n que produzem uma saída y . Mas as tentativas vários autores para definir a noção indicam que a palavra implica muito mais do que isso, algo na ordem de (para o exemplo disso):

Instruções precisas (em linguagem compreendida por "o computador") para um "bom" processo rápido, eficiente, que especifica os "movimentos" de "o computador" (máquina ou humano, equipado com o necessário contido internamente informações e recursos) para encontrar , descodificar, e, em seguida, processar a entrada arbitrária inteiros / símbolos m e n , símbolos + e = ... e "eficaz" produzir, em um tempo "razoável", saída-inteiro y num determinado local e num formato especificado.

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

formalização

Algoritmos são essenciais para os dados do processo computadores caminho. Muitos programas de computador contêm algoritmos que detalham as instruções específicas de um computador deve executar (em uma ordem específica) para realizar uma tarefa específica, como o cálculo contracheques ou estudantes de impressão dos funcionários boletins. Assim, um algoritmo pode ser considerada como sendo qualquer sequência de operações que podem ser simulados por uma Turing completo do sistema. Autores que afirmam essa tese incluem Minsky (1967), Savage (1987) e Gurevich (2000):

Minsky: "Mas vamos também manter, com Turing que qualquer procedimento que poderia... 'Naturalmente' ser chamado eficaz, pode, de fato, ser realizado por uma máquina (simples) Embora isso possa parecer extrema, os argumentos... . a seu favor são difíceis de refutar".

Gurevich: "... 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 ... de acordo com Savage [1987], um algoritmo é um processo computacional definido por uma máquina de Turing" .

Tipicamente, quando um algoritmo está associado com processamento de informação, os dados podem ser lidos a partir de uma fonte de entrada, por escrito para um dispositivo de saída e armazenada para processamento adicional. Os dados armazenados são considerados como parte do estado interno da entidade realizar o algoritmo. Na prática, o estado é armazenado em um ou mais estruturas de dados .

Para alguns, tal 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, quaisquer passos condicionais devem ser tratados sistematicamente com, caso a caso; os critérios para cada caso devem ser claras (e computável).

Porque um algoritmo é uma lista precisa de passos precisos, a fim de computação é sempre crucial para o funcionamento do algoritmo. As instruções são geralmente assumido coletados explicitamente, e são descritos como de partida "de cima" e ir "até o fundo", uma idéia que é descrito mais formalmente pelo 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 que tenta descrever uma tarefa em, meios mecânicos "" discretas. Exclusivo para esta concepção de algoritmos formalizados é a operação de atribuição , definindo o valor de uma variável. Ela deriva da intuição de " memória " como um rascunho. Há um exemplo abaixo de uma tal atribuição.

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

expressando algoritmos

Algoritmos pode ser expressa em muitos tipos de notação, incluindo as línguas naturais , pseudocódigo , fluxogramas , drakon-charts , linguagens de programação ou tabelas de controle (processados por intérpretes ). Expressões de algoritmos de linguagem natural tendem a ser detalhado e ambígua, e são raramente utilizados para algoritmos complexos ou técnicos. Pseudocódigo, fluxogramas, drakon-charts e tabelas de controle são formas estruturadas para expressar algoritmos que evitam muitas das ambiguidades comuns nas declarações de linguagem natural. As linguagens de programação são indicadas principalmente para expressar algoritmos em um formulário que pode ser executado por um computador, mas são muitas vezes utilizados como uma forma de definir ou algoritmos de documentos.

Existe uma vasta variedade de representações possível e pode-se expressar uma determinada máquina de Turing programa como uma sequência de quadros da máquina (ver mais à máquina de estado finito , tabela de transição de estado e tabela de controlo ), como fluxogramas e drakon-gráficos (ver mais em diagrama de estado ), ou como uma forma de rudimentar código de máquina , ou do código de montagem chamado "conjuntos de quádruplos" (ver mais à máquina de Turing ).

Representações algoritmos podem ser classificados em três níveis aceitos de inscrição máquina de Turing:

descrição 1 de Alto Nível
"... prosa para descrever um algoritmo, ignorando os detalhes de implementação. A este nível, não preciso mencionar como a máquina gere a sua fita ou na cabeça."
Descrição dois Implantaçã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ós não dar detalhes de estados ou função de transição."
3 descrição formal
Mais detalhada, "nível mais baixo", dá "tabela de estado" da máquina de Turing.

Para um exemplo do algoritmo simples "Adicionar m + n" descrito em todos os três níveis, ver Algoritmo # Exemplos .

desenhar

Projeto de algoritmos refere-se a um método ou processo matemático para resolução de problemas e de engenharia algoritmos. O projeto de algoritmos é parte de muitas teorias de soluções de pesquisa de operação , tais como programação dinâmica e dividir-e-conquistar . Técnicas de concepção e implementação de projetos de algoritmos são também chamados de padrões de projeto de algoritmos, como o padrão de método de modelo e padrão decorador.

Um dos aspectos mais importantes do projeto algoritmo é criar um algoritmo que tem um tempo de execução eficiente, também conhecido como o Big O .

As etapas comuns no desenvolvimento de algoritmos:

  1. Definição de problema
  2. Desenvolvimento de um modelo
  3. Especificação do algoritmo
  4. Projetando um algoritmo
  5. Verificar a exactidão do algoritmo
  6. Análise de algoritmos
  7. Implementação do algoritmo
  8. teste de programa
  9. preparação de documentação

Implementação

NAND lógico algoritmo implementado eletronicamente em 7400 de chip

A maioria dos algoritmos são destinadas a ser implementadas como programas de computador . No entanto, os algoritmos também são implementados por outros meios, tais como numa rede neural biológica (por exemplo, o cérebro humano execução aritmética ou um insecto à procura de alimentos), em um circuito elétrico , ou num dispositivo mecânico.

algoritmos de computador

Exemplos fluxograma do canônicas estruturas Böhm-Jacopini : A seqüência (retângulos descendente da página), o while-do e do IF-THEN-ELSE. As três estruturas são feitas da GOTO condicional primitivo ( SE teste = verdadeiro Then GoTo passo xxx ) (um diamante), a GOTO incondicional (rectângulo), vários operadores de atribuição (rectângulo), e Halt (rectângulo). Nidificação destas estruturas no interior de atribuição de blocos resultar em diagramas complexos (cf Tausworthe 1977: 100,114).

Em sistemas de computador , um algoritmo é basicamente um exemplo de lógica escrito em software por desenvolvedores de software, para ser eficaz para o computador destinam "target" (s) para produzir saída de dados (talvez null) de entrada . Um algoritmo ótimo, mesmo rodando em hardware antigo, produziria resultados mais rápidos do que um não-óptima (maior complexidade de tempo algoritmo) para o mesmo fim, sendo executado em hardware mais eficiente; por isso algoritmos, como hardware de computador, são a tecnologia considerada.

Programas "Elegante" (compactos), "bons" programas (rápido) : a noção de "simplicidade e elegância" aparece informalmente em Knuth e precisamente na Chaitin :

Knuth:.." .Que deseja boas ...... Algoritmos em algum sentido estético vagamente definido Um critério é a duração do tempo necessário para executar o algoritmo .. Outros critérios são adaptabilidade do algoritmo para computadores, a sua simplicidade e elegância , etc"
Chaitin: ".. Um programa é 'elegante', pelo qual quero dizer que é o menor programa possível para produzir a saída que ele faz"

Chaitin prefacia sua definição com: "Eu vou mostrar que você não pode provar que um programa é 'elegante ' " -como uma prova resolveria o problema da parada (ibid).

Algoritmo em função da função calculável por um algoritmo : Para uma dada função podem existir vários algoritmos. Isto é verdade, mesmo sem expandir o conjunto de instruções disponíveis disponíveis para o programador. Rogers observa que "É... Importante distinguir entre a noção de algoritmo , ou seja, procedimento e a noção de função calculável por algoritmo , ou seja mapeamento gerados pelo processo. A mesma função pode ter vários algoritmos diferentes".

Infelizmente, pode haver uma troca entre a bondade (velocidade) e elegância (compactação) programa elegante -um pode dar mais passos para completar um cálculo do que um menos elegante. Um exemplo que utiliza o algoritmo de Euclides aparece abaixo.

Computadores (e computors), modelos de computação : um computador (ou "computor" humana) é um tipo restrito da máquina, um "dispositivo mecânico determinista discreta" cegamente que segue as suas instruções. Modelos primitivos de de Melzak e Lambek reduzida esta noção de quatro elementos: (i) discretos, distinguíveis locais , (ii) discretos, indistinguíveis contadores (iii) um agente, e (iv) uma lista de instruções que são eficazes em relação à capacidade da agente.

Minsky descreve uma variação mais agradável do modelo "ábaco" do Lambek em suas "bases muito simples para Computability ". Máquina de Minsky passa sequencialmente através da sua cinco (ou seis, dependendo de como um contagens) instruções, a menos que seja uma condicional IF-THEN GOTO ou um GOTO incondicional modifica o fluxo do programa de sequência. Além HALT, máquina de Minsky inclui três atribuição (substituição, substituição) operações: zero (por exemplo, o conteúdo da localização substituídos por 0: L ← 0), SUCCESSOR (por exemplo, L ← L + 1), e redução (por exemplo, L ← L - 1 ). Raramente deve um "código" programador de gravação com um tal conjunto de instruções limitado. Mas Minsky mostra (como fazem Melzak e Lambek) que sua máquina é Turing completa com apenas quatro gerais tipos de instruções: GOTO condicional, incondicional GOTO, cessão / substituição / substituição, e Halt.

Simulação de um algoritmo: computador linguagem (computor) : Knuth informa ao leitor que ".. A melhor maneira de aprender um algoritmo é experimentá-lo imediatamente levar caneta e papel e trabalhar com um exemplo". Mas o que dizer de uma simulação ou execução da coisa real? O programador deve traduzir o algoritmo em uma linguagem que o simulador / computador / computor pode efetivamente executar. Pedra dá um exemplo disso: ao calcular as raízes de uma equação quadrática do computor deve saber como tirar uma raiz quadrada. Se não o fizerem, então o algoritmo, para ser eficaz, deve fornecer um conjunto de regras para a extração de uma raiz quadrada.

Isto significa que o programador deve conhecer uma "linguagem" que é eficaz em relação ao agente de computação alvo (computador / computor).

Mas o modelo deve ser usado para a simulação? Van Emde Boas observa "mesmo que baseamos a teoria da complexidade no sumário em vez de máquinas de concreto, a arbitrariedade da escolha de um modelo permanece. É neste ponto que a noção de simulação entra". Quando a velocidade está sendo medido, o conjunto de instruções assuntos. Por exemplo, o subprograma no algoritmo de Euclides para calcular o restante seria executado muito mais rápido se o programador tinha um " módulo de instrução" disponíveis ao invés de apenas subtração (ou pior: apenas de Minsky "decréscimo").

Programação estruturada, estruturas canónicas : Pela tese de Church-Turing , qualquer algoritmo pode ser calculado por um modelo conhecido por ser Turing completa , e por manifestações de Minsky, Turing completude requer GOTO apenas quatro instrução tipos condicional e incondicional GOTO, cessão, Halt. Kemeny e Kurtz observar que, enquanto o uso "indisciplinada" do GOTOs incondicional e condicional IF-THEN GOTOs pode resultar em " código espaguete ", um programador pode escrever programas estruturados utilizando apenas estas instruções; por outro lado, "também é possível, e não muito difícil, para escrever programas mal estruturados em uma linguagem estruturada". Tausworthe aumenta os três Böhm-Jacopini estruturas canónicas : SEQÜÊNCIA, IF-THEN-ELSE, e enquanto-DO, com mais dois: do-while e CASE. Um benefício adicional de um programa estruturado é que ele se presta a provas de correção usando indução matemática .

Símbolos de fluxograma canônicos : O assessor gráfica chamado de fluxograma , oferece uma maneira de descrever e documentar um algoritmo (e um programa de computador de um). Como o fluxo de programa de uma máquina de Minsky, um fluxograma começa sempre no topo de uma página e continua para baixo. Seus símbolos primários são apenas quatro: o fluxo dirigido seta que mostra o programa, o retângulo (SEQUÊNCIA, GOTO), o diamante (IF-THEN-ELSE), eo ponto (OR-tie). As estruturas canónicas Böhm-Jacopini são feitos destas formas primitivas. Sub-estruturas pode "ninho" em retângulos, mas somente se uma única saída ocorre a partir da superestrutura. Os símbolos, e a sua utilização para criar as estruturas canónicas são mostrados no diagrama.

Exemplos

exemplo algoritmo

Uma animação do algoritmo quick triagem uma matriz de valores aleatórios. As barras vermelhas marcar o elemento de pivô; no início da animação, o elemento mais distante para o lado direito é escolhido como o pivô.

Um dos algoritmos mais simples é encontrar o maior número em uma lista de números de forma aleatória. Encontrar a solução requer olhando para cada número na lista. A partir deste segue um algoritmo simples, que pode ser indicado em uma descrição de alto nível em Inglês prosa, como:

descrição de alto nível:

  1. Se não existirem números no conjunto, então não há número mais alto.
  2. Suponha que o primeiro número no conjunto é o maior número no conjunto.
  3. Para cada número restante no conjunto: se este número é maior do que o número atual maior, considere este número para ser o maior número no conjunto.
  4. Quando não há números deixados no conjunto para iterar, considere o número atual maior a ser o maior número do conjunto.

(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 código pidgin :

Algorithm LargestNumber
  Input: A list of numbers L.
  Output: The largest number in the list L.
  if L.size = 0 return null
  largestL[0]
  for each item in L, do
    if item > largest, then
      largestitem
  return largest
  • "←" denota atribuição . Por exemplo, " maiorartigo " significa que o valor de maiores alterações no valor do item de .
  • " Retorno " termina o algoritmo e produz o seguinte valor.

O algoritmo de Euclides

O exemplo do diagrama de algoritmo de Euclides de TL Heath (1908), com mais detalhe adicionado. que Euclides não ir além de uma terceira medição e não dá exemplos numéricos. Nicomachus dá o exemplo de 49 e 21: "I subtrair a menos da maior; 28 é esquerdo; em seguida, novamente eu subtrair este o mesmo 21 (por isso é possível); 7 é esquerdo; eu subtrair este a partir de 21, 14 é esquerda, a partir do qual eu novamente subtrair 7 (para isso é possível); 7 é esquerda, mas 7 não pode ser subtraído 7." Heath comenta que "A última frase é curiosa, mas o significado é óbvio o suficiente, como também o significado da frase sobre o fim 'em um e ao mesmo número'." (Heath 1908: 300).

Euclides algoritmo 's para calcular o máximo divisor comum (GCD) para dois números aparece como Proposição II no Livro VII ( 'Teoria dos números elementar') dos seus elementos . Euclides coloca o problema assim: "Dados dois números não primos uns aos outros, para encontrar a sua maior medida comum". Ele define "Um número [ser] uma multidão composta de unidades": um número de contagem, um número inteiro positivo não incluindo zero. Para "medir" é colocar um comprimento mais curto de medição s sucessivamente ( q vezes) ao longo de um comprimento mais longo l até que a porção restante r é menor do que o comprimento mais curto s . Em palavras modernas, restante r = l - q × s , q sendo o quociente, ou restante r é o "módulo", a parte inteira-fraccionada sobra após a divisão.

Para o método de Euclides para ter sucesso, os comprimentos de partida deve satisfazer dois requisitos: (i) os comprimentos não deve ser zero, e (ii) a subtração deve ser “adequada”; ou seja, um ensaio deve garantir que o menor dos dois números é subtraído do maior (alternadamente, os dois podem ser iguais então os seus rendimentos subtração zero).

Comprovante original de Euclides adiciona uma terceira exigência: os dois comprimentos não deve ser privilegiada para o outro. Euclides estipulado isso para que ele pudesse construir um reductio ad absurdum prova de que medida comum os dois números é de fato o maior . Enquanto algoritmo Nicômaco é o mesmo que Euclides da, quando os números são primos uns dos outros, ele produz o número '1' para a sua medida comum. Assim, para ser mais preciso, o seguinte é realmente algoritmo Nicômaco.

A expressão gráfica do algoritmo de Euclides para encontrar o máximo divisor comum para 1599 e 650.
 1599 = 650×2 + 299
 650 = 299×2 + 52
 299 = 52×5 + 39
 52 = 39×1 + 13
 39 = 13×3 + 0

linguagem de computador para o algoritmo de Euclides

Apenas alguns instrução tipos são necessários para executar algoritmo de alguns testes de Euclides lógicos (Goto condicional), Goto incondicional, cessão (substituição) e subtração.

  • A localização é simbolizada pela letra maiúscula (s), por exemplo, S, A, etc.
  • A quantidade variável (número) numa localização é escrita em letra minúscula (s) e (normalmente) associado com o nome do local. Por exemplo, a localização G no início pode conter o número l = 3009.

Um programa deselegante para o algoritmo de Euclides

"Deselegante" é uma tradução da versão de Knuth do algoritmo com um resto de circuito baseado em subtração substituindo o uso de divisão (ou uma instrução de "módulo"). Derivado do Knuth, 1973: 2-4. Dependendo dos dois números "deselegante" pode calcular o mdc em menos etapas do que "elegante".

O seguinte algoritmo é moldado como a versão de quatro etapas de Knuth de Euclides e Nicomachus', mas, em vez de utilizar a divisão para encontrar o restante, ele usa subtracções sucessivas do menor comprimento s do comprimento restante R até R é menos do que s . A descrição de alto nível, mostrados em negrito, é adaptado de Knuth, 1973: 2-4:

ENTRADA :

1 [Into two locations L and S put the numbers l and s that represent the two lengths]:
  INPUT L, S
2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]:
  R ← L

E0: [Certifique- rs .]

3 [Ensure the smaller of the two numbers is in S and the larger in R]:
  IF R > S THEN
    the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6:
    GOTO step 6
  ELSE
    swap the contents of R and S.
4   L ← R (this first step is redundant, but is useful for later discussion).
5   R ← S
6   S ← L

E1: [Encontrar restante] : Até que o comprimento restante de R em R é menor do que o comprimento mais curto s em S, subtrair repetidamente a medição número s em S a partir do comprimento restante r em R.

7 IF S > R THEN
    done measuring so
    GOTO 10
  ELSE
    measure again,
8   R ← R − S
9   [Remainder-loop]:
    GOTO 7.

E2: [é zero restante?] : (I) a última medida foi exata, o restante em R é zero, eo programa pode parar, ou (ii) o algoritmo deve continuar: a última medida deixou um resto em R menos do que medir o número de S.

10 IF R = 0 THEN
     done so
     GOTO step 15
   ELSE
     CONTINUE TO step 11,

E3: [Interchange s e r ] : A porca de algoritmo de Euclides. Use restante r para medir o que anteriormente era menor número de s ; L serve como um local temporário.

11  L ← R
12  R ← S
13  S ← L
14  [Repeat the measuring process]:
    GOTO 7

SAÍDA :

15 [Done. S contains the greatest common divisor]:
   PRINT S

FEITO :

16 HALT, END, STOP.

Um programa elegante para o algoritmo de Euclides

A versão seguinte do algoritmo de Euclides exige apenas seis instruções centrais para fazer o que treze são obrigados a fazer por "deselegante"; pior, "deselegante" exige mais tipos de instruções. O fluxograma de "elegante" pode ser encontrado na parte superior deste artigo. No (não estruturada) linguagem Basic, os passos são numerados, ea instrução é a instrução de atribuição simbolizada por ←. LET [] = []

  5 REM Euclid's algorithm for greatest common divisor
  6 PRINT "Type two integers greater than 0"
  10 INPUT A,B
  20 IF B=0 THEN GOTO 80
  30 IF A > B THEN GOTO 60
  40 LET B=B-A
  50 GOTO 20
  60 LET A=A-B
  70 GOTO 20
  80 PRINT A
  90 END

A versão seguinte pode ser usado com linguagens Object Oriented:

// Euclid's algorithm for greatest common divisor
integer euclidAlgorithm (int A, int B){
     A=Math.abs(A);
     B=Math.abs(B);
     while (B!=0){
          if (A>B) A=A-B;
          else B=B-A;
     }
     return A;
}

Como "elegante" funciona : No lugar de um "loop de Euclides" exterior "elegante" muda e para trás entre dois "co-loops", um A> circuito B que computa A ← A - B, e B ≤ Um loop que calcula B ← B - A. Isso funciona porque, quando finalmente o minuendo M é menor ou igual ao subtrahend s (diferença = minuendo - subtrahend), o minuendo pode se tornar s (o novo comprimento de medição) ea subtrahend pode tornar-se a nova r (o comprimento a ser medida); em outras palavras, o "sentido" da subtração inverte.

Testar os algoritmos de Euclides

Será que um algoritmo fazer o seu autor quer que ele faça? Alguns casos de teste normalmente suficiente para confirmar a funcionalidade do núcleo. Uma fonte usa 3009 e 884. Knuth sugeriu 40902, 24140. Outro caso interessante é o de dois relativamente primos números 14157 e 5950.

Mas casos excepcionais devem ser identificados e testados. Vai "deselegante" executar corretamente quando R> S, S> R, R = S? O mesmo vale para "Elegant": B> A, A> B, A = B? (Sim para tudo). O que acontece quando um número é zero, ambos os números são zero? ( "Deselegante" calcula sempre em todos os casos; "elegante" calcula sempre quando A = 0.) O que acontece se negativos números são inseridos? Números fracionários? Se os números de entrada, isto é, o domínio da função calculado pelo algoritmo / programa, é incluir apenas números inteiros positivos, incluindo zero, em seguida, as falhas em zero indicam que o algoritmo (e o programa que instancia ele) é uma função parcial , em vez de uma função totais . Uma falha notável devido a exceções é o Ariane 5 Vôo 501 falhas de foguetes (4 de Junho, 1996).

Prova de correção programa por uso de indução matemática : Knuth demonstra a aplicação de indução matemática para uma versão "estendida" do algoritmo de Euclides, e ele propõe "um método geral aplicável a provar a validade de qualquer algoritmo". Tausworthe propõe que uma medida da complexidade de um programa de ser o comprimento de sua prova de correcção.

Medir e melhorar os algoritmos de Euclides

Elegance (compactação) versus bondade (velocidade) : Com apenas seis instruções do núcleo, "elegante" é o vencedor claro, em comparação com "deselegante" em treze instruções. No entanto, "deselegante" é mais rápido (que chega HALT em menos etapas). Análise de algoritmos indica por que este é o caso: "Elegant" faz dois testes condicionais em cada circuito subtração, enquanto que "deselegante" só faz uma. Como o algoritmo (geralmente) requer muitas loop-throughs, em média, muito tempo é desperdiçado fazendo um "B = 0?" teste que é necessário apenas depois o restante é calculado.

Os algoritmos pode ser melhorado? : Uma vez que os juízes programador um programa de "ajuste" e "eficaz", isto é, ele calcula a função pretendida pelo autor, então a questão torna-se, pode ser melhorado?

A compacidade de "deselegante" pode ser melhorada através da eliminação de cinco etapas. Mas Chaitin provou que compactar um algoritmo não pode ser automatizado por um algoritmo generalizada; ao contrário, ela só pode ser feito de forma heurística ; isto é, por pesquisa exaustiva (exemplos para ser encontrada em castor Busy ), de tentativa e erro, a inteligência, visão, aplicação de raciocínio indutivo , etc. Observa-se que os passos 4, 5 e 6 são repetidos nos passos 11, 12 e 13. A comparação com "elegante" proporciona uma indicação de que estes passos, conjuntamente com os passos 2 e 3, pode ser eliminado. Isso reduz o número de instruções do núcleo 13-8, o que torna "mais elegante" do que "elegante", em nove etapas.

A velocidade de "elegante" pode ser melhorado, movendo o "B = 0?" teste de fora dos dois circuitos de subtracção. Esta mudança exige a adição de três instruções (B = 0 ?, A = 0 ?, Goto). Agora "elegante" calcula os exemplos de-números mais rápido; se este é sempre o caso, para qualquer A, B, e R, S exigiria uma análise detalhada.

análise algorítmica

É frequentemente importante saber quanto de um recurso específico (como o tempo ou armazenamento) é teoricamente necessária para um determinado algoritmo. Métodos foram desenvolvidos para a análise de algoritmos para obter tais respostas quantitativas (estimativas); por exemplo, o algoritmo de classificação acima tem um requisito de tempo de O ( n ), usando a notação grande S com n 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 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 ( n ) se for contado.

Algoritmos diferentes 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, uma busca binária algoritmo (com custo O (log n)) supera uma pesquisa seqüencial (custo O (n)), quando utilizado para pesquisas de tabela de listas ordenadas ou matrizes.

Formal versus empírica

A análise e estudo de algoritmos é uma disciplina de ciência da computação , e é muitas vezes praticado de forma abstrata, sem o uso de uma específica linguagem de programação ou implementação. Nesse sentido, a análise de algoritmos se assemelha a 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 mais geral. No entanto, em última análise, a maioria dos algoritmos são geralmente implementadas em determinadas plataformas de hardware / software e sua eficiência algorítmica , eventualmente, é posta à prova usando o código real. Para a solução de um "one off" problema, a eficiência de um determinado algoritmo pode não ter consequências significativas (a menos que n é extremamente grande), mas por algoritmos projetados para uso científico rápido vida interativa, comercial ou tempo pode ser crítico. Escala de pequena n para n grande frequência expõe algoritmos ineficientes que são de outra forma benigna.

Teste empírico é útil porque pode descobrir interações inesperadas que afetam o desempenho. Benchmarks pode ser usado para comparar antes / depois potenciais melhorias para um algoritmo após otimização do programa. Testes empíricos não podem substituir a análise formal, no entanto, e não são triviais para executar de uma forma justa.

eficiência de execução

Para ilustrar as potenciais melhorias possíveis algoritmos, mesmo em bem estabelecidos, uma recente inovação significativa, relativos a FFT algoritmos (muito usado no campo de processamento de imagens), pode diminuir o tempo de processamento de até 1.000 vezes para aplicações como imagens médicas. Em geral, melhorias de velocidade dependem de propriedades especiais do problema, que são muito comuns em aplicações práticas. Speedups desta magnitude permitir que dispositivos de computação que fazem uso extensivo de processamento de imagem (como câmeras digitais e equipamentos médicos) para consumir menos energia.

Classificação

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

por implementação

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

Recursão
Um algoritmo recursivo é um que invoca (faz referência a) em si várias vezes até que uma determinada condição (também conhecido como condição de terminação) corresponde a, que é um método comum de programação funcional . Iterativos algoritmos usar construções repetitivas como laços e estruturas de dados, por vezes adicionais, como pilhas para resolver os problemas apresentados. Alguns problemas são naturalmente adequadas para uma aplicação ou outro. Por exemplo, torres de Hanoi é bem compreendida utilizando 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 controlado dedução lógica . Esta noção pode ser expressa como: Algoritmo = lógica + controle . O componente lógica expressa os axiomas que podem ser utilizados no cálculo eo componente de controle determina a maneira pela qual dedução é aplicada aos axiomas. Esta é a base para a programação em lógica de paradigma. Em linguagens de programação lógica pura, o componente de controle é fixo e algoritmos são especificados, fornecendo apenas o componente lógica. O apelo dessa abordagem é o elegante semântica : uma mudança nos axiomas produz uma mudança bem definida no algoritmo.
De série, em paralelo ou distribuído
Algoritmos são normalmente discutidos com o pressuposto de que os computadores executar uma instrução de um algoritmo de cada vez. Esses computadores são chamados às vezes computadores de série. Um algoritmo concebido para tal ambiente é chamado um algoritmo de série, ao invés de em paralelo algoritmos 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 utilizam várias máquinas conectadas com uma rede de computadores . Algoritmos paralelos ou distribuídos dividir o problema em sub-problemas mais simétricos ou assimétricos e recolher os resultados de volta juntos. O consumo de recursos em tais algoritmos não é apenas ciclos de processador em cada processador, mas também a sobrecarga de comunicação entre os processadores. Alguns algoritmos de ordenação pode ser paralelizado de forma eficiente, mas a sua sobrecarga de comunicação é caro. Algoritmos iterativos são geralmente paralelizável. Alguns problemas não têm algoritmos paralelos e são chamados inerentemente problemas de série.
Determinista ou não-determinístico
Algoritmo determinístico resolver o problema com a decisão exata a cada passo do algoritmo enquanto algoritmos não-deterministas resolver problemas através de adivinhação, embora suposições típicas são feitas mais precisos através do uso de heurística .
Exacta ou aproximada
Enquanto muitos algoritmos de alcançar uma solução exata, algoritmos de aproximação procuram uma aproximação que está mais perto da verdadeira solução. A aproximação pode ser alcançado por qualquer um usando um determinista ou uma estratégia aleatória. Esses algoritmos têm valor prático para muitos problemas difíceis. Um dos exemplos de um algoritmo aproximado é o problema da mochila . O problema da mochila é um problema onde há um conjunto de objectos disponíveis. O objetivo do problema é para embalar a mochila para obter o valor máximo total. Cada item tem algum peso e algum valor. Peso total que podemos realizar nada mais é que um número X. fixo Então, devemos considerar pesos de itens, bem como o seu valor.
algoritmo quântico
Elas funcionam com um modelo realista de computação quântica . O termo é usado geralmente para esses algoritmos que parecem quantum inerentemente, ou usar alguma característica essencial da computação quântica , tais como superposição quântica ou entrelaçamento quântico .

Por paradigma de design

Outra forma de classificar algoritmos é pela sua metodologia de projeto ou paradigma. Há um certo número de paradigmas, diferentes uns dos outros. Além disso, cada uma dessas categorias inclui muitos tipos diferentes de algoritmos. Alguns paradigmas comuns são:

De força bruta ou busca exaustiva
Este é o método ingênuo de tentar todas as soluções possíveis para ver qual é o melhor.
Dividir e conquistar
Um algoritmo de dividir para conquistar reduz repetidamente um exemplo de um problema para um ou mais pequenos instâncias do mesmo problema (geralmente de forma recursiva ) até que os exemplos são suficientemente pequenas para resolver facilmente. Um exemplo de dividir e conquistar é fundir a classificação . A classificação pode ser feito em cada segmento de dados depois de dividir os dados em segmentos e triagem de dados podem ser obtidos na fase conquista por fusão dos segmentos. Uma variante mais simples de dividir e conquistar é chamado de queda e conquistar algoritmo , que resolve um subproblema idênticos e usa a solução deste subproblema para resolver o problema maior. Dividir para conquistar divide o problema em vários sub-problemas e por isso a fase conquista é mais complexo do que diminuem e conquistar algoritmos. Um exemplo de um algoritmo de redução e conquistar é o algoritmo de busca binária .
Pesquisa e enumeração
Muitos problemas (tais como jogar xadrez ) podem ser modelados como problemas em gráficos . Um algoritmo de exploração gráfico especifica regras para a movimentação em torno de um gráfico e é útil para tais problemas. Esta categoria também inclui algoritmos de busca , derivação e limitação enumeração e retrocesso .
algoritmo aleatório
Tais algoritmos fazer algumas escolhas de forma aleatória (ou pseudo-aleatoriamente). Eles podem ser muito úteis na busca de soluções aproximadas para problemas onde encontrar soluções exatas pode ser impraticável (ver método heurístico abaixo). Para alguns desses problemas, sabe-se que as aproximações mais rápidos deve envolver algum aleatoriedade . Se algoritmos randomizados com complexidade de tempo polinomial podem ser os algoritmos mais rápidos para alguns problemas é uma questão em aberto conhecido como o P versus NP . Há duas grandes classes de tais algoritmos:
  1. Monte Carlo algoritmos retornar uma resposta correta com alta probabilidade. Por exemplo, RP é a subclasse destes que ser executado em tempo polinomial .
  2. Las Vegas algoritmos sempre retornar a resposta correta, mas o seu tempo de execução só é probabilisticamente ligados, por exemplo, ZPP .
Redução da complexidade
Esta técnica envolve a solução de um problema difícil, transformando-o em um problema mais conhecido para o qual temos (espero) assintoticamente ótimos algoritmos. O objetivo é encontrar um algoritmo de redução cuja complexidade não é dominada pelos resultantes algoritmo de redução. Por exemplo, um algoritmo de seleção para encontrar a mediana de uma lista não ordenada envolve primeiramente classificar a lista (a parte caro) e, em seguida, puxando para fora o elemento do meio na lista ordenada (a parte barato). Esta técnica também é conhecida como transformar e conquistar .
rastreamento de volta
Nesta abordagem, várias soluções são construídas de forma incremental e abandonado quando for determinado que eles não podem conduzir a uma solução completa válida.

problemas de optimização

Para problemas de otimização há uma classificação mais específica de algoritmos; um algoritmo para esses problemas podem cair em uma ou mais das categorias gerais acima descritos, bem como em um dos seguintes procedimentos:

Programação linear
Ao procurar soluções óptimas para uma função linear ligado a igualdade e desigualdade lineares, as restrições de que o problema pode ser utilizado directamente na produção de soluções óptimas. Existem algoritmos que podem resolver qualquer problema nesta categoria, tais como o popular algoritmo simplex . Problemas que podem ser resolvidos com programação linear incluir o problema do fluxo máximo para grafos dirigidos. Se um problema exige ainda que uma ou mais das incógnitas deve ser um número inteiro , então ele é classificado na programação inteira . Um algoritmo de programação linear pode resolver um problema tão grande se puder ser provado que todas as restrições para valores inteiros são superficiais, ou seja, as soluções satisfazer essas restrições de qualquer maneira. No caso geral, um algoritmo especializado ou um algoritmo que encontra soluções aproximadas é usado, dependendo da dificuldade do problema.
Programaçao dinamica
Quando um problema mostra subestruturas óptimas - ou seja, a solução ideal para um problema pode ser construído a partir de soluções óptimas para sub-problemas - e subproblems sobrepostas , ou seja, os mesmos sub-problemas são usados para resolver muitos casos de problemas diferentes, uma abordagem mais rápida chamado programação dinâmica evita soluções recomputing que já foram computados. Por exemplo, Floyd-Warshall algoritmo , o caminho mais curto para um objectivo de um vértice de um ponderada gráfico pode ser encontrado usando o caminho mais curto para o objectivo de todos os vértices adjacentes. Programação dinâmica e memoization ir juntos. A principal diferença entre a programação dinâmica e dividir e conquista é que os sub-problemas são mais ou menos independente em dividir para conquistar, ao passo que se sobrepõem em sub-problemas de 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; daí programação dinâmica não é uma solução para todos os problemas complexos. Usando memoization ou manter uma mesa de subproblemas já resolvido, programação dinâmica reduz a natureza exponencial de muitos problemas a complexidade polinomial.
O método ávido
Um algoritmo guloso é semelhante a um algoritmo de programação dinâmica em que ele funciona por subestruturas examinando, neste caso, não do problema, mas de uma determinada solução. Tais algoritmos começar com alguma solução, que pode ser dada ou que tenham sido construídas, de alguma forma, e melhorá-la, fazendo pequenas modificações. Para alguns problemas que podem encontrar a solução ideal, enquanto para outros eles param em ótimos locais , ou seja, a soluções que não podem ser melhoradas pelo algoritmo, mas não são a melhor. O uso mais popular de algoritmos gulosos é para encontrar a árvore de extensão mínima onde encontrar a melhor solução é possível com este método. Huffman Árvore , Kruskal , Prim , Sollin são algoritmos gananciosos que podem resolver este problema de otimização.
O método heurístico
Em problemas de otimização , algoritmos heurísticos pode ser usado para encontrar uma solução perto da solução ideal nos casos em que encontrar a solução ideal é impraticável. Esses algoritmos trabalham cada vez mais perto para a solução ideal à medida que progridem. Em princípio, se executado por uma quantidade infinita de tempo, eles vão encontrar a solução ideal. Seu mérito é que eles podem encontrar uma solução muito próxima da solução ótima em um tempo relativamente curto. Tais algoritmos incluem a busca local , busca tabu , recozimento simulado , e algoritmos genéticos . Alguns deles, como o recozimento simulado, são algoritmos não-determinístico enquanto outros, como busca tabu, são deterministas. Quando um limite do erro da solução não óptimo é conhecida, o algoritmo está ainda classificados como um algoritmo de aproximaçã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 exemplo são algoritmos de busca , algoritmos de classificação , fundir algoritmos , algoritmos numéricos , algoritmos de grafos , algoritmos de cordas , algoritmos geométricos computacionais , algoritmos combinatórios , algoritmos médicos , aprendizado de máquina , criptografia , compressão de dados algoritmos e técnicas de análise .

Campos tendem a sobrepor-se uns com os outros, e os avanços algoritmo em um campo pode melhorar os da outra, por vezes, completamente independentes, campos. Por exemplo, programação dinâmica foi 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.

pela complexidade

Algoritmos podem ser classificados pela quantidade de tempo necessário para completar em relação ao tamanho de entrada:

  • Constante de tempo: se o tempo necessário para que o algoritmo é o mesmo, independentemente do tamanho da entrada. Por exemplo, um acesso a uma matriz elemento.
  • O tempo linear: se o tempo é proporcional ao tamanho da entrada. Por exemplo, a travessia de uma lista.
  • Tempo logarítmica: se o tempo é uma função logarítmica do tamanho da entrada. Por exemplo algoritmo de busca binária .
  • Tempo polinomial: se o tempo é um poder do tamanho da entrada. Por exemplo, o bubble sort algoritmo tem complexidade de tempo quadrática.
  • Tempo exponencial: se o tempo é uma função exponencial do tamanho da entrada. Por exemplo, a pesquisa de força bruta .

Alguns problemas podem ter vários algoritmos de diferentes complexidade, enquanto outros problemas podem não têm algoritmos ou há algoritmos eficientes conhecidos. Há também mapeamentos de alguns problemas para outros problemas. Devido a isso, verificou-se ser mais adequada para classificar os próprios problemas em vez dos algoritmos em classes de equivalência com base na complexidade dos melhores algoritmos possíveis para eles.

algoritmos contínuos

O adjetivo "contínuo" quando aplicado à palavra "algoritmo" pode significar:

  • Um algoritmo que opera em dados que representa quantidades contínuos, mesmo considerando que estes dados é representado por aproximações-discretas tais algoritmos são estudados em análise numérica ; ou
  • Um algoritmo na forma de uma equação diferencial que opera continuamente sobre os dados, rodando em um computador analógico .

Questões legais

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

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

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

Antigo Oriente Próximo

Algoritmos foram utilizados na Grécia antiga. Dois exemplos são o Crivo de Eratóstenes , que foi descrito em Introduction to Aritmética por Nicomachus , e o algoritmo de Euclides , que foi descrita pela primeira vez em elementos de Euclides (c. 300 BC). Tábuas de argila Babilônicas descrever e utilizar procedimentos algorítmicos para calcular o tempo e local de eventos significativos astronómicas.

símbolos discretos e distinguíveis

Tally-marcas : Para manter o controle de seus rebanhos, seus sacos de grãos e seu dinheiro os antigos usavam contagem: acumulando pedras ou marcas riscadas em varas ou fazer símbolos discretos em argila. Através do uso babilônica e egípcia de marcas e símbolos, eventualmente, numerais romanos eo ábaco evoluiu (Dilson, p. 16-41). Marcas de registro aparecer com destaque no sistema numeral unário aritmética usada na máquina de Turing e máquina Post-Turing cálculos.

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

O trabalho dos antigos geômetras gregos ( algoritmo de Euclides ), o indiano matemático Brahmagupta , eo matemático persa Al-Khwarizmi (de cujo nome os termos " algorism " e "algoritmo" são derivados) e matemáticos da Europa Ocidental culminou com Leibniz 's noção de calculus ratiocinator (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 manipular números.

invenções mecânicas com estados discretos

O relógio : créditos Bolter a invenção do impulsionado-peso relógio como "A invenção tecla [da Europa na Idade Média]", em particular, a fuga beira que nos fornece o carrapato e tock de um relógio mecânico. "A máquina automática precisas" levou imediatamente a "mecânica autômatos ", começando no século 13 e, finalmente, "máquinas computacionais" -a motor de diferença e motores analíticos de Charles Babbage e Condessa Ada Lovelace , meados do século 19. Lovelace é creditado com a primeira criação de um algoritmo destinado a ser transformado em um computador - máquina analítica de Babbage, o primeiro dispositivo considerado uma verdadeira Turing completo computador em vez de apenas uma calculadora - e às vezes é chamado de "primeira programadora da história", como resultado, embora uma implementação completa do segundo dispositivo de Babbage não seria realizado até décadas após a sua vida.

Máquinas lógicas 1870- Stanley Jevons 'ábaco lógica' 'e 'máquina lógica' : O problema técnico foi reduzir equações booleanas quando apresentadas de forma semelhante ao que hoje é conhecido como mapas de Karnaugh . Jevons (1880) descreve pela primeira vez um "ábaco" simples de "tiras de madeira, equipadas com pinos, maquinado de modo a que qualquer parte ou classe das combinações [lógicos] pode ser retirado mecanicamente... Mais recentemente, no entanto, que reduziram a sistema de uma forma completamente mecânica, e, assim, incorporada a todo o processo indireto de inferência no que pode ser chamado de uma máquina lógica "Sua máquina veio equipado com 'certos hastes de madeira móveis' e" no pé são 21 teclas como as de um piano [etc]... ". Com esta máquina, ele poderia analisar um " silogismo ou qualquer outro argumento lógico simples".

Esta máquina que ele mostrou em 1870 antes que os Fellows da Royal Society. Outra lógico John Venn , no entanto, em seu 1881 Symbolic Logic , virou um olhar invejoso para este esforço: "Eu não tenho high-me estimar o interesse ou importância do que às vezes são chamados máquinas lógicas ... não me parece que quaisquer artifícios, actualmente conhecidos ou susceptíveis de ser descoberto realmente merece o nome de máquinas lógicas "; veja mais em caracterizações Algorithm . Mas para não ficar atrás, ele também apresentou "um plano de algo análogo, eu entendo, a do Prof. Jevon ábaco ... [E] [a] ganho, correspondendo a máquina lógica do Prof. Jevons, o seguinte artifício pode ser descrito. Prefiro chamá-lo apenas uma máquina lógica diagrama ... mas suponho que ele poderia fazer muito completamente tudo o que pode ser racionalmente esperado de qualquer máquina lógica".

Tear Jacquard, Hollerith cartões perfurados, telegrafia e telefonia do relé eletromecânico : Bell e Newell (1971) indicam que o tear Jacquard (1801), precursor Hollerith cartões (cartões perfurados, 1887), e "tecnologias de comutação telefônica" foram as raízes de uma árvore levando ao desenvolvimento dos primeiros computadores. Até o meados do século 19 telégrafo , o precursor do telefone, estava em uso em todo o mundo, a sua codificação discreto e distinguíveis de letras como "pontos e traços" um som comum. No final do século 19, a fita de relógio (1870 ca) estava em uso, como foi o uso de Hollerith cartões no censo de 1890 dos EUA. Depois veio o teletipo (cerca de 1910) com o seu uso em papel perfurado de código Baudot em fita.

Redes de comutação de telefone de eletromecânica relés (inventado 1835) estava por trás da obra de George Stibitz (1937), o inventor do dispositivo acrescentando digital. Enquanto trabalhava na 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 binário dispositivo acrescentando' .

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

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 escopo Babbage tinha imaginado ".

Matemática durante o século 19 até meados do século 20

Os símbolos e as regras : Em sucessão rápida, a matemática da George Boole (1847, 1854), Gottlob Frege (1879), e Giuseppe Peano (1888-1889) reduzido aritmética para uma sequência de símbolos manipuladas 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".

Mas Heijenoort dá Frege (1879) este elogios: Frege é "talvez a obra mais importante já escrito na lógica ... em que vemos um." 'Linguagem de fórmula', que é um characterica língua , uma língua escrita com símbolos especiais , "para o pensamento puro", isto é, livre de enfeites retóricos ... construída a partir de símbolos específicos que são manipulados de acordo com regras definidas". O trabalho de Frege foi ainda mais simplificada e amplificado por Alfred North Whitehead e Bertrand Russell , em seu Principia Mathematica (1910-1913).

Os paradoxos : Ao mesmo tempo um número de paradoxos perturbadoras apareceu na literatura, em particular, o paradoxo Burali-Forti (1897), o paradoxo Russell (1902-1903), e o Richard Paradox . As considerações resultantes levaram a Kurt Gödels papel 's (1931) -ele cita especificamente o paradoxo da liar-que reduz completamente as regras de recursividade de números.

Calculabilidade eficaz : 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 eficaz" (ou seja, um cálculo que teria sucesso ). Em rápida sucessão, o seguinte apareceu: Alonzo Church , Stephen Kleene e JB Rosser 's λ-calculus uma definição finamente afinados de 'recursão geral' do trabalho de Gödel agindo em sugestões de Jacques Herbrand (cf. palestras de Princeton de Gödel de 1934) e simplificações subsequentes por Kleene. A prova da Igreja que o Entscheidungsproblem era insolúvel, Emil Publicar definição 's de calculabilidade eficaz 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 salas e enquanto não há qualquer marca ou apagar um papel ou observar o papel e fazer um sim-não decisão sobre a próxima instrução. Prova de que o Entscheidungsproblem de Alan Turing era insolúvel pelo uso de sua "a- máquina [automático-]" efeito -em quase idêntico a "formulação" do Post, J. Barkley Rosser definição de 'método eficaz' 's em termos de "uma máquina". SC Kleene proposta de um precursor da ' tese de Church ', que ele chamou de 'Tese I', e alguns anos mais tarde Kleene de renomear sua tese 'Tese da Igreja' e propondo 'Tese de Turing'.

Emil Post (1936) e Alan Turing (1936-1937, 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 que produzam definições praticamente idênticos.

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

" ... dois conceitos estão envolvidos: a de um espaço de símbolo em que o trabalho que conduz do problema para responder é para ser levada a cabo, e uma inalterável fixo conjunto de direçõ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 caixa in, mas um de cada vez .... uma caixa é de admitir de mas duas condições possíveis, ou seja, estar vazio ou não marcado, e possuindo um único ponto em que, digamos, um curso vertical.
"Uma caixa é para ser apontados e chamado o ponto de partida. ... um problema específico deverá ser determinada de forma simbólica por um número finito de caixas de [ou seja, ENTRADA] ser marcados com um acidente vascular cerebral. Do mesmo modo, a resposta [ou seja , OUTPUT] deve ser dada de forma simbólica por uma tal configuração de caixas marcadas ...
"Um conjunto de instruções aplicáveis a um problema geral define-se um processo determinista, quando aplicado para cada problema específico. Este processo termina apenas quando se trata de direcção do tipo (C) [ou seja, STOP]". Veja mais na máquina de Post-Turing
A estátua de Alan Turing em Bletchley Park

Alan Turing trabalho da 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 um modelo de máquina de escrever do tipo de Turing 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 chamando uma máquina de escrever 'mecânica'". Dada a prevalência de código Morse e telegrafia, máquinas de fita ticker, e teletypewriters podemos conjecturar que todos eram influências.

Turing-o seu modelo de computação é agora chamado uma máquina de Turing -begins, como fez Post, com uma análise de um computador humano que ele whittles até 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.

"Computing é normalmente feito por escrito certos símbolos no papel. Podemos supor que este trabalho está dividido em quadrados como o livro de aritmética de uma criança ... Eu suponho então que o cálculo é realizado em papel unidimensional, ou seja, em uma fita dividida em quadrados. Eu também deve supor que o número de símbolos que podem ser impressas é 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 que 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 dividido em 'operações simples', que são tão elementar que não é fácil imaginá-los ainda mais dividido."

redução de Turing produz o seguinte:

"As operações simples deve, portanto, incluir:
"(A) Alterações do símbolo em um dos quadrados observados
"(B) As alterações de um dos quadrados observados para outro quadrado dentro L quadrados de um dos quadrados 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 um dos seguintes procedimentos.:

"(A) A possível mudança (a) do símbolo juntamente com uma possível mudança de estado de espírito.
"(B) A possível mudança (b) de quadrados observados, juntamente com uma possível mudança de estado de espírito"
"Nós agora pode construir uma máquina para fazer o trabalho deste computador."

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

"A função é dito ser 'efetivamente 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, não deixa de ser desejável ter alguns, definição expressible matemática mais definida ... [ele discute a história da definição muito bonito, tal como apresentado acima em relação a Gödel, Herbrand, Kleene, Church, Turing, e Post]... Podemos tomar essa afirmação literalmente, entendendo por um processo puramente mecânico, que poderia ser realizada por uma máquina. é possível dar uma descrição matemática, de certa forma normal, das estruturas destas máquinas. o desenvolvimento dessas idéias leva a definição do autor de uma função computável, e uma identificação de † computability com calculabilidade eficaz....
"† Usaremos a expressão 'função computável' para significar uma função calculável por uma máquina, e nós vamos 'efetivamente calculável' referem-se a idéia intuitiva, sem especial, a identificação com qualquer uma dessas definições".

JB Rosser (1939) e SC Kleene (1943)

J. Barkley Rosser definido um 'método eficaz [matemática]' da seguinte maneira (itálico adicionado):

" 'Método eficaz' é usado aqui no sentido bastante especial de um método cada passo 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 dadas a data [sua nota # 5; veja a discussão imediatamente abaixo]. a mais simples delas para estado (devido ao Post e Turing) diz essencialmente que. um método eficaz de resolução de certos conjuntos de problemas existe se se pode construir uma máquina que irá então resolver qualquer problema do conjunto sem intervenção humana para além de inserir a questão e (mais tarde) lendo a 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)

Nota de rodapé de Rosser No. 5 referências o trabalho de (1) Church e Kleene e sua definição de λ-definibilidade, no uso particular da Igreja de que em seu um problema insolúvel da teoria dos números elementar (1936); (2) Herbrand e Gödel e seu uso de recursão em uso particular de Gödel em seu famoso papel no Formalmente indecidíveis Proposições de Principia Mathematica e sistemas relacionados I (1931); e (3) Pós (1936) e Turing (1936-1937) nos seus 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 contexto seguinte (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" para a pergunta, "é o valor 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 relacionadas, em particular, fundamentos da matemática (especialmente a tese de Church-Turing ) e filosofia da mente (especialmente argumentos sobre inteligência artificial ). Para mais, veja caracterizações Algorithm .

Veja também

Notas

Bibliografia

  • Axt, P (1959). "Em um Subrecursive Hierarquia e Graus primitiva recursiva". Transações da American Mathematical Society . 92 : 85-105. doi : 10,2307 / 1993169 . JSTOR  1.993.169 .
  • Bell, C. Gordon e Newell, Allen (1971), Estruturas de computador: Leituras e Exemplos , McGraw-Hill Book Company, Nova Iorque. ISBN  0-07-004357-4 .
  • Blass, Andreas ; Gurevich, Yuri (2003). "Algoritmos: A Quest for definições absolutas" (PDF) . Boletim da Associação Europeia para a Ciência da Computação Teórica . 81 . Inclui uma excelente bibliografia de 56 referências.
  • Peneira, David J. (1984). Homem de Turing: Cultura ocidental na era do computador (1984 ed.). A University of North Carolina Press, Chapel Hill NC. ISBN  0-8078-1564-0 ., ISBN  0-8078-4108-0 pbk.
  • Boolos, George ; Jeffrey, Richard (1999) [1974]. Computability e lógica (4a ed.). Cambridge University Press, Londres. ISBN  0-521-20402-X .: Cf. Capítulo 3 máquinas de Turing , onde discutem "certos conjuntos enumeráveis não efetivamente (mecanicamente) enumeráveis".
  • Burgin, Mark (2004). Algoritmos Super-recursiva . Springer. ISBN  978-0-387-95569-8 .
  • Campagnolo, ML, Moore, C. , e Costa, JF (2000) Uma caracterização analógico das funções subrecursive. Em Proc. da 4ª Conferência sobre números e computadores reais , Universidade de Odense, pp. 91-109
  • Igreja, Alonzo (1936a). "Um problema insolúvel da teoria dos números elementar". O American Journal of Mathematics . 58 (2): 345-363. doi : 10,2307 / 2371045 . JSTOR  2.371.045 .Reproduzido na A Indecidíveis , p. 89ff. A primeira expressão de "Tese da Igreja". Ver, em particular a página 100 ( A Indecidíveis ), onde ele define a noção de "calculabilidade eficaz" em termos de "um algoritmo", e ele usa a palavra "termina", etc.
  • Igreja, Alonzo (1936b). "Uma nota sobre o Entscheidungsproblem". O Journal of Lógica simbólica . 1 (1): 40-41. doi : 10,2307 / 2269326 . JSTOR  2.269.326 .Igreja, Alonzo (1936). "Correção de uma nota no Entscheidungsproblem". O Journal of Lógica simbólica . 1 (3): 101-102. doi : 10,2307 / 2269030 . JSTOR  2.269.030 .Reproduzido na A Indecidíveis , p. 110ff. Igreja mostra que a Entscheidungsproblem é insolúvel em cerca de 3 páginas de texto e 3 páginas de notas de rodapé.
  • Daffa', Ali Abdullah al-(1977). A contribuição muçulmana para a matemática . Londres: Croom Helm. ISBN  0-85664-464-1 .
  • Davis, Martin (1965). O Indecidíveis: Papéis básicas sobre indecidíveis Proposições, problemas insolúveis e funções computáveis . New York: Raven Press. ISBN  0-486-43228-9 .Davis dá o comentário antes de cada artigo. Papéis de Gödel , Alonzo Church , Turing , Rosser , Kleene , e Emil Publicar estão incluídas; aqueles citados no artigo são listados aqui pelo nome do autor.
  • Davis, Martin (2000). Motores de Logic: Matemáticos e a Origem do computador . New York: WW Nortion. ISBN  0-393-32229-7 .Davis oferece biografias concisas de Leibniz , Boole , Frege , Cantor , Hilbert , Gödel e Turing com von Neumann como o vilão de roubo show. Muito breves biografias de Joseph-Marie Jacquard , Babbage , Ada Lovelace , Claude Shannon , Howard Aiken , etc.
  •  Este artigo incorpora material em domínio público  do  NIST documento:  preto, Paul E. "algoritmo" . Dicionário de Algoritmos e Estruturas de Dados .
  • Dean, Tim (2012). "Evolução e diversidade moral". Baltic Internacional Yearbook of Cognition, Lógica e Comunicação . 7 .
  • Dennett, Daniel (1995). Perigosa idéia de Darwin . New York: Touchstone / Simon & Schuster. ISBN  0-684-80290-2 .
  • Dilson, Jesse (2007). O ábaco ((1968,1994) ed.). Imprensa do St. Martin, NY. ISBN  0-312-10409-X ., ISBN  0-312-10409-X (PBK).
  • Yuri Gurevich , seqüenciais abstratos State Machines captura seqüencial Algoritmos , ACM Transactions em Computational Logic, Vol 1, No 1 (Julho de 2000), páginas 77-111. Inclui bibliografia de 33 fontes.
  • van Heijenoort, Jean (2001). De Frege de Gödel, um livro de origem em Lógica Matemática, 1879-1931 ((1967) ed.). Harvard University Press, Cambridge, MA. ISBN  0-674-32449-8 ., 3ª edição de 1976 [?], ISBN  0-674-32449-8 (pbk).
  • Hodges, Andrew (1983). Alan Turing: The Enigma . New York: Simon and Schuster . ISBN  0-671-49207-1 ., ISBN  0-671-49207-1 . Cf. Capítulo "O Espírito da Verdade" para uma história que leva a, e uma discussão sobre, sua prova.
  • Kleene, Stephen C. (1936). "Funções Gerais recursiva dos números naturais" . Mathematische Annalen . 112 (5): 727-742. doi : 10,1007 / BF01565439 .Apresentado ao American Mathematical Society, em setembro de 1935. Reproduzido em The Indecidíveis , p. 237ff. Definição de "recursão geral" (conhecido agora como mu-recursão) de Kleene foi utilizado pela Igreja em seu trabalho de 1935 um problema insolúvel da teoria dos números elementar que provou o "problema de decisão" para ser "indecidível" (ie, um resultado negativo).
  • Kleene, Stephen C. (1943). "Recursiva Predicados e quantificadores". Transações da Sociedade Matemática americanos . 54 (1): 41-73. doi : 10,2307 / 1990131 . JSTOR  1.990.131 .Reproduzido na A Indecidíveis , p. 255ff. Kleene refinou sua definição de "recursão geral" e prosseguiu em seu capítulo "teorias 12. Algorithmic" postular "Tese I" (p 274.); ele viria a repetir essa tese (em Kleene 1952: 300) e nomeá-la "Tese da Igreja" (Kleene 1952: 317) (ou seja, a tese de Church ).
  • Kleene, Stephen C. (1991) [1952]. Introdução ao metamatemática (ed décimo.). North-Holland Publishing Company. ISBN  0-7204-2103-9 . Excelente acessíveis, fonte legível-referência para "fundações" matemáticos.
  • Knuth, Donald (1997). Algoritmos Fundamentais, terceira edição . Reading, Massachusetts: Addison-Wesley. ISBN  0-201-89683-4 .
  • Knuth, Donald (1969). Volume 2 / Seminumerical Algoritmos, The Art of Computer Programming Primeira Edição . Reading, Massachusetts: Addison-Wesley.
  • Kosovsky, NK Elements of Mathematical Logic e sua aplicação à teoria da Subrecursive Algoritmos , LSU Publ., Leningrado de 1981
  • Kowalski, Robert (1979). "Algoritmo = + Lógica de Controlo". Comunicações da ACM . 22 (7): 424-436. doi : 10,1145 / 359.131,359136 .
  • AA Markov (1954) Teoria de algoritmos . [Traduzido por Jacques J. Schorr-Kon e equipe PST] Imprint Moscou, da Academia de Ciências da URSS de 1954 [ou seja, Jerusalém, Israel Programa de tradução científica, 1961; disponível a partir do Escritório de Serviços Técnicos, US Dept. of Commerce, Washington] Descrição 444 p. 28 cm. Tp Adicionado em Russo Tradução de Obras do Instituto de Matemática da Academia de Ciências da URSS, v 42. Título original:. Teoriya algerifmov. [Biblioteca QA248.M2943 Dartmouth College. EUA Departamento de Comércio, Escritório de Serviços Técnicos, número OTS 60-51085.]
  • Minsky, Marvin (1967). Computação: Máquinas finito e o infinito (Primeira ed.). Prentice-Hall, Englewood Cliffs, NJ. ISBN  0-13-165449-7 .Minsky expande sua "... idéia de um algoritmo de um procedimento eficaz ..." no capítulo 5.1 Computability, procedimentos eficazes e Algoritmos. Máquinas infinito.
  • Post, Emil (1936). "Processos combinatória finitos, formulação I". O Journal of Lógica simbólica . 1 (3): 103-105. doi : 10,2307 / 2269031 . JSTOR  2.269.031 .Reproduzido na A Indecidíveis , p. 289ff. Pós define um processo algorítmico-like simples de um homem a escrever marcas ou apagando marcas e indo de caixa em caixa e eventualmente travar, como ele segue uma lista de instruções simples. Esta é citado por Kleene como uma fonte de sua "Tese I", a chamada tese de Church-Turing .
  • Rogers, Jr, Hartley (1987). Teoria das Funções Recursivas e eficaz Computability . O MIT Press. ISBN  0-262-68052-1 .
  • Rosser, JB (1939). "Uma Exposição Informal da prova de teorema de Gödel e Teorema da Igreja". Journal of Symbolic Logic . 4 (2): 53-60. doi : 10,2307 / 2269059 . JSTOR  2.269.059 .Reproduzido na A Indecidíveis , p. 223ff. Nisto é famosa definição de "método eficaz" de Rosser:" ... um método cada passo que é precisamente predeterminado e que é certo para produzir a resposta em um número finito de passos ... uma máquina que irá resolver qualquer problema de o conjunto sem intervenção humana para além de inserir a questão e (mais tarde) lendo a resposta"(p. 225-226, o Indecidíveis )
  • Santos-Lang, Christopher (2014). "Ecologia Moral Abordagens para a Ética Machine". Em van Rysewyk, Simon; Pontier, Matthijs. Máquina de Ética Médica (PDF) . Suíça: Springer. pp. 111-127. doi : 10,1007 / 978-3-319-08108-3_8 .
  • Scott, Michael L. (2009). Programação Pragmática Língua (3ª ed.). Morgan Kaufmann Publishers / Elsevier. ISBN  978-0-12-374514-9 .
  • Sipser, Michael (2006). Introdução à Teoria da Computação . PWS Publishing Company. ISBN  0-534-94728-X .
  • Sóbrio, Elliott; Wilson, David Sloan (1998). Unto Others: A Evolução e Psicologia do Comportamento altruísta . Cambridge: Harvard University Press.
  • Pedra, Harold S. (1972). Introdução à Organização de Computadores e Estruturas de Dados (1972 ed.). McGraw-Hill, New York. ISBN  0-07-061726-0 .Cf. nomeadamente o primeiro capítulo intitulado: Algoritmos, Turing Machines, e programas . Sua sucinta definição informal: "... qualquer sequência de instruções que podem ser obedecidas por um robô, é chamado um algoritmo " (p. 4).
  • Tausworthe, Robert C (1977). Desenvolvimento padronizado de Software de Computador Parte 1 Métodos . Englewood Cliffs NJ: Prentice-Hall, Inc. ISBN  0-13-842195-1 .
  • Rees, Alan M. (1936-1937). "Em números computáveis, com um aplicativo para o Entscheidungsproblem". Anais da Sociedade Matemática de Londres . Série 2. 42 : 230-265. doi : 10,1112 / MPM / s2-42.1.230 .. Correções, ibid, vol. 43 (1937) pp. 544-546. Reproduzido na A Indecidíveis , p. 116ff. Famoso artigo de Turing concluída como uma dissertação de mestrado, enquanto no Kings College Cambridge UK.
  • Rees, Alan M. (1939). "Sistemas de lógica baseada em ordinais". Anais da Sociedade Matemática de Londres . 45 : 161-228. doi : 10,1112 / MPM / s2-45.1.161 .Reproduzido na A Indecidíveis , p. 155ff. O trabalho de Turing que definiu "o oráculo", foi sua tese de doutoramento, enquanto em Princeton EUA.
  • United States Patent and Trademark Office (2006), 2.106,02 **> Matemática Algoritmos: 2100 patenteabilidade , Manual of Patent Examinando Procedimento (MPEP). Revisão mais recente agosto 2006

Outras leituras

links externos

repositórios algoritmo
notas de aula