Notas de aula de Teoria da Computação

Notas de Aula em

Teoria da Computação
Prof. Leandro M. Zatesko
2o. semestre de 2014

Esta página foi intencionalmente deixada em branco.

A vida não é um problema para ser resolvido, mas uma realidade para ser experienciada.
Søren A. Kierkegaard

Prefácio
Escrevi estas Notas de Aula para o curso de Teoria da Computação da Universidade Federal da
Fronteira Sul ministrado no 2o. semestre de 2014 com os objetivos apenas de padronizar notações matemáticas e orientar os acadêmicos em seus estudos. São meras anotações, pouco revisadas e possivelmente com muitos erros, ainda em sua segunda versão, e de modo nenhum substituem a bibliografia indicada, a saber:
Bibliografia básica [1], [2], [3], [4].
Bibliografia complementar [5], [6], [7], [8].
Portanto, não é o que está escrito nestas Notas, nem mesmo o que o professor fala em sala de aula, mas são os livros supracitados que são autoridade suprema no assunto, e são eles que devem ser utilizados pelo estudante enquanto se preparando para as avaliações.
Se o leitor encontrar algum erro nestas Notas ou quiser tecer sobre elas algum comentário, que se sinta à vontade e, por favor, que me envie um e-mail. Não tenho a menor pretensão de algum dia tornar estas Notas um livro, uma vez que já existem excelentes livros sobre o assunto. Divulgo-as publicamente, sem proteção, e autorizo que sejam usadas livremente.
Todavia, ressalto que minhas 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