Eu tenho trabalhado na introdução de alguns resultados da complexidade computacional na biologia teórica, especialmente evolução e ecologia , com o objetivo de ser interessante / útil para os biólogos. Uma das maiores dificuldades que enfrentei é justificar a utilidade da análise de pior caso assintótica para limites inferiores. Existem referências na extensão do artigo que justifiquem limites inferiores e análise assintótica de pior caso para um público científico?
Estou realmente procurando uma boa referência que possa adiar na minha escrita, em vez de ter que passar pelas justificativas no espaço limitado que tenho disponível (já que esse não é o ponto central do artigo). Também estou ciente de outros tipos e paradigmas de análise, por isso não estou buscando uma referência que diga que o pior caso é a "melhor" análise (já que existem configurações quando muito não é), mas que não é. completeletely inútil: ele ainda pode nos dá idéias teoricamente úteis sobre o comportamento de reais algoritmos em reais entradas. Também é importante que a escrita seja direcionada a cientistas gerais e não apenas engenheiros, matemáticos ou cientistas da computação.
Como exemplo, o ensaio de Tim Roughgarden, que introduz a teoria da complexidade para economistas, está no caminho certo para o que eu quero. No entanto, apenas as seções 1 e 2 são relevantes (o restante é muito específico da economia) e o público-alvo é um pouco mais confortável com o pensamento à prova de teoremas e lemas do que a maioria dos cientistas [1] .
Detalhes
No contexto da dinâmica adaptativa da evolução , conheci dois tipos específicos de resistência de biólogos teóricos:
[A] "Por que eu deveria me importar com o comportamento de arbitrário ? Eu já sei que o genoma tem pares de bases (ou talvez genes) e não mais."n = 3 * 10 9 n = 2 * 10 4
Isso é relativamente fácil de ignorar com o argumento "podemos imaginar aguardando segundos, mas não ". Mas, um argumento mais intrincado pode dizer que "claro, você diz que se importa apenas com um específico , mas suas teorias nunca usam esse fato, elas apenas usam que ele é grande, mas finito, e é com a sua teoria que estamos estudando". análise assintótica ".2 10 9 n
[B] "Mas você só mostrou que isso é difícil, construindo esse cenário específico com esses gadgets. Por que devo me preocupar com isso, em vez da média?"
Essa é uma crítica mais difícil de abordar, porque muitas das ferramentas comumente usadas neste campo são provenientes da física estatística, onde é frequentemente seguro assumir uma distribuição uniforme (ou outra simples específica). Mas a biologia é "física com história" e quase tudo não está em equilíbrio ou "típico", e o conhecimento empírico é insuficientepara justificar suposições sobre distribuições sobre entradas. Em outras palavras, quero um argumento semelhante ao usado contra a análise de casos médios de distribuição uniforme na engenharia de software: "modelamos o algoritmo, não podemos construir um modelo razoável de como o usuário interagirá com o algoritmo ou qual será sua distribuição. de insumos será; isto é, para psicólogos ou usuários finais, não para nós ". Exceto neste caso, a ciência não está em uma posição em que o equivalente a 'psicólogos ou usuários finais' exista para descobrir as distribuições subjacentes (ou se isso é significativo).
Notas e perguntas relacionadas
- O link discute ciências cognitivas, mas a mentalidade é semelhante em biologia. Se você navegar pela Evolution ou Journal of Theoretical Biology , raramente verá a prova de teoremas e lemas, e quando o fizer, será tipicamente apenas um cálculo, em vez de algo como uma prova de existência ou construção complexa.
- Paradigmas para análise de complexidade de algoritmos
- Outros tipos de análise de tempo de execução além do pior caso, caso médio, etc?
- Ecologia e evolução através da lente algorítmica
- Por que os economistas devem se preocupar com a complexidade computacional
fonte
Respostas:
Minha opinião pessoal (e tendenciosa) é que a análise assintótica de pior caso é um trampolim histórico para tipos de análise mais úteis. Portanto, parece difícil justificar para os praticantes.
Provar limites para o pior caso geralmente é mais fácil do que provar limites para definições "boas" de caso médio. A análise assintótica também costuma ser muito mais fácil do que provar limites razoavelmente rígidos. A análise assintótica no pior dos casos é, portanto, um ótimo ponto de partida.
O trabalho de Daniel Spielman e Shanghua Teng na análise simplificada do Simplex me parece um prenúncio do que pode acontecer quando começamos a entender melhor a forma de um problema: enfrentar o pior dos casos primeiro permite uma compreensão mais sutil. desenvolvido. Além disso, como Aaron Roth sugeriu nos comentários, se o comportamento "usual" de um sistema for significativamente diferente de seu pior caso, o sistema ainda não está completamente especificado e é necessário mais trabalho para melhorar o modelo. Portanto, ir além do pior caso geralmente parece importante como um objetivo a longo prazo.
No que diz respeito à análise assintótica, ela geralmente serve para manter uma prova longa e confusa, livre de detalhes perturbadores. Infelizmente, atualmente não parece haver uma maneira de recompensar o trabalho tedioso de preencher os detalhes para obter as constantes reais, de modo que raramente parece ser feito. (Os limites de página também funcionam contra isso.) A análise cuidadosa dos detalhes de um limite assintótico levou a algoritmos reais, com bons limites para as constantes, então eu pessoalmente gostaria de ver mais desse tipo de trabalho. Talvez se mais provas fossem formalizadas usando sistemas assistentes de prova, as constantes poderiam ser estimadas com menos esforço adicional. (Ou os limites nas constantes, ao longo das linhas de Gowers para o lema da regularidade de Szemerédi, podem se tornar mais rotineiros.) Existem também maneiras de provar limites inferiores livres de constantes, usando modelos de máquina mais explícitos (como autômatos determinísticos de estado finito). No entanto, esses limites inferiores (quase) exatos para modelos mais gerais de computação podem exigir muito trabalho ou estar totalmente fora de alcance. Isso parece ter sido buscado em 1958-1973 durante o primeiro auge da teoria dos autômatos, mas, tanto quanto posso dizer, desde então foi largamente deixado em paz.
fonte
Limites inferiores e análise de pior caso geralmente não andam juntos. Você não diz que um algoritmo levará pelo menos tempo exponencial no pior dos casos, portanto é ruim. Você diz que pode demorar no máximo um tempo linear no pior dos casos e, portanto, é bom. O primeiro só é útil se você quiser executar seu algoritmo em todas as entradas possíveis, e não apenas em uma entrada média.
Se você deseja usar limites inferiores para demonstrar defeitos, deseja uma análise de melhor caso ou uma análise de caso médio. Você pode simplificar as coisas, baseando-se no argumento de @ PeterShor de que o pior e o médio geralmente são muito semelhantes e fornece uma lista de algoritmos para os quais isso é verdade. (Ex: todos os tipos clássicos, além do quicksort.)
Quanto à demonstração de que os assintóticos são importantes quando comparados a entradas e fatores constantes, meu artigo favorito sobre o tema é "Pérolas de programação: técnicas de design de algoritmos", de Jon Bentley. Ele apresenta quatro soluções diferentes para um problema simples de matriz e demonstra como a abordagem linear aniquila a cúbica. Ele chama sua mesa de "A Tirania dos Assintóticos", após o termo usado pelos físicos para a intratabilidade da equação do foguete. Eu uso este exemplo para motivar a busca de melhores algoritmos para estudantes pré-universitários.
Será que um cientista que não é de informática lê um artigo que contém código e sabe pular os detalhes de baixo nível para obter uma visão geral? Eu não sei. Talvez haja uma apresentação melhor em outro lugar. Mas acho que esse é um recurso decente para citar.
E se eles argumentam que não se importam com n arbitrariamente grande, faça com que executem Fibonacci não memorizados recursivos em 3 x 10 9 pares de bases e digam que é O (1), pois o tamanho da sequência de DNA é fixo. ;)
fonte
Muitos concordaram que este é um tópico importante a ser pesquisado / abordado, mas parece que ainda não foi muito. algumas referências de estilo / cobertura / público / formalidade variados, não exatamente conforme solicitado, mas um pouco próximas (melhor visualizadas online até o momento em pesquisas médias, esperamos ouvir outras melhores; mais notas abaixo):
A complexidade dos algoritmos Atkinson (infelizmente, apenas uma referência à biologia no artigo, mas pode ser suficiente em termos gerais de ciência / engenharia)
Complexidade e algoritmos J. Diaz. 100 slides. amplo; alguém poderia extrair os relevantes em particular.
em outras palavras, existe uma espécie de introdução / pesquisa / visão geral da lente teórica da complexidade em estreita combinação / conjunção / companheira com a lente algorítmica avançada da ciência, algo como "Teoria da complexidade para cientistas, engenheiros e pesquisadores" ?
existem boas referências na "lente algorítmica" anterior que você citou, por exemplo, Papadimitriou, mas não parece uma referência altamente satisfatória por um especialista na área que tenha sido escrita na última "lente de complexidade" ... ainda (talvez alguma "elite" " membro deste site considerará isso como seu próximo livro ou projeto em papel).
note também que existem muitas referências à relevância P vs NP fora da teoria da complexidade e em outros campos científicos que poderiam ser usados de alguma forma para esse propósito. irá adicioná-los nos comentários, se houver algum interesse.
fonte