enade computacao2008

2008

Computao

Carlos Augusto ProloFabiano Passuelo Hessel

Miriam Sayo(organizadores)

ENADE COMENTADO 2008:

Computao

Pontifcia Universidade Catlica do Rio Grande do Sul

Chanceler: Dom Dadeus Grings

Reitor:

Joaquim Clotet

Vice-Reitor: Evilzio Teixeira

Conselho Editorial:

Antnio Carlos Hohlfeldt Elaine Turk Faria

Gilberto Keller de Andrade Helenita Rosa Franco

Jaderson Costa da Costa Jane Rita Caetano da Silveira Jernimo Carlos Santos Braga

Jorge Campos da Costa Jorge Luis Nicolas Audy (Presidente)

Jos Antnio Poli de Figueiredo Jussara Maria Rosa Mendes

Lauro Kopper Filho Maria Eunice Moreira

Maria Lcia Tiellet Nunes Marlia Costa Morosini

Ney Laert Vilar Calazans Ren Ernaini Gertz

Ricardo Timm de Souza Ruth Maria Chitt Gauer

EDIPUCRS: Jernimo Carlos Santos Braga Diretor Jorge Campos da Costa Editor-chefe

Carlos Augusto Prolo

Fabiano Passuelo Hessel

Miriam Sayo (Organizadores)

ENADE COMENTADO 2008:

Computao

Porto Alegre 2009

EDIPUCRS, 2009

Capa: Vincius de Almeida Xavier

Preparao de originais: Carlos Augusto Prolo

Diagramao: Josianni dos Santos Nunes

Reviso lingustica: Grasielly Hanke Angeli

Questes retiradas da prova do ENADE 2008 da rea de Computao

Dados Internacionais de Catalogao na Publicao (CIP)

E56 ENADE comentado 2008 [recurso eletrnico] : computao / Carlos Augusto Prolo, Fabiano Passuelo Hessel, Miriam Sayo (Organizadores). Porto Alegre : EDIPUCRS, 2009. 184 p.

Sistema requerido: Adobe Acrobat Reader Modo de Acesso: World Wide Web:

ISBN 978-85-7430-852-4 (on-line)

1. Ensino Superior Brasil Avaliao. 2. Exame Nacional de Cursos (Educao). 3. Computao Ensino Superior. I. Prolo, Carlos Augusto. II. Hessel, Fabiano Passuelo. III. Sayo, Miriam.

CDD 378.81

Ficha Catalogrfica elaborada pelo Setor de Tratamento da Informao da BC-PUCRS

Av. Ipiranga, 6681 - Prdio 33 Caixa Postal 1429

90619-900 Porto Alegre, RS - BRASIL Fone/Fax: (51) 3320-3711 E-mail: [email protected] http://www.edipucrs.com.br

SUMRIO

APRESENTAO ............................................................................................... 12

Avelino Francisco Zorzo

QUESTES DO NCLEO COMUM

QUESTO 11 ....................................................................................................... 16

Fernanda Denardin Walker

QUESTO 12 ....................................................................................................... 19

Bernardo Copstein e Flvio Moreira de Oliveira

QUESTO 13 ....................................................................................................... 22


QUESTO 14 ....................................................................................................... 24

Bernardo Copstein e Jlio Henrique Arajo Pereira Machado

QUESTO 15 ....................................................................................................... 28

Dilnei Venturini e Jlio Henrique Arajo Pereira Machado

QUESTO 16 ....................................................................................................... 30

Rafael Prikladnicki

QUESTO 17 ....................................................................................................... 33

Alfio Ricardo de Brito Martini

QUESTO 18 ....................................................................................................... 36

Michael da Costa Mra

QUESTO 19 ....................................................................................................... 38

Csar Augusto Fonticielha De Rose e Tiago Coelho Ferreto

QUESTO 20 DISCURSIVA.............................................................................. 40

Joo Batista Souza de Oliveira

QUESTES DO BACHARELADO EM CINCIA DA COMPUTAO

QUESTO 21 ....................................................................................................... 43

Eduardo Henrique Pereira de Arruda

QUESTO 22 ....................................................................................................... 45

Alexandre Agustini

QUESTO 23 ....................................................................................................... 47


QUESTO 24 ....................................................................................................... 49


QUESTO 25 ....................................................................................................... 52

Soraia Raupp Musse

QUESTO 26 ....................................................................................................... 54

Isabel Harb Manssour, Marcelo Cohen e Mrcio Sarroglia Pinho

QUESTO 27 ....................................................................................................... 56

Ana Cristina Benso da Silva e Cristina Moreira Nunes

QUESTO 28 ....................................................................................................... 57

Renata Viera

QUESTO 29 ....................................................................................................... 59


QUESTO 30 ....................................................................................................... 62


QUESTO 31 ....................................................................................................... 63

Michael da Costa Mra

QUESTO 32 ....................................................................................................... 65

Paulo Henrique Lemelle Fernandes

QUESTO 33 ....................................................................................................... 69

Alexandre Agustini

QUESTO 34 ....................................................................................................... 71


QUESTO 35 ....................................................................................................... 73


QUESTO 36 ....................................................................................................... 75


QUESTO 37 ....................................................................................................... 78

Hlio Radke Bittencourt

QUESTO 38 ....................................................................................................... 80

Csar Augusto Missio Marcon





QUESTES DA ENGENHARIA DE COMPUTAO

QUESTO 41 ....................................................................................................... 89

Anderson Royes Terroso e Pablo Alberto Spiller

QUESTO 42 ....................................................................................................... 94


QUESTO 43 ....................................................................................................... 95

Ney Laert Vilar Calazans

QUESTO 44 (ANULADA) ................................................................................... 98

QUESTO 45 ......................................................................................................100

Dalcidio Moraes Claudio

QUESTO 46 ......................................................................................................102


QUESTO 47 ......................................................................................................104

Fernando Gehm Moraes

QUESTO 48 ......................................................................................................105


QUESTO 49 ......................................................................................................106

Mrcio Sarroglia Pinho, Isabel Harb Manssour e Marcelo Cohen

QUESTO 50 ......................................................................................................107

Ney Laert Vilar Calazans

QUESTO 51 ......................................................................................................111

Joo Batista Souza de Oliveira

QUESTO 52 ......................................................................................................114

Alexandre Agustini

QUESTO 53 ......................................................................................................116

Hlio Radke Bittencourt

QUESTO 54 ......................................................................................................119


QUESTO 55 ......................................................................................................121

Eduardo Augusto Bezerra

QUESTO 56 ......................................................................................................124


QUESTO 57 ......................................................................................................126


QUESTO 58 ......................................................................................................127


QUESTO 59 DISCURSIVA.............................................................................128

Celso Maciel da Costa


Edgar Bortolini

QUESTES DO BACHARELADO EM SISTEMAS DE INFORMAO

QUESTO 61 ......................................................................................................134

Gilberto Keller de Andrade

QUESTO 62 ......................................................................................................137

Ronei Martins Ferrigolo

QUESTO 63 ......................................................................................................140


QUESTO 64 ......................................................................................................142

Gilberto Keller de Andrade

QUESTO 65 ......................................................................................................144

Marcelo Hideki Yamaguti

QUESTO 66 ......................................................................................................146

Dilnei Venturini

QUESTO 67 ......................................................................................................148


QUESTO 68 ......................................................................................................149

Eduardo Henrique Pereira de Arruda e Duncan Dubugras Alcoba Ruiz

QUESTO 69 ......................................................................................................151

Miriam Sayo

QUESTO 70 ......................................................................................................153


QUESTO 71 ......................................................................................................154


QUESTO 72 ......................................................................................................156

Rafael Prikladnicki

QUESTO 73 ......................................................................................................158

Eduardo Meira Peres

QUESTO 74 ......................................................................................................164

Marco Aurlio Souza Mangan

QUESTO 75 ......................................................................................................167

Tiago Coelho Ferreto e Cristina Moreira Nunes

QUESTO 76 ......................................................................................................169

Duncan Dubugras Alcoba Ruiz

QUESTO 77 ......................................................................................................170

Miriam Sayo

QUESTO 78 ......................................................................................................173

Ana Paula Terra Bacelo


Ana Paula Terra Bacelo, Carlos Augusto Prolo, Daniel Antonio Callegari, Gilberto

Keller de Andrade, Jorge Luis Nicolas Audy, Marcelo Hideki Yamaguti, Marco

Aurlio Souza Mangan, Miriam Sayo, Ronei Martins Ferrigolo



LISTA DE CONTRIBUINTES..............................................................................183

12

APRESENTAO

A avaliao de estudantes tem sido prtica h muitos anos como forma de

verificar o aprendizado dos alunos em relao a determinados contedos. Nos

ltimos anos temos notado uma crescente demanda, da prpria sociedade, em

conhecer o resultado da avaliao de estudantes no somente em relao a um

determinado contedo, mas a um conjunto de contedos. Essas avaliaes

buscam trazer informaes sobre a formao de um determinado estudante nas

diversas instituies existentes no Brasil (o mesmo processo tambm acontece

em diversos outros pases).

Na rea de Computao as principais instituies de ensino superior do

Brasil com programas de ps-graduao sentiam a necessidade de uma

avaliao global de estudantes dos cursos de Computao. Como a rea no

possua um sistema de avaliao nacional, o Frum de Coordenadores de Ps-

Graduao, um Grupo de Trabalho da Sociedade Brasileira de Computao

(SBC), props uma avaliao para todos os alunos que desejassem concorrer a

uma vaga em um programa de ps-graduao em Computao no Brasil. Esta

avaliao recebeu o nome de POSCOMP e realizada h diversos anos pela

SBC. A necessidade desta avaliao surgiu para que o processo de seleo fosse

o mais justo possvel, pois, em geral, a mdia final de cada aluno difere muito de

instituio para instituio. Entretanto, o POSCOMP uma avaliao

individualizada, na qual os resultados no so divulgados de maneira ampla e

realizada de maneira voluntria, no servindo para um processo de avaliao de

cursos ou institucionais de maneira ampla.

Para uma avaliao mais geral, no Brasil existem duas principais

avaliaes oficiais realizadas com estudantes que finalizam o Ensino Mdio ou

Ensino Superior. Quando terminam o Ensino Mdio, os estudantes so avaliados

por meio do Exame Nacional de Ensino Mdio (ENEM). Por outro lado, os

estudantes ingressantes (aqueles que j realizaram de 7% a 22% da carga

horria do curso) ou concluintes (aqueles que j realizaram pelo menos 80% da

carga horria do curso) de algum curso de graduao so avaliados atravs do

13

Exame Nacional de Desempenho de Estudantes (ENADE). O ENADE faz parte do

Sistema Nacional de Avaliao da Educao Superior (SINAES) e busca aferir o

rendimento dos estudantes dos cursos de graduao das Instituies de Ensino

Superior no Brasil. Tal importncia dada ao ENADE pelo MEC, que o aluno

selecionado a participar tem sua formatura condicionada ao efetivo

comparecimento prova, e atualmente cogita-se em universalizar a participao

do ENADE tornando-o obrigatrio a todos os estudantes. O ENADE composto

por uma prova, um questionrio de impresses dos estudantes sobre a prova, um

questionrio socioeconmico e um questionrio do coordenador do(a)

curso/habilitao. A prova composta por 40 questes, sendo 10 questes de

formao geral e 30 questes de componente especfico.

Este livro surgiu de um senso comum existente entre os professores de

que os alunos tm procurado provas j realizadas como fonte de consulta por

diversos motivos, entre os quais, curiosidade, para sentirem-se seguros quando

da realizao do ENADE, para verificar em que reas no possuem determinado

conhecimento ou como fonte de exerccios para os cursos que esto realizando.

Apesar de indicar para os estudantes onde encontrar as provas e resultados,

diversas vezes os estudantes trazem as questes para os professores no sentido

de entender a resposta apresentada. Assim este livro tenta responder alguns dos

questionamentos dos alunos.

Muitas das discusses sobre esta necessidade aconteceram na sala de

convivncia dos professores da Faculdade de Informtica (FACIN) da Pontifcia

Universidade Catlica do Rio Grande do Sul (PUCRS). Essas discusses

aconteciam entre os intervalos de aula, quando o professor Gilberto Keller de

Andrade props um desafio ao conjunto de professores: que os mesmos

respondessem s questes do ENADE de maneira comentada e juntassem essas

respostas em um livro para consulta dos estudantes.

Atravs deste volume, a Pr-Reitoria de Graduao da PUCRS, atravs da

EDIPUCRS, lana o e-book ENADE 2008 Comentado: Computao, primeiro

volume da Coleo ENADE Comentado. Esta obra apresenta as questes do

componente especfico das provas aplicadas aos alunos dos trs cursos da rea

de Computao (Cincia da Computao, Engenharia de Computao e Sistemas

14

de Informao). Este volume consiste de 10 questes comuns aos trs cursos

mais 20 questes particulares de cada curso (70 questes no total da obra).

Optou-se por no abordar neste livro as 10 questes de conhecimentos gerais

comuns a todas as provas.

O livro contou com o apoio de diversos professores das Faculdades de

Informtica, de Engenharia e de Matemtica. A organizao das questes de

cada uma das provas foi realizada pelos professores Carlos Augusto Prolo

(questes comuns e do curso de Cincia da Computao), Fabiano Passuelo

Hessel (questes do curso de Engenharia de Computao) e Miriam Sayo

(questes do curso de Sistemas de Informao). Os professores foram orientados

a responderem de maneira livre, sem seguir um padro predeterminado, podendo

trabalhar questes conceituais em suas respostas ou at observaes crticas

quanto formulao das questes. Algumas questes foram respondidas no por

um nico professor, mas por um conjunto de professores que discutiram a melhor

forma de responder s mesmas.

Este livro com certeza ser um excelente apoio aos alunos da rea de

Computao dos diversos cursos de graduao existentes no Brasil. Ao mesmo

tempo, professores tambm podero utilizar o mesmo para enriquecer o material

utilizado em sala de aula.

Porto Alegre, maio de 2009

Avelino Francisco Zorzo

Diretor da Faculdade de Informtica da PUCRS

QUESTES DO NCLEO COMUM

16

QUESTO 11

Com relao s diferentes tecnologias de armazenamento de dados, julgue os

itens a seguir.

I Quando a tenso de alimentao de uma memria ROM desligada, os

dados dessa memria so apagados. Por isso, esse tipo de memria

denominado voltil.

II O tempo de acesso memria RAM maior que o tempo de acesso a um

registrador da unidade central de processamento (UCP).

III O tempo de acesso memria cache da UCP menor que o tempo de

acesso a um disco magntico.

IV O tempo de acesso memria cache da UCP maior que o tempo de

acesso memria RAM.

Esto certos apenas os itens

(A) I e II. (B) I e III. (C) II e III. (D) II e IV. (E) III e IV. Gabarito: Alternativa C Autora: Fernanda Denardin Walker

Comentrio: Sobre o item I, segundo Loureno [1], a memria ROM (Read Only Memory

- Memria Apenas de Leitura) uma memria no voltil e apenas de leitura que

chega ao usurio j previamente gravada. O fabricante grava as informaes na

pastilha e estas so permanentes, no havendo possibilidade de alterao. Esse

tipo de memria utilizado no armazenamento de programas e/ou informaes

fixas para sistemas produzidos em srie. No entanto, existem tipos especiais de

memria ROM que permitem alterao:

17

PROM (Programmable Read Only Memory Memria Apenas de Leitura Programvel): uma memria no voltil e apenas de leitura, porm

programvel. Nesta memria, a programao pode ser realizada pelo

prprio usurio. No entanto, uma vez programada, no permite a alterao

de seu contedo.

EPROM (Erasable Programmable Read Only Memory Memria Apenas de Leitura Programvel e Apagvel): uma memria no voltil, apenas de

leitura e reprogramvel. Sua programao feita eletricamente, podendo

ser apagada atravs da exposio de sua pastilha luz ultravioleta.

EEPROM (Electrically Erasable Programmable Read Only Memory Memria Apenas de Leitura Programvel e Apagvel Eletricamente): assim

como a EPROM, esta memria pode ser programada e apagada, porm,

ao invs de utilizar luz ultravioleta para apag-la, utiliza-se um sinal

eltrico.

Pode-se concluir, ento, que a afirmativa I FALSA.

Com relao s afirmaes II, III e IV, Monteiro [2] apresenta o subsistema

de memria constitudo de um conjunto de diferentes tipos, organizados de forma

hierrquica. Para representar esta hierarquia, utilizada uma estrutura na forma

de pirmide, cuja base larga simboliza a elevada capacidade, o tempo de acesso

e o custo do componente ali representado.

Registradores

Memria cache

Memria principal

Memria auxiliar

Custo alto Velocidade alta

Capacidade baixa

Custo baixo Velocidade baixa

Capacidade elevada

18

Um dos aspectos considerados a velocidade, que se refere ao tempo de

acesso, ou seja, quanto tempo a memria gasta para colocar uma informao no

barramento de dados aps uma determinada posio ter sido endereada. O

valor do tempo de acesso de uma memria dependente da sua tecnologia de

construo e da velocidade dos seus circuitos. Ele varia bastante para cada tipo,

de alguns poucos nanossegundos (ns) at dezenas ou mesmo centenas de

milissegundos (ms), no caso da memria auxiliar.

Diante desse esquema comparativo, chega-se concluso de que as

afirmativas II e III so VERDADEIRAS, enquanto a IV FALSA.

Ento a letra C, que afirma que II e III esto CERTAS, a alternativa

correta para a questo.

Referncias: [1] LOURENO, Antonio Carlos, et al. Circuitos Digitais. So Paulo: Editora rica, 1996. [2] MONTEIRO, Mrio A. Introduo Organizao de Computadores. Editora: LTC.

19

QUESTO 12

Ao longo de todo o desenvolvimento do software, devem ser aplicadas

atividades de garantia de qualidade de software (GQS), entre as quais

se encontra a atividade de teste. Um dos critrios de teste utilizados

para gerar casos de teste o denominado critrio dos caminhos

bsicos, cujo nmero de caminhos pode ser determinado com base na

complexidade ciclomtica. Considerando-se o grafo de fluxo de

controle apresentado na figura ao lado, no qual os ns representam os

blocos de comandos e as arestas representam a transferncia de

controle, qual a quantidade de caminhos bsicos que devem ser testados no

programa associado a esse grafo de fluxo de controle, sabendo-se que essa

quantidade igual complexidade ciclomtica mais um?

(A) 1. (B) 3. (C) 4. (D) 7. (E) 8. Gabarito: Alternativa C Autores: Bernardo Copstein e Flvio Moreira de Oliveira

Comentrio: Complexidade ciclomtica uma mtrica de software desenvolvida por

Thomas J. McCabe em 1976. Ela mede a quantidade de lgica de deciso usada

em um mdulo de software. Mais especificamente, mede o nmero de caminhos

linearmente independentes atravs do cdigo fonte de um programa.

A complexidade ciclomtica medida a partir do grafo de fluxo de controle

de um programa: os nodos do grafo correspondem aos comandos do programa e

uma aresta orientada conecta dois nodos se o segundo comando puder ser

executado imediatamente aps o primeiro.

O conceito de complexidade ciclomtica importante na rea de teste de

software porque ajuda a definir o esforo de teste necessrio para se verificar um

determinado mdulo. Quanto maior a complexidade, maior o nmero de casos de

20

teste necessrios para verificar adequadamente o mdulo. Por exemplo, dado

que Cm seja a complexidade ciclomtica de um mdulo m, sabe-se que:

a) Cm a quantidade mxima de testes necessrios para se obter cobertura de

ramos sobre o grafo de fluxo de controle do mdulo m.

b) Cm a quantidade mnima de testes necessrios para se obter cobertura de

caminhos sobre o grafo de fluxo de controle do mdulo m.

A questo 12 solicita que se avalie a quantidade de caminhos bsicos que

devem ser testados no programa associado ao grafo de fluxo de controle

apresentado (ver figura 1).

Figura 1 Grafo de fluxo de controle apresentado na questo 12.

O mtodo dos caminhos bsicos de McCabe apresentado por Jorgensen

(1995). Por este mtodo, o nmero ciclomtico de um grafo G, denotado por V(G),

igual a:

V(G) = e n + p

Onde:

e = nmero de arestas do grafo

n = nmero de nodos do grafo

p = nmero de componentes de G

21

A proposta de McCabe baseia-se na teoria dos grafos, de onde se sabe

que o nmero ciclomtico de um grafo fortemente conectado corresponde quantidade de circuitos independentes do grafo (um circuito similar a uma

cadeia, sem laos ou decises).

Para Jorgensen, um componente de um grafo um conjunto maximal de

nodos conectados. Neste caso, todo grafo de programa ter p = 1, visto que

nodos no conectados correspondem a comandos que nunca sero alcanados.

No caso da figura 1, o nmero ciclomtico seria: V(G) = 9 7 + 1 = 3.

O mtodo dos caminhos bsicos de McCabe coloca ainda que, como os

grafos de programa no so fortemente conexos, necessrio acrescentar uma

aresta conectando o ltimo nodo ao primeiro de maneira a obter esta

caracterstica. Por esta razo a questo coloca que o nmero de caminhos

bsicos a serem testados igual complexidade ciclomtica mais um.

Por esta razo, dado que o nmero ciclomtico calculado foi 3, somando-

se 1, a resposta correta da questo 12 4.

A questo, porm, polmica. O prprio Jorgensen coloca que existe

confuso na literatura sobre a frmula da complexidade ciclomtica. Algumas

fontes usam a frmula V(G) = e n + p, enquanto outras usam V(G) = e n + 2p,

j prevendo na prpria frmula o acrscimo do arco extra que torna o grafo

fortemente conexo. Alm disso, todos concordam que e igual ao nmero de arestas e que n igual ao nmero de nodos, mas alguns consideram p como o nmero de componentes do grafo e outros como sendo o nmero de regies (p.

ex. Pezz e Young (2008) e Delamaro et al. (2007)). So diferenas sutis, mas

que podem causar alteraes no resultado.

Referncias: JORGENSEN, P.C. Software Testing a Craftsmans Approach. CRC Press, 1995. DELAMARO, M.E.; MALDONADO, J.C.; JINO, M. Introduo ao Teste de Software. Campus, 2007. PEZZ, M.; YOUNG, M. Teste e Anlise de Software. Bookman, 2008.

22

QUESTO 13

Considerando o conjunto A = {1, 2, 3, 4, 5, 6}, qual opo corresponde a uma

partio desse conjunto?

(A) {{1}, {2}, {3}, {4}, {5}, {6}} (B) {{1}, {1,2}, {3,4}, {5, 6}} (C) {{ }, {1, 2, 3}, {4, 5, 6}} (D) {{1, 2, 3}, {5, 6}} (E) {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}} Gabarito: Alternativa A Autor: Carlos Augusto Prolo

Comentrio: Esta uma questo bastante simples. Dado um conjunto A, uma partio

de A um conjunto de subconjuntos de A tal que:

1. A unio de todos os subconjuntos igual a A.

2. Os subconjuntos so disjuntos, isto , no h elementos comuns a dois

ou mais subconjuntos, a interseco de cada par de subconjuntos vazia.

3. No permitido o subconjunto vazio.

Mais formalmente, PA = {A1, A2, ..., An}, para n>0 uma partio de A, se:

1. A1 A2 ... An = A 2. Para todo 1

23

A alternativa A est correta porque a unio dos conjuntos {1}, {2}, {3}, {4},

{5}, {6} precisamente o conjunto A = {1, 2, 3, 4, 5, 6}; os conjuntos {1}, {2}, {3},

{4}, {5}, {6} so disjuntos entre si, isto , no h elemento repetido em mais de um

conjunto, e nenhum conjunto vazio.

A alternativa B est errada porque desrespeita a restrio 2: os conjuntos

no so disjuntos ({1} e {1,2} tem elemento em comum). A alternativa C est

errada porque desrespeita a restrio 3: o subconjunto vazio no pode estar

incluso. A alternativa D est errada porque desrespeita a regra 1: falta o elemento

4. A alternativa E est errada pelo mesmo motivo que a B: os subconjuntos no

so disjuntos.

24

QUESTO 14

Um programador props um algoritmo no-recursivo para o percurso em

preordem de uma rvore binria com as seguintes caractersticas.

h Cada n da rvore binria representado por um registro com trs campos: chave, que armazena seu identificador; esq e dir, ponteiros para os filhos esquerdo e direito, respectivamente.

h O algoritmo deve ser invocado inicialmente tomando o ponteiro para o n raiz da rvore binria como argumento.

h O algoritmo utiliza push() e pop() como funes auxiliares de empilhamento e desempilhamento de ponteiros para ns de rvore binria,

respectivamente.

A seguir, est apresentado o algoritmo proposto, em que representa o

ponteiro nulo.

Procedimento preordem (ptraiz : PtrNoArvBin)

Var ptr : PtrNoArvBin; ptr := ptraiz; Enquanto (ptr ) Faa

escreva (ptr.chave); Se (ptr.dir ) Ento

push(ptr.dir); Se (ptr.esq ) Ento

push(ptr.esq); ptr := pop();

Fim_Enquanto Fim_Procedimento

Com base nessas informaes e supondo que a raiz de uma rvore binria com n

ns seja passada ao procedimento preordem(), julgue os itens seguintes.

I O algoritmo visita cada n da rvore binria exatamente uma vez ao longo do percurso.

II O algoritmo s funcionar corretamente se o procedimento pop() for projetado de forma a retornar caso a pilha esteja vazia.

III Empilhar e desempilhar ponteiros para ns da rvore so operaes que podem ser implementadas com custo constante.

25

IV A complexidade do pior caso para o procedimento preordem() O(n). Assinale a opo correta.

(A) Apenas um item est certo. (B) Apenas os itens I e IV esto certos. (C) Apenas os itens I, II e III esto certos. (D) Apenas os itens II, III e IV esto certos. (E) Todos os itens esto certos. Gabarito: Alternativa E Autores: Bernardo Copstein e Jlio Henrique Arajo Pereira Machado

Comentrio: Esta uma questo tpica da disciplina de algoritmos e programao. Ela

envolve os conceitos bsicos de manipulao de estruturas de dados para a

soluo de um problema. No caso da questo de nmero 14, as estruturas de

dados utilizadas so: rvore binria e pilha. Alm desses conceitos, a questo

tambm aborda os tpicos de algoritmos recursivos e complexidade de

algoritmos. Em termos de linguagem de programao, a questo foi construda

sobre o paradigma estruturado.

Para a soluo da questo, deve ser utilizada a estrutura de dados rvore

binria, implementada atravs do encadeamento de ns, conforme indicado pela

primeira caracterstica do algoritmo apresentado Cada n da rvore binria

representado por um registro com trs campos: chave, que armazena seu

identificador; esq e dir, ponteiros para os filhos esquerdo e direito, respectivamente. A figura 2 traz um exemplo de rvore binria juntamente com

sua representao da estrutura de dados encadeada.

Figura 2 rvore binria e estrutura de dados correspondente

26

Alternativa I: Essa alternativa correta, pois o procedimento apresentado (pr-ordem)

um dos muitos algoritmos de caminhamento (outros algoritmos muito utilizados

so ps-ordem, ordem central e amplitude) cujo propsito percorrer uma rvore

binria de modo que cada n seja visitado uma nica vez.

A definio do algoritmo de caminhamento em pr-ordem inerentemente

recursiva e pode ser enunciada como:

1. visitar o n;

2. percorrer em pr-ordem o n filho esquerdo;

3. percorrer em pr-ordem o n filho direito.

Como exemplo, tomando a rvore da figura 2 e comeando a percorrer a

estrutura pelo n A, teramos como resultado do algoritmo de caminhamento a

sequncia de visitao: A, B, D, E, C.

O algoritmo apresentado para o caminhamento em pr-ordem uma das

possveis solues que no utilizam a recurso na soluo. Nesse caso foi

utilizada a estrutura de dados pilha como uma estrutura auxiliar que mantm uma

coleo de ns que ainda no foram visitados. Seguindo-se a execuo do

algoritmo passo a passo, verifica-se que o mesmo visita cada n da rvore uma

nica vez. Alternativa II:

A alternativa correta.

O algoritmo utiliza uma pilha para manter uma coleo de ns ainda no

visitados da rvore e, a cada lao de iterao (o lao enquanto), aps visitar o

n corrente, empilha respectivamente seus filhos direito e esquerdo, escolhendo,

dessa maneira, quais ns devero ser visitados no futuro. Como ltimo comando

no lao de iterao, o algoritmo executa uma operao de pop() que remove dessa pilha o prximo n que ser visitado em pr-ordem. Contudo, esse n

recm removido da pilha o elemento principal na condio de trmino do lao de

repetio (ptr ) e, caso nunca seja nulo(), o algoritmo ir incorrer em um lao de repetio infinito! Mas em nenhum momento o algoritmo executa uma

27

operao de empilhamento do valor nulo (push()), sendo assim, a operao pop que dever retornar o valor nulo () caso no exista mais nenhum n a ser

visitado, ou seja, caso o nodo A esteja vazio.

Alternativa III:

Essa alternativa correta, pois as operaes de empilhamento (push) e desempilhamento (pop) podem ser implementadas de maneira eficiente sobre uma pilha utilizando tanto uma estrutura encadeada quanto uma estrutura

esttica.

Para entender que o custo de tempo de execuo dessas operaes

constante, assume-se que o tempo necessrio para recuperar e armazenar um

dado na memria constante. Tambm se assume que o tempo necessrio para

efetuar operaes aritmticas bsicas e de comparao de valores tambm

constante.

Sendo assim, considere o seguinte algoritmo para implementar as

operaes de push e pop sobre um estrutura esttica de arranjo. Note que ambas as operaes realizam apenas operaes cujo tempo de execuo

considerado constante e, portanto, o tempo de execuo da mesma tambm ser

constante.

Procedimento push(no : PtrNoArvBin)

arranjo[contador++] := no; Fim_Procedimento

Procedimento pop(no : PtrNoArvBin)

retorne arranjo[--contador]; Fim_Procedimento

Alternativa IV:

Essa alternativa correta, pois para imprimir toda a rvore o algoritmo

precisa visitar todos os n nodos e cada passagem pelo lao uma visita a um

nodo. Cada operao de visita realiza um nmero constante de operaes desde

que as operaes de push() e pop() sejam implementadas em tempo constante. Como no total so n passos com um nmero constante de operaes

em cada passo, o trabalho total O(n).

28

QUESTO 15

Alm do acesso a pginas html, a Internet tem sido usada cada vez mais para a

cpia e troca de arquivos de msicas, filmes, jogos e programas. Muitos desses

arquivos possuem direitos autorais e restries de uso. Considerando o uso das

redes ponto-a-ponto para a troca de arquivos de msicas, filmes, jogos e

programas na Internet, a quem cabe a identificao e o cumprimento das

restries de uso associados a esses arquivos?

(A) aos programas de troca de arquivo (B) aos usurios (C) ao sistema operacional (D) aos produtores dos arquivos (E) aos equipamentos roteadores da Internet

Gabarito: Alternativa B Autores: Dilnei Venturini e Jlio Henrique Arajo Pereira Machado

Comentrio: A questo trata de definir a quem cabe a identificao e o cumprimento

das restries de uso de arquivos trocados atravs de redes ponto-a-ponto.

Assim, compreende-se duas questes: 1) quem identifica as restries de uso? e 2) quem cumpre as restries de uso?

A opo A refere-se aos programas de troca de arquivo. Tecnicamente falando, esses programas podem identificar a existncia de questes autorais.

Porm, no atual estado da tecnologia, os programas de troca de arquivo ainda

no possuem funcionalidades capazes de fazer cumprir eventuais restries em

100% das situaes.

A opo C refere-se ao sistema operacional. Para este pode ser utilizado o mesmo raciocnio da opo A, porm em situao ainda mais prejudicada pelo

prprio objetivo (mais genrico) de um sistema operacional.

A opo D refere-se aos produtores dos arquivos. Ao alcance destes est a possibilidade da utilizao da tecnologia para buscar bloquear a utilizao

da sua obra em situaes no autorizadas. Entretanto, novamente a experincia

29

demonstra que atualmente este objetivo impossvel de ser atingido em 100%

dos casos.

A opo E refere-se aos equipamentos roteadores da Internet. A funo bsica de um roteador definir a melhor rota (caminho) para que uma informao

(pacote de dados) chegue ao seu destino. Outras funes adicionais existentes

atualmente (p. ex., priorizao de mensagens e recursos de segurana) no so

capazes de identificar restries de uso sobre o contedo transmitido e fazer

cumprir tais restries.

A opo B refere-se aos usurios. A evoluo da tecnologia tem proporcionado o surgimento de novas formas de relaes entre consumidores e

fornecedores. Essas novas formas tanto contribuem para a divulgao do produto

quanto, em muitos casos, facilitam a quebra das regras do jogo. Independente

dos recursos tecnolgicos, os usurios possuem condies tanto de identificar (reconhecer) um contedo restrito quanto, em conhecendo-o, no execut-lo, ou execut-lo cumprindo as restries de uso existentes. Alm disso, sobre outra abordagem, um dos princpios gerais do Direito declara: a ningum lcito desconhecer a lei ou invocar o desconhecimento da lei em benefcio prprio. Deste fato decorre a responsabilidade civil e criminal do indivduo que no cumpre as restries legais. Independente das facilidades

tcnicas disponibilizadas pela tecnologia.

Assim, a quem cabe a parte do processo de identificao e cumprimento

das restries de uso associados aos arquivos o usurio (opo B).

30

QUESTO 16

O gerenciamento de configurao de software (GCS) uma atividade que deve

ser realizada para identificar, controlar, auditar e relatar as modificaes que

ocorrem durante todo o desenvolvimento ou mesmo durante a fase de

manuteno, depois que o software for entregue ao cliente. O GCS embasado

nos chamados itens de configurao, que so produzidos como resultado das

atividades de engenharia de software e que ficam armazenados em um

repositrio. Com relao ao GCS, analise as duas asseres apresentadas a

seguir.

No GCS, o processo de controle das modificaes obedece ao seguinte fluxo:

comea com um pedido de modificao de um item de configurao, que leva

aceitao ou no desse pedido e termina com a atualizao controlada desse

item no repositrio

porque

o controle das modificaes dos itens de configurao baseia-se nos processos

de check-in e check-out que fazem, respectivamente, a insero de um item de

configurao no repositrio e a retirada de itens de configurao do repositrio

para efeito de realizao das modificaes.

Acerca dessas asseres, assinale a opo correta.

(A) As duas asseres so proposies verdadeiras, e a segunda uma justificativa correta da primeira.

(B) B As duas asseres so proposies verdadeiras, e a segunda no uma justificativa correta da primeira.

(C) C A primeira assero uma proposio verdadeira, e a segunda uma proposio falsa.

(D) D A primeira assero uma proposio falsa, e a segunda uma proposio verdadeira.

(E) E As duas asseres so proposies falsas.

Gabarito: Alternativa B Autor: Rafael Prikladnicki

31

Comentrio: A Gerncia de Configurao de Software (GCS), tambm conhecida como

Gerncia de Configurao (GC) ou ainda Gesto de Configurao de Software,

uma rea da Engenharia de Software que fornece apoio s atividades de

desenvolvimento. Suas principais atribuies so o controle de verso, o controle

de mudana e a auditoria das configuraes. Tambm pode ser definida como o

conjunto de atividades projetadas para controlar as mudanas pela identificao

dos produtos do trabalho que sero alterados, estabelecendo um relacionamento

entre eles, definindo o mecanismo para o gerenciamento de diferentes verses

desses produtos, controlando as mudanas impostas, e auditando e relatando as

mudanas realizadas. Geralmente as mudanas so realizadas em itens de

configurao.

Um item de configurao um artefato produzido durante o

desenvolvimento de software e precisa sofrer controle de verses e de mudanas.

O item de configurao um elemento unitrio que ser gerenciado. Pode ser um

arquivo de cdigo fonte, um documento de texto, entre outros. A configurao de

um sistema basicamente a lista de todos os itens de configurao necessrios

para se reproduzir um determinado estado de um sistema.

Dito isto, possvel analisar as asseres apresentadas na questo 16. Vamos a elas:

A primeira assero diz que No GCS, o processo de controle das

modificaes obedece ao seguinte fluxo: comea com um pedido de modificao

de um item de configurao, que leva aceitao ou no desse pedido e termina

com a atualizao controlada desse item no repositrio.

De fato, quando existe a necessidade de modificar um item de

configurao, uma solicitao deve ser feita. Se for possvel modificar o item

desejado, a resposta ser um aceite, e ento possvel modificar o item de

configurao. Ao final, o item modificado atualizado no repositrio do projeto e

liberado para futuras modificaes.

A segunda assero diz que o controle das modificaes dos itens de

configurao baseia-se nos processos de check-in e check-out que fazem, respectivamente, a insero de um item de configurao no repositrio e a

32

retirada de itens de configurao do repositrio para efeito de realizao das

modificaes.

Para algum alterar um item de configurao, necessrio permisso para

isto. O comando que deve ser utilizado para poder alterar qualquer item de

configurao em um projeto o check-out. Aps realizar um check-out, e com as modificaes finalizadas, possvel usar o check-in para armazenar as alteraes feitas no sistema de gerncia de configurao. Ao fazer isto, as

verses anteriores do item de configurao alterado so mantidas no repositrio,

permitindo com isto a comparao entre as diferentes verses do mesmo item.

Portanto, a segunda assero tambm verdadeira.

Em relao questo em si, podemos ento analisar as possveis

alternativas. Se as duas asseres so verdadeiras, existem apenas duas

respostas candidatas: A e B. Analisando novamente as asseres, conclui-se que

a resposta correta a letra B. A razo para isto que a segunda assero no

uma justificativa da primeira. De fato, ambas so caractersticas do processo de

gerncia de configurao de software, mas a segunda no justifica a necessidade

descrita na primeira. A segunda assero apenas apresenta como funciona o

processo de permisso para alterar itens de configurao. Uma justificativa

correta da primeira assero seria que o processo de controle das modificaes

obedece ao fluxo descrito PORQUE necessrio um controle contnuo da

evoluo das funcionalidades de um sistema, com as mudanas devidamente

gerenciadas e documentadas.

33

QUESTO 17

Uma frmula bem formada da lgica de predicados vlida se ela verdadeira

para todas as interpretaes possveis. Considerando essa informao, analise as

duas asseres apresentadas a seguir.

A frmula bem formada ( x) P(x) ( x) P(x) vlida

porque,

em qualquer interpretao de uma frmula da lgica de predicados, se todo

elemento do conjunto universo tem a propriedade P, ento existe um elemento do

conjunto que tem essa propriedade.

Assinale a opo correta com relao a essas asseres.


(B) As duas asseres so proposies verdadeiras, e a segunda no uma justificativa correta da primeira.

(C) A primeira assero uma proposio verdadeira, e a segunda uma proposio falsa.

(D) A primeira assero uma proposio falsa, e a segunda uma proposio verdadeira.

(E) As duas asseres so proposies falsas.

Gabarito: Alternativa D. Autor: Alfio Ricardo de Brito Martini

Comentrio: Primeiramente, provaremos que a primeira assero no uma proposio

verdadeira, mostrando uma interpretao em que a frmula dada falsa. Antes

de prosseguirmos, convm lembrar a definio da noo de interpretao de uma

frmula na lgica de predicados.

Dada uma frmula (bem-formada) A qualquer da lgica de predicados,

uma interpretao para A dada conforme o esquema abaixo (estou fazendo

34

uma simplificao aqui, j que o correto seria definir uma interpretao com

relao a uma assinatura e no com relao a uma frmula):

a. Um conjunto no vazio D , chamado de domnio.

b. Para cada constante k presente na frmula A , um elemento )(kI do

domnio D .

c. Para cada smbolo de funo f com n argumentos em A , uma

funo total )( fI com n argumentos sobre D .

d. Para cada smbolo de predicado Q com n argumentos em A , uma

relao )(QI com n argumentos sobre D .

No nosso caso, )()()()( xPxxPxA = e, portanto, temos apenas um smbolo de predicado P com um argumento. Dessa forma, qualquer interpretao

para esta frmula resume-se em um conjunto no vazio D e uma parte dele

(subconjunto) para interpretar o predicado P . Vejamos ento dois exemplos de

interpretao para essa frmula.

1. }1,0{)(},1,0{ == PID . 2. }0{)(},1,0{ == PID .

Primeiramente, uma frmula A vlida se e somente se ela verdadeira para qualquer interpretao. Note que o operador principal da frmula uma implicao e, portanto, se o antecedente da implicao for

verdadeiro ( )()( xPx ), ento o consequente tambm deve ser ( )()( xPx ). Note que, no primeiro exemplo de interpretao, a propriedade verdadeira para

todos os valores do domnio, isto , 0=x ou 1=x , o que faz com que a frmula seja trivialmente verdadeira. No segundo caso, existe um valor que torna o

antecedente verdadeiro, e.g., 0=x , mas o consequente falso, j que a propriedade P no verdadeira para todos os valores do domnio, por exemplo,

para 1=x . Dessa forma, a segunda interpretao um contra-exemplo para a frmula A , isto , uma situao em que A falsa. Desta forma A no vlida.

35

Com relao segunda assero da questo, isto , que em qualquer

interpretao de uma frmula da lgica de predicados, se todo elemento do

conjunto universo tem a propriedade P, ento existe um elemento do conjunto que

tem essa propriedade, a mesma est correta, embora seja uma justificativa

incorreta para a assero anterior, j que ela afirma o contrrio da primeira. Na

linguagem da lgica de predicados, essa assero equivale a dizer que a frmula

)()()()( xPxxPx uma tautologia (ou um teorema). Isto , essa frmula precisa ser verdadeira para qualquer interpretao. Note que, nos dois exemplos

que mostramos acima, essa frmula verdadeira. No primeiro caso, porque tanto

o antecedente ( )()( xPx ) como o consequente ( )()( xPx ) da implicao so verdadeiros. No segundo tambm, porque o antecedente falso (a propriedade

no verdadeira para todos os casos, somente para 0=x ) e, logo, a implicao trivialmente verdadeira. Agora, para mostrar que a mesma frmula acima

verdadeira para qualquer interpretao, suficiente mostrar uma prova da

mesma, utilizando o clculo de deduo natural que consistente e completo com

relao noo de interpretao colocada anteriormente.

1. )()( xPx hiptese 2. 1,)( EaP 3. )(. xPx 2,I 4. )()()()( xPxxPx I 31

Dessa forma, a resposta correta para esta questo a alternativa D.

36

QUESTO 18

Os nmeros de Fibonacci constituem uma seqncia de nmeros na qual os dois

primeiros elementos so 0 e 1 e os demais, a soma dos dois elementos

imediatamente anteriores na seqncia. Como exemplo, a seqncia formada

pelos 10 primeiros nmeros de Fibonacci : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Mais

precisamente, possvel definir os nmeros de Fibonacci pela seguinte relao

de recorrncia:

fib (n) = 0, se n = 0 fib (n) = 1, se n = 1 fib (n) = fib (n - 1) + fib (n - 2), se n > 1

Abaixo, apresenta-se uma implementao em linguagem funcional para essa

relao de recorrncia:

fib :: Integer -> Integer fib 0 = 0 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2)

Considerando que o programa acima no reutilize resultados previamente

computados, quantas chamadas so feitas funo fib para computar fib 5?

(A) 11 (B) 12 (C) 15 (D) 24 (E) 25

Gabarito: Alternativa C Autor: Michael da Costa Mra

Comentrio: Pode-se utilizar diferentes abordagens para resolver esta questo. Um

caminho possvel seria construir a rvore de chamadas da funo gerada pela

recurso sobre a funo fib. Repare que a implementao oferecida, sem

37

reutilizao de resultados computados (tcnica conhecida como Memoizao),

reexecutaria a chamada da funo sobre argumentos previamente tratados.

Figura 3 rvore de Chamadas de Funo fib

Uma vez gerada a rvore, conta-se a quantidade de chamadas funo

fib. Neste caso, para o argumento 5, seriam 15 chamadas. importante notar que

esta abordagem no seria vivel para argumentos com valores muito elevados.

Logo, a resposta correta a letra C.

38

QUESTO 19

Uma alternativa para o aumento de desempenho de sistemas computacionais o

uso de processadores com mltiplos ncleos, chamados multicores. Nesses

sistemas, cada ncleo, normalmente, tem as funcionalidades completas de um

processador, j sendo comuns, atualmente, configuraes com 2, 4 ou mais

ncleos. Com relao ao uso de processadores multicores, e sabendo que

threads so estruturas de execuo associadas a um processo, que compartilham

suas reas de cdigo e dados, mas mantm contextos independentes, analise as

seguintes asseres. Ao dividirem suas atividades em mltiplas threads que

podem ser executadas paralelamente, aplicaes podem se beneficiar mais

efetivamente dos diversos ncleos dos processadores multicores

porque o sistema operacional nos processadores multicores pode alocar os ncleos

existentes para executar simultaneamente diversas seqncias de cdigo,

sobrepondo suas execues e, normalmente, reduzindo o tempo de resposta das

aplicaes s quais esto associadas.

Acerca dessas asseres, assinale a opo correta.


(B) As duas asseres so proposies verdadeiras, mas a segunda no uma justificativa correta da primeira.

(C) A primeira assero uma proposio verdadeira, e a segunda, uma proposio falsa.

(D) A primeira assero uma proposio falsa, e a segunda, uma proposio verdadeira.

(E) Tanto a primeira quanto a segunda asseres so proposies falsas. Gabarito: Alternativa A Autores: Csar Augusto Fonticielha De Rose e Tiago Coelho Ferreto

39

Comentrio: A resposta correta a letra A, pois as duas asseres so proposies

verdadeiras, sendo que a segunda uma justificativa correta da primeira.

Tanto as definies sobre arquiteturas multicore quanto sobre threads na

primeira assero esto corretas. A afirmao principal, a qual diz que aumento

de desempenho de sistemas computacionais pode ser obtido com o uso de

processadores com mltiplos ncleos, tambm est correta, e ainda se tomou o

cuidado de destacar que esta apenas uma das alternativas possveis para que

este ganho de desempenho ocorra.

A segunda assero pode ser entendida como uma justificativa correta da

primeira, no sentido que descreve mais detalhadamente uma das formas como as

aplicaes podem ser preparadas para que este ganho de desempenho seja

possvel. Tambm est correta a explicao de como essas aplicaes com

vrias threads so executadas pelo sistema operacional para que este aumento

de desempenho possa efetivamente ser obtido. Aqui tambm se tomou o cuidado

de se fazer uma ressalva indicando que, mesmo com todas as condies

atendidas, o tempo de execuo das aplicaes pode no ser reduzido (por

exemplo, devido a questes de E/S).

40

QUESTO 20 DISCURSIVA

Tabelas de disperso (tabelas hash) armazenam elementos com base no

valor absoluto de suas chaves e em tcnicas de tratamento de colises. As

funes de disperso transformam chaves em endereos-base da tabela, ao

passo que o tratamento de colises resolve conflitos em casos em que mais de

uma chave mapeada para um mesmo endereo-base da tabela.

Suponha que uma aplicao utilize uma tabela de disperso com 23

endereos-base (ndices de 0 a 22) e empregue h(x) = x mod 23 como funo de

disperso, em que x representa a chave do elemento cujo endereo-base deseja-

se computar. Inicialmente, essa tabela de disperso encontra-se vazia. Em

seguida, a aplicao solicita uma seqncia de inseres de elementos cujas

chaves aparecem na seguinte ordem: 44, 46, 49, 70, 27, 71, 90, 97, 95.

Com relao aplicao descrita, faa o que se pede a seguir.

A Escreva, no espao reservado, o conjunto das chaves envolvidas em colises.

B Assuma que a tabela de disperso trate colises por meio de encadeamento exterior. Esboce a tabela de disperso para mostrar seu contedo aps a

seqncia de inseres referida.

Autor: Joo Batista Souza de Oliveira

Resposta e comentrio do item A

As chaves envolvidas em colises so:

-- 49 e 95 tm coliso direta, caem na posio 3 da tabela

-- 44 e 90 tm coliso direta, caem na posio 21 da tabela

Neste item, a questo no descreve como feito o tratamento de colises,

e dependendo do caso outras chaves podem ser consideradas envolvidas.

Por exemplo, a chave 95 vai para a posio 6 porque quando ela entra na

tabela as posies 3, 4 e 5 j esto ocupadas pelos elementos 49, 27 e 97

41

respectivamente. Mas a questo no diz se as chaves dessas posies devem

ser consideradas envolvidas.

Resposta e comentrio do item B

O mais importante que a questo esclarece que o tratamento de colises

por encadeamento exterior. Isso significa que quando uma posio da tabela j

foi ocupada os novos itens que chegam para a mesma posio so colocados em

uma lista associada posio. Ou seja, a tabela passa a se comportar como uma

lista de listas (ou lista de rvores, ou outra estrutura) onde as chaves x guardadas

na estrutura que foi associada a uma posio p tm a funo de hashing h(x)=p.

Desenhando apenas as posies da tabela que tm elementos, temos

Posio Contedos

0 46

1 70

2 71

3 49 95 4 27

5 97

21 44 90

QUESTES DO

BACHARELADO EM CINCIA DA COMPUTAO

43

QUESTO 21

Considere a relao EMPREGADO (NumeroEmp, RG, nome, sobrenome, salario, endereco), em que o atributo grifado corresponde chave primria da relao. Suponha que se deseje realizar as seguintes consultas:

1 Listar o nome dos empregados com sobrenome Silva;

2 Listar o nome dos empregados em ordem crescente de seus

sobrenomes.

Em relao definio de um ndice sobre o atributo sobrenome para melhorar o desempenho das consultas acima, julgue os itens a seguir.

I Um ndice que implemente rvore-B+ ser adequado para melhorar o

desempenho da consulta 1.

II Um ndice que implemente rvore-B+ ser adequado para melhorar o


III Um ndice que implemente uma funo hash ser adequado para melhorar o


IV Um ndice que implemente uma funo hash ser adequado para melhorar o


Assinale a opo correta.

(A) Apenas um item est certo. (B) Apenas os itens I e II esto certos. (C) Apenas os itens III e IV esto certos. (D) Apenas os itens I, II e III esto certos. (E) Todos os itens esto certos. Gabarito: Alternativa D Autor: Eduardo Henrique Pereira de Arruda

44

Comentrio: O tema central da questo est relacionado otimizao de desempenho,

mais precisamente s estruturas de acesso que podem ser utilizadas para

otimizar a execuo de consultas. So referidas duas estruturas: rvores-B e

Funes Hash.

Particularmente, a questo cinge-se ao fato de que rvores-B se prestam

para otimizar consultas por igualdade, desigualdade e com ordenao. J

Funes Hash podem otimizar o acesso apenas para consultas por igualdade.

A consulta 1 uma consulta por igualdade e a consulta 2 uma consulta

com ordenao, ambas sobre a coluna sobrenome.

A assertiva I est correta, pois uma rvore-B se presta para otimizao de

consultas por igualdade, caso da consulta 1.

A assertiva II est correta, pois uma rvore-B se presta para otimizao de

consultas com ordenao, caso da consulta 2.

A assertiva III est correta, pois uma Funo Hash se presta para

otimizao de consultas por igualdade, caso da consulta 1.

J a assertiva IV est incorreta, pois a existncia da Funo Hash sobre a

coluna sobrenome no auxiliar na ordenao do resultado e acabar sendo

empregado um algoritmo de EXTERNAL SORTING para executar tal tarefa.

45

QUESTO 22

Qual tipo de software tradutor deve ser utilizado para programas em geral,

quando a velocidade de execuo uma exigncia de alta prioridade?

(A) compiladores (B) interpretadores (C) tradutores hbridos (D) macroprocessadores (E) interpretadores de macroinstrues Gabarito: Alternativa A Autor: Alexandre Agustini

Comentrio: Esta questo diz respeito a diferentes tipos de tradutores: programas que

recebem como entrada um programa em uma linguagem-fonte e traduzem esta

entrada para um programa equivalente em uma linguagem-objeto, ou linguagem-

alvo:

- compilador realiza a traduo de um programa em linguagem de alto

nvel (pascal, c, etc.) para linguagem de mquina, eventualmente de montagem. A

execuo de um programa compilado corresponde ao carregamento em memria

e desvio do fluxo de execuo.

- interpretadores realiza a traduo para um programa objeto apenas no

momento da execuo medida que as instrues so executadas, tornando os

programas interpretados claramente mais lentos que os programas compilados.

- tradutores hbridos um termo utilizado para compiladores que geram

cdigo para um cdigo intermedirio (virtual), que ser, em tempo de execuo,

interpretado por uma mquina virtual. So exemplos de tradutores hbridos o

tradutor Java e linguagens que geram cdigo para a plataforma .NET. Como o

cdigo gerado ser interpretado em tempo de execuo, esta alternativa tambm

torna o cdigo menos eficiente que o cdigo gerado por um compilador.

- macroprocessadores traduzem programas escritos em linguagem de

alto nvel (macros) em outros programas tambm escritos em linguagem de alto

46

nvel, que dever ser posteriormente traduzido. Desta forma no se aplicam como

resposta questo.

- interpretadores de macroinstrues macroinstrues dizem respeito a

conjuntos de instrues que podem ser utilizados como uma nica instruo ao

longo de um programa em linguagem de montagem, no se aplicando a

programas em geral.

Conclui-se, ento, que a resposta correta a alternativa A (Compiladores).

47

QUESTO 23

Considere o esquema de banco de dados relacional apresentado a seguir,

formado por 4 relaes, que representa o conjunto de estudantes de uma

universidade que podem, ou no, morar em repblicas (moradias compartilhadas

por estudantes). A relao Estudante foi modelada como um subconjunto da relao Pessoa. Considere que os atributos grifados correspondam chave primria da respectiva relao e os atributos que so seguidos da palavra

referencia sejam chaves estrangeiras. Pessoa(IdPessoa:integer, Nome:varchar(40), Endereco:varchar(40)) FonePessoa(IdPessoa:integer referencia Pessoa, DDD:varchar(3), Prefixo:char(4), Nro:char(4)) Republica(IdRep:integer, Nome:varchar(30), Endereco:varchar(40)) Estudante(RA:integer, Email:varchar(30), IdPessoa:integer referencia Pessoa, IdRep:integer referencia Republica)

Suponha que existam as seguintes tuplas no banco de dados:

Pessoa(1, Jos Silva, Rua 1, 20); Republica(20, Vrzea, Rua Chaves, 2001)

Qual opo apresenta apenas tuplas vlidas para esse esquema de banco de

dados relacional?

(A) Estudante(10, [email protected], null, 20); FonePessoa(10, 019, 3761, 1370)

(B) Estudante(10, [email protected], 1, null); FonePessoa(10, 019, 3761, 1370)

(C) Estudante(10, [email protected], 1, 20); FonePessoa(1, null, 3761, 1370)

(D) Estudante(10, [email protected], 1, 50); FonePessoa(1, 019, 3761, 1370)

(E) Estudante(10, [email protected], 1, null); FonePessoa(1, 019, 3761, 1370)

48

Gabarito: Alternativa E Autor: Eduardo Henrique Pereira de Arruda

Comentrio: A questo trata de restries de integridade de identidade (chave primria)

e referencial (chaves estrangeiras).

Elimina-se de pronto as alternativas onde est violada a integridade

referencial:

Alternativa A: FonePessoa referencia IdPessoa = 10. Alternativa B: FonePessoa referencia IdPessoa = 10. Alternativa D: Estudante referencia IdRep = 50.

Restam as alternativas C e E que esto corretas neste ponto.

No que se refere integridade de entidade, a alternativa C est incorreta,

pois em FonePessoa h um atributo integrante da chave primria com valor nulo.

49

QUESTO 24

Considere o bloco decodificador ilustrado acima, o qual opera segundo a tabela

apresentada. Em cada item a seguir, julgue se a funo lgica mostrada

corresponde ao circuito lgico a ela associado.

Assinale a opo correta.

(A) Apenas um item est certo. (B) Apenas os itens I e II esto certos. (C) Apenas os itens I e III esto certos. (D) Apenas os itens II e III esto certos. (E) Todos os itens esto certos.

50

Gabarito: Alternativa E Autor: Carlos Augusto Prolo

Comentrio: Das questes que eu comentei, esta foi sem dvida a que deu mais

trabalho. No porque seja difcil. Mas porque existem vrias maneiras diferentes

de se resolver a questo em um tempo razovel, aproveitando-se

oportunisticamente dos conhecimentos que se dispe. Tendo resolvido a questo,

quando mais tarde comecei a escrever meu comentrio, iniciei com a seguinte

frase: O decodificador apresentado o tradicional gerador de mintermos... e

quando percebi estava prestes a escrever um tratado. E percebi que eu no tinha

usado para resolver a questo nem 10% do que estava escrevendo. Embora todo

esse conhecimento seja relevante e til como possvel abordagem para esta e

outras questes, isto funo de um livro e no de um comentrio como este.

Serei aqui mais objetivo.

Cada item da questo apresenta um circuito e uma expresso booleana e

pede que se avalie se eles representam a mesma funo lgica. Uma maneira de

fazer isto em cada item produzir a tabela verdade de ambos, circuito e

expresso, e verificar se so idnticas. Abaixo seguem as tabelas para cada um

dos itens. A seguir, comentrios a respeito das mesmas:

ITEM III

A B CIRCUITO EXPRESSO0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1

ITEM II A B CIRCUITO EXPRESSO0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1

ITEM I A B CIRCUITO EXPRESSO0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0

51

Dadas as tabelas acima, fica bvio que nos trs casos o circuito e a

expresso representam a mesma funo (o que remete alternativa E). Agora

vamos discutir como as tabelas podem ser construdas.

A funo dada pela expresso a mais fcil. Basta avaliar a funo para

cada par de valores da entrada: 00, 01, 10, e 11. No entanto, se voc

simplesmente percebe que a primeira funo um ou-exclusivo (xor) e dado que

as outras duas expresses so triviais (and e or), a tabulao simples.

Quanto coluna do circuito: no item I, temos um or das sadas 1 e 2 do

decodificador. Neste caso, voc pode fazer o or das colunas das sadas 1 e 2 da

tabela no topo da questo, ou se voc entendeu que o decodificador um

gerador de mintermos e que a porta or est implementando a funo como soma

de mintermos (1 e 2), voc imediatamente coloca 1s nessas duas linhas e 0s

nas linhas 0 e 3. Ou seja, dependendo da sua familiaridade com os diversos

conceitos voc pode agilizar a resoluo da questo ou ainda usar uma

abordagem para verificar a correo do que voc fez atravs da outra abordagem,

reduzindo chance de erros.

No circuito do item II, o processo semelhante ao anterior, porm o

resultado da porta or invertido, conforme indicado pela bolinha na sada da

porta. Ento temos uma linha em que preliminarmente haveria 1s nas linhas 0, 1

e 2, e 0 na linha 3, porm a bolinha inverte esses valores, resultando os valores

na coluna da tabela II acima.

Infelizmente, o circuito do item III, que bastante sutil, pode comprometer

toda a questo, pois se voc analis-lo mal optar pela resposta B para a

questo. As sutilezas aqui so duas. Primeiro, voc tem que saber o que fazer

com aquele ou-exclusivo de trs entradas. Tecnicamente, voc seria instado a

lembrar que uma porta xor com mltiplas entradas, por conveno, implementa

uma generalizao do ou-exclusivo definida como tendo sada 1 se e somente se

o nmero de entradas com o valor 1 mpar. A segunda sutileza perceber que,

como o decodificador gera apenas uma sada em 1 num dado momento, aquela

porta xor, na verdade, est tendo o mesmo papel que seria desempenhado por

uma porta or, ou seja, soma de mintermos.

52

QUESTO 25

A figura acima ilustra uma imagem binria com pixels brancos formando retas

sobre um fundo preto. Com relao aplicao de transformadas sobre essa

imagem, assinale a opo correta.

(A) A transformada de Fourier, quando aplicada imagem descrita, produz como resultado um mapa de freqncias que equivale ao histograma dos nveis de cinza das retas presentes.

(B) A transformada de Hadamard da imagem apresentada tem resultado equivalente aplicao de um filtro passa-baixas, o que destaca as retas existentes.

(C) Ao se aplicar a transformada da distncia imagem binria, considerando pixels brancos como objetos, so geradas as distncias entre as retas presentes e o centro da imagem, o que permite identificar as equaes das retas formadas na imagem.

(D) O uso da transformada dos cossenos produz uma lista dos coeficientes lineares e angulares das diversas retas existentes nessa imagem binria.

(E) O resultado da aplicao da transformada de Hough usando parametrizao de retas um mapa cujos picos indicam os pixels colineares, permitindo que sejam identificados coeficientes que descrevem as diversas retas formadas na imagem.

Gabarito: Alternativa E Autora: Soraia Raupp Musse

53

Comentrio: A questo poderia ser respondida por intermdio da eliminao de algumas

opes. Ainda assim, dentre os conceitos vistos em graduao (normalmente em

disciplina de Computao Grfica), no se aprofundam as reas de

transformadas e filtros. Portanto, os alunos no conheceriam transformadas

especficas como Hadamard e Hough. Acredito que somente alunos bolsistas de

iniciao cientfica na rea especfica de processamento de imagens teriam

condies de acertar esta questo.

A) A Transformada de Fourier no equivalente a um histograma dos

nveis de cinza. De fato, a Transformada de Fourier reflete a

decomposio da imagem original em seus componentes de

frequncia espacial nas direes horizontal e vertical.

B) A Transformada de Hadamard no um filtro passa-baixa. Alm

disso, um filtro passa-baixa suaviza a imagem, o que borraria as retas

ao invs de destac-las.

C) A transformada da distncia aplicada a uma imagem binria gera

outra imagem (em tons de cinza) cujo valor para cada pixel a menor

distncia entre esse pixel e qualquer outro do objeto da imagem

binria de entrada (e no a distncia entre as retas e o centro da

imagem, conforme o enunciado).

D) A Transformada dos Cossenos (DCT) similar Transformada de

Fourier, mas usa apenas cossenos como base para a transformao.

Seu resultado descreve os componentes de frequncia da imagem, e

no coeficientes lineares ou angulares de retas.

E) RESPOSTA CORRETA. A Transformada Hough usada para

reconhecimento de linhas ou crculos.

Agradeo a Cludio Jung e Jlio C. J. Jr pela colaborao nesta resposta.

54

QUESTO 26

Figura I

Figura II

As figuras I e II apresentam duas imagens, ambas com resoluo de 246 pixels

300 pixels, sendo que a figura I apresenta 256 nveis de cinza e a figura II, 4

nveis de cinza. Considere que a imagem da figura I seja a original, tendo sido

manipulada em um nico atributo para gerar a imagem da figura II. Nessa

situao, em qual atributo se diferenciam as imagens I e II acima?

(A) resoluo (B) quantizao (C) iluminao (D) escala (E) amostragem espacial

Gabarito: Alternativa B

55

Autores: Isabel Harb Manssour, Marcelo Cohen e Mrcio Sarroglia Pinho

Comentrio: Tanto pelo enunciado da questo, como pelas figuras, fica claro que houve

uma reduo nos nveis de cinza da imagem. Este processo de reduo do

nmero de cores conhecido como quantizao, e um dos conceitos bsicos

de Processamento de Imagens estudado na Graduao. Portanto:

A) Resoluo a quantidade de pixels (geralmente expressa por colunas

x linhas) de uma determinada imagem. Neste caso, no h diferena

entre as duas imagens apresentadas.

B) RESPOSTA CORRETA, conforme explicado acima.

C) Iluminao diz respeito distribuio e caracterstica da luz que incide

em toda uma imagem. Considerando esse aspecto, no se nota

diferena entre as duas imagens.

D) Escala o tamanho com que uma imagem exibida. Neste caso, as

imagens I e II so mostradas com o mesmo tamanho.

E) Para uma imagem ser armazenada em um computador, deve ser

aplicado um processo de discretizao de coordenadas espaciais, que

chamado de amostragem. Uma mudana na taxa de amostragem

espacial implicaria em uma mudana de resoluo, o que no ocorreu

nas imagens apresentadas.

56

QUESTO 27

Em redes locais de computadores, o protocolo de controle de acesso ao meio

define um conjunto de regras que devem ser adotadas pelos mltiplos dispositivos

para compartilhar o meio fsico de transmisso. No caso de uma rede Ethernet

IEEE 802.3 conectada fisicamente a um concentrador (hub), em que abordagem

se baseia o protocolo de controle de acesso ao meio?

(A) na passagem de permisso em anel (B) na ordenao com conteno (C) na ordenao sem conteno (D) na conteno com deteco de coliso (E) na arbitragem centralizada

Gabarito: Alternativa D Autoras: Ana Cristina Benso da Silva e Cristina Moreira Nunes

Comentrio: O protocolo de controle de acesso ao meio utilizado em uma rede Ethernet

IEEE 802.3 o CSMA/CD, o qual se baseia na conteno com deteco de

coliso. Isso significa que, ao enviar um quadro, a estao de envio deve primeiro

verificar se o meio est livre (conteno) para ento realizar a transmisso do

mesmo. Caso durante o envio ocorra uma coliso com outro quadro que tambm

est sendo transmitido no mesmo tempo, a coliso ser detectada e ambas as

estaes, que estavam transmitindo seus quadros, devem esperar um tempo

aleatrio para tentar retransmiti-los.

57

QUESTO 28

A figura acima mostra uma rvore de deciso construda por um algoritmo de

aprendizado indutivo a partir de um conjunto de dados em que os objetos so

descritos por 4 atributos: X1, X2, X3 e X4. Dado um objeto de classe

desconhecida, essa rvore classifica o objeto na classe 1 ou na classe 2. A tabela

a seguir apresenta trs objetos a serem classificados: O1, O2 e O3.

A que classes corresponderiam, respectivamente, os objetos O1, O2 e O3?

(A) 1, 1 e 2 (B) 1, 2 e 1 (C) 2, 1 e 2 (D) 2, 2 e 1 (E) 1, 1 e 1 Gabarito: Alternativa A Autora: Renata Viera

Comentrio: A questo apresenta uma rvore de deciso e solicita, como resposta, a

classificao de trs objetos 01, 02 e 03.

58

Para responder questo, necessrio observar as caractersticas

descritivas de cada objeto, que so apresentadas na tabela, e seguir o fluxo

descrito pela rvore. Os ns das rvores representam cada uma das

caractersticas observveis dos objetos, e os ns folhas representam as classes,

que o valor solicitado como resposta para cada objeto.

Conforme o valor apresentado pelo objeto para um conjunto predefinido de

caractersticas, um determinado caminho ser percorrido na rvore, levando a

uma classificao.

O objeto O1, por exemplo, possui para a caracterstica X1 o valor a. De

acordo com o fluxo definido na rvore para objetos com valor X1 = a, a prxima

caracterstica a ser observada X3. O valor do objeto O1 para X3 20 (conforme

descrito na tabela) e, portanto, menor ou igual a 35, o que indica que devemos

seguir para o prximo n esquerda. O prximo nodo esquerda um nodo

folha (ou terminal). Como dito acima, os nodos folhas representam as classes.

Portanto, dadas as caractersticas de O1 (representadas na primeira linha da

tabela) e o fluxo correspondente na rvore para estas caractersticas, pode-se

concluir que O1 pertence classe 1.

Procedemos da mesma maneira para os prximos objetos O2 e O3. O2

possui b como valor de X1, o que nos leva imediatamente a uma definio de

classe. Nesse caso, a classe de O2 definida como 1.

Para classificar O3, que apresenta X1=c, seguimos para a verificao do

valor de X2, que M e nos leva identificao de O3 como sendo um objeto da

classe 2.

A resposta da questo , portanto, letra A: 1,1,2.

A questo de soluo simples, pois considera a aplicao de uma rvore

de deciso a um conjunto de exemplos (os objetos). Requer apenas o

conhecimento do conceito principal do que uma rvore de deciso. No tema

rvores de deciso, questes mais complexas poderiam considerar o processo de

induo, ou seja, os algoritmos que a partir de exemplos induzem

automaticamente uma rvore.

59

QUESTO 29

Considere a gramtica G definida pelas regras de produo ao lado,

em que os smbolos no-terminais so S, A e B, e os smbolos terminais so a e b.

Com relao a essa gramtica, correto afirmar que

(A) a gramtica G ambgua. (B) a gramtica G uma gramtica livre de contexto. (C) a cadeia aabbb gerada por essa gramtica. (D) possvel encontrar uma gramtica regular equivalente a G. (E) a gramtica G gera a cadeia nula.

Gabarito: Alternativa D Autor: Carlos Augusto Prolo

Comentrio: Esta questo muito bem feita, mas difcil, porque consegue entrelaar, de

maneira sutil, vrios conceitos de Linguagens Formais em uma nica questo: a

diferena entre o conceito de linguagem e o formalismo usado para descrev-la,

tipos de gramticas, classes de linguagens, conceito de ambiguidade em

linguagens formais, interpretao da linguagem expressa por uma gramtica

irrestrita que no livre de contexto, e ainda a capacidade de classificar a

linguagem extrada da gramtica original, percebendo que ela bem mais

simples do que o poder de descrio do tipo de gramtica usado na questo.

Devido ao nmero de tpicos envolvidos, vou resistir tentao de cobrir cada

tpico envolvido de maneira sistemtica. Ao invs, vou usar uma abordagem mais

guiada.

Quanto ao tipo da gramtica, ela no livre de contexto (alternativa B),

pois uma das regras, a segunda, tem dois smbolos do lado esquerdo. As

gramticas livres de contexto so caracterizadas por terem as regras na forma:

A , onde A um no terminal (ou varivel) e uma sequncia de smbolos terminais e no terminais possivelmente vazia. Alm de obviamente se adequar

ao tipo mais geral de gramticas irrestritas da Hierarquia de Chomsky, a

60

gramtica tambm obedece s restries do tipo de gramtica sensvel ao

contexto.

Quanto linguagem gerada, a gramtica gera sentenas que tm a forma

anb, com n>=1, ou, de outra maneira, a*ab. Se no, vejamos: o smbolo inicial obviamente S. (Apesar de isto no estar explcito, francamente falando, no vejo

o menor cabimento em algum sugerir anulao da questo devido a este

filigrana.) O primeiro passo de uma derivao tem que ser S==> AB. A partir da, pode-se usar a regra AB AAB um nmero indefinido de vezes, acrescentando assim novos As. Finalmente as duas ltimas regras permitem substituir os no

terminais A e B pelos terminais a e b, respectivamente. Uma sequncia de

derivao tpica tem ento a forma (tomamos a liberdade de usar o asterisco

caracterstico da operao de fechamento de Kleene, como em A*, para denotar

uma sequncia de 0 ou mais As na forma sentencial):

S ==> AB ==> AAB ==> AAAB ==> ... ==> AA*B ... ==> aa*b.

A linguagem aa*b gerada (as sentenas so iniciadas por um a, seguido de 0 ou mais as, e terminadas por um b) claramente uma linguagem regular,

pois a expresso aa*b uma expresso regular, que exatamente um dos formalismos usados para caracterizar a classe de linguagens regulares. Em

termos de gramticas, h dois subtipos particulares de gramticas livres de

contexto cujo poder de representao se restringe exatamente s linguagens

regulares. Esses dois tipos de gramtica, as gramticas regulares direita e as

gramticas regulares esquerda, so conjuntamente conhecidos como

gramticas regulares. Portanto, a alternativa D correta. Por curiosidade, uma

gramtica linear direita para aa*b pode ser to simples como a formada pelas regras:

S aS | ab

(A caracterstica de uma gramtica regular direita que o lado esquerdo

das produes pode ter no mximo um no terminal, e, quando houver, este deve

ser o smbolo mais direita.)

61

Pode parecer bastante surpreendente para alguns que uma gramtica que

sequer livre de contexto, gera uma linguagem que no s livre de contexto,

mas, mais do que isso, regular. Esta foi provavelmente uma das intenes dos

formuladores da questo. Uma linguagem regular aquela que to simples que

pode ser representada por uma gramtica regular. Mas nada impede que sejam usadas regras tpicas de formalismos das gramticas com poder de

descrio bem maior, dependendo do contexto da aplicao. Uma rea em que

uma situao como esta poderia fazer sentido a de aplicaes relacionadas

modelagem da fala.

Uma gramtica livre de contexto dita ambgua se existir alguma sentena

para a qual exista mais de uma rvore de derivao. No caso, a gramtica no

livre de contexto. E lcito perguntar qual seria a interpretao para o conceito de

ambiguidade em gramticas que no so livres de contexto. Uma resposta que

a literatura no define ambiguidade nem sequer para gramticas sensveis ao

contexto como a acima. E me arrisco a adotar a posio de que realmente no faz

sentido, a menos que as regras fossem marcadas quanto ao contexto. Por

exemplo, a segunda produo da gramtica da questo poderia ser vista como

(os contextos esto entre colchetes)

[] A [B] [] AA [B] ou [A] B [] [A] AB [].

Sem este tipo de marcao, nem o conceito de rvore faz sentido, menos

ainda o de ambiguidade. Vejam que o exemplo da prpria questo justifica que

no faz sentido julgar que uma gramtica sensvel ao contexto ambgua. Por

fim, alguns s vezes confundem ambiguidade com a mera existncia de mais de

uma sequncia de derivao. Veja ento o comentrio a este respeito na

questo 39.

Para encerrar a questo, as alternativas C e E esto incorretas porque nem

a sentena nula, nem a sentena aabbb tm o formato aa*b (note que as sentenas da linguagem tm exatamente um b).

62

QUESTO 30

Na comunicao sem fio, o espectro de radiofreqncia adotado um recurso

finito e apenas determinada banda de freqncia est disponvel para cada

servio. Dessa forma, torna-se crtico explorar tcnicas de mltiplo acesso que

permitam o compartilhamento da banda de freqncia do servio entre os

usurios. Qual opo apresenta apenas tcnicas de mltiplo acesso para o

compartilhamento da banda de freqncia alocada a um servio?

(A) Bluetooth, WiFi e WiMax (B) CDMA, GSM, TDMA (C) 3G, WAP e ZigBee (D) CDMA, FDMA e TDMA (E) CCMP, TKIP e WEP

Gabarito: Alternativa D Autoras: Ana Cristina Benso da Silva e Cristina Moreira Nunes

Comentrio: A questo faz relao a tcnicas de mltiplo acesso que compartilham

banda de frequncia entre os usurios. A nica resposta que indica somente

tcnicas de mltiplo acesso a letra D, onde:

CDMA (Code Division Multiple Access): tanto os dados quanto a voz so separados dos sinais por cdigos e depois so transmitidos em

um amplo conjunto de frequncias.

FDMA (Frequency Division Multiple Access): o espectro de frequncias disponvel dividido em faixas relativamente estreitas

(30KHZ), que so os canais. Cada um desses canais alocado a um

usurio no momento de realizao da chamada.

TDMA (Time Division Multiple Access): divide os canais de frequncia, e cada usurio utiliza um espao de tempo especfico para impedir

interferncias.

63

QUESTO 31

Julgue os itens a seguir, relativos a mtodos de busca com informao (busca

heurstica) e sem informao (busca cega), aplicados a problemas em que todas

as aes tm o mesmo custo, o grafo de busca tem fator de ramificao finito e as

aes no retornam a estados j visitados.

I A primeira soluo encontrada pela estratgia de busca em largura a

soluo tima.

II A primeira soluo encontrada pela estratgia de busca em profundidade a

soluo tima.

III As estratgias de busca com informao usam funes heursticas que,

quando bem definidas, permitem melhorar a eficincia da busca.

IV A estratgia de busca gulosa eficiente porque expande apenas os ns que

esto no caminho da soluo.

Esto certos apenas os itens

(A) I e II. (B) I e III. (C) I e IV. (D) II e IV. (E) III e IV.

Gabarito: Alternativa B Autor: Michael da Costa Mra

Comentrio: Analisando as quatro alternativas elencadas, temos:

I a Busca em Largura gera a rvore de busca nvel a nvel, ou seja, antes de

testar um novo nodo em um nvel n da rvore, o algoritmo garante que verifica

todos os nodos do nvel n-1. Como o grafo de busca tem fator de ramificao

finito, garantido que a estratgia de busca em amplitude no incorrer em um

lao infinito gerando nodos de um determinado nvel. Como as aes tm todas o

64

mesmo custo c (positivo), se uma soluo for encontrada em um nvel n, esta ser

necessariamente melhor que uma soluo encontrada em um nvel m > n, pois

se m > n ento c*m > c*n

Da mesma forma, como todas as aes tm o mesmo custo, todos os

nodos de um mesmo nvel tero o mesmo custo. Logo, essa estratgia encontra

uma soluo tima, e a afirmao est correta.

II J na busca em profundidade isto no acontece. A busca em profundidade

prioriza a expanso dos filhos de cada nodo testado antes de verificar os nodos

no mesmo nvel (seus irmos). Como o custo da soluo dado pelo seu valor

constante c multiplicado pelo nvel do nodo, a busca em profundidade pode

desprezar uma soluo em um nvel anterior, escolhendo uma soluo no tima.

Logo, a afirmao est incorreta.

III de fato, as heursticas so utilizadas para guiar a escolha do prximo nodo a

ser testado, em busca da soluo. Uma heurstica bem-formulada vai reduzir o

nmero de nodos a serem testados, tornando a busca mais eficiente. Note-se, no

entanto, que uma heurstica malformulada pode ter o efeito oposto, diminuindo a

eficincia do algoritmo. Mesmo assim, a afirmao est correta.

IV a Busca Gulosa determina que o nodo seguinte a ser escolhido seja aquele,

dentre os nodos disponveis, que tem o menor custo. Ao analisar apenas o timo

local, o algoritmo pode, medida que a busca avana, necessitar escolher

caminhos alternativos, pois a Busca Gulosa no garante que o caminho escolhido

seja o da soluo do problema (ou seja, um timo local no leva,

necessariamente, a um timo global). Assim, a afirmao est incorreta.

65

QUESTO 32

Uma empresa realizou uma avaliao de desempenho de um sistema web. Nessa

avaliao, foram determinados o desvio padro e a mdia do tempo de resposta

do referido sistema, tendo como base 10 consultas realizadas. Const

Documents

enade computacao2008