Baixe o app para aproveitar ainda mais
Prévia do material em texto
QXD0041 Lista de Exercícios 2014.1 UNIVERSIDADE FEDERAL DO CEARÁ E2Campus de Quixadá Prof. Arthur Araruna QXD0041- Projeto e Análise de Algoritmos 2014.1 Nome: Matrícula: 1. Pensando nas notações O eΩ segundo suas definições, quais funções pertencem aos conjuntos O(−1) e Ω(−1)? 2. Qual é a ordem de grandeza das seguintes funções? (a) f (n) = (n2 +n) · (n− 1) (b) g(n) = ( n− 1 n− k ) + ( n− 1 k + 1 ) (c) h(n) = n∑ i=0 ( n i ) (d) F(n) = 9F(n/3) +n2; F(1) = 1 (e) G(n) = 3G(n− 1) +n; G(0) = 0 3. Considere dois computadores C1 e C2 que executam 107 e 109 passos por segundo (P /s) e dois algorit- mos de ordenação A e B com funções de complexidade de pior caso respectivamente f1(n) = 2n + 2 e f2(n) = 50n log10n para uma entrada de tamanho n. (a) Qual seria o tempo de execução de cada algoritmo se considerássemos executá-los em cada um dos computadores descritos? (b) Assintoticamente, qual dos algoritmo é mais eficiente? 4. Considere a função definida pela recorrência F(n) =2 ·F(n− 1) F(0) =1. Marotônio afirma que F(n) = O(n), e que isso pode ser verificado simplesmente da seguinte forma: F(n) =2 ·F(n− 1) =2 ·O(n− 1) =2 ·O(n) =O(n) O raciocínio de Marotônio não está correto, está? Qual seria a resposta correta? Onde ocorreu erro? 5. Determine a complexidade de pior caso do Algoritmo 1 a seguir. 6. Considere o Algoritmo 2 a seguir, que dependendo dos dados de entrada determina o menor elemento de três maneiras distintas. Qual a complexidade de pior caso desse algoritmo? 7. Sejam AlgoritmoA e AlgoritmoB dois algoritmos para resolver um dado problema. Imagine que divi- dimos as possíveis instâncias desse problema em dois conjuntos, I1 e I2. Após essa divisão, observamos que o AlgoritmoA necessita de O(n2) passos para resolver o problema para as instâncias em I1 e O(n2) passos para as em I2, e o AlgoritmoB, contrariamente, precisa de O(n2) passos para I1 e O(n) para I2. Assim, qual seria então a complexidade do Algoritmo 3 a seguir? QXD0041 Lista de Exercícios 2014.1 Algoritmo 1: Algoritmo: Loteria(R,A,n) Entrada: Vetor de resultados R e Matriz de apostas A13×n, natural n Saída: Um vetor P com os pontos feitos por cada apostador. para i← 1,2, . . . ,n faça P [i]← 0; para j← 1,2, . . . ,13 faça se A[i][j] = R[j] então P [i]← P [i] + 1; para i← 1,2, . . . ,n faça se P [i] = 13 então escreva “Apostador i é ganhador!” retorne P Algoritmo 2: Algoritmo: ElementoMinimo(V ) Entrada: Vetor V Saída: Maior elemento em V se V [1] mod 3 = 0 então retornaMenor(V); senão se V [1] mod 3 = 1 então MergeSort(V); senão BubbleSort(V); retorna V [1]; Algoritmo 3: Algoritmo: AlgoritmoC(e) Entrada: e ∈ I1 ∪ I2 AlgoritmoA(e); AlgoritmoB(e); QXD0041 Lista de Exercícios 2014.1 8. Escreva um algoritmo para resolver o problema de determinar o segundo menor elemento de um vetor de elementos dado como entrada. Quais as complexidades de pior caso de tempo e de memória do seu algoritmo? 9. Escreva um algoritmo que, dada uma sequência a1, a2, . . . , an, com ai ∈ N, determina um conjunto de índices I tal que o valor ∣∣∣∣∣∣∣∣ ∑ i ∈ I ai − ∑ j < I aj ∣∣∣∣∣∣∣∣ é mínimo. Qual a complexidade de pior caso do seu algoritmo? 10. Considere uma variação no algoritmo de busca eficiente em vetores ordenados, onde dividiremos nosso vetor em três porções ao invés de duas, continuando a busca na porção favorável. Supondo que o elemento procurado sempre está presente no vetor, escreva esse algoritmo e calcule sua complexidade de pior caso. Verifique se seu algoritmo é correto. 11. Seja um algoritmo A1 com tempo de execução O(n lgn) para resolver um dado problema. Suponha que possamos escrever um segundo algoritmo, A2, para resolver esse problema usando uma estratégia de Divisão e Conquista onde, para n > 1, geramos duas subinstâncias de tamanho n/2 para o problema, com combinação em a > 4 passos constantes, e apenas um passo no caso-base. Imagine que n é uma potência de 2. (a) Avalie a complexidade de A2. (b) Considere um terceiro algoritmo, A3, que chama o algoritmo A2 para n > n0 e o algoritmo A1 para n ≤ n0, com n0 dado. Determine o tempo de execução de A3 (observe que esse tempo também dependerá de n0). 12. Imagine que exista um algoritmo TrocaMatrizes que recebe duas matrizes A e B de dimensão n × n e realiza a troca dos elementos dessas matrizes em tempo O(n), de forma que, após a troca, todos os elementos de A estejam nas respectivas posições na matriz B e vice-versa. Utilizando esse algoritmo, desenvolva um algoritmo com a técnica de Divisão e Conquista para rotacionar uma matriz. Qual é a complexidade de pior caso do seu algoritmo? Observe abaixo, dada a matriz C, a matriz Cr obtida ao rotacionarmos a matriz C. C = a b cd e f g h j Cr = g d ah e b j f c 13. Para um valor de n que seja uma potência de 2, dizemos que uma matriz An×n é repetitiva se n = 1 ou se, para n > 1, A pode ser dividida em quatro submatrizes (n/2)× (n/2) da seguinte forma: A = ( B B C B ) , onde B e C são também matrizes repetitivas. Por exemplo, a matriz M abaixo é repetitiva. 3 3 3 3 4 3 4 3 5 5 3 3 6 5 4 3 . Escreva um algoritmo de Divisão e Conquista para multiplicar duas matrizes repetitivas de maneira eficiente, fazendo uso dessa propriedade (eficiente, nesse caso, significa um algoritmo com um limite melhor que O(n3)), e faça sua análise de complexidade. 14. Dê dois exemplos de problemas para os quais não encontramos instâncias com subestrutura ótima. QXD0041 Lista de Exercícios 2014.1 15. Na nação de Monolitávia, a casa da moeda local produz cédulas de 1, 7 e 10 coroas, moeda oficial da nação. Um dos bancos do país, visando diminuir a frequência de reposição de notas em seus caixas automáticos espalhados pela Monolitávia, deseja entregar aos clientes a quantia a sacar fazendo uso do menor número de cédulas possível. Escreva um algoritmo de Programação Dinâmica para resolver esse problema e faça sua análise de complexidade. 16. Suponha que você foi contratado por uma empresa administradora de rodovias para solucionar o se- guinte problema. A empresa deseja instalar postos de pedágio na rodovia BR-000 que sai de Quixadá e atravessa o país na direção sul por M kilômetros. Os possíveis lugares de instalação desses postos ficam nos marcos dados por x[1] < x[2] < · · · < x[n], onde cada x[i] representa a quantos quilômetros de Quixadá fica o possível local de instalação i. Se for construído um posto de pedágio no marco x[i], o valor a ser cobrado é dado por r[i] > 0. As regras impostas pela ANTT impedem que quaisquer dois postos de pedágio sejam instalados a uma distância inferior a 5km. Assim, a empresa deseja instalar pedágios na estrada de forma a obter o maior ganho possível. Por exemplo, se tivéssemos M = 10 e n = 5, com os valores 〈x〉 = 〈6,7,12,13,14〉 e 〈r〉 = 〈5,6,5,3,1〉, a melhor das opções seria instalar pedágios nos marcos x[1] e x[3], pois obteríamos um ganho de 10. Escreva um algoritmo de Programação Dinâmica para resolver esse problema e faça sua análise de complexidade.
Compartilhar