Scc-205(joaoluis)

• SCC-205 - Teoria da Computação e Linguagens Formais - Turma A - prof. João Luís

Linguagens Regulares: Autômatos finitos determinísticos e não-determinísticos; expressões regulares; técnicas para identificar e descrever linguagens regulares; técnicas para mostrar que uma linguagem não é regular; propriedades de tais linguagens. 2. Linguagens Livres de Contexto: Gramáticas Livres de Contexto; derivações; árvores de derivação; ambigüidade; autômatos a pilha; propriedades de tais linguagens; técnicas para mostrar que uma linguagem não é livre de contexto. Linguagens Dependentes de Contexto e Linguagens com Estrutura de Frase: Máquinas de Turing; definições básicas e sua relação com a noção de um algoritmo/programa. Poder das Máquinas de Turing e Tese de Church-Turing. Indecibilidade: Máquinas de Turing Universais; Limitações sobre a nossa habilidade de computar; problemas indecidíveis. Teoria de Complexidade: Complexidade de Tempo, Complexidade de Espaço, Intratabilidade.

Quadro de Avisos

• 14/08/2012: Disponíveis Slides do Capítulo 2 + Lista de exercícios.
• 08/08/2012: Especificações do Trabalho 1 disponíveis.
• 31/07/2012: Disponível Lista de Exercícios do Capítulo 1.
• 31/07/2012: Inicio do período letivo.

Informações Gerais

Título: Teoria da Computação e Linguagens Formais (SCC-205) - Turma A - Ciências de Computação

Professor: Dr. João Luis Garcia Rosa (joaoluis@icmc.usp.br)

Aluno PAE: Cristiano Bacelar de Oliveira (cbacelar@icmc.usp.br)

Monitor: Gabriel (gabriel.zerbetto@gmail.com)

Horário de Aulas: Terça (08:10 - 9:50) e Quinta (10:10 - 11:50). Sala 5-004.

Horários de atendimento:

• Professor:

 Quinta, das 15h00 às 18h00. Local: Bloco 4, sala 4-127.

• Aluno PAE:

 Quarta, das 14 às 17h00. Local: ICMC - Bloco 6, sala 6-205.

• Monitor:

 Segunda, das 20h00 às 23h00. Local: A definir.

Programa do Curso

Programa do Curso (apresentação)

Material Didático

• O material do Capítulo 1 está disponível através do Dropbox.

Link: https://www.dropbox.com/sh/rtszzifu0j735qz/ALFB-ZCE0G/SCC-205

• Capítulo 2 - Linguagens Livres de Contexto e Autômatos de Pilha

Trabalhos Práticos

Trabalho 1

• Especificações do Trabalho 1
• Orientações Gerais:

Os grupos para os trabalhos devem ser compostos preferencialmente por três alunos.
Todos os trabalhos deverão ser submetidos ao corretor automático BOCA.
Período de submissão: 27 e 28 de Setembro de 2012.

Sistema BOCA

• Sistema BOCA - SCC205

Listas de Exercícios

• Lista de Exercícios Capítulo 1
• Lista de Exercícios Capítulo 2

Datas Importantes

Provas

• 3 provas:

P1 = 30/08
P2 = 16/10
P3 = 29/11

Apresentação dos trabalhos em grupo

• 2 trabalhos em grupo, com implementação:

Submissão do Trabalho T1 : 27/9.
Submissão do Trabalho T2 : 22/11.

• Trabalho Extra (Alan Turing) - opcional T3 : 29/11

Acréscimo de 0,5 na média.

Notas

• MP = Média Ponderada das Provas:

 P1 ∗ 0, 4 + P2 ∗ 0, 3 + P3 ∗ 0, 3

• MT = Média Aritmética dos Trabalhos

• MF = Média Final:

 Se MP ≥ 5, 0 e MT ≥ 5, 0 então MF = (7*MP + 3*MT)/10
 Senão MF = menor valor entre MP e MT

Links úteis

• Ementa Sistema Júpiter [1]
• Ferrameta JFLAP [2]