Estou interessado no histórico inicial de resultados publicados sobre compensações de espaço-tempo de uso geral. Em particular, quero saber quem primeiro descreveu o seguinte tipo de algoritmo para avaliar uma computação com um gráfico de fluxo de dados arbitrário com grau O (1) usando espaço proporcional à profundidade (não largura) do gráfico de fluxo de dados (mais o tamanho da entrada) fazendo uma avaliação direta e profunda da profundidade do gráfico. Em mais detalhes:
Seja o gráfico do fluxo de dados G = (V, E) onde V é o conjunto de vértices computacionais (valores de dados de tamanho O (1)) e E é o conjunto de arestas (v_p, v_s), de modo que o valor do sucessor o vértice v_s \ in V depende imediatamente do valor do vértice predecessor v_p \ in V. Seja v_f o vértice sem sucessores representando o resultado final da computação. Seja eu um conjunto de vértices de entrada ordenados canonicamente (sem predecessores), pois i \ in I é fornecido seu valor x (i). Para outros vértices v \ in S, seus valores são definidos por x (v) = F_v (x (P (v))) em que P (v) é uma lista canonicamente ordenada dos predecessores de v, x (P (v)) é a lista correspondente de seus valores e F_v é a função do vértice que determina seu valor como uma função da lista de valores de seus predecessores.
Dada essa configuração, o algoritmo em questão é bastante óbvio e trivial:
def eval(v): (v can be any vertex in the graph)
let P := P(v), the list of v's predecessors (has O(1) elements by assumption)
let val[] := uninitialized array of |P| data values
for each predecessor p[i] in P (i.e. for i from 1 to |P|):
if p[i] is in I then
val[i] = x(p) (look up a given input)
else
val[i] = eval(p[i]) (recursive call)
return F_v(val[]) (apply vertex's function to list of predecessor values)
Isso leva a O (d) níveis de recursão, onde d é a profundidade do gráfico do fluxo de dados e o espaço da pilha em cada nível é constante devido às suposições de que o grau do gráfico do fluxo de dados é constante e que o tamanho de os valores dos dados são constantes. (Para simplificar aqui, estou tratando o tamanho das referências de vértice também como constantes, mesmo que sejam realmente logarítmicas em | V |.) Assim, o uso total de espaço é O (d + | I |). A largura máxima do gráfico de fluxo de dados pode ser exponencialmente maior que isso; portanto, na melhor das hipóteses, essa técnica pode proporcionar uma economia de espaço bastante extrema, em comparação com, por exemplo, uma avaliação ambiciosa e avançada do gráfico (que pode ser a cada etapa, avalie todos os vértices que dependem diretamente apenas de vértices cujos valores já são conhecidos,
De qualquer forma, é uma técnica bastante óbvia, pelo menos em retrospecto, e certamente é conhecida há muito tempo, mas eu estava me perguntando o quanto a literatura sobre isso vai voltar. Alguém conhece a história inicial de resultados desse tipo (descritos nesses termos ou outros análogos) e qual seria uma boa referência para se aprofundar nesse assunto?
Muito obrigado, -Mike Frank
fonte