Existe um método para análise automática de algoritmos em tempo de execução?

10

Gostaria de saber, existe um método para análise automática de tempo de execução que funciona pelo menos em um subconjunto relevante de algoritmos (algoritmos que podem ser analisados)?

Eu pesquisei "Análise automática de algoritmo", o que me deu isso, mas é muito matemático. Eu só quero um exemplo simples no psuedocode que eu possa entender. Pode ser muito específico, mas achei que valia a pena tentar.

algorithms algorithm-analysis reference-request runtime-analysis Nathvi
fonte
Não vejo como o estresse entre "any" e "an" esclarece o que você realmente procura. Se algum procedimento de decisão estiver vinculado a um algoritmo específico B, não haverá entrada real e a resposta será sempre a mesma. Eu acho que o que você quer perguntar é se 'algum algoritmo dentro de alguma classe de algoritmos' onde a classe está vinculada / conhecida. (editar: isso também foi apontado no comentário do meu mhum).
Nicholas Mancuso
2
A ambiguidade no uso de "an" e "any" é exatamente o motivo pelo qual os quantificadores foram inventados.
Nate Eldredge
2
Eu editei a pergunta para focar nas partes relevantes. Observe como uso exatamente a matemática zero para expressar o problema com precisão (até onde você especificou sua pergunta até agora) e de forma sucinta. Agora, a questão ainda está mal colocada: é claro que existem tais algoritmos. Por exemplo, existe um algoritmo simples que analisa todos os algoritmos da classe (muito relevante) de algoritmos que são executados no tempo . Portanto, você claramente precisa colocar algumas restrições nos conjuntos de entradas. (Observe que pode não haver "um exemplo simples no código psuedoc que eu possa entender".)Θ(nlog⁡n)
Raphael

Respostas:

12

A ferramenta COSTA faz exatamente isso, embora falhe em muitos casos, como você pode imaginar, devido a problemas de computabilidade . Existem muitos artigos sobre isso; Análise de custos do bytecode Java por E. Albert, P. Arenas, S. Genaim, G. Puebla, D. Zanardini é um bom ponto de partida.

A abordagem adotada é inferir uma recorrência em tempo de execução do código Javabyte, convertendo-o em um formulário fechado. A ferramenta também calcula os limites de uso de espaço.

Dave Clarke
fonte
8
@Nathvi Eu entendo que você está irritado com alguns comentários, que eu concordo que não eram realmente necessários, mas você também deve tomar cuidado para não usar o termo "pedante drivel" no trabalho de cientistas muito respeitáveis ​​(e, aliás, na minha resposta). Você tem o direito de não gostar de matemática, mas é improvável que você vá muito longe sem ela, e palavras depreciativas gratuitas não ajudam ninguém.
babou
12

Nenhum algoritmo pode decidir se um determinado algoritmo é interrompido ou não, portanto, em particular, nenhum algoritmo pode analisar rigidamente a complexidade de um determinado algoritmo.

Yuval Filmus
fonte
2
Minha pergunta não é sobre um algoritmo de entrada arbitrário, que, se fosse, sua resposta estaria correta devido ao problema de interrupção. Você estaria correto se minha pergunta fosse formulada: "Existe um algoritmo A que aceita qualquer algoritmo B e gera a complexidade de tempo do algoritmo B?"
Nathvi
6
Se o algoritmo B for fixo, verifique se existe um algoritmo A. Basta ter um algoritmo que não faça nada além de imprimir "O (n)" ou qualquer medida de complexidade que corresponda a B. Se houver apenas uma entrada possível para o algoritmo A, então precisamos apenas de uma saída.
Mhum
5
@Athvi também não estava claro para mim - eu também entendi a pergunta como "existe um algoritmo para encontrar a complexidade de qualquer outro algoritmo" e ainda não entendo sua pergunta real . Se você gosta de contar votos positivos, aparentemente> 2 pessoas o interpretaram dessa maneira. Em caso de confusão, é realmente uma boa ideia editar sua pergunta; caso contrário, apenas as pessoas que lerem essa conversa (em vez de todos que lerem a pergunta) entenderão o que você está perguntando e darão boas respostas. Parece que você sentiu a resposta de DW era hostil - FWIW, eu não acho que se destinava a ser ..
JKFF
6
@ignis A resposta pode estar incompleta, mas a frase que Yuval escreveu está absolutamente correta. E o problema da parada não é um caso secundário exótico: é a própria essência da computação.
precisa saber é o seguinte
3
@nikie Isso não ajuda em nada nesta questão; os limites de tempo de execução são indecidíveis, mesmo no conjunto de todos os algoritmos que terminam sempre.
Raphael
9

Conheço uma abordagem para a análise de caso médio (semi) automatizada, a saber, MaLiJAn ¹. É muito parecido com o tipo de análise que Knuth usa no TAoCP. A idéia central é

  • modelar o programa (fluxo) como cadeia de Markov,
  • treine suas probabilidades de transição para alguns tamanhos de entrada fixos contando um conjunto de execuções de programa (que gera estimadores de probabilidade máxima ),n
  • extrapolar para funções probility emn e
  • use álgebra computacional para derivar o custo médio (escreva essas funções).

Observe que apenas medidas de custo aditivo (por exemplo, comparações, "tempo") funcionam e apenas o valor esperado é preciso (assumindo funções perfeitas de probabilidade), momentos mais altos não podem ser derivados.

Todas as etapas, exceto a extrapolação, são rigorosas [2] e foi demonstrado que o método reproduz resultados bem conhecidos com alta precisão - dados dados de amostra aleatória adequados, é claro. Embora não haja prova ou mesmo garantia de aproximação nos resultados (a etapa de extrapolação é, até o momento, puramente heurística), os resultados obtidos com a ferramenta servem bem para experimentar algoritmos difíceis de analisar e formular hipóteses [3,4].

  1. Divulgação completa: Sou membro desse grupo de pesquisa e participei do desenvolvimento da ferramenta.
  2. Análise de máxima verossimilhança de algoritmos e estruturas de dados por U. Laube e M. Nebel (2010) [ pré-impressão ]
  3. Engenharia de Quicksort Dual Pivot do Java 7 usando MaLiJAn por S. Wild et al (2012) [ pré-impressão ]
  4. Análise de máxima verossimilhança do método Ford – Fulkerson em gráficos especiais de U. Laube e M. Nebel (2015) [ pré-impressão ]
Rafael
fonte
Essas técnicas vêm com uma estimativa da precisão da análise de caso médio?
Martin Berger
@MartinBerger Infelizmente, não. Temos algumas idéias sobre isso, mas nada solidificado e muito menos implementado ainda. Observe que é fácil enganar qualquer método que verifique apenas finitamente muitos tamanhos de entrada; portanto, há pouca esperança em geral. Com suposições sobre as funções de tempo de execução e / ou conjuntos de dados, algo pode ser possível. A ferramenta deve pelo menos ser capaz de dizer "precisa de mais dados".
Raphael
Isso é interessante. Espero que você faça esse trabalho adicional.
Martin Berger
8

Obviamente, como observado por Yuval Filmus, não se deve esperar uma solução geral para esses problemas. Mas, como geralmente é o caso, podem ser encontradas soluções para subconjuntos interessantes do caso geral.

Eu não sou especialista em nada, nem tenho um conhecimento significativo nessa área, pois conheço algum trabalho desse tipo. Trata-se de análise automática de complexidade média, e o trabalho foi realizado por Philippe Flajolet e seus colegas.

Pelo que entendi quando me foi explicado, os autores projetaram uma linguagem pequena (nada de Turing completo como você poderia esperar, mas significativo o suficiente) para que qualquer algoritmo escrito dentro da restrição dessa linguagem pudesse ter sua complexidade média analisada automaticamente. O sistema foi chamado na época Lambda-Upsilon-Omega, ou seja, (eu desamarro).λυ´ω

Um artigo que encontrei na web é o artigo de 1990: análise automática de casos médios de algoritmos por Philippe Flajolet, Paul Zimmermann e Bruno Salvy .

Eu esperaria que trabalhos posteriores estendessem esse trabalho, mas eu realmente não sei. O trabalho foi bastante citado e a pesquisa na Web deve render trabalhos mais recentes sobre o mesmo tópico.

Agora, receio que o trabalho de Flajolet e seus colegas tenha sido muito matemático, e eu não esperaria uma leitura muito fácil.

babou
fonte