Algoritmo -Algorithm
Em matemática e ciência da computação , um algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ( escute ) ) é uma sequência finita de instruções rigorosas , normalmente usadas para resolver uma classe de problemas específicos ou para realizar uma computação . Algoritmos são usados como especificações para realizar cálculos e processamento de dados . Algoritmos mais avançados podem realizar deduções automatizadas (conhecidas como raciocínio automatizado ) e usar testes matemáticos e lógicos para desviar a execução do código por várias rotas (conhecidas como tomada de decisão automatizada ). Usar características humanas como descritores de máquinas de forma metafórica já era praticado por Alan Turing com termos como "memória", "busca" e "estímulo".
Em contraste, uma heurística é uma abordagem para a resolução de problemas que pode não ser totalmente especificada ou pode não garantir resultados corretos ou ótimos, especialmente em domínios de problemas onde não há um resultado correto ou ótimo bem definido.
Como um método eficaz , um algoritmo pode ser expresso em uma quantidade finita de espaço e tempo e em uma linguagem formal bem definida para calcular uma função . Partindo de um estado inicial e de uma entrada inicial (talvez vazia ), as instruções descrevem uma computação que, quando executada , passa por um número finito de estados sucessivos bem definidos, eventualmente produzindo "saída" e terminando em um estado final final. A transição de um estado para o próximo não é necessariamente determinística ; alguns algoritmos, conhecidos como algoritmos aleatórios , incorporam entrada aleatória.
História
O conceito de algoritmos existe desde a antiguidade. Algoritmos aritméticos , como um algoritmo de divisão , foram usados por antigos matemáticos da Babilônia c. 2500 aC e matemáticos egípcios c. 1550 aC. Mais tarde, os matemáticos gregos usaram algoritmos em 240 aC na peneira de Eratóstenes para encontrar números primos e o algoritmo euclidiano para encontrar o máximo divisor comum de dois números. Matemáticos árabes , como al-Kindi , no século IX, usaram algoritmos criptográficos para decifrar códigos , com base na análise de frequência .
A palavra algoritmo é derivada do nome do matemático persa do século IX Muhammad ibn Musa al-Khwarizmi . Al-Khwarizmi foi um matemático, astrônomo , geógrafo e estudioso da Casa da Sabedoria em Bagdá , cujo nome significa "o nativo de Khwarazm ", região que fazia parte do Grande Irã e hoje faz parte do Uzbequistão . Por volta do ano 825, al-Khwarizmi escreveu um tratado em árabe sobre o sistema de numeração hindu-árabe , que foi traduzido para o latim durante o século XII. O manuscrito começa com a frase Dixit Algorizmi ("Assim falou Al-Khwarizmi"), onde "Algorizmi" era a latinização feita pelo tradutor do nome de Al-Khwarizmi. Al-Khwarizmi foi o matemático mais lido na Europa no final da Idade Média, principalmente por meio de outro de seus livros, a Álgebra . No latim medieval tardio, algorismus , inglês " algorismo ", a corrupção de seu nome, significava o " sistema de numeração decimal ". No século XV, sob a influência da palavra grega ἀριθμός ( arithmos ), "número" ( cf. "aritmética"), a palavra latina foi alterada para algoritmo , e o termo inglês correspondente "algoritmo" é atestado pela primeira vez no século XVII século; o sentido moderno foi introduzido no século XIX.
A matemática indiana era predominantemente algorítmica. Algoritmos que são representativos da tradição matemática indiana vão desde os antigos Śulbasūtrās até os textos medievais da Escola de Kerala .
Em inglês, a palavra algoritmo foi usada pela primeira vez por volta de 1230 e depois por Chaucer em 1391. O inglês adotou o termo francês, mas foi somente no final do século 19 que "algoritmo" assumiu o significado que tem no inglês moderno.
Outro uso antigo da palavra é de 1240, em um manual intitulado Carmen de Algorismo composto por Alexandre de Villedieu . Começa com:
Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.
que se traduz em:
Algorismo é a arte pela qual atualmente usamos essas figuras indianas, que numeram duas vezes cinco.
O poema tem algumas centenas de linhas e resume a arte de calcular com o novo estilo de dados indianos ( Tali Indorum ), ou numerais hindus.
Uma formalização parcial do conceito moderno de algoritmo começou com tentativas de resolver o Entscheidungsproblem (problema de decisão) proposto por David Hilbert em 1928. As formalizações posteriores foram enquadradas como tentativas de definir " calculabilidade efetiva " ou "método efetivo". Essas formalizações incluíam as funções recursivas de Gödel – Herbrand – Kleene de 1930, 1934 e 1935, o cálculo lambda de Alonzo Church de 1936, a Formulação 1 de Emil Post de 1936 e as máquinas de Turing de Alan Turing de 1936–37 e 1939.
Definição informal
Uma definição informal poderia ser "um conjunto de regras que define com precisão uma sequência de operações", que incluiria todos os programas de computador (incluindo programas que não realizam cálculos numéricos) e (por exemplo) qualquer procedimento burocrático prescrito ou receita de livro de receitas .
Em geral, um programa só é um algoritmo se parar eventualmente - mesmo que loops infinitos possam às vezes ser desejáveis.
Um exemplo prototípico de um algoritmo é o algoritmo euclidiano , que é usado para determinar o máximo divisor comum de dois inteiros; um exemplo (existem outros) é descrito no fluxograma acima e como exemplo em uma seção posterior.
Boolos, Jeffrey & 1974, 1999 oferecem um significado informal da palavra "algoritmo" na seguinte citação:
Nenhum ser humano pode escrever rápido o suficiente, ou longo o suficiente, ou pequeno o suficiente† (†"menor e menor sem limite ... você estaria tentando escrever em moléculas, em átomos, em elétrons") para listar todos os membros de um conjunto enumeravelmente infinito escrevendo seus nomes, um após o outro, em alguma notação. Mas os humanos podem fazer algo igualmente útil, no caso de certos conjuntos infinitos enumeráveis: eles podem dar instruções explícitas para determinar o enésimo membro do conjunto , para n finito arbitrário . Tais instruções devem ser dadas de forma bastante explícita, de forma que possam ser seguidas por uma máquina de computação ou por um ser humano capaz de realizar apenas operações muito elementares sobre símbolos.
Um "conjunto enumeravelmente infinito" é aquele cujos elementos podem ser colocados em correspondência um-a-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 de saída a partir de um inteiro arbitrário de "entrada" ou inteiros que, em teoria, podem ser arbitrariamente grandes. Por exemplo, um algoritmo pode ser uma equação algébrica como y = m + n (ou seja, duas "variáveis de entrada" arbitrárias m e n que produzem uma saída y ), mas várias tentativas de autores para definir a noção indicam que a palavra implica muito mais que isso, algo da ordem de (para o exemplo de adição):
- Instruções precisas (em uma linguagem entendida pelo "computador") para um processo rápido, eficiente e "bom" que especifica os "movimentos" do "computador" (máquina ou humano, equipado com as informações e capacidades contidas internamente necessárias) para encontre, decodifique e, em seguida, processe inteiros/símbolos de entrada arbitrários m e n , símbolos + e = ... e produza "efetivamente", em um tempo "razoável", inteiro de saída y em um local especificado e em um formato especificado.
O conceito de algoritmo também é usado para definir a noção de decidibilidade - uma noção que é central para explicar como os sistemas formais surgem a partir de um pequeno conjunto de axiomas e regras. Na lógica , o tempo que um algoritmo leva para ser concluído não pode ser medido, pois aparentemente não está relacionado à dimensão física habitual. Dessas incertezas, que caracterizam o trabalho em andamento, decorre a indisponibilidade de uma definição de algoritmo que se adapte tanto ao uso concreto (em algum sentido) quanto ao uso abstrato do termo.
A maioria dos algoritmos destina-se a ser implementada como programas de computador . No entanto, os algoritmos também são implementados por outros meios, como em uma rede neural biológica (por exemplo, o cérebro humano implementando aritmética ou um inseto procurando comida), em um circuito elétrico ou em um dispositivo mecânico.
Formalização
Algoritmos são essenciais para a maneira como os computadores processam dados. Muitos programas de computador contêm algoritmos que detalham as instruções específicas que um computador deve executar - em uma ordem específica - para realizar uma tarefa específica, como calcular o contracheque dos funcionários ou imprimir os boletins dos alunos. Assim, um algoritmo pode ser considerado qualquer sequência de operações que pode ser simulada por um sistema Turing-completo . Autores que afirmam esta tese incluem Minsky (1967), Savage (1987) e Gurevich (2000):
Minsky: "Mas também sustentaremos, com Turing... que qualquer procedimento que poderia ser chamado "naturalmente" de eficaz pode, de fato, ser realizado por uma máquina (simples). Embora isso possa parecer extremo, os argumentos... . a seu favor são difíceis de refutar". Gurevich: "... o argumento informal de Turing em favor de sua tese justifica uma tese mais forte: todo 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".
Máquinas de Turing podem definir processos computacionais que não terminam. As definições informais de algoritmos geralmente requerem que o algoritmo sempre termine. Esse requisito torna a tarefa de decidir se um procedimento formal é um algoritmo impossível no caso geral – devido a um importante teorema da teoria da computabilidade conhecido como problema da parada .
Normalmente, quando um algoritmo está associado ao processamento de informações, os dados podem ser lidos de uma fonte de entrada, gravados em um dispositivo de saída e armazenados para processamento posterior. Os dados armazenados são considerados como parte do estado interno da entidade que executa o algoritmo. Na prática, o estado é armazenado em uma ou mais estruturas de dados .
Para alguns desses processos computacionais, o algoritmo deve ser rigorosamente definido: e especificado na forma como se aplica em todas as circunstâncias possíveis que possam surgir. Isso significa que quaisquer etapas condicionais devem ser tratadas sistematicamente, caso a caso; os critérios para cada caso devem ser claros (e calculáveis).
Como um algoritmo é uma lista precisa de etapas precisas, a ordem da computação é sempre crucial para o funcionamento do algoritmo. Normalmente, supõe-se que as instruções sejam listadas explicitamente e são descritas como começando "do topo" e indo "para baixo" - uma ideia que é descrita mais formalmente por fluxo de controle .
Até agora, a discussão sobre a formalização de um algoritmo assumiu as premissas da programação imperativa . Esta é a concepção mais comum - aquela que tenta descrever uma tarefa em meios "mecânicos" discretos. Exclusivo para essa concepção de algoritmos formalizados é a operação de atribuição , que define o valor de uma variável. Deriva da intuição da " memória " como um bloco de rascunhos. Um exemplo de tal atribuição pode ser encontrado abaixo.
Para algumas concepções alternativas do que constitui um algoritmo, consulte programação funcional e programação lógica .
Expressando algoritmos
Algoritmos podem ser expressos em muitos tipos de notação, incluindo linguagens naturais , pseudocódigo , fluxogramas , gráficos drakon , linguagens de programação ou tabelas de controle (processadas por interpretadores ). Expressões de linguagem natural de algoritmos tendem a ser detalhadas e ambíguas e raramente são usadas para algoritmos complexos ou técnicos. Pseudocódigo, fluxogramas, gráficos de drakon e tabelas de controle são formas estruturadas de expressar algoritmos que evitam muitas das ambiguidades comuns nas declarações baseadas em linguagem natural. As linguagens de programação destinam-se principalmente a expressar algoritmos em uma forma que pode ser executada por um computador, mas também são frequentemente usadas como uma maneira de definir ou documentar algoritmos.
Existe uma grande variedade de representações possíveis e pode-se expressar um determinado programa de máquina de Turing como uma sequência de tabelas de máquina (consulte máquina de estado finito , tabela de transição de estado e tabela de controle para obter mais informações), como fluxogramas e gráficos de drakon (consulte diagrama de estado para saber mais), ou como uma forma de código de máquina rudimentar ou código de montagem chamado "conjuntos de quádruplos" (consulte Máquina de Turing para saber mais).
As representações de algoritmos podem ser classificadas em três níveis aceitos de descrição da máquina de Turing, como segue:
- 1 descrição de alto nível
- "...prosa para descrever um algoritmo, ignorando os detalhes de implementação. Nesse nível, não precisamos mencionar como a máquina gerencia sua fita ou cabeçote."
- 2 Descrição da implementação
- "...prosa usada para definir a forma como a máquina de Turing usa sua cabeça e a forma como ela armazena dados em sua fita. Nesse nível, não fornecemos detalhes de estados ou funções de transição."
- 3 Descrição formal
- O mais detalhado, "nível mais baixo", fornece a "tabela de estado" da máquina de Turing.
Para obter um exemplo do algoritmo simples "Adicionar m+n" descrito em todos os três níveis, consulte Exemplos .
Projeto
O projeto de algoritmo refere-se a um método ou processo matemático para resolução de problemas e algoritmos de engenharia. O design de algoritmos faz parte de muitas teorias de solução, como divisão e conquista ou programação dinâmica dentro da pesquisa operacional . As técnicas para projetar e implementar designs de algoritmos também são chamadas de padrões de design de algoritmos, com exemplos incluindo o padrão de método de modelo e o padrão de decorador.
Um dos aspectos mais importantes do projeto de algoritmo é a eficiência de recursos (tempo de execução, uso de memória); a notação O grande é usada para descrever, por exemplo, o crescimento do tempo de execução de um algoritmo à medida que o tamanho de sua entrada aumenta.
Etapas típicas no desenvolvimento de algoritmos:
- Definição de problema
- Desenvolvimento de um modelo
- Especificação do algoritmo
- Projetando um algoritmo
- Verificando a exatidão do algoritmo
- Análise do algoritmo
- Implementação do algoritmo
- Teste do programa
- preparação de documentação
Algoritmos de computador
Programas "elegantes" (compactos), programas "bons" (rápidos) : A noção de "simplicidade e elegância" aparece informalmente em Knuth e precisamente em Chaitin :
- Knuth: "... queremos bons algoritmos em algum sentido estético vagamente definido. Um critério... é o tempo necessário para executar o algoritmo... Outros critérios são a adaptabilidade do algoritmo a computadores, sua simplicidade e elegância, etc."
- Chaitin: "... um programa é 'elegante', com o que quero dizer que é o menor programa possível para produzir a saída que ele faz"
Chaitin prefacia sua definição com: "Vou mostrar que você não pode provar que um programa é 'elegante ' "—tal prova resolveria o problema da parada (ibid).
Algoritmo versus função computável por um algoritmo : Para uma determinada função podem existir vários algoritmos. Isso é verdade, mesmo sem expandir o conjunto de instruções disponível para o programador. Rogers observa que "É... importante distinguir entre a noção de algoritmo , ou seja, procedimento, e a noção de função computável por algoritmo , ou seja, mapeamento produzido por procedimento. A mesma função pode ter vários algoritmos diferentes".
Infelizmente, pode haver uma troca entre qualidade (velocidade) e elegância (compacidade) - um programa elegante pode levar mais passos para completar uma computação do que um menos elegante. Um exemplo que usa o algoritmo de Euclides aparece abaixo.
Computadores (e computors), modelos de computação : Um computador (ou "computador" humano) é um tipo restrito de máquina, um "dispositivo mecânico determinístico discreto" que segue cegamente suas instruções. Os modelos primitivos de Melzak e Lambek reduziram essa noção a quatro elementos: (i) localizações discretas e distinguíveis, (ii) contadores discretos e indistinguíveis (iii) um agente e (iv) uma lista de instruções que são efetivas em relação à capacidade do agente.
Minsky descreve uma variação mais agradável do modelo "ábaco" de Lambek em seu "Very Simple Bases for Computability ". A máquina de Minsky prossegue sequencialmente através de suas cinco (ou seis, dependendo de como se conta) instruções, a menos que um IF-THEN GOTO condicional ou um GOTO incondicional altere o fluxo do programa fora da sequência. Além de HALT, a máquina de Minsky inclui três operações de atribuição (substituição, substituição): ZERO (por exemplo, o conteúdo do local substituído por 0: L ← 0), SUCCESSOR (por exemplo, L ← L+1) e DECREMENT (por exemplo, L ← L − 1 ). Raramente um programador deve escrever "código" com um conjunto de instruções tão limitado. Mas Minsky mostra (assim como Melzak e Lambek) que sua máquina é Turing completa com apenas quatro tipos gerais de instruções: GOTO condicional, GOTO incondicional, atribuição/substituição/substituição e HALT. No entanto, algumas instruções de atribuição diferentes (por exemplo, DECREMENT, INCREMENT e ZERO/CLEAR/EMPTY para uma máquina Minsky) também são necessárias para Turing-completeness; sua especificação exata depende um pouco do designer. O GOTO incondicional é conveniente; pode ser construído inicializando um local dedicado a zero, por exemplo, a instrução "Z ← 0"; depois disso, a instrução IF Z=0 THEN GOTO xxx é incondicional.
Simulação de um algoritmo: linguagem de computador (computador) : Knuth aconselha o leitor que "a melhor maneira de aprender um algoritmo é experimentá-lo... imediatamente pegue papel e caneta e trabalhe com um exemplo". Mas e quanto a uma simulação ou execução da coisa real? O programador deve traduzir o algoritmo para uma linguagem que o simulador/computador/computador possa efetivamente executar. Stone dá um exemplo disso: ao calcular as raízes de uma equação quadrática, o computador deve saber como tirar uma raiz quadrada. Caso contrário, o algoritmo, para ser eficaz, deve fornecer um conjunto de regras para extrair uma raiz quadrada.
Isso significa que o programador deve conhecer uma "linguagem" que seja eficaz em relação ao agente de computação de destino (computador/computador).
Mas qual modelo deve ser usado para a simulação? Van Emde Boas observa que "mesmo que baseemos a teoria da complexidade em máquinas abstratas em vez de máquinas concretas, a arbitrariedade da escolha de um modelo permanece. É neste ponto que entra a noção de simulação ". Quando a velocidade está sendo medida, o conjunto de instruções é importante. Por exemplo, o subprograma no algoritmo de Euclides para calcular o resto seria executado muito mais rápido se o programador tivesse uma instrução " módulo " disponível em vez de apenas subtração (ou pior: apenas o "decremento" de Minsky).
Programação estruturada, estruturas canônicas : De acordo com a tese de Church-Turing , qualquer algoritmo pode ser calculado por um modelo conhecido por ser Turing completo e, de acordo com as demonstrações de Minsky, Turing completo requer apenas quatro tipos de instrução - GOTO condicional, GOTO incondicional, atribuição, HALT. Kemeny e Kurtz observam que, embora o uso "indisciplinado" de GOTOs incondicionais e IF-THEN GOTOs condicionais possa resultar em " código espaguete ", um programador pode escrever programas estruturados usando apenas essas instruções; por outro lado "também é possível, e não muito difícil, escrever programas mal estruturados em uma linguagem estruturada". Tausworthe aumenta as três estruturas canônicas de Böhm-Jacopini : SEQUENCE, IF-THEN-ELSE e WHILE-DO, com mais duas: 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 fluxogramas canônicos : O auxílio gráfico chamado fluxograma oferece uma maneira de descrever e documentar um algoritmo (e um programa de computador correspondente a ele). Como o fluxo do programa de uma máquina Minsky, um fluxograma sempre começa no topo de uma página e segue para baixo. Seus símbolos principais são apenas quatro: a seta direcionada mostrando o fluxo do programa, o retângulo (SEQUENCE, GOTO), o losango (IF-THEN-ELSE) e o ponto (OR-tie). As estruturas canônicas de Böhm-Jacopini são feitas dessas formas primitivas. As subestruturas podem "aninhar-se" em retângulos, mas apenas se ocorrer uma única saída da superestrutura. Os símbolos e seu uso para construir as estruturas canônicas são mostrados no diagrama.
Exemplos
Exemplo de algoritmo
Um dos algoritmos mais simples é encontrar o maior número em uma lista de números de ordem aleatória. Encontrar a solução requer olhar para cada número na lista. A partir disso, segue um algoritmo simples, que pode ser declarado em uma descrição de alto nível em prosa em inglês, como:
Descrição de alto nível:
- Se não houver números no conjunto, não haverá número mais alto.
- Suponha que o primeiro número do conjunto seja o maior número do conjunto.
- Para cada número restante no conjunto: se esse número for maior que o maior número atual, considere esse número como o maior número do conjunto.
- Quando não houver números restantes no conjunto para iterar, considere o maior número atual como o maior número do conjunto.
Descrição (quase)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 largest ← L[0] for each item in L, do if item > largest, then largest ← item return largest
- "←" denota atribuição . Por exemplo, " maior ← item " significa que o valor do maior muda para o valor do item .
- " return " encerra o algoritmo e gera o seguinte valor.
algoritmo de euclides
Em matemática , o algoritmo de Euclides , ou algoritmo de Euclides , é um método eficiente para calcular o máximo divisor comum (GCD) de dois inteiros (números), o maior número que os divide sem deixar resto . É nomeado após o antigo matemático grego Euclides , que primeiro o descreveu em seus Elementos ( c. 300 aC ). É um dos algoritmos mais antigos de uso comum. Ele pode ser usado para reduzir frações à sua forma mais simples e faz parte de muitos outros cálculos numéricos e criptográficos.
Euclides coloca o problema assim: "Dados dois números não primos entre si, encontrar sua maior medida comum". Ele define "Um número [para ser] uma multidão composta de unidades": um número de contagem, um inteiro positivo que não inclui zero. "Medir" é colocar um comprimento de medição s mais curto sucessivamente ( q vezes) ao longo do comprimento l até que a porção restante r seja menor que o comprimento s mais curto . Em palavras modernas, resto r = l − q × s , sendo q o quociente, ou resto r é o "módulo", a parte inteira-fracionária que sobra após a divisão.
Para que o método de Euclides seja bem-sucedido, os comprimentos iniciais devem satisfazer dois requisitos: (i) os comprimentos não devem ser zero, E (ii) a subtração deve ser "adequada"; ou seja, um teste deve garantir que o menor dos dois números seja subtraído do maior (ou os dois podem ser iguais, de modo que sua subtração produza zero).
A prova original de Euclides acrescenta um terceiro requisito: os dois comprimentos não devem ser primos um do outro. Euclides estipulou isso para que pudesse construir uma prova reductio ad absurdum de que a medida comum dos dois números é de fato a maior . Embora o algoritmo de Nicômaco seja o mesmo de Euclides, quando os números são primos entre si, ele produz o número "1" para sua medida comum. Então, para ser preciso, o seguinte é realmente o algoritmo de Nicômaco.
Linguagem de computador para o algoritmo de Euclides
Apenas alguns tipos de instrução são necessários para executar o algoritmo de Euclides - alguns testes lógicos (GOTO condicional), GOTO incondicional, atribuição (substituição) e subtração.
- Um local é simbolizado por letras maiúsculas, por exemplo, S, A, etc.
- A quantidade variável (número) em um local é escrita em letras minúsculas e (geralmente) associada ao nome do local. Por exemplo, a localização L no início pode conter o número l = 3009.
Um programa deselegante para o algoritmo de Euclides
O algoritmo a seguir é enquadrado como a versão de quatro etapas de Knuth de Euclides e Nicômaco, mas, em vez de usar a divisão para encontrar o restante, ele usa subtrações sucessivas do comprimento mais curto s do comprimento restante r até que r seja menor que s . A descrição de alto nível, mostrada em negrito, é adaptada 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-se de que r ≥ s .]
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 7 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 r em R seja menor que o comprimento menor s em S, subtraia repetidamente o número de medição s em S 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: [O resto é zero?] : OU (i) a última medida foi exata, o resto em R é zero e o programa pode parar, OU (ii) o algoritmo deve continuar: a última medida deixou um resto em R menor que o número de medição em S.
10 IF R = 0 THEN done so GOTO step 15 ELSE CONTINUE TO step 11,
E3: [Interchange s e r ] : A noz do algoritmo de Euclides. Use o resto r para medir o que antes era um número s menor ; 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 a seguir do algoritmo de Euclides requer apenas seis instruções principais para fazer o que treze são exigidos por "Deselegante"; pior, "Deselegante" requer mais tipos de instruções. O fluxograma de "Elegant" pode ser encontrado no início deste artigo. Na linguagem Basic (não estruturada), as etapas são numeradas e a 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
Como funciona "Elegant" : No lugar de um "loop de Euclides" externo, "Elegant" alterna entre dois "co-loops", um loop A > B que calcula A ← A − B e um loop B ≤ A que calcula B ← B − A. Isso funciona porque, quando finalmente o minuendo M for menor ou igual ao subtraendo S (Diferença = Minuendo − Subtraendo), o minuendo pode se tornar s (o novo comprimento medido) e o subtraendo pode torne-se o novo r (o comprimento a ser medido); em outras palavras, o "sentido" da subtração se inverte.
A seguinte versão pode ser usada com linguagens de programação da família C :
// Euclid's algorithm for greatest common divisor
int euclidAlgorithm (int A, int B) {
A = abs(A);
B = abs(B);
while (B != 0) {
while (A > B) {
A = A-B;
}
B = B-A;
}
return A;
}
Testando os algoritmos de Euclides
Um algoritmo faz o que seu autor quer que ele faça? Alguns casos de teste geralmente fornecem alguma confiança na funcionalidade principal. Mas os testes não são suficientes. Para casos de teste, uma fonte usa 3009 e 884. Knuth sugeriu 40902, 24140. Outro caso interessante são os dois números relativamente primos 14157 e 5950.
Mas "casos excepcionais" devem ser identificados e testados. "Deselegante" funcionará corretamente quando R > S, S > R, R = S? O mesmo vale para "Elegante": 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 para sempre em todos os casos; "Elegante" calcula para sempre quando A = 0.) O que acontece se números negativos forem inseridos? Números fracionários? Se os números de entrada, ou seja, o domínio da função computada pelo algoritmo/programa, devem incluir apenas inteiros positivos incluindo zero, então as falhas em zero indicam que o algoritmo (e o programa que o instancia ) é uma função parcial em vez de uma função total . Uma falha notável devido a exceções é a falha do foguete Ariane 5 Flight 501 (4 de junho de 1996).
Prova da exatidão do programa pelo uso de indução matemática : Knuth demonstra a aplicação da indução matemática a uma versão "estendida" do algoritmo de Euclides e propõe "um método geral aplicável para provar a validade de qualquer algoritmo". Tausworthe propõe que uma medida da complexidade de um programa seja o comprimento de sua prova de correção.
Medindo e melhorando os algoritmos de Euclides
Elegância (compacidade) versus bondade (velocidade) : Com apenas seis instruções principais, "Elegant" é o vencedor claro, em comparação com "Deselegant" com treze instruções. Porém, "Deselegante" é mais rápido (chega ao HALT em menos passos). A análise do algoritmo indica por que esse é o caso: "Elegante" faz dois testes condicionais em cada loop de subtração, enquanto "Deselegante" faz apenas um. Como o algoritmo (normalmente) requer muitos loop-throughs, em média muito tempo é desperdiçado fazendo um "B = 0?" teste que é necessário somente após o cálculo do restante.
Os algoritmos podem ser melhorados? : Uma vez que o programador julga um programa "adequado" e "eficaz" - isto é, ele calcula a função pretendida por seu autor - então a questão é: ele pode ser melhorado?
A compacidade de "Deselegante" pode ser melhorada pela eliminação de cinco etapas. Mas Chaitin provou que compactar um algoritmo não pode ser automatizado por um algoritmo generalizado; em vez disso, só pode ser feito heuristicamente ; ou seja, por busca exaustiva (exemplos encontrados em Busy beaver ), tentativa e erro, esperteza, insight, aplicação de raciocínio indutivo , etc. Observe que os passos 4, 5 e 6 são repetidos nos passos 11, 12 e 13. Comparação com "Elegant" fornece uma dica de que essas etapas, juntamente com as etapas 2 e 3, podem ser eliminadas. Isso reduz o número de instruções principais de treze para oito, o que o torna "mais elegante" do que "elegante", com nove etapas.
A velocidade de "Elegant" pode ser melhorada movendo o "B=0?" teste fora dos dois loops de subtração. Essa alteração exige a adição de três instruções (B = 0?, A = 0?, GOTO). Agora "Elegant" calcula os números de exemplo mais rapidamente; se este é sempre o caso para qualquer dado A, B e R, S exigiria uma análise detalhada.
Análise algorítmica
Freqüentemente, é importante saber quanto de um determinado recurso (como tempo ou armazenamento) é teoricamente necessário para um determinado algoritmo. Foram desenvolvidos métodos de análise de algoritmos para obtenção dessas respostas quantitativas (estimativas); por exemplo, um algoritmo que soma os elementos de uma lista de n números teria um requisito de tempo de O(n) , usando a notação big O . Em todos os momentos, o algoritmo só precisa se lembrar de dois valores: a soma de todos os elementos até o momento e sua posição atual na lista de entrada. Portanto, diz-se que ele tem um requisito de espaço de O(1) , se o espaço necessário para armazenar os números de entrada não for contado, ou O(n) se for contado.
Diferentes algoritmos podem concluir 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, um algoritmo de pesquisa binária (com custo O(log n) ) supera uma pesquisa sequencial (custo O(n) ) quando usado para pesquisas de tabela em listas ou matrizes classificadas.
Formal versus empírico
A análise e o estudo de algoritmos é uma disciplina da ciência da computação e geralmente é praticada de forma abstrata, sem o uso de uma linguagem de programação ou implementação específica. Nesse sentido, a análise de algoritmos se assemelha a outras disciplinas matemáticas, pois se concentra nas propriedades subjacentes do algoritmo e não nas especificidades de qualquer implementação específica. Normalmente , o pseudocódigo é usado para análise, pois é a representação mais simples e geral. No entanto, em última análise, a maioria dos algoritmos geralmente é implementada em plataformas de hardware/software específicas e sua eficiência algorítmica é eventualmente testada usando código real. Para a solução de um problema "único", a eficiência de um algoritmo específico pode não ter consequências significativas (a menos que n seja extremamente grande), mas para algoritmos projetados para uso científico interativo, comercial ou de longa duração, pode ser crítico. Escalar de n pequeno para n grande frequentemente expõe algoritmos ineficientes que, de outra forma, são benignos.
O teste empírico é útil porque pode revelar interações inesperadas que afetam o desempenho. Benchmarks podem ser usados para comparar antes/depois de melhorias potenciais para um algoritmo após a otimização do programa. Porém, os testes empíricos não podem substituir a análise formal e não são triviais para serem executados de maneira justa.
Eficiência de execução
Para ilustrar as possíveis melhorias possíveis mesmo em algoritmos bem estabelecidos, uma recente inovação significativa, relacionada aos algoritmos FFT (muito usados no campo de processamento de imagens), pode diminuir o tempo de processamento em 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. Acelerações dessa magnitude permitem que dispositivos de computação que fazem uso extensivo de processamento de imagem (como câmeras digitais e equipamentos médicos) consumam menos energia.
Classificação
Existem várias maneiras de classificar algoritmos, cada uma com seus próprios méritos.
Por implementação
Uma maneira de classificar algoritmos é por meios de implementação.
int gcd(int A, int B) {
if (B == 0)
return A;
else if (A > B)
return gcd(A-B,B);
else
return gcd(A,B-A);
}
|
Implementação C recursiva do algoritmo de Euclides do fluxograma acima |
- Recursão
- Um algoritmo recursivo é aquele que invoca (faz referência a) a si mesmo repetidamente até que uma certa condição (também conhecida como condição de término) corresponda, que é um método comum à programação funcional . Algoritmos iterativos usam construções repetitivas como loops e, às vezes, estruturas de dados adicionais, como pilhas , para resolver os problemas fornecidos. Alguns problemas são naturalmente adequados para uma implementação ou outra. Por exemplo, as torres de Hanoi são bem compreendidas usando implementação recursiva. Cada versão recursiva tem uma versão iterativa equivalente (mas possivelmente mais ou menos complexa) e vice-versa.
- Lógico
- Um algoritmo pode ser visto como uma dedução lógica controlada . Esta noção pode ser expressa como: Algoritmo = lógica + controle . A componente lógica expressa os axiomas que podem ser usados na computação e a componente de controle determina a forma como a dedução é aplicada aos axiomas. Esta é a base para o paradigma de programação lógica . Em linguagens de programação lógica pura, o componente de controle é fixo e os algoritmos são especificados fornecendo apenas o componente lógico. O apelo dessa abordagem é a semântica elegante : uma mudança nos axiomas produz uma mudança bem definida no algoritmo.
- Serial, paralelo ou distribuído
- Os algoritmos geralmente são discutidos com a suposição de que os computadores executam uma instrução de um algoritmo por vez. Esses computadores às vezes são chamados de computadores seriais. Um algoritmo projetado para tal ambiente é chamado de algoritmo serial, em oposição a algoritmos paralelos ou algoritmos distribuídos . Algoritmos paralelos tiram proveito de arquiteturas de computador onde vários processadores podem trabalhar em um problema ao mesmo tempo, enquanto algoritmos distribuídos usam várias máquinas conectadas a uma rede de computadores . Algoritmos paralelos ou distribuídos dividem o problema em subproblemas mais simétricos ou assimétricos e reúnem os resultados novamente. 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 classificação podem ser paralelizados com eficiência, mas sua sobrecarga de comunicação é cara. Algoritmos iterativos são geralmente paralelizáveis. Alguns problemas não possuem algoritmos paralelos e são chamados de problemas inerentemente seriais.
- Determinístico ou não determinístico
- Os algoritmos determinísticos resolvem o problema com decisões exatas em cada etapa do algoritmo, enquanto os algoritmos não determinísticos resolvem problemas por meio de suposições, embora as suposições típicas sejam mais precisas por meio do uso de heurísticas .
- Exato ou aproximado
- Enquanto muitos algoritmos chegam a uma solução exata, os algoritmos de aproximação buscam uma aproximação mais próxima da verdadeira solução. A aproximação pode ser alcançada usando uma estratégia determinística ou aleatória. Tais algoritmos têm valor prático para muitos problemas difíceis. Um dos exemplos de algoritmo aproximado é o problema da mochila , onde há um conjunto de itens dados. Seu objetivo é arrumar a mochila para obter o valor total máximo. Cada item tem algum peso e algum valor. O peso total que pode ser carregado não passa de um número fixo X. Portanto, a solução deve considerar os pesos dos itens, bem como seu valor.
- algoritmo quântico
- Eles rodam em um modelo realista de computação quântica . O termo é geralmente usado para aqueles algoritmos que parecem inerentemente quânticos, ou usam algum recurso essencial da computação quântica , como superposição quântica ou emaranhamento quântico .
Por paradigma de design
Outra maneira de classificar algoritmos é por sua metodologia de design ou paradigma . Existe um certo número de paradigmas, cada um diferente do outro. Além disso, cada uma dessas categorias inclui muitos tipos diferentes de algoritmos. Alguns paradigmas comuns são:
- Força bruta ou busca exaustiva
- Este é o método ingênuo de tentar todas as soluções possíveis para ver qual é a melhor.
- Dividir e conquistar
- Um algoritmo de divisão e conquista reduz repetidamente uma instância de um problema a uma ou mais instâncias menores do mesmo problema (geralmente recursivamente ) até que as instâncias sejam pequenas o suficiente para serem resolvidas facilmente. Um desses exemplos de divisão e conquista é a classificação por mesclagem . A classificação pode ser feita em cada segmento de dados depois de dividir os dados em segmentos e a classificação de dados inteiros pode ser obtida na fase de conquista, mesclando os segmentos. Uma variante mais simples de dividir e conquistar é chamada de algoritmo de diminuir e conquistar , que resolve um subproblema idêntico e usa a solução desse subproblema para resolver o problema maior. Dividir e conquistar divide o problema em vários subproblemas e, portanto, o estágio de conquista é mais complexo do que diminuir e conquistar algoritmos. Um exemplo de algoritmo de diminuição e conquista é o algoritmo de busca binária .
- Pesquisa e enumeração
- Muitos problemas (como jogar xadrez ) podem ser modelados como problemas em gráficos . Um algoritmo de exploração de grafos especifica regras para movimentação em um grafo e é útil para tais problemas. Esta categoria também inclui algoritmos de busca , enumeração de ramificação e limite e retrocesso .
- Algoritmo aleatório
- Tais algoritmos fazem algumas escolhas aleatoriamente (ou pseudo-aleatoriamente). Eles podem ser muito úteis para encontrar 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ápidas devem envolver alguma aleatoriedade . Se algoritmos aleatórios com complexidade de tempo polinomial podem ser os algoritmos mais rápidos para alguns problemas é uma questão em aberto conhecida como problema P versus NP . Existem duas grandes classes de tais algoritmos:
- Os algoritmos de Monte Carlo retornam uma resposta correta com alta probabilidade. Ex : RP é a subclasse dessas que rodam em tempo polinomial .
- Os algoritmos de Las Vegas sempre retornam a resposta correta, mas seu tempo de execução é limitado apenas probabilisticamente, por exemplo, ZPP .
- Redução da complexidade
- Essa técnica envolve resolver um problema difícil, transformando-o em um problema mais conhecido para o qual temos (esperamos) algoritmos assintoticamente ótimos . O objetivo é encontrar um algoritmo redutor cuja complexidade não seja dominada pelos algoritmos reduzidos resultantes. Por exemplo, um algoritmo de seleção para encontrar a mediana em uma lista não classificada envolve primeiro classificar a lista (a parte cara) e, em seguida, retirar o elemento do meio da lista classificada (a parte barata). Essa 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 abandonadas quando é determinado que elas não podem levar a uma solução completa válida.
Problemas de otimização
Para problemas de otimização existe uma classificação mais específica de algoritmos; um algoritmo para tais problemas pode cair em uma ou mais das categorias gerais descritas acima, bem como em uma das seguintes:
- Programação linear
- Ao procurar soluções ótimas para uma função linear vinculada a restrições de igualdade e desigualdade lineares, as restrições do problema podem ser usadas diretamente na produção de soluções ótimas. Existem algoritmos que podem resolver qualquer problema nesta categoria, como o popular algoritmo simplex . Problemas que podem ser resolvidos com programação linear incluem o problema de fluxo máximo para grafos direcionados. Se um problema exigir adicionalmente que uma ou mais das incógnitas deva ser um número inteiro , ele será classificado em programação inteira . Um algoritmo de programação linear pode resolver tal problema se puder provar que todas as restrições para valores inteiros são superficiais, ou seja, as soluções satisfazem essas restrições de qualquer maneira. No caso geral, utiliza-se um algoritmo especializado ou um algoritmo que encontra soluções aproximadas, dependendo da dificuldade do problema.
- Programaçao dinamica
- Quando um problema mostra subestruturas ótimas – o que significa que a solução ótima para um problema pode ser construída a partir de soluções ótimas para subproblemas – e subproblemas sobrepostos , o que significa que os mesmos subproblemas são usados para resolver muitas instâncias de problemas diferentes, uma abordagem mais rápida chamada programação dinâmica evita a recomputação de soluções que já foram computados. Por exemplo, algoritmo Floyd-Warshall , o caminho mais curto para um objetivo de um vértice em um grafo ponderado pode ser encontrado usando o caminho mais curto para o objetivo de todos os vértices adjacentes. A programação dinâmica e a memoização andam juntas. A principal diferença entre programação dinâmica e dividir e conquistar é que os subproblemas são mais ou menos independentes em dividir e conquistar, enquanto os subproblemas se sobrepõem na programação dinâmica. A diferença entre programação dinâmica e recursão direta está no cache ou na memoização de chamadas recursivas. Quando os subproblemas são independentes e não há repetição, a memoização não ajuda; portanto, a programação dinâmica não é uma solução para todos os problemas complexos. Usando memoização ou mantendo uma tabela de subproblemas já resolvidos, a programação dinâmica reduz a natureza exponencial de muitos problemas à complexidade polinomial.
- O método ganancioso
- Um algoritmo guloso é semelhante a um algoritmo de programação dinâmica, pois funciona examinando subestruturas, neste caso não do problema, mas de uma determinada solução. Tais algoritmos começam com alguma solução, que pode ser dada ou construída de alguma forma, e a aprimoram fazendo pequenas modificações. Para alguns problemas eles podem encontrar a solução ótima enquanto para outros eles param em ótimos locais , ou seja, em soluções que não podem ser melhoradas pelo algoritmo, mas não são ótimas. O uso mais popular de algoritmos gulosos é para encontrar a árvore geradora mínima onde encontrar a solução ótima é possível com esse método. Huffman Tree , Kruskal , Prim , Sollin são algoritmos gananciosos que podem resolver esse problema de otimização.
- O método heurístico
- Em problemas de otimização , algoritmos heurísticos podem ser usados para encontrar uma solução próxima da solução ótima em casos onde encontrar a solução ótima é impraticável. Esses algoritmos funcionam aproximando-se cada vez mais da solução ideal à medida que progridem. Em princípio, se rodar por um tempo infinito, eles encontrarão a solução ótima. 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 busca local , busca tabu , recozimento simulado e algoritmos genéticos . Alguns deles, como o recozimento simulado, são algoritmos não determinísticos, enquanto outros, como a pesquisa tabu, são determinísticos. Quando um limite no erro da solução não ótima é conhecido, o algoritmo é classificado como um algoritmo de aproximação .
Por campo 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 estudados em conjunto. Algumas classes de exemplo são algoritmos de busca, algoritmos de classificação, algoritmos de mesclagem , algoritmos numéricos, algoritmos de gráfico, algoritmos de string, algoritmos geométricos computacionais , algoritmos combinatórios , algoritmos médicos , aprendizado de máquina , criptografia , algoritmos de compressão de dados e técnicas de análise .
Os campos tendem a se sobrepor uns aos outros, e os avanços do algoritmo em um campo podem melhorar os de outros campos, às vezes completamente não relacionados. Por exemplo, a programação dinâmica foi inventada para otimizar o consumo de recursos na indústria, mas agora é usada para resolver uma ampla gama de problemas em muitos campos.
Por complexidade
Os algoritmos podem ser classificados pela quantidade de tempo que precisam para serem concluídos em comparação com o tamanho da entrada:
- Tempo constante: se o tempo necessário para o algoritmo for o mesmo, independentemente do tamanho da entrada. Por exemplo, um acesso a um elemento de array .
- Tempo logarítmico: se o tempo for uma função logarítmica do tamanho da entrada. Por exemplo , algoritmo de pesquisa binária .
- Tempo linear: se o tempo for proporcional ao tamanho da entrada. Por exemplo, o percurso de uma lista.
- Tempo polinomial: se o tempo for uma potência do tamanho da entrada. Por exemplo, o algoritmo de classificação de bolhas tem complexidade de tempo quadrática.
- Tempo exponencial: se o tempo for uma função exponencial do tamanho da entrada. Por exemplo , pesquisa de força bruta .
Alguns problemas podem ter vários algoritmos de complexidade diferente, enquanto outros problemas podem não ter algoritmos ou nenhum algoritmo eficiente conhecido. Há também mapeamentos de alguns problemas para outros problemas. Devido a isso, verificou-se ser mais adequado 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 operando em dados que representam quantidades contínuas, mesmo que esses dados sejam representados 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 nos 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 que consiste apenas em manipulações simples de conceitos abstratos, números ou sinais não constitui "processos" (USPTO 2006) e, portanto, os algoritmos não são patenteáveis (como em Gottschalk v. Benson ). No entanto, aplicações práticas de algoritmos às vezes são patenteáveis. Por exemplo, em Diamond v. Diehr , a aplicação de um algoritmo de feedback simples para auxiliar na cura de borracha sintética foi considerada patenteável. O patenteamento de software é altamente controverso, e há patentes altamente criticadas envolvendo algoritmos, especialmente algoritmos de compressão de dados , como a patente LZW da Unisys .
Além disso, alguns algoritmos criptográficos têm restrições de exportação (consulte exportação de criptografia ).
História: Desenvolvimento da noção de "algoritmo"
Antigo Oriente Próximo
A evidência mais antiga de algoritmos é encontrada na matemática babilônica da antiga Mesopotâmia (atual Iraque). Uma tábua de argila suméria encontrada em Shuruppak perto de Bagdá e datada de cerca de 2500 aC descreveu o algoritmo de divisão mais antigo . Durante a dinastia Hammurabi, por volta de 1800-1600 aC, as tabuletas de argila da Babilônia descreviam algoritmos para calcular fórmulas . Algoritmos também foram usados na astronomia babilônica . As tabuletas de argila babilônicas descrevem e empregam procedimentos algorítmicos para calcular a hora e o local de eventos astronômicos significativos.
Algoritmos para aritmética também são encontrados na matemática egípcia antiga , datando do Papiro Matemático de Rhind por volta de 1550 aC. Algoritmos foram usados mais tarde na antiga matemática helenística . Dois exemplos são o Crivo de Eratóstenes , que foi descrito na Introdução à Aritmética por Nicômaco , e o algoritmo de Euclides , que foi descrito pela primeira vez nos Elementos de Euclides ( c. 300 aC ).
Símbolos discretos e distinguíveis
Marcas de contagem: Para manter o controle de seus rebanhos, seus sacos de grãos e seu dinheiro, os antigos usavam a contagem: acumulando pedras ou marcas riscadas em varas ou fazendo símbolos discretos em argila. Através do uso babilônico e egípcio de marcas e símbolos, eventualmente os numerais romanos e o ábaco evoluíram (Dilson, p. 16–41). As marcas de registro aparecem proeminentemente na aritmética do sistema numeral unário usada na máquina de Turing e nos cálculos da máquina Post–Turing .
Manipulação de símbolos como "espaços reservados" para números: álgebra
Muhammad ibn Mūsā al-Khwārizmī , um matemático persa , escreveu o Al-jabr no século IX. Os termos " algoritmo " e "algoritmo" são derivados do nome al-Khwārizmī, enquanto o termo " álgebra " é derivado do livro Al-jabr . Na Europa, a palavra "algoritmo" foi originalmente usada para se referir aos conjuntos de regras e técnicas usadas por Al-Khwarizmi para resolver equações algébricas, antes de ser posteriormente generalizada para se referir a qualquer conjunto de regras ou técnicas. Isso finalmente culminou na noção de Leibniz do calculus ratiocinator ( c. 1680 ):
Um bom século e meio à frente de seu tempo, Leibniz propôs uma álgebra da lógica, uma álgebra que especificaria as regras para a manipulação de conceitos lógicos da mesma forma que a álgebra comum especifica as regras para a manipulação de números.
Algoritmos criptográficos
O primeiro algoritmo criptográfico para decifrar o código criptografado foi desenvolvido por Al-Kindi , um matemático árabe do século IX , em A Manuscript On Deciphering Cryptographic Messages . Ele deu a primeira descrição da criptoanálise por análise de frequência , o primeiro algoritmo de quebra de código.
Dispositivos mecânicos com estados discretos
O relógio : Bolter credita a invenção do relógio movido a peso como "A principal invenção [da Europa na Idade Média]", em particular, o escape de borda que nos fornece o tique-taque de um relógio mecânico. "A máquina automática precisa" levou imediatamente aos " autômatos mecânicos " começando no século 13 e, finalmente, às "máquinas computacionais" - o mecanismo de diferença e os mecanismos analíticos de Charles Babbage e da Condessa Ada Lovelace , em meados do século 19. Lovelace é creditado com a primeira criação de um algoritmo destinado a ser processado em um computador - o mecanismo analítico de Babbage, o primeiro dispositivo considerado um verdadeiro computador completo de Turing em vez de apenas uma calculadora - e às vezes é chamado de "o primeiro programador da história" como resultado, embora uma implementação completa do segundo dispositivo de Babbage não fosse realizada até décadas depois de sua vida.
Máquinas lógicas 1870 - "ábaco lógico" e "máquina lógica" de Stanley Jevons : O problema técnico era reduzir as equações booleanas quando apresentadas de uma forma semelhante ao que hoje é conhecido como mapas de Karnaugh . Jevons (1880) descreve primeiro um "ábaco" simples de "pedaços de madeira providos de alfinetes, planejados de modo que qualquer parte ou classe das combinações [lógicas] possa ser selecionada mecanicamente... sistema a uma forma completamente mecânica, e assim incorporaram todo o processo indireto de inferência no que pode ser chamado de Máquina Lógica " Sua máquina veio equipada com "certas hastes móveis de madeira" e "ao pé estão 21 chaves 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 ele exibiu em 1870 perante os membros da Royal Society. Outro lógico John Venn , no entanto, em sua Lógica Simbólica de 1881 , olhou com desconfiança para este esforço: "Eu não tenho uma estimativa elevada do interesse ou importância do que às vezes são chamados de máquinas lógicas... não me parece que quaisquer artifícios atualmente conhecidos ou prováveis de serem descobertos realmente merecem o nome de máquinas lógicas”; veja mais em Caracterizações do Algoritmo . Mas, para não ficar atrás, ele também apresentou "um plano um tanto análogo, eu apreendo, ao ábaco do Prof. Jevon ... [E] [um] ganho, correspondendo à máquina lógica do Prof. Jevons, o seguinte artifício pode ser descrito. chamá-la meramente de máquina de diagramas lógicos...
Tear Jacquard, cartões perfurados Hollerith, telegrafia e telefonia - o relé eletromecânico : Bell e Newell (1971) indicam que o tear Jacquard (1801), precursor dos cartões Hollerith (cartões perfurados, 1887) e "tecnologias de comutação telefônica" foram as raízes de uma árvore que levou ao desenvolvimento dos primeiros computadores. Em meados do século 19, o telégrafo , o precursor do telefone, estava em uso em todo o mundo, sua codificação discreta e distinguível de letras como "pontos e traços" um som comum. No final do século 19, a fita adesiva ( c. 1870 ) estava em uso, assim como o uso de cartões Hollerith no censo dos Estados Unidos de 1890. Então veio o teleimpressor ( c. 1910 ) com seu uso de papel perfurado do código Baudot na fita.
As redes de comutação telefônica de relés eletromecânicos (inventadas em 1835) estavam por trás do trabalho de George Stibitz (1937), o inventor do dispositivo de adição digital. Enquanto trabalhava nos Laboratórios Bell, ele observou o uso "pesado" de calculadoras mecânicas com engrenagens. "Ele foi para casa uma noite em 1937 com a intenção de testar sua ideia... Quando o conserto acabou, Stibitz havia construído um dispositivo de adição binária" .
O matemático Martin Davis observa a particular importância do relé eletromecânico (com seus dois "estados binários" aberto e fechado ):
- Foi somente com o desenvolvimento, a partir da década de 1930, de calculadoras eletromecânicas usando relés elétricos, que as máquinas foram construídas com o escopo que Babbage havia imaginado."
Matemática durante o século 19 até meados do século 20
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 a aritmética a uma sequência de símbolos manipulados por regras. Os princípios da aritmética de Peano , apresentados por um novo método (1888) foi "a primeira tentativa de axiomatização da matemática em uma linguagem simbólica ".
Mas Heijenoort dá a Frege (1879) este elogio: Frege é "talvez a mais importante obra individual já escrita em lógica ... , "para o pensamento puro", isto é, livre de embelezamentos retóricos ... construídos a partir de símbolos específicos que são manipulados de acordo com regras definidas". O trabalho de Frege foi ainda mais simplificado e ampliado por Alfred North Whitehead e Bertrand Russell em seu Principia Mathematica (1910-1913).
Os paradoxos : Ao mesmo tempo, vários paradoxos perturbadores apareceram na literatura, em particular, o paradoxo de Burali-Forti (1897), o paradoxo de Russell (1902–03) e o paradoxo de Richard . As considerações resultantes levaram ao artigo de Kurt Gödel (1931) - ele cita especificamente o paradoxo do mentiroso - que reduz completamente as regras de recursão a números.
Calculabilidade efetiva : Em um esforço para resolver o Entscheidungsproblem definido precisamente por Hilbert em 1928, os matemáticos começaram a definir o que significava um “método efetivo” ou “cálculo efetivo” ou “calculabilidade efetiva” (ou seja, um cálculo que teria sucesso ). Em rápida sucessão, apareceram os seguintes: Alonzo Church , Stephen Kleene e JB Rosser 's λ-calculus uma definição refinada de "recursão geral" do trabalho de Gödel agindo sobre sugestões de Jacques Herbrand (cf. as palestras de Gödel em Princeton de 1934) e simplificações subseqüentes por Kleene. A prova de Church de que o Entscheidungsproblem era insolúvel, a definição de Emil Post de calculabilidade efetiva como um trabalhador que segue sem pensar uma lista de instruções para se mover para a esquerda ou para a direita através de uma sequência de quartos e, enquanto lá, marca ou apaga um papel ou observa o papel e faz uma decisão sim-não sobre a próxima instrução. A prova de Alan Turing de que o Entscheidungsproblem era insolúvel pelo uso de sua "máquina [automática]" — com efeito quase idêntico à "formulação" de Post, a definição de J. Barkley Rosser de "método eficaz" em termos de "uma máquina". A proposta de Kleene de um precursor da " Tese da Igreja " que ele chamou de "Tese I", e alguns anos depois Kleene renomeou sua Tese como "Tese da Igreja" e propôs a "Tese de Turing".
Emil Post (1936) e Alan Turing (1936–37, 1939)
Emil Post (1936) descreveu as ações de um "computador" (ser humano) da seguinte forma:
- "...dois conceitos estão envolvidos: o de um espaço simbólico no qual o trabalho que leva do problema à resposta deve ser realizado, e um conjunto fixo e inalterável de direções .
Seu espaço de símbolo seria
- "uma sequência infinita bidirecional de espaços ou caixas... O solucionador de problemas ou trabalhador deve se mover e trabalhar neste espaço simbólico, sendo capaz de estar e operar em apenas uma caixa por vez... uma caixa é admitir apenas duas condições possíveis, ou seja, estar vazio ou não marcado e ter uma única marca, digamos, um traço vertical.
- "Uma caixa deve ser destacada e chamada de ponto de partida. ...um problema específico deve ser dado em forma simbólica por um número finito de caixas [ie, INPUT] marcadas com um traço. Da mesma forma, a resposta [ie , OUTPUT] deve ser dado em forma simbólica por tal configuração de caixas marcadas...
- "Um conjunto de direções aplicáveis a um problema geral configura um processo determinístico quando aplicado a cada problema específico. Esse processo termina apenas quando se trata da direção do tipo (C ) [ou seja, STOP]". Veja mais em Post–Turing machine
A obra de Alan Turing precedeu a de Stibitz (1937); não se sabe se Stibitz conhecia o trabalho de Turing. O biógrafo de Turing acreditava que o uso de Turing de um modelo parecido com uma máquina de escrever derivava de um interesse juvenil: "Alan sonhava em inventar máquinas de escrever quando menino; a Sra. Turing tinha uma máquina de escrever e ele poderia muito bem ter começado se perguntando o que significava chamar uma máquina de escrever 'mecânica ' ". Dada a prevalência na época do código Morse, telegrafia, máquinas de fita adesiva e teletipos, é bem possível que todos tenham influenciado Turing durante sua juventude.
Turing - seu modelo de computação agora é chamado de máquina de Turing - começa, assim como Post, com uma análise de um computador humano que ele reduz a um conjunto simples de movimentos básicos e "estados da mente". Mas ele dá um passo adiante e cria uma máquina como modelo de cálculo de números.
- "A computação é normalmente feita escrevendo-se certos símbolos no papel. Podemos supor que este papel é dividido em quadrados como um livro de aritmética infantil... Presumo então que a computação é realizada em papel unidimensional, ou seja, em uma fita dividida em quadrados. Suponho também que o número de símbolos que podem ser impressos é finito...
- "O comportamento do computador em qualquer momento é determinado pelos símbolos que ele está observando e seu "estado de espírito" naquele momento. Podemos supor que existe 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. Também vamos supor que o número de estados mentais que precisam ser levados em conta é finito...
- "Vamos imaginar que as operações realizadas pelo computador sejam divididas em 'operações simples' que são tão elementares que não é fácil imaginá-las ainda divididas."
A redução de Turing produz o seguinte:
- "As operações simples devem, portanto, incluir:
- "(a) Alterações do símbolo em um dos quadrados observados
- "(b) Mudanças de um dos quadrados observados para outro quadrado dentro de L quadrados de um dos quadrados observados anteriormente.
"Pode ser que algumas dessas mudanças invoquem necessariamente uma mudança de estado de espírito. A operação única mais geral deve, portanto, ser considerada uma das seguintes:
- "(A) Uma possível mudança (a) de símbolo juntamente com uma possível mudança de estado de espírito.
- "(B) Uma possível mudança (b) de quadrados observados, juntamente com uma possível mudança de estado de espírito"
- "Agora podemos construir uma máquina para fazer o trabalho deste computador."
Alguns anos depois, Turing expandiu sua análise (tese, definição) com esta expressão contundente dela:
- "Diz-se que uma função é 'efetivamente calculável' se seus valores podem ser encontrados por algum processo puramente mecânico. Embora seja bastante fácil obter uma compreensão intuitiva dessa ideia, é desejável ter alguma definição matemática mais definida e expressável. ... [ele discute a história da definição praticamente como apresentada acima em relação a Gödel, Herbrand, Kleene, Church, Turing e Post] ... Podemos tomar esta afirmação literalmente, entendendo por um processo puramente mecânico um que poderia ser realizado por uma máquina. É possível dar uma descrição matemática, em uma certa forma normal, das estruturas dessas máquinas. O desenvolvimento dessas idéias leva à definição do autor de uma função computável e à identificação de computabilidade † com calculabilidade efetiva...
- "† Usaremos a expressão "função computável" para significar uma função calculável por uma máquina, e deixaremos "efetivamente calculável" referir-se à ideia intuitiva sem identificação particular com qualquer uma dessas definições".
JB Rosser (1939) e SC Kleene (1943)
J. Barkley Rosser definiu um "método [matemático] eficaz" da seguinte maneira (itálico adicionado):
- " 'Método eficaz' é usado aqui no sentido bastante especial de um método em que cada etapa é determinada com precisão e que certamente produzirá a resposta em um número finito de etapas. Com esse significado especial, três definições precisas diferentes foram dadas até o momento. [sua nota de rodapé nº 5; veja a discussão imediatamente abaixo]. O mais simples deles para declarar (devido a Post e Turing) diz essencialmente que existe um método eficaz de resolver certos conjuntos de problemas se alguém puder construir uma máquina que, então, resolva qualquer problema do conjunto sem intervenção humana além de inserir a pergunta e (posteriormente) ler a resposta . Todas as três definições são equivalentes, portanto, não importa qual é usada. Além disso, o fato de todas as três serem equivalentes é um argumento muito forte para a correção de qualquer um." (Rosser 1939: 225–226)
A nota de rodapé nº 5 de Rosser faz referência ao trabalho de (1) Church e Kleene e sua definição de λ-definibilidade, em particular, o uso que Church faz dela em seu An Unsolvable Problem of Elementary Number Theory (1936); (2) Herbrand e Gödel e seu uso de recursão, em particular, o uso de Gödel em seu famoso artigo On Formally Undecidable Propositions of Principia Mathematica and Related Systems I (1931); e (3) Post (1936) e Turing (1936-37) em seus modelos de mecanismo de computação.
Stephen C. Kleene definiu como sua agora famosa "Tese I", conhecida como a tese de Church-Turing . Mas ele fez isso no seguinte contexto (em negrito no original):
- "12. Teorias algorítmicas ... Ao estabelecer uma teoria algorítmica completa, o que fazemos é descrever um procedimento, executável para cada conjunto de valores das variáveis independentes, cujo procedimento termina necessariamente e de tal maneira que, a partir do resultado, podemos leia uma resposta definitiva, "sim" ou "não", para a pergunta "o valor do predicado é verdadeiro?" (Kleene 1943:273)
História depois de 1950
Vários esforços foram direcionados para um maior refinamento da definição de "algoritmo", e a atividade está em andamento por causa de questões que envolvem, em particular, os fundamentos da matemática (especialmente a tese de Church-Turing ) e filosofia da mente (especialmente argumentos sobre inteligência artificial ). Para obter mais informações, consulte Caracterizações de algoritmo .
Veja também
- máquina abstrata
- Engenharia de algoritmo
- caracterizações do algoritmo
- viés algorítmico
- Composição algorítmica
- entidades algorítmicas
- Síntese algorítmica
- técnica algorítmica
- Topologia algorítmica
- Lixo entra, lixo sai
- Introdução aos Algoritmos (livro didático)
- Governo por algoritmo
- Lista de algoritmos
- Lista de tópicos gerais de algoritmo
- Lista de publicações importantes em ciência da computação teórica – Algoritmos
- Regulação de algoritmos
- teoria da computação
- matemática computacional
Notas
Bibliografia
- Axt, P (1959). "Em uma hierarquia subrecursiva e graus recursivos primitivos" . Transações da American Mathematical Society . 92 (1): 85–105. doi : 10.2307/1993169 . JSTOR 1993169 .
- Bell, C. Gordon e Newell, Allen (1971), Estruturas de computador: leituras e exemplos , McGraw–Hill Book Company, Nova York. ISBN 0-07-004357-4 .
- Blass, Andreas ; Gurevich, Yuri (2003). "Algoritmos: uma busca por definições absolutas" (PDF) . Boletim da Associação Européia de Ciência da Computação Teórica . 81 . Arquivado (PDF) do original em 9 de outubro de 2022.Inclui uma excelente bibliografia de 56 referências.
- Bolter, David J. (1984). O Homem de Turing: Cultura Ocidental na Era do Computador (1984 ed.). Chapel Hill, NC: The University of North Carolina Press. ISBN 978-0-8078-1564-9., ISBN 0-8078-4108-0
- Boolos, George ; Jeffrey, Richard (1999) [1974]. Computabilidade e Lógica (4ª ed.). Cambridge University Press, Londres. ISBN 978-0-521-20402-6.: cf. Capítulo 3 Máquinas de Turing onde eles discutem "certos conjuntos enumeráveis não efetivamente (mecanicamente) enumeráveis".
- Burgin, Mark (2004). Algoritmos Super-Recursivos . Springer. ISBN 978-0-387-95569-8.
- Campagnolo, ML, Moore, C. , e Costa, JF (2000) Uma caracterização analógica das funções subrecursivas. Em Proc. da 4ª Conferência sobre Números Reais e Computadores , Universidade de Odense, pp. 91–109
- Igreja, Alonzo (1936). "Um problema insolúvel da teoria elementar dos números". O jornal americano da matemática . 58 (2): 345–363. doi : 10.2307/2371045 . JSTOR 2371045 .Reimpresso em O Indecidível , p. 89ss. A primeira expressão da "Tese da Igreja". Veja em particular a página 100 ( The Undecidable ) onde ele define a noção de "calculabilidade efetiva" em termos de "um algoritmo", e ele usa a palavra "termina", etc.
- Igreja, Alonzo (1936). "Uma nota sobre o Entscheidungsproblem". O Jornal da Lógica Simbólica . 1 (1): 40–41. doi : 10.2307/2269326 . JSTOR 2269326 . S2CID 42323521 . Igreja, Alonzo (1936). "Correção de uma nota sobre o Entscheidungsproblem". O Jornal da Lógica Simbólica . 1 (3): 101–102. doi : 10.2307/2269030 . JSTOR 2269030 . S2CID 5557237 .Reimpresso em O Indecidível , p. 110ss. Church mostra que o 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 978-0-85664-464-1.
- Davis, Martin (1965). O indecidível: artigos básicos sobre proposições indecidíveis, problemas insolúveis e funções computáveis . Nova York: Raven Press. ISBN 978-0-486-43228-1.Davis faz comentários antes de cada artigo. Documentos de Gödel , Alonzo Church , Turing , Rosser , Kleene e Emil Post estão incluídos; aqueles citados no artigo são listados aqui pelo nome do autor.
- Davis, Martin (2000). Máquinas de Lógica: Matemáticos e a Origem do Computador . Nova York: WW Nortion. ISBN 978-0-393-32229-3.Davis oferece biografias concisas de Leibniz , Boole , Frege , Cantor , Hilbert , Gödel e Turing com von Neumann como o vilão que roubou o show. Breves biografias de Joseph-Marie Jacquard , Babbage , Ada Lovelace , Claude Shannon , Howard Aiken , etc.
- Este artigo incorpora material de domínio público de Paul E. Black. "algoritmo" . Dicionário de Algoritmos e Estruturas de Dados . NIST .
- Dean, Tim (2012). "Evolução e diversidade moral" . Baltic International Yearbook of Cognition, Logic and Communication . 7 . doi : 10.4148/biyclc.v7i0.1775 .
- Dennett, Daniel (1995). A Perigosa Idéia de Darwin . Complexidade . Vol. 2. Nova York: Touchstone/Simon & Schuster. pp. 32-36 . Código Bib : 1996Cmplx ...2a..32M . doi : 10.1002/(SICI)1099-0526(199609/10)2:1<32::AID-CPLX8>3.0.CO;2-H . ISBN 978-0-684-80290-9.
- Dilson, Jesse (2007). O Ábaco ((1968, 1994) ed.). St. Martin's Press, NY. ISBN 978-0-312-10409-2., ISBN 0-312-10409-X
- Yuri Gurevich , Sequential Abstract State Machines Capture Sequential Algorithms , ACM Transactions on Computational Logic, Vol 1, no 1 (julho de 2000), pp. 77–111. Inclui bibliografia de 33 fontes.
- van Heijenoort, Jean (2001). De Frege a Gödel, A Source Book in Mathematical Logic, 1879–1931 ((1967) ed.). Harvard University Press, Cambridge. ISBN 978-0-674-32449-7., 3ª edição 1976[?], ISBN 0-674-32449-8 (pbk.)
- Hodges, Andrew (1983). Alan Turing: O Enigma . Física Hoje . Vol. 37. Nova York: Simon and Schuster . pp. 107–108. Código Bib : 1984PhT ....37k.107H . doi : 10.1063/1.2915935 . ISBN 978-0-671-49207-6., ISBN 0-671-49207-1 . Cf. Capítulo "O Espírito da Verdade" para uma história levando a, e uma discussão de, sua prova.
- Kleene, Stephen C. (1936). "Funções Recursivas Gerais de Números Naturais" . Mathematische Annalen . 112 (5): 727–742. doi : 10.1007/BF01565439 . S2CID 120517999 . Arquivado do original em 3 de setembro de 2014 . Acesso em 30 de setembro de 2013 .Apresentado à American Mathematical Society, setembro de 1935. Reimpresso em The Undecidable , p. 237ss. A definição de Kleene de "recursão geral" (conhecida agora como mu-recursão) foi usada por Church em seu artigo de 1935, An Unsolvable Problem of Elementary Number Theory , que provou que o "problema de decisão" era "indecidível" (ou seja, um resultado negativo).
- Kleene, Stephen C. (1943). "Predicados e quantificadores recursivos" . Transações da American Mathematical Society . 53 (1): 41–73. doi : 10.2307/1990131 . JSTOR 1990131 .Reimpresso em O Indecidível , p. 255ss. Kleene refinou sua definição de "recursão geral" e prosseguiu em seu capítulo "12. Teorias algorítmicas" para postular a "Tese I" (p. 274); mais tarde, ele repetiria essa tese (em Kleene 1952:300) e a chamaria de "Tese da Igreja" (Kleene 1952:317) (isto é, a tese da Igreja ).
- Kleene, Stephen C. (1991) [1952]. Introdução à Metamatemática (Décima ed.). North-Holland Publishing Company. ISBN 978-0-7204-2103-3.
- Knuth, Donald (1997). Algoritmos Fundamentais, Terceira Edição . Reading, Massachusetts: Addison-Wesley. ISBN 978-0-201-89683-1.
- Knuth, Donald (1969). Volume 2/Seminumerical Algorithms, The Art of Computer Programming First Edition . Reading, Massachusetts: Addison-Wesley.
- Kosovsky, NK Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms , LSU Publ., Leningrado, 1981
- Kowalski, Robert (1979). "Algoritmo=Lógica+Controle". Comunicações da ACM . 22 (7): 424–436. doi : 10.1145/359131.359136 . S2CID 2509896 .
- AA Markov (1954) Teoria dos algoritmos . [Traduzido por Jacques J. Schorr-Kon e equipe do PST] Impresso Moscou, Academia de Ciências da URSS, 1954 [ou seja, Jerusalém, Israel Programa para Traduções Científicas, 1961; disponível no Escritório de Serviços Técnicos, Departamento de Comércio dos EUA, Washington] Descrição 444 p. 28 cm. Acrescentado tp na tradução russa de trabalhos do Instituto de Matemática, Academia de Ciências da URSS, v. 42. Título original: Teoriya algerifmov. [QA248.M2943 Biblioteca do Dartmouth College. Departamento de Comércio dos EUA, Escritório de Serviços Técnicos, número OTS 60-51085.]
- Minsky, Marvin (1967). Computação: Máquinas Finitas e Infinitas (Primeira ed.). Prentice-Hall, Englewood Cliffs, NJ. ISBN 978-0-13-165449-5.Minsky expande sua "...ideia de um algoritmo – um procedimento efetivo..." no capítulo 5.1 Computabilidade, Procedimentos Efetivos e Algoritmos. Máquinas infinitas.
- Post, Emil (1936). "Processos Combinatórios Finitos, Formulação I". O Jornal da Lógica Simbólica . 1 (3): 103–105. doi : 10.2307/2269031 . JSTOR 2269031 . S2CID 40284503 .Reimpresso em The Undecidable , pp. 289ff. Post define um processo algorítmico simples de um homem escrevendo marcas ou apagando marcas e indo de caixa em caixa e eventualmente parando, enquanto segue uma lista de instruções simples. Isso é citado por Kleene como uma fonte de sua "Tese I", a chamada tese de Church-Turing .
- Rogers, Hartley Jr. (1987). Teoria das Funções Recursivas e Computabilidade Efetiva . Imprensa do MIT. ISBN 978-0-262-68052-3.
- Rosser, JB (1939). "Uma Exposição Informal de Provas do Teorema de Gödel e do Teorema de Church". Jornal de Lógica Simbólica . 4 (2): 53–60. doi : 10.2307/2269059 . JSTOR 2269059 . S2CID 39499392 .Reimpresso em O Indecidível , p. 223ss. Aqui está a famosa definição de "método eficaz" de Rosser: "... um método em que cada etapa é precisamente predeterminada e que certamente produzirá a resposta em um número finito de etapas... o conjunto sem intervenção humana além de inserir a pergunta e (mais tarde) ler a resposta" (p. 225–226, The Undecidable )
- Santos-Lang, Christopher (2014). "Abordagens da Ecologia Moral para a Ética da Máquina" (PDF) . Em van Rysewyk, Simon; Pontier, Matthijs (eds.). Ética Médica da Máquina . Sistemas Inteligentes, Controle e Automação: Ciência e Engenharia. Vol. 74. Suíça: Springer. pp. 111–127. doi : 10.1007/978-3-319-08108-3_8 . ISBN 978-3-319-08107-6. Arquivado (PDF) do original em 9 de outubro de 2022.
- Scott, Michael L. (2009). Pragmática da Linguagem de Programação (3ª ed.). Morgan Kaufmann Publishers/Elsevier. ISBN 978-0-12-374514-9.
- Sipser, Michael (2006). Introdução à Teoria da Computação . Editora PWS. ISBN 978-0-534-94728-6.
- Sóbrio, Elliott; Wilson, David Sloan (1998). Aos outros: a evolução e a psicologia do comportamento altruísta . Cambridge: Harvard University Press. ISBN 9780674930469.
- Stone, Harold S. (1972). Introdução à Organização de Computadores e Estruturas de Dados (1972 ed.). McGraw-Hill, Nova York. ISBN 978-0-07-061726-1.Cf. em particular o primeiro capítulo intitulado: Algorithms, Turing Machines, and Programs . Sua definição informal sucinta: "...qualquer seqüência de instruções que pode ser obedecida por um robô é chamada de algoritmo " (p. 4).
- Tausworthe, Robert C (1977). Desenvolvimento Padronizado de Software de Computador Parte 1 Métodos . Englewood Cliffs NJ: Prentice-Hall, Inc. ISBN 978-0-13-842195-3.
- Turing, Alan M. (1936–37). "Em números computáveis, com um aplicativo para o Entscheidungsproblem". Anais da London Mathematical Society . Série 2. 42 : 230–265. doi : 10.1112/plms/s2-42.1.230 . S2CID 73712 .. Correções, ibid, vol. 43 (1937), pp. 544–546. Reimpresso em O Indecidível , p. 116ss. O famoso artigo de Turing foi concluído como uma dissertação de mestrado no King's College Cambridge, Reino Unido.
- Turing, Alan M. (1939). "Sistemas de Lógica Baseados em Ordinais". Anais da London Mathematical Society . 45 : 161–228. doi : 10.1112/plms/s2-45.1.161 . hdl : 21.11116/0000-0001-91CE-3 .Reimpresso em The Undecidable , pp. 155ff. O artigo de Turing que definiu "o oráculo" foi sua tese de doutorado enquanto estava em Princeton.
- Escritório de Marcas e Patentes dos Estados Unidos (2006), 2106.02 **> Algoritmos Matemáticos: 2100 Patenteabilidade , Manual de Procedimento de Exame de Patentes (MPEP). Última revisão Agosto de 2006
Leitura adicional
- Bellah, Robert Neelly (1985). Hábitos do Coração: Individualismo e Compromisso na Vida Americana . Berkeley: University of California Press. ISBN 978-0-520-25419-0.
- Berlinski, David (2001). O Advento do Algoritmo: A Jornada de 300 Anos de uma Ideia ao Computador . Livros da Colheita. ISBN 978-0-15-601391-8.
- Chabert, Jean-Luc (1999). Uma história de algoritmos: do seixo ao microchip . Springer Verlag. ISBN 978-3-540-63369-3.
- Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introdução aos Algoritmos (3ª ed.). Imprensa MIT. ISBN 978-0-262-03384-8.
- Harel, David; Feldman, Yishai (2004). Algoritmica: O Espírito da Computação . Addison-Wesley. ISBN 978-0-321-11784-7.
- Hertzke, Allen D.; McRorie, Chris (1998). "O Conceito de Ecologia Moral". Em Lawler, Peter Augustine; McConkey, Dale (eds.). Comunidade e pensamento político hoje . Westport, CT: Praeger .
- Knuth, Donald E. (2000). Artigos selecionados sobre análise de algoritmos . Stanford, Califórnia: Centro para o Estudo da Linguagem e Informação.
- Knuth, Donald E. (2010). Artigos selecionados sobre design de algoritmos . Stanford, Califórnia: Centro para o Estudo da Linguagem e Informação.
- Wallach, Wendell; Allen, Colin (novembro de 2008). Moral Machines: Ensinando Robôs do Certo ao Errado . EUA: Oxford University Press. ISBN 978-0-19-537404-9.
- Bleakley, Chris (2020). Poemas que resolvem quebra-cabeças: a história e a ciência dos algoritmos . Imprensa da Universidade de Oxford. ISBN 978-0-19-885373-2.
links externos
- "Algorithm" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Algoritmos em Curlie
- Weisstein, Eric W. "Algoritmo" . MathWorld .
- Dicionário de Algoritmos e Estruturas de Dados – Instituto Nacional de Padrões e Tecnologia
- repositórios de algoritmos