Turmas - 1º Semestre de 2018
Turmas
1º Semestre de 2018

(POSCOMP, 2017) Analise as assertivas a seguir.

1. Segundo a Tese de Church, a capacidade de computação representada pela máquina de Turing é o limite máximo que pode ser atingido por qualquer modelo de computação.
2. Um problema X é NP-completo quando X pertence à classe NP e, adicionalmente, X é redutível em tempo polinomial para qualquer outro problema Y na classe NP.
3. Todo problema que está na classe P também está na classe NP.
4. A máquina de Turing, a máquina de Post e a máquina com Pilhas são considerados modelos de computação equivalentes.

É correto apenas o que se afirma nas assertivas:

a. apenas as assertivas I e II.

b. apenas as assertivas I e III.

c. apenas as assertivas II e III.

d. apenas as assertivas II e IV.

e. apenas as assertivas III e IV.

(INMETRO, 2010) No que concerne a utilização e o processamento de máquina de Turing, assinale a opção correta.

a. Na máquina de Turing, o processamento inclui a sucessiva aplicação da função programada até ocorrer uma condição de parada.

b. A máquina em questão registra o valor da palavra de entrada e depois pára, quando a função indicar um movimento da cabeça para a esquerda e ela já se encontrar no início da fita.

c. O conjunto de símbolos usados pela máquina de Turing é infinito.

d. As saídas podem ser apenas binárias, pois as referidas máquinas trabalham com representações lógicas.

e. Uma máquina de Turing pode alterar várias entradas em cada vez, pois ela é capaz de transferir sua atenção para mais de uma posição da fita em cada argumento da função de transição.

Considere o seguinte termo do cálculo-lambda: M = (((λx. λz.(x z))(λy.y)) w)

Considerando a forma normal que resulta da redução completa do termo M, assinale a alternativa correta.

a. w

b. x

c. y

d. z

e. w w

(IFE, 2015) Considere uma Máquina de Turing M que possui:

• Um conjunto finito de estados Q = (q₀, q₁)
• Um estado inicial q₀
• Um estado final q₁
• Um alfabeto inicial Σ = (a, b)
• Um alfabeto de fita Γ = (a, b, ε)
• Um símbolo de fita vazio ε
• Funções de transição representadas pela tabela a seguir:

Qual é a palavra aceita pela Máquina de Turing M?

a. abaab

b. aabab

c. abba

d. babab

e. εaεb

(Marinha, 2011) Em relação às classes de complexidade de problemas, assinale a opção correta.

a. A classe de problemas em P consiste nos problemas que dado um “certificado” de uma solução, é possível verificar se a solução é correta em tempo polinomial no tamanho da entrada.

b. A classe de problemas NP consiste nos problemas que não pertencem a classe P, e por isso são problemas não “verificáveis” em tempo polinomial.

c. A busca binária é um problema em NP-completo, dependendo do tamanho da entrada.

d. Um problema que está em P não estará em NP, exceto problemas NP-completos, os quais não foram demonstrados pela ciência.

e. Dado que exista um problema NP-completo com solução em tempo polinomial, então todos os problemas em NP terão soluções em tempo polinomial.

Na teoria da computação, uma máquina de Post, assim denominada em honra a Emil Leon Post, é um autômato determinístico, baseado na estrutura de dados do tipo fila com um símbolo auxiliar. Post publicou este modelo computacional em 1943 como uma forma simples de sistema canônico de Post. Em poucas palavras, uma máquina de estados finita cuja fila tem um tamanho ilimitado, tal que em cada transição a máquina lê o símbolo da cabeça da fila, remove um número fixo de símbolos da cabeça, e ao fim concatena uma palavra-símbolo pré-definida ao símbolo removido. Desenvolva uma máquina de Post, sobre o alfabeto {0, 1}, que verifique se os números binários fornecidos pelo usuário são números binários pares. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

M = ({0, 1}, D, #)

A Máquina de Turing consiste de basicamente três partes: Uma fita, uma unidade de controle e uma função de transição. A fita é usada como um dispositivo de entrada, saída e memória. Ela é dividida em células que armazenam um símbolo de cada vez. A unidade de controle reflete o estado controle da máquina. Possui uma unidade de leitura e gravação que pode deslocar-se para a esquerda (L) ou para a direita (R) da fita, podendo ler e/ou gravar um único símbolo em cada movimento. A função de transição comanda as leituras e gravações, o sentido de movimento da cabeça e define o estado da máquina. Desenvolva uma máquina de Turing, sobre o alfabeto {a, b, c}, que verifique o triplo balanceamento da entrada fornecida pelo usuário, ou seja, L = {aⁿbⁿcⁿ | n ≥ 0}. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

M = ({a, b, c}, {q₀, q₁, q₂, q₃, q₄, q₅, q₆}, ∏, q₀, {q₆}, {A, B, C}, β, ⊗)

(Diverio, 2000) Autômatos com pilha diferem da definição normal de máquinas de estados finitos de duas maneiras: a) podem fazer uso da informação que está no topo da pilha para decidir qual transição deve ser efetuada e b) podem manipular a pilha ao efetuar uma transição. Autômatos com pilha escolhem uma transição analisando o símbolo atual na cadeia de entrada ou o topo da pilha, enquanto que máquinas de estados finitos convencionais apenas analisam o símbolo da cadeia de entrada. Desenvolva uma máquina com pilhas que reconheça a linguagem L = {ww | w é palavra sobre {a, b}}.

M = ({a, b}, D)