Algoritmo

Da Wikipédia, a enciclopédia livre
  (Redireccionado de Projeto de Algoritmos )
Ir para a navegação Saltar para pesquisar

Fluxograma de um algoritmo (algoritmo de Euclides ) para calcular o máximo divisor comum (mcd) de dois números a e b em locais denominados A e B. O algoritmo procede por subtrações sucessivas em dois loops: SE o teste B ≥ A produz "sim" ou "verdadeiro" (mais precisamente, o número b no local B é maior ou igual ao número a no local A) ENTÃO, o algoritmo especifica B ← B − A (significando que o número ba substitui o antigo b). Da mesma forma, SE A > B, ENTÃO A ← A − B. O processo termina quando (o conteúdo de) B é 0, produzindo o mdc em A. (Algoritmo derivado de Scott 2009:13; símbolos e estilo de desenho de Tausworthe 1977) .
Diagrama de Ada Lovelace da "nota G", o primeiro algoritmo de computador publicado

Em matemática e ciência da computação , um algoritmo ( / æ l ɡ ə r ɪ ð əm / ( listen )ícone de alto-falante de áudio ) é uma sequência finita de instruções bem definidas , normalmente usadas para resolver uma classe de problemas específicos ou para realizar uma computação. [1] Algoritmos são usados ​​como especificações para realizar cálculos , processamento de dados , raciocínio automatizado , tomada de decisão automatizada e outras tarefas. 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. [2]

Como um método eficaz , um algoritmo pode ser expresso dentro de uma quantidade finita de espaço e tempo, [3] e em uma linguagem formal bem definida [4] para calcular uma função . [5] Partindo de um estado inicial e de uma entrada inicial (talvez vazia ), [6] as instruções descrevem uma computação que, quando executada , prossegue por um número finito [7] de estados sucessivos bem definidos, eventualmente produzindo "saída" [ 8] e terminando em um estado final final. A transição de um estado para o outro não é necessariamente determinística; alguns algoritmos, conhecidos como algoritmos aleatórios , incorporam entradas aleatórias. [9]

História [ editar ]

O conceito de algoritmo existe desde a antiguidade. Algoritmos aritméticos , como um algoritmo de divisão , foram usados ​​por antigos matemáticos babilônicos c. 2500 aC e matemáticos egípcios c. 1550 aC. [10] Os matemáticos gregos mais tarde 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. [11] Matemáticos árabes como al-Kindi no século IX usaram algoritmos criptográficos para quebrar códigos, com base na análise de freqüência . [12]

A palavra algoritmo é derivada do nome do matemático persa do século IX Muḥammad ibn Mūsā al-Khwārizmī , cujo nisba (identificando-o como de Khwarazm ) foi latinizado como Algoritmi ( persa arabizado الخوارزمی c. 780–850). [13] [14] Muḥammad ibn Mūsā al-Khwārizmī foi um matemático, astrônomo , geógrafo e estudioso da Casa da Sabedoria em Bagdá , cujo nome significa 'o nativo de Khwarazm ', uma região que fazia parte do Grande Irã e é agora no Uzbequistão. [15] [16] Por volta de 825, al-Khwarizmi escreveu um tratado em árabe sobre o sistema de numeração hindu-arábico , 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 do nome de Al-Khwarizmi pelo tradutor. [17] 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 . [18] No latim medieval tardio, algorismus , inglês ' algorism', a corrupção de seu nome, significava simplesmente o "sistema de numeração decimal". [19] No século 15, sob a influência da palavra grega ἀριθμός ( arithmos ), 'número' ( cf. 'aritmética'), a palavra latina foi alterada para algoritmous , e o termo inglês correspondente 'algoritmo' é atestado pela primeira vez no século XVII; o sentido moderno foi introduzido no século XIX. [20]

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 . [ citação necessária ]

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 não foi até o final do século 19 que "algoritmo" assumiu o significado que tem no inglês moderno. [21]

Outro uso inicial da palavra é de 1240, em um manual intitulado Carmen de Algorismo composto por Alexandre de Villedieu . Ele começa com:

Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.

que se traduz em:

O algorismo é a arte pela qual atualmente usamos essas figuras indianas, que são duas vezes cinco.

O poema tem algumas centenas de linhas e resume a arte de calcular com os novos dados indianos ( Tali Indorum ), ou numerais hindus. [22]

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 " [23] ou "método efetivo". [24] Essas formalizações incluíram as funções recursivas de GödelHerbrandKleene de 1930, 1934 e 1935, o cálculo lambda de Alonzo Church de 1936, a Formulação 1 de Emil Post de 1936 e a de Alan TuringMáquinas de Turing de 1936-37 e 1939.

Definição informal [ editar ]

Uma definição informal poderia ser "um conjunto de regras que define precisamente uma sequência de operações", [25] [ precisa de cotação para verificar ] que inclui todos os programas de computador (incluindo programas que não realizam cálculos numéricos) e (por exemplo) qualquer procedimento burocrático prescrito [26] ou receita de livro de receitas . [27]

Em geral, um programa só é um algoritmo se parar eventualmente [28] — mesmo que loops infinitos às vezes possam ser desejáveis.

Um exemplo prototípico de algoritmo é o algoritmo euclidiano , que é usado para determinar o máximo divisor comum de dois inteiros; um exemplo (há outros) é descrito pelo 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, átomos, elétrons") para listar todos os membros de uma enumeravelmente infinitos, 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 infinitamente infinitos: eles podem dar instruções explícitas para determinar o n - ésimo membro do conjunto , para n finito arbitrário . Tais instruções devem ser dadas de forma bastante explícita, de uma forma que possam ser seguidas por uma máquina de computação ou por um humano capaz de realizar apenas operações muito elementares sobre símbolos. [29]

Um "conjunto infinitamente infinito" é aquele cujos elementos podem ser colocados em correspondência um-para-um com os inteiros. Assim, Boolos e Jeffrey estão dizendo que um algoritmo implica instruções para um processo que "cria" inteiros de saída 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" m e n arbitrárias que produzem uma saída y ), mas as tentativas de vários autores para definir a noção indicam que a palavra implica muito mais do que isso, algo da ordem de (para o exemplo de adição):

Instruções precisas (em uma linguagem compreendida pelo "computador") [30] para um processo rápido, eficiente, "bom" [31] que especifica os "movimentos" do "computador" (máquina ou humano, equipado com os necessários continha informações e capacidades) [32] para encontrar, decodificar e então processar inteiros/símbolos de entrada arbitrária m e n , símbolos + e = ... e "efetivamente" [33] produzir, em um tempo "razoável", [34 ] output-integer 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. Em lógica , o tempo que um algoritmo requer para completar não pode ser medido, pois aparentemente não está relacionado à dimensão física habitual. De tais 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 abstrato do termo.

A maioria dos algoritmos destina-se a ser implementado 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 [ editar ]

Os algoritmos são essenciais para a forma 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 os contracheques 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 . Os autores que afirmam esta tese incluem Minsky (1967), Savage (1987) e Gurevich (2000):

Minsky: "Mas também sustentaremos, com Turing... que qualquer procedimento que possa "naturalmente" ser chamado de eficaz, pode, de fato, ser realizado por uma máquina (simples). Embora isso possa parecer extremo, os argumentos... . em seu favor são difíceis de refutar". [35] 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". [36]

Máquinas de Turing podem definir processos computacionais que não terminam. As definições informais de algoritmos geralmente exigem 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 grande 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: 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 computáveis).

Como um algoritmo é uma lista precisa de etapas precisas, a ordem de computação é sempre crucial para o funcionamento do algoritmo. As instruções geralmente são listadas explicitamente e são descritas como começando "de cima" 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 - uma que tenta descrever uma tarefa em meios discretos, "mecânicos". Exclusivo para esta 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 rascunho. 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 [ editar ]

Os algoritmos podem ser expressos em vários tipos de notação, incluindo linguagens naturais , pseudocódigo , fluxogramas , drakon-charts , linguagens de programação ou tabelas de controle (processadas por intérpretes ). As expressões de linguagem natural de algoritmos tendem a ser verbosas e ambíguas e raramente são usadas para algoritmos complexos ou técnicos. Pseudocódigo, fluxogramas, drakon-chartse as 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 (veja máquina de estado finito , tabela de transição de estado e tabela de controle para mais), como fluxogramas e drakon-charts (veja diagrama de estado para mais), ou como uma forma de código de máquina rudimentar ou código de montagem chamado "conjuntos de quádruplos" (veja máquina de Turing para 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: [37]

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 maneira como a máquina de Turing usa sua cabeça e a maneira 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
Mais detalhado, "nível mais baixo", fornece a "tabela de estados" 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 [ editar ]

Projeto de algoritmo refere-se a um método ou processo matemático para resolução de problemas e algoritmos de engenharia. O projeto de algoritmos faz parte de muitas teorias de solução de pesquisa operacional , como programação dinâmica e divisão e conquista . Técnicas para projetar e implementar projetos de algoritmos também são chamadas de padrões de projeto de algoritmos, [38] com exemplos que incluem o padrão de método de modelo e o padrão de decorador.

Um dos aspectos mais importantes do projeto de algoritmos é 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 em tempo de execução de um algoritmo à medida que o tamanho de sua entrada aumenta.

Etapas típicas no desenvolvimento de algoritmos:

  1. Definição de problema
  2. Desenvolvimento de um modelo
  3. Especificação do algoritmo
  4. Projetando um algoritmo
  5. Verificando a correção do algoritmo
  6. Análise do algoritmo
  7. Implementação do algoritmo
  8. Teste do programa
  9. Preparação da documentação [ esclarecimento necessário ]

Algoritmos de computador [ editar ]

Algoritmo lógico NAND implementado eletronicamente no chip 7400
Exemplos de fluxogramas das estruturas canônicas de Böhm-Jacopini : a SEQUÊNCIA (retângulos descendo a página), o WHILE-DO e o IF-THEN-ELSE. As três estruturas são compostas pelo GOTO condicional primitivo ( IF test THEN GOTO step xxx, mostrado como losango), o GOTO incondicional (retângulo), vários operadores de atribuição (retângulo) e HALT (retângulo). O aninhamento dessas estruturas dentro de blocos de atribuição resulta em diagramas complexos (cf. Tausworthe 1977:100, 114).

Em sistemas de computador , um algoritmo é basicamente uma instância de lógica escrita em software por desenvolvedores de software, para ser eficaz para o(s) computador(es) "alvo" pretendido(s) para produzir saída de uma determinada entrada (talvez nula) . Um algoritmo ótimo, mesmo rodando em hardware antigo, produziria resultados mais rápidos do que um algoritmo não ótimo (maior complexidade de tempo ) para o mesmo propósito, rodando em hardware mais eficiente; é por isso que algoritmos, como hardware de computador, são considerados tecnologia.

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 aos computadores, sua simplicidade e elegância , etc." [39]
Chaitin: "... um programa é 'elegante', pelo que quero dizer que é o menor programa possível para produzir a saída que ele faz" [40]

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, vários algoritmos podem existir. 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 gerado por procedimento. A mesma função pode ter vários algoritmos diferentes". [41]

Infelizmente, pode haver uma troca entre bondade (velocidade) e elegância (compacidade) – um programa elegante pode dar mais passos para completar uma computação do que um menos elegante. Um exemplo que usa o algoritmo de Euclides aparece abaixo.

Computadores (e computadores), modelos de computação : Um computador (ou "computador" humano [42] ) é um tipo restrito de máquina, um "dispositivo mecânico determinístico discreto" [43] que segue cegamente suas instruções. [44] Os modelos primitivos de Melzak e Lambek [45] reduziram essa noção a quatro elementos: (i) localizações discretas e distinguíveis , (ii) contadores discretos e indistinguíveis [46] (iii) um agente e (iv) uma lista de instruções que são eficazes em relação à capacidade do agente. [47]

Minsky descreve uma variação mais agradável do modelo "ábaco" de Lambek em seu "Very Simple Bases for Computability ". [48] 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 programa condicional IF-THEN GOTO ou um GOTO incondicional mude o fluxo do programa fora de sequência. Além de HALT, a máquina de Minsky inclui três operações de atribuição (substituição, substituição) [49] : ZERO (por exemplo, o conteúdo da localização substituído por 0: L ← 0), SUCESSOR (por exemplo, L ← L+1) e DECREMENTO (por exemplo, L ← L − 1). [50] Raramente um programador deve escrever "código" com um conjunto de instruções tão limitado.Turing completo 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 a completude de Turing; sua especificação exata depende um pouco do designer. O GOTO incondicional é uma conveniência; ele pode ser construído inicializando um local dedicado para zero, por exemplo, a instrução " Z ← 0 "; depois 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". [51] 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 tirar uma raiz quadrada. Caso contrário, o algoritmo, para ser eficaz, deve fornecer um conjunto de regras para extrair uma raiz quadrada. [52]

Isso significa que o programador deve conhecer uma "linguagem" que seja efetiva 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 se basearmos a teoria da complexidade em máquinas abstratas em vez de concretas, a arbitrariedade da escolha de um modelo permanece. É neste ponto que entra a noção de simulação ". [53] 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 de " 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 como Turing completo e, pelas demonstrações de Minsky, a completude de Turing requer apenas quatro tipos de instrução - GOTO condicional, GOTO incondicional, atribuição, HALT. Kemeny e Kurtz observam que, enquanto o uso "indisciplinado" de GOTOs incondicionais e GOTOs IF-THEN condicionais pode 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".[54] Tausworthe aumenta as três estruturas canônicas de Böhm-Jacopini :[55] SEQUENCE, IF-THEN-ELSE e WHILE-DO, com mais dois: DO-WHILE e CASE. [56] Um benefício adicional de um programa estruturado é que ele se presta a provas de correção usando indução matemática . [57]

Símbolos de fluxogramas canônicos [58] : O auxiliar gráfico chamado fluxograma , oferece uma maneira de descrever e documentar um algoritmo (e um programa de computador de um). Assim 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 primários são apenas quatro: a seta direcionada mostrando o fluxo do programa, o retângulo (SEQUENCE, GOTO), o diamante (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 [ editar ]

Exemplo de algoritmo [ editar ]

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 inglesa, como:

Descrição de alto nível:

  1. Se não houver números no conjunto, então não há número mais alto.
  2. Suponha que o primeiro número do conjunto seja o maior número do conjunto.
  3. 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.
  4. Quando não houver mais números 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 :

Algoritmo Maior Número
  Entrada: Uma lista de números L .
  Saída: O maior número na lista L .
  if  L.size = 0 retorna null
   maiorL [0]
   para cada  item  em  L , faça 
    se  item > maior , então 
      maioritem 
  retorna  maior
  • "←" denota atribuição . Por exemplo, " maioritem " significa que o valor do maior muda para o valor do item .
  • " return " encerra o algoritmo e gera o seguinte valor.

Algoritmo de Euclides [ editar ]

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 divide ambos sem deixar resto . É nomeado após o antigo matemático grego Euclides , que o descreveu pela primeira vez em seus Elementos (c. 300 aC). [59] É um dos algoritmos mais antigos em uso comum. Ele pode ser usado para reduzir frações à sua forma mais simples e faz parte de muitos outros cálculos teóricos de números e criptográficos.

O diagrama de exemplo do algoritmo de Euclides de TL Heath (1908), com mais detalhes adicionados. Euclides não vai além de uma terceira medição e não dá exemplos numéricos. Nicômaco dá o exemplo de 49 e 21: "Eu subtraio o menor do maior; resta 28; então novamente subtraio disso os mesmos 21 (pois isso é possível); resta 7; subtraio isso de 21, 14 é esquerda; do qual subtraio novamente 7 (pois isso é possível); resta 7, mas 7 não pode ser subtraído de 7." Heath comenta que "A última frase é curiosa, mas o significado dela é bastante óbvio, como também o significado da frase sobre terminar 'no mesmo número'." (Heath 1908:300).

Euclides coloca o problema assim: "Dados dois números não primos entre si, encontre sua maior medida comum". Ele define "Um número [para ser] uma multidão composta de unidades": um número de contagem, um número 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 maior até que a porção restante r seja menor que o comprimento s mais curto . [60] Em palavras modernas, resto r = lq × s , q sendo o quociente, ou resto ré o "módulo", a parte fracionária inteira que sobra após a divisão. [61]

Para que o método de Euclides tenha sucesso, os comprimentos iniciais devem satisfazer a dois requisitos: (i) os comprimentos não devem ser zero, E (ii) a subtração deve ser "própria"; isto é, um teste deve garantir que o menor dos dois números seja subtraído do maior (ou os dois podem ser iguais para que sua subtração resulte em zero).

A prova original de Euclides acrescenta um terceiro requisito: os dois comprimentos não devem ser primos entre si. 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 . [62] Embora o algoritmo de Nicômaco seja o mesmo que o 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.

Uma 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 [ editar ]

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 [ editar ]

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

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 resto, ele usa subtrações sucessivas do menor comprimento 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 [Em dois locais L e S coloque os números l e s que representam os dois comprimentos]:
  ENTRADA L, S
2 [Inicializar R: tornar o comprimento restante r igual ao comprimento inicial/inicial/de entrada l ]:
  R ← L

E0: [Certifique-se de que rs .]

3 [Certifique-se de que o menor dos dois números esteja em S e o maior em R]:
  SE R > S ENTÃO
    o conteúdo de L é o número maior, então pule as etapas de troca 4 , 5 e 6 :
    GOTO passo 7
  SENÃO
    troque o conteúdo de R e S.
4    L ← R (este primeiro passo é redundante, mas é útil para discussão posterior).
5    R ← S
6    S ← L

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

7 SE S > R ENTÃO
    feito medindo assim
    GOTO 10
  SENÃO
    medir novamente,
8    R ← R − S
9    [Loop restante]:
    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 do que o número de medição em S.

10 SE R = 0 ENTÃO
     Feito assim
     GOTO passo 15
   SENÃO
     CONTINUE AO PASSO 11 ,

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

11   L ← R
12   R ← S
13   S ← L
14   [Repita o processo de medição]:
    IR PARA 7

SAÍDA :

15 [Concluído. S contém o máximo divisor comum ]:
   IMPRESSÃO

CONCLUÍDO :

16 PARAR, TERMINAR, PARAR.

Um programa elegante para o algoritmo de Euclides [ editar ]

A seguinte versão do algoritmo de Euclides requer apenas seis instruções básicas para fazer o que treze são exigidos por "Deselegante"; pior, "Deselegante" requer mais tipos de instruções. [ esclarecer ] O fluxograma de "Elegante" pode ser encontrado no início deste artigo. Na linguagem básica (não estruturada), as etapas são numeradas e a instrução é a instrução de atribuição simbolizada por ←. LET [] = []

  5  REM Algoritmo de Euclides para o máximo divisor comum 
  6  PRINT  "Digite dois inteiros maiores que 0" 
  10  INPUT  A , B 
  20  IF  B = 0  ENTÃO  GOTO  80 
  30  SE  A  >  B  ENTÃO  GOTO  60 
  40  LET  B = B - A 
  50  GOTO  20 
  60  DEIXE  A = A - B 
  70  GOTO  20 
  80  IMPRIMIR  A 
  90  FIM

Como funciona o "Elegant" : No lugar de um "loop Euclid" externo, "Elegant" muda para frente e para trás 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 é menor ou igual ao subtraendo S (Diferença = Minuendo − Subtraendo), o minuendo pode se tornar s (o novo comprimento de medição) 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 :

// Algoritmo de Euclides para o máximo divisor comum 
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 [ editar ]

Um algoritmo faz o que seu autor quer que ele faça? Alguns casos de teste geralmente dão alguma confiança na funcionalidade principal. Mas os testes não são suficientes. Para casos de teste, uma fonte [63] 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" [64] devem ser identificados e testados. O "Deselegante" funcionará corretamente quando R > S, S > R, R = S? Idem 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" computa para sempre em todos os casos; "Elegante" computa 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 calculada pelo algoritmo/programa, deve incluir apenas números inteiros positivos, incluindo zero,. Uma falha notável devido a exceções é a falha do foguete Ariane 5 Flight 501 (4 de junho de 1996).

Prova de correçã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". [65] Tausworthe propõe que uma medida da complexidade de um programa seja o comprimento de sua prova de correção. [66]

Medindo e melhorando os algoritmos de Euclides [ editar ]

Elegância (compacidade) versus bondade (velocidade) : Com apenas seis instruções básicas, "Elegante" é o vencedor claro, comparado a "Deselegante" com treze instruções. No entanto, "Deselegante" é mais rápido (chega ao HALT em menos etapas). A análise do algoritmo [67] indica por que este é o caso: "Elegant" faz dois testes condicionais em cada loop de subtração, enquanto "Deselegante" faz apenas um. Como o algoritmo (geralmente) requer muitos loop-throughs, em média , muito tempo é desperdiçado fazendo um "B = 0?" teste que é necessário somente após o restante ser calculado.

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; [68] em vez disso, isso 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 "Elegante" 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 básicas de treze para oito, o que o torna "mais elegante" do que "Elegante", em nove etapas.

A velocidade de "Elegante" pode ser melhorada movendo o botã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 esse é sempre o caso para qualquer dado A, B e R, S exigiria uma análise detalhada.

Análise algorítmica [ editar ]

Frequentemente, é importante saber quanto de um recurso específico (como tempo ou armazenamento) é teoricamente necessário para um determinado algoritmo. Foram desenvolvidos métodos para a análise de algoritmos para obter tais 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 O grande . Em todos os momentos, o algoritmo precisa lembrar apenas dois valores: a soma de todos os elementos 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 for contado, ou O(n) se for contado.

Diferentes algoritmos podem completar a mesma tarefa com um conjunto diferente de instruções em menos ou mais tempo, espaço ou ' esforço ' do que outros. Por exemplo, 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 [ editar ]

A análise e estudo de algoritmos é uma disciplina da ciência da computação , e muitas vezes é praticada de forma abstrata sem o uso de uma linguagem de programação específica ou implementação. 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 em particular. 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 são implementados em plataformas de hardware/software específicas e sua eficiência algorítmicaé eventualmente posto à prova 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 rápido, comercial ou de longa vida pode ser crítico. A escala 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. Os benchmarks podem ser usados ​​para comparar melhorias potenciais antes/depois de um algoritmo após a otimização do programa. Testes empíricos não podem substituir a análise formal, no entanto, e não são triviais para serem executados de maneira justa. [69]

Eficiência de execução [ editar ]

Para ilustrar as possíveis melhorias possíveis mesmo em algoritmos bem estabelecidos, uma inovação significativa recente, 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. [70] Em geral, melhorias de velocidade dependem de propriedades especiais do problema, que são muito comuns em aplicações práticas. [71] Aceleração dessa magnitude permite 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 [ editar ]

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

Por implementação [ editar ]

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

int mdc ( int A , int B ) {     
    se ( B == 0 )   
        retornar A ; 
    senão se ( A > B )    
        return mdc ( A - B , B ); 
    senão
        return mdc ( A , B - A ); 
}
Implementação recursiva em C 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 determinada 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 Hanói 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 . [72] A componente lógica expressa os axiomas que podem ser utilizados na computação e a componente de controlo 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 de 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 aos algoritmos paralelos ou algoritmos distribuídos . Os algoritmos paralelos tiram proveito de arquiteturas de computador onde vários processadores podem trabalhar em um problema ao mesmo tempo, enquanto os algoritmos distribuídos utilizam 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 coletam 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 ordenação podem ser paralelizados de forma eficiente, 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ão exata em cada etapa do algoritmo, enquanto os algoritmos não determinísticos resolvem problemas por meio de adivinhação, embora as suposições típicas sejam mais precisas pelo uso de heurísticas .
Exato ou aproximado
Enquanto muitos algoritmos alcançam 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 existe um conjunto de itens dados. Seu objetivo é embalar a mochila para obter o valor total máximo. Cada item tem algum peso e algum valor. O peso total que pode ser transportado não é mais do que algum número fixo X. Assim, a solução deve considerar os pesos dos itens, bem como seu valor. [73]
Algoritmo quântico
Eles são executados 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 [ editar ]

Outra maneira de classificar algoritmos é por sua metodologia de projeto ou paradigma . Há 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. [74]
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 exemplo de dividir e conquistar é 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 diminuição e conquista, 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 os algoritmos de diminuição e conquista. 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 se mover em torno de 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 (veja o método heurístico abaixo). Para alguns desses problemas, sabe-se que as aproximações mais rápidas devem envolver alguma aleatoriedade . [75] 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:
  1. Os algoritmos de Monte Carlo retornam uma resposta correta com alta probabilidade. Por exemplo , RP é a subclasse destes que rodam em tempo polinomial .
  2. 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 de redução 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
Nessa 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 [ editar ]

Para problemas de otimização existe uma classificação mais específica de algoritmos; um algoritmo para tais problemas pode se enquadrar 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 lineares de igualdade e desigualdade, as restrições do problema podem ser usadas diretamente na produção das soluções ótimas. Existem algoritmos que podem resolver qualquer problema nesta categoria, como o popular algoritmo simplex . [76] Problemas que podem ser resolvidos com programação linear incluem o problema de fluxo máximo para grafos direcionados. Se um problema requer adicionalmente que uma ou mais incógnitas sejam um número inteiro , então ele é classificado em programação inteira. Um algoritmo de programação linear pode resolver tal problema se puder ser provado 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, é utilizado um algoritmo especializado ou um algoritmo que encontre soluções aproximadas, dependendo da dificuldade do problema.
Programaçao dinamica
Quando um problema mostra subestruturas ótimas – significando que a solução ótima para um problema pode ser construída a partir de soluções ótimas para subproblemas – e subproblemas sobrepostos , significando 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 recomputar soluções que já foram computados. Por exemplo, o 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. Programação dinâmica e memorizaçãová junto. A principal diferença entre programação dinâmica e divisão e conquista é que os subproblemas são mais ou menos independentes na divisão e conquista, 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 memorização de chamadas recursivas. Quando os subproblemas são independentes e não há repetição, a memorizaçã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 é encontrar a árvore geradora mínima onde encontrar a solução ótima é possível com este método. Huffman Tree , Kruskal , Prim , Sollin são algoritmos gulosos que podem resolver este 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 nos casos em que encontrar a solução ótima é impraticável. Esses algoritmos funcionam aproximando-se cada vez mais da solução ótima à medida que progridem. Em princípio, se executados por uma quantidade infinita de tempo, 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 busca tabu, são determinísticos. Quando um limite no erro da solução não ótima é conhecido, o algoritmo é ainda categorizado como um algoritmo de aproximação .

Por área de estudo [ editar ]

Cada campo da ciência tem seus próprios problemas e precisa de algoritmos eficientes. Problemas relacionados em um campo são frequentemente estudados juntos. 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 sintática .

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 [ editar ]

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, independente 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 busca binária .
  • Tempo linear: se o tempo for proporcional ao tamanho da entrada. Por exemplo, a travessia 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 algoritmos eficientes conhecidos. Há também mapeamentos de alguns problemas para outros problemas. Devido a isso, verificou-se ser mais adequado classificar os problemas em si do que os algoritmos em classes de equivalência com base na complexidade dos melhores algoritmos possíveis para eles.

Algoritmos contínuos [ editar ]

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 . [77]

Questões legais [ editar ]

Os algoritmos, por si só, geralmente não são patenteáveis. Nos Estados Unidos, uma reivindicação que consiste apenas em simples manipulações 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 Unisys' Patente LZW .

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" [ editar ]

Antigo Oriente Próximo [ editar ]

A evidência mais antiga de algoritmos é encontrada na matemática babilônica da antiga Mesopotâmia (atual Iraque). Uma tabuleta 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 . [10] Durante a dinastia Hamurabi, por volta de 1800-1600 aC, tabuletas de argila babilônicas descreviam algoritmos para calcular fórmulas . [78] 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. [79]

Algoritmos para aritmética também são encontrados na matemática egípcia antiga , que remonta ao Papiro Matemático Rhind por volta de 1550 aC. [10] Os algoritmos foram usados ​​mais tarde na matemática helenística antiga . Dois exemplos são a Peneira de Eratóstenes , que foi descrita na Introdução à Aritmética por Nicômaco , [80] [11] : Ch 9.2  e o algoritmo de Euclides , que foi descrito pela primeira vez nos Elementos de Euclides (c. 300 aC). [11] : Ch 9.1 

Símbolos discretos e distinguíveis [ editar ]

Marcas de contagem: Para acompanhar seus rebanhos, seus sacos de grãos e seu dinheiro, os antigos usavam a contagem: acumulando pedras ou marcas rabiscadas em paus ou fazendo símbolos discretos no barro. 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 tally aparecem com destaque na aritmética do sistema de numeração unária usada na máquina de Turing e nos cálculos da máquina de Post-Turing .

Manipulação de símbolos como "lugares" para números: álgebra [ editar ]

Muhammad ibn Mūsā al-Khwārizmī , um matemático persa , escreveu o Al-jabr no século IX. Os termos " algorismo " 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 mais tarde ser generalizada para se referir a qualquer conjunto de regras ou técnicas. [81] Isso culminou na noção de Leibniz do raciocinador do cálculo (ca 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 manipular conceitos lógicos da mesma maneira que a álgebra comum especifica as regras para manipular números. [82]

Algoritmos criptográficos [ editar ]

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. [12]

Dispositivos mecânicos com estados discretos [ editar ]

O relógio : Bolter credita a invenção do relógio a peso como "A invenção chave [da Europa na Idade Média]", em particular, o escape de beira [83] que nos fornece o tique-taque de um relógio mecânico. "A máquina automática precisa" [84] 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 XIX. [85]Lovelace é creditado com a primeira criação de um algoritmo destinado ao processamento em um computador - o mecanismo analítico de Babbage, o primeiro dispositivo considerado um verdadeiro computador Turing-completo 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 em uma forma semelhante ao que hoje é conhecido como mapas de Karnaugh . Jevons (1880) descreve primeiro um simples "ábaco" de "lascas de madeira providas de alfinetes, elaboradas de modo que qualquer parte ou classe das combinações [lógicas] possam ser escolhidas mecanicamente ... Mais recentemente, porém, reduzi o sistema para 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 de madeira móveis" e "ao pé estã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 " . [86]

Esta máquina ele exibiu em 1870 perante os membros da Royal Society. [87] Outro lógico John Venn , no entanto, em seu livro Symbolic Logic , de 1881 , voltou-se para esse esforço: para mim que quaisquer artifícios atualmente conhecidos ou passíveis de serem descobertos realmente merecem o nome de máquinas lógicas”; veja mais em Caracterizações de algoritmos . Mas para não ficar atrás, ele também apresentou "um plano um tanto análogo, creio, ao ábaco do Prof.... [E] [a] de novo, correspondendo à máquina lógica do Prof. Jevons, o seguinte artifício pode ser descrito. Prefiro chamá-la meramente de máquina de diagramas lógicos... mas suponho que ela poderia fazer completamente tudo o que se pode esperar racionalmente de qualquer máquina lógica" .

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. [89] 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 ticker (cerca de 1870) estava em uso, assim como o uso de cartões Hollerith no censo de 1890 dos EUA. Então veio o teleimpressor(ca. 1910) com seu uso em papel perfurado do código Baudot em 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 soma digital. Enquanto trabalhava nos Laboratórios Bell, ele observou o "trabalho pesado" de calculadoras mecânicas com engrenagens. [ 90]

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, 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." [91]

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

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) reduziram 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 ". [92]

Mas Heijenoort dá a Frege (1879) este kudos: Frege é "talvez o trabalho individual mais importante já escrito em lógica ... , "para pensamento puro", isto é, livre de embelezamentos retóricos ... construído a partir de símbolos específicos que são manipulados de acordo com regras definidas". seus 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-1903) e o paradoxo de Richard . [94] 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 eficaz : 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 eficaz" ou "cálculo eficaz" ou "calculabilidade efetiva" (ou seja, um cálculo que teria sucesso ). Em rápida sucessão apareceram: Alonzo Church , Stephen Kleene e JB Rosser 's λ-calculus [95] uma definição finamente afiada de "recursão geral" do trabalho de Gödel agindo em sugestões de Jacques Herbrand (cf. 1934) e simplificações subsequentes por Kleene. [96] Igreja's prova [97]que o Entscheidungsproblem era insolúvel, a definição de Emil Post de calculabilidade efetiva como um trabalhador que segue uma lista de instruções para se mover para a esquerda ou para a direita através de uma sequência de salas e, enquanto lá, marcar ou apagar um papel ou observar o papel e fazer um sim -nenhuma decisão sobre a próxima instrução. [98] A prova de Alan Turing de que o Entscheidungsproblem era insolúvel pelo uso de sua "máquina a- [automática-]" [99] - na verdade quase idêntica à "formulação" de Post, a definição de J. Barkley Rosser de "método eficaz" " em termos de "uma máquina". [100] A proposta de Kleene de um precursor da " tese da Igreja " que ele chamou de "e alguns anos depois, Kleene renomeou sua Tese como "Tese da Igreja" [102] e propôs "Tese de Turing". [103]

Emil Post (1936) e Alan Turing (1936–37, 1939) [ editar ]

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 de direções fixas e inalteráveis .

Seu espaço simbólico seria

"uma seqüência infinita de duas vias de espaços ou caixas... O solucionador de problemas ou trabalhador deve se mover e trabalhar neste espaço de símbolos, sendo capaz de estar e operar em apenas uma caixa de cada vez... uma caixa é admitir apenas duas condições possíveis, isto é, estar vazio ou não marcado, e ter uma única marca nele, digamos um traço vertical.
"Uma caixa deve ser destacada e chamada de ponto de partida. ...um problema específico deve ser dado de forma simbólica por um número finito de caixas [ie, INPUT] sendo marcadas com um traço. Da mesma forma, a resposta [ie, , OUTPUT] deve ser dado de 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. Este processo termina apenas quando se trata da direção do tipo (C) [isto é, PARAR]". [104] Veja mais em Máquina Post–Turing
Estátua de Alan Turing em Bletchley Park

A obra de Alan Turing [105] 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 semelhante a uma máquina de escrever derivava de um interesse juvenil: "Alan sonhava em inventar máquinas de escrever quando menino; a Sra. uma máquina de escrever 'mecânica'". [106] Dada a prevalência do código Morse e da telegrafia, máquinas de ticker tape e teletipos nós [ quem? ] pode conjecturar que todos foram influências.

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 simples conjunto de movimentos básicos e “estados mentais”. Mas ele dá um passo adiante e cria uma máquina como modelo de computação de números. [107]

"A computação normalmente é feita escrevendo certos símbolos no papel. Podemos supor que este papel seja dividido em quadrados como um livro de aritmética infantil... 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 mental" naquele momento. Podemos supor que há um limite B para o número de símbolos ou quadrados que o computador pode observe em um momento. Se ele deseja observar mais, ele deve usar observações sucessivas. Também vamos supor que o número de estados de espírito 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." [108]

A redução de Turing produz o seguinte:

"As operações simples devem, portanto, incluir:
"(a) Mudanças 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 necessariamente invoquem 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 junto 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." [108]

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

"Diz-se que uma função é "efetivamente calculável" se seus valores podem ser encontrados por algum processo puramente mecânico. ... [ele discute a história da definição mais ou menos como apresentada 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 aquele que pode 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 a uma identificação de computabilidade † com calculabilidade efetiva ... .
"† Usaremos a expressão "função computável" para designar 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". [109]

JB Rosser (1939) e SC Kleene (1943) [ editar ]

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 [sua nota de rodapé #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, resolver qualquer problema do conjunto sem intervenção humana além de inserir a pergunta e (depois) ler a resposta. Todas as três definições são equivalentes, portanto, não importa qual seja usada. Além disso, o fato de que todos os três são 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 Formly 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 (negrito no original):

"12. Teorias algorítmicas ... Ao montar uma teoria algorítmica completa, o que fazemos é descrever um procedimento, executável para cada conjunto de valores das variáveis ​​independentes, cujo procedimento necessariamente termina e de tal forma 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 [ editar ]

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, fundamentos da matemática (especialmente a tese de Church-Turing ) e filosofia da mente (especialmente argumentos sobre inteligência artificial ). Para saber mais, consulte Caracterizações de algoritmos .

Veja também [ editar ]

Notas [ editar ]

  1. ^ "Definição de ALGORITMO" . Dicionário Online Merriam-Webster . Arquivado do original em 14 de fevereiro de 2020 . Recuperado em 14 de novembro de 2019 .
  2. David A. Grossman, Ophir Frieder, Information Retrieval: Algorithms and Heuristics , 2ª edição, 2004, ISBN 1402030045 
  3. "Qualquer algoritmo matemático clássico, por exemplo, pode ser descrito em um número finito de palavras em inglês" (Rogers 1987:2).
  4. ^ Bem definido em relação ao agente que executa o algoritmo: "Existe um agente de computação, geralmente humano, que pode reagir às instruções e realizar os cálculos" (Rogers 1987:2).
  5. ^ "um algoritmo é um procedimento para calcular uma função (com respeito a alguma notação escolhida para inteiros) ... esta limitação (para funções numéricas) não resulta em perda de generalidade", (Rogers 1987:1).
  6. ^ "Um algoritmo tem zero ou mais entradas, ou seja, quantidades que são dadas a ele inicialmente antes do algoritmo começar" (Knuth 1973:5).
  7. "Um procedimento que tem todas as características de um algoritmo, exceto que possivelmente carece de finitude, pode ser chamado de 'método computacional ' " (Knuth 1973:5).
  8. ^ "Um algoritmo tem uma ou mais saídas, ou seja, quantidades que têm uma relação especificada com as entradas" (Knuth 1973:5).
  9. ^ Se um processo com processos internos aleatórios (sem incluir a entrada) é um algoritmo é discutível. Rogers opina que: "uma computação é realizada em um modo discreto passo a passo, sem o uso de métodos contínuos ou dispositivos analógicos ... levado adiante deterministicamente, sem recorrer a métodos ou dispositivos aleatórios, por exemplo, dados" (Rogers 1987: 2) .
  10. ^ a b c Chabert, Jean-Luc (2012). Uma história de algoritmos: do seixo ao microchip . Springer Science & Business Media. págs. 7–8. ISBN 9783642181924.
  11. ^ a b c Cooke, Roger L. (2005). A História da Matemática: Um Breve Curso . John Wiley & Filhos. ISBN 978-1-118-46029-0.
  12. ^ a b Dooley, John F. (2013). Uma Breve História da Criptologia e Algoritmos Criptográficos . Springer Science & Business Media. págs. 12–3. ISBN 9783319016283.
  13. ^ "Biografia de Al-Khwarizmi" . www-history.mcs.st-andrews.ac.uk . Arquivado do original em 2 de agosto de 2019 . Recuperado em 3 de maio de 2017 .
  14. ^ "Etimologia de algoritmo" . Dicionário Chambers . Arquivado do original em 31 de março de 2019 . Recuperado em 13 de dezembro de 2016 .
  15. ^ Hogendijk, janeiro P. (1998). "al-Khwarzimi" . Pitágoras . 38 (2): 4–5. Arquivado a partir do original em 12 de abril de 2009.
  16. ^ Oaks, Jeffrey A. "Al-Khwarizmi era um algebrista aplicado?" . Universidade de Indianápolis . Arquivado a partir do original em 18 de julho de 2011 . Recuperado em 30 de maio de 2008 .
  17. ^ Brezina, Corona (2006). Al-Khwarizmi: O inventor da álgebra . O Grupo Editorial Rosen. ISBN 978-1-4042-0513-0.
  18. Os principais textos matemáticos da história Arquivado em 9 de junho de 2011, no Wayback Machine , de acordo com Carl B. Boyer .
  19. ^ "algorismic" , The Free Dictionary , arquivado do original em 21 de dezembro de 2019 , recuperado em 14 de novembro de 2019
  20. ^ Oxford English Dictionary , Terceira Edição, 2012 sv
  21. ^ Mehri, Bahman (2017). "De Al-Khwarizmi ao algoritmo". Olimpíadas de Informática . 11 (2): 71–74. doi : 10.15388/ioi.2017.special.11 .
  22. ^ "Abu Jafar Muhammad ibn Musa al-Khwarizmi" . membros.peak.org . Arquivado do original em 21 de agosto de 2019 . Recuperado em 14 de novembro de 2019 .
  23. ^ Kleene 1943 em Davis 1965:274
  24. ^ Rosser 1939 em Davis 1965:225
  25. ^ Pedra 1973:4
  26. ^ Simanowski, Roberto (2018). O Algoritmo da Morte e Outros Dilemas Digitais . Meditações intempestivas. Vol. 14. Traduzido por Chase, Jefferson. Cambridge, Massachusetts: MIT Press. pág. 147. ISBN  9780262536370. Arquivado do original em 22 de dezembro de 2019 . Recuperado em 27 de maio de 2019 . [...] o próximo nível de abstração da burocracia central: algoritmos de operação global.
  27. ^ Dietrich, Eric (1999). "Algoritmo". Em Wilson, Robert Andrew; Keil, Frank C. (eds.). A Enciclopédia do MIT das Ciências Cognitivas . Biblioteca MIT Cognet. Cambridge, Massachusetts: MIT Press (publicado em 2001). pág. 11. ISBN  9780262731447. Recuperado em 22 de julho de 2020 . Um algoritmo é uma receita, método ou técnica para fazer algo.
  28. Stone simplesmente exige que "deve terminar em um número finito de etapas" (Stone 1973:7-8).
  29. ^ Boolos e Jeffrey 1974,1999:19
  30. ^ cf Pedra 1972:5
  31. ^ Knuth 1973: 7 afirma: "Na prática, não queremos apenas algoritmos, queremos bons algoritmos ... um critério de bondade é o tempo necessário para executar o algoritmo ... outros critérios são a adaptabilidade do algoritmo aos computadores , sua simplicidade e elegância, etc."
  32. ^ cf Pedra 1973:6
  33. Stone 1973:7-8 afirma que deve haver "... um procedimento que um robô [isto é, computador] pode seguir para determinar precisamente como obedecer à instrução". Stone acrescenta finitude do processo e definição (sem ambiguidade nas instruções) a esta definição.
  34. ^ Knuth, loc. cit
  35. ^ Minsky 1967 , p. 105
  36. ^ Gurevich 2000:1, 3
  37. ^ Sipser 2006:157
  38. ^ Goodrich, Michael T. ; Tamassia, Roberto (2002), Algoritmo Design: Fundamentos, Análise e Exemplos de Internet , John Wiley & Sons, Inc., ISBN 978-0-471-38365-9, arquivado do original em 28 de abril de 2015 , recuperado em 14 de junho de 2018
  39. ^ Knuth 1973:7
  40. ^ Chaitin 2005:32
  41. ^ Rogers 1987:1-2
  42. Em seu ensaio "Calculations by Man and Machine: Conceptual Analysis" Seig 2002:390 credita essa distinção a Robin Gandy, cf Wilfred Seig, et al., 2002 Reflections on the foundations of mathematics: Essays in honor of Solomon Feferman , Association for Lógica Simbólica, AK Peters Ltd, Natick, MA.
  43. ^ cf Gandy 1980:126, Thesis and Principles for Mechanisms de Robin Gandy Church aparecendo nas pp. 123-148 em J. Barwise et al. 1980 The Kleene Symposium , North-Holland Publishing Company.
  44. ^ Um "robô": "Um computador é um robô que executa qualquer tarefa que pode ser descrita como uma sequência de instruções." cf Stone 1972:3
  45. O "ábaco" de Lambek é um "número infinito contável de locais (buracos, fios etc.) junto com um suprimento ilimitado de contadores (pedras, contas, etc.). Os locais são distinguíveis, os contadores não". Os buracos têm capacidade ilimitada, e de prontidão está um agente que entende e é capaz de executar a lista de instruções" (Lambek 1961: 295). Lambek faz referência a Melzak que define sua Q-machine como "um número indefinidamente grande de locais. .. um estoque indefinidamente grande de contadores distribuídos entre esses locais, um programa e um operador cujo único objetivo é executar o programa" (Melzak 1961: 283). BBJ (loc. cit.) adiciona a estipulação de que os buracos são "capaz de segurar qualquer número de pedras" (p. 46)., vol. 4, não. 3 de setembro de 1961.
  46. Se não houver confusão, a palavra "contadores" pode ser descartada e pode-se dizer que um local contém um único "número".
  47. ^ "Dizemos que uma instrução é eficaz se houver um procedimento que o robô pode seguir para determinar precisamente como obedecer à instrução." (Pedra 1972:6)
  48. ^ cf Minsky 1967: Capítulo 11 "Modelos de computador" e Capítulo 14 "Bases muito simples para computabilidade" pp. 255-281, em particular,
  49. ^ cf Knuth 1973:3.
  50. ^ Mas sempre precedido por SE-ENTÃO para evitar subtração imprópria.
  51. ^ Knuth 1973:4
  52. ^ Pedra 1972:5. Métodos para extrair raízes não são triviais: veja Métodos de cálculo de raízes quadradas .
  53. ^ Leeuwen, janeiro (1990). Manual de Ciência da Computação Teórica: Algoritmos e complexidade. Volume A. Elsevier. pág. 85. ISBN 978-0-444-88071-0.
  54. ^ John G. Kemeny e Thomas E. Kurtz 1985 De volta ao básico: A história, a corrupção e o futuro da língua , Addison-Wesley Publishing Company, Inc. Reading, MA, ISBN 0-201-13433-0 . 
  55. ^ Tausworthe 1977:101
  56. ^ Tausworthe 1977:142
  57. Knuth 1973 seção 1.2.1, expandida por Tausworthe 1977 nas páginas 100ff e Capítulo 9.1
  58. ^ cf Tausworthe 1977
  59. ^ Charneca 1908:300; A edição de 2005 de Hawking's Dover deriva de Heath.
  60. ^ "'Deixe que CD, medindo BF, deixe FA menor que ele mesmo.' Esta é uma abreviatura para dizer, meça ao longo de BA comprimentos sucessivos iguais a CD até que um ponto F seja alcançado tal que o comprimento restante FA seja menor que CD; em outras palavras, seja BF o maior múltiplo exato de CD contido em BA" (Heath 1908:297)
  61. Para tratamentos modernos usando divisão no algoritmo, veja Hardy e Wright 1979:180, Knuth 1973:2 (Volume 1), além de mais discussão sobre o algoritmo de Euclides em Knuth 1969:293–297 (Volume 2).
  62. Euclides aborda essa questão em sua Proposição 1.
  63. ^ "Elementos de Euclides, Livro VII, Proposição 2" . Aleph0.clarku.edu. Arquivado do original em 24 de maio de 2012 . Recuperado em 20 de maio de 2012 .
  64. Embora esta noção esteja em uso generalizado, não pode ser definida com precisão.
  65. ^ Knuth 1973: 13-18. Ele credita "a formulação de comprovação de algoritmos em termos de afirmações e indução" a R W. Floyd, Peter Naur, CAR Hoare, HH Goldstine e J. von Neumann. Tausworth 1977 toma emprestado o exemplo de Euclides de Knuth e estende o método de Knuth na seção 9.1 Provas formais (pp. 288-298).
  66. ^ Tausworthe 1997:294
  67. ^ cf Knuth 1973:7 (Vol. I), e suas análises mais detalhadas nas pp. 1969:294-313 (Vol. II).
  68. ^ O colapso ocorre quando um algoritmo tenta se compactar. O sucesso resolveria o problema da parada .
  69. ^ Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). "A arte (negra) da avaliação em tempo de execução: estamos comparando algoritmos ou implementações?". Conhecimento e Sistemas de Informação . 52 (2): 341–378. doi : 10.1007/s10115-016-1004-2 . ISSN 0219-1377 . S2CID 40772241 .  
  70. ^ Gillian Conahan (janeiro de 2013). "Melhor matemática torna as redes de dados mais rápidas" . Discovermagazine. com. Arquivado a partir do original em 13 de maio de 2014 . Recuperado em 13 de maio de 2014 .
  71. Haitham Hassanieh, Piotr Indyk , Dina Katabi e Eric Price, " ACM-SIAM Symposium On Discrete Algorithms (SODA) Arquivado em 4 de julho de 2013, no Wayback Machine , Kyoto, janeiro de 2012. Veja também a página da Web do sFFT Arquivada em 21 de fevereiro , 2012, no Wayback Machine .
  72. ^ Kowalski 1979
  73. ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Problemas da mochila | Hans Kellerer | Springer . Springer. doi : 10.1007/978-3-540-24777-7 . ISBN 978-3-540-40286-2. Arquivado do original em 18 de outubro de 2017 . Recuperado em 19 de setembro de 2017 .
  74. ^ Carroll, Sue; Daughtrey, Taz (4 de julho de 2007). Conceitos Fundamentais para o Engenheiro de Qualidade de Software . Sociedade Americana de Qualidade. págs. 282 e segs. ISBN 978-0-87389-720-4.
  75. ^ Por exemplo, o volume de um politopo convexo (descrito usando um oráculo de associação) pode ser aproximado com alta precisão por um algoritmo de tempo polinomial aleatório, mas não por um determinístico: ver Dyer, Martin; Frieza, Alan; Kannan, Ravi (janeiro de 1991), "A Random Polynomial-time Algorithm for Aproximating the Volume of Convex Bodies", J. ACM , 38 (1): 1–17, CiteSeerX 10.1.1.145.4600 , doi : 10.1145/102782.102783 , S2CID 13268711  .
  76. ^ George B. Dantzig e Mukund N. Thapa. 2003. Programação Linear 2: Teoria e Extensões . Springer-Verlag.
  77. ^ Tsípkin (1971). Adaptação e aprendizagem em sistemas automáticos . Imprensa Acadêmica. pág. 54. ISBN 978-0-08-095582-7.
  78. ^ Knuth, Donald E. (1972). "Algoritmos Babilônicos Antigos" (PDF) . Comum. ACM . 15 (7): 671-677. doi : 10.1145/361454.361514 . ISSN 0001-0782 . S2CID 7829945 . Arquivado do original (PDF) em 24 de dezembro de 2012.   
  79. Aaboe, Asger (2001), Episódios do início da história da astronomia , Nova York: Springer, pp. 40–62, ISBN 978-0-387-95136-2
  80. ^ Ast, Courtney. "Eratóstenes" . Universidade Estadual de Wichita: Departamento de Matemática e Estatística. Arquivado do original em 27 de fevereiro de 2015 . Recuperado em 27 de fevereiro de 2015 .
  81. ^ Chabert, Jean-Luc (2012). Uma história de algoritmos: do seixo ao microchip . Springer Science & Business Media. pág. 2. ISBN 9783642181924.
  82. ^ Davis 2000:18
  83. ^ Bolter 1984:24
  84. ^ Bolter 1984:26
  85. ^ Bolter 1984: 33-34, 204-206.
  86. Todas as citações de W. Stanley Jevons 1880 Elementary Lessons in Logic: Dedutiva e Indutiva , Macmillan and Co., Londres e Nova York. Republicado como um googlebook; cf Jevons 1880:199-201. Louis Couturat 1914 a Álgebra da Lógica , The Open Court Publishing Company, Chicago e Londres. Republicado como um googlebook; cf Couturat 1914:75-76 dá mais alguns detalhes; ele compara isso a uma máquina de escrever, bem como a um piano. Jevons afirma que o relato deve ser encontrado em 20 de janeiro de 1870, The Proceedings of the Royal Society .
  87. ^ Jevons 1880: 199-200
  88. Todas as citações de John Venn 1881 Symbolic Logic , Macmillan and Co., London. Republicado como um googlebook. cf Venn 1881:120-125. O leitor interessado pode encontrar uma explicação mais profunda nessas páginas.
  89. ^ Diagrama de Bell e Newell 1971:39, cf. Davis 2000
  90. ^ * Melina Hill, Valley News Correspondent, A Tinkerer Gets a Place in History , Valley News West Lebanon NH, quinta-feira, 31 de março de 1983, p. 13.
  91. ^ Davis 2000:14
  92. ^ van Heijenoort 1967:81ff
  93. Comentário de van Heijenoort sobre o Begriffsschrift de Frege, uma linguagem de fórmula, modelada sobre a aritmética, para o pensamento puro em van Heijenoort 1967:1
  94. ^ Dixon 1906, cf. Kleene 1952: 36-40
  95. ^ cf. nota de rodapé em Alonzo Church 1936a em Davis 1965:90 e 1936b em Davis 1965:110
  96. Kleene 1935–6 em Davis 1965:237ff, Kleene 1943 em Davis 1965:255ff
  97. ^ Igreja 1936 em Davis 1965:88ff
  98. ^ cf. "Processos Combinatórios Finitos - formulação 1", Post 1936 em Davis 1965: 289-290
  99. Turing 1936–37 em Davis 1965:116ff
  100. ^ Rosser 1939 em Davis 1965:226
  101. ^ Kleene 1943 em Davis 1965: 273-274
  102. ^ Kleene 1952:300, 317
  103. ^ Kleene 1952:376
  104. Turing 1936–37 em Davis 1965:289–290
  105. Turing 1936 em Davis 1965, Turing 1939 em Davis 1965:160
  106. ^ Hodges, p. 96
  107. ^ Turing 1936–37:116
  108. ^ a b Turing 1936–37 em Davis 1965:136
  109. ^ Turing 1939 em Davis 1965:160

Bibliografia [ editar ]

Leitura adicional [ editar ]

Links externos [ editar ]

Repositórios de algoritmos