Notas de aula de Teoria da Computação

Notas foram escritas dentro do contexto do curso de Ciência da Computação da Universidade Federal da Fronteira Sul, de acordo com a ementa e com a carga horária que não foram definidas por mim. Há infinitamente mais sobre o assunto do que o que contemplo aqui. Os exercícios apresentados no fim de cada capítulo devem ser entendidos apenas como exercícios iniciais sobre o ponto contemplado, selecionados de modo minimalista dentro do contexto dos instrumentos avaliativos do curso. O leitor deve buscar na bibliografia outros exercícios mais interessantes e mais úteis para sua aprendizagem. Como recursos, o texto conta com comentários em notas de margem e índice remissivo. As equações, teoremas, lemas, corolários e definições seguem uma numeração única, prefixada pela numeração dos capítulos. Bons estudos! Prof. Leandro M. Zatesko leandro.zatesko@uffs.edu.br i ii Sumário 1 Introdução à Teoria da Computação 1.1 O algoritmo mais antigo da História . . . . . . . . 1.2 Um problema intrigante . . . . . . . . . . . . . . 1.3 Não dá para esperar a Idade do Universo . . . . . 1.4 A Pergunta do Milhão . . . . . . . . . . . . . . . . 1.5 Teoria da Computação: uma jornada desafiadora 1.6 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Teóricos da Computação I – EMENTA Máquinas de Turing e a tese de Turing-Church, Problemas Solucionáveis e Não Solucionáveis, Complexidade Computacional e Problemas NP-Completos. Problemas NP-Difíceis. Teorema da Incompletude de Gödel. II – OBJETIVOS GERAIS Permitir que os alunos travem contato com resultados teóricos da Ciência da Computação e avaliem adequadamente a importância dos mesmos. III – OBJETIVOS ESPECÍFICOS — Explicar a tese de Turing-Church e seu significado; —…

uma determinada instância de E se produz a mesma instância de S. 42 LINGUAGENS FORMAIS Modelos Determinísticos e Não Determinísticos Modelos Determinísticos - Exemplo Espaço percorrido por um móvel à uma determinada velocidade constante num determinado espaço de tempo: E= V*T onde E = espaço (variável de saída), V = velocidade constante (variável de entrada) T = tempo decorrido do deslocamento do móvel (variável de entrada) Sempre que V = 80 Km/h e T = 2h, tem-se…

História da Máquina Turing Breve Histórico: 1936: Alan Turing propôs um modelo conhecido como Máquina de Turing. Máquina de Turing é a formalização de um procedimento (seqüência finita de instruções), que pode ser realizado mecanicamente em tempo finito. → Alonzo Church apresentou Hipótese de Church: “Qualquer procedimento pode ser descrito por uma Máquina de Turing”. → Qualquer computação que pode ser descrita por uma Máquina de Turing pode ser executada mecanicamente ou…

5. Maquinas de Turing 5.1 Introdução As maquinas de Turing são uma proposta de formalização da noção de procedimento efetivo (programa executado num computador que sempre fornece uma resposta) A maquina de Turing não é nada mais do que um autômato finito determinístico com uma fita, onde será escrita a palavra a processar, e uma cabeça de leitura que pode se movimentar tanto a direita quanto a esquerda. Com a cabeça de leitura podemos então ler e escrever símbolos do alfabeto…

LISTA DE EXERCÍCIOS – Máquinas de Turing 1. Seja M = (K, ∑, δ, s), em que K = {q0, q1, q2}, ∑ = {a, b, #}, s = q0, e δ é fornecido pela tabela abaixo: q δ(q, σ) σ q0 a (q1, L) q0 b (q0, R) q0 # (q0, R) q1 a (q1, L) q1 b (q2, R) q1 # (q1, L) q2 a (q2, R) q2 b (q2, R) q2 # (h, ‘#’) a) Execute a máquina a partir da configuração inicial (q0, abb#bb##aba). b) Descreva informalmente o que realiza M, e o que M faria se fosse iniciada em qualquer outro quadrado…

Trabalho: Teoria da computação Máquina de Turing Prof. Mestre Hugo Resende. João Paulo Ramos Exercício 2.1: Qual a importância da MT? A MT teve importância fundamental no desenvolvimento das áreas de computabilidade, teoria dos autômatos formais e análise de algoritmos. Baseado nela, Turing tentou construir computadores com instruções extremamente elementares, o que bem depois concretizou-se com as máquinas denominadas de "RISC" (reduced instruction…

Computação Trabalho – Máquina de Turing Instruções: este trabalho poderá ser desenvolvido em duplas e está dividido em duas partes: entrega de material e apresentação da simulação das máquinas Produto a ser entregue: as respectivas máquinas de Turing para cada exercício, postadas no webfólio da disciplina Produto a ser apresentado em aula: as máquinas desenvolvidas rodando em um simulador Data de entrega/apresentação: 20 de junho em laboratório No acervo da turma (página da…

INTRODUÇÃO No primeiro módulo da presente disciplina, será apresentada uma revisão da Hierarquia de Chomsky, bem como da máquina de estados finitos, tópicos estes estudados em disciplina anterior. Em seguida, será apresentada a Máquina de Turing, modelo que simula procedimentos computacionais mais gerais que a máquina de estados finitos. Ao final, a definição formal da Máquina de Turing será aduzida. HIERARQUIA DE CHOMSKY Noam Chomsky classificou as Linguagens em quatro tipos, a…

Teoria da Computação Aula 9 Prof. Me. João Paulo R. de Siqueira Prof. Me. João Paulo R. Siqueira – www.jpsiqueira.com.br 1 Exemplo 3 • Máquina de Turing de duplo balanceamento; Duplo_Bal = { anbn | n ≥ 0 } Prof. Me. João Paulo R. Siqueira – www.jpsiqueira.com.br 2 Exemplo 3 (A/A, D) ab aab abb aabb aba q3 (b/B, E) q1 q2 (a/a, D) (B/B, D) (a/a, E) (B/B, E) (B/B, D) (�/ �, E) Analise as palavras: (�/ �, D) (B/B, D) q0 …