Buscar

Aspectos_teoricos_da_computacao

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 14 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 14 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 14 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

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.Com base no cenário descrito, assinale a alternativa correta.
A- Não se pode afirmar nada sobre a decidibilidade dos problemas PC e PD.
B- Não se pode afirmar nada sobre a decidibilidade de PC, porém PD é decidível.
C- PC é indecidível, contudo não se pode afirmar nada sobre a decidibilidade de PD.
D- PC e PD são ambos indecidíveis.
E- PC é indecidível e PD é decidível.
JUSTIFICATIVA: Nesse caso temos que considerar a redutiblidade:
PA >> PC: Nessa circunstância PA é indecidível e reduziu para PC com decisão desconhecida, logo, PC é indecivivel.
PD >> PA: PD tem decidibilidade desconhecida, reduziu para PA que é indecidível. Portanto, não tem como saber ainda se PD é decidivel.
PD >> PB: PD é indecidivel, porém reduziu para um problema PB decídivel, ou seja, é decidivel. 
Exercicios Classroom Dominação Assintótica
QUESTÃO 1 - Considere as seguintes funções:
f(n) = 2^n --> (dois elevado a n)
g(n) = n! --> (fatorial de n)
h(n)= n^log⁡ n --> (n elevado a log n)
Assinale a alternativa correta a respeito do comportamento assintótico de f(n), g(n) e h(n).
A- f(n)=Ο(g(n)); g(n)=Ο(h(n))
B- f(n)=Ω(g(n)); g(n)=Ο(h(n))
C- g(n)=Ο(f(n)); h(n)=Ο(f(n))
D- h(n)=Ο(f(n)); g(n)=Ω(f(n))
E- Nenhuma das anteriores
JUSTIFICATIVA: O correto seria: h(n)=O(f(n)); f(n)=O'(g(n)). Pois, g(n) domina assintoticamente as demais funções.
Exercicíos Classroom Análise de Algoritmos
QUESTÃO 1 - Para medir o custo de execução de um algoritmo, é comum definir uma função de complexidade f, em que f(n) é a medida de tempo necessário para executar um algoritmo para um problema de tamanho n. Considere as afirmações abaixo sobre funções de complexidade:
I. Se f(n) é uma medida de quantidade de tempo necessário para executar um algoritmo em um problema de tamanho n, então f é chamada função de complexidade de tempo.
II. Se f(n) é uma medida de quantidade de memória necessária para executar um algoritmo de tamanho n, então f é chamada função de complexidade de espaço.
III. A complexidade de tempo não representa o tempo diretamente, mas é estimada pelo número de vezes que determinada operação relevante é executada.
Quais estão corretas?
A- Apenas I
B- Apenas II
C- Apenas III
D- Apenas I e II
E- I, II e III
JUSTIFICATIVA: O custo de execução de um algoritmo tem como premissas todas afirmações acima. 
QUESTÃO 2 - A análise de algoritmos que estabelece um limite superior para o tempo de execução de qualquer entrada é denominada análise:
A- do melhor caso.
B- do caso médio.
C- do pior caso.
D- de ordem de crescimento.
E- do tamanho da entrada.
JUSTIFICATIVA: O melhor caso sempre definirá o limite superior para o tempo de execução. Portanto, no momento que que houver um algoritmo de melhor desempenho, será esse algoritmo estabelecido como o melhor caso.
Exercicíos – LISTA 1
QUESTÃO 6 – A que se refere o caráter não-deterministico de um mq.T que seja classificada desta forma ?
JUSTIFICATIVA: 
Trata se de uma Máquina de Turing que, dados um mesmo estado e símbolo, admitem mais de uma transição possível. Desta forma pode existir eventualmente várias computações possíveis para o processamento de uma mesma palavra. Uma cadeia é tida como válida (aceita) quando existe alguma computação para a qual a máquina pára alcançando um estado final.
QUESTÃO 8 – A respeito da Tese de Church-Turing:
Descreva de maneira consistente e objetiva o que ela define.
Quais as implicações da sua veracidade? 
JUSTIFICATIVA:
Uma definição para Tese de Chrurch Turing seria: A partir de um estado inicial e uma entrada inicial (possivelmente vazia), as instruções descrevem uma computação que, quando executada, irá prosseguir por meio de um número finito de estados sucessivos bem definidos, acabando por produzir uma ‘saída’ e terminando em um estado final .
Houve um implicação direta dessa tese que definiu uma equivalência entre os dois metodos: Toda função computável por um Algoritmo também é computável por uma Máquina de Turing.
Exercicíos – LISTA 2
QUESTÃO 5 - Qual a diferença fundamental entre um problema verificável em tempo polinomial de um problema solucionável em tempo polinomial?
QUESTÃO JÁ FOI RESPONDIDA ACIMA.
QUESTÃO 6 - Após as descobertas de Church e de Turing, a comunidade científica se dedicou ao estudo de inúmeros problemas que ainda permaneciam em aberto, de características e naturezas aparentemente diferentes. Muitos deles já haviam recebido alguma atenção, porém até aquele momento, não se dispunha de definições formais para que se pudesse conduzir uma análise mais consistente. Notoriamente, surgiram elementos comuns e bastante típicos entre eles, o que permitiu que se realizasse uma classificação dos problemas em categorias. Deste modo, caracterize as classes de problemas P, NP e NP-Completo.
JUSTIFICATIVA: 
Classes P: P é a classe de problemas de decisão para os quais existe um algoritmo deterministico que soluciona em tempo polinomial. Isto é, trata-se do conjunto de problemas que podem ser resolvidos em tempo polinomial.
Classes NP: Np é a classe de problemas de decisão para os quais existe um algoritmo não-deterministico limitado polinomialmente.Ou seja, trata-se do conjunto de porblçemas que podem ser verificados em tempo polinomial.
Classes NP- completo: Um problema N é dito NP completo se: N pertence a NP e, para todo problema K pertencente a NP, tal que K esteja em N. Ou seja, trata-se de um grupo de problemas em NP nos quais todos os demais problemas da classe NP podem ser a eles reduzidos, através de um processo que consome tempo polinomial.
QUESTÃO 7 - A respeito das relações entre P, NP e NP-Completo
Demonstre que P ( NP
Qual seria a consequência caso fosse demonstrado que NP ( P?
Qual a consequência de encontrarmos um algoritmo de tempo polinomial para um problema NP-Completo?
JUSTIFICATIVA:
TEOREMA 𝑃⊆𝑁𝑃: Para qualquer algoritmo polinomial que solucione os problemas de decisão em 𝑃, pode se conceber um algoritmo não determinístico com fase inicial
vazia.
TEOREMA 𝑁𝑃⊆𝑃: Provar isso se mostrou extremamente difícil! Ninguém conseguiu isso até hoje.
Implicação de algoritmo de tempo polinomial para NP-completo:
Significa que se um algoritmo polinomial decidir um desses problemas, então todos os problemas em NP serão decididos em tempo polinomial. Por sua vez, se alguém provar que um desses problemas não é decidível em tempo polinomial, então prova se que as classes são diferentes.
Exercicíos – LISTA 3
QUESTÃO 1 - Quais das conjecturas abaixo são verdadeiras? Justifique sua resposta demonstrando de modo matemático a veracidade ou falsidade da igualdade proposta.
10n = ((n): Para: n ≥ 10, temos que 10 ≤ 10n ≤ O(n). Portanto, verdadeiro. 
n ≥ 10 
10n ≤ n * 10n 
10n = 10n * n 
=10 n^2/10 n 
= n
10n2 = ((n): Para: n ≥ 10^2, temos que 10 ≤ 10n^2 ≤ O(n). Portanto, falso. 
n^2 ≥ 10
10n^2 ≥ n^2 * 10n ^2 
10n^2 = 10n^4 
= 10n^4 / 10n^2 
= n^2 
10n55 = ((2n) : Para n ≥ 10, temos que 10 ≤ 10n^55 ≤ O(2^n).Portanto, 
n ≥ 10
QUESTÃO 2 - É correto afirmar que ... ? Justifique.
n2 + 200n + 300 = O(n2)
n^2 + 200n + 300 ≤ n^2 + 200n^2 + 300n^2 = 501n^2 
f(n) ≤ 501 g(n) para todo n ≥ 1. Portanto, f(n) = O(g(n)) 
QUESTÃO 7 - Sejam e duas funções assintoticamente não-negativas. Usando a definição básica da notação , mostre que a função pertence a 
c1 * (f(n) + g(n)) ≤ (f(n), g(n)) ≤ c2 . (f(n) + g(n)) 
define-se: c1 * (f(n) + g(n)) ≤ c2 * (f(n), g(n)) 
 
 max (f(n), g(n)) ≤ c2 * (f(n) + g(n)) 
 f(n) ≤ (f(n) + g(n)) ≤ g(n) ≤ (f(n) + g(n)) 
somando as equações: f (n) ≤ max(f(n), g(n)) ≤ c1 * g(n) (f(n), g(n))
c1 * (f(n)+g(n)) ≤ 2 * max(f(n), g(n)) \\ 1/2.(g(n)+f(n))(f(n), g(n)) 
resposta: c1 = ½ ; c2 = 1; n0 = 0;
Exercicíos – LISTA 4 
QUESTÃO 1 - Dado os algoritmos abaixo, calcule a complexidade para o pior caso e para o caso médio:
A – JUSTIFICATIVA: 
Caso médio: 
CUSTO 
# VEZES 
c1 
N 
c2
N – 1 
c3
0
c4
N – 1 
c5
N – 1 
c6
0
c7
0 
c8
N – 1 
T(N) = (c1 + c2 + c4 + c5 + c8) n – (c2 + c4 + c5 + c8) T(N) = AN – B 
T(N) = c1n + c2(n-1) + c4(n – 1) ... c8(n-1),portanto O(n). 
Pior caso:
CUSTO 
# VEZES 
c1 
N 
c2
N – 1 
c3
N – 1 
c4
N – 1
c5
½ (N^2 + N – 2) 
c6
½ (N^2 + N – 2)
 c7
½ (N^2 + N – 2) 
c8
N – 1 
𝑇𝑛= 𝑛 + 4𝑛 − 1+ ½(𝑛^2 + 𝑛 – 2 + ( 𝑛^2 − 𝑛)
𝑇𝑛=3/2 𝑛^2 +9/2𝑛 – 5, portanto O(n^2).
B- JUSTIFICATIVA: 
Caso médio: 
CUSTO 
#VEZES
C1 
N 
C2 
N – 1 
C3 
0
C4 
0
C5 
0
T(N) = ( C1 + C2)N – (C2) 
T(N) = AN – B 
T(N) = C1N + C2(N-1) = O(N)
Pior caso:

Outros materiais