Prévia do material em texto
eBOOK: QUESTÕES DO ENADE COMENTADAS
Curso:
CIÊNCIAS DA COMPUTAÇÃO
Organizador(es): Sibelius Lellis Vieira
SUMÁRIO
QUESTÃO DISCURSIVA Nº 3
Autor(a): Anibal Jukemura
QUESTÃO DISCURSIVA Nº 4
Autor(a): Joriver Canedo e Sibelius Lellis Vieira
QUESTÃO DISCURSIVA Nº 5
Autor(a): Sibelius Lellis Vieira
QUESTÃO Nº 9
Autor(a): André Luiz Alves e Sibelius Lellis Vieira
QUESTÃO Nº 10
Autor(a): André Luiz Alves e Sibelius Lellis Vieira
QUESTÃO Nº 11
Autor(a): Sibelius Lellis Vieira
QUESTÃO Nº 12
Autor(a): Sibelius Lellis Vieira
QUESTÃO Nº 13
Autor(a): Cármen Cecília Centeno
QUESTÃO Nº 14
Autor(a): Sibelius Lellis Vieira
QUESTÃO Nº 15
Autor(a): Cármen Cecília Centeno
QUESTÃO Nº 16
Autor(a): Sibelius Lellis Vieira
QUESTÃO Nº 17
Autor(a): André Luiz Alves, Ronaldo Lopes de Oliveira e Sibelius Lellis Vieira
QUESTÃO Nº 18
Autor(a): Sibelius Lellis Vieira
QUESTÃO Nº 19
Autor(a): Fábio Gomes Barbosa
QUESTÃO Nº 20
Autor(a): Sibelius Lellis Vieira
QUESTÃO Nº 21
Autor(a): Sibelius Lellis Vieira
QUESTÃO Nº 22
Autor(a): Cármen Cecília Centeno
QUESTÃO Nº 23
Autor(a): Sibelius Lellis Vieira
QUESTÃO Nº 24
Autor(a): André Luiz Alves e Ronaldo Lopes de Oliveira
QUESTÃO Nº 25
Autor(a): Cármen Cecília Centeno
QUESTÃO Nº 26
Autor(a): Sibelius Lellis Vieira
QUESTÃO Nº 27
Autor(a): Cármen Cecília Centeno e Sibelius Lellis Vieira
QUESTÃO Nº 28
Autor(a): Anibal Jukemura e Sibelius Lellis Vieira
QUESTÃO Nº 29
Autor(a): Cármen Cecília Centeno e Sibelius Lellis Vieira
QUESTÃO Nº 30
Autor(a): Cármen Cecília Centeno e Sibelius Lellis Vieira
QUESTÃO Nº 31
Autor(a): Sibelius Lellis Vieira
QUESTÃO Nº 32
Autor(a): Cármen Cecília Centeno
QUESTÃO Nº 33
Autor(a): Sibelius Lellis Vieira
QUESTÃO Nº 34
Autor(a): Sibelius Lellis Vieira
QUESTÃO Nº 35
Autor(a): Wilmar Oliveira de Queiroz
QUESTÃO DISCURSIVA Nº 3
O jogo Sudoku consiste em uma matriz 9x9 dividida em 9 sub-matrizes 3x3, como mostrado
na figura a seguir.
Disponível em <http://www.en-wikipedia.org>. Acesso em 26 jul 2014 (adaptado).
A matriz está parcialmente preenchida com números de 1 a 9, e o objetivo do jogo é
completar a matriz, de forma que cada linha, coluna e sub-matriz contenham todos os
números de 1 a o.
A partir dessas informações, escreva um algoritmo recursivo baseado em retrocesso
(backtracking) para resolver o jogo. A matriz fio transformada em um vetor V de 81 posições,
contendo zeros nas posições que faltam para serem preenchidas.
Considere que existem duas funções implementadas. A primeira função, NaoHaViolacao (x, i,
V), retorna verdadeiro se a inserção do número x na posição i do vetor V não causa violação
das restrições do jogo (número repetido em linha, coluna ou sub-matriz). A segunda função,
Imprime (V) , realiza a impressão do vetor V.
Considere, ainda, que o algoritmo deve imprimir o vetor V com a solução encontrada, se esta
existir. (valor: 10,0 pontos)
Conteúdo avaliado: Algoritmos
Autor: Anibal Jukemura
Comentário:
Foi usada uma notação em português estruturado, de forma imperativa.
1 Sudoku (i,V)
2 Se i > 81 então Imprime(V) e termine; /* solução encontrada */
3 Senão se V[i]=0 então /* posição a preencher */
4 Repita para x=1 até 9
5 Se NaoHaViolacao(x,i,V) então /* registra e avança */
6 V[i]=x
7 Sudoku(i+1,V)
8 Fim se
9 Fim repita
10 V[i]=0 /* apaga solução anterior */
11 Senão Sudoku(i+1,V) /* pula posição já preenchida */
12 Fim
A análise do algoritmo Sudoku(i,V) segue da seguinte forma:
O algoritmo faz a análise da matriz como sendo um vetor. Considere i o índice
(posição) do número a ser avaliado começando em 1. Como é uma matriz 9x9, temos
81 posições. Na linha 2 o vetor será impresso quando todas as 81 posições forem
avaliadas e calculadas (preenchidas). Caso contrário, o algoritmo verifica se a
posição corrente em i deve ser preenchida (V[i]=0, na linha 2). Se não for o caso, o
algoritmo continua na linha 11 e pula-se a posição já preenchida chamando a função
Sudoku na posição i+1 (próxima posição).
As linhas 4-9 tratam o caso do preenchimento da posição corrente (V[i]=0) testando
todos os nove valores de x (1 a 9) para cada posição a ser preenchida (lembre-se:
certamente um destes valores podem ser utilizados na posição corrente). A
verificação da posição i, neste caso, inicia-se com a função NaoHaViolacao(x,i,V)
que, se retornar "VERDADEIRO", o valor corrente de x poderá ser inserido na posição
e o algoritmo continua na próxima posição (chamada recursiva na linha 7).
Repare que, se não há preenchimento para os nove valores de x na posição corrente,
ou seja, a função NaoHaViolacao(x,i,V) retorna "FALSO" para posição corrente i, o
algoritmo segue na linha 10 e apaga a solução anterior aplicada "voltando" na
aplicação recursiva daquele valor, desde a primeira chamada.
Para ilustrar o funcionamento do algoritmo, neste exemplo, se aplicarmos o algoritmo,
a primeira tentativa será preencher os espaços vazios da primeira linha com os
valores 1,2,4,8,9. Quando o algoritmo tenta preencher a posição 9 da primeira linha, a
função NaoHaViolacao(x,i,V) retornará FALSO para todos os valores tentados de x.
Assim, o algoritmo vai à linha 10 e todo um processo de retorno das chamadas
recursivas vão executando a linha 10 e apagando a solução até então tentada. Ao
retornar das chamadas recursivas, a linha 4 é executada novamente, agora com uma
nova tentativa para o valor de x e o processo é reiniciado.
QUESTÃO DISCURSIVA Nº 4
Muitas aplicações utilizam o sistema de localização (GPS) do dispositivo móvel do usuário para
descobrir qual o melhor caminho a seguir. Algumas aplicações também permitem que o
usuário notifique a ocorrência de eventos que ele presencia durante seu percurso, tais como
acidentes ou trânsito lento. Em um possível cenário, esta notificação é enviada para um
servidor centralizado, o qual é responsável por disseminar a notificação para os demais
usuários do aplicativo. Uma equipe de desenvolvimento criou uma aplicação desse tipo
utilizando uma base de dados relacional para o armazenamento de dados referentes aos
usuários, eventos e notificações enviadas. A modelagem conceitual foi feita utilizando o
diagrama entidade-relacionamento conforme apresentado na figura a seguir.
A equipe de desenvolvimento deseja adicionar as seguintes características ao modelo:
• Cada notificação deve ter data e hora;
• O grupo de usuários para o qual uma notificação é enviada deve ser restrito. Cada
usuário deve ter um grupo com um número arbitrário de amigos, que também são
usuários da aplicação, e as notificações enviadas por um usuário devem ser enviadas
somente a seus amigos. Também se deseja armazenar informações sobre quais
notificações foram enviadas para quais usuários.
Nessa situação, adapte o diagrama ER da figura para atender os novos requisitos. (valor: 10,0
pontos)
Conteúdo avaliado: Banco de dados
Autor: Joriver Canedo
Comentário:
1) Forma gráfica:
Diagrama ER abaixo.
Observação:
Nesta representação pode-se substituir o relacionamento amizade pela
entidade “Grupo” com as consequentes alterações de cardinalidade.
2) Forma escrita:
��Para a notificação ter data e hora, adicionar o atributo do tipo
timestamp;
��Para restringir o acesso da notificação para amigos do Usuário:
o criar uma relação n para n de Usuário para Usuário chamada
amizade; ou
o criar uma entidade “Grupo” com uma relação 1 para n de
Usuário para grupo.
��Para guardar as notificações enviadas para cada usuário, criar uma
relação n para n entre notificação e Usuário chamada notificações
enviadas. Neste caso, o relacionamento entre EVENTO e NOTIFICAÇÃOserá 1xN e o
relacionamento entre NOTIFICAÇÃO e USUÁRIO seria retirado e substituído pelo
relacionamento ENVIO (NxN).
QUESTÃO DISCURSIVA Nº 5
As técnicas de projeto de algoritmos são essenciais para que os desenvolvedores possam
implementar software de qualidade. Essas técnicas descrevem os princípios que devem ser
adotados para se projetar soluções algorítmicas para um dado problema. Entre as principais
técnicas, destacam-se os projetos de algoritmos por tentativa e erro, divisão e conquista,
programação dinâmica e algoritmos gulosos.
Nesse contexto, faça o que se pede nos itens a seguir.
a) Descreva o que caracteriza o projeto de algoritmos por divisão e conquista. (valor: 6,0
pontos)
b) Apresente uma situação de uso da técnica de projeto de algoritmos por divisão e
conquista. (valor: 4,0 pontos)
Conteúdo avaliado: Algoritmos e estrutura de dados
Autor: Sibelius Lellis Vieira
Comentário: a) Muitos algoritmos úteis são recursivos em sua estrutura: para resolver
um dado problema, eles evocam a si mesmo recursivamente uma ou mais vezes para
lidar com subproblemas correlatos. Tais algoritmos seguem uma abordagem de dividir
e conquistar: eles quebram ou dividem o problema em vários problemas menores que
são similares ao problema principal, mas menores em tamanho, e resolvem os
subproblemas recursivamente, ou seja, quebrando sucessivamente os subproblemas,
até alcançar um ponto em que o subproblema possa ser solucionado diretamente, e a
partir das soluções dos menores subproblemas, estas são combinadas até criar uma
solução completa para o problema original.
O paradigma de dividir e conquistar envolve 3 passos em cada nível da recursão:
Dividir o problema em um número de subproblemas que são instâncias menores do
mesmo problema;
Conquistar os subproblemas via sua solução de forma recursiva. Os subproblemas
são divididos até que atinjam um tamanho que possibilita a sua solução diretamente,
sem nova divisão.
Combinar as soluções dos subproblemas de tal forma a obter a solução do problema
original.
b) Neste ponto, ilustra-se a utilização prática do uso da técnica de divisão e conquista
no projeto de algoritmos, em uma situação simples, como por exemplo, os algoritmos
de ordenação quicksort e mergesort. No caso, será usado o algoritmo mergesort. O
algoritmo de mergesort segue de forma muito próxima o paradigma de dividir e
conquistar. Intuitivamente, opera da maneira como se segue:
• Divisão: dividir uma sequência de n elementos que devem ser ordenador em
duas subsequências, cada uma com n/2 elementos, aproximadamente.
• Conquista: ordenar as duas subsequências, e caso sejam ainda muito
grandes, dividir novamente as duas, de forma a obter quatro subsequências
do problema original. Continuar a divisão até atingir subsequências de
tamanho adequado para uma ordenação direta.
• Combinação: juntar as subsequências para produzir as respostas ordenadas.
A recursão para quando a sequência a ser ordenada tem tamanho 2 ou 1, e aí o
processo termina e os resultados intermediários são combinados para formar o
resultado final, ou seja, a sequência ordenada.
QUESTÃO Nº 9
A figura a seguir apresenta duas telas de um sistema de venda de passagens aéreas de uma
empresa. Na tela 1, o usuário selecionou sua origem, seu destino, e, logo em seguida, sua data
de ida. Ao mudar o foco para o campo de preenchimento da data de retorno, a ferramenta de
calendário apresentou automaticamente a data do dia da compra (01/09/2014), conforme
exibido na tela 2.
Com base nas telas apresentadas e em dimensões de qualidade, tais como facilidade de
aprendizagem, prevenção de erros, eficiência, memorização e satisfação subjetiva, avalie as
afirmações a seguir.
I. O botão “Ir” apresenta uma metáfora adequada com o mundo real, facilitando a
aprendizagem.
II. Na tela 1, o uso do calendário clicável não auxilia na prevenção de erros, visto que
a entrada de datas pode ser realizada manualmente pelos usuários.
III. Na tela 2, o fato de o calendário selecionar a data da compra prejudica a eficiência
da interface, já que a data preenchida é anterior à data de ida.
IV. A memorização é prejudicada pois a interface apresenta elementos gráficos em
demasia.
É correto apenas o que se afirma em
A. I e II
B. I e III
C. II e IV
D. I, III e IV
E. II, III e IV
Gabarito: B
Tipo de questão: Fácil
Conteúdo avaliado: Engenharia de Software e Interação Humano-Computador
Autor(a): André Luiz Alves e Sibelius Lellis Vieira
Comentário: A afirmação I está correta, visto que o botão “Ir” indica uma metáfora
adequada, pois trata-se de uma situação de prosseguimento de um processo. A
afirmação II está incorreta, uma vez que o calendário clicável facilita a prevenção de
erros, uma vez que as entradas não precisam ser efetuadas manualmente. A
afirmação III está correta, pois a interface da tela 2 pode prejudicar a eficiência da
interface uma vez que o usuário terá que necessariamente corrigir a data de retorno
que foi automaticamente preenchida pelo sistema quando a data da ida for maior que
a data da compra, sob pena de o sistema recusar a transação e ele ter que submetê-
la novamente. A interface não apresenta elementos gráficos além dos necessários, o
que implica que a afirmação IV está incorreta.
Referências:
OLIVEIRA NETTO, A. A. Interação humano computador. Florianópolis: Visual
Books, 2004.
SHNEIDER, Pen. et al. Designing the user interface: strategies for effective
human-computer interaction. 5. ed. New York: Addison Wesley, 2009.
QUESTÃO Nº 10
O gerenciamento de um projeto inclui atividades com o objetivo de garantir que todos os
produtos definidos no seu escopo sejam entregues no prazo estimado. Nesse contexto, avalie
as afirmações a seguir.
I. Técnicas como PERT e COM são utilizadas para obtenção de estimativas de esforço e
como apoio para definição de atividades.
II. Séries históricas, quando utilizadas para obter estimativas de esforço no
desenvolvimento de um sistema, levam à obtenção de estimativas consistentes,
independentemente do domínio de aplicação dos sistemas que deram origem às
séries históricas.
III. No caso de atraso da execução do cronograma, a contratação de novos
desenvolvedores assegura que o produto será entregue de acordo com o cronograma
inicialmente proposto.
É correto o que se afirma em
A. I, apenas
B. II, apenas
C. I e III, apenas
D. II e III, apenas
E. I, II e III
Gabarito: A
Tipo de questão: Fácil
Conteúdo avaliado: Engenharia de Software e Interação Humano-Computador
Autor(a): André Luiz Alves e Sibelius Lellis Vieira
Comentário: Afirma-se que o gerenciamento de projeto tem o objetivo de garantir que
os produtos do seu escopo sejam entregues no prazo estimado, e é solicitado que
sejam avaliadas 3 afirmações: a afirmação I apresenta as técnicas de PERT (Program
Evaluation and Review Technique) que tem o propósito de avaliar o progresso no
tempo com base em revisões, e CPM (Critical Path Method) que identifica o caminho
crítico, ou seja, as atividades que definem o tempo total do projeto como úteis para a
obtenção dos objetivos do gerenciamento. A afirmação II indica que as séries
históricas levam à obtenção de estimativas consistentes, independentemente do
domínio de aplicação que deu origem às series, o que não pode ser afirmado porque
séries históricas apenas dão uma diretriz e dependem do contexto ou domínio a
aplicação. A afirmação III diz que, no caso de atraso, a contratação de mais
empregados por si só assegura que o produto será entregue de acordo com o
cronograma, ignorando que o atraso pode advir de outras situações. As afirmaçõesII
e III são muito gerais, podendo não se aplicar a todos os casos, e são, portanto,
falsas. A única alternativa possível é a letra A, que indica apenas a afirmação I como
verdadeira.
Referências:
MEREDITH, Jack R. Administração de projetos: uma abordagem gerencial. 4. ed.
Rio de Janeiro: LTC, 2003.
CLELAND, David I. Gerenciamento de projetos. 2. ed. Rio de Janeiro: LTC, 2007.
KERZNER, Harold. Project management: a systems approach to planning,
scheduling, and controlling, 10. ed. New Jersey: Wiley, 2009.
QUESTÃO Nº 11
Considere um esquema de gerência de memória por paginação simples, onde a memória
física é dividida em quadros (frames) de 1 Kbyte e endereçada por byte. Os espaços de
endereçamento dos processos são múltiplo de 1Kbyte. A tabela de página para um
determinado processo P é apresentado a seguir, em que o primeiro bit (BV) mostra se a
página é válida (1) ou inválida (0).
BV Quadro(frame)
0 1 0010
1 1 0100
2 1 0001
3 1 0111
4 1 0000
5 1 1101
6 0 1111
7 0 0110
Com base na tabela apresentada, avalie as afirmações a seguir.
I. O endereço físico é composto por 13 bits.
II. O esquema de gerência de memória apresentado reduz a fragmentação externa.
III. A tradução do endereço lógico 0110000000110 para endereço físico causa exceção.
É correto o que se afirma em
A. I, apenas
B. II, apenas
C. I e III, apenas
D. II e III, apenas
E. I, II e III
Gabarito: B
Tipo de questão: Difícil
Conteúdo avaliado: Sistemas Operacionais e Arquitetura de Computadores
Autor(a): Sibelius Lellis Vieira
Comentário: Com base na tabela de paginação e na informação que a memória é
dividida em quadros de 1 Kbyte e endereçada por byte, existem 1024 endereços por
quadro, sendo necessário 10 bits para indicar o endereço no quadro, portanto
(210=1024). Portanto, como a tabela de páginas indica que cada quadro é identificado
por 4 bits, tem-se 14 bits de endereço físico e 13 bits de endereço lógico.
Logo, a afirmação I é falsa. O esquema apresentado reduz a fragmentação externa,
vez que qualquer área da memória pode ser usada com paginação, sendo esta uma
característica da paginação, e implicando que a afirmação II é verdadeira. Para
encontrar o endereço físico correspondente ao endereço lógico 0110000000110,
observa-se que tal endereço deve mapear a página 011 (3) para a moldura 0111 (7),
e o bit é valido, não resultando em exceção. A afirmação III é incorreta, o que
resultada na alternativa B.
Referências:
SILBERSCHATZ, A.; GAVIN B. P.; GAGNE G. Fundamentos de sistemas
operacionais. 8. ed. Rio de Janeiro: Elsevier/Campus, 2013.
TANENBAUM, Andrew S. Sistemas operacionais modernos. 3. ed. São Paulo:
Prentice-Hall, 2010.
QUESTÃO Nº 12
Analise o custo computacional dos algoritmos a seguir, que calculam o valor de um polinômio
de grau n, da forma: P(x) = anx
n+an-1 x
n-1+ ... +a1x + a0, onde os coeficientes são números de
ponto flutuante armazenados no vetor a[0..n], e o valor de n é maior que zero. Todos os
coeficientes podem assumir qualquer valor, exceto o coeficiente an que é diferente de zero.
Algoritmo 1:
soma = a[0]
Repita para i = 1 até n
Se a[i] ≠ 0.0 então
potencia = x
Repita para j = 2 até i
potencia = potência * x
Fim repita
soma = soma + a[i] * potencia
Fim se
Fim repita
Imprima (soma)
Algoritmo 2:
soma = a[n]
Repita para i = n-1 até 0 passo -1
soma = soma * x + a[i]
Fim repita
Imprima (soma)
Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação proposta entre elas.
I. Os algoritmos possuem a mesma complexidade assintótica.
PORQUE
II. Para o melhor caso, ambos os algoritmos possuem complexidade O(n).
A respeito dessas asserções, assinale a opção correta.
A. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
B. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta
da I.
C. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
D. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
E. As asserções I e II são proposições falsas.
Gabarito: D
Tipo de questão: Difícil
Conteúdo avaliado: Teoria da Computabiidade e Complexidade
Autor(a): Sibelius Lellis Vieira
Comentário: Observa-se que o algoritmo 1 contêm dois laços, um externo e um
interno, e o algoritmo 1 apresenta 1 laço. O laço externo do algoritmo 1 e o laço do
algoritmo 2 tem a mesma complexidade, mas a existência de 2 laços no algoritmo 1
invalida a asserção I. O algoritmo 1 não necessariamente executa o laço interno,
sendo que, no melhor caso, não executa o laço interno vez alguma. Portanto, a
asserção II está correta, e a alternativa D indica esta situação. Pode-se verificar que a
questão não exige que se verifique detalhadamente se os algoritmos realmente
calculam o valor do polinômio, apenas que se analise a complexidade dos algoritmos,
o que se reduz a analisar o possível número de iterações dos mesmos.
Referências:
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro:
Campus, 2012.
SZWARCFITER, Jayme Luiz, MARKEZAON, Lilian. Estrutura de Dados e seus
Algoritmos. RJ, Editora LTC. 1994.
ZIVIANI, Nivio. Projeto de algoritmos com implementações em Java e C++. São
Paulo: Cengage Learning, 2006.
QUESTÃO Nº 13
A figura a seguir apresenta uma árvore binária de pesquisa, que mantém a seguinte
propriedade fundamental: o valor associado à raiz é sempre menor do que o valor de todos os
nós da subárvore à direita e sempre maior do que o valor de todos os nós da subávore à
esquerda.
15
20
17 25
10
13 7
14
Em relação à árvore apresentada na figura, avalie as afirmações a seguir.
I. A árvore possui a vantagem de realizar a busca de elementos de forma eficiente,
como a busca binária em um vetor.
II. A árvore está desbalanceada, pois a subárvore da esquerda possui um número de nós
maior do que a subárvore da direita.
III. Quando a árvore é percorrida utilizando o método de caminhamento pós-ordem, os
valores são encontrados em ordem decrescente.
IV. O número de comparações realizadas em função do número n de elementos na
árvore em uma busca binária realizada com sucesso é O(log n).
É correto apenas o que se afirma em
A. I e III
B. I e IV
C. II e III
D. I, II e IV
E. II, III e IV
Gabarito: B
Tipo de questão: Difícil
Conteúdo avaliado: Algoritmos e Estrutura de Dados
Autor(a): Cármen Cecília Centeno
Comentário: Inicialmente, pode ser observado que a figura representa uma arvore
binária completa. Percebemos que todos os seus níveis estão completos, exceto o
último. Sendo assim, a árvore tem uma altura mínima e com certeza está balanceada,
o que exclui a afirmação II, logo as letras C, D e E estão incorretas.
Analisando as alternativas, concluímos que I está correta. A alternativa III está
incorreta, pois em um percurso de pós ordem se percorre a árvore da esquerda
depois da direita e a partir daí se imprime a raiz. Logo, o resultado seria 7,14,13,10,
17,25,20,15. A afirmação IV está correta, pois basta verificar se o valor buscado está
do lado esquerdo ou direito da árvore, procedendo da mesma forma com as
subárvores. Desta forma, a busca olha sempre metade, da metade, da metade, ... dos
nós (idem a busca binária mencionada em I), implicando em um tempo de busca de
O(log n).
Referências:
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro:
Campus, 2012.
SZWARCFITER, Jayme Luiz, MARKEZAON, Lilian. Estrutura de Dadose seus
Algoritmos. RJ, Editora LTC. 1994.
QUESTÃO Nº 14
Seja o universo U={10,20,30,40} e o conjunto dos números naturais N. com base no
conhecimento sobre lógica de predicados, avalie as afirmações a seguir.
I. H = (∀x ∈ N)(∃y ∈ U)(x<y) é válida.
II. H = (∀x ∈ N)(∃y ∈ N)(y<x) é válida.
III. H = (∀x ∈ U)(∃y ∈ U)(x>y) é inválida, sendo x=10 um contra-exemplo.
É correto o que se afirma em
A. I, apenas
B. III, apenas
C. I e II, apenas
D. II e III, apenas
E. I, II e III
Gabarito: B
Tipo de questão: Difícil
Conteúdo avaliado: Lógica e Matemática Discreta
Autor(a): Sibelius Lellis Vieira
Comentário: Três afirmações devem ser avaliadas. Normalmente, começar pela que
apresenta um contra-exemplo pode ser mais adequada, pois o contra-exemplo pode
ser avaliado sem necessidade de generalização. A afirmativa III indica que para
qualquer x (elemento) pertencente à U, existe y (também elemento de U) tal que x > y
é invalido, ou seja, existe x em U tal que não existe um y menor que x e x=10 é este
contra-exemplo. De fato, a afirmativa III é verdadeira, pois esta afirmação é realmente
inválida. Diante disto, a análise da afirmativa II pode revelar a resposta correta, pois
se II for falsa, a resposta correta é B. A afirmativa II é similar à afirmativa III, sendo
que os elementos avaliados são do conjunto de números naturais. O conjunto de
números naturais é infinito, tendo como elementos 0, 1, 2, e assim por diante. A
afirmativa diz que é válida a situação na qual, para qualquer elemento de N, existe um
elemento menor do que o primeiro. Pode-se observar que para o elemento 0 isto não
é verdade. Portanto, II é falsa e a resposta é B. Como o conjunto U está contido no
conjunto N, fica fácil verificar que a afirmação I é falsa, pois é similar à afirmação II, e
mais restritiva ainda.
Referências:
SOUZA, João Nunes da Silva. Lógica para ciência da computação: uma introdução
concisa. 2. ed. Rio de Janeiro: Elsevier, 2008.
SILVA, Flávio Correa da. Lógica para computação. São Paulo: Thomson Learning,
2006.
QUESTÃO Nº 15
Considere as seguintes expressões regulares cujo alfabeto é {a,b}.
R1 = a(a ∪ b)*
R2 = b(a ∪ b)*
Se L(R) é uma linguagem associada a uma expressão regular R, é correto afirmar que
A. L(R1) = L(r2)
B. L(R2) = {w | w termina com b}
C. Existe um autômato finito determinístico cuja linguagem é igual a L(R1) ∪ L(R2).
D. Se R3 é uma expressão regular tal que L(R3) = L(R1) ∩ L(R2), então L(R3) é uma
linguagem infinita.
E. Um autômato finito não determinístico que reconheça L(R1) ∪ L(R2) tem, pelo
menos, quatro estados.
Gabarito: C
Tipo de questão: Difícil
Conteúdo avaliado: Linguagens Formais, Autômatos e Compiladores
Autor(a): Cármen Cecília Centeno
Comentário: A linguagem L(R1) é composta das palavras ou sequências que iniciam
com “a” e a linguagem L(R2) é composta das palavras ou sequências que iniciam
com “b”. Note que a expressão regular (a ∪ b)* gera qualquer sequência de a´s e b´s.
Logo, L(R2) não termina com b necessariamente. Sabemos ainda que a união de
L(R1) e L(R2) são todas as palavras que comecem com “a” ou com “b”, ou seja
qualquer palavra sobre o alfabeto, exceto a palavra vazia. Este AFD pode ser
representado com dois estados apenas. Portanto, resta apenas a alternativa C, e
como afirmado anteriormente, um AFD de dois estados reconhece L(R1) ∪ L(R2).
Referências:
HOPCROFT, John; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introduction to
automata theory, languages, and computation. 3. ed. New Jersey: Prentice Hall,
2006.
MENEZES, Paulo Blauth. Linguagens Formais e Autômatos. RS. Editora Sagra
Luzzatto. 2002
SIPSER, Michael. Introdução a teoria da computação. 2. ed. São Paulo: Thomson
Learning, 2007.
QUESTÃO Nº 16
Uma pilha é uma estrutura de dados que armazena uma coleção de itens de dados
relacionados e que garante o seguinte funcionamento: o último elemento a ser inserido é o
primeiro a ser removido. É comum na literatura utilizar os nome push e pop para as
operações de inserção e remoção de um elemento em uma pilha, respectivamente. O
seguinte trecho de código em linguagem C define uma estrutura de dados pilha utilizando um
vetor de inteiros, bem como algumas funções para sua manipulação.
#include <stdlib.h>
#include <stdio.h>
typedef struct {
int elementos[100];
int topo;
}pilha;
pilha * cria_pilha () {
pilha * p = malloc (sizeof(pilha));
p ->topo = -1;
a,b
a,b
return pilha;
}
void push (pilha *p, int element) {
if (p ->topo >= 99)
return;
p->elementos[++p->topo] = element;
}
int pop(pilha *p) {
int a = p->elementos[p->topo];
p->topo--;
return a;
}
O programa a seguir utiliza uma pilha
int main(){
pilha * p = cria_pilha( );
push(p, 2);
push(p, 3);
push(p, 4);
pop(p);
push(p, 2);
int a = pop(p) + pop(p);
push(p, a);
a += pop(p);
printf(“ %d”, a);
return 0;
}
A esse respeito, avalie as afirmações a seguir.
I. A complexidade computacional de ambas as funções push e pop e O(1).
II. O valor exibido pelo programa seria o mesmo caso a instrução a += pop(p); fosse
trocada por a += a;
III. Em relação ao vazamento de memória (memory leak), é opcional chamar a função
free(p), pois o vetor usado pela pilha é alocado estaticamente.
É correto o que se afirma em
A. I, apenas
B. III, apenas
C. I e II, apenas
D. II e III, apenas
E. I, II e III
Gabarito: C
Tipo de questão: Difícil
Conteúdo avaliado: Algoritmos e Estrutura de Dados
Autor(a): Sibelius Lellis Vieira
Comentário: As funções push e pop empilham e desempilham um elemento da pilha,
realizando uma operação única. Tem complexidade O(1), indicando que a afirmação I
é verdadeira. A execução do programa inicia empilhando 2, 3 e 4, na ordem, e depois
desempilhando 4 e empilhando 2. Posteriormente, desempilha 2 e 3, realiza a adição
destes (a=2+3=5) e empilha este valor (5). A seguir, desempilha este valor e soma
com o valor de a, que acabou de ser empilhado (5). Portanto, empilhar 5 e somar com
o que foi empilhado é equivalente a somar a variável a consigo mesmo e colocar o
resultado em a. Portanto, II está correta. A afirmação III está incorreta, pois uma
alocação de memória foi feita via chamada à malloc, pois embora a pilha seja definida
como um vetor de elementos e um topo, a variável que a representa é dinâmica, e
pode ser alocada e desalocada por free. Logo, não é opcional invocar free(p) para
liberar memória. Logo, as afirmativas I e II estão corretas e a letra adequada é C.
Referências:
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro:
Campus, 2012.
DROZDEK, Adam. Estruturas de dados e algoritmos em C++. São Paulo: Cengage
Learning, 2002.
ZIVIANI, Nivio. Projeto de algoritmos com implementações em Java e C++. São
Paulo: Cengage Learning, 2006.
QUESTÃO Nº 17
Considerando que o gerente de qualidade é o responsável por definir os meios necessários
para se obter um produto com a qualidade desejada, bem como por estabelecer técnicas para
aferir a qualidade do produto, avalie as afirmações a seguir.
I. O uso de processos de desenvolvimento padronizados, sem adaptações,
independente do tipo de software a ser desenvolvido, assegura que o produto terá a
qualidade desejada.
II. O controle de qualidade pode ser realizado por meio de revisões, incluindo inspeções
de programas, e de artefatos de projetos.
III. Fatores de qualidade de software estão diretamente relacionados a um único atributo
interno de software.
É correto o que se afirma em
A. II, apenas
B.III, apenas
C. I e II, apenas
D. I e III, apenas
E. I, II e III
Gabarito: A
Tipo de questão: Fácil
Conteúdo avaliado: Engenharia de Software e Interação Humano-Computador
Autor(a): André Luiz Alves, Ronaldo Lopes de Oliveira e Sibelius Lellis Vieira
Comentário: A afirmação I está incorreta, pois os processos precisam ser adaptados
ao contexto do desenvolvimento, considerando o tipo de software que vai ser
desenvolvido, tecnologias envolvidas, recursos disponíveis e cultura organizacional.
Por exemplo, software de tempo real tem características próprias que devem ser
consideradas para acrescentar algumas atividades de desenho e também de garantia
de qualidade. A afirmação III também está incorreta, pois a qualidade de software é
multidimensional, sendo avaliada por vários fatores internos e externos. Alguns
exemplos desses fatores são funcionalidade, usabilidade, manutenibilidade,
eficiência, portabilidade e confiabilidade. A afirmação II está correta, pois a qualidade
deve ser garantida durante todo o ciclo de vida, através de revisões e outras técnicas
nos artefatos produzidos e também pelos testes no software construído.
Referências:
KOSCIANSKI, Andre; SOARES, Michel dos Santos. Qualidade de Software. 2. Ed.
São Paulo: Novatec, 2007.
SOMMERVILLE, Ian. Engenharia de Software. 8. ed. São Paulo: Pearson Education
do Brasil, 2007.
QUESTÃO Nº 18
Em relação à aplicação adequada das técnicas de Inteligência Artificial, avalie as afirmações a
seguir.
I. Indução em Árvore de Decisão é utilizada para identificação de fraudes em cartões de
crédito.
II. Redes Neurais Artificiais são utilizadas no desenvolvimento de sistemas de análise de
risco em aplicações financeiras.
III. Sistemas Especialistas baseados em regras são utilizados no desenvolvimento de
sistemas de diagnóstico de falhas em hardware.
É correto o que se afirma em
A. I, apenas
B. III, apenas
C. I e II, apenas
D. II e III, apenas
E. I, II e III
Gabarito: E
Tipo de questão: Difícil
Conteúdo avaliado: Inteligência Artificial e Computacional
Autor(a): Sibelius Lellis Vieira
Comentário: As três afirmações são verdadeiras: árvores de decisão são usadas para
a tarefa de classificação em mineração de dados, e identificação de padrões, bem
como redes neurais artificiais, que podem ser utilizadas para sistemas de análise de
risco, classificando o risco em alto ou baixo. Já sistemas especialistas são usados
para simular o comportamento de um especialista, que pode fazer diagnósticos, tais
como diagnósticos médicos. Está correta a letra E.
Referências:
RUSSEL, Stuart.; NORVIG, Peter. Inteligência artificial. 2. ed. Rio de Janeiro:
Elsevier, 2004.
LUGER, George F. Inteligência artificial. 4. ed. Porto Alegre: Bookman, 2004.
QUESTÃO Nº 19
O algoritmo de traçado de raios (ray-tracing) é considerado um marco no desenvolvimento de
técnicas de computação gráfica para a geração de imagens realistas.
Imagem 1
Disponível em: <http://wikipedia.org>
Imagem 2
Disponível em: <http://www.colegioweb.com.br>
Imagem 3
Disponível em: <http://www.cgw.com>
A partir da análise das imagens apresentadas, conclui-se que a técnica de traçado de raios foi
utilizada para a geração
A. Apenas da imagem 1.
B. Apenas da imagem 2.
C. Apenas das imagens 1 e 3.
D. Apenas das imagens 2 e 3.
E. Das imagens 1, 2 e 3.
Gabarito: A
Tipo de questão: Muito difícil
Conteúdo avaliado: Computação Gráfica e Processamento de Imagem
Autor(a): Fábio Gomes Barbosa
Comentário: O Ray-Tracing é um algoritmo recursivo que, para cada pixel da projeção
(imagem), projeta um raio (vetor) traçado a partir do observador em direção aos
objetos constituintes da cena, os interceptando, conforme a distância e usando esta
informação para determinar quais os objetos mais próximos e os mais distantes.
Desta forma, é possível calcular qual a cor será atribuída ao pixel. Porém é preciso
lembrar que principal característica é: este raio torna-se a fonte de luz, revelando
assim apenas a luz visível para ser processada. Para tal, observa-se a incidência das
fontes de luz (ambiente) no ponto interceptado: são consideradas as componentes de
luz refletida, refratada e também de sombra e o mais importante: qual a contribuição
(peso) de cada uma no referido ponto de intersecção. Observa-se que as 3 imagens
apresentadas se originam de uma projeção ancorada a partir do ponto de vista do
observador e que esta é uma das características do Ray-Tracing. Entretanto, a
Imagem 1 apresenta em sua composição diversos objetos transparentes, feitos de
vidro colorido. Algumas das características do vidro são transparência, refração e a
reflexão de luz. Neste contexto, outra característica do Ray-Tracing facilmente
observada na Imagem 1 é que a técnica considera o redirecionamento dos raios (por
meio de uma árvore), assim é possível produzir os reflexos na superfície dos vidros
de forma realista. Na imagem 2, um raio, o ponto de vista do observador exerce
pouca influência na constituição da imagem, uma vez que um raio é sua própria fonte
de luz. A imagem 3 apenas o sol age como fonte de luz, demonstrando pouca (ou
quase nenhuma) característica de transparência, reflexão e refração nos objetos
constituintes.
Referências:
AZEVEDO, Eduardo e CONCI, Aura. Computação Gráfica – Teoria e Prática.
Editora Campus, 2003.
SHIRLEY, Peter H. Fundamentals of computer graphics. Massachusetts:
AK Peters, 2005.
QUESTÃO Nº 20
Um processo tem um ou mais fluxos de execução, normalmente denominado apenas por
threads.
A partir das figuras 1 e 2 apresentadas, avalie as afirmações a seguir.
I. Tanto na figura 1 quanto na figura 2, existem três threads que utilizam o mesmo
espaço de endereçamento.
II. Tanto na figura 1 quanto na figura 2, existem três threads que utilizam três espaços
de endereçamento distintos.
III. Na figura 2, existe um processo com um único espaço de endereçamento e três
threads de controle.
IV. Na figura 1, existem três processos tradicionais, cada qual tem seu espaço de
endereçamento e uma única thread de controle.
V. As threads permitem que várias execuções ocorram no mesmo ambiente de processo
de forma independente uma das outras.
É correto apenas o que se afirma em
A. I, II e III
B. I, II e IV
C. I, III e V
D. II, IV e V
E. III, IV e V
Gabarito: E
Tipo de questão: Fácil
Conteúdo avaliado: Sistemas Operacionais e Arquitetura de Computadores
Autor(a): Sibelius Lellis Vieira
Comentário:De acordo com o enunciado, na Figura 1 existem 3 threads, uma para
cada processo e na figura 2 existem 3 threads em um único processo. Como cada
processo tem seu próprio espaço de endereçamento, a afirmação I e a afirmação II
estão incorretas, o que indica que a alternativa correta é a letra E. Nesta alternativa,
III, IV e V estão corretas. A afirmação III diz que na Figura 2 existe um único espaço
de endereçamento e 3 threads de controle. Como cada processo tem seu próprio
espaço de endereçamento, está correta. A afirmação IV diz que na figura 2 existem 3
processos, cada um com seu espaço de endereçamento e uma thread, o que está
correto. A afirmação V diz que as threads permitem que várias execuções ocorram no
mesmo ambiente de processo de forma independente umas das outras, o que está
correto.
Referências:
SILBERSCHATZ, A.; GAVIN B. P.; GAGNE G. Fundamentos de sistemas
operacionais. 8. ed. Rio de Janeiro: Elsevier/Campus, 2013.
TANENBAUM, Andrew S. Sistemas operacionais modernos. 3. ed. São Paulo:
Prentice-Hall,2010.
QUESTÃO Nº 21
O fragmento de código a seguir, escrito em Java, descreve duas implementações para um
lock. Ambas possuem um método denominado acquire e um método denominado release.
class LockA {
private int turn = 0
public void acquire (int tid) {
while (turn == (1-tid));
}
public void release(int tid) {
turn = (1 – tid);
}
}
class LockB {
public void acquire ( ) {
disableInterrupts ( ) ;
}
public void release ( ) {
enableInterrupts( );
}
}
Considera-se que:
• As duas implementações de lock são utilizadas por aplicações com, no máximo, duas
threads;
• Uma aplicação que utilizar qualquer uma destas implementações invocará o método
acquire antes de entrar em sua seção crítica e o método release após deixar a
seção crítica;
• Tanto o método acquire quanto o método release são operações atômicas nas
duas implementações de lock;
• Para a implemetanção que requer um tid (thread id), assume-se que ele sempre será
0 ou 1;
• Os métodos disableInterrupts e enableInterrupts são utilizados para desabilitar
e habilitar respectivamente as interrupções do processador onde o código for
executado. O código desses dois métodos foi desenvolvido para ser utilizado em uma
máquina com um ou dois processadores.
A partir das informações apresentadas, avalie as afirmações a seguir.
I. A implementação de LockA garante progresso.
II. A implementação de LockB garante progresso.
III. A implementação de LockA garante exclusão mútua.
IV. A implementação de LockB garante exclusão mútua
É correto apenas o que se afirma em
A. I e II
B. II e III
C. III e IV
D. I, II e IV
E. I, III e IV
Gabarito: B
Tipo de questão: Difícil
Conteúdo avaliado: Sistemas Operacionais e Arquitetura de Computadores
Autor(a): Sibelius Lelllis Vieira
Comentário: No fragmento do código apresentado existem duas formas de proteger a
seção crítica de acesso concorrente em um sistema com um ou dois processadores.
Na primeira, da classe LockA, uma variável turn é utilizada para controlar o acesso, e
só acessa a seção aquele processo ou thread para o qual a variável turn indica. No
segundo fragmento, da classe LockB, o processo que desabilitar a interrupção acessa
a seção crítica e posteriormente libera o acesso, liberando a interrupção. No
enunciado, duas threads no máximo, acessam a seção crítica. O acesso é efetivado
invocando o método acquire, e após o retorno do método, a seção crítica é utilizada e
o método release é invocado, na sequência. A implementação de LockA garante que
apenas uma thread acessa a seção crítica, pois apenas uma delas será apontada
(valor de turn é único, 0 ou 1) por turn em um dado momento, mas não garante
progresso, pois se uma thread que pode acessar a seção crítica não quiser, a outra
não vai poder. Portanto, alternativas corretas podem ser B ou C. A implementação de
LockB garante progresso, mas não a exclusão mútua, no caso de existirem dois
processadores. Portanto, a alternativa correta é a B.
Referências:
SILBERSCHATZ, A.; GAVIN B. P.; GAGNE G. Fundamentos de sistemas operacionais. 8.
ed. Rio de Janeiro: Elsevier/Campus, 2013.
TANENBAUM, Andrew S. Sistemas operacionais modernos. 3. ed. São Paulo:
Prentice-Hall, 2010.
QUESTÃO Nº 22
Considere o processo de fabricação de um produto siderúrgico que necessita passar por n
tratamentos térmicos e químicos para ficar pronto. Cada uma das n etapas de tratamento é
realizada uma única vez na mesma caldeira. Além do custo próprio de cada etapa do
tratamento, existe o custo de se passar de uma etapa para a outra, uma vez que, dependendo
da sequência escolhida, pode ser necessário alterar a temperatura da caldeira e limpá-la para
evitar a reação entre os produtos químicos utilizados. Assuma que o processo de fabricação
inicia e termina com a caldeira limpa. Deseja-se projetar um algoritmo para indicar a
sequência de tratamentos que possibilite fabricar o produto com o menor custo total. Nesta
situação, conclui-se que
A. A solução do problema é obtida em tempo de ordem O(nlogn), utilizando um
algoritmo ótimo de ordenação.
B. Uma heurística para a solução do problema de coloração de grafos solucionará o
problema em tempo polinomial.
C. O problema se reduz a encontrar a árvore geradora mínima para o conjunto de etapas
do processo, requerendo tempo de ordem polinomial para ser solucionado.
D. A utilização do algoritmo de Dijkstra para se determinar o caminho de custo mínimo
entre o estado inicial e o final soluciona o problema em tempo polinomial.
E. Qualquer algoritmo conhecido para a solução do problema descrito possui ordem de
complexidade de tempo não-polinomial, uma vez que o problema do caixeiro viajante
se reduz a ele.
Gabarito: E
Tipo de questão: Difícil
Conteúdo avaliado: Teoria dos Grafos
Autor(a): Cármen Cecília Centeno
Comentário: Para modelar este problema utilizando grafos se usa um grafo completo
com n+1 vértices representando cada uma das etapas e a etapa inicial caldeira limpa.
As arestas contêm pesos que representam o custo de se passar de uma etapa para a
outra. Deseja se sair do vértice que representa a caldeira limpa passar por todos os
vértices uma única vez e retornar ao vértice caldeira limpa de forma que o custo seja
mínimo. O problema não pode ser resolvido através de uma arvore geradora mínima,
pois temos que encontrar um ciclo (exclui C). Não podemos aplicar Dijkstra, pois
temos que garantir que todos os vértices sejam visitados (exclui D). O problema de
coloração determina conjuntos de tarefas e não uma ordem de tarefas (exclui B). Não
é suficiente fazer uma ordenação dos valores pois isso não garante que os vértices
serão todos visitados uma única vez de forma mínima. Se colocarmos todas as
etapas com o mesmo custo como garantir que será encontrado um ciclo que visite
todas os vértices. O problema em questão corresponde ao problema do Caixeiro
Viajante ou Ciclo Hamiltoniano, que é NP-Completo.
Referências:
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro:
Campus, 2012.
SZWARCFITER, Jayme Luiz, MARKEZAON, Lilian. Estrutura de Dados e seus
Algoritmos. RJ, Editora LTC. 1994.
QUESTÃO Nº 23
Qual o valor de retorno da função a seguir, caso n=27?
int recursao (int n) {
if (n <=10) {
return n * 2;
}
else {
return recursao (recursao (n/3));
}
}
A. 8.
B. 9.
C. 12.
D. 16.
E. 18.
Gabarito: D
Tipo de questão: Difícil
Conteúdo avaliado: Fundamentos e Técnicas de Programação
Autor(a): Sibelius Lellis Vieira
Comentário: No caso de n=27, a função recursao(27) retorna
recursao(recursal(27/3))=recursao(recursao(9)); recursao(9) retorna 18. Portanto,
recursao(18) é avaliada; recursao(18) retorna
recursao(recursao(18/3)=recursao(recursao(6)); recursao(6) retorna 12, logo, deve-se
avaliar recursao(12) e esta, por sua vez, retorna
recursao(recursao(12/3))=recursao(recursao(4); recursao(4) retorna 8 e recursao(8),
por sua vez, retorna 16. Portanto, a alternativa correta é D.
Referências:
FARREL, Joyce. Lógica e design de programação: introdução. São Paulo:
Cengage Learning, 2010.
FARRER, Harry. et al. Programação estruturada de computadores: algoritmos
estruturados. 3. ed. Rio de Janeiro: LTC, 1999.
LOPES, Anita; GUTO, G. Introdução à programação. Rio de Janeiro: Campus,
2002.
QUESTÃO Nº 24
Considere as seguintes tabelas de um banco de dados:
1. Fornecedor (cod_fornec, nome_fornec, telefone, cidade, UF)
2. Estado (UF, nome_estado)
A expressão SQL que obtém os nomes dos estados para os quais não há fornecedores
cadastrados é.
A.SELECT E.UF
FROM Estado AS E
WHERE E.nome_estado NOT IN (
SELECT F.UF
FROM Fornecedor AS F);
B. SELECT E.nome_estado
FROM Estado AS E, FROM
Forncedor AS F
WHERE E.UF = F.UF;
C. SELECT E. nome_estado
FROM Estado AS E
WHERE E.UF NOT IN (
SELECT F.UF
FROM Fornecedor AS F);
D. SELECT E.nome_estado
FROM Estado AS E, FROM
Forncedor AS F
WHERE E.nome_estado = F.UF;
E. SELECT E. nome_estado
FROM Estado AS E
WHERE E.UF IN (
SELECT F.UF
FROM Fornecedor AS F);
Gabarito: C
Tipo de questão: Fácil
Conteúdo avaliado: Banco de Dados
Autor(a): André Luiz Alves e Ronaldo Lopes de Oliveira
Comentário: O enunciado da questão afirma que existem duas tabelas: uma tabela
FORNECEDOR em que cada tupla (linha da tabela) representa um fornecedor
cadastrado e uma tabela ESTADO em que cada tupla (linha da tabela) representa um
Estado da Federação (também conhecido como Unidade da Federação ou UF). A
tabela FORNECEDOR contém para cada fornecedor a sigla da UF em que ele está
situado. A tabela ESTADO contém para cada estado a sua sigla e o seu nome.
Observando a definição das tabelas pode-se concluir que os Estados que não tem
fornecedores são aqueles cuja sigla não aparecem na tabela FORNECEDOR. Uma
expressão de linguagem de consulta SQL que pode ser usada para obter o nome dos
estados que não tem fornecedores é baseada em uma construção usando consultas
aninhadas com a opção NOT IN para selecionar as tuplas da tabela ESTADO cujo
valor do atributo UF não estão no conjunto de valores de UF contidos na tabela
FORNECEDOR. A opção que segue esse raciocínio são apenas as das alternativas A
e C. Entretanto, a alternativa A tem dois erros: seleciona a sigla, mas o que se quer é
o nome e compara valor de nome com sigla. Algumas observações adicionais: a letra
B e D apresentam sintaxe SQL errada na cláusula FROM e a letra E lista o nome dos
estados que tem fornecedores cadastrados porque usa a cláusula IN ao invés de
NOT IN.
Referências:
KORTH, Henry; SILBERSCHATZ, Abraham. Sistema de banco de dados. 6. ed. Rio
de Janeiro: Campus, 2012.
ELMASRI, Ramez. Sistemas de banco de dados. 6. ed. São Paulo: Pearson
Addison Wesley, 2012.
QUESTÃO Nº 25
Uma gramática livre de contexto (GLC) é um modelo computacional geralmente utilizado para
definir linguagens de programação e, quando está de acordo com a Forma de Backus-Naur
(BNF), permite que alguns operadores sejam utilizados no lado direito de suas produções,
como o operador | (pipe) que indica seleção, o operador [ ] que indica que o operando em
questão é opcional, e o operador * que indica repetição de 0 ou mais vezes.
Projetar um compilador para uma determinada linguagem envolve, entre outras coisas,
especificar quais são os símbolos válidos nesta linguagem, bem como quais são as regras
sintáticas que a definem.
A linguagem de programação Java é uma linguagem com suporte à orientação a objetos que
não permite herança múltipla e que permite que uma classe implemente múltiplas interfaces.
A seguir, exibem-se trechos de código sintaticamente válidos na linguagem Java.
Trecho 1:
class A extends B { }
Trecho 2:
class F implements C { }
Trecho 3:
class J extends A implements C, D { }
No trecho 1, cria-se uma classe chamada A que herda de uma classe chamada B. No trecho 2,
cria-se uma classe F que implementa uma interface chamada C. No trecho 3, cria-se uma
classe chamada J que herda de uma classe chamada A e implementa duas interfaces C e D.
Considere que:
• <classdecl> é um não terminal cujo intuito é dar origem a declarações de classes;
• <classbody> é um não terminal cujo intuito é dar origem ao corpo de classes;
• Os terminais aparecem entre aspas duplas;
• “ id” é um símbolo que representa identificador válido, como nomes de classes ou
variáveis.
A gramática que especifica uma linguagem que não permita herança múltipla e que
implemente zero ou mais interfaces é
A. <classdecl> “class” “id” [“ extends”] “id” <classbody>
B. <classdecl> “class” “id” (“ extends” “id”)* <classbody>
C. <classdecl> “class” “id” [“ extends”] “id” [“implements” (, | “id”)*]<classbody>
D. <classdecl> “class” “id” [“ extends” “id”] [“implements” “id” (“,” “id”)*]<classbody>
E. <classdecl> “class” “id” [“ extends” “id”] “implements” “id” (“,” “id”)*<classbody>
Gabarito: D
Tipo de questão: Médio
Conteúdo avaliado: Linguagens Formais, Autômatos e Compiladores
Autor(a): Cármen Cecília Centeno
Comentário: Como indicado na questão o operador [ ] indica que o operando é
opcional. Observando os exemplos vemos que “ class” “ id” acontece em todos, estes
podem ser seguidos pelos terminais “ extends” (trecho 1 e 3) ou “ implements”
(trecho 2) o que indica que podemos escolher entre “ extends” ou “ implements” , o
que exclui letras A e B.
A seguir note a diferença de [“ extends” ] “ id” e [“ extends” “ id”], no primeiro ocorre
um id sem o terminal “ extends”, no segundo os dois estão ligados, como pode ser
observado nos exemplos, excluímos assim letra C. A diferença entre as letras D e E
é que na segunda o terminal “ implements” é obrigatório e em D é opcional pois está
entre [ ]. Como dito anteriormente tanto “ implements” quanto “ extends” são
elementos opcionais, logo letra D é a opção correta.
Referências:
HOPCROFT, John; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introduction to
automata theory, languages, and computation. 3. ed. New Jersey: Prentice Hall,
2006.
MENEZES, Paulo Blauth. Linguagens Formais e Autômatos. RS. Editora Sagra
Luzzatto. 2002
QUESTÃO Nº 26
Um conjunto indutivo S é definido de acordo com os seguintes passos:
[Base] Declaração dos elementos iniciais, atômicos.
[Indução] Definição de regras que constroem expressões a partir de elementos já existentes
em S.
[Fecho] Uma declaração de que nada mais está em S a não ser os elementos construídos
pelos passos Base e Indução.
Os operadores que constroem as expressões nos passos Base e Indução são chamados de
construtores do conjunto S. Como um exemplo, a definição abaixo especifica um conjunto
indutivo Prop, das proposições booleanas formadas pelos construtores V (valor verdadeiro),
F(valor falso), ! (para negação de expressões) e and (para a conjunção de expressões).
1. [Base] V,F estão em Prop.
2. [Indução] Se B está em Prop, então (! B) está em Prop.
3. [Indução] Se B1 e B2 estão em Prop, então (and B1 B2) está em Prop.
4. [Fecho] Nada mais está em Prop, a não ser o especificado em Base e Indução.
Expressões (termos) em Prop incluem V, F, !F, !V, (and V F), (and (! V) (! F)) e assim por
diante. De forma análoga, linguagens funcionais permitem a declaração de tipos indutivos
com seus respectivos construtores.
Neste contexto, avalie as seguintes afirmações.
I. Conjuntos indutivos são conjuntos enumeráveis.
II. Conjuntos infinitos não podem ser especificados por meio de definições indutivas.
III. Para estender a linguagem Prop de tal forma a considerar expressões para disjunção e
implicação de proposição, é necessário acrescentar mais dois construtores à definição
de Prop anterior.
É correto o que se afirma em
A. I, apenas
B. II, apenas
C. I e III, apenas
D. II e III, apenas
E. I, II e III
Gabarito: C
Tipo de questão: Difícil
Conteúdo avaliado: Lógica e Matemática Discreta
Autor(a): Sibelius Lellis Vieira
Comentário: Trata-se de uma questão de matemática discreta, que apresenta uma
série de definições em relação à formação de um conjunto indutivo S. A questão
apresenta as seguintes afirmações, que podem ser deduzidas do contexto da
questão: I. Conjuntos indutivos são enumeráveis.Formalmente, um conjunto é
enumerável ou infinitamente contável se existe uma bijeção entre este conjunto e um
subconjunto infinito de número naturais ou N. Intuitivamente, pode-se compreender
um conjunto enumerável como sendo aquele para o qual seus elementos podem ser
discriminados, um a um, em uma ordem. No caso, o conjunto indutivo é enumerável,
uma vez que os elementos deste conjunto podem ser adicionados a ele em uma
sequência de indução, um após o outro. A afirmação II indica que conjuntos infinitos
não podem ser especificados por meio de definições indutivas. Não há esta limitação,
visto que conjuntos de números tais como os naturais podem ser definidos de forma
indutiva e são infinitos. De fato, conjuntos enumeráveis são infinitamente contáveis,
visto que se forem finitos, serão apenas conjuntos contáveis. A afirmação III diz que
se considerarmos expressões para disjunção e implicação de proposição, teríamos
que acrescentar mais dois construtores à definição de Prop. Uma vez que prop já tem
definido elementos que são a conjunção e a negação, nas definições de indução 2 e
3, deve-se acrescentar expressões como as propostas para disjunção e implicação.
Portanto, I e III estão corretas, tendo como gabarito a letra C.
Referências:
ROSEN, Kenneth H. Matemática discreta e suas aplicações. 6. ed. São Paulo:
McGraw-Hill, 2009.
MENEZES, P. B. Matemática Discreta para Computação e Informática. 2ª Edião.
Editora Sagra Luzzatto, 2005.
QUESTÃO Nº 27
Considere o seguinte argumento:
1 – Se existe fogo, então existe oxigênio.
2 – Não há oxigênio.
3 – Então não há fogo.
A regra de inferência que justifica a validade do argumento acima é
A. P →Q , ¬P
¬Q
B. P →Q , ¬Q
¬P
C. P →Q , Q
P
D. P →Q , ¬Q
¬¬P
E. P →Q , P
Q
Gabarito: B
Tipo de questão: Fácil
Conteúdo avaliado: Lógica e Matemática Discreta
Autor(a): Cármen Cecília Centeno e Sibelius Lellis Vieira
Comentário: Pelo enunciado, se P corresponde à existe fogo, e Q corresponde à
existe oxigênio, então a afirmação 1 equivale à P → Q , a afirmação 2 equivale à ┐Q
e a afirmação 3 equivale à ┐P. Observe que como há negação, as alternativas C e E
são incorretas, e a afirmativa D nega duas vezes, o que também indica inexatidão. A
alternativa correta é B, modus tollens, que a partir de P → Q e ┐Q implicam que ┐P.
Além disso sabemos que somente nas alternativas A e E temos regras de inferências
válidas, sendo que A representa a regra Modus Tollens e E representa a regra Modus
Ponens.
Referências:
ALENCAR FILHO, Edgar. Iniciação à Lógica Matemática. Nobel.2013 SP.
ROSEN, Kenneth H. Matemática discreta e suas aplicações. 6. ed. São Paulo:
McGraw-Hill, 2009.
SILVA, Flávio Correa da. Lógica para computação. São Paulo: Thomson Learning,
2006.
SOUZA, João Nunes da Silva. Lógica para ciência da computação: uma introdução
concisa. 2. ed. Rio de Janeiro: Elsevier, 2008.
QUESTÃO Nº 28
Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo
para um problema pertencente à classe P. Considerando que esta afirmação tem implicações
importantes no que diz respeito à complexidade computacional, avalie as seguintes asserções
e a relação proposta entre elas.
I. A descoberta do cientista implica que P = NP
PORQUE
II. A descoberta do cientista implica na existência de algoritmos polinomiais para
todos os problemas NP-Completos.
A respeito dessas asserções, assinale a opção correta.
A. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
B. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta
da I.
C. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
D. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
E. As asserções I e II são proposições falsas.
Gabarito: A
Tipo de questão: Difícil
Conteúdo avaliado: Teoria da Computabilidade e Complexidade
Autor(a): Aníbal Jukemura e Sibelius Lellis Vieira
Comentário: Uma redução polinomial de um problema NP-completo para um
problema pertencente à classe P implica que P=NP, pois se qualquer problema NP-
completo pode ser resolvido em tempo polinomial, então P=NP, um problema
aberto e fundamental na teoria da computação. Logo, a asserção I está correta. Por
outro lado, quando um problema pertence à classe NP-Completo, o mesmo pode ser
reduzido, em tempo polinomial, a um outro problema da classe NP-Completo. Por
isso, ao solucionar um problema em tempo polinomial, todos podem ser solucionados
da mesma forma. Logo, a alternativa A é a correta.
Referências:
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro:
Campus, 2012.
SIPSER, Michael. Introdução a teoria da computação. 2. ed. São Paulo: Thomson
Learning, 2007.
QUESTÃO Nº 29
Diferentes implementações da linguagem de programação PROLOG permitem predicados
com parâmetros, aceitam as operações de conjunção e disjunção lógica, utilizando os
símbolos vírgula (conjunção) e ponto e vírgula (disjunção), e a negação lógica com o predicado
not.
Considere que um programador propôs as cláusulas mostradas a seguir, definidas em uma
linguagem de programação como o PROLOG, como parte da verificação de critérios para
seleção de candidatos a uma chapa de presidente e vice-presidente de uma empresa. Estas
cláusulas apresentam as premissas para chegar às conclusões selecionadas, desconsiderados
e descartados, a partir da possibilidade da existência de fatos ou regras com o identificador
superior.
superior (jorge).
superior (ana).
selecionados (P,Q) :- superior(P), superior(Q).
desconsiderados (P,Q) :- not(superior(P)); not(superior(Q)).
descartado (P) :- not(superior(P)).
Considerando apenas as colocações e cláusulas acima e a hipótese de mundo fechado (closed
world assumption), avalie as afirmações a seguir.
I. Para todos valores dos parâmetros P e Q, o predicado selecionados retornará um
valor lógico falso.
II. Para todos os valores de P e Q, os predicados selecionados e desconsiderados
retornarão valores lógicos diferentes.
III. A conjunção dos predicados selecionados e desconsiderados, para quaisquer
valores de P e Q, retornará um valor lógico verdadeiro.
IV. Para qualquer valor de parâmetro P, o predicado descartado retornará um valor
verdadeiro.
V. A disjunção dos predicados selecionados e desconsiderados, para quaisquer
valores de P e Q, retornará um valor lógico verdadeiro.
É correto apenas o que se afirma em
A. I e II
B. I e III
C. II e V
D. III e IV
E. IV e V
Gabarito: C
Tipo de questão: Médio
Conteúdo avaliado: Paradigmas e Linguagens de Programação; Lógica e Matemática
Discreta
Autor(a): Cármen Cecília Centeno e Sibelius Lellis Vieira
Comentário: Para solucionar a questão não é necessário o conhecimento de
PROLOG, basta analisar o que é considerado em cada uma das situações:
candidatos selecionados corresponde à expressão lógica P e Q; candidatos
desconsiderados corresponde a ~P ou ~Q (~denota não) e candidatos descartados
corresponde a ~P.
Para facilitar a análise das afirmações vamos aplicar a lei de equivalência de De
Morgan (~(P e Q) ≡ ~P ou ~Q.
Resumindo:
Selecionados: P e Q
Desconsiderados: ~(P e Q)
Descartado: ~P
Análise das alternativas:
I. Falso. V(P) = V e V(Q) = V retorna verdadeiro
II. Verdadeiro, após a aplicação da lei de De Morgan fica claro que um é o
oposto do outro.
III. Falso. (P e Q) e ~(P e Q), a conjunção de uma proposição e sua negação
é sempre falso.
IV. Falso. V(P)= V então V(~P) = F
V. Verdadeiro. (P e Q) ou ~(P e Q), a disjunção de uma proposição e sua
negação é sempre verdadeiro.
Portanto, II e V são verdadeiros, sendo correto o que se afirma na letra C.
Referências:
ROSEN, Kenneth H. Matemática discreta e suas aplicações. 6. ed. São Paulo:
McGraw-Hill, 2009.
RUSSEL, Stuart.; NORVIG, Peter. Inteligência artificial. 2. ed. Rio de Janeiro:
Elsevier, 2004.
SOUZA, João Nunes da Silva. Lógica para ciência da computação: uma introdução
concisa. 2. ed. Rio de Janeiro: Elsevier, 2008.
QUESTÃO Nº 30
Uma fazenda possui um único poço artesiano que deve abastecer n bebedouros para o gado.
Deseja-se determinar um projeto de ligação entre esses n+1 pontos através de encanamento
com a menor extensão total. Um algoritmo proposto para a solução do problema executa os
seguintes passos:
1. Crie n+1 conjuntos unitários, cada um contendo um dos pontos a serem ligados entre
si e insira esses conjuntos em um conjunto C.
2. Crie um conjunto D contendo um registro para cada combinação possível de dois
pontos distintos a serem ligados. Cada registro deve conter os campos ci, cj e d, em
que ci e cj são dois pontos a serem ligados e d é a distância entre eles.
3. Enquanto D não estiver vazio faça:
3.1. Remova o registro de D com o menor valor de distância d.
3.2. Se os valores de ci e cj do registro removido pertencerem a conjuntos distintos de
C, então:
3.2.1. Substitua estes dois conjuntos pela união entre eles.
3.2.2. Guarde o registro removido em um conjunto-solução.
Com base na descrição do problema e do algoritmo proposto, conclui-se que:
A. O problema exemplifica a obtenção de uma árvore geradora mínima, portanto está
no conjunto P.
B. O algoritmo é uma heurística para o Problema do Caixeiro Viajante, logo apresenta
complexidade polinomial.
C. O problema descrito é de otimização, logo pertence ao conjunto NP-difícil, mas não
ao conjunto NP-completo.
D. Uma alternativa para a solução do problema é usar o algoritmo de Dijkstra para
obtenção do caminho mínimo entra dois pontos.
E. O passo de maior custo do algoritmo é a criação do conjunto D com as combinações
de pontos, apresentando complexidade computacional O(n!).
Gabarito: A
Tipo de questão: Difícil
Conteúdo avaliado: Teoria dos Grafos; Teoria da Computabilidade e Complexidade
Autor(a): Cármen Cecília Centeno e Sibelius Lellis Vieira
Comentário: É solicitado que um conjunto de n+1 pontos sejam conectados, em
qualquer ordem. Qualquer ponto deve estar conectado a algum outro ponto. Portanto,
não é um problema de caminho mínimo, pois todos os pontos devem ser incluídos, ou
seja, o algoritmo de Dijkstra não é adequado, pois este acha o menor caminho que
não necessariamente passa por todos os vértices. Também não é um problema de
caixeiro viajante, pois um ponto pode ser conectado a outro já cheio de conexões e
não é necessário voltar ao ponto de partida. Isto exclui as letras B e D.
Analisando o algoritmo vemos que em 1 é criado um conjunto de vértices, e que cada
vértice ocorre uma única vez no conjunto. Em 2 é criado um conjunto de arestas com
pesos, é criado todas as possíveis arestas originado um grafo completo. Note que o
algoritmo é um algoritmo guloso, sempre retira a aresta de menor peso. Uma vez
encontrada a aresta é removido os vértices do conjunto C, sendo assim a solução
encontrada não terá ciclos, o que gera uma arvore, como é sempre escolhida a aresta
de menor peso é encontrada uma arvore geradora mínima.
O exame ainda mostra que se trata de um algoritmo polinomial, pois tanto o conjunto
C quanto o conjunto D têm cardinalidade n2, pois para a criação do conjunto D basta
combinar cada vértice com todos os outros. Portanto, a alternativa E é excluída. Ao
final, o item 3.2 do algoritmo testa se cada elemento de D tem valores ci e cj que
pertencem à conjuntos disjuntos de C. Para realizar este exame, é necessário
examinar os conjuntos de C dois a dois. Como o conjunto C se inicia com
cardinalidade n e esta cardinalidade não aumenta, este teste também pode ser
realizado em tempo polinomial. Logo, a letra C está incorreta. Trata-se, portanto, de
um algoritmo que possibilita a formação de uma árvore geradora mínima em tempo
polinomial, estando correta a letra A.
Referências:
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro:
Campus, 2012.
SZWARCFITER, Jayme Luiz, MARKEZAON, Lilian. Estrutura de Dados e seus
Algoritmos. RJ, Editora LTC. 1994.
QUESTÃO Nº 31
Na transmissão de dados em sistemas computacionais, o dispositivo de verificação de erros
conhecido como bit de paridade consiste da adição de um bit extra durante a transmissão. O
valor associado a esse bit é uma função da quantidade de bits de dados iguais a 1 a serem
transmitidos.
Nesse contexto, considere a transmissão de 7 bits de dados, com um bit extra de paridade,
em um sistema de comunicação no qual a probabilidade de transmitir um bit de forma
incorreta é igual a 10 -6 e independe de outros erros ocorridos. O bit de paridade também
pode sofrer erros.
A probabilidade da ocorrência de transmissão de 2 bits errados, que seria erroneamente
detectada como uma transmissão sem erros, é
A. 1,0 x 10-12.
B. 2,0 x 10-12.
C. 2,8 x 10-11.
D. 2,0 x 10-6.
E. 2,8 x 10-5.
Gabarito: C
Tipo de questão: Muito difícil
Conteúdo avaliado: Redes de Computadores e Sistemas Distribuídos; Probabilidade e
Estatística
Autor(a): Sibelius Lellis Vieira
Comentário: No caso em comento, oito bits são transmitidos, e a probabilidade de que
um deles qualquer seja transmitido incorretamente é de 10-6. A probabilidade de que
exista um bit errado é 10-6 multiplicado por 8 (número de bits que podem estar
errados). Caso possam existir dois bits errados, então pode ser o bit 1 e 2, o bit 1 e 3,
etc. Desta forma, existem 28 combinações de dois bits errados. Logo, a probabilidade
de se transmitir dois bits errados é 28. 10-6.10-6, ou seja, 2,8.10-11. A alternativa
correta é a letra C.
Referências:
FOROUZAN, Behrouz. Comunicação de dados e redes de Computadores. 4. ed.
Porto Alegre: McGraw Hill, 2008.
TANENBAUM, Andrew; WETHERHALL, David. Redes de computadores. 5. ed. São
Paulo: Campus, 2011.
MONTGOMERY, Douglas C. Probabilidade aplicada à engenharia. 4. ed. Rio de
Janeiro: LTC, 2011.
QUESTÃO Nº 32
Considere as proposições lógicas simples P,Q,R:
P: o programador lê a literatura técnica
Q: o programador conhece o idioma inglês
R: o programador será selecionado
Pretende-se demonstrar a validade ou invalidade do seguinte argumento:
Se o programador lê a literatura técnica, então ele conhece inglês.
Se o programador conhece o idioma inglês, então ele será selecionado.
O programador não será selecionado ou ele lê a literatura técnica.
Logo, o programador lê a literatura técnica se e somente se conhece o idioma inglês.
Considerando as colocações acima, avalie as afirmações a seguir.
I. As premissas do argumento podem ser expressas na forma: P � Q, Q � R e ¬R v P. A
conclusão do argumento pode ser expressa na forma: P ↔ Q.
II. A validade do argumento se demonstra com os passos: ¬Q v P (equivalente de uma
premissa), P �R (transitividade da implicação a partir das premissas) e conclusão Q
↔ R (conjunção de duas proposições condicionais e transformação em bicondicional)
III. A validade do argumento se demonstra com os passos: R � P (equivalente de uma
premissa), Q �P (transitividade da implicação), chegamos à conclusão Q ↔ R
(conjunção de duas proposições condicionais e transformação em bicondicional).
IV. As premissas do argumento podem ser expressas na forma: P�Q, Q�R e ¬R � P e a
conclusãodo argumento acima pode ser expressa na forma: P�Q.
V. A invalidade do argumento acima se demonstra desta forma: a proposição lógica
P↔Q é diferente das premissas P�Q, Q�R e ¬R v P.
É correto apenas o que se afirma em
A. I e III
B. II e IV
C. I, III e V
D. I, II, IV e V
E. II, III, IV e V
Gabarito: A
Tipo de questão: Médio
Conteúdo avaliado: Lógica e Matemática Discreta
Autor(a): Cármen Cecília Centeno
Comentário: Considerando as premissas P, Q, R a tradução do argumento é imediata:
P�Q, Q ↔R, ¬R v P e a conclusão P ↔ Q, com isso concluímos que I é verdadeira e
IV é falsa, o que exclui as letras B, D e E. Resta apenas A.( I e III) e C. (I, III e V).
sendo assim podemos concluir que III é verdadeiro. Se III é verdadeiro então o
argumento é válido o que torna V falsa pois esta afirma que o argumento é inválido.
Referências:
ALENCAR FILHO, Edgar. Iniciação à Lógica Matemática. Nobel.2013 SP.
ROSEN, Kenneth H. Matemática discreta e suas aplicações. 6. ed. São Paulo:
McGraw-Hill, 2009.
SOUZA, João Nunes da Silva. Lógica para ciência da computação: uma introdução
concisa. 2. ed. Rio de Janeiro: Elsevier, 2008.
QUESTÃO Nº 33
A seguinte sequência de instruções lógicas e aritméticas será executada por um processador
em pipeline de 5 estágios: busca da instrução, leitura de registradores, execução, acesso à
memória e escrita de dados.
and R5, R4, R3
or R6, R4, R2
add R1, R2, R2
mul R3, R2, R1
sub R1, R1, R4
O pipeline foi implementado sem hardware adicional para a resolução de conflitos, mas os
valores dos registradores podem ser escritos na primeira metade do ciclo e lidos na segunda
metade. Sabendo-se que o primeiro operando das instruções é o registrador destino, avalie as
afirmações a seguir.
I. A troca de posição entre as instruções or e add soluciona o conflito de dados.
II. A troca de posição entre as instruções add e and soluciona o conflito de dados.
III. A inserção de uma operação nop (sem operação) entre add e mul soluciona o conflito
de dados.
É correto o que se afirma em
A. I, apenas
B. II, apenas
C. I e II, apenas
D. II e III apenas
E. I, II e III
Gabarito: B
Tipo de questão: Difícil
Conteúdo avaliado: Sistemas Operacionais e Arquitetura de Computadores
Autor(a): Sibelius Lellis Vieira
Comentário: Segundo o enunciado, 5 instruções são executadas em sequência, por
um processador com pipeline em 5 estágios, sendo o estágio de leitura o segundo e o
estágio de escrita o quinto. Existe um conflito de dados entre a instrução add
R1,R2,R2 que escreve no registrador R1 e a instrução mul R3,R2,R1 lê o registrador
R1 logo em seguida, uma vez que o enunciado indica que o primeiro operando é o
registrador destino (a ser escrito). Esta leitura deve esperar por um tempo que
permita que a escrita da instrução anterior seja efetivada. Como o pipeline não tem
hardware para a resolução de conflitos, é necessário ao programador modificar o
código para evitá-lo. Supõe-se que cada estágio tem o mesmo tempo de ciclo. Para
prevenir o conflito RAW (leitura após escrita) de R1, a escrita deve anteceder a leitura
em pelo menos, 3 ciclos (diferença do estágio de leitura e escrita em cada instrução).
A diferença de 3 ciclos entre a instrução add e a instrução mul só é conseguida se
add trocar de posição com a instrução and. Neste caso, supondo que a execução
inicia-se no ciclo 0 e cada estágio dura um ciclo, a escrita de R1 é feita no ciclo 4 (0,
1, 2, 3, e 4 são os estágio da instrução add, a primeira a executar). A instrução mul é
a quarta, iniciando em sua execução no ciclo 3, e a leitura de R1 é feita no ciclo 4
também. Como o enunciado afirma que os registradores são escritos na primeira
metade de ciclo, a escrita de R1 no ciclo 4 é efetivada antes da leitura de R1 no ciclo
4. Portanto, a alternativa B é a correta.
Referências:
HENNESSY, John L.; PATTERSON, David. A. Organização e projeto de
computadores: a interface hardware/software. 3. ed. Rio de Janeiro: Campus, 2005.
STALLINGS, William. Arquitetura e organização de computadores. 8. ed. São
Paulo: Pearson, 2010.
QUESTÃO Nº 34
Considere a implementação de um compilador em que as etapas de análise léxica e sintática
possam compartilhar o mesmo processador de forma concorrente. Considere, ainda, uma
solução para o problema, cujo pseudocódigo é mostrado abaixo. O analisador léxico lê os
lexemas e identifica os respectivos tokens do arquivo-fonte por meio da chamada ao
procedimento Leia. O analisador sintático verifica a sequencia dos tokens por meio da
chamada ao procedimento Case. Os dois processos compartilham a constante N e as
variáveis buffer, vez e cont.
constante N = 10;
inteiro buffer[N], vez = 0, cont = 0;
Analisador_Lexico:
01 inteiro token, in = 0;
02 enquanto verdadeiro faça
03 Leia(token);
04 enquanto cont = N-1 aguarde;
05 enquanto vez = 1 aguarde;
06 buffer[in] = token;
07 cont = cont + 1;
08 vez = 1;
09 in = (in + 1) mod N;
10 fim enquanto
Analisador_Sintatico
11 inteiro token, out = 0;
12 enquanto verdadeiro faça
13 enquanto cont = 0 aguarde;
14 enquanto vez = 0 aguarde;
15 token buffer[out];
16 cont = cont-1;
17 vez = 0;
18 out = (out + 1) mod N;
19 Case(token);
20 fim enquanto
A partir da análise da solução, avalie as asserções a seguir e a relação proposta entre elas.
I. A eliminação da variável cont e das linhas 4,7,13 e 16 causa erro de sincronismo
entre os processos.
PORQUE
II. A variável cont é responsável pelo controle do acesso à seção crítica do código.
A respeito dessas asserções, assinale a opção correta.
A. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
B. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta
da I.
C. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
D. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
E. As asserções I e II são proposições falsas.
Gabarito: E
Tipo de questão: Muito difícil
Conteúdo avaliado: Fundamentos e Técnicas de Programação; Sistemas
Operacionais e Arquitetura de Computadores
Autor(a): Sibelius Lellis Vieira
Comentário: No caso em comento, um processo que executa um analisador léxico
utiliza a variável cont para indicar se pode colocar um token no buffer no caso dele
estar cheio e a variável vez para indicar se é a vez do processo executar. Outro
processo, executando concorrentemente, também utiliza a variável cont para não ler
os token do buffer caso este esteja vazio e usa variável vez para verificar se é a sua
vez. Portanto, a variável vez é usada pelo controle de acesso à seção crítica do
código, e a variável cont para indicar quantos elementos existem no buffer. Trata-se
de um caso clássico de problema do produtor versus consumidor, compartilhando um
buffer de memória e variáveis de controle para acesso ao buffer. É correta a
alternativa E, pois a eliminação da variável cont, para o caso do problema, não afeta o
processo, dado que a variável vez alterna a execução dos processos.
Referências:
SILBERSCHATZ, A.; GAVIN B. P.; GAGNE G. Fundamentos de sistemas operacionais. 8.
ed. Rio de Janeiro: Elsevier/Campus, 2013.
TANENBAUM, Andrew S. Sistemas operacionais modernos. 3. ed. São Paulo:
Prentice-Hall, 2010.
QUESTÃO Nº 35
Um prédio de 4 andares, sendo o primeiro andar térreo, é servido por 2 elevadores. Por
motivo de economia de energia, o elevador 2 só é acionado se for solicitado em mais de 2
andares. Considere um circuito proposto para habilitar o acionamento do elevador2
conforme é mostrado a seguir. Ele utiliza um multiplexador 4x1, cuja saída é selecionada
através da composição dos sinais A e B, que indicam se os andares 1 e 2 solicitaram o serviço
do elevador. Assim o valor AB=10(2) indica que o primeiro andar solicitou elevador, mas não o
segundo. Os sinais C e D indicam se os andares 3 e 4 solicitaram o serviço, respectivamente.
Com base na análise do circuito proposto para o problema, avalie as seguintes asserções e a
relação proposta entre elas.
I. O circuito não atende às especificações do projeto.
PORQUE
II. A entrada superior do multiplexador com valor constante 0 indica que a saída
será 0 independentemente dos valores dos sinais A,B, C e D.
A respeito dessas asserções, assinale a opção correta.
A. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
B. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta
da I.
C. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
D. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
E. As asserções I e II são proposições falsas.
Gabarito: E
Tipo de questão: Difícil
Conteúdo avaliado: Sistemas Digitais
Autor(a): Wilmar Oliveira de Queiroz
Comentário: A condição para acionar o elevador 2 é que seja solicitado por mais de 2
andares, isto é, 3 ou 4 andares.
As entradas de endereçamento AB do MUX selecionam qual das 4 entradas vai para a
saída S (habilita o elevador 2), portanto:
A B S
0 0 habilita a 1ª entrada, que é 0, então a saída é 0.
0 1 habilita a 2ª entrada que depende da saída da porta AND (entradas C e
D)
1 0 habilita a 3ª entrada que depende da saída da porta AND (entradas C e
D)
1 1 habilita a 4ª entrada que depende da saída da porta OR (entradas C ou
D)
Analisando as entradas C e D nas portas AND e OR:
C D AND OR
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 1
Juntando as 4 entradas em uma Tabela Verdade a saída será 1 quando pelo menos
três entradas estiverem em 1:
A B C D S SAÍDA
0 0 0 0 0 1ª entrada do MUX, S=0
0 0 0 1 0 1ª entrada do MUX, S=0
0 0 1 0 0 1ª entrada do MUX, S=0
0 0 1 1 0 1ª entrada do MUX, S=0
0 1 0 0 0 2ª entrada do MUX, S=0 (S=1 somente se C=D=1)
0 1 0 1 0 2ª entrada do MUX, S=0 (S=1 somente se C=D=1)
0 1 1 0 0 2ª entrada do MUX, S=0 (S=1 somente se C=D=1)
0 1 1 1 1 2ª entrada do MUX, S=1 (três entradas em 1)
1 0 0 0 0 3ª entrada do MUX, S=0 (S=1 somente se C=D=1)
1 0 0 1 0 3ª entrada do MUX, S=0 (S=1 somente se C=D=1)
1 0 1 0 0 3ª entrada do MUX, S=0 (S=1 somente se C=D=1)
1 0 1 1 1 3ª entrada do MUX, S=1 (três entradas em 1)
1 1 0 0 0 4ª entrada do MUX, S=0 (S=1 somente se C=D=1, ou C ou
D=1)
1 1 0 1 1 4ª entrada do MUX, S=1 (três entradas em 1)
1 1 1 0 1 4ª entrada do MUX, S=1 (três entradas em 1)
1 1 1 1 1 4ª entrada do MUX, S=1 (três entradas em 1)
Conclusão:
Asserção I é falsa, pois o circuito atende às especificações.
Asserção II: é falsa, pois a saída do MUX depende dos valores de A, B, C e D e será 1
quando 3 ou 4 delas forem 1.
Então resposta é a opção E.
Referências:
IDOETA, Ivan V.; CAPUANO, Francisco G. Elementos de eletrônica digital. 41.
ed. São Pulo: Érica, 2012.
TOCCI, Ronald J.; WIDMER, Neal S. Sistemas digitais: princípios e aplicações.
11. ed. Rio de Janeiro: Pearson Prentice Hall, 2011.