en pt-br

Teoria da Computação

A partir de 2004/2, parte material apresentado em sala de aula na WEB, está disponibilizado neste site.

Quem dispuser de algo pertinente na área, agradeço antecipadamente o envio do material.

Veja abaixo o diretório principal da disciplina.

Junto aos estudantes, tenho trabalhado para formatar um material consistente e completo.

Todos os links interessam aos estudantes, bem como complemento do conteúdo apresentado em sala de aula !


Horário das aulas

  • 2as. feiras: 08:20 às 10:00 hrs. (Nova Sala F-103)
  • 4as. feiras: 08:20 às 10:00 hrs. (Nova Sala F-103)

Obs: O intervalo das 09:10 hrs. é compensado com o término da aula às 10:00 hrs

Avisos a turma de 2006-1

Recomendável para usuários Windows, os demais do Linux fiquem com o xfig;

Veja: o Sítio do TEXcad? ;

  • Notas sendo liberadas na medida do possível ...
  • 1a. Prova: (notas liberadas em 13/06)
  • 2a. Prova: 05/07 4a. feira - 08:00 hrs.
  • Exame Final: 24 ou 26 julho ver com o Prof. Mendes
  • Novo material de Lambda Calculo ... liberado hoje 28/06 (4a. feira)
  • Na 2a. feira, dia 03/07, no horário da aula, estarei a disposição para tirar dúvidas sobre a prova de 05/07.
  • Todas as listas devem ser entregues em papel impresso.
  • A maioria dos textos está no formato em PS e PDF. Ver links do Ghostview e Ghostscript.

Critério de Avaliação para 2006-1

  • 02 provas (peso: 50% a 80% da MS)
  • 06 a 10 (dez) listas de exercícios

Alguns links (consulte-os)::

Parte do material apresentado em sala de aula está neste diretório

Este é o Diretório principal/oficial da disciplina.

Atualizações quase que diárias.

Contudo, o livro texto e os demais indicados pelo professor, é o que se constitui como: indispensável.

Agradecimentos: Carlos Camarão (UFMG) e Bernardo Lula (UFCG), que gentilmente cederam parte do material aqui contido.

Turma 2006/1 - Listas de exercícios, provas, notas, etc

Basicamente as listas (em ps, pdf e tex), e notas dos alunos, etc

Disciplina de Teoria da Computação na UFRGS

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

Um simulador da Máquina de Turing

Gráfico e tudo mais. Não tenho certeza sobre qual é a versão, e se está operacional.

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 simulador de Máquina de Turing (em Prolog)

Este simulador encontra-se numa versão estável... foi adaptado por mim 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.

A 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 , meu Prolog predileto !

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.

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

Arquivo em Postscript, numa abordagem próxima ao do livro do Sipser. Em português.

Um texto/slides sobre computabilidade e sistemas formais

Arquivo em PDF, pronto para download. Versão em português de Portugal.

Um texto sobre Máquinas de Turing do Prof. Lucas Rangel

Arquivo em PDF, pronto para download

Um texto sobre o problema da parada, escrito pelo Prof. Lucas Rangel (interessante)

Arquivo em PDF, pronto para download

Um resumo (com muito humor e figuras)

Do que é visto em um curso típico de Teoria da Computacao

Arquivo em PDF, pronto para download. Versão em inglês.

Outros modelos computacionais, além da MT

Enfatizo esta abordagem no curso.

Arquivo em PDF, pronto para download. Versão em inglês.

Artigo de Lambek

Um clássico que faz um "overview" da área de computabilidade

Arquivo em Postscript, pronto para download. Versão em inglês.

Turma 2003/1 - Listas de exercícios, provas, avisos, etc

Turma 2003/2 - Listas de exercícios, provas, avisos, etc

"Release" definitivo dos temas das apresentações.

Confira a sua vez e seu tema ... (antigo).

Turma 2004/1 - Listas de exercícios, provas, notas, etc

Basicamente as listas, e notas dos alunos, etc

Turma 2004/2 - Listas de exercícios, provas, notas, etc

Basicamente as listas, e notas dos alunos, etc

Turma 2005/1 - Listas de exercícios, provas, notas, etc

Basicamente as listas, e notas dos alunos, etc

Turma 2005/2 - Listas de exercícios, provas, notas, etc

Basicamente as listas, e notas dos alunos, etc


Uma motivação a disciplina, é o que Michael Sipser 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."

Endereço Eletrônico: claudio@joinville.udesc.br