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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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; — Explicar como…

(linguagens de livre contexto) As Máquinas de Turing com fita limitada reconhecem sentenças de linguagens Tipo 1 (linguagens Sensíveis ao Contexto) As Máquinas de Turing reconhecem sentenças de linguagens Tipo 0 (linguagens recursivamente enumeráveis) 66 LINGUAGENS FORMAIS Linguagens Tipo 3, 2, 1 e 0 • Asociação entre classes de linguagens, gramáticas e reconhecedores Linguagem Tipo 3: Regular Tipo 2: Livre Contexto Tipo 1: Sensíveis ao contexto Tipo 0:…

símbolos, a descrição da situação inicial do "jogo" (ou o layout do 'tabuleiro') e uma lista de quais movimentos são permitidos a uma dada posição. Verificação de jogadas de xadrez, a lógica, a matemática são exemplos de sistemas formais que satisfazem estes critérios. Por volta da década de 1930, os esforços para reduzir a matemática a fundamentos lógicos seguros levou a várias tentativas de se tratar a aritmética - o braço da matemática que lida com operações sobre números - como…

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…

exercício 1.1 RESPOSTA: A origem do estudo da computação é milenar e se desenvolveu em diversas épocas e culturas, objetivando responder questões como: ■ O que é uma solução computável? ■ Quais são os limites do que pode ser computado? ■ Existem problemas sem solução computacional? Foi a partir do século XX que importantes contribuições ocorreram, com destaque para os trabalhos de Hilbert (problema de decisão), de Church (cálculo Lambda e hipótese de Church) e de Turing…

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 disciplina) há…

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…

É impossível discutir a era da informação sem passar pelo nome de Alan Turing. Coube ao matemático britânico lançar as bases do que hoje chamamos de ciências da computação. Foi a partir delas que os computadores se tornaram realidade. Para chegar a seus maiores feitos por meio de estudos matemáticos, ele contava com basicamente duas qualidades. Ou, pelo menos, foi o que o próprio Turing sugeriu, em sua tese de doutorado, publicada em 1938. "O raciocínio matemático pode ser considerado,…