Questão de Tecnologia da Informação

1.a ® Ø b 2.b Ù a 3.Ø b Ú b seja Q o seguinte conjunto de fórmulas da lógica proposicional: 4.a Ú b 5.b ® a e seja R a fórmula 6.Ø b ® a Veja a tabela-verdade para estas fórmulas.

Sabe-se que cada linha da tabela-verdade corresponde a uma atribuição de valores-verdade para os símbolos proposicionais (a e b) e cada coluna corresponde à avaliação da fórmula para esta atribuição. Algumas definições: (i) Uma fórmula é uma tautologia se e somente se, para toda atribuição de valores-verdade, sua avaliação é verdadeira. (ii) Uma atribuição de valores-verdade satisfaz a um conjunto de fórmulas se e somente se, para toda fórmula no conjunto, a avaliação é verdadeira. (iii) Um conjunto de fórmulas é satisfazível se e somente se existe uma atribuição de valores-verdade que satisfaz o conjunto. Em caso contrário, ele é insatisfazível. (iv) Uma fórmula é uma consequência lógica de um conjunto de fórmulas se e somente se, para toda atribuição de valores-verdade, se a atribuição satisfaz o conjunto então satisfaz a fórmula. 14 CIÊNCIA DA COMPUTAÇÃO Com base nas informações apresentadas, responda os itens a seguir. a) Há alguma tautologia nas fórmulas 1 a 6? Justifique sua resposta. (valor: 2,5 pontos) b) Há algum conjunto (p ou Q) satisfazível? Justifique sua resposta. (valor: 2,5 pontos) c) Há algum conjunto (p ou Q) insatisfazível? Justifique sua resposta. (valor: 2,5 pontos) d) A fórmula 6 é consequência lógica de Q? Justifique sua resposta. (valor: 2,5 pontos) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Área livre CIÊNCIA DA COMPUTAÇÃO 15 QuEStãO diSCuRSiVa 04 A soma de dois números binários é feita bit a bit, começando da direita (menos significativo) para a esquerda (mais significativo), passando o transporte, vai um (do inglês, carry out, representado na figura como Cout), para o bit seguinte como vem um (do inglês, carry in, representado na figura como Cin). Uma forma simples de implementar um somador de N bits é implementar N somadores elementares de 1 bit. Cada somador de um bit tem as entradas A, B e carry in (Cin) e as saídas Soma (S) e carry out (Cout). DELGADO, J.; RIBEIRO, C. arquitetura de Computadores. Rio de Janeiro: LTC, 2009 (adaptado). Nesse contexto, considere a figura a seguir. Entradas A Saídas S B Somador Completo Cout de 1-bit Cin Com base no somador completo de 1-bit apresentado na figura, descreva sua tabela verdade e o diagrama do seu circuito lógico. (valor: 10,0 pontos) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Área livre 16 CIÊNCIA DA COMPUTAÇÃO QuEStãO diSCuRSiVa 05 Um heap binário é um arranjo que pode ser visualizado como uma árvore binária, sendo que cada nó da árvore corresponde a um elemento do arranjo, como pode ser observado na figura a seguir. 0 1 2 3 4 5 6 7 8 9 12 10 11 8 9 1 4 5 7 2 12 11 10 8 9 1 4 5 7 2 Percebe-se que existem dois tipos de heaps: heaps máximo e heaps mínimo. O heap máximo é uma estrutura de dados que possibilita a consulta ou extração de forma eficiente do maior elemento de uma coleção. A propriedade de heap máximo especifica que um nó filho (no código calculado pelas funções left e right) tem sempre armazenado um valor menor ou igual ao seu pai. CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Introduction to Algorithms. 3. ed. MIT Press and McGraw-Hill. p. 131-161, 2009 (adaptado). Considerando a implementação a seguir, o heapify é uma função auxiliar para reorganizar o arranjo (garantindo a propriedade de heap máximo em uma determinada posição do arranjo) e buildHeap é uma função que usa heapify para reorganizar todas as posições do arranjo (garantindo a propriedade de heap máximo para todos os elementos). int left(int i) { return (2 * i + 1); } int right(int i) { return (2 * i + 2); } /* a - arranjo, n - número de elementos, i - posição do elemento que deve ser colocado em propriedade de heap */ void heapify (int *a, int n, int i) { int e, d, max, aux; e = left(i); d = right(i); if (e < n && a[e] > a[i]) max = e; else max = i; if (d < n && a[d] > a[max]) max = d; if (max != i) { aux = a[i]; a[i] = a[max]; a[max] = aux; heapify(a, n, max); } } /a - arranjo, n - número de elementos */ void buildHeap(int *a, int n) { int i; for (i = (n-1)/2; i >= 0; i--) heapify(a, n, i); } CIÊNCIA DA COMPUTAÇÃO 17 De acordo com as informações apresentadas, faça o que se pede nos itens a seguir. a) Como ficará o arranjo int a[ ] = {2, 5, 8 ,13, 21, 1, 3, 34} após a execução da função buildHeap(a, 8). (valor: 5,0 pontos) b) Apresente a complexidade de tempo no pior caso para a função heapify, use a notação O ou Q. (valor: 5,0 pontos) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Área livre 18 CIÊNCIA DA COMPUTAÇÃO