Lista de Exercicios - Algoritmos de Otimizacao e NP-Completude

PERGUNTA 1 A ideia por traz de uma como o nome sugere é um para um problema já recurso reduzir problema resolvido minimização minimizar custo otimizado redução reduzir novo problema conhecido otimização otimizar algoritmo resolvido indução induzir caso base conhecido PERGUNTA 2 Dizer que um problema é significa dizer que ele está em e que todo problema em se em tempo polinomial para este problema NPDifícil NP NP reduz NPcompleto NP NP reduz P NP NPDifícil reduz NP NPCompleto NP compara P NP NPCompleto compara PERGUNTA 3 Em relação à NPCompletude podemos afirmar que I Se algum problema NPcompleto puder ser resolvido em tempo polinomial então todo problema em NP poderá ser resolvido em tempo polinomial II Para mostrarmos que um problema é NPCompleto temos que mostrar que o problema está em NP e que todo problema em NP se reduz a esse problema III A primeira prova de NPCompletude foi apresentada para o problema CLIQUE As afirmações I e II estão corretas Somente a afirmação I está correta Todas as afirmações estão corretas As afirmações II e III estão corretas Nenhuma das afirmações está correta PERGUNTA 4 Suponha que conseguimos reduzir em tempo polinomial um problema A para um problema B Então podemos afirmar I Se existe um algoritmo eficiente para B então necessariamente existe um algoritmo eficiente para A II Se não existe um algoritmo eficiente para A então não existe um algoritmo eficiente para B III Se não existe um algoritmo eficiente para B não podemos afirmar nada sobre um algoritmo para A Todas as afirmações estão corretas Somente a afirmação I está correta Nenhuma das afirmações está correta As afirmações I e III estão corretas As afirmações II e III estão corretas PERGUNTA 5 Suponha que conseguimos reduzir em tempo polinomial um problema A para um problema B Se existe um algoritmo eficiente para A então não podemos afirmar nada sobre o algoritmo B o algoritmo para B é tão eficiente quanto o algoritmo para A não existe um algoritmo eficiente para B existe um algoritmo eficiente para B A e B produzem soluções ótimas PERGUNTA 6 Em relação às classes de problemas P e NP podemos afirmar que I Todos os problemas que podem ser resolvidos em tempo polinomial pertencem à classe P II Todo problema que é NP também é um problema P III Um problema NP Completo é um problema NPDifícil que está em NP Somente a afirmação I está correta As afirmações II e III estão corretas Todas as afirmações estão corretas As afirmações I e III estão corretas Nenhuma das afirmações está correta LISTA 1 A ideia por trás de uma como nome sugere é um para um problema já a recursão reduzir problema resolvido b minimização minimizar custo otimizado c redução reduzir novo problema conhecido d otimização otimizar algoritmo resolvido e indução induzir caso base conhecido RESOLUÇÃO Vamos preencher a frase com cada uma das alternativas e ver o que melhor a preenche a A ideia por trás de uma recursão como nome sugere é reduzir um problema para um problema já resolvido Recursão é algo que se repete de forma análoga de forma a se resolver um problema baseado em uma versão menor do mesmo problema logo a alternativa A é falsa b A ideia por trás de uma minimização como nome sugere é minimizar um custo para um problema já otimizado Se um problema já está otimizado seu custo não pode ser reduzido então essa alternativa está errada c A ideia por trás de uma redução como nome sugere é reduzir um novo problema para um problema já conhecido Usamos a redução para através de algoritmos simples reduzir um problema a ser estudada a um problema já conhecido e com um algoritmo conhecido Logo essa alternativa é a correta d A ideia por trás de uma otimização como nome sugere é otimizar um algoritmo para um problema já resolvido A otimização na verdade serve para alterar a implementação de um algoritmo de forma a manter o funcionamento do mesmo melhorando apenas sua eficiência e A ideia por trás de uma indução como nome sugere é induzir um caso base para um problema já conhecido A indução é uma técnica usada para provar uma propriedade de forma ampla baseado no funcionamento da pro priedade em alguns casos então essa alternativa também está errada Logo a alternativa C é a correta 1 2 Dizer que um problema é significa dizer que ele está em e que todo problema em se em tempo polinomial para esse problema a NPDifícil NP NP reduz b NPCompleto NP NP reduz c P NP NPDifícil reduz d NP NPCompleto NP compara e P NP NPCompleto compara RESOLUÇÃO Um problema NPCompleto é aquele problema NP para o qual todo problema em NP pode ser reduzido em tempo polinomial Ou seja a alternativa B é a correta 2 3 Em relação à NPcompletude podemos afirmar que I Se algum problema NPcompleto puder ser resolvido em tempo polinomial então todo problema em NP poderá ser resolvido em tempo polinomial II Para mostrarmos que um problema é NPCompleto temos que mostrar que o problema está em NP e que todo problema em NP se reduz a esse problema III A primeira prova de NPCompletude foi apresentada par ao problema CLIQUE a As afirmações I e II estão corretas b Somente a afirmação I está correta c Todas as afirmações estão corretas d As afirmações II e III estão corretas e Nenhuma das afirmações está correta RESOLUÇÃO Conforme vimos no exercício anterior um problema NPCompleto é aquele problema NP para o qual todo problema em NP pode ser reduzido em tempo polinomial Se encontrarmos uma solução polinomial para um problema NPCompleto toda a classe NP passa automaticamente a ter solução polinomial Ou seja a afirmação I está correta A afirmação II estaria correta se tivesse citado que a redução deve acontecer em tempo polinomial logo da forma como foi escrita é falsa Estando a primeira afirmação correta e a segunda errada já podemos concluir que a alternativa B é a correta 3 4 Suponha que conseguimos reduzir em tempo polinomial um problema A para um problema B Então podemos afirmar I Se existe um algoritmo eficiente para B então necessariamente existe um algoritmo eficiente para A II Se não existe um algoritmo eficiente para A então não existe um algoritmo eficiente para B III Se não existe um algoritmo eficiente para B não podemos afirmar nada sobre um algoritmo para A a Todas as afirmações estão corretas b Somente a afirmação I está correta c Nenhuma das afirmações está correta d As afirmações I e III estão corretas e As afirmações II e III estão corretas RESOLUÇÃO Se existe um algoritmo eficiente para B e A pode ser reduzido em tempo polinomial para B então existe um algoritmo polinomial para A que aqui chamamos de eficiente visto que estamos comparando com problemas NP Logo a afirmação I é verdadeira Se não existe um algoritmo eficiente para A mesmo sabendo que podemos reduzir por B para isso então não pode existir um eficiente para B pois se existisse existiria também um eficiente para A Logo a afirmação II é verdadeira Se não existe um algoritmo eficiente para B não significa que não exista para A pois podemos reduzir de A para B e não necessariamente o contrário então pode existir um algoritmo eficiente para A que não tenha a ver com o algoritmo de B Logo a afirmação III é verdadeira Dessa forma as três afirmações são verdadeira o que nos leva à alternativa A como correta 4 5 Suponha que conseguimos reduzir em tempo polinomial um problema A para um problema B Se existe um algoritmo eficiente para A então a não podemos afirmar nada sobre o algoritmo B b o algoritmo para B é tão eficiente quanto o algoritmo para A c não existe um algoritmo eficiente para B d existe um algoritmo eficiente para B e A e B produzem soluções ótimas RESOLUÇÃO Conseguimos reduzir de A para B mas só sabemos que existe um algoritmo eficiente para A Nesse caso não podemos afirmar nada sobre B pois a redição não é recíproca isto é redução de A para B em tempo polinomial não significa redução de B para A nesse mesmo tempo polinomial Dessa forma a alternativa A é a correta 5 6 Em relação às classes de problemas P e NP podemos afirmar que I Todos os problemas que podem ser resolvidos em tempo polinomial pertencem à classe P II Todo problema que é NP também é um problema P III Um problema NPCompleto é um problema NPDifícil que está em NP a Somente a afirmação I está correta b As afirmações II e III estão corretas c Todas as afirmações estão corretas d As afirmações I e III estão corretas e Nenhuma das afirmações está correta RESOLUÇÃO A classe P é a classe de problemas que podem ser resolvidas em tempo polinomial por uma máquina de Turing determinística logo a afirmação I é verdadeira A classe NP é a classe de problemas que podem ser resolvidas em tempo polinomial por uma máquina de Turing não determinística Dessa forma todos os problemas de P estão em NP mas o contrário não é verdade de forma que a afirmação II é falsa Um problema NPDifícil é definido como um problema para o qual todo problema em NP pode ser reduzido em tempo polinomial Um problema NPCompleto é aquele problema NP para o qual todo problema em NP pode ser reduzido em tempo polinomial Ou seja a única diferença entre eles é que o NPDifícil não precisa estar na classe NP ou seja a afirmação III é verdadeira Assim a alternativa D é a correta 6