SCC-505-2012(erickrf)

Introdução à Teoria da Computação

Objetivos

Dar ao aluno noção formal de algoritmo, computabilidade e do problema de decisão, de modo a deixá-lo consciente das limitações da ciência da computação: Ineficiência e Intratabilidade; e Problemas Não Computáveis e Indecidíveis. Aparelhá-lo com as ferramentas de modo a habilitá-lo a melhor enfrentar a solução de problemas com o auxílio do computador via Teoria das Linguagens Formais e dos Autômatos.

Informações Gerais

Professor: João Luis Garcia Rosa (joaoluis at icmc dot usp dot br)

Horário de atendimento: Quintas-feiras, 16h às 19h

Aluno PAE: Erick Rocha Fonseca (erickrf at icmc dot usp dot br)

Horário de atendimento: Terças-feiras, 16h às 19h, sala 1-114.

Horário das Aulas: Quartas-feiras, 21h às 22h40.

Sala: 5-003

Quadro de Avisos

• 30/06/2012: Notas da Prova 2 disponíveis. Vista de Provas: aula de 04/07.
• 15/05/2012: Notas da Prova 1 e do Trabalho 1 disponíveis (abaixo). Vista de provas: até o dia 24/05/2012, na sala do professor. Dúvidas em relação à nota do trabalho: ver com Erick.
• A prova substitutiva será realizada no dia 06/06/2012

Material

• Programa do Curso (Apresentação)
• Capítulo 1 - Linguagens Regulares e Autômatos Finitos
• Capítulo 2 - Linguagens Livres de Contexto e Autômatos de Pilha
• Capítulo 3 - Linguagens Sensíveis ao Contexto e Autômatos Limitados Linearmente
• Capítulo 4 - Máquinas de Turing e a Teoria da Computabilidade

Listas de Exercícios

• Lista 1
• Lista 2
• Lista 3
• Lista 4

Trabalhos

• Trabalho 1
• Trabalho 2 (Submissão: 28 a 29 de junho)

Provas

• Data da primeira prova: 02/05
• Data da segunda prova: 27/06
• Data da recuperação: 18/07, às 19h.

Notas

• Notas Prova 1 e Trabalho 1
• Notas da prova substitutiva
• Notas Prova 2 e Médias das Provas
• Notas Trabalho 2