PROVA ASPECTOS TEÓRICOS DA COMPUTAÇÃO - ALGUÉM AJUDA A RESPONDER?

ASPECTO TEORICO DA COMPUTAÇÃO

1 – Assinale a alternativa correta:

1. Para se aumentar o poder computacional da máquina de Turing, deve-se adicionar múltiplas fitas de entrad
2. Há provas formais que demonstram que o dispositivo da MT com fita infinita possui exatamente o poder computacional de qualquer outra versão entendida.
3. Há provas formais que demonstram que o dispositivo da MT com fita  ilimitada á esquerda e á direita possui poder computacional maior que aquela que apresenta fita ilimitada apenas á direita.
4. Um dos recentes resultados da Teoria da Computação diz respeito à prova formal que uma Máquina de Turing tridimensional apresenta poder computacional maior que as máquinas de Turing padrão.
5. Prova-se que “Uma função da teoria dos números é computável por um algoritmo se, e somente se, for computável por Turing”.

 

 

2 – Assinale a alternativa correta:

1. A Máquina de Turing não reconhece Linguagens Regulares.
2. Há provas formais que demonstram que o dispositivo da MT com fita ilimitada à esquerda e à direita possui poder computacional maior que aquela que apresenta fita ilimitada apenas á direita.
3. Para se aumentar o poder computacional da Máquina de Turing, deve-se multiplicar o número de cursores a fim de se permitir operações de leitura e escrita paralelas.
4. Todas linguagens recursivamente enumeráveis é regular.
5. Existem Linguagens que não são recursivamente enumeráveis.

 

 

3 -  Assinale a alternativa que apresenta a definição de Decidibilidade:

1. É a capacidade de simular qualquer Máquina de Turing apropriadamente codificad
2. É o estudo da propriedades exibidas pelas linguagens, com o objetivo de terminar a existência ou não de  algum algoritmo capaz de aceitar ou rejeitar, em tempo e espeço finitos, uma cadeia qualquer apresentada para análise.
3. É a capacidade de processar uma linguagem regular.
4. É o estudo das propriedades exibidas por uma Máquina de Turing para determina e tempo de processamento de uma linguagem.
5. É o estudo das propriedades exibidas por uma máquina de Turing para determinar a quantidade de memória consumida no processamento de uma cadeia qualquer.

 

4 – Assinale a alternativa correta:

1. Todo problema decidível apresenta solução O(n²).
2. Todo problema decidível apresenta solução O(2\n)
3. Todo problema decidível apresenta solução com complexidade computacional polinomial.
4. Toda máquina de Turing com n³ 1 fita pode ser reduzida a uma máquina de Turing padrão.
5. A eliminação de fitas adicionais de uma MT não transforma o tempo de execução.

 

5 – Assinale a alternativa que apresenta apenas funções Polinomiais.

1. f(n) = 2, f(n) = 2n² + 2, f(n) = n³ + 3 n² +n² +3m + 1.
2. f(n) = n² +2\n, f(n) = 2n² +2, f(n) = log n²
3. f(n) = n² + n, f(n) = log n, f(n) = 2n² + 2.
4. f(n) = n² +2\n, f(n) = 2n² + 2, f(n) = n³ + 3 n² + 3n +1.
5. f(n) = n² +2\n, f(n) = 2n² + 2, f(n) = 3.

 

6 – Assinale a alternativa correta.

1. O problema do caixeiro viajante pertence á classe P.
2. O problema do caixeiro viajante não apresentaria soluções práticas.
3. O problema do caixeiro viajante é tratável.
4. O problema do caixeiro viajante é não-solucionável.
5. O problema do caixeiro viajante é intratável.

 

7 – Assinale a alternativa que apresenta uma característica que não diz respeito à Máquina de Turing:

1. Fita de trabalho ilimitada à direit
2. Conjunto finito ou infinito de estados.
3. Cursor movimenta-se livremente à direita ou à esquerda.
4. Fita de trabalho passível de ser lida e escrita.
5. Processa linguagens recursivas.

 

8 – Assinale a alternativa que apresenta um problema cuja solução é polinomial.

1. A rota mais longa para se visitar n cidades de uma região.
2. A rota mas curta para se visitar n cidades de uma região.
3. A pior alocação de processos à memória de um sistema computacional.
4. A alocação ótima de processos ao microprocessador.
5. A verificação da existência de um caminho em um grafo G que passe por todas as arestas uma única vez.

 

9 - Assinale a alternativa incorreta.

1. Em um problema de decisão, o objetivo é decidir a resposta sim ou não a uma questão.
2. Linguagem codificam problemas.
3. É possível reduzir o problema do ciclo hamiltoniano para o da satisfabilidade booleana.
4. A classe NP contém muitos problemas de interesse prático.
5. NP é o conjunto de todas as linguagens que são decidíveis em tempo polinomial p(n) em máquinas de Turing determinadas.

 

10 – Assinale a alternativa correta:

1. O problema do caminho de Euler é NP = Completo.
2. É possível demonstrar que PÍ NP e NP Í P.
3. Não se sabe se P = NP.
4. O problema do caixeiro viajante pertence à classe P.
5. O algoritmo para busca em uma árvore binária é NP = Completo.