O que exatamente é um algoritmo?

Eu sei que isso pode parecer um pouco fora da caixa, na verdade eu costumava pensar sempre dentro da caixa, mas recentemente eu tenho pensado, possivelmente porque a ciência da computação oferece um alto grau de liberdade, sobre maneiras de conceber programas diferentes de os ensinados na universidade.

Considere a função fatorial. Normalmente, definimos essa função como

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

Eu chamaria isso de algoritmo e não tenho dúvida de que esse é o caminho certo para fazê-lo. Então, eu me perguntei "posso fazer isso em tempo constante?", Que deixou a seguinte idéia: e se eu tivesse uma matriz de números inteiros onde matriz [n] abriga o fatorial de n? Depois que essa matriz estiver preenchida, eu poderia simplesmente definir fato como:

 int fact(int n) 
 { 
 return array[n]; 
 } 

Ainda assim, parece que não posso chamar esse algoritmo, mesmo que ele forneça o resultado correto e opere em tempo constante O (1). Isso pode ser chamado de algoritmo? Caso contrário, por que não? Eu poderia argumentar que o preenchimento da matriz exigiria que um algoritmo operasse em algum momento, mesmo que estivesse em nosso cérebro para preenchermos a matriz, mas esse poderia ser o critério? Como esses aspectos são tratados formalmente?

Observe que esse conceito pode ser estendido a qualquer função que opere sobre números inteiros independentemente do número de argumentos; eu precisaria usar uma matriz se a função tivesse 2 argumentos ou 3 se a função tivesse 3 argumentos, e assim por diante. Além disso, essas soluções não são usadas simplesmente devido ao consumo de memória?

Além disso, não que as funções também abranjam qualquer programa com saída, pois eu poderia encontrar uma maneira de indexar cada saída possível que um programa poderia fornecer.

Como outro exemplo, considere o uso comum de uma matriz: aloque uma matriz inicialmente do tamanho N e, em seguida, adiciono elementos à matriz armazenando o valor no índice n e aumentando n em uma unidade. Então, se eu quiser procurar um elemento, não posso ajudar, mas para executar uma pesquisa linear sobre a matriz. Se, em vez disso, eu criei uma matriz de tamanho, por exemplo, Integer.MAXVALUE, para armazenar números inteiros, inicializados com zeros, eu poderia armazenar um número inteiro colocando 1 em seu índice. Então eu poderia procurar por sua existência na matriz no tempo O (1). E se eu quisesse colocar várias unidades do mesmo número? Não tem problema, eu apenas aumentaria o valor armazenado no índice inteiro.

A classificação seria um pouco mais complicada, mas, mesmo assim, a consulta e a adição podem ser realizadas em O (1).

A definição informal de um algoritmo em um livro popular é algo como:

Um algoritmo é (1) um procedimento computacional bem definido (2) que recebe alguma entrada e (3) produz alguma saída (4) para um problema computacional bem definido.

No seu primeiro caso, você codificou um algoritmo em que: O problema é encontrar o fatorial (parte 4 da definição), dado int n como entrada (parte 2 da definição), o código descreve o cálculo a ser executado (parte 1 da definição ), a saída é o fatorial (parte 3 da definição).

No seu segundo caso: O problema é encontrar o elemento do array na posição n (parte 4 da definição), dado n como entrada (parte 3 da definição), o código descreve o cálculo a ser executado (parte 2 da definição), o output é o elemento na posição n (parte 1 da definição).

Você armazenou fatoriais lá, portanto, fornece fatoriais. Se você tivesse armazenado quadrados ou cubos lá, obteria quadrados ou cubos; portanto, não se pode dizer que o segundo trecho por si só seja um algoritmo para calcular fatoriais.

E se você disser que uma matriz procura junto com uma matriz que tem f (n) na posição n é um algoritmo para calcular f (n), então você foi tão profundo que não há mais computação abaixo. Um procedimento computacional bem definido deve ser uma informação finita. Se uma matriz infinita de fatoriais fizer parte do procedimento computacional, isso não se aplica. Portanto, isso não seria um algoritmo para calcular fatoriais.

De maneira geral, um algoritmo é uma série de etapas para resolver um problema .

No CS, o seguinte é comumente entendido / assumido ao usar o termo algoritmo:

• O algoritmo tem descrição finita e um procedimento bem definido para executar suas etapas, dada qualquer instância do problema. (Mais abaixo.)
• Uma instância de problema fornecida como uma sequência finita (sequência de símbolos de entrada) e a saída do algoritmo pode ser codificada como uma sequência finita.
• Um problema é uma coleção de instâncias de problemas, juntamente com possíveis saídas "corretas" para cada instância. "Resolver" significa produzir uma saída correta.
• (Geralmente) as instâncias do problema podem ser arbitrariamente grandes (há um número infinito de instâncias possíveis que seu algoritmo finito deve resolver).

Antes da criação do CS, os matemáticos tinham os mesmos tipos de preocupações que você levanta e introduziam definições formais de computação para abordar essas preocupações. Assim, hoje em dia, podemos formalizar todas as suposições acima dizendo simplesmente "um algoritmo é um procedimento que pode ser implementado em uma máquina de Turing" . Esta é provavelmente a melhor resposta formal para sua pergunta.

Observe que a tese de Church-Turing diz que achamos que não há formalização "mais poderosa" de algoritmos do que a Máquina de Turing.

O exemplo fatorial entra em um modelo diferente de computação, chamado computação não uniforme. Uma Máquina de Turing é um exemplo de um modelo uniforme de computação: possui uma descrição única e finita e funciona para entradas de tamanho arbitrariamente grande. Em outras palavras, existe uma TM que resolve o problema para todos os tamanhos de entrada.

Agora, poderíamos considerar a computação da seguinte maneira: Para cada tamanho de entrada, existe uma TM (ou algum outro dispositivo computacional) que resolve o problema. Esta é uma pergunta muito diferente. Observe que uma única TM não pode armazenar o fatorial de cada número inteiro, uma vez que a TM possui uma descrição finita. No entanto, podemos fazer uma TM (ou um programa em C) que armazene os fatoriais de todos os números abaixo de 1000. Em seguida, podemos criar um programa que armazene os fatoriais de todos os números entre 1000 e 10000. E assim por diante.

Esses tipos de computação não uniformes são tipicamente modelados em CS teórico por circuitos. Você considera uma construção de circuito diferente para cada tamanho de entrada possível.

Modelos de computação não uniformes geralmente não são considerados algoritmos , mesmo que possam se encaixar na minha primeira frase. O motivo é que eles não se encaixam em nossas principais premissas: eles não têm uma descrição finita que pode ser implementada para resolver o problema "inteiro" para qualquer tamanho de entrada. Em vez disso, eles precisam de uma descrição cada vez maior à medida que o problema aumenta (como precisar de uma tabela de pesquisa maior). No entanto, eles ainda são modelos interessantes de computação.

Um algoritmo é um programa escrito em C que deve funcionar para qualquer comprimento de entradas (assumindo memória infinita e números inteiros ilimitados). Nos seus exemplos, se quiséssemos que o programa funcionasse para todos os comprimentos de entradas, a tabela na qual os resultados são armazenados seria infinitamente grande; os programas em C são sempre finitos; portanto, essa abordagem não pode ser usada.

A definição de algoritmo é muito resiliente: nos primeiros dias da teoria da recursão, muitas definições foram propostas e todas se mostraram equivalentes. Por exemplo, em vez de C, você pode usar máquinas de Turing. No entanto, esses modelos não são necessariamente equivalentes em termos de eficiência : um problema pode ser resolvido muito mais eficientemente em C do que usando máquinas de Turing. Quando estivermos interessados ​​em eficiência, devemos nos restringir a todos os modelos "próximos o suficiente" de C em relação ao tempo de execução. Por exemplo, se tivermos permissão para usar uma instrução que calcule em uma unidade de tempo, o modelo resultante ainda define o mesmo conjunto de funções computáveis, mas algumas funções (como n $n!$$n!$) podem ser computados com muito mais eficiência, em comparação com C.

Quando preocupados com o tempo real de execução em um computador real, devemos ter ainda mais cuidado, mas isso geralmente está além dos limites da ciência da computação teórica, infelizmente.

Se somos muito exigentes, precisamos esclarecer a diferença entre algoritmos e funções calculadas por algoritmos . Por exemplo, a função fatorial obtém como entrada um número natural e gera n ! . A função fatorial pode ser calculada por um algoritmo. Dizemos que uma função é computável se puder ser calculada usando algum algoritmo.$n$$n!$

Que noção de algoritmo devemos usar? Uma sugestão, descrita acima, é usar programas em C. Podemos chamar essa noção de C-computation. Computação de Turing é o que você obtém ao usar máquinas de Turing. Acontece que uma função é computável em C se e somente se for computável em Turing. É nesse sentido que esses dois modelos de computação são equivalentes. De fato, muitos outros modelos são equivalentes, por exemplo, todas as linguagens de programação de uso comum (assumindo memória infinita e variáveis ​​ilimitadas).

Dizemos que uma linguagem de programação P é Turing-complete é uma função que é computável em P se e somente se for computável em Turing. A hipótese de Church-Turing é uma afirmação informal de que todos os modelos de computação razoáveis, com descrição finita e tempo limitado, são completos para Turing. Seu modelo tem uma descrição finita, mas não leva tempo finito.

A parte importante da definição comum de um algoritmo que está faltando no seu é que a especificação deve ser finita e o tamanho da especificação não deve variar com o tamanho da entrada.

A memória pode ser arbitrariamente grande, assim como as entradas, mas para ser uma definição útil de um algoritmo, o espaço de código deve ser finito. Caso contrário, você terá o problema que você acabou de identificar.

$O(\log A)$$A$$O(\log n)$$O(\log n!)$$O(n (\log n)^2)$$s$$n = O(2^s)$$O(2^s~s^2)$$O(1)$

Algumas observações que podem ser úteis:

Problemas são declarações sobre entradas permitidas e saídas correspondentes. Eles são o que queremos resolver. Algoritmos são procedimentos computacionais. Podemos dizer que um algoritmo está correto com relação a um problema se ele aceitar entradas permitidas com relação ao problema e produzir saídas de acordo com a descrição do problema.

Ambos os seus exemplos são algoritmos, pois são claramente procedimentos computacionais. Se os algoritmos estão corretos ou não, depende de como você define o problema e como interpreta a representação do algoritmo. Algumas declarações de problemas:

1. $n$$n!$
2. $n > 0$$n! <$ INT_MAX$n!$

Algumas interpretações do seu primeiro trecho de código:

1. Esse é um pseudocódigo que se assemelha ao C / C ++, exceto nos detalhes. intrealmente significa "qualquer número inteiro", por exemplo.
2. Isso deve ser interpretado como se fosse um programa C / C ++ real.

A interpretação 1 está correta para a afirmação do problema 1, desde que o fatorial assuma o valor 1 para números negativos (caso contrário, poderíamos modificar a declaração do problema para restringir o domínio ou o algoritmo para explicar o comportamento desejado). A interpretação 2 está correta para a declaração do problema 2, com a mesma ressalva.

arrayarray$n$$n > 0$$n! <$ INT_MAX$n!$$n < 0$

$n$$n! \geq 2^{32}$$n! \geq 2^{64}$

$k$$k$$n$$kn$$k+n$

Um algoritmo é um programa escrito em uma linguagem completa de Turing que provadamente pára em todas as entradas válidas. Todas as linguagens de programação padrão são completas em Turing. A palavra se origina como uma tradução européia do nome al-Khwārizmī, matemático persa, astrônomo e geógrafo, cujo trabalho foi construído sobre o do matemático indiano do século VII Brahmagupta, que introduziu o sistema numérico indiano no mundo ocidental.

A questão parece ser basicamente sobre se as tabelas de pesquisa fazem parte dos algoritmos. Absolutamente! Nas máquinas de Turing (TM), as tabelas podem ser codificadas na tabela de estados da TM. A TM pode inicializar a fita com base em uma quantidade finita de dados armazenados na tabela de transição. No entanto, "algoritmos" que não são executados em entradas infinitas, apenas entradas finitas, são máquinas de estado finito (FSM) "trivialmente" .

Em poucas palavras : Um algoritmo é a parte construtiva de uma prova construtiva de que um determinado problema tem uma solução. A motivação para essa definição é o isomorfismo de Curry-Howard entre programas e prova, considerando que um programa só tem interesse se resolver um problema, mas é provável. Essa definição permite mais abstração e deixa algumas portas abertas com relação ao tipo de domínios que podem estar envolvidos, por exemplo, com propriedades de finitude.

Atenção . Estou tentando encontrar uma abordagem formal adequada para responder à pergunta. Eu acho que é necessário, mas parece que nenhum dos usuários que responderam até agora (inclusive eu, e alguns foram mais ou menos explícitos sobre isso em outras postagens) tem o background certo para desenvolver adequadamente os problemas relacionados a matemática construtiva, teoria das provas, teoria dos tipos e resultados como o isomorfismo de Curry-Howard entre provas e programas. Estou fazendo o meu melhor aqui, com quaisquer trechos de conhecimento que possuo (acredito) que possuo, e estou ciente das limitações desta resposta. Só espero dar algumas dicas de como acho que a resposta deve ser. Se você vir algum ponto que esteja claramente errado formalmente (provavelmente), deixe-me agora em um comentário - ou por e-mail.

Identificando alguns problemas

Uma maneira padrão de considerar um algoritmo é declarar que um algoritmo é um programa arbitrariamente especificado finitamente para algum dispositivo de computação , incluindo aqueles que não têm limitações na memória. O idioma também pode ser a linguagem da máquina do computador. Na verdade, basta considerar todos os programas para um dispositivo de computação completo Turing (o que implica não ter limitações de memória). Pode não fornecer todas as apresentações de algoritmos, no sentido de que os algoritmos devem ser expressos de uma forma que depende em seus detalhes do contexto de interpretação, mesmo teórico, pois tudo é definido até alguma codificação. Mas, como computará tudo o que há para ser computado, incluirá de alguma forma todos os algoritmos, até a codificação.

$\pi$

O problema é que $\pi$, possivelmente no sentido matemático de quase todos. Mas isso exigiria mais precisão nas definições.

Portanto, a verdadeira questão é saber quais são os algoritmos significativos. A resposta é que os algoritmos significativos são aqueles que resolvem um problema, calculando passo a passo a "solução", a "resposta", para esse problema. Um algoritmo é interessante se estiver associado a um problema que resolve.

Portanto, dado um problema formal, como obtemos um algoritmo que resolve o problema. De maneira explícita ou implícita, os algoritmos estão associados à idéia de que existe uma solução para o problema, que pode ser provada correta. Se nossas técnicas de prova são precisas é outra questão, mas tentamos pelo menos nos convencer. Se você se restringe à matemática construtiva, que é realmente o que temos que fazer (e é uma restrição axiomática muito aceitável para a maioria da matemática), a maneira de provar a existência de uma solução é passar por etapas de prova que realmente exibem uma construção que representa a solução, incluindo possivelmente outras etapas que a estabelecem.

Todos os programadores pensam algo como: se eu mexer com os dados de tal maneira, então eu obtenho esse widget que tem as propriedades certas por causa do teorema do gergelim e, ao executar essa transformação de preservação, obtenho a resposta desejada . Mas a prova é geralmente informal, e não trabalhamos todos os detalhes, o que explica por que um satélite tentou orbitar Marte no subsolo (entre outras coisas). Fazemos grande parte do raciocínio, mas na verdade mantemos apenas a parte construtiva que constrói a solução, e a descrevemos em uma linguagem de computador como o algoritmo que resolve o problema.

Algoritmos (ou programas) interessantes

Tudo isso foi para introduzir as seguintes idéias, que são objeto de muitas pesquisas atuais (das quais eu não sou especialista). A noção de " algoritmo interessante " usada aqui é minha, introduzida como um espaço reservado informal para definições mais precisas.

Um algoritmo interessante é a parte construtiva de uma prova construtiva de que um determinado problema tem uma solução . Isso significa que a prova deve realmente exibir a solução em vez de simplesmente provar sua existência, por exemplo, por contradição. Para mais detalhes, veja Lógica Intuicionista e Construtivismo em Matemática.

É claro que esta é uma definição muito restritiva, que considera apenas o que chamei de algoritmos interessantes. Por isso, ignora quase todos eles. Mas o mesmo acontece com todos os nossos livros sobre algoritmo. Eles tentam ensinar apenas alguns dos interessantes.

Dados todos os parâmetros do problema (dados de entrada), ele mostra como obter um resultado especificado passo a passo. Um exemplo típico é a resolução de equações (o algoritmo de nome é realmente derivado do nome de um matemático persa, Muḥammad ibn Mūsā al-Khwārizmī , que estudou a resolução de algumas equações). Partes da prova são usadas para estabelecer que alguns valores calculados no algoritmo têm algumas propriedades, mas essas partes não precisam ser mantidas no próprio algoritmo.

Obviamente, isso deve ocorrer dentro de uma estrutura lógica formalizada que estabeleça com que dados os dados são computados, quais são as etapas computacionais elementares permitidas e quais são os axiomas usados.

Voltando ao seu exemplo fatorial, ele pode ser interpretado como um algoritmo, embora trivial. A função fatorial normal corresponde a uma prova de que, dada alguma estrutura aritmética e dado um número inteiro n, existe um número que é o produto dos primeiros n números inteiros. Isso é bem direto, assim como a computação fatorial. Pode ser mais complexo para outras funções.

Agora, se você decidir tabular o fatorial, assumindo que pode, o que não é verdadeiro para todos os números inteiros (mas pode ser verdadeiro para algum domínio finito de valores), tudo o que você está fazendo é incluir em seus axiomas a existência do fatorial, definindo com um novo axioma seu valor para cada número inteiro, para que você não precise mais provar (portanto, calcular) qualquer coisa.

Mas um sistema de axiomas deve ser finito (ou pelo menos definido finitamente). E há uma infinidade de valores para fatorial, um por inteiro. Então você está com problemas para o seu sistema finito de axiomas se axiomatizar uma função infinita, ou seja, definida em um domínio infinito. Isso se traduz computacionalmente no fato de que sua possível pesquisa de tabela não pode ser implementada para todos os números inteiros. Isso mataria o requisito de finitude usual para algoritmos (mas deve ser tão rigoroso quanto frequentemente apresentado?).

Você pode optar por ter um gerador de axiomas finitamente definido para lidar com todos os casos. Isso equivaleria, mais ou menos, a incluir o programa fatorial padrão em seu algoritmo para inicializar a matriz conforme necessário. Isso é chamado de memorização pelos programadores. Na verdade, esse é o valor mais próximo possível do equivalente a uma tabela pré-computada. Pode-se entender que possui uma tabela pré-computada, exceto pelo fato de a tabela ser realmente criada no modo de avaliação lenta , sempre que necessário. Essa discussão provavelmente precisaria de cuidados um pouco mais formais.

Você pode definir suas operações primitivas como desejar (dentro de consistência com seu sistema formal) e atribuir a elas o custo que escolherem quando usados ​​em um algoritmo, para fazer análises de complexidade ou desempenho. Porém, se os sistemas concretos que realmente implementam seu algoritmo (um computador ou um cérebro, por exemplo) não podem respeitar essas especificações de custo, sua análise pode ser intelectualmente interessante, mas é inútil para o uso real no mundo real.

$2^{1000}$

Quais programas são interessantes

Essa discussão deve estar mais adequadamente vinculada a resultados como o isomorfismo de Curry-Howard entre programas e provas. Se algum programa é realmente uma prova de algo, qualquer programa pode ser interpretado como um programa interessante no sentido da definição acima.

No entanto, para meu entendimento (limitado), esse isomorfismo é limitado a programas que podem ser bem digitados em algum sistema de digitação apropriado, em que tipos corresponde a proposições da teoria axiomática. Portanto, nem todos os programas podem se qualificar como programas interessantes. Meu palpite é que é nesse sentido que um algoritmo deve resolver um problema.

Isso provavelmente exclui a maioria dos programas "gerados aleatoriamente".

É também uma definição um tanto aberta do que é um "algoritmo interessante". Qualquer programa que possa ser visto como interessante é definitivamente assim, pois existe um sistema de tipos identificado que o torna interessante. Mas um programa que não era tipável até o momento, poderia se tornar tipificado com um sistema de tipo mais avançado e, assim, se tornar interessante. Mais precisamente, sempre foi interessante, mas por falta de conhecimento do sistema de tipos adequado, não podíamos conhecê-lo.

No entanto, sabe-se que nem todos os programas são tipificáveis, pois é sabido que algumas expressões lambda, como a implementação do combinador Y , não podem ser digitadas em um sistema de tipos de som .

Essa visão se aplica apenas a formalismos de programação que podem ser diretamente associados a algum sistema de provas axiomático. Não sei como isso pode ser estendido a formalismos computacionais de baixo nível, como a Máquina de Turing. No entanto, como algoritmos e computabilidade geralmente são um jogo de codificação de problemas e soluções (pense em aritmética codificada no cálculo lambda ), pode-se considerar que qualquer computação formalmente definida que possa ser mostrada como uma codificação de um algoritmo também é um algoritmo. Tais codificações provavelmente usam apenas uma parte muito pequena do que pode ser expresso em um formalismo de baixo nível, como as Máquinas de Turing.

Um interesse dessa abordagem é que ela fornece uma noção de algoritmo mais abstrata e independente de questões de codificação real, de "representabilidade física" do domínio de computação. Assim, pode-se, por exemplo, considerar domínios com objetos infinitos, desde que haja uma maneira computacionalmente sólida de usá-los.

Não há uma boa definição formal de "algoritmo" no momento da redação. No entanto, há pessoas inteligentes trabalhando nisso.

O que sabemos é que, qualquer que seja um "algoritmo", ele fica em algum lugar entre "função matemática" e "programa de computador".

Uma função matemática é uma noção formal de um mapeamento de entradas para saídas. Portanto, por exemplo, "classificar" é um mapeamento entre uma sequência de itens que podem ser solicitados e uma sequência de itens que podem ser pedidos do mesmo tipo, que mapeia cada sequência para sua sequência ordenada. Esta função pode ser implementada usando algoritmos diferentes (por exemplo, classificação de mesclagem, classificação de heap). Cada algoritmo, por sua vez, pode ser implementado usando programas diferentes (mesmo com a mesma linguagem de programação).

Portanto, o melhor controle que temos sobre o que é um "algoritmo" é que é algum tipo de classe de equivalência em programas, onde dois programas são equivalentes se fizerem "essencialmente a mesma coisa". Quaisquer dois programas que implementam o mesmo algoritmo devem calcular a mesma função, mas o inverso não é verdadeiro.

Da mesma forma, há uma classe de equivalência entre algoritmos, em que dois algoritmos são equivalentes se eles computarem a mesma função matemática.

A parte difícil de tudo isso é tentar capturar o que queremos dizer com "essencialmente a mesma coisa".

Existem algumas coisas óbvias que devemos incluir. Por exemplo, dois programas são essencialmente os mesmos se diferirem apenas por renomeações de variáveis. A maioria dos modelos de linguagens de programação possui noções nativas de "equivalência" (por exemplo, redução beta e conversão eta no cálculo lambda), portanto, também devemos incluí-las.

Qualquer relação de equivalência que escolhemos, isso nos dá alguma estrutura. Os algoritmos formam uma categoria em virtude do fato de serem a categoria quociente de programas. Sabe-se que algumas relações equivalentes interessantes dão origem a estruturas categóricas interessantes; por exemplo, a categoria de algoritmos recursivos primitivos é um objeto universal na categoria de categorias. Sempre que você vê uma estrutura interessante como essa, sabe que essa linha de investigação provavelmente será útil.

Sua pergunta e descrição não se relacionam muito. O algoritmo é teórico e não se relaciona com nenhuma linguagem de programação. Algoritmo é um conjunto de regras ou etapas (procedimento) para resolver um problema. Seu problema pode ser resolvido de várias maneiras ou em muitos algoritmos.

Suas segundas soluções significam calcular primeiro uma grande variedade de fatoriais que inicialmente levarão muito tempo e depois armazená-lo. Ele consumirá mais armazenamento, mas, eventualmente, será mais rápido, enquanto o primeiro não consome armazenamento, mas consome energia da computação; portanto, você terá que escolher dependendo do seu ambiente.