Publiquei uma tarefa para a próxima quarta.
Como deveria ser a resposta para a execução de um algoritmo? Eu deveria me comportar como um computador e dar a resposta final, deveria mostrar passo a passo? Nesse caso, o que eu deveria considerar como passo?
Agora sobre algoritmos probabilísticos: qual seria a probabilidade de acerto que eu deveria ter para considerar razoável um algoritmo probabilístico?
Agora sobre algoritmos probabilísticos: qual seria a probabilidade de acerto que eu deveria ter para considerar razoável um algoritmo probabilístico?
A segunda pergunta eu sei responder.
Em algoritmos probabilísticos, considera-se uma probabilidade razoável de acerto algo que seja menor ou igual a 1/p( n), onde p( n) é um polinômio no tamanho da entrada n. Neste caso, podemos rodar o algoritmo p( n) vezes e usar a melhor resposta encontrada e a probabilidade de encontrar a resposta certa será alta.
Em algoritmos probabilísticos, considera-se uma probabilidade razoável de acerto algo que seja menor ou igual a 1/p( n), onde p( n) é um polinômio no tamanho da entrada n. Neste caso, podemos rodar o algoritmo p( n) vezes e usar a melhor resposta encontrada e a probabilidade de encontrar a resposta certa será alta.
Dê a resposta que o algoritmo daria.