1197 Teoria da Computação

Programa, critério de avaliação.

Material

O material encontra-se disponível no xérox do CAM (centro acadêmico de matemática).

Avaliações

Os alunos que entregarem todas as atividades do bimestre, poderão utilizar no dia da prova uma folha A4 manuscrita com suas anotações.

Data das avaliações

• 25/04 - Avaliação 1: Linguagens regulares. Autômatos finitos determinísticos e não determinísticos. Expressões regulares.
• 27/06 - Avaliação 2: Linguagens livres do contexto. Gramáticas livres do contexto. Autômatos com pilha.
• 19/09 - Avaliação 3: Linguagens Turing-reconhecíveis e Turing-decidíveis. Máquinas de Turing. Decidibilidade.
• 28/11 - Avaliação 4: Linguagens livres do contexto. Gramáticas livres do contexto. Autômatos com pilha. Máquinas de Turing.
• 07/12 - Exame final.

Atividades

• Atividade 12: Simulado 04 - Trabalho do 4º bimestre. Entrega: 28/11.
• Atividade 11: Simulado 03. Entrega: 19/09.
• Atividade 10: exercícios 4.2 - 4.7 (livro do Sipser). Entrega: 12/09.
• Atividade 09: exercícios 3.1 a, c, d; 3.2 b, c, d, e; 3.4; 3.6; 3.7; 3.8 (livro do Sipser). Entrega: 17/08.
• Atividade 08: Simulado 02. Entrega: 22/06.
• Atividade 07: exercícios 2.5 b, c, e, f; 2.7 b, d; 2.10; 2.11; 2.12; 2.14 (livro do Sipser). Entrega: 06/06.
• Atividade 06: exercícios 2.1; 2.4 b, c, e, f; 2.6 b, d; 2.9 (livro do Sipser). Entrega: 18/05.
• Atividade 05: Simulado 01. Entrega: 25/04.
• Atividade 04: exercícios 1.12; 1.17 - 1.22; 1.28 (livro do Sipser). Entrega: 13/04.
• Atividade 03: exercícios 1.13; 1.16; 1.8; 1.9; 1.10 (livro do Sipser). Entrega: 04/04.
• Atividade 02: exercícios 1.4 a, c, e, f, g; 1.5 c, g, h; 1.6 (livro do Sipser). Entrega: 23/03.
• Atividade 01: exercícios 0.1 - 0.12 (livro do Sipser). Entrega: 02/03.

Normas de entrega das atividades

• Papel A4 branco, com margens de 2cm.
• Usar frente e verso do papel.
• Escrever na primeira linha com caneta vermelha: nome do acadêmico,RA, código da disciplina e turma, número da atividade. Faça o download do modelo.
• Manuscrito.
• A troca de informações é permitida (e aconselhada), mas a cópia de solução / código não são permitidas. Veja o regime disciplinar.
• As atividades fora das normas não serão aceitos.

Desafios

• Desafio 01: Este programa faz a simulação de AFD e AFN. Existem diversas funções que podem ser acrescentadas nele, como por exemplo, conversão de AFN para AFD. O aluno que implementar alguma dessas funções e apresentar a implementação para o professor até o dia 18/05, terá 1,0 ponto extra na nota do primeiro bimestre. Um aluno pode implementar mais que uma função e ganhar mais pontos! Veja o código para saber as funções que podem ser acrescentadas.