Algoritmos e Estruturas para Problemas de Sequências e Grafos

55 Uma subsequência contígua 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 contígua mas 5 15 40 não é Forneça um algoritmo de tempo linear para a seguinte tarefa Entrada Uma lista de inteiros a1 a2 an Saída A subsequência contígua 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 suma soma 55 Dica Para cada i j considere subsequências contíguas terminando exatamente na posição j 56 Dadas duas strings x x1x2xm e y y1y2yn desejamos encontrar o comprimento do maior substring comum delas isto é o maior l para o qual existem índices i e j com xixil1 yjyjl1 Mostre como fazer isso em tempo Omn 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 Um ávore nãodirecionada T V E Saída O tamanho da menor cobertura de vértices de T Por exemplo para a árvore abaixo as possíveis coberturas de vértice incluem A B C D E F G e A C D e C E F em 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 a complexidade do algoritmo tempo e memória 6 Transformação de problemas 61 Maria aposta com João que ele pode fazer o seguinte truque João reterá n 1 números diferentes de 1 a n em uma ordem aleatória e ela será capaz de no número ú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 ele 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 os cavaleiros para um jantar anual em Camelot Infelizmente alguns dos cavaleiros brigam entre si e Arthur sabe que brigando com Arthur quer sentar seus convidados ao redor de uma mesa para que dos cavaleiros briguentos não se sentem próximos uns 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 sentar à mesa de modo que dos membros da mesma família não estejam na mesma mesa Mostre como encontrar uma disposição das mesas Comece com esse objetivo ou prove que não está à disposição usando o problema do fluxo máximo Suponha que o jantar tenha n famílias e que iésima família tenha ai os membros Suponha que uma mesa esteja disponível e que a jésima mesa possua capacidade bj 64 O problema da coloração de grafos é geralmente declarado como o problema da coloração do vértice atribua 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 Considerando a operação da coloração das arestas atribua ao menor número de cores aos lados de um determinado grafo onde os vertices não tenham a mesma cor Explique como o problema da coloração de arestas 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 e Ração do Sucesso que são feitas de uma mistura de cereais e carne Um pacote de Viralatas é vendido por 1 15 quilo de cereais e 1 quilo de carne 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 porquilo 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 pacote de produto que não faz de fato baseado para empacotar apenas 110000 pacotes de Viralatas por mês Desnecessariamente dizer a gerência gostaria de maximizar o lucro