-

PPGCC001 - TEORIA DA COMPUTAÇÃO - Turma: 01 (2013.1)

Tópicos Aulas
Introdução: motivação e plano de ensino (03/04/2013 - 03/04/2013)

Introdução a Teoria da Computação

Por que estudar Teoria da Computação?

Discussão do plano de ensino e sistema de avaliação

   Livro texto 
Introdução aos Fundamentos da Computação Linguagens e Máquinas.pdf
  aula1-TermosFormais 
aula01-termosFormais.pdf
  Resultado Final Teoria 2013.1 
Caros, segue resultado final da disciplina, com notas atribuídas a cada questão nos exercícios de teoria.
Teoria da Computação: introdução (08/04/2013 - 08/04/2013)

Autômatos e linguagens

Teoria da computabilidade

Teoria da complexidade

Atividade prática 1 (10/04/2013 - 10/04/2013)

1) Fazer um texto de até uma lauda sobre a palestra de John Hopcroft realizada durante a CLEI 2012:  

Computer science theory to support research in the information age.

 John Hopcroft, Cornell University, Ithaca, New York.

 

2) Fazer um texto de uma lauda (máximo) sobre a palestra de Luiz von Ahn no TED.com em 2011:

Massive-scale online collaboration.

 Luis von Ahn, Carnegie Mellon University.

 

 

    
Inicia em 08/04/2013 às 0h 0 e finaliza em 15/04/2013 às 15h 59
Hierarquia de Chomsky (15/04/2013 - 15/04/2013)

Discussão sobre a Hierarquia de Chomsky:

Gramáticas Regulares, Gramáticas Livres de Contexto, Gramáticas Sensível ao Contexto e Gramáticas Irrestritas.

  aula03-hierarquia de Chomsky.pdf 
aula03-hierarquia de Chomsky.pdf
Atividade prática 2 (17/04/2013 - 17/04/2013)

 

Questões: 1, 2 e 3 (página 66)

Lista-exercícios-1

Referência:

Vieira, Newton J., Introdução aos Fundamentos da Computação : Linguagens e máquinas. Pioneira Thompson Learning, 2006.

 

 

    
Inicia em 15/04/2013 às 0h 0 e finaliza em 16/04/2013 às 12h 0
    
Inicia em 15/04/2013 às 0h 0 e finaliza em 22/04/2013 às 15h 59
Autômatos (22/04/2013 - 15/05/2013)

DES: Definição

DES baseado na Teoria de Autômatos

Implementação de algoritmos

  Linguagens e automatos para DES-parte1.pdf 
Linguagens e automatos para DES-parte1.pdf
  Linguagens e automatos para DES-total.pdf 
Linguagens e automatos para DES-total.pdf
  Linguagens e automatos para DES-parte2.pdf 
Linguagens e automatos para DES-parte2.pdf
    
Inicia em 25/04/2013 às 0h 0 e finaliza em 02/05/2013 às 23h 59
Autômatos com guarda (20/05/2013 - 22/05/2013)

Autômatos com guarda

Statecharts (27/05/2013 - 29/05/2013)

Statechars: conceitos, modelos e propriedades

Rede de Petri (03/06/2013 - 19/06/2013)

DES baseados em Redes de Petri (RdP)

RdP: conceitos, modelos e propriedades

Implementação de algoritmos

  Rede de Petri - modelos gráficos 
SED Redes de Petri-parte1.pdf
  SED Redes de Petri.pdf 
SED Redes de Petri.pdf
Decidibilidade (17/06/2013 - 26/06/2013)

A tese de Church-Turing; Máquinas de Turing e Problemas de Decisão; Máquina de Turing Universal; Problema da Parada; Redução de problemas.

 

Máquina de Turing (01/07/2013 - 03/07/2013)

Definição; Variações de Máquinas de Turing; Gramáticas e Máquinas de Turing; Propriedades das LREs e das Linguagens Recursivas.

 

    
Inicia em 03/07/2013 às 0h 0 e finaliza em 08/07/2013 às 23h 59
    
Inicia em 15/07/2013 às 0h 0 e finaliza em 15/07/2013 às 23h 59
    
Inicia em 14/08/2013 às 0h 0 e finaliza em 30/08/2013 às 23h 59
Atividade prática 3 (08/07/2013 - 10/07/2013)

Resolução de exercícios sobre máquinas de turing e decidibilidade.

Frequências da Turma
# Matrícula ABR MAI JUN JUL Total
03 08 10 15 17 22 24 29 06 08 13 15 20 22 27 29 03 05 10 12 17 19 24 26 01 03 08 10 15 17
1 201310**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 201310**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 201310**** 0 0 0 0 0 2 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4
4 201310**** 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 5
5 201310**** 0 0 0 0 0 0 0 0 2 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 6
6 201310**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1
7 201310**** 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 5
8 201310**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 2
9 201310**** 0 0 0 0 0 2 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 6
10 201310**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
Notas da Turma
# Matrícula Unid. 1 Prova Final Resultado Faltas Situação
1 201310**** 7,1 7.1 0 AM
2 201310**** 7,6 7.6 1 AM
3 201310**** 7,0 7.0 5 AM
4 201310**** 7,4 7.4 2 AM
5 201310**** 8,3 8.3 4 AM
6 201310**** 8,3 8.3 2 AM
7 201310**** 5,5 5.5 5 RN
8 201310**** 8,4 8.4 6 AM
9 201310**** 9,8 9.8 6 AM
10 201310**** 7,6 7.6 0 AM

Nenhum item foi encontrado

Plano de Curso

Nesta página é possível visualizar o plano de curso definido pelo docente para esta turma.

Dados da Disciplina
Ementa: Conceitos Preliminares: representação; prova de teoremas; conjuntos; relações; funções; conjuntos enumeráveis; definições recursivas; indução matemática; linguagens formais; gramáticas; problemas de decisão. Máquinas de Estado-Finito: alguns exemplos; autômatos finitos determinísticos; autômatos finitos não determinísticos; linguagens regulares: propriedades; máquinas de Mealy e de Moore; expressões regulares; gramáticas regulares; linguagens regulares: propriedades. Autômatos com Pilha: uma introdução informal; autômatos com pilha determinísticos; autômatos com pilha não determinísticos; gramáticas livres do contexto; linguagens livres do contexto: propriedades. Máquinas de Turing; Algoritmo de Markov; gramáticas e máquinas de Turing; propriedades das linguagens recursivamente enumeráveis e linguagens recursivas. Indecidibilidade: funções primitivas recursivas e a tese de Church-Turing; máquina de Turing universal; o problema da parada; redutibilidade; exemplos de problemas indecidíveis.
Objetivos:
Metodologia de Ensino e Avaliação
Metodologia: Aulas expositivas (T)
Aulas práticas (P)
Exercícios (E)
Trabalhos de pesquisa bibliográfica (TB)
Estudos dirigidos (ED).
Grupos de discussão (GD)
Procedimentos de Avaliação da Aprendizagem: Para efeito de avaliação será observada a Resolução 043/95-CEPEX que regulamenta a Verificação do Rendimento Escolar nos Cursos de Graduação da Universidade Federal do Piauí.
Serão realizadas 4 avaliações envolvendo os conceitos apresentados nas aulas.
Será considerado aprovado na disciplina o aluno que:
• Obtiver freqüência igual ou superior a 75% da carga horária da
disciplina.
• Obtiver média aritmética nas 4 avaliações maior ou igual a 7 (sete), ou
média aritmética igual ou superior a 6 (seis), resultante da média aritmética das avaliações e da nota do exame final.
O aluno que obtiver média aritmética das 3 avaliações inferior a 4 (quatro) será considerado reprovado e não realizará avaliação final. A prova final consistirá do conteúdo da disciplina.
O aluno que não comparecer às avaliações e/ ou exame final terá o direito de requerer a oportunidade de realizá-los em segunda chamada.
O candidato a exame de segunda chamada poderá requerê-lo por si ou por procurador legalmente constituído, ao professor da disciplina, através do departamento responsável pela mesma, em um prazo de 3 dias úteis, justificando através de documento o motivo da ausência.
Horário de atendimento:
Bibliografia:
Cronograma de Aulas

Início

Fim

Descrição
03/04/2013
03/04/2013
Introdução: motivação e plano de ensino
08/04/2013
08/04/2013
Teoria da Computação: introdução
10/04/2013
10/04/2013
Atividade prática 1
15/04/2013
15/04/2013
Hierarquia de Chomsky
17/04/2013
17/04/2013
Atividade prática 2
22/04/2013
15/05/2013
Autômatos
20/05/2013
22/05/2013
Autômatos com guarda
27/05/2013
29/05/2013
Statecharts
03/06/2013
19/06/2013
Rede de Petri
17/06/2013
26/06/2013
Decidibilidade
01/07/2013
03/07/2013
Máquina de Turing
08/07/2013
10/07/2013
Atividade prática 3
Avaliações
Data Descrição
29/05/2013 1ª Avaliação
12/08/2013 2a Avaliação
: Referência consta na biblioteca
Referências Básicas
Tipo de material Descrição
Referências Complementares
Tipo de material Descrição
Notícias da Turma
: Visualizar

Título

Data
Trabalho Final 14/08/2013
Aula Final 10/08/2013
Aula 05/08 05/08/2013
Aula 10/07/2013 10/07/2013
Avaliação dos trabalhos sobre Redes de Petri 06/07/2013
Máquinas de Turing e Decidibilidade 01/07/2013
Lista de Exercícios 1 17/04/2013

SIGAA | Superintendência de Tecnologia da Informação - STI/UFPI - (86) 3215-1124 | sigjb04.ufpi.br.instancia1 vSIGAA_3.12.446 27/09/2020 00:27