ASPECTOS TEÓRICOS DA COMPUTAÇÃO Questionario 1

Prévia do material em texto

• Pergunta 1 
0,5 em 0,5 pontos 
 
Qual é a interseção dos conjuntos A = {1, 2, 3, 4} e B = {3, 4, 5, 6}? 
Resposta Selecionada: b. 
{3, 4}. 
Respostas: a. 
{1, 2, 3, 4}. 
 
b. 
{3, 4}. 
 
c. 
{1, 2, 5, 6}. 
 
d. 
{1, 2, 3, 4, 5, 6}. 
 
e. 
{}. 
Comentário da 
resposta: 
Resposta: B 
Comentário: A interseção dos conjuntos A e B contém apenas os 
elementos que estão presentes em ambos A e B, que são 3 e 4. 
 
 
• Pergunta 2 
0,5 em 0,5 pontos 
 
O que representa o estado inicial em um autômato finito determinístico (AFD)? 
Resposta Selecionada: c. 
O estado atual onde o AFD começa a processar a entrada. 
Respostas: a. 
O estado de liberdade. 
 
b. 
O estado de exclusão. 
 c. 
 
O estado atual onde o AFD começa a processar a entrada. 
 
d. 
O estado vazio. 
 
e. 
Não há estado inicial em um AFD. 
Comentário da 
resposta: 
Resposta: C 
Comentário: O estado inicial em um AFD é o estado a partir do 
qual o processamento da entrada começa. É o estado a partir do 
qual o AFD começa a executar a função de transição de acordo com 
os símbolos de entrada. 
 
• Pergunta 3 
0,5 em 0,5 pontos 
 
O que é um autômato finito determinístico (AFD)? 
Resposta 
Selecionada: 
b. 
Um modelo computacional abstrato que representa 
linguagens regulares. 
Respostas: a. 
Um dispositivo que simula a criatividade humana na resolução 
de problemas. 
 
b. 
Um modelo computacional abstrato que representa 
linguagens regulares. 
 
c. 
Um software utilizado para criar interfaces gráficas. 
 
d. 
Uma linguagem de programação popular para 
desenvolvimento web. 
 
e. 
Uma técnica para melhorar algoritmos de ordenação. 
 
Comentário da 
resposta: 
Resposta: B 
Comentário: Um AFD é um modelo matemático abstrato usado 
na teoria da computação para representar linguagens regulares. 
 
• Pergunta 4 
0,5 em 0,5 pontos 
 
Qual é o valor de f(x) = 2x + 3 quando x = 5? 
Resposta Selecionada: b. 
13. 
Respostas: a. 
10. 
 
b. 
13. 
 
c. 
15. 
 
d. 
20. 
 
e. 
23. 
Comentário da 
resposta: 
Resposta: B 
Comentário: Substituindo x por 5 na função, obtemos f(5) = 
2 5 + 3 = 10 + 3 = 13. 
 
 
• Pergunta 5 
0,5 em 0,5 pontos 
 
Qual é o objetivo principal de uma gramática livre de contexto na teoria das 
linguagens formais? 
 
Resposta Selecionada: c. 
Descrever a estrutura sintática de uma linguagem. 
Respostas: a. 
 
Definir regras para construção de linguagens naturais. 
 
b. 
Definir a semântica de um programa de computador. 
 
c. 
Descrever a estrutura sintática de uma linguagem. 
 
d. 
Traduzir um texto de uma língua para outra. 
 
e. 
Criar uma representação gráfica de um algoritmo. 
Comentário 
da resposta: 
Resposta: C 
Comentário: Uma das principais finalidades de uma gramática livre 
de contexto é descrever a estrutura sintática de uma linguagem, 
definindo as regras para a construção de sentenças válidas na 
linguagem. Isso é fundamental na teoria das linguagens formais e 
na análise sintática de linguagens de programação. 
 
• Pergunta 6 
0,5 em 0,5 pontos 
 
Em um autômato de pilha, quais tipos de operações podem ser realizadas na pilha? 
Resposta Selecionada: b. 
Empilhamento (push) e desempilhamento (pop). 
Respostas: a. 
Adição e subtração. 
 
b. 
Empilhamento (push) e desempilhamento (pop). 
 
c. 
Multiplicação e divisão. 
 
d. 
Concatenação e interseção. 
 e. 
 
Comparação e ordenação. 
Comentário 
da resposta: 
Resposta: B 
Comentário: Em um autômato de pilha, as operações principais 
realizadas na pilha são o empilhamento (push), que adiciona 
símbolos à pilha, e o desempilhamento (pop), que remove símbolos 
do topo da pilha. Essas operações são usadas para manipular a pilha 
de acordo com as regras da gramática da linguagem reconhecida 
pelo autômato de pilha. 
 
• Pergunta 7 
0,5 em 0,5 pontos 
 
Qual é a principal diferença entre uma linguagem recursiva e uma linguagem 
recursivamente enumerável? 
 
Resposta 
Selecionada: 
c. 
Linguagens recursivas têm um algoritmo de decisão. 
Respostas: a. 
Linguagens recursivas são Turing-reconhecíveis. 
 
b. 
Linguagens recursivamente enumeráveis são sempre finitas. 
 
c. 
Linguagens recursivas têm um algoritmo de decisão. 
 
d. 
Linguagens recursivamente enumeráveis têm um algoritmo 
de decisão. 
 
e. 
Não há diferença entre as duas. 
Comentário 
da resposta: 
Resposta: C 
Comentário: A principal diferença entre as duas é que as linguagens 
recursivas têm um algoritmo de decisão, o que significa que há um 
procedimento que decide se uma cadeia de entrada pertence à 
linguagem ou não. Por outro lado, nas linguagens recursivamente 
enumeráveis, a máquina de Turing pode entrar em loop. 
 
 
• Pergunta 8 
0,5 em 0,5 pontos 
 
O que é a fita em uma máquina de Turing? 
Resposta Selecionada: e. 
O local onde a entrada e a saída são representadas. 
Respostas: a. 
Uma instrução de programação. 
 
b. 
Um dispositivo magnético de tamanho finito. 
 
c. 
O mecanismo de controle da máquina. 
 
d. 
O local onde os estados da máquina estão armazenados. 
 
e. 
O local onde a entrada e a saída são representadas. 
Comentário 
da resposta: 
Resposta: E 
Comentário: A fita em uma máquina de Turing é o local onde a 
entrada é representada e onde os resultados intermediários e a 
saída também são registrados. Ela desempenha um papel 
fundamental no funcionamento da máquina, armazenando e 
manipulando símbolos à medida que a máquina realiza seus 
cálculos. 
 
 
• Pergunta 9 
0,5 em 0,5 pontos 
 
Qual dos seguintes quantificadores em uma expressão regular significa "zero ou 
mais concatenações”? 
 
Resposta Selecionada: c. 
"*" (asterisco). 
Respostas: a. 
"+" (mais). 
 
b. 
"?" (interrogação). 
 
 
c. 
"*" (asterisco). 
 
d. 
"{n}" (chaves com um número específico). 
 
e. 
"{n, m}" (chaves com um intervalo específico). 
Comentário 
da resposta: 
Resposta: C 
Comentário: O quantificador "*" (asterisco) em uma expressão 
regular significa "zero ou mais concatenações" do elemento 
precedente ao quantificador. Isso indica que o elemento pode estar 
ausente na entrada ou pode ocorrer várias vezes. 
 
• Pergunta 10 
0,5 em 0,5 pontos 
 
Qual é o conceito principal da tese de Church-Turing na teoria da computação? 
Resposta 
Selecionada: 
c. 
A equivalência entre máquinas de Turing e computação 
efetiva. 
Respostas: a. 
A unicidade do computador pessoal. 
 
b. 
A existência de computadores quânticos. 
 
c. 
A equivalência entre máquinas de Turing e computação 
efetiva. 
 
d. 
A necessidade de máquinas de Turing com recursos 
infinitos. 
 
e. 
A dependência da computação em nuvem. 
 
Comentário 
da resposta: 
Resposta: C 
Comentário: A Tese de Church-Turing afirma que qualquer função 
que seja computável de forma efetiva (algorítmica) é computável 
por uma máquina de Turing. Isso estabelece a equivalência entre 
máquinas de Turing e a noção de computação efetiva, 
independentemente do modelo de cálculo escolhido.