Algoritmos em Tempo Linear e Dinâmico para Problemas de Subsequências e Grafos

55 Uma subsequência contigua de uma lista S é uma subsequência feita de elementos consecutivos de S Por exemplo se S é 5 15 30 10 5 40 10 então 15 30 10 é uma subsequência contigua mas 5 15 40 não é Forneça um algoritmo de tempo linear para a seguinte tarefa Entrada Uma lista de números a1 a2 an Saída A subsequência contigua de soma máxima a subsequência de tamanho zero tem soma zero Para o exemplo anterior a resposta seria 10 5 40 10 com soma um total de 55 Dica Para cada j i considere subsequências contiguas terminando exatamente na posição j 56 Dadas duas strings x x1x2xk e y y1y2ym desejamos encontrar o comprimento da maior substring comum delas isto é o maior l para o qual existem índices i e j com xi xi1 xil1 yj yj1 yjl1 Mostre como fazer isso em tempo Onm 57 Uma cobertura de vértices de um grafo G V E é um subconjunto de vértices S V que inclui ao menos uma extremidade de cada aresta de E Forneça um algoritmo de tempo linear para a seguinte tarefa Entrada Uma árvore nãodirecionada T V E Saída O tamanho da menor cobertura de vértices de T Por exemplo para o enunciado abaixo as possíveis coberturas de vértice incluem A B C D E F e G A D E F e G e A D F e G A menor cobertura de vértice tem tamanho 3 B E G 58 Forneça um algoritmo de programação dinâmica note que será pseudopolynomial para o problema SUBSET SUM Entrada Um conjunto A com valores inteiros positivos e um inteiro t Questão Existe um subconjunto A A cuja soma dos valores seja exatamente t 59 Dado um grafo simples GV E e dois vértices s t V projete um algoritmo de programação dinâmica que encontre a quantidade de caminhos simples distintos entre s e t 510 Mostre um algoritmo de programação dinâmica para o problema do CAMINHO MÁXIMO entre dois vértices s e t caminho simples Qual o complexity do algoritmo tempo e memória 6 Transformação de problemas 61 Maria aposta com João que ela pode fazer o seguinte truque João retirará n 1 números diferentes de 1 a n em uma ordem aleatória e ela será capaz de n um único número nesse intervalo que ele terá perdido Claro ele terá que realizar a tarefa em sua cabeça sem fazer anotações Como ela deve fazer esse truque Em outras palavras projete um algoritmo que descubra o número faltante utilizando O1 de espaço em memória 62 O Rei Arthur espera ar cavaleiros para um jantar anual em Camelot Infelizmente alguns dos cavaleiros brigam entre si e Arthur sabe que brigões com Arthur quer sentar ao lado um do outro Qual problema pode ser usado para melhorar a tarefa do Rei Arthur 63 Várias famílias saem para jantar juntas Para aumentar sua interação social eles gostariam de sentarse à mesa de modo que dois membros de mesma família não estejam na mesma mesa Mostre como encontrar uma disposição das mesas Mostre como este objetivo ou prove que não está disposto e solução do problema de fluxo máximo Suponha que o jantar tenha k famílias e que iésima família tenha ai membros Suponha que mes também estão disponíveis e que e iésima mesa possua capacidade bi 64 O problema da coloração em grafos é geralmente declarado como o problema de coloração do vértice atribuir o menor número de cores aos vértices de um dado grafo de forma que não haja dois vértices adjacentes com a mesma cor Considere agora o problema da coloração das arestas atribua o menor número de cores às arestas de um determinado grafo do qual não têm a mesma cor Explique como o problema da coloração da aresta pode ser reduzido a um problema de coloração de vértices 65 Considere o seguinte problema de programação linear max 5x 3y sa 5x 2y 0 x y 7 x 0 y 0 Desenhe a região factível e identifique a solução ótima 66 A companhia de produtos caninos oferece duas comidas para cachorro Viralatas Ração do Sucesso que são feitas de uma mistura de cereais e carne Um pacote de Viralatas custa 15 quilo de cereal e é vendido por 7 Um pacote de Ração do Sucesso usa 2 quilos de cereal e 1 quilo de carne e é vendido por 6 O cereal bruto custa 1 por quilo e a carne bruta 2 por quilo Há também o custo de 140 para empacotar o Viralatas e 020 para o Ração do Sucesso Um total de 240000 quilos de cereal e 180000 quilos de carne estão disponíveis a cada mês O único aglomerado de produto não fato de fábrica poderá empacar apenas 110000 pacotes de Viralatas por mês Desnecessário dizer a gerência gostaria de maximizar o lucro