Problemas de exemplo com soluções polinomiais e exponenciais e pegada minúscula?

8

Estou planejando executar um "experimento" ao ensinar minha classe de algoritmos neste outono, com um computador muito antigo e limitado (o principal fator limitante provavelmente é a memória - possivelmente tão baixa quanto 16 KB) e um moderno / padrão. A idéia é resolver um problema com um polinômio, rodando no computador lento, e um exponencial no rápido (e, é claro, fazer com que o lento vença).

O problema é encontrar um problema adequado - um em que os tempos de execução sejam realmente diferentes para instâncias de tamanho muito limitado (e, de preferência, onde as estruturas de dados sejam bastante simples; o computador primitivo é ... primitivo). Inicialmente, pensei em ordenar algoritmos (por exemplo, quadrático versus linear), mas isso exigiria instâncias muito grandes (a menos que eu fosse com o bogosort, por exemplo).

No momento, o único exemplo (bastante chato) que pensei é computar os números de Fibonacci da maneira inteligente e estúpida. Seria bom ter algo um pouco menos cansado / usado em excesso e, de preferência, algo (semi-) obviamente útil. Alguma idéia / sugestão?

Magnus Lie Hetland
fonte
Na verdade, eu estava pensando em usar as soluções pseudopolinomial (“linear no ranking de Fibonacci”) e superexponencial (recursiva) para o problema; o ponto principal é a óbvia diferença de complexidade, que permite que o computador mais fraco vença facilmente.
Magnus Lie Hetland
1
Correspondência bipartida de peso máximo (força húngara x força bruta)?
Jukka Suomela

Respostas:

6

Uma resposta que generaliza um pouco o comentário de Neel é procurar na área de pesquisa e programação dinâmica, repleta de algoritmos maravilhosos que apresentam um ótimo desempenho se você memoriza e terrivelmente se não - até a função fatorial chata que você estava pensando se enquadra nessa categoria.

É claro que você ficará limitado pelo limite de memória no computador lento, mas acho que isso significa apenas que você deve ter cuidado para ser suficientemente "mesquinho" com o computador veloz. Aqui estão algumas idéias específicas:

  • Dado um grande gráfico não direcionado, encontre um caminho entre dois pontos. O computador rápido implementa uma pesquisa aleatória (regular ou pode não terminar!) Através do gráfico, enquanto o computador lento realiza calmamente uma pesquisa de amplitude ou profundidade. Você provavelmente precisaria executar isso em várias tentativas para garantir que a diferença de desempenho seja perceptível.
  • Obtenha um gráfico direcionado e tente encontrar o caminho mais curto entre dois pontos: o computador rápido enumera todos os caminhos acíclicos (usando o algoritmo de detecção do ciclo da tartaruga e da lebre a cada passo, bwahahahaha) primeiro, e o computador lento executa pacientemente a fonte única mais curta caminho.
  • O algoritmo de distância de edição? Qualquer algoritmo de programação mais ingênuo que dinâmico pode provavelmente sufocar completamente aqui.

Uma última idéia é que você pode tentar alguns algoritmos no Prolog com e sem uma verificação de ocorrência (desnecessária). Mas se você mostrar a esses alunos como é maravilhoso que o Prolog sem uma verificação semanticamente significativa seja mais rápida, vou chorar. Além disso, isso geralmente é um linear versus quadrático, não polinomial versus exponencial.

Rob Simmons
fonte
9

Você pode fazer a correspondência de expressões regulares. Um combinador de retrocesso ingênuo pode facilmente ser levado a um comportamento exponencial nas entradas que um comparador mais inteligente pode manipular em tempo linear.

Neel Krishnaswami
fonte
5

Tente contar combinações perfeitas em gráficos planares, um problema que deve ser fácil de explicar. No caso planar, o algoritmo Fisher-Kastelyen-Temperley o soluciona em tempo polinomial, enquanto que para gráficos gerais o problema é # P-completo, ou seja, provavelmente não é uma maneira mais rápida do que fazer a contagem de força bruta. Basta executar o FKT na máquina lenta e a força bruta contando na rápida.

( Essa também é uma pergunta relacionada.)

Martin Schwarz
fonte
1

Se você está ensinando algoritmos, acho que você deve fazer algo simples, que ilustra a ideia. Acho que a sua ideia de algoritmo de classificação é muito boa e provavelmente funcionará se você tentar algoritmos não recursivos no computador primitivo.

Atualmente, estou comparando algoritmos de classificação e tenho o Heap Sort sendo executado com 17.000 elementos em um computador com 32kb de ram.

Eu tentaria classificar inserção vs Heap Sort.

Topo
fonte
Mas o tipo de inserção de 17000 elementos em um computador moderno é bastante rápido. (A questão já faz alusão a isso.)
Radu Grigore