Mudanças entre as edições de "Scc-205(gracan)A"
De CoteiaWiki
(→Avaliação:) |
(→Aula a aula:) |
||
| Linha 46: | Linha 46: | ||
#- 25/8 Máquinas de Turing (3) | #- 25/8 Máquinas de Turing (3) | ||
#- 30/8 Linguagens Decidíveis e Indecidíveis (informal): a propriedades da parada e do algoritmo. | #- 30/8 Linguagens Decidíveis e Indecidíveis (informal): a propriedades da parada e do algoritmo. | ||
| − | #- 1/9 1ª. Prova | + | #- '''1/9 1ª. Prova''' |
| − | #- 5 a 10/9 (S.Patria) | + | #- 5 a 10/9 (S.Patria) - não há aulas |
#- 13/9 Linguagens Decidíveis e Indecidíveis: O processo de redução | #- 13/9 Linguagens Decidíveis e Indecidíveis: O processo de redução | ||
#- 15/9 Teoria da Tratabilidade: problemas P e NP (1) | #- 15/9 Teoria da Tratabilidade: problemas P e NP (1) | ||
| − | #- 19 a 23/9 (S.Comp) | + | #- 19 a 23/9 (S.Comp) - não há aulas |
#- 27/9 Teoria da Tratabilidade: problemas P e NP (2) | #- 27/9 Teoria da Tratabilidade: problemas P e NP (2) | ||
#- 29/9 Hierarquia de Chomsky; Formalismo Gerativo de Linguagens; Gramáticas Irrestritas e Linguagens com Estrutura de Frase X Linguagens Rec. Enum. | #- 29/9 Hierarquia de Chomsky; Formalismo Gerativo de Linguagens; Gramáticas Irrestritas e Linguagens com Estrutura de Frase X Linguagens Rec. Enum. | ||
| Linha 57: | Linha 57: | ||
#- 11/10 Linguagens e Gramáticas Livres de Contexto (2): Lema do Bombeamento e propriedades | #- 11/10 Linguagens e Gramáticas Livres de Contexto (2): Lema do Bombeamento e propriedades | ||
#- 13/10 Linguagens e Gramáticas Regulares (1): definições e exemplos | #- 13/10 Linguagens e Gramáticas Regulares (1): definições e exemplos | ||
| − | #- 18/10 2ª. Prova | + | #- '''18/10 2ª. Prova''' |
#- 20/10 Linguagens e Gramáticas Regulares (2): Lema do Bombeamento, propriedades e Expressões Regulares | #- 20/10 Linguagens e Gramáticas Regulares (2): Lema do Bombeamento, propriedades e Expressões Regulares | ||
| − | #- 24 a 28/10 ( | + | #- 24 a 28/10 (afastamento da professora)- não há aulas |
| − | #- 1 a 4/11 (Finados) | + | #- 1 a 4/11 (Finados)- não há aulas |
#- 8/11 Formalismo de Reconhecimento de Linguagens: Autômatos Linearmente Limitados e LSC; Complexidade de tempo | #- 8/11 Formalismo de Reconhecimento de Linguagens: Autômatos Linearmente Limitados e LSC; Complexidade de tempo | ||
#- 10/11 Autômatos a Pilha e LLC ; Definições, exemplos e Complexidade de tempo | #- 10/11 Autômatos a Pilha e LLC ; Definições, exemplos e Complexidade de tempo | ||
| Linha 66: | Linha 66: | ||
#- 22/11 Autômatos Finitos e LR (2): propriedades | #- 22/11 Autômatos Finitos e LR (2): propriedades | ||
#- 24/11 AFs e APs na Teoria da Compilação: noções gerais | #- 24/11 AFs e APs na Teoria da Compilação: noções gerais | ||
| − | #- 29/11 3ª. Prova | + | #- '''29/11 3ª. Prova''' |
| − | #- 1/12 Substitutiva (necessariamente substitui menor nota) | + | #- '''1/12 Substitutiva (necessariamente substitui menor nota)''' |
Edição das 15h24min de 26 de julho de 2011
Índice
SCC-205 - TEORIA DA COMPUTAÇÃO E LINGUAGENS FORMAIS (TURMA A)
- Local: Sala () - Horários: TERÇAS E QUINTAS - 10:10 - 11:50h
- Profa. Graça Nunes; gracan [arroba] icmc.usp.br; Sala: 4-201
Bibliografia Básica
- Hopcroft, J. E., Ullman, J. D. Formal Languages and Their Relation to Automata.
Addison-Wesley Publishing Company, 1979.
- Hopcroft, J. E., Ullman, J. D. and Motwani, R. Introdução à Teoria de Autômatos, Linguagens e Computação. Tradução da 2a. edição.
Editora Campus, 2001.
- Hopcroft, J. E., Motwani, R., and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation.
3rd. edition. Addison-Wesley, 2007.
- Sipser, M. Introduction to the Theory of Computation. Second Edition, Thomson, 2006.
- Rosa, J.L.G. Linguagens Formais e Autômatos. LTC, 2010.
Avisos:
Avaliação:
3 Provas:
P1: 1o. de setembro
P2: 18 de outubro
P3: 29 de novembro
Média Final = (P1 + P2 + P3) / 3
Obs.: Haverá uma prova substitutiva, no dia 1o. de dezembro, que necessariamente substitui a menor nota das provas anteriores.
Frequência:
Será exigida frequência em 70% das aulas ministradas (incluindo dias de provas).
Aula a aula:
- - 2/8 Organização do Curso; Critério de Avaliação; Motivação para o Curso
- - 4/8 Visão Geral das Teorias tratadas no Curso – objetivos de estudo
- - 9/8 Definição formal de procedimento e algoritmo. Verificação de Término.
- - 11/8 Análise de complexidade de algoritmos (recordação)
- - 16/8 Vocabulários, Cadeias, Linguagens, Reconhecedores e Gramáticas: Definições e Exemplos
- - 18/8 Problemas X Linguagens. Computabilidade: a Tese de Church-Turing. Máquinas de Turing (1)
- - 23/8 Máquinas de Turing (2)
- - 25/8 Máquinas de Turing (3)
- - 30/8 Linguagens Decidíveis e Indecidíveis (informal): a propriedades da parada e do algoritmo.
- - 1/9 1ª. Prova
- - 5 a 10/9 (S.Patria) - não há aulas
- - 13/9 Linguagens Decidíveis e Indecidíveis: O processo de redução
- - 15/9 Teoria da Tratabilidade: problemas P e NP (1)
- - 19 a 23/9 (S.Comp) - não há aulas
- - 27/9 Teoria da Tratabilidade: problemas P e NP (2)
- - 29/9 Hierarquia de Chomsky; Formalismo Gerativo de Linguagens; Gramáticas Irrestritas e Linguagens com Estrutura de Frase X Linguagens Rec. Enum.
- - 4/10 Linguagens e Gramáticas Sensíveis ao Contexto: definições e exemplos
- - 6/10 Linguagens e Gramáticas Livres de Contexto (1): definições e exemplos
- - 11/10 Linguagens e Gramáticas Livres de Contexto (2): Lema do Bombeamento e propriedades
- - 13/10 Linguagens e Gramáticas Regulares (1): definições e exemplos
- - 18/10 2ª. Prova
- - 20/10 Linguagens e Gramáticas Regulares (2): Lema do Bombeamento, propriedades e Expressões Regulares
- - 24 a 28/10 (afastamento da professora)- não há aulas
- - 1 a 4/11 (Finados)- não há aulas
- - 8/11 Formalismo de Reconhecimento de Linguagens: Autômatos Linearmente Limitados e LSC; Complexidade de tempo
- - 10/11 Autômatos a Pilha e LLC ; Definições, exemplos e Complexidade de tempo
- - 17/11 Autômatos Finitos e LR (1): definições e exemplos
- - 22/11 Autômatos Finitos e LR (2): propriedades
- - 24/11 AFs e APs na Teoria da Compilação: noções gerais
- - 29/11 3ª. Prova
- - 1/12 Substitutiva (necessariamente substitui menor nota)
