Disciplina_ Teoria da Computação_AV2_40

Prévia do material em texto

Disciplina​: Teoria da Computação - 6 5TECO-NT1 
Professor​: Jardeson Nascimento Barbosa 
Semestre: 2020/02 
 
Estudo Dirigido que corresponde a 40% da Avaliação AV2 
Teresina-PI, 18/11/2020 
 
Baseado nos enunciados abaixo e no material fornecido, responda o que se pede sobre 
Máquinas de Turing e Complexidade Computacional. A resolução desse estudo dirigido deve 
ser enviada para o e-mail ​jardeson.nascimento@professores.facid.edu.br até 28/11/2020 com 
assunto “ATIVIDADE AV2 - Seu Nome” e corresponde a até 40% da AV2. 
 
1. Máquina de Turing 
Em 1936, Alan Turing introduziu um modelo matemático do processo de computação 
conhecido atualmente como Máquina de Turing. Sua estrutura é simples e é o principal modelo 
usado para o estudo do que é ou não computável. Ainda em 1936, Alonzo Church apresentou a 
sua Hipótese que afirma que qualquer função computável pode ser processada por uma 
Máquina de Turing. 
 
a) Descreva o funcionamento da Máquina de Turing 
b) Descreva as finalidades de uso da Máquina de Turing 
 
2. Complexidade Computacional 
A teoria de complexidade computacional procura estabelecer limites para a eficiência 
dos algoritmos, investigando a dificuldade inerente dos problemas computacionais. O problema 
P vs NP é uma questão central em complexidade computacional. Informalmente, ele procura 
determinar se, para uma classe importante de problemas computacionais, a busca exaustiva 
por soluções é essencialmente a melhor alternativa algorítmica possível. 
 
a) Descreva as classes de complexidade de algoritmos 
b) Discorra sobre as diferenças entre problemas P e NP 
c) Cite exemplos de problemas P, NP e NP-Completo 
mailto:jardeson.nascimento@professores.facid.edu.br