Numa dízima periódica, o tamanho do período é definido como o número de algarismos que se repetem indefinidamente, na mesma ordem. Assim, por exemplo, temos que: $$\frac{1}{7} = 0 …

No pseudocódigo do Branch & Bound Simplificado no último slide desta apresentação, são mantidos um limitante superior e um inferior, ambos globais: branch_bound_simplificado(p …

Pessoal, como faço pra criar funções que podem receber quantos argumentos eu quiser, como a printf e a scanf, nas quais a cada % que coloco, devo adicionar um parâmetro?

Um heap é uma estrutura organizada em forma de árvore binária, com a propriedade extra de que o valor de cada nó deve ser maior do que o valor do nó de seus filhos (no caso de um h …

Os slides 121-122 desta apresentação ilustram como resolver o problema do empacotamento através da formulação por Programação Linear Inteira, relaxamento da restrição de integralid …

Amigos, Escrevi um programa que resolve a mochila binária em tempo polinomial. Contudo, mochila é NP-Completo. Eu não sou tão esperto assim, então me digam: por que não provei que …

Como posso fazer para verificar em um problema de maximização ou minimização se ele possui apenas uma solução?

Estou com dificuldade para entender porque um algoritmo funciona, e quero entender suficientemente bem para explicá-lo. Também não consegui resolver o problema por indução, mas sei …

O algoritmo ingênuo que a gente faz com papel e lápis multiplica um dígito do número "de baixo" por cada dígito do número "de cima", então dá $O(n^2)$. Depois soma as parcelas, que …

O exercício 5 da lista de reduções pede para encontrar uma redução linear do problema MAX (encontrar pontos maximais em um conjunto de pontos no plano) para o problema INTERVAL (en …

Na definição de problema como uma linguagem formal é feita a distinção entre algoritmos que aceitam uma linguagem e os que decidem uma linguagem. Aceitar uma linguagem L significa …

Para um problema ser NP, ele tem que ser verificável em tempo polinomial, isto é, o algoritmo de verificação tem que rodar em tempo polinomial. Por que o tamanho do certificado tam …

Na aula, falando sobre a cota inferior O(nlogn) da ordenação baseada em comparações, o professor salientou várias vezes que era para a ordenação de números distintos. A cota é d …

Eu sei que, no conjunto NP-completo, a redutibilidade é simétrica, isto é: $$P_1 \triangleright{}P_2 \implies P_2 \triangleright{} P_1$$ porque todos os problemas em NP podem ser …

Verificar um problema P em tempo polinomial prova que ele também é NP. Essa verificação é feita por um algoritmo que toma a entrada de P e um certificado como parâmetros. No caso d …