Apostila para o curso de Introdução à Teoria da Computação
Essas são notas de aula da disciplina Introdução à Teoria da Computação ministrados no segundo semestre de 2019 para uma das turmas do período noturno do curso de Sistemas de Informação da Escola de Artes Ciências e Humanidades (EACH) da USP. A apostila é o conteúdo apresentado em aula que segue o livro homônio de Michael Sipser. Algumas poucas coisas foram tiradas do livro Elementos da Teoria da Computação de Lewis e Papadimitrius, a parte sobre Máquinas de Turing teve grande inspiração no livro Computabilidade, Funções Computáveis, Lógica e os Fundamentos da Matemática de Carnielle e Epstein e, por fim, a parte sobre complexidade computacional teve grande inspiração no livro Computational Complexity de Papadimitrius.
Agradecemos contribuições como correções de erros ortográficos e gramaticais. Estamos também abertos a debater conceitos mal explicados ou com eventuais erros. As contribuições devem ser feitas por meio de pull requests como um projeto de software convencional.
Alguns direitos sobre o conteúdo desta apostila são protegidos pelo autor sob licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0). Ou seja, você é livre para distribuir cópias e adaptar este trabalho desde que mantenha a mesma licença, dê o devido crédito ao autor e não faça uso comercial.