July 2023 2 66 Report
Observe as afirmações a seguir.

I. As classes de complexidade visam classificar problemas computacionais de acordo com sua dificuldade, e relacionar essas classes entre si.

II. Na classe P encontra-se o conjunto de problemas que são resolvidos em tempo polinomial por uma por uma máquina de Turing determinística.

III. A classe NP possui o conjunto de problemas que são solucionados em tempo polinomial por uma máquina de Turing também determinística.

Assinale a alternativa que contenha TODAS as informações corretas.

a. Somente as afirmações I e III estão corretas.
b. Somente a afirmação I está correta.
c. Somente as afirmações I e II estão corretas.
d. Somente as afirmações II e III estão corretas.
e. Somente as afirmações I, II e III estão corretas.
Please enter comments
Please enter your name.
Please enter the correct email address.
You must agree before submitting.

Lista de comentários

More Questions From This User See All
Utilizando o teorema de Norton, determine a tensão e a corrente na resistência entre os nós A e B: a. V = 20V e i = 0,28mA. b. V = 10V e i = 1,28mA. c. V = 20V e i = 2,28mA. d. V = 44V e i = 5,28mA. e. V = 60V e i = 0,28mA.
Responda
PERGUNTA 1 A operação de união de dois conjuntos é uma operação elementar na teoria dos conjuntos. Assinale a alternativa que contenha TODAS as informações corretas sobre a operação união.a) A operação união entre dois conjuntos A e B corresponde ao conjunto formado por todos os elementos que não estão contidos nos conjuntos A e B. A operação de união é representada pelo símbolo ∩. A operação de união de A e B é representado por A ∩ B. Caso haja elementos repetidos em ambos os conjuntos, são considerados duas vezes no conjunto formado pela união dos conjuntos.b) A operação de união entre dois conjuntos A e B corresponde ao conjunto formado por nenhum elemento que esteja contido em A e B. A operação de união é representada pelo símbolo Ø. A operação de união de A e B é representado por A Ø B. Caso haja elementos repetidos em ambos os conjuntos, são considerados duas vezes no conjunto formado pela união dos conjuntos.c) A operação de união entre dois conjuntos A e B corresponde ao conjunto formado por elementos repetidos de A e B. A operação de união é representada pelo símbolo ≥. A operação de união de A e B é representada por A ≥ B. Caso haja elementos repetidos em ambos os conjuntos, são considerados três vezes no conjunto formado pela união dos conjuntos.d) A operação de união entre dois conjuntos A e B corresponde ao conjunto formado por todos que não existem em A e B. A operação de união é representada pelo símbolo β. A operação de união de A e B é representada por A β B. Caso haja elementos repetidos em ambos os conjuntos, são considerados seis vezes no conjunto formado pela união dos conjuntos.e) A operação de união entre dois conjuntos A e B corresponde ao conjunto formado por todos os elementos contidos em cada um dos conjuntos A e B. A operação de união é representada pelo símbolo U. A operação de união de A e B é representada por A U B. Caso haja elementos repetidos em ambos os conjuntos, são considerados uma única vez no conjunto formado pela união dos conjuntos.
Responda
Observe o seguinte autômato. Nesse autômato a palavra abba. a. é aceita, abb não é aceita e aaaa é aceita. b. não é aceita, abb não é aceita e aaaa não é aceita. c. é aceita, abb é aceita e aaaa é aceita. d. não é aceita, abb é aceita e aaaa não é aceita. e. é aceita, abb é aceita e aaaa não é aceita.
Responda
Observe as afirmações a seguir: I. A operação de concatenação sucessiva * garante haverá duas ou ocorrências. II. Para toda ER há um Autômato correspondente. Assinale a alternativa CORRETA: a. As Afirmações I e II estão incorretas. b. As Afirmações I e II estão corretas. c. Somente a II está correta. d. Nenhuma das alternativas anteriores. e. Somente a afirmação I está correta.
Responda
Observe o seguinte Autômato:Qual expressão regular é possível obter com esse Autômato?a. a*.b. a.c. (aa+bb).d. aaaab.e. a*bb.
Responda
Observe o Autômato a seguir: Qual ER é possível obter com esse Autômato? a. abab*. b. b*. c. bba*. d. ba*. e. a*.
Responda
Dado o alfabeto ∑ = {a,b}, a ER a*ba*ba*, quais palavras são geradas? a. Todas as palavras contendo exatamente dois ab. b. Todas as palavras contendo exatamente dois bbbb. c. Todas as palavras contendo exatamente dois a. d. Todas as palavras contendo exatamente dois baa. e. Todas as palavras contendo exatamente dois b.
Responda
Considerando as seguintes regras: F -> aF -> EAssinale a alternativa que apresenta a CORRETA Backus Naur Form (BNF):
Responda
A classe de complexidade P contém: a. O conjunto de problemas que são resolvidos em tempo não polinomial por uma máquina de Turing não determinística. b. O conjunto de problemas que são resolvidos em tempo não polinomial por uma máquina de Turing determinística. c. O conjunto de problemas que são resolvidos em tempo polinomial por uma máquina de Turing determinística. d. O conjunto de problemas que não contém soluções. e. O conjunto de problemas que são resolvidos em tempo polinomial por uma máquina de Turing não-determinística.
Responda
A classe NP possui o conjunto de problemas que: Assinale a alternativa que contém TODAS as informações corretas. a. São solucionados em tempo polinomial por uma máquina de Turing não-determinística. b. Não possuem soluções. c. São solucionados em tempo polinomial. d. Não são solucionados em tempo polinomial. e. São solucionados em tempo polinomial por uma máquina de Turing determinística.
Responda

Helpful Links

Helpful Social

Copyright © 2025 ELIBRARY.TIPS - All rights reserved.