en pt-br

Teoria da Computação

  1. Quem dispuser de algo pertinente na área, em LaTeX , o material será bem recebido e compartilhado
  2. Junto aos estudantes, estamos trabalhando para formatar um material consistente e completo.

Uma motivação a disciplina, é o que Michael Sipser (autor do livro texto) diz:

"Theory is good for you because studying it expands your mind. Computer technology changes quickly. Specific technical knowledge, though useful today, becomes outdated in just a few years. Consider instead the abilities to think, to express yourself clearly and precisely, to solve problems, and to know when you haven't solved a problem. These abilities have lasting value. Studying theory trains you in these areas."


Semestre Corrente

Horário das aulas

  • 2as. feiras: 08:20 às 10:00 hrs. (Salas F-107)
  • 3as. feiras: 10:10 às 11:50 hrs. (Salas F-107)

Avaliação

  • 2015: um exercicio no simulador 5%
  • 2 provas ~ 45%
  • Avaliações semanais ... 2% a 3% cada avaliação
  • Provão Final (toda disciplina -- obrigatório) ~ 35%
  • O trabalho sobre algoritimo redutores e redução (duplas) ~ 15%
  • Há pontos extras por balões na maratona
  • Há pontos extras por problemas resolvidos na disciplina, propostos pelo prof.
  • MS >= 5,0 (aprovado)
  • Exame Final: SEMPRE NO PRIMEIRO DIA OFICIAL DOS EXAMES (para 2015/2 : )

Material do Curso

(caso algum link esteja inválido me avisem

Basicamente tudo aqui, exceto exercícios resolvidos (sempre em elaboração):

a MTs?. Obrigatório para quem se aventurar na área.

Outros Formalismos de Computacionais -- Complementar

valida a nota na disciplina. Este foi em 2006, pode ser que tenhamos novas versões.


Material ANTIGO ... talvez útil

Contudo, o livro texto e os demais indicados pelo professor, é o que se constitui como: indispensável.
Agradecimentos: Carlos Camarão (UFMG), Bernardo Lula (UFCG), e Humberto Longo (UFG) que gentilmente cederam parte do material aqui contido.


Um simulador de Máquina de Turing (em Prolog)

Ou também:

Outros exemplos e a versão atual do simulador, via Dropbox

Este simulador encontra-se numa versão estável... foi adaptado afim de torná-lo didático, para que os alunos possam melhorá-lo, e desenvolvam aplicações sobre este simulador. Seu ponto forte é a flexibilidade quanto ao que se deseja sobre o programa simulado na MT.

Uma versão original foi escrita pelo Dr. Rajshekhar Sunderraman, Georgia State University, raj@cs.gsu.edu

Mas com a permissão ("copyright") do Dr. Sunderraman, reescrevi boa parte do código.

Oficialmente utilizei o: SWI-Prolog , um Prolog padrão e bem-conhecido !
Há alguns exemplos que o aluno pode testar. Ex: soma e multiplicação unária, etc.

Um exemplo de programa para o simulador acima

Este programa computa sentenças do tipo: a^nb^nc^n para n>=0 É um exemplo clássico da área, é uma gramática do tipo 1. Outras implementações de exemplos estão sendo disponibilizadas. Para programação, basta seguir a notação aqui adotada nos exemplos.

'''News: Apostila sobre complexidade computacional: baixe aqui '''


Alguns links de interesse (talvez desatulizados):

Disciplina de Teoria da Computação na UFRGS

Uso muitos exemplos e partes do livro texto do Prof. Tiaraju.

Aulas teóricas de Lógica Computacional

link de Portugal, bem interessante.

Disciplina de Teoria da Computação na UFCG

Onde o Prof. BERNARDO LULA JUNIOR, usa o mesmo livro que é adotado em nosso curso. Há um trabalho de tradução do livro do Sipser e muitos slides em ppt.

Vale pena conferir.

Disciplina da Pós do ICMS-USP de Teoria da Computação

Há várias monografias em *.doc e *.pdf, de vários assuntos tratados na disciplina de TEC.

Fortemente recomendável.

Referência do curso: pos2o2002_Teoria_Computacao_(SCE5832?) (http://coweb.icmc.usp.br/coweb/mostra.php?ident=46)

Disciplina de Fundamentos da Teoria da Computação na UFMG

Onde prof. Newton José Vieira possui experiência na área.

Há um interessante material, das várias vezes que o prof. ensinou esta disciplina.

Siga para última edição, e que há um livro em pdf.

Introduction to the Theory of Computation, de Michael Sipser

Este é o livro texto adotado (no momento), usamos a partir do capítulo 3 até o 7 inclusive.

As transparências do curso tem por base este livro.

Grupo de Teoria da Computação do MIT

Dispõe de links interessantes a disciplinas lá lecionadas por este grupo.

Um texto sobre decidibilidade do prof. Newton José Vieira (UFMG)