Redutibilidade em Problemas

Prévia do material em texto

<p>Você acertou 1 de 10</p><p>questões</p><p>Verifique o seu desempenho e continue</p><p>treinando! Você pode refazer o exercício</p><p>quantas vezes quiser.</p><p>Verificar Desempenho</p><p>1 Marcar para revisão</p><p>Uma redução é um processo de conversão de</p><p>um problema em outro problema resolvido de</p><p>tal forma que a solução do segundo problema</p><p>possa ser usada para resolver o primeiro</p><p>problema. Em particular, a redutibilidade pode</p><p>ser usada para demonstrar que problemas são</p><p>indecidíveis ou decidíveis. Nesse contexto,</p><p>avalie as seguintes afirmativas:</p><p>I��A Redutibilidade não diz nada em resolver</p><p>os problemas A ou B sozinhos, mas somente</p><p>sobre a resolução de A na presença de um</p><p>método para resolver B.</p><p>II��Reduções apresentam um importante papel</p><p>em classificar os problemas em decidíveis ou</p><p>indecidíveis.</p><p>III��Se A é redutível a B e B é um problema</p><p>indecidível, então A é um problema decidível.</p><p>Quais as afirmativas verdadeiras?</p><p>09/10/2024, 11:19 estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 1/16</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>I e II.</p><p>II e III.</p><p>I, II e III.</p><p>I e III.</p><p>III.</p><p>Resposta correta</p><p>Parabéns, você selecionou a</p><p>alternativa correta. Confira o</p><p>gabarito comentado!</p><p>Gabarito Comentado</p><p>A afirmativa I está correta, pois a</p><p>redutibilidade não se preocupa em resolver</p><p>os problemas A ou B isoladamente, mas</p><p>sim em resolver o problema A com a ajuda</p><p>de um método para resolver B. A afirmativa</p><p>II também está correta, pois as reduções</p><p>desempenham um papel crucial na</p><p>classificação dos problemas como</p><p>decidíveis ou indecidíveis. No entanto, a</p><p>afirmativa III está incorreta. Se A é redutível</p><p>a B e B é um problema indecidível, então A</p><p>também é um problema indecidível, e não</p><p>decidível como a afirmativa sugere.</p><p>Portanto, as afirmativas verdadeiras são I e</p><p>II, o que corresponde à alternativa A.</p><p>09/10/2024, 11:19 estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 2/16</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>2 Marcar para revisão</p><p>Analise as seguintes afirmativas</p><p>I�� Em um problema de decisão, o objetivo é</p><p>decidir a resposta sim ou não a uma questão.</p><p>Em um problema de localização, procura-se</p><p>localizar uma certa estrutura que satisfaça</p><p>um conjunto de propriedades dadas. Se as</p><p>propriedades envolverem critérios de</p><p>otimização, então o problema é dito de</p><p>otimização.</p><p>II�� A teoria da complexidade restringe-se a</p><p>problemas de decisão, já que o estudo de</p><p>problemas NP-completos é aplicado somente</p><p>para esse tipo de problema.</p><p>III�� Os problemas NP�Completos são</p><p>considerados como os problemas mais</p><p>difíceis em NP. Se qualquer problema NP�</p><p>Completo pode ser resolvido em tempo</p><p>polinomial, então todos os problemas em NP</p><p>podem ser resolvidos da mesma forma.</p><p>A análise permite concluir que:</p><p>Apenas a afirmativa I está correta.</p><p>Apenas a afirmativa II está correta.</p><p>Apenas as afirmativas I e II estão</p><p>corretas.</p><p>Apenas as afirmativas I e III estão</p><p>corretas.</p><p>As afirmativas I, II e III estão corretas.</p><p>Questão 2 de 10</p><p>Corretas �1�</p><p>Em branco �9�</p><p>1 2 3 4 5</p><p>6 7 8 9 10</p><p>Exercicio</p><p>Computabilidade e a</p><p>Máquina De Turing</p><p>Sair</p><p>09/10/2024, 11:19 estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 3/16</p><p>Questão não respondida</p><p>Opa! A alternativa correta é a letra</p><p>E. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>Em um problema de decisão, o objetivo é</p><p>decidir a resposta sim ou não. Problemas</p><p>de otimização envolvem critério de</p><p>otimização. Afirmativa I está correta. Os</p><p>problemas NP�Completos são objeto da</p><p>teoria da complexidade computacional e</p><p>são problemas de decisão que, até o</p><p>momento, não foram reduzidos a um tempo</p><p>de solução polinomial. A afirmativa II está</p><p>correta. Para esse caso hipotético, por</p><p>redução, implica que P�NP. Uma vez que</p><p>P�NP, existem algoritmos polinomiais para</p><p>todos os problemas NP e a proposição III é</p><p>correta. Ocorre que não se sabe se P�NP,</p><p>ainda.</p><p>3 Marcar para revisão</p><p>Uma analogia matemática simples do conceito</p><p>de redutibilidade ocorre quando desejamos</p><p>medir a área de um retângulo. Nesse sentido,</p><p>podemos reduzir o problema à medição da</p><p>largura e comprimento. Acerca dos conceitos</p><p>de redução, o que é verdadeiro para</p><p>redutibilidade?</p><p>09/10/2024, 11:19 estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 4/16</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>Se A se reduz a B, podemos usar uma</p><p>solução de A para resolver B.</p><p>Converter um problema resolvido em</p><p>outro problema não resolvido.</p><p>Se A se reduz a B, podemos usar uma</p><p>solução de B para resolver A.</p><p>Converter um problema não resolvido</p><p>em outro problema não resolvido.</p><p>Se A é redutível a B e B é um problema</p><p>indecidível, então A é um problema</p><p>decidível.</p><p>Questão não respondida</p><p>Opa! A alternativa correta é a letra</p><p>C. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>A redutibilidade é um conceito que se</p><p>refere à capacidade de transformar um</p><p>problema em outro de forma que a solução</p><p>do segundo possa ser aplicada ao primeiro.</p><p>Nesse contexto, a alternativa correta é a C�</p><p>"Se A se reduz a B, podemos usar uma</p><p>solução de B para resolver A". Isso significa</p><p>que, se conseguirmos reduzir o problema A</p><p>ao problema B, e já tivermos uma solução</p><p>para o problema B, podemos aplicar essa</p><p>solução ao problema A. Portanto, a solução</p><p>do problema B nos ajuda a resolver o</p><p>problema A.</p><p>09/10/2024, 11:19 estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 5/16</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>4 Marcar para revisão</p><p>O problema da parada para máquinas de Turing,</p><p>ou simplesmente problema da parada, pode ser</p><p>assim descrito: determinar, para qualquer</p><p>máquina de Turing M e palavra w, se M irá</p><p>eventualmente parar com entrada w. Mais</p><p>informalmente, o mesmo problema também</p><p>pode ser assim descrito: dados um algoritmo e</p><p>uma entrada finita, decidir se o algoritmo</p><p>termina ou se executará indefinidamente. Para</p><p>o problema da parada:</p><p>Existe algoritmo exato de tempo de</p><p>execução polinomial para solucioná-</p><p>lo.</p><p>Existe algoritmo exato de tempo de</p><p>execução exponencial para solucioná-</p><p>lo.</p><p>Não existe algoritmo exato, mas existe</p><p>algoritmo de aproximação de tempo</p><p>de execução exponencial que o</p><p>soluciona, fornecendo respostas</p><p>aproximadas.</p><p>Não existe algoritmo exato, mas existe</p><p>algoritmo de aproximação de tempo</p><p>de execução polinomial que o</p><p>soluciona, fornecendo respostas</p><p>aproximadas.</p><p>Não existe algoritmo que o solucione,</p><p>não importa quanto tempo seja</p><p>disponibilizado.</p><p>09/10/2024, 11:19 estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 6/16</p><p>Questão não respondida</p><p>Opa! A alternativa correta é a letra</p><p>E. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>O problema da parada é um dos mais</p><p>famosos problemas indecidíveis na teoria</p><p>da computação. Isso significa que não há</p><p>um algoritmo que possa determinar, para</p><p>qualquer máquina de Turing M e palavra w,</p><p>se M irá eventualmente parar com entrada</p><p>w. Em outras palavras, não existe um</p><p>algoritmo que possa decidir, para qualquer</p><p>algoritmo e entrada finita, se o algoritmo</p><p>terminará ou executará indefinidamente.</p><p>Portanto, a alternativa correta é a E� "Não</p><p>existe algoritmo que o solucione, não</p><p>importa quanto tempo seja disponibilizado".</p><p>5 Marcar para revisão</p><p>Na classificação da hierarquia de Chomsky, a</p><p>gramática tipo 0 é uma gramática de estrutura</p><p>de frase sem qualquer restrição. Dentro dessa</p><p>hierarquia estão classificadas a linguagem</p><p>recursiva e a linguagem recursivamente</p><p>enumerável. Acerca de suas características,</p><p>assinale a afirmação verdadeira.</p><p>09/10/2024, 11:19 estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 7/16</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>Uma linguagem recursiva é um</p><p>subconjunto de uma linguagem</p><p>recursivamente enumerável.</p><p>Uma linguagem recursivamente</p><p>enumerável é um subconjunto de uma</p><p>linguagem recursiva.</p><p>Uma linguagem recursiva e uma</p><p>recursivamente enumerável podem</p><p>fazer um loop para sempre na entrada</p><p>de uma máquina de Turing.</p><p>Uma linguagem recursiva e uma</p><p>recursivamente enumerável são</p><p>equivalentes.</p><p>Uma linguagem recursiva é uma</p><p>linguagem que não é aceita por uma</p><p>Máquina de Turing.</p><p>Questão não respondida</p><p>Opa! A alternativa correta é a letra</p><p>A. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>Na hierarquia de Chomsky, as linguagens</p><p>recursivas são, de fato, subconjuntos das</p><p>linguagens recursivamente enumeráveis.</p><p>Isso significa que todas as linguagens</p><p>recursivas são também recursivamente</p><p>enumeráveis, mas o contrário não é</p><p>necessariamente verdadeiro. Portanto, as</p><p>duas linguagens não são equivalentes.</p><p>Além disso, tanto as linguagens recursivas</p><p>quanto as recursivamente enumeráveis são</p><p>aceitas por Máquinas de Turing. Quando</p><p>09/10/2024, 11:19 estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 8/16</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>uma linguagem é rejeitada, a Máquina de</p><p>Turing para, não entrando em um loop</p><p>infinito. Portanto, a alternativa A é a</p><p>correta.</p><p>6 Marcar para revisão</p><p>Considere uma Máquina de Turing �MT� T dada</p><p>pelas quíntuplas:</p><p>1. �0, 1, 1, 0, D�</p><p>2. �0, b, 1, 1, H�</p><p>Considere que 0 é um estado inicial e 1 é um</p><p>estado final. A configuração inicial da fita é</p><p>igual a 111, com brancos antes e depois da</p><p>cadeia 111 e n é o tamanho da cadeia, neste</p><p>caso igual a 3.</p><p>Qual é a função que essa MT calcula?</p><p>2  �1n</p><p>2 - 1n+1</p><p>2 �1n</p><p>2n+1</p><p>2n</p><p>Questão não respondida</p><p>Opa! A alternativa correta é a letra</p><p>B. Confira o gabarito comentado!</p><p>09/10/2024, 11:19 estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 9/16</p><p>A</p><p>B</p><p>C</p><p>Gabarito Comentado</p><p>Este exemplo ilustra a capacidade de</p><p>computação das Máquinas de Turing. O</p><p>processo deve começar utilizando a</p><p>quíntupla 1. Enquanto a Máquina de Turing</p><p>lê 1 na fita, ela escreve 1, mantém-se no</p><p>estado 0 e move-se para a direita �D�. Ao</p><p>encontrar um espaço em branco, ela</p><p>escreve 1, muda para o estado final 1 e para</p><p>�H�. A cadeia final resultante é 1111. A</p><p>cadeia inicial era 111, que é igual a 2 �1, e</p><p>foi transformada em 1111, que é igual a 2 �1.</p><p>Portanto, a Máquina de Turing calcula a</p><p>função 2 - 1.</p><p>3</p><p>4</p><p>n+1</p><p>7 Marcar para revisão</p><p>Existem dois tipos principais de complexidade</p><p>computacional para um algoritmo:</p><p>complexidade de tempo e complexidade de</p><p>espaço. Nesse sentido, o que é falso para o</p><p>problema da classe P?</p><p>O número de passos (ou tempo)</p><p>necessários para completar o</p><p>algoritmo é uma função polinomial de</p><p>n.</p><p>É computável por uma máquina de</p><p>Turing determinística em tempo</p><p>polinomial.</p><p>Ele contém todos os conjuntos nos</p><p>quais a pertinência pode ser decidida</p><p>por um algoritmo cujo tempo de</p><p>execução é limitado por um polinômio.</p><p>09/10/2024, 11:19 estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 10/16</p><p>D</p><p>E</p><p>Em geral, a classe P contém todos os</p><p>problemas que são resolvidos</p><p>facilmente usando computadores.</p><p>P é definido como o conjunto de todos</p><p>os problemas de decisão para os</p><p>quais existe um algoritmo que pode</p><p>ser realizado por uma máquina de</p><p>Turing não-determinística em tempo</p><p>polinomial.</p><p>Questão não respondida</p><p>Opa! A alternativa correta é a letra</p><p>E. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>A alternativa E é falsa porque a classe P é</p><p>definida como o conjunto de todos os</p><p>problemas de decisão para os quais existe</p><p>um algoritmo que pode ser realizado por</p><p>uma máquina de Turing determinística em</p><p>tempo polinomial, e não por uma máquina</p><p>de Turing não-determinística. A diferença</p><p>entre as duas é que a máquina de Turing</p><p>determinística segue um único caminho de</p><p>computação, enquanto a máquina de</p><p>Turing não-determinística pode seguir</p><p>vários caminhos simultaneamente.</p><p>Portanto, a definição correta da classe P</p><p>envolve a máquina de Turing</p><p>determinística, não a não-determinística.</p><p>8 Marcar para revisão</p><p>Um algoritmo é executado em 10 segundos</p><p>para uma entrada de tamanho 50. Se o</p><p>09/10/2024, 11:19 estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 11/16</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>algoritmo é quadrático, quanto tempo em</p><p>segundos ele gastará, aproximadamente, no</p><p>mesmo computador, se a entrada tiver tamanho</p><p>100?</p><p>10.</p><p>20.</p><p>40.</p><p>100.</p><p>500.</p><p>Questão não respondida</p><p>Opa! A alternativa correta é a letra</p><p>C. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>Para entender a resposta correta, é</p><p>importante compreender o conceito de</p><p>algoritmo quadrático. Nesse tipo de</p><p>algoritmo, o tempo de execução é</p><p>proporcional ao quadrado do tamanho da</p><p>entrada. Portanto, se o tempo de execução</p><p>para uma entrada de tamanho 50 é de 10</p><p>segundos, podemos estabelecer a seguinte</p><p>relação: T(n)=cn , onde c é uma constante</p><p>a ser determinada. Sabendo que T�50��10,</p><p>temos que c*50 = 10 segundos, o que nos</p><p>permite determinar que c=1/250. Assim, a</p><p>expressão de complexidade de tempo para</p><p>esse algoritmo é T(n)=  �1/250� * n .</p><p>2</p><p>2</p><p>2</p><p>09/10/2024, 11:19 estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 12/16</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>Com essa expressão, podemos calcular o</p><p>tempo de execução para uma entrada de</p><p>tamanho 100� T�100� = �1/250��100 , que</p><p>resulta em T�100� = 10000/250 � 40</p><p>segundos. Portanto, se a entrada do</p><p>algoritmo tiver tamanho 100, ele gastará</p><p>aproximadamente 40 segundos para ser</p><p>executado no mesmo computador.</p><p>2</p><p>9 Marcar para revisão</p><p>Com base nas afirmativas abaixo sobre a</p><p>descrição instantânea �DI) da máquina de</p><p>Turing, assinale a resposta correta:</p><p>I. Lembra o estado da máquina.</p><p>II. Lembra da célula que está sendo digitalizada</p><p>pelo cabeçote de leitura e gravação.</p><p>III. O conteúdo de todas as células da fita.</p><p>IV. O conteúdo da célula seguinte à que está</p><p>sendo lida.</p><p>II e III, apenas</p><p>II e IV, apenas</p><p>I, II e IV, apenas</p><p>I, II e III, apenas</p><p>I e IV, apenas.</p><p>Questão não respondida</p><p>09/10/2024, 11:19 estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 13/16</p><p>Opa! A alternativa correta é a letra</p><p>D. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>A alternativa correta é a letra D, que afirma</p><p>que a Descrição Instantânea �DI) da</p><p>máquina de Turing lembra o estado da</p><p>máquina �I�, a célula que está sendo</p><p>digitalizada pelo cabeçote de leitura e</p><p>gravação �II) e o conteúdo de todas as</p><p>células da fita �III�. A afirmativa IV está</p><p>incorreta, pois a cabeça de leitura não tem</p><p>como saber o conteúdo da célula seguinte</p><p>à que está sendo lida. Portanto, as</p><p>afirmativas I, II e III estão corretas</p><p>conforme a definição de Descrição</p><p>Instantânea.</p><p>10 Marcar para revisão</p><p>Para resolver problemas, precisamos construir</p><p>algoritmos. Para esses algoritmos, suas</p><p>complexidades precisam ser calculadas, as</p><p>quais são necessárias para analisar os</p><p>algoritmos e encontrar o mais adequado.</p><p>Considere as seguintes quatro funções:</p><p>f1 (n) = 2n</p><p>f2 (n) = n</p><p>f3 (n) = 2n</p><p>f4 (n) = 2 + 3</p><p>Quais das seguintes sentenças matemáticas</p><p>são verdadeiras?</p><p>I. para n > 0, f2 (n) 2, f1 (n) 2, f3 (n)</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690e4c9138ee6cb7cf4b2/gabarito/ 14/16</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>Somente I e II.</p><p>Somente II, III e IV.</p><p>Somente III, IV e V.</p><p>Somente I, II e V.</p><p>Somente I, III e IV.</p><p>Questão não respondida</p><p>Opa! A alternativa correta é a letra</p><p>D. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>Para entender a resposta correta, vamos</p><p>analisar cada uma das sentenças:</p><p>I. Para n > 0, f2 (n) 2, f1 (n) 2, f3 (n)</p>