Universidade Federal de Mato Grosso do Sul
Departamento de Computação e Estatística

Fundamentos da Teoria da Computação
Ciência da Computação, ano 2004

Objetivos

A disciplina Fundamentos da Teoria da Computação tem por objetivo introduzir o estudante de graduação em Ciência da Computação às linguagens formais, à teoria dos autômatos e à complexidade computacional, com ênfase nos dois primeiros tópicos.

O sucesso prático da Ciência da Computação se deve em grande parte aos seus sólidos e elegantes fundamentos. Essa ciência tem suas questões fundamentais, como por exemplo: O que é um algoritmo? O que pode e o que não pode ser computado? Quando um algoritmo pode ser considerado viável na prática? O foco do curso é justamente nessas idéias fundamentais, modelos e resultados que permeiam a Ciência da Computação e que são de certa forma seus paradigmas básicos.

Matemáticos freqüentemente fornecem respostas a certas questões bem antes do mundo todo encontrar razões para fazer essas perguntas. A operação de redes de relés utilizada nos primeiros computadores é descrita exatamente pelas funções de Boole. Note que George Boole fez sua contribuição à Ciência da Computação no meio do século XIX e a álgebra de Boole é usada ainda hoje para representar circuitos TTL. Em meados de 1930, Alan Turing formalizou o conceito de um algoritmo com a apresentação de um dispositivo abstrato de computação e caracterizou as limitações de tais máquinas. Nos anos 50, a abstração dos conceitos por detrás das gramáticas de linguagens naturais forneceu as bases teóricas para o desenvolvimento de linguagens de programação.

As aplicações dessa teoria são evidentes em especial na análise léxica e sintática de linguagens de programação, em modelos de sistemas biológicos, projeto de hardware e em linguagens naturais.

Pré-requisitos

Fundamentos da Teoria da Computação tem como pré-requisito oficial a disciplina de Matemática Discreta. Familiaridade com conceitos como conjuntos, relações, tipos especiais de relações binárias, funções e técnicas de demonstração são muito importantes.

Noções de algoritmos e de programação também são necessárias.

Tópicos

  • Introdução
    • Alfabetos e Linguagens
    • Representações Finitas de Linguagens
  • Autômatos Finitos
    • Determinismo e Não-deterministmo
    • Autômatos Finitos e Expressões Regulares
    • Linguagens Regulares e Não-regulares
    • Minimização de Estados
    • Algoritmos
  • Linguagens Livres de Contexto
    • Gramáticas Livres de Contexto
    • Árvores de Derivações
    • Autômatos à Pilha, Gramáticas Livre de Contexto
    • Linguagens Livres de Contexto
    • Algoritmos
    • Determinismo e Derivações
  • Máquinas de Turing
    • Computação com Máquinas de Turing
    • Extensões
    • Máquinas de Turing de Acesso Aleatório
    • Máquinas de Turing Não-determinísticas
    • Gramáticas