POSCOMP 2011

Exame Nacional para Ingresso na Ps-Graduao em Computao 9/10/2011 INSTRUES1. Conra, abaixo, seu nome e nmero de inscrio. Assine no local indicado. 2. Verique se os dados impressos no Carto-Resposta correspondem aos seus. Caso haja alguma irregularidade, comunique-a imediatamente ao Aplicador da Prova. 3. No sero permitidos emprstimos de materiais, consultas e comunicao entre os candidatos, tampouco o uso de livros e apontamentos. Relgios e aparelhos eletrnicos em geral devero ser desligados. O no cumprimento dessas exigncias ocasionar a excluso do candidato deste Exame. 4. Aguarde o Aplicador da Prova autorizar a abertura do Caderno de Prova. Aps a autorizao, conra a paginao antes de iniciar a Prova. 5. Este Caderno de Prova contm 70 (setenta) questes objetivas, cada qual com apenas 1 (uma) alternativa correta. No Carto-Resposta, preencha, com tinta preta, o retngulo correspondente alternativa que julgar correta para cada questo. 6. No Carto-Resposta, anulam a questo: a marcao de mais de uma alternativa em uma mesma questo, as rasuras e o preenchimento alm dos limites do retngulo destinado para cada marcao. No haver substituio do Carto-Resposta por erro de preenchimento. 7. No sero permitidas perguntas ao Aplicador da Prova sobre as questes da Prova. 8. A durao desta prova ser de 4 (quatro) horas, j includo o tempo para o preenchimento do Carto-Resposta. 9. O tempo mnimo para ausentar-se denitivamente da sala de 1 (uma) hora. 10. Ao concluir a prova, permanea em seu lugar e comunique ao Aplicador da Prova. 11. Aguarde autorizao para devolver, em separado, o Caderno de Prova e o Carto-Resposta, devidamente assinados.

Transcreva abaixo as suas respostas, dobre na linha pontilhada e destaque cuidadosamente esta parte. .................................................................................................................................... RESPOSTAS

01 19 37 55

02 20 38 56

03 21 39 57

04 22 40 58

05 23 41 59

06 24 42 60

07 25 43 61

08 26 44 62

09 27 45 63

10 28 46 64

11 29 47 65

12 30 48 66

13 31 49 67

14 32 50 68

15 33 51 69

16 34 52 70

17 35 53

18 36 54

O gabarito ocial provisrio estar disponvel no endereo eletrnico www.cops.uel.br a partir das 20 horas do dia 9 de outubro de 2011.

MATEMTICA 1 Considere a matriz a seguir. 2 4 2 A= 1 5 2 4 1 9 No mtodo da eliminao de Gauss, foram efetuados os seguintes passos para se obter uma matriz na forma degrau: I. Subtraiu-se a metade da primeira linha da segunda. II. Subtraiu-se o dobro da primeira linha da terceira. III. Adicionou-se o triplo da segunda linha terceira. Em termos matriciais, o processo descrito corresponde a: a) Adicionar A a matriz 0 0 0 1 2 0 4 1 1 0 0 0 2 0 0 1/2 1/3 0 1 1/2 2 0 1 3 0 0 1 1 0 0 1/2 1 0 7/2 3 1 2 0 0 4 2 5 2 0 9 x a + y b = 1 que formam

b) Multiplicar A, esquerda, por

c) Multiplicar A, direita, por

d) Multiplicar A, esquerda, por

e) Subtrair de A a matriz

2 Sejam a e b nmeros reais no nulos. As duas retas perpendiculares reta a) ax by = 1 e ax + by = 1 x y y x b) =1e =1 a b b a x2 y2 x2 y2 c) 2 + 2 = 1 e 2 2 = 1 b a b a x y y x d) = 2e = 2 b a a b x x y y e) + = 2e + = 2 |b| |a| |b| |a| tringulos de rea |ab| com os eixos ordenados so descritas pelas equaes:

3 Suponha que, em vez de usar a base padro {e1 , e2 } para R2 , onde e1 = [1, 0]T e e2 = [0, 1]T , deseja-se utilizar a base {u1 , u2 }, com u1 = [3, 2]T e u2 = [1, 1]T As coordenadas do vetor x = [7, 4]T em relao a u1 e u2 so: a) [0, 1]T b) [1, 2]T d) [4, 3]T c) [3, 2]T

e) [15, 18]T 1 / 24

4 O valor de x > 0, pertencente ao primeiro quadrante, para a expresso 2 + 2cos(x) + 2cos(x)cos(x) + 2cos(x)cos(x)cos(x) + 2cos(x)cos(x)cos(x)cos(x) + ... = 4 : a) 0 b) 6 c) 3 d) 2 e) 5 Em muitos problemas prticos, deseja-se encontrar a reta r(x) = ax + b que melhor se ajusta a um conjunto {(x1 , y1 ), (x2 , y2 ), ..., (xn , yn )} de pontos no plano. No mtodo dos mnimos quadrados, os coecientes a e b da reta so determinados de modo que o erro, dado pela soma do quadrado da diferena entre yi e r(xi ), isto ,n

Erro(a, b) =i=1

(yi r(xi ))2 ,

seja o menor possvel. A tabela a seguir mostra o conjunto de pontos {(3, 3), (2, 2), ..., (2, 6), (3, 6)} no plano. x y -3 -3 -2 -2 -1 2 0 2 1 4 2 6 3 6

A reta que melhor se ajusta aos dados apresentados nessa tabela, no sentido dos mnimos quadrados, : a) r(x) = x 15 x b) r(x) = 7 3 3 c) r(x) = x + 2 2 15 45 x+ d) r(x) = 28 7 7 45 e) r(x) = x + 2 7 6 O problema de determinar um vetor normal a um tringulo ou polgono muito comum em computao grca. Dado o tringulo formado pelos pontos A(1, 2, 3), B(3, 2, 1) e C(1, 1, 1), um vetor normal, n, a esse tringulo dado por: a) n = [2, 4, 2]T b) n = [0, 0, 4]T d) n = [3, 4, 5]T e) n = [5, 5, 5]T 7 Com base em f (x, y, z) = x2 ey + 2zy, uma funo real de trs variveis reais, considere as armativas a seguir. I. O ponto P0 = (1, 0, 1) um ponto crtico de f . II. A funo f contnua no ponto P0 = (1, 0, 1). 3 2 III. A direo unitria em que f cresce mais rapidamente no ponto P0 = (1, 0, 1) i + j. 13 13 IV. O vetor gradiente de f no ponto P0 nulo se, e somente se, P0 = (0, 0, 0). Assinale a alternativa correta. a) Somente as armativas I e II so corretas. b) Somente as armativas I e III so corretas. 2 / 24 c) n = [2, 1, 4]T

c) Somente as armativas III e IV so corretas. d) Somente as armativas I, II e IV so corretas. e) Somente as armativas II, III e IV so corretas. 8 Relacione a equao em coordenadas polares da coluna da esquerda com a gura geomtrica correspondente apresentada na coluna da direita.

(I) sen() =

2

2

(A)

(II) r = 2cos(3)

(B)

(III) r =

1 1 sen()

(C)

(IV) cos(r) = 0

(D)

(V) r = 2cos() a) I-A, II-C, III-D, IV-E, V-B. b) I-A, II-D, III-B, IV-C, V-E. c) I-B, II-C, III-E, IV-A, V-D. d) I-B, II-E, III-A, IV-D, V-C. e) I-D, II-E, III-C, IV-B, V-A.

(E)

Assinale a alternativa que contm a associao correta.

3 / 24

9 Considere o polinmio pn (x) = an xn + ... + a1 x + a0 em seu formato padro que pode ser escrito no formato encadeado pn (x) = x(x(...x(x(an x + an1 ) + an2 ) + ... + a2 ) + a1 ) + a0 , colocando a varivel x em evidncia num nmero nito de vezes at que no seja mais possvel faz-lo. Considerando que todos os coecientes do polinmio so diferentes de zero, correto armar que o total de operaes de adio e multiplicao para obter o valor de p100 (5) : a) Duas vezes maior no formato encadeado que no padro. b) Igual no formato padro e no encadeado. c) Impossvel de ser calculado. d) Maior no formato encadeado que no padro. e) Maior no formato padro que no encadeado. 10 A proporo de computadores acessando um provedor em um dado instante t a partir das 8 horas dada por 1 N (t) = 1 + 3ekt onde o instante t dado em horas e k uma constante positiva. A proporo estimada de computadores acessando este provedor ao meio-dia de: 1 a) ln(2 + e4k ) k 1 (3e12k + 1) b) ln k 4 1 (3e12k + 1) c) ln k (3 + e8k ) 1 (3 + e4k ) ln k 4 1 (3 + e4k )3k e) ln k 4 d) 11 Sobre a funo f : R (1, 1) denida pela lei f (x) = a) f bijetora. b) f decrescente. c) f no injetora, mas sobrejetora. d) f no sobrejetora, mas injetora. e) f no sobrejetora nem injetora. 12 Com base na funo f (x) = 6x3/2 x2 1, considere as armativas a seguir. I. f tem um zero no intervalo [0,1] II.x+

x 1 + |x|

correto armar:

lim f (x) = + 81 4

III. f assume o valor mximo no ponto x = IV. f possui uma descontinuidade em zero Assinale a alternativa correta. a) Somente as armativas I e II so corretas. b) Somente as armativas I e III so corretas. c) Somente as armativas III e IV so corretas. d) Somente as armativas I, II e IV so corretas.

e) Somente as armativas II, III e IV so corretas.

4 / 24

13 Considere o grafo a seguir.

O grafo representa a relao: a) R = {(1, 1), (1, 2), (1, 3), (3, 1), (4, 3)} b) R = {(1, 1), (1, 2), (1, 3), (3, 1), (3, 4)} d) R = {(1, 1), (1, 2), (1, 3), (3, 4), (4, 3)} c) R = {(1, 1), (1, 3), (2, 1), (3, 1), (3, 4)}

e) R = {(1, 1), (1, 3), (2, 1), (3, 1), (4, 3)} 14 Considere as proposies p e q, cujas respectivas negaes so p e q. Ento correto armar que a recproca de p q : a) q p c) p q b) q p

d) p e q e) p e q

15 Considere o inteiro 360. Se x a quantidade de seus divisores inteiros e positivos e y a quantidade de seus divisores inteiros, positivos e pares, ento correto armar: a) x divide y. b) y divide x. c) x = y. e) x y divide x e x y divide y. 16 Considere a armao a seguir. Se um nmero inteiro primo e quadrado perfeito, ento ele negativo. Com relao a essa proposio, assinale a alternativa correta. a) A armao falsa. b) A armao verdadeira. c) A armao verdadeira e falsa. d) No possvel decidir se a armao verdadeira ou falsa. e) No existe um inteiro primo negativo. 17 Sejam A e B eventos arbitrrios de um espao amostral, em que B o complementar de B. Nessas condies, correto armar: a) P (A) > P (B) b) P (A) < P (B) c) P (A) = P (B) d) P (A) = P (B) e) P (A) = P (A B) + P (A B) 5 / 24 d) x y mltiplo de 5.

18 Sejam 10 cidades conectadas por rodovias, conforme o grafo a seguir.

Um vendedor sai de uma das cidades com o intuito de visitar cada uma das outras cidades uma nica vez e retornar ao seu ponto de partida. Com base no grafo e nessa informao, considere as armativas a seguir. I. O vendedor cumprir seu propsito com xito se sair de uma cidade par. II. O vendedor cumprir seu propsito com xito se sair de uma cidade mpar. III. O vendedor no cumprir seu propsito com xito se sair de uma cidade par. IV. O vendedor no cumprir seu propsito com xito se sair de uma cidade mpar. Assinale a alternativa correta. a) Somente as armativas I e II so corretas. b) Somente as armativas I e IV so corretas. c) Somente as armativas III e IV so corretas. d) Somente as armativas I, II e III so corretas. e) Somente as armativas II, III e IV so corretas. 19 Zezinho aposta 6 nmeros, dentre os 60 disponveis, no jogo da mega-sena. Aps o sorteio, Zezinho observa que o resultado formado por 6 nmeros primos. Se, no momento de sua aposta, Zezinho tivesse essa informao, ento a probabilidade de acerto de Zezinho seria de:

a)

b)

c)

d)

e)

20 O cdigo Morse usa dois smbolos: ponto e trao horizontal. Se as palavras desse alfabeto tiverem de 1 a 4 letras, correto armar que o cdigo Morse permitir escrever: a) 8 palavras. b) 16 palavras. c) 30 palavras. d) 32 palavras. e) 256 palavras.

6 / 24

FUNDAMENTOS DE COMPUTAO Para responder s questes 21 e 22, considere a seguinte variante do algoritmo quicksort para ordenao de uma lista de inteiros x1 , . . . , xn : Algoritmo QS(x1 , . . . , xn ) Entrada: x1 , . . . , xn Z.

1. Se n = 2 e x1 > x2 , permutar x1 com x2 . 2. Se n 2, retornar. 4. Enquanto i < j, 4.1 4.2 4.3 Enquanto x1 xi e i < n + 1, incrementar i. 3. i 2, j n,

Sada: x1 , . . . , xn Z.

Enquanto x1 < xj , decrementar j. Se i < j, permutar xi com xj .

5. Permutar x1 com xj . 6. QS(x1 , . . . , xj1 ) 7. QS(xj+1 , . . . , xn ) 21 Seja (x1 , ..., xn ) o nmero total de permutaes de dois elementos durante a execuo do algoritmo QS, inclusive durante as chamadas recursivas. Seja max (n) o maior valor de (x1 , . . . , xn ) para todas as listas possveis de comprimento n. Sabendo que max (n) = max max (j 1) + max (n j) + min(j 1, n j) + 1,1jn

a) b) c) d) e)

max(n) max(n) max(n) max(n) max(n)

= n 1. est em o(n). est em O(n log(n)), mas no em O(n). est em O(n2 ), mas no em O(n log n). > 2n .

22 Assinale a alternativa correta. a) O tempo de execuo do algoritmo QS, no pior caso, para entradas de tamanho n, de (n log2 (n)). b) O tempo de execuo total do algoritmo para a entrada x1 , . . . , xn sempre de O((x1 , . . . , xn )). c) O tempo de execuo total do algoritmo QS para a entrada x1 , . . . , xn no proporcional soma das vezes que cada uma das linhas foi executada. d) O tempo de execuo do algoritmo QS, no pior caso, para entradas de tamanho n, de (n2 ). e) O nmero total de comparaes do algoritmo QS, incluindo as chamadas recursivas, de O(max (n)) no pior caso. 23 Ao usar o clculo de endereo ou hashing, geralmente necessrio o uso de um mtodo de tratamento de colises. Sobre esse mtodo, correto armar: a) O tratamento de colises necessrio apenas quando a tabela est cheia e se necessita inserir mais uma chave. b) O tratamento de colises necessrio para determinar o local da chave no momento da insero na tabela. c) O tratamento de colises necessrio quando a tabela est vazia, pois no possvel calcular o endereo diretamente nesse caso. d) O tratamento de colises necessrio quando a chave inserida ainda no existir na tabela de endereamento. e) O tratamento de colises necessrio, pois o hashing gera repetio de endereo para diferentes chaves. 7 / 24

24 Sejam TA (n) e TB (n) os tempos de execuo de pior caso de dois algoritmos A e B propostos para um mesmo problema computacional, em funo de um certo parmetro n. Dizemos que o algoritmo A mais eciente que o algoritmo B assintoticamente no pior caso quando a) TA (n) = o(TB (n)). b) TB (n) = o(TA (n)). c) TA (n) = O(TB (n)). d) TB (n) = O(TA (n)). e) TA (n) = (TB (n)). 25 Com relao aos mtodos de ordenao, relacione a coluna da esquerda com a coluna da direita. (I) (II) Insero Seleo (A) (B) Encontra o menor elemento e o troca com a primeira posio, depois o segundo menor com a segunda posio e assim sucessivamente (n-1 vezes). As comparaes e trocas so feitas baseadas em uma distncia determinada (por exemplo: distncia 4, onde o primeiro seria comparado com o quinto elemento, o segundo com o sexto, e assim sucessivamente), depois a distncia reduzida. Este processo se repete at que a distncia seja 1 e as ltimas comparaes e trocas sejam efetuadas. A partir do segundo elemento, este deve ser colocado na sua posio correspondente (entre os elementos j analisados, como ao se organizarem as cartas de baralho na mo do jogador). Repete-se o procedimento at o ltimo elemento. Escolhe-se um ponto de referncia (piv) e separam-se os elementos em 2 partes: esquerda, cam os elementos menores que o piv, e direita, os maiores. Repete-se este processo para os grupos de elementos formados (esquerda e direita) at que todos os elementos estejam ordenados. Divide-se o grupo de elementos ao meio, repete-se a diviso para cada um dos subgrupos, at que cada subgrupo tenha apenas 1 elemento. Nesse ponto, faz-se o reagrupamento dos subgrupos comparando os elementos e trocando, se necessrio, para que eles quem ordenados. Repete-se este procedimento at restar um s grupo de elementos.

(III)

QuickSort

(C)

(IV)

ShellSort

(D)

(V)

MergeSort (ou ordenao por fuso)

(E)

Assinale a alternativa que contm a associao correta. a) I-A, II-D, III-B, IV-C, V-E. b) I-B, II-A, III-C, IV-E, V-D. c) I-B, II-A, III-E, IV-D, V-C. d) I-C, II-A, III-D, IV-B, V-E. e) I-D, II-E, III-B, IV-A, V-C. 26 A teoria da computabilidade, em conjunto com a lgebra booleana, garante que possvel construir um processador com um conjunto de instrues unitrio que possua capacidade de resolver qualquer problema solvel. Suponha que exista uma organizao de computador convencional, dotada de um processador de uma instruo, memria e perifricos de entrada e sada. Com relao instruo nica que o processador executa, considere as armativas a seguir. I. Deve obrigatoriamente fazer acesso a um dispositivo de entrada e sada. II. Deve obrigatoriamente ler e escrever na memria principal do processador. III. Deve obrigatoriamente calcular uma soma de produtos de literais booleanos. IV. Deve obrigatoriamente realizar um teste, e sua ao deve ser condicionada ao resultado deste teste. Assinale a alternativa correta. a) Somente as armativas I e II so corretas. b) Somente as armativas II e IV so corretas. c) Somente as armativas III e IV so corretas. d) Somente as armativas I, II e III so corretas. e) Somente as armativas I, III e IV so corretas. 8 / 24

27 As estruturas de dados lineares (la, pilha e lista) so muito utilizadas para resolver problemas computacionais. Cada uma dessas estruturas pode ser implementada com diferentes caractersticas e atendem a diferentes tipos de problemas. Sobre as caractersticas dessas estruturas de dados, atribua V (verdadeiro) ou F (falso) para as armativas a seguir. ( ( ( ( ( ) Em uma pilha, o ltimo elemento a entrar o primeiro a sair. ) Em uma la, o primeiro elemento a entrar o ltimo a sair. ) Uma lista permite que as inseres possam ser feitas em qualquer lugar (posio), mas as remoes, no. ) Em uma lista circular com encadeamento simples, o primeiro elemento aponta para o segundo e para o ltimo. ) Para remover um elemento de uma lista duplamente encadeada, deve-se alterar o encadeamento dos elementos anterior e prximo ao elemento removido. Assinale a alternativa que contm, de cima para baixo, a sequncia correta. a) V, F, V, F, V. b) V, F, F, V, F. c) V, F, F, F, V. d) F, V, V, F, F. e) F, F, V, V, V. 28 Um processador RISC implementado em duas verses de organizao sncrona: uma monociclo, em que cada instruo executa em exatamente um ciclo de relgio, e uma verso pipeline de 5 estgios. Os estgios da verso pipeline so: (1) busca de instruo, (2) busca de operandos, (3) execuo da operao, (4) acesso memria e (5) atualizao do banco de registradores. A frequncia mxima de operao das organizaes foi calculada em 100 MHz para a verso monociclo e 400 MHz para a verso pipeline. Um programa X que executa 200 instrues usado para comparar o desempenho das organizaes. Das 200 instrues, apenas 40% fazem acesso memria, enquanto as demais operam apenas sobre registradores internos da organizao. Assuma que o programa no apresenta nenhum conito de dados ou de controle entre instrues que podem estar simultaneamente dentro do pipeline da segunda organizao. Assim, o tempo de execuo do programa X nas organizaes monociclo e pipeline , respectivamente: a) 2.000 nanossegundos e 510 nanossegundos. b) 2.000 nanossegundos e 500 nanossegundos. c) 2.000 nanossegundos e 2.300 nanossegundos. d) 2.300 nanossegundos e 500 nanossegundos. e) 2.300 nanossegundos e 510 nanossegundos. 29 Relacione a coluna da esquerda com a coluna da direita. (I) (II) (III) (IV) Multicore Superpipeline Superescalar Pipeline dinmico (A) (B) (C) (D) Mltiplos pipelines que operam em paralelo. Execuo de instrues fora de ordem em um pipeline. Pipelines com grande nmero de estgios. Mltiplos processadores compartilhando um espao de endereos. (E) Mltiplos processadores em um nico encapsulamento.

(V) Multiprocessadores a) I-B, II-A, III-C, IV-E, V-D. b) I-C, II-A, III-B, IV-D, V-E. c) I-D, II-E, III-B, IV-A, V-C. d) I-E, II-C, III-A, IV-B, V-D. e) I-E, II-C, III-A, IV-D, V-B.

Assinale a alternativa que contm a associao correta.

9 / 24

30 Um sistema de computador possui um mapa de memria de 4 Gbytes, usando endereamento a byte e uma memria cache com organizao de mapeamento direto. A cache tem capacidade de armazenar at 1.024 palavras de 32 bits provenientes do mapa de memria. Assuma que a cache sempre escrita de forma atmica com quatro bytes vindos de um endereo de memria alinhado em uma fronteira de palavra de 32 bits, e que ela usa 1 bit de validade por linha de cache. Neste caso, as dimenses do rtulo (tag) da cache, do ndice e o tamanho da cache so, respectivamente: a) 12 bits, 18 bits e 54.272 bits. b) 14 bits, 18 bits e 56.320 bits. c) 20 bits, 10 bits e 54.272 bits. d) 20 bits, 12 bits e 54.272 bits. e) 22 bits, 10 bits e 56.320 bits. 31 Considerando as duas equaes booleanas de um somador completo S = Ai xor Bi xor Cin e Cout = (Ai and Bi ) or Cin and (Bi xor Ai ), atribua V (verdadeiro) ou F (falso) para as armativas a seguir. ( ( ( ( ( ) A equao Cout = (Bi and Cin ) or Ai and Cin or (Ai and Bi ) equivalente equao Cout do enunciado da questo. ) O maior atraso de propagao ocorre na equao S = Ai xor Bi xor Cin . ) O uso destas equaes conduz implementao do mais rpido somador completo, entre os somadores descritos na literatura. ) Somadores completos de n bits (com n > 1) podem ser implementados com n circuitos, cada um deles implementando estas mesmas equaes. ) Para apenas uma combinao de valores de Ai , Bi e Cin , obtm-se S = 1 e Cout = 1. Assinale a alternativa que contm, de cima para baixo, a sequncia correta. a) V, V, F, V, F. b) V, F, F, V, V. c) F, V, V, F, V. d) F, V, F, V, F. e) F, F, V, F, V. 32 Considere a seguinte propriedade sobre uma linguagem formal L: Existe um nmero p 0, tal que para qualquer palavra w L, |w| p, existem palavras x, y e z, com y = e |xy| p, tais que, para qualquer inteiro i 0, a palavra xy i z L. Com base no enunciado e nos conhecimentos sobre o tema, atribua V (verdadeiro) ou F (falso) para as armativas a seguir. ( ( ( ( ( ) Se L aceita por AFND, ento L satisfaz a propriedade acima. ) A linguagem formada de 1s e 0s com igual quantidade de ocorrncias das palavras 01 e 10 satisfaz a propriedade acima. ) A propriedade acima falsa para a linguagem 0i 1k 2j /i, j, k 0 e se i = 1, ento k = j. ) A linguagem {an bm /n, m 0 e n = m} satisfaz a propriedade acima. Assinale a alternativa que contm, de cima para baixo, a sequncia correta. a) V, V, V, V, F. b) V, V, F, V, F. c) V, F, V, F, F. d) F, V, V, F, V. e) F, V, F, V, V. ) A linguagem {an bn cn /n 0} no satisfaz a propriedade acima.

10 / 24

33 Com base nos conhecimentos sobre projeto de circuitos sequenciais, considere as armativas a seguir. I. O projeto de circuitos sequenciais usando ip-ops crtico devido ao problema conhecido como transparncia de ip-ops. II. Uma vez que um ip-op sabidamente sensvel a uma das bordas do relgio, o tempo de permanncia do relgio em nvel alto ou baixo no mais crtico para o funcionamento do circuito sequencial. III. Tempo de setup o tempo durante o qual a entrada deve ser mantida estvel antes da transio ativa do relgio. IV. Um ip-op tipo D pode ser implementado com dois latchs tipo D ou com um latch tipo D e um circuito detector de borda. Assinale a alternativa correta. a) b) c) d) e) Somente as armativas I e IV so corretas. Somente as armativas II e III so corretas. Somente as armativas III e IV so corretas. Somente as armativas I, II e III so corretas. Somente as armativas I, II e IV so corretas.

34 Em linguagens orientadas a objetos, o polimorsmo refere-se ligao tardia de uma chamada a uma ou vrias implementaes diferentes de um mtodo em uma hierarquia de herana. Neste contexto, considere as seguintes classes descritas na Linguagem C++. #include using namespace std; class PosComp1 { public: int Calcula() { return 1; }; }; class PosComp2 : public PosComp1 { public: virtual int Calcula() { return 2; } }; class PosComp3 : public PosComp2 { public: int Calcula() { return 3; } }; Se estas classes forem utilizadas a partir do programa a seguir int main() { int Result=0; PosComp1 *Objs[3]; Objs[0] = new PosComp1(); Objs[1] = new PosComp2(); Objs[2] = new PosComp3(); for (int i=0; iCalcula(); cout n; for (int i=0; iA = i; C->B = i+1; C->L = new N; C->L->A = i+1; C->L->B = i+1; C->L->L = NULL; } else { A = C; B = A->L; while (B) { if (A->B + B->B L = new N; A->L->A = A->A + B->A; A->L->B = A->B + B->B; A->L->L = B; }end while A = B; B = B->L; } } A = C; while (A) { cout A 1 e p(x) > 1 para todo vrtice x diferente de v. Considere dois vrtices u e w de G e denote por d(u, w) a distncia em G de u at w. Com base nesses dados, assinale a alternativa correta. a) Se l(u) < l(w) e p(u) < p(w), ento d(v, u) < d(v, w). b) Se l(u) < l(w) e p(u) > p(w), ento d(v, u) = d(v, w). d) Se l(u) > l(w) e p(u) > p(w), ento d(v, u) < d(v, w). e) Se l(u) < l(w) e p(u) > p(w), ento d(v, u) d(v, w). c) Se l(u) > l(w) e p(u) < p(w), ento d(v, u) d(v, w).

17 / 24

TECNOLOGIA DA COMPUTAO 51 Considere a relao a seguir, denida na linguagem SQL padro. CREATE TABLE EMPREGADO ( CODIGO NUMBER(4) PRIMARY KEY, NOME VARCHAR2(10), SALARIO NUMBER(7,2) ) Considere tambm as consultas (C1, C2, C3 e C4) a seguir, expressas na linguagem SQL. C1: select NOME from EMPREGADO where CODIGO in ((select CODIGO from EMPREGADO) minus (select E1.CODIGO from EMPREGADO E1, EMPREGADO E2 where E1.SALARIO < E2.SALARIO) ) Obs: o operador minus realiza a operao de subtrao entre relaes. C2: select NOME from EMPREGADO where SALARIO = (select max(SALARIO) from EMPREGADO) C3: Select NOME from EMPREGADO where SALARIO >= all (select SALARIO from EMPREGADO) C4: select NOME from EMPREGADO where CODIGO in ( select E1.CODIGO from EMPREGADO E1, EMPREGADO E2 where E1.SALARIO > E2.SALARIO ) Com relao s consultas, assinale a alternativa correta. a) Apenas as consultas C2 e C3 so equivalentes. b) Todas as consultas so equivalentes. c) Apenas as consultas C1 e C3 so equivalentes. d) Apenas as consultas C1 e C4 so equivalentes. e) Apenas as consultas C1, C2 e C3 so equivalentes. 52 Considere, a seguir, a gramtica livre de contexto: S aS|Sb|c Qual expresso regular gera a mesma linguagem que a gramtica denida acima? a) a* c b* b) a+ b+ c c) a+ c b+ d) c a* b* e) c a+ b+

18 / 24

53 Considere, a seguir, as escalas S1 e S2, de execuo de transaes (T).

Com base nessas informaes, considere as armativas a seguir. I. II. III. IV. a) b) c) d) e) S2 serializvel no conito. S1 serializvel no conito. S1 serializvel na viso. S2 serializvel na viso.

Assinale a alternativa correta. Somente as armativas I e II so corretas. Somente as armativas I e III so corretas. Somente as armativas III e IV so corretas. Somente as armativas I, II e IV so corretas. Somente as armativas II, III e IV so corretas.

54 Sobre a tabela de smbolos, considere as armativas a seguir. I. A tabela de smbolos associa um conjunto de atributos a cada identicador reconhecido no programa. Tais atributos so preenchidos durante a anlise sinttica. II. Uma alternativa para a implementao de escopos aninhados e regra de aninhamento mais prximo simula o comportamento de pilha na tabela de smbolos, colocando a declarao que se aplica a uma referncia no topo da pilha quando tal referncia for alcanada. III. Diferentes ocorrncias de um mesmo identicador em um programa so armazenadas na mesma entrada da tabela de smbolos. Tal estratgia evita que um mesmo identicador seja tratado de forma distinta em diferentes partes do programa. IV. A tabela de smbolos acessada durante todo o processo de traduo de cdigo. Portanto, o tempo de acesso aos dados dessa tabela tem grande impacto na ecincia do compilador e, por essa razo, ela comumente implementada utilizando tabelas hash. Assinale a alternativa correta. a) b) c) d) e) Somente as armativas I e II so corretas. Somente as armativas I e III so corretas. Somente as armativas III e IV so corretas. Somente as armativas I, II e IV so corretas. Somente as armativas II, III e IV so corretas. 19 / 24

55 Com relao ao processo tradicional de sntese de imagens em computao grca, relacione a coluna da esquerda com a coluna da direita. (I) Projeo Perspectiva (II) Volume de Visualizao (III) Modelo de Gouraud (IV) Algoritmo de Z-buffer (V) Rasterizao a) I-B, II-C, III-E, IV-D, V-A. b) I-B, II-E, III-D, IV-C, V-A. c) I-C, II-B, III-D, IV-A, V-E. d) I-C, II-D, III-B, IV-A, V-E. e) I-E, II-B, III-A, IV-D, V-C. 56 Sobre anlise sinttica, considere as armativas a seguir. I. Um analisador sinttico descendente recursivo pode apenas ser utilizado para reconhecer gramticas em que o primeiro smbolo terminal de cada subexpresso fornece informaes sucientes para a escolha da produo a ser utilizada. II. No possvel construir um analisador sinttico descendente recursivo para reconhecer a gramtica: S Sa|a. (A) Responsvel pela remoo das linhas e superfcies ocultas. (B) Dene a poro visvel da cena. (C) Mapeia coordenadas num espao tridimensional para um espao bidimensional. (D) Efetua interpolao linear das cores. (E) Encontra as coordenadas de pixel na tela.

Assinale a alternativa que contm a associao correta.

III. De forma geral, os analisadores sintticos descendentes so capazes de reconhecer um nmero maior de gramticas do que os analisadores sintticos ascendentes. IV. Os analisadores sintticos ascendentes fazem uso de pilha e um autmato nito para auxiliar na validao da sintaxe de um programa. Assinale a alternativa correta. a) Somente as armativas I e II so corretas. b) Somente as armativas I e III so corretas. c) Somente as armativas III e IV so corretas. d) Somente as armativas I, II e IV so corretas. e) Somente as armativas II, III e IV so corretas. 57 A UML (Unied Modeling Language) uma linguagem visual para visualizar, especicar, construir e documentar os artefatos dos sistemas. A palavra visual importante, pois a UML uma notao diagramtica. Em relao aos diagramas da UML, correto armar: a) Os diagramas de interao descrevem como grupos de classes colaboram em algum comportamento. O diagrama de sequncia um diagrama de interao que, normalmente, captura o comportamento de vrios cenrios, mostrando como as classes e mensagens so passadas no contexto de um conjunto de casos de uso. b) O diagrama de mquina de estados permite visualizar um workow ou um processo de negcio. especialmente til para detalhar um caso de uso que descreve um workow complexo envolvendo muitas partes e aes concorrentes. c) A UML 2.0 divide os diagramas em duas categorias: (i) diagramas estruturais (ou estticos) e (ii) diagramas comportamentais (ou dinmicos). O diagrama de componentes um diagrama comportamental que representa a topologia fsica do sistema, bem como os vrios componentes de software de um sistema e suas dependncias. d) O diagrama de casos de uso apresenta as funcionalidades externamente observveis do sistema e os elementos externos ao sistema que interagem com ele. No diagrama de casos de uso, um elemento externo que interage com o sistema denominado de ator. Os atores podem ser, por exemplo, pessoas, outros sistemas e equipamentos. e) Um modelo de domnio ilustrado com um conjunto de diagramas de classes. O termo Modelo de domnio signica uma representao de classes conceituais do mundo real e as restries inerentes tecnologia a ser utilizada na soluo. importante constarem neste modelo os atributos e operaes de cada classe. 20 / 24

58 Em cenas de computao grca, para aumentar o realismo visual, comum aplicar-se um modelo de iluminao local que calcula as cores nos vrtices dos tringulos a partir das propriedades de reexo do objeto, propriedades geomtricas do objeto e propriedades da(s) fonte(s) de luz. Sobre os modelos de iluminao locais, considere as armativas a seguir. I. A parcela de reexo difusa depende da posio do observador. II. A parcela especular pode ser aproximada pelo modelo de Phong, que estabelece que a reexo especular de uma superfcie proporcional ao cosseno do ngulo entre o vetor direo do observador e o vetor que estabelece a direo de reexo especular ideal. III. A parcela difusa ideal de iluminao pode ser aproximada pela lei de Lambert, que estabelece que a reexo difusa de uma superfcie proporcional ao ngulo entre o vetor normal superfcie e o vetor direo da fonte de luz. IV. A parcela de luz ambiente aproxima as mltiplas reexes de luz das inmeras superfcies presentes na cena. Assinale a alternativa correta. a) Somente as armativas I e II so corretas. b) Somente as armativas I e III so corretas. c) Somente as armativas III e IV so corretas. d) Somente as armativas I, II e IV so corretas. e) Somente as armativas II, III e IV so corretas. 59 Considere o algoritmo A* (A Estrela / A Star) usado para a busca de uma trajetria (pathnding), sendo aplicado sobre um mapa do tipo grade de ocupao, com custos de passagem associados a cada uma das clulas da grade e com a seguinte congurao de nodos listados no conjunto em aberto (open-set): Nodo Nodo Nodo Nodo Nodo 1: 2: 3: 4: 5: g(1)=19; g(2)=18; g(3)=13; g(4)=16; g(5)=16; h(1)=6; h(2)=4; h(3)=5; h(4)=3; h(5)=3; L=6; C=8 L=7; C=9 L=5; C=10 L=9; C=8 L=10;C=7

onde L e C so a linha e coluna do respectivo nodo dentro da grade de ocupao. A posio alvo a ser alcanada dentro da trajetria deste exemplo denida pela linha e coluna L_Alvo=10 e C_Alvo=10, ou seja, a coordenada (10,10). g(n) representa o custo (gasto) do caminho percorrido e h(n) representa a estimativa heurstica de custo at o alvo da clula em questo, sendo que n representa o nmero do nodo que identica as clulas, e esta clula ocupa uma determinada posio (L,C) dentro da grade. Qual dos seguintes nodos ser selecionado do conjunto em aberto como sendo o prximo nodo a ser avaliado, depois removido do conjunto de nodos em aberto (open-set) e colocado na lista de nodos j visitados (closed-set)? a) Nodo 1 b) Nodo 2 c) Nodo 3 d) Nodo 4 e) Nodo 5 60 Tendo em vista a complexidade envolvida no desenvolvimento de um sistema de software, importante assegurar que ele cumpra com suas especicaes e atenda s necessidades dos usurios. Sobre o desenvolvimento de software, considere as armativas a seguir. I. A Validao tem como objetivo responder: Estamos construindo o produto certo? J a Vericao busca responder: Estamos construindo o produto corretamente? II. Em um cadastro, encontra-se um campo de entrada solicitando o ano de nascimento, sendo vlidos valores entre 1900 e 2011. Os casos de testes para este campo, considerando a tcnica de anlise de valor limite, so: 1899, 1900, 1901, 2010, 2011, 2012 e 0. 21 / 24

III. As atividades de Vericao e Validao envolvem atividades de anlise esttica e de anlise dinmica do produto em desenvolvimento, e apenas as atividades de anlise dinmica envolvem a execuo do produto. IV. Um dos objetivos dos mtodos de teste de caixa-preta garantir que todos os caminhos de um programa tenham sido exercitados pelo menos uma vez, podendo-se aplicar a tcnica do teste do caminho bsico para este m. Assinale a alternativa correta. a) Somente as armativas I e II so corretas. b) Somente as armativas I e III so corretas. c) Somente as armativas III e IV so corretas. d) Somente as armativas I, II e IV so corretas. e) Somente as armativas II, III e IV so corretas. 61 O algoritmo de busca Minimax uma tcnica de Inteligncia Articial muito usada em jogos. Com relao a esse algoritmo, considere as armativas a seguir. I. O Minimax um algoritmo que faz uma busca exaustiva no espao de estados considerando as possveis jogadas de um oponente a m de encontrar a soluo tima. II. A poda Alfa-Beta, junto ao Minimax, utiliza-se de uma heurstica de corte limitando a profundidade em termos do nmero de jogadas de cada oponente. III. O Minimax um algoritmo que faz uma busca heurstica do tipo em largura (Breadth-rst_search). IV. O Minimax se caracteriza por ser um algoritmo de busca em jogos com adversrios. Assinale a alternativa correta. a) Somente as armativas I e II so corretas. b) Somente as armativas I e IV so corretas. c) Somente as armativas III e IV so corretas. d) Somente as armativas I, II e III so corretas. e) Somente as armativas II, III e IV so corretas. 62 No que tange rea de segmentao de imagens, considere as armativas a seguir. I. A tcnica de componentes conexos considerada um tipo de segmentao, pois realiza o agrupamento de pixels adjacentes. II. A segmentao de imagens identica as cores que se encontram fora do espectro de cores RGB, adequando a sua intensidade conforme os limites deste espectro. III. A segmentao de imagens consiste em produzir regies na imagem com base em algum critrio de similaridade, homogeneidade e continuidade. IV. A segmentao uma forma de compactao de imagem, ocasionando, no entanto, perda na qualidade. Assinale a alternativa correta. a) Somente as armativas I e II so corretas. b) Somente as armativas I e IV so corretas. c) Somente as armativas III e IV so corretas. d) Somente as armativas I, II e III so corretas. e) Somente as armativas II, III e IV so corretas.

22 / 24

63 Observe as propriedades a seguir. i. Algoritmo de Aprendizado Indutivo como parte integrada do mtodo. ii. Capacidade de generalizao do aprendizado a partir de exemplos e avaliao do treinamento usando validao cruzada (cross-validation). iii. Uso do ganho de informao como critrio de deciso ao ponderar sobre a escolha de atributos. iv. Algoritmo aceita o tratamento de atributos contnuos (quantitativos) ou discretos (qualitativos). Assinale a alternativa que apresenta a tcnica de Inteligncia Articial que rene todas as propriedades listadas. a) rvores de Deciso (C4.5). b) Redes Neurais Articiais (Back-Propagation). c) Algoritmos Genticos (Michigan Approach). d) Conjuntos e Lgica Fuzzy (FIS - Fuzzy Inference System). e) Sistemas Especialistas (Forward Chaining). 64 Em relao transmisso com bras ticas, considere as armativas a seguir. I. A velocidade de propagao em uma bra tica muito superior velocidade de propagao em um cabo coaxial. II. Uma bra monomodo, por permitir luz se propagar apenas em um modo, permite obter uma taxa em bps bem superior de uma bra multimodo. III. Pode-se ter comunicao full-duplex (transmisso simultnea nos dois sentidos) utilizando-se apenas uma bra nica e no um par de bras. IV. A atenuao em bra tica ocorre devido principalmente absoro (produo de calor) e radiao e independe do comprimento de onda utilizado na transmisso da luz. Assinale a alternativa correta. a) Somente as armativas I e IV so corretas. b) Somente as armativas II e III so corretas. c) Somente as armativas III e IV so corretas. d) Somente as armativas I, II e III so corretas. e) Somente as armativas I, II e IV so corretas. 65 Com base na diviso dos protocolos de comunicao em camadas, assinale a alternativa correta. a) O modelo de protocolos em camadas dene que protocolos so utilizados entre as camadas de um mesmo hospedeiro. b) No modelo em camadas, cada camada suporta apenas um nico protocolo. c) O uso de camadas em protocolos de comunicao surgiu para diminuir o overhead. d) Uma camada pode oferecer um servio convel para uma camada acima, mesmo que a camada abaixo no seja convel. e) A arquitetura TCP/IP padroniza os protocolos das camadas fsica e de enlace. 66 A converso de imagens de RGB para tons de cinza pode ser realizada atravs da mdia dos componentes de cores. No entanto, esta converso produz uma escala de brilho na qual a percepo no equivalente ao brilho na imagem colorida. A forma adequada de calcular a luminncia Y dada pela equao: a) Y = 0.299 R + 0.587 G + 0.114 B c) Y = R + G + B d) Y = R2 + G2 + B 2 R+G+B e) Y = 3 b) Y = 0.587 R + 0.114 G + 0.299 B

23 / 24

67 Assuma uma topologia de rede local Ethernet comutada, formada pela interconexo de trs comutadores (switches SW1, SW2 e SW3), como mostrado a seguir.

10 estaes esto conectadas diretamente ao switch 1, 9 estaes ao switch 2 e 15 estaes ao switch 3. Supondo-se que todas as estaes esto ativas e transmitindo na rede local simultaneamente, assinale a alternativa correta quanto quantidade mnima de endereos MAC a serem armazenados nos buffers das portas X (de SW1), Y (de SW2) e Z (de SW3) para que no haja a necessidade de gerao de broadcast numa transmisso entre duas estaes quaisquer, aps o equilbrio no preenchimento dos buffers para armazenamento de endereo MAC nas portas dos comutadores. a) X=10, Y=9, Z=15 b) X=24, Y=10, Z=19 c) X=9, Y=10, Z=15 d) X=34, Y=34, Z=34 e) X=10, Y=25, Z=15 68 Qual dos parmetros a seguir tem maior impacto sobre o desempenho de algoritmos distribudos? a) O volume total de dados transferidos. b) A transparncia de dados. c) A transparncia de execuo. d) A poltica de escalonamento de tarefas em cada n do sistema. e) O nmero de mensagens trocadas. 69 Sobre o acesso residencial de banda larga, atravs de modem a cabo (cable modem) ou ADSL (asymmetrical digital subscriber line), assinale a armativa correta. a) O desempenho do acesso em arquitetura de modem a cabo independe de quantos usurios esto usando simultaneamente a rede, porque o cabo trabalha com multiplexao em frequncia (FDM). b) Na tecnologia de modem a cabo, a taxa mxima de transmisso (em bps) varivel e alocada de acordo com a demanda do usurio. c) A banda passante usada nas comunicaes digitais atravs das linhas de assinante, como visto na tecnologia ADSL, a mesma usada para a transmisso de voz e da ordem de 4 kHz. d) Em ADSL, a taxa mxima de operao em bps independe do nvel de rudo da linha e da distncia at a central da operadora. e) Em ADSL, trabalha-se com multiplexao em frequncia, e a taxa de acesso do assinante depende do acesso de outros usurios. 70 O Google File System (GFS) o sistema de arquivos distribudos usado pela Google em seus sistemas. Uma caracterstica marcante nele o uso de blocos xos de 64 megabytes (chunks) para o armazenamento de arquivos, que so replicados atravs de cpias em chunkservers, gerenciadas por um mestre em cada cluster. Assinale a alternativa que contm uma vantagem nessa estrutura. a) Permite o acesso sequencial e direto de arquivos completos em um nico bloco. b) estritamente compatvel com NFS e AFS. c) Permite acesso indexado de forma eciente. d) O uso de chunkservers elimina a necessidade de controle de replicao. e) Aumenta o volume de metadados para facilitar os processos de busca. 24 / 24