Mudanças entre as edições de "SCC-505(gracan)"

Edição das 19h08min de 8 de fevereiro de 2011

Índice

1 SCC-505 - INTRODUÇÃO À TEORIA DA COMPUTAÇÃO
2 Avisos:
3 Avaliação:
4 Aula a aula:
5 Slides das Aulas
6 Listas de Exercícios
7 Notas

SCC-505 - INTRODUÇÃO À TEORIA DA COMPUTAÇÃO

Local: Sala ( ) - Horário: SEXTA - 19 - 21h
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, 1969.

Hopcroft, J. E., Motwani, R., and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation.

3rd. edition. Addison-Wesley, 2007.

Moll, R. N., Arbib, M. A., and Kfoury, A. J. An Introduction to Formal Language Theory.

Springer-Verlag, 1988.

Sipser, M. Introduction to the Theory of Computation. Second Edition, Thomson, 2006.
Rosa, J.L.G. Linguagens Formais e Autômatos. LTC, 2010.

Avisos:

- Data de Início das aulas: 21/fevereiro

Avaliação:

3 Provas de igual peso:

05 de maio

02 de junho

30 de junho

Seja MP a média aritmética das 3 provas, e seja CF o conceito final.

CF = A se 8 MP 10;

CF = B se 7 MP< 8;

CF = C se 5 MP <7;

CF = R, caso contrário.

Será exigida freqüência em 70% das aulas ministradas (incluindo dias de provas).

No caso de o aluno ficar distante de até 0,25 de um conceito maior, a entrega das listas de exercícios resolvidas permitirá a mudança de nível.

Aula a aula:

-

Slides das Aulas

Listas de Exercícios

- Lista 0- Análise de Algoritmos: Arquivo:GNLista0AnaliseAlg.pdf

- Lista 1- Automatos Finitos: Arquivo:GNLista1AFDeAFND.pdf

- Lista 2- Gramáticas Livres de Contexto: Arquivo:GNLista2GLC.pdf

- Lista 3- Automatos a Pilha: Arquivo:GNLista3AP.pdf

- Lista 4- Linguagens Livres de Contexto: Arquivo:GNLista4LLC.pdf

- Lista 5- Máquinas de Turing: Arquivo:GNLista5MT.pdf

- Lista 6- Decidibilidade: Arquivo:GNLista6Decidib.pdf

@@ Linha 1: / Linha 1: @@
-=== <font color = "green"> SCE5832 -TEORIA DA COMPUTAÇÃO   </font>===
+=== <font color = "green"> SCC-505 - INTRODUÇÃO À TEORIA DA COMPUTAÇÃO   </font>===
-* Local:  Sala (3010) - Horário: QUA - 9 - 12h
+* Local:  Sala ( ) - Horário: SEXTA - 19 - 21h
 * Profa. '''Graça Nunes'''; gracan [arroba] icmc.usp.br; Sala: 4-201
@@ Linha 15: / Linha 15: @@
 === <font color = "green"> Avisos: </font> ===
--    Data de Início das aulas: 08/março
+-    Data de Início das aulas: 21/fevereiro
 === <font color = "green"> Avaliação: </font> ===
@@ Linha 44: / Linha 44: @@
 === <font color = "green"> Aula a aula: </font> ===
-#- ''10 Mar'' – Apresentação da Disciplina (Prof. João Luis Rosa)
+#-
-#-'' 17 Março'' – Noções de Complexidade
-#- ''24 Março'' – Conceitos de Linguagens Formais. Autômatos Finitos (1)
-#- ''31 Março'' – Semana Santa - não há aula
-#- ''7 Abril'' -  Autômatos Finitos Determinísticos e Não-Determinísticos (2)
-#- ''14 Abril'' - Expressões Regulares e Propriedades (Lema do Bombeamento)
-#- ''28 Abril'' - '''1a. Prova'''
-#- ''5 Maio'' – Propriedades de Decisão das LR. Minimização de AF.
-#- ''12 Maio'' - Gramáticas Livres de Contexto e Autômatos a Pilha
-#- ''19 Maio'' -  Linguagens Livres de Contexto
-#- ''26 Maio'' - '''2a. Prova'''
-#- ''2 Junho'' -  Indecidibilidade e Máquinas de Turing
-#- ''9 Junho'' -  Poder Computacional das Máquinas de Turing
-#- ''16 Junho'' -  Indecidibilidade
-#- ''23 Junho'' - Intratabilidade
-#- ''30 Junho'' - '''3a. Prova'''
 === <font color = "green"> Slides das Aulas </font> ===
 <!-- como colocar arquivo:  [[Arquivo:Teste.pdf]] -->
-'''Aula 1 - 17/3/2010''' - Análise de Algoritmos:
-[[Arquivo:Analisealgoritmos1.pdf]]
-[[Arquivo:Analisealgoritmos2.pdf]]
-'''Aula 2 - 24/3/2010'''
-Tipos de Prova de Teoremas:
-[[Arquivo:Tiposdeprova.pdf]]
-Conceitos Básicos - Linguagens e Problemas:
-[[Arquivo:ConceitosBasicos.pdf]]
-Automatos Finitos Determinísticos:
-[[Arquivo:AFD.pdf]]
-'''Aula 3 - 06/4/2010'''
-Automatos Finitos Não-Determinísticos:
-[[Arquivo:AulaAFND.pdf]]
-'''Aula 4 - 13/4/2010'''
-Expressões Regulares:
-[[Arquivo:ERLinguagens.pdf]]
-Propriedades de Linguagens Regulares:
-[[Arquivo:PropriedadesLRx.pdf]]
-Minimização de Autômatos Finitos:
-[[Arquivo:MinimizacaoAFD.pdf]]
-'''Aula 5 - 12/5/2010'''
-Gramáticas Livres de Contexto
-[[Arquivo:GLC.pdf]]
-Autômatos a Pilha
-[[Arquivo:GNACPx.pdf]]
-'''Aula 6 - 19/5/2010'''
-Propriedades das Linguagens Livres de Contexto
-[[Arquivo:PropLLC.pdf]]
-'''Aula 7 - 26/5/2010'''
-Gramáticas
-[[Arquivo:Gramaticas.pdf]]
-'''Aulas 8 e 9 - 09 e 16/06/2010'''
-Decidibilidade e Máquinas de Turing
-[[Arquivo:Decidibilidade.pdf]]
-[[Arquivo:MT1.pdf]]
-[[Arquivo:MT2.pdf]]
-[[Arquivo:Indecidibilidade.pdf]]
-'''Aula 10 - 23/6/2010'''
-Intratabilidade
-[[Arquivo:Intratabilidade.pdf]]
-=== <font color = "green"> Links e referências </font> ===
-* [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm A questão P=NP]
-*  [http://www.aduni.org/courses/theory/index.php?view=cw Aulas de Teoria da Computação do MIT]
-Linguagens Livres de Contexto e Automatos a Pilha (Prof. João Rosa)
-[[Arquivo:LLC&APJoao.pdf]]
-Linguagens Sensíveis ao Contexto, Linguagens Recursivamente Enumeraveis e Maquinas de Turing (Prof. João Rosa)
-[[Arquivo:LSC&MTJoao.pdf]]
 === <font color = "green"> Listas de Exercícios </font> ===
@@ Linha 175: / Linha 68: @@
 === <font color = "green"> Notas </font> ===
-- Notas todas as provas (01 julho 2010): [[Arquivo:NotasTC01jul.pdf]]

Mudanças entre as edições de "SCC-505(gracan)"

Edição das 19h08min de 8 de fevereiro de 2011

Índice

SCC-505 - INTRODUÇÃO À TEORIA DA COMPUTAÇÃO

Avisos:

Avaliação:

Aula a aula:

Slides das Aulas

Listas de Exercícios

Notas

Menu de navegação

Visualizações

Ferramentas pessoais

Navegação

Pesquisa

Ferramentas