Problemas de Complexidade: Tripartição, Caminho Hamiltoniano e Árvores Geradoras

PROBLEMA TRIPARTIGAOA n Dado um vetor A1 de nimeros inteiros posi tivos decidir se existem subconjuntos disjuntos I e J de 1 tais que Al Al Yo ALi iel ie iIuJ Sabese que 0 PROBLEMA PaRTICAO é NPcompleto Um aluno alega que 0 PROBLEMA TRIPARTICAO também é NPcompleto O aluno esta certo Jus tifique cuidadosamente a sua resposta 76 Busca versus decisao Suponha que vocé tenha um procedimento que execute em tempo polinomial e que informe se um grafo tem ou nao um caminho Hamiltoniano Mostre que vocé pode usalo para de senvolver um algoritmo de tempo polinomial para o PROBLEMA DO CAMINHO HAMILTONIANO em sua versao de busca que retorna o caminho propria mente se ele existe 7 NP letud 77 O PROBLEMA DA ARVORE GERADORA COM RESTRI completude CAO DE GRAU 6 0 seguinte Entrada Um grafo nao direcionado GV E 71 Responda cada um dos itens abaixo e dé uma justifi Saida Uma 4rvore geradora de G na qual cada né cativa para as respostas tem grau k se uma arvore desse tipo existe O que significa dizer que um problema IT pode Mostre que para todo k 2 0 problema é NPdificil ser polinomialmente reduzido a um problema ll2 78 Uma pipa é um grafo sobre um numero par de vér tices digamos 2n nos quais n dos vértices formam Defina as classes P NP e problema NP 18 q eas uma clique e os restantes n vértices sdo conectados completo os em um rabo que consiste em um caminho inci PONP dente a um dos vértices da clique Dado um grafo oo e um objetivo g o PROBLEMA DA PIPA pede que se 72 Responda cada um dos itens abaixo e dé uma justifi J a d encontre um subgrafo que seja uma pipa e que con cativa para as respostas J tenha 2g nos Prove que Pipa é NPcompleto Se um problema II pode ser polinomialmente reduzido a um problema IT e II esta em P en 79 No PROBLEMA CONJUNTO INCIDENTE é dada uma tio I esta em P familia de conjuntos SjS2S e um inteiro b e desejamos encontrar um conjunto H de tamanho Se um problema II pode ser polinomialmente we io b que intercepte todos os S se um tal H existir reduzido a um problema II e II é NP Em outras palavras queremos Hn S 4 para todo completo entao II é NPcompleto Z i Mostre que Conjunto Incidente é NPcompleto Ha problemas em NP que nao sao NP completos 710 SUBGRAFO DENSO dados um grafo G e dois inteiros ae b encontre um conjunto de a vértices de G tal Existem problemas NPcompletos em P que exista pelo menos b arestas entre eles Prove que 73 Encontre 5 problemas NPcompletos nao estuda o problema é NPcompleto dos na disciplina aula e lista Para cada um deles descrevao formalmente entrada e questao e apre sente uma ilustracdo de uma instancia e uma solu 8 Lidando com Gao NPCompletude 74 Considere 0 seguinte algoritmo forca bruta para re solver 0 problema do nimero CoMPOSTO Verifique 81 Um quadrado magico de ordem 3 uma tabela 3 x 3 inteiros sucessivos de 2 a n2 como possiveis divi preenchida com nove ntimeros inteiros distintos de sores de n Se um deles divide n retorna SIM ou 1 a9 de modo que a soma dos numeros em cada li seja o ntimero é composto se nenhum deles o fi nha coluna e duas diagonais de ponta a ponta seja zer retorne NAO Por que esse algoritmo nao coloca a mesma Implemente um algoritmo backtracking e o problema na classe P encontre todos os quadrados magicos de ordem 3 75 Considere os problemas a seguir PROBLEMA PaRTI 82 Implemente um algoritmo backtracking para 0 PRO CAOA n BLEMA DO PASSEIO DO CAVALO iniciando de uma das Dado um vetor A1 de numeros inteiros posi quinas Informe o tempo em segundos e apresente a tivos decidir se existe um subconjunto J de 1 7 solucao tal que 4 y Ali Ali 83 Projete um algoritmo para 0 PROBLEMA DO CamI a NHO HAMILTONIANO de um vértice fixo s 84 Escolha um problema de otimização e dê um exem plo de uma execução de um algoritmo branchand bound sobre o problema escolhido Escolha um ins tância pequena Isso implica decidir a Como calcular um limitante para o problema b Como você expandir um nó em subproblemas c Qual subproblema escolher 85 De forma similar à questão anterior responda as perguntas projete um algoritmo branchand bound para o problema da COBERTURA DE CON JUNTO 86 No problema da ÁRVORE DE STEINER MÍNIMA a en trada consiste em um grafo completoG VE com distâncias duv entre todos os pares de nós e um de terminado conjunto de vértices terminais V V O objetivo é encontrar uma árvore de custo mínimo que inclua os vértices V Essa árvore pode ou não in cluir nós em V V Sabese que este problema é NP difícil proponha uma heurística construtiva para ge rar uma solução viável para o problema note que a solução pode não ser ótima 87 Apresente o algoritmo de busca local 2opt para o TSP dê um exemplo de execução e mostre que ele não é exato 88 Escolha um problema de otimização NPdifícil e apresente um estrutura de vizinhança para tal pro blema 89 Escolha 5 metaheurístias do livro Handbook of Metaheuristics httpswwwspringercom gpbook9783319910857 cada capítulo fala de uma metaheurística Para cada uma das 5 des creva o algoritmo e explique quais os mecanismos de intensificação e diversificação da busca 810 No problema do BIN PACKING a entrada consiste em n itens com tamanhos s1s2sn em que si 01 O objetivo é encontrar o menor número de bins caixas unitárias para armazenar os n itens O algoritmo First Fit consiste em 1 procedure ALGORITMO FIRST FITvetor s1n 2 for i 1 n do 3 Coloque o item i no bin de menor índice que tenha espaço dis ponível si 4 end for 5 end procedure Mostre que o algoritmo é 2aproximado Dica O FF não deixa ao final dois bins com espaço utilizado 05 8