-

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

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

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
    
Inicia em 30/03/2015 às 0h 0 e finaliza em 31/03/2015 às 23h 59
Teoria da Computação: introdução (19/03/2015 - 24/03/2015)

Autômatos e linguagens

Teoria da computabilidade

Teoria da complexidade

    
Inicia em 30/03/2015 às 0h 0 e finaliza em 31/03/2015 às 23h 59
    
Inicia em 30/03/2015 às 0h 0 e finaliza em 31/03/2015 às 23h 59
Hierarquia de Chomsky (26/03/2015 - 07/04/2015)

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
Autômatos (09/04/2015 - 16/04/2015)

DES: Definição

DES baseado na Teoria de Autômatos

Implementação de algoritmos

  Linguagens e automatos para DES-parte2.pdf 
Linguagens e automatos para DES-parte2.pdf
  Linguagens e automatos para DES-total.pdf 
Linguagens e automatos para DES-total.pdf
  Linguagens e automatos para DES-parte1.pdf 
Linguagens e automatos para DES-parte1.pdf
    
Inicia em 24/04/2015 às 0h 0 e finaliza em 15/05/2015 às 23h 59
    
Inicia em 24/04/2015 às 0h 0 e finaliza em 29/05/2015 às 23h 59
Autômatos com guarda (21/04/2015 - 23/04/2015)

Autômatos com guarda

Statecharts (28/04/2015 - 30/04/2015)

Statechars: conceitos, modelos e propriedades

Rede de Petri (05/05/2015 - 05/05/2015)

DES baseados em Redes de Petri (RdP)

RdP: conceitos, modelos e propriedades

Implementação de algoritmos

  SED Redes de Petri.pdf 
SED Redes de Petri.pdf
  Rede de Petri - modelos gráficos 
SED Redes de Petri-parte1.pdf
Decidibilidade (07/05/2015 - 14/05/2015)

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 (19/05/2015 - 28/05/2015)

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 16/07/2015 às 0h 0 e finaliza em 21/07/2015 às 23h 59
Atividade prática (02/06/2015 - 09/07/2015)

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

Frequências da Turma
# Matrícula MAR ABR MAI JUN JUL Total
17 19 31 14 23 28 05 07 12 19 26 02 09 11 16 18 23 25 30 02
1 2015100**** 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 2
2 2015100**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 2015100**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 2015100**** 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0 3
5 2015100**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 2015100**** 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
7 2015100**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 2015100**** 0 0 2 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 2 6
9 2015100**** 0 0 2 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4
10 2015100**** 0 0 0 0 0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 1 5
11 2015100**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 2015100**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 2015100**** 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 2
14 2015100**** 0 0 0 0 0 0 2 0 0 2 0 0 0 0 2 0 0 0 0 1 7
15 2015100**** 0 0 0 2 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 6
16 2015100**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
17 2015100**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
18 2015100**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
19 2015100**** 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3
20 2015100**** 0 0 0 0 0 0 0 0 2 2 0 0 0 0 2 0 0 0 0 2 8
Notas da Turma
# Matrícula Unid. 1 Prova Final Resultado Faltas Situação
1 2015100**** 9,0 9.0 3 AM
2 2015100**** 8,7 8.7 2 AM
3 2015100**** 7,6 7.6 0 AM
4 2015100**** 7,3 7.3 4 AM
5 2015100**** 9,3 9.3 2 AM
6 2015100**** 7,9 7.9 0 AM
7 2015100**** 9,4 9.4 3 AM
8 2015100**** 8,4 8.4 7 AM
9 2015100**** 8,9 8.9 0 AM
10 2015100**** 8,6 8.6 2 AM
11 2015100**** 8,9 8.9 0 AM
12 2015100**** 9,0 9.0 6 AM
13 2015100**** 9,4 9.4 0 AM
14 2015100**** 8,4 8.4 5 AM
15 2015100**** 8,4 8.4 6 AM
16 2015100**** 9,0 9.0 8 AM
17 2015100**** 8,6 8.6 0 AM
18 2015100**** 8,8 8.8 0 AM
19 2015100**** 9,0 9.0 0 AM
20 2015100**** 8,7 8.7 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
17/03/2015
17/03/2015
Introdução: motivação e plano de ensino
19/03/2015
24/03/2015
Teoria da Computação: introdução
26/03/2015
07/04/2015
Hierarquia de Chomsky
09/04/2015
16/04/2015
Autômatos
21/04/2015
23/04/2015
Autômatos com guarda
28/04/2015
30/04/2015
Statecharts
05/05/2015
05/05/2015
Rede de Petri
07/05/2015
14/05/2015
Decidibilidade
19/05/2015
28/05/2015
Máquina de Turing
02/06/2015
09/07/2015
Atividade prática
Avaliações
Data Descrição
22/07/2015 Parte 1
23/07/2015 Parte 2
: 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
Recepção dos trabalhos 20/07/2015
Submissão das máquinas de turing 16/07/2015
Aula 16/07 16/07/2015
Trabalhos Máquina de Turing 14/07/2015
Última Aula e Recepção dos Trabalhos 07/07/2015
Aula 25/06 25/06/2015
Trabalho Final Máquina de Turing 23/06/2015
Aula 18/06 18/06/2015
Finalmente Máquinas de Turing! 16/06/2015
Mudança no início 11/06/2015
Entrega trabalho de Autômatos e Redes de Petri 10/06/2015
Máquina de Turing 09/06/2015
Parte 2 da Disciplina 01/06/2015
Atividades registradas 24/04/2015
Bate-papo quinta-feira 23/04 22/04/2015
Sobre a aula hoje quinta-feira 09/04 09/04/2015
Não haverá aula na terça (07/04) 06/04/2015
Atividades Práticas 20/03/2015

SIGAA | Superintendência de Tecnologia da Informação - STI/UFPI - (86) 3215-1124 | sigjb03.ufpi.br.sigaa vSIGAA_3.12.1054 29/03/2024 06:14