-

PPGCC001 - TEORIA DA COMPUTAÇÃO - Turma: 02 (2012.1)

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

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 
Teoria da Computação: introdução (27/03/2012 - 27/03/2012)

Autômatos e linguagens

Teoria da computabilidade

Teoria da complexidade

  aula1-TermosFormais 
Teoria da Computação; Termos Formais; Exercícios
Atividade prática 1 (29/03/2012 - 29/03/2012)

1) Fazer um texto de até uma lauda sobre a palestra de John Hopcroft realizada na UFMG em 2011:  

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.

 

 
Hierarquia de Chomsky (03/04/2012 - 03/04/2012)

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.
Atividade prática 2 (05/04/2012 - 05/04/2012)

 

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.

 

 
Autômatos (10/04/2012 - 19/04/2012)

DES: Definição

DES baseado na Teoria de Autômatos

Implementação de algoritmos
Autômatos com guarda (24/04/2012 - 24/04/2012)

Autômatos com guarda
Statecharts (26/04/2012 - 26/04/2012)

Statechars: conceitos, modelos e propriedades
Rede de Petri (01/05/2012 - 17/05/2012)

DES baseados em Redes de Petri (RdP)

RdP: conceitos, modelos e propriedades

Implementação de algoritmos
Máquina de Turing (22/05/2012 - 12/06/2012)

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

 
Decidibilidade (14/06/2012 - 03/07/2012)

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.

 
Atividade prática 3 (05/07/2012 - 05/07/2012)

Resolução de exercícios sobre máquinas de turing e decidibilidade.
Frequências da Turma
# Matrícula MAR ABR MAI JUN JUL Total
22 27 29 03 10 12 17 19 24 26 03 08 10 15 17 22 24 29 31 05 12 14 19 21 26 28 03 05
1 201210**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 201210**** 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 201210**** 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4
4 201210**** 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
5 201210**** 0 2 0 0 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14
6 201210**** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 201210**** 0 0 0 0 0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4
8 201210**** 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
9 201210**** 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 0 0 0 2
Notas da Turma
# Matrícula Unid. 1 Prova Final Resultado Faltas Situação
1 201210**** 9,0 9.0 0 AM
2 201210**** 8,3 8.3 0 AM
3 201210**** 8,8 8.8 0 AM
4 201210**** 7,5 7.5 0 AM
5 201210**** 8,0 8.0 0 AM
6 201210**** 8,8 8.8 0 AM
7 201210**** 8,5 8.5 0 AM
8 201210**** 8,5 8.5 0 AM
9 201210**** 8,3 8.3 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: Terça e quinta, 18-19h
Bibliografia:
Cronograma de Aulas

Início

Fim

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

Nenhum item foi encontrado

SIGAA | Superintendência de Tecnologia da Informação - STI/UFPI - (86) 3215-1124 | sigjb06.ufpi.br.instancia1 vSIGAA_3.12.495 17/01/2021 06:43