Algoritmos de Programação Dinâmica e Problemas de Otimização - Matrizes, Palíndromos e Substrings

Questão 1 2 pontos Determine de quantas maneiras você pode ir a partir do canto superior esquerdo para o canto inferior direito em uma matriz n x m A entrada do algoritmo é uma matriz n x m boolean B em que true representa um obstáculo Os únicos movimentos permitidos são ir para baixo e ir para a direita Questão 2 2 pontos Um palíndromo é uma cadeia não vazia em algum alfabeto que é lida do mesmo modo da esquerda para a direita e da direita para a esquerda Exemplo de palíndromos são radar asa reter e oco Usando programação dinâmica dê um algoritmo eficiente para encontrar o palíndromo mais longo que é uma subsequência de uma cadeia de entrada dada Por exemplo dada entrada character nosso algoritmo retornaria carac Questão 3 2 pontos Dadas duas strings x x1x2xn e y y1y2 ym desejamos encontrar o comprimento do maior substring comum delas isto é o maior k para o qual existem índices i e j com xixi1 xik1 yjyj1 yjk1 Mostre como fazer isso em tempo Omn Questão 4 2 pontos O monitor de PAA tem um algoritmo que recebe um vetor com números binários de tamanho n Este algoritmo possui um bug se o vetor possuir valores zeros seguidos Por exemplo 1010100 causaria um segmentation fault e 011011010 rodaria sem problemas Para calcular a probabilidade de haver um bug o monitor precisa saber o número de entradas válidas sem bug Calcule uma recorrência Sn que corresponde ao número de entradas válidas com comprimento n e comente a chances do monitor rodar o algoritmo sem bug Em seguida mostre um algoritmo de programação dinâmica para calculála Questão 5 2 pontos Várias famílias saem para jantar juntas Para aumentar sua interação social eles gostariam de sentarse à mesa de modo que dois membros da mesma família não estivessem na mesma mesa Mostre como encontrar uma disposição dos assentos que atenda a esse objetivo ou prove que não existe tal disposição usando o problema de fluxo máximo Suponha que o jantar tenha p famílias e que a iésima família tenha ai os membros Suponha que q mesas são disponíveis e que a meia jésima mesa possui capacidade bj Questão 6 1 ponto O quadrado mágico consiste em encontrar para um dado n uma matriz n tal que i cada célula da matriz seja um número entre 1 e n2 ii todas as células da matriz devem ser diferentes e iii a soma das linhas colunas e duas diagonais são todas iguais Usando programação por restrições modele o problema Dica use uma variável xij que representa o valor que a célula i j da matriz pode assumir e uma variável S para a soma de cada linha coluna e diagonal Questão 7 1 ponto Dado um grafo GV E e a seguinte formulação em programação linear inteira abaixo em que Nv representa o conjunto dos vizinhos de v Qual o problema representado