Teoria da Computação/Introdução

Proposta do curso

O curso de Teoria da Computação é voltado para alunos de Computação e visa fornecer aos alunos as ferramentas para analisar, avaliar e entender problemas reais sob o ponto de vista da computabilidade e complexidade dos mesmos. Neste curso, especificamente, os alunos conhecerão os campos de aplicação da teoria da computação com ênfase nos problemas de decisão.

Este curso se relaciona com o curso de Introdução às Linguagens Formais e Autômatos na medida em que vários dos conteúdos daquele curso são retomados neste. Como principal diferença entre os cursos destaca-se que o foco deste é a abordagem da Teoria da Decidibilidade e da Teoria da Complexidade. Os tópicos relativos à Teoria dos Autômatos são apresentados brevemente, com objetivo de apresentar os fundamentos necessários para o entendimento das outras duas teorias. Por meio desta abordagem garante-se que o curso seja contido em si mesmo, não tendo como pré-requisito o curso de Introdução às Linguagens Formais e Autômatos. Porém, os alunos já habituados aos conceitos da Teoria dos Autômatos poderão saltar diretamente para as teorias da Decidibilidade e da Complexidade.

Contudo, o curso não pode ser seguido sem um mínimo de conhecimento formal sobre alguns construtos matemáticos como conjuntos, funções e sequências. Também será útil que o aluno domine a lógica matemática e os métodos de provas de teoremas matemáticos, de modo a acompanhar as provas fornecidas durante o curso.

Da bibliografia do curso

A bibliografia básica é dada pelo livro de Michael Sipser Introdução à Teoria da Computação, já que este livro é adequado para estudantes de computação e serve de base para a proposta do curso. Para contato com um método diferente do utilizado neste curso, o aluno pode utilizar o livro de Diverio e Menezes Teoria da Computação - Máquinas Universais e Computabilidade. Porém, deve-se salientar que este livro não trata da Teoria da Complexidade. A lista de todos os livros recomendados para o curso pode ser encontrada na página da ementa do curso.

As três teorias

A teoria da computação, vista como uma disciplina, oferece as ferramentas necessárias para entender os limites do poder computacional. A pergunta fundamental que pretendemos abordar neste curso é: quais são as capacidades e limitações fundamentais dos computadores? A resposta para esta questão fundamental envolve o estudo de três teorias diferentes: a teoria dos autômatos, a teoria da computabilidade e a teoria da complexidade de problemas.

A teoria dos autômatos trata do desenvolvimento de geradores (gramáticas formais) e reconhecedores (autômatos) para linguagens formais. Esta teoria é o foco principal do curso de Introdução às Linguagens Formais e Autômatos. Aqui, nosso objetivo é visitar esta teoria para determinar a importância das linguagem formais e focar nos reconhecedores de linguagens simples: autômatos finitos determinísticos e não-determinísticos e autômatos com pilha. O estudo destes reconhecedores introduz os alunos no formalismo necessário para manipular estruturas mais complexas, como as Máquinas de Turing, que são o foco desta disciplina.

A teoria da computabilidade lida com os limites do poder de solução de problemas por meio de algoritmos. Esta teoria nos remete à criação dos computadores e da própria ideia de computação. Embora os primeiros computadores tenham criados na década de 40 do século XX, a ideia de Von Neumman sobre o computador com programa armazenado (arquitetura de Von Neumman) retoma a teoria das Máquinas de Turing criada por Alan Turing em 1936. Embora tenha sido criada para lidar com problemas presentes na matemática, a teoria desenvolvida por Turing e outros autores correlatos introduziu o conceito de computabilidade, o qual procura classificar os problemas como solúveis ou insolúveis, servindo como base para a compreensão dos limites da computação.

Tomando como base os problemas solúveis, é possível ainda classificá-los de acordo com a dificuldade de sua resolução. Esta classificação e as técnicas envolvidas na determinação da dificuldade dos problemas é o campo de estudo da teoria da complexidade, cuja principal questão é: o que faz alguns problemas computacionais difíceis e outros fáceis? No escopo desta teoria, a complexidade de um problema é medida pela quantidade de esforço computacional empregada para solucionar tal problema, que pode ser medido em termos de tempo e de espaço (memória). Assim conforme o tempo de solução de um determinado problema ele é posto em uma classe específica. Vale dizer que a teoria da complexidade ainda não é uma disciplina acabada, existindo nela grandes questões em aberto.

Conhecer sobre a complexidade permite que o aluno de computação perceba porque um problema é difícil e como ele deve ser tratado. Vale dizer que nem todas as áreas têm interesse em problemas mais fáceis. A área de criptografia, por exemplo, emprega esforços na procura por problemas que sejam difíceis, pois seu objetivo é elaborar códigos cuja quebra (isto é a solução) seja difícil.