Turmas - 2º Semestre de 2018
Turmas
2º Semestre de 2018

Relacione a Coluna 1 à Coluna 2, associando as definições referentes a complexidade de problemas.

Coluna 1

1. Classe P
2. Classe NP
3. Redução em tempo polinomial
4. Problema NP-completo

Coluna 2

(  ) Problema pertencente à NP para o qual existem reduções de tempo polinomial de todas os problemas pertencentes à NP para ele.

(  ) Conjunto das linguagens que podem ser decididas por uma Máquina de Turing não determinística de tempo polinomial.

(  ) Conjunto das linguagens que podem ser decididas por uma Máquina de Turing determinística de tempo polinomial.

(  ) Redução que mapeia cadeias de uma linguagem A em cadeias de uma linguagem B. Ela ocorre em tempo que é uma função polinomial do comprimento da cadeia de A.

A ordem correta de preenchimento dos parênteses, de cima para baixo, é:

a. 1, 2, 3, 4.

b. 4, 1, 2, 3.

c. 1, 2, 4, 3.

d. 4, 2, 1, 3.

e. 2, 1, 3, 4.

O processamento de uma Máquina de Turing M para uma palavra de entrada w consiste na sucessiva aplicação da função programa a partir do estado inicial q₀ e da cabeça de leitura/gravação posicionada na célula mais à esquerda da fita, até ocorrer uma condição de parada. Analise as assertivas a seguir.

1. Se M aceitar w, significa que w conduziu M
2. Se M rejeitar w, significa que w conduziu M à uma configuração final de rejeição.
3. Se M rejeitar w, significa que w travou M durante o seu processamento.
4. Se M aceitar w, significa que w posicionou a cabeça de leitura/gravação de M na célula mais à esquerda da fita novamente.

É correto apenas o que se afirma na(s) assertiva(s):

a. I e II.

b. I e III.

c. II e III.

d. II e IV.

e. III e IV.

Considere o seguinte termo do cálculo-lambda:

M = (((λxy.(xy))(λa.a))w)

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

a. λa.a .

b. λx.a.

c. w.

d. w w.

e. w w w.

(Diverio, 2000) Uma Máquina Universal é aquela que permite a representação de qualquer algoritmo na forma de um programa para ela mesma. As evidências de que uma máquina é, de fato, universal, podem ser classificados como: interna, consiste na demonstração de que qualquer extensão das capacidades da máquina proposta computa, no máximo, a mesma classe de funções, ou seja, não aumenta o seu poder computacional; e externa, consiste no exame de outros modelos que definem a noção de algoritmo, juntamente com a prova de que são, no máximo, computacionalmente equivalentes. Analise as assertivas a seguir sobre algumas Máquinas Universais.

1. Máquinas de Turing são máquinas universais que manipulam símbolos em uma fita de tamanho infinito.
2. Máquinas de Post são máquinas universais que manipulam símbolos em uma fila circular.
3. Máquinas com Pilhas são máquinas universais que manipulam símbolos em um conjunto de n pilhas, com n > 0.

É correto apenas o que se afirma na(s) assertiva(s):

a. I.

b. II.

c. III.

d. I e II.

e. I e III.

R. Bird desenvolveu um formalismo para o tratamento do conceito de recursão através de definições recursivas, os quais se verifica que a Classe das Funções com Definição Recursiva é a mesma Classe das Funções Computáveis. Implemente uma função recursiva, conforme as definições recursivas de Bird, que verifique se um número natural é ímpar através da seguinte definição recursiva, que retorna 1 quando o argumento é ímpar e 0 quando ele é par.

ímpar(x) = λx.(x = 0 → 0, (x = 1 → 1, ímpar(x - 2)))

A Máquina de Turing consiste basicamente de 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 corrente 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 corrente da máquina. Desenvolva uma máquina de Turing que reconheça a linguagem {xccx^R | x ∈ {a, b}*}.

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

Uma Máquina de Post, assim denominada em honra a Emil Leon Post, é um autômato determinístico, baseado na estrutura de dados de tipo fila com um símbolo auxiliar. Desenvolva uma máquina de Post, sobre o alfabeto {a, b}, que verifique se a palavra fornecida tem o sufixo aa, ou seja, termina com aa. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

M = ({a, b}, D, #)

(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 verifique se duas palavras sobre o alfabeto {a, b, $} são diferentes. O símbolo $ é utilizado como separador das duas palavras. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

M = ({a, b}, D)