Lista de Exercicios Divisao e Conquista e Paralelismo

3 Divisão e Conquista 31 Explique a relação da técnica DivisãoeConquista com paralelismo Como utilizar o paralelismo em um algoritmo divisãoeconquista Por que elas funcionam bem em conjunto 32 Existem n panquecas todas de tamanhos diferentes empilhadas umas sobre as outras Você pode colocar uma espátula sob uma das panquecas e virar a pilha inteira acima da espátula O objetivo é arranjar as panquecas de acordo com o tamanho com a maior na parte inferior A Figura mostra uma instância do quebracabeça para n 7 Projete um algoritmo para resolver este problema e determine o número de operações feitas pelo algoritmo no pior caso 33 Suponha que você tenha os resultados de um torneio concluído no qual n equipes jogaram entre si uma vez Assumindo que não houve empate mostre um algoritmo que liste os times em uma sequência de forma que todos ganhem o jogo com o time listado imediatamente após 34 Escreva um algoritmo de divisãoeconquista On log n para computar an em que n é um inteiro positivo 35 São dadas duas listas ordenadas de tamanho m e n Dê um algoritmo de tempo Olog m log n para computar o késimo menor elemento da união das duas listas 36 Suponha que esteja escolhendo entre os seguintes três algoritmos Algoritmo A resolve problemas dividindoos em cinco subproblemas de metade do tamanho solucionando cada subproblema recursivamente e então combinando as soluções em tempo linear Algoritmo B resolve problemas de tamanho n resolvendo recursivamente dois subproblemas de tamanho n 1 e então combinando as soluções em tempo constante Algoritmo C soluciona problemas de tamanho n dividindoos em nove subproblemas de tamanho n3 resolvendo recursivamente cada subproblema e então combinando as respostas em tempo On² Qual o tempo de execução de cada um desses algoritmos em notação O e qual você escolheria 37 Dado A1n um vetor ordenado de inteiros distintos você quer saber se existe um índice i para o qual Ai i Dê um algoritmo de divisãoeconquista que execute em tempo Olog n 38 Mostre que qualquer vetor de inteiros x 1n pode ser ordenado em tempo On M onde M maxxi minxi 39 Resolver o problema da Torre de Hanói quando se dispõe de 4 torres em vez de 3 Determinar o número de movimentos de disco 310 Dado um vetor A com n entradas com cada entrada um número distinto Sabese que a sequência de valores A1 A2 An é unimodal ou seja existe índice p entre 1 e n os valores nas entradas do vetor aumentam até a posição p e em seguida reduzem o resto do caminho até que a posição n Desejase encontrar o ponto de máximo p Mostre como encontrar p através de um algoritmo Olog n 4 Algoritmos Gulosos 41 As sentenças seguintes podem ou não estar corretas Em cada caso prove a sentença se ela for correta ou forneça um contraexemplo se não for correta Sempre considere o grafo G V E nãodirecionado e conexo Não considere que os pesos nas arestas sejam distintos a menos que isso seja explicitamente afirmado a Se um grafo G tem mais do que V 1 arestas e existe uma única aresta de maior peso então esta aresta não pode ser parte da árvore geradora mínima b Se G tem um ciclo com uma aresta de maior peso única e então e não pode ser parte de nenhuma AGM c Seja e qualquer aresta de peso mínimo em G Então e tem de ser parte de alguma AGM d Se a aresta de menor peso em um grafo é única então ela tem de ser parte de todas as AGMs e Se e é parte de alguma AGM de G então ela tem de ser a aresta de menor peso através de algum corte de G f Se G tem um ciclo com uma aresta mais leve única e então e tem de ser parte de todas as AGM g Árvore de caminhos mínimos computada pelo algoritmo de Dijkstra é necessariamente uma AGM h O caminho mínimo entre dois nós é necessariamente parte de alguma AGM i O algoritmo de Prim funciona corretamente quando existem arestas negativas j Para qualquer r 0 defina um rcaminho cujas arestas tenham todas peso r Se G contém um rcaminho do nó s até t então toda AGM de G tem de conter também um rcaminho do nó s até o nó t 42 Considere um grafo nãodirecionado G VE com pesos de aresta nãonegativos we 0 Suponha que você computou uma árvore geradora mínima de G e que também computou os caminhos mínimos para todos os nós partindo de um particular nó s V Agora suponha que cada peso de aresta seja aumentado em uma unidade os novos pesos são we we 1