Logo Passei Direto

A maior rede de estudos do Brasil

Grátis
14 pág.
Aspectos_teoricos_da_computacao

Pré-visualização | Página 1 de 3

Curso: Ciência da Computação
Campus: Araraquara
Código da Disciplina: 53A3
 ASPECTOS TEÓRICOS DA COMPUTAÇÃO
Nome: Leonardo Souza de Araujo 
RA: D38HAG-0
Turma: CC7P52
Maio, 2020
Módulo 1 – REVISÃO DA HIERARQUIA DE CHOMSKY 
Questão 1: A Hierarquia de Chomsky prevê quatro tipos de Linguagens, que são denominadas respectivamente:
A - Regular, Irregular, Contextual e Natural;
B - Regular, Livre de Contexto, Dependente de Contexto e Natural;
C - Regular, Livre de Contexto, Dependente de Contexto e Irrestrita;
D -Regular, Irregular, Dependente de Contexto e Livre de Contexto;
E - Regular, Irregular, Livre de Contexto e Natural;
Justificativa:
A Hierarquia de Chomsky é a classificação das gramáticas formais, formado por Noan Chomsky. A classificação possui 4 níveis, descritas na alternativa C.
Questão 2: Assinale a alternativa que apresenta uma máquina conceitual capaz de reconhecer apenas a componente regular das Linguagens previstas na Hierarquia de Chomsky.
A - Máquina de Estados Finitos;
B - Autômato de Pilha;
C - Máquina de Post;
D - Máquina de Early finita;
E - Máquina de Turing com fita finita;
Justificativa:
Uma linguagem regular satisfaz as seguintes propriedades que são equivalentes:
Ela é uma linguagem de expressão regular.
É aceita por um autômato finito.
Questão 3: Assinale a alternativa que apresenta um elemento que não diz respeito a autômatos finitos:
A - Unidade controle;
B - Cursor
C - Fita de entrada;
D - Memória auxiliar;
E - Movimento do cabeçote (cursor) de leitura sempre à direita.
Justificativa: Autômatos não possuem memória auxiliar.
Módulo 2 - DEFINIÇÃO FORMAL DE MÁQUINAS DE TURING; LINGUAGENS RECURSIVAS E RECURSIVAMENTE ENUMERÁVEIS
Questão 4: Uma Linguagem aceita por uma Máquina de Turing é dita:
A - Recursivamente enumerável;
B - Dinâmica;
C - Regularmente Recursiva;
D - Regularmente Adaptável;
E - Adaptável;
Justificativa:
A máquina de Turing pode não parar uma determinada entrada já que podemos mover a máquina para frente e para trás.
Questão 5: Para a classe das Linguagens Recursivas:
A - não existe uma Máquina de Turing que a reconheça;
B - existe pelo menos uma Máquina de Turing reconhecedora que sempre para qualquer que seja a entrada;
C - existe uma classe equivalente de linguagens dinâmicas;
D - existe pelo menos um autômato finito que sempre para qualquer que seja a entrada;
E - existe uma classe equivalente de linguagens irregulares;
Justificativa:Existe pelo menos uma máquina de Turing que reconhecedora que sempre para qualquer que seja a entrada.
Questão 6: A Classe das Linguagens Recursivas:
A - está contida propriamente na Classe das Linguagens Enumeráveis Recursivamente;
B - não pode ser reconhecida por uma máquina de Turing;
C - não pode ser reconhecida por uma máquina de Turing que sempre para qualquer que seja a entrada;
D - é sempre reconhecida por um autômato finito;
E - é sempre reconhecida por um autômato de pilha;
Justificativa:Está contida propriamente na classe de linguagens enumeráveis recursivamente. São linguagens que aceitam a classe de recursivas.
Exercícios propostos (avaliativos)
Exercicios Classroom Mq.T. 
QUESTÃO 1 - Crie uma Máquina de Turing capaz de, dado um número binário qualquer, calcular a quantidade de ocorrências do dígito 1.
Exemplo: Para a entrada [ 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | | | | ... ] 
a máquina deverá responder [ 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | = | 5 | | ... ]
QUESTÃO 2 - Demonstre que a classe de Linguagens Recursivas (LRs) são um subconjunto da classe das Linguagens Recursivamente Enumeráveis (LREs), i.e., LR ⊂ LRE.
JUSTIFICATIVA: As definições da linguagens são as seguintes : 
Linguagens recursivamente Enumeráveis: Uma Linguagem L é recursivamente enumerável se e somente se existe uma máquina de Turing. 
Linguagens Recursivas. Uma linguagem L é dita ser Recursiva se existe uma Máquina de Turing que aceita L e que para em cada w em ∑+.
Como fica dficil determinar se uma cadeia não pertence a linfuagem, já que oide acontecer que ao processar essa cadeia não pertence a linguagem já que pode acontecer que ao processar essa cadeia a Máqiuna de Turing entre em loop infinito, pode-se restringir as Linguagens Recursivamente Enumeráveis dizendo que elas devem ter o conjunto Loop(M) = ꝋ, ou seja: Aceita (M1) = L(M1) = L1/ Rejeita(M1) = ∑+ - L1/ Loop(M1) = ꝋ. Restringindo a linguagem recursivamente enumeravel cria-se um outro subconjunto: A linguagem recursiva. 
QUESTÃO 3 - Um problema de decisão D pode ser enunciado como a relação existente entre um conjunto de instâncias de entrada I e um conjunto de soluções S, ou seja, D: I -> S. Se esta relação é uma função computável, sabemos que há algoritmo A que aceita ou decide uma linguagem L = { <x> | x pertence a ∑* e D(x) = 1 }, onde:
a) O conjunto ∑* corresponde a ...
b) Os valores x para os quais D(x) = 1 equivalem a ...
c) Se o algoritmo A for capaz de responder 1 ou 0 para qualquer x pertencente a ∑*, dizemos que ...
d) Entreganto, se o algoritmo A for capaz de responder 1 apenas para os valores em que D(x)=1, dizemos que ...
Exercicios Classroom Classes de Problemas 
QUESTÃO 1 - Qual a diferença fundamental entre um problema verificável em tempo polinomial de um problema solucionável em tempo polinomial?
JUSTIFICATIVA: A principal diferença consiste no fato de que problemas verificaveis em tempo polinomial podem ser revolvidos por uma máquina deterministica sequencial em uma quantidade de tempo que é polinomial para o tamanho da entrada, já os problemas solucionaveis em tempo polinomial verifica-se as soluções possíveis em tempo polinomial para as máquinas não-deterministicas. Ou seja, enquanto um busca solucionar o problema atraves de passos sequenciais o outro verifica as soluções possíveis.
QUESTÃO 2 - Usando suas próprias palavras, procure caracterizar as classes de problemas P, NP e NP-Completo.
JUSTIFICATIVA: As classes P são problemas de decisão que buscam resolver determinados problemas deterministicos atraves de passos sequenciais em tempo polinomial. As classes NP são problemas do tipo não deterministicos que busca verificar soluções em tempo polinomial. Já as classes NP-Completo são problemas NP que podem ser reduzidos em outros problemas NP, significa que, existem problemas NP complexos que podem ser resolvidos através de subconjuntos de problemas existentes dentro do próprio problema NP, através de um processo que consome tempo polinomial.
QUESTÃO 3 - Pesquise 5 exemplos de problemas NP e o seu correspondente redutível NP-Completo.
JUSTIFICATIVA:
Problema NP – 3 – SAT 
 >> Redutível – Coloração de Grafos.
Problema NP – CLIQUE 
 >> Redútivel – Cobertura de Vértices.
Problema NP – Caminho Hamiltoriano >> Redútivel – Caixeiro Viajante.
Problema NP – Soma de Subconjuntos >> Redútivel – Execução de taredas/penalidades. 
Problema NP – Coloração dos Grafos >> Redútivel – Acoplamento 3D.
QUESTÃO 4 - Assinale a alternativa INCORRETA.
A- A união de duas linguagens recursivas é uma linguagem recursiva.
B- 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.
C- Seja L uma linguagem enumerável recursivamente, se o complemento de L for enumerável recursivamente, então L é uma linguagem recursiva.
D- 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.
E- Todo problema que está na classe P também está na classe NP.
JUSTIFICATIVA: Na realidade a segunda afirmação está equivocada. É impossível saber se X é redutível em tempo polinomial para qualquer outro problema Y.
QUESTÃO 5 - Considere dois problemas de decisão PA e PB, sendo PA indecidível e PB decidível. Observe também dois problemas de decisão PC e PD, cuja decidibilidade é desconhecida. Suponha que seja possível construir de forma correta as seguintes reduções:
de PA para PC.
de PD para PA.
de PD para PB.
Página123