Ministério da Educação
Brasil um país de todos
Personal tools
You are here: Home → Members → Rodrigo Soares → Introdução a Teoria da Computação2014-1
Navigation
Log in


Forgot your password?
 
Document Actions

06239 - Introdução a Teoria da Computação

by Rodrigo Soares — last modified 2014-09-13 03:56

 

material e cronograma de aulas...
 

Hierarquia de Chomsky

 

  • Presença e Notas

    NOTAS PASSADAS: SEMESTRE 2009-2 em diante

Notas disponíveis abaixo

    NOTAS SEMESTRE 2014.1


 

  • PROJETOS

 

  • Comunicação


     Cadastre-se no https://groups.google.com/d/forum/itc-si1 e participe do Grupo de Introdução a Teoria da Computação (2014-1).
 

  • Ementa e Plano de Ensino

 

     Ementas e Conteúdo Programático

     PLANO de ENSINO


Livros...      

 

Elementos de Teoria da Computação. Harry R. Lewis, Christos H. Papdimitriou. 2. ed. 2004. (LIVRO-TEXTO)

Languages and Machines. Thomas Sudkamp, 3a. ed.  Addison-Wesley, 2005. (EXERCÍCIOS)

Menezes, Paulo Blauth. Linguagens Formais e Autômatos. Editora Sagra Luzzatto, 2000. (ALGORITMO DE MINIMIZAÇÃO DE ESTADOS)

Introdução aos fundamentos da Computação - Linguagens e Máquinas. Newton José Vieira. Thomsom, 2006.

Diverio, Tiarajú Asmuz e Menezes, Paulo Blauth. Teoria da Computação: Máquinas Universais e Computabilidade. Editora Sagra Luzzatto, 1999.

Introdução à Teoria de Autômatos, Linguagens e Computação. Hopcroft, J. E. e Ullman, J. D. e Motwani, R. Tradução. Editora Campus, 2003. Exercícios * resolvidos



Software

JFLAP JAVA Formal Language and Automata Package - ferramenta visual usada para criar e simular diversos tipos de autômatos, e converter diferentes representações de linguagens.


Slides


Execução de Aulas

BÔNUS MEGA-EXTRA

 

BÔNUS (10%): 

 

 

aula data assunto para casa
2 02.abr.14
  1. O que é Teoria da Computação
  2. Metodologia de Ensino
  3. Metodologia de Avaliação
Fundamentos de Matemática por Matemática Essencial -

MOTIVACIONAL: Os códigos e as linguagens...

Cap. 1 do Livro do Papadimitriou.

 

Uma breve introdução a Teoria da Computação
 

Revisão conteúdo de Matemática Discreta
4 07.abr.14

 

Alfabetos e Linguagens

  1. (60min) TESTE de Revisão de conceitos Preliminares de Matemática Discreta:
    1. Conjuntos
    2. Relações
    3. Funções
    4. Grafos
  2. Conceitos Preliminares

Cap. 1 do Livro do Papadimitriou.
6-8 09.abr.14 e 14.abr.14
 Conceitos Preliminares

Alfabetos e Linguagens

 Capítulo 1 do Livro-texto

21.abr.14FERIADOhttp://www.ufrpe.br/calendario.php
12
28.abr.14
visita MEC

14
 30.abr.14 

 TIRA-DÚVIDAS e

PROVA ESCRITA 1: expressões, fundamentos de linguagens

 

 Capítulo 1 do Livro-texto
12 05.mai.14
  1. Máquinas de Estados Finitos
  2. Autômatos Finitos Determinísticos

Cap. 1 do Livro do Papadimitriou.

Cap. 2 do Livro do Paulo Menezes

 

Animação: http://www.cs.montana.edu/~dynalab/
14 07.mai.14

Exercícios - Autômatos Finitos

Cap. 1 do Livro do Papadimitriou.

Cap. 2 do Livro do Paulo Menezes

Bônus-extra: Entender o Algoritmo de conversão de AFN em AFD e resolver a questão 2.2.6
16 19.mai.14

TIRA-DÚVIDAS e exercícios do Capítulo 2

  1. PROVA ESCRITA 2: TESTE Autômatos Finitos Determinísticos

 

 Capítulo 1 do Livro-texto
18 28.mai.14 AFN e Implementação de Autômatos
 		  
22 04.jun.14 Equivalência AFDs e AFNs
24 09.jun.14
  1. Autômatos e Linguagens
  2. Minimização de Estados
  3. PROVA ESCRITA 3: TESTE Autômatos Finitos Não-Determinísticos
  1. Seção 2.3 do Livro texto
  2. Seção 2.5 do Livro texto
  3. Algoritmo Minimização
  4. Outra explicação do algoritmo de minimização


  1. Minimização de Estados (continuação)
  2. TIRA-DÚVIDAS e exercícios do Capítulo 2
  1. Seção 2.3 do Livro texto
  2. Seção 2.5 do Livro texto
  3. Algoritmo Minimização
  4. Outra explicação do algoritmo de minimização



  1. estudos sobre Minimização de Estados (continuação)
  2. Equivalência AFDs e AFNs
  3. e resolução de exercícios do Capítulo 2



    1. Tira-dúvidas
    2. PROVA ESCRITA 4: Exp. regulares, AFD, AFN e minimização de estados
  1. BONUS EXTRA: (?????) Implementar em Python, usando Orientação a Objetos, um minimizador de autômatos que receba como ENTRADA: uma t-upla (definindo um autômato) e tenha como SAÍDA: o autômato mínimo.
    ENTREGA MÁXIMA: 04 de março, entrega de código-fonte e texto em formato de artigo científico: MODELO AQUI.
  2. FECHAMENTO 1 VA 
  

 NOVO PROFESSOR


 
26
 11.jun.14
  • Linguagens Livres de Contexto
  • Gramáticas Livres de Contexto
  • Exemplos
 Seção 3.1 do livro-texto

EXEMPLOS:

Gramática Python
Gramática Java
34  16.jun.14
  • Árvores de Análise Sintática
  1. Ambiguidade
  • Autômatos de Pilha
  • Exemplos
 Seções 3.2 e 3.3 do livro-texto
36 18.jun.14
Autômatos de Pilha e Gramáticas Livres de Contexto

 Seção 3.4 do livro-texto
38




25.jun.14

 

 
  • Determinismo e analise sintática
  1. Analise sintática descendente
 Seção 3.7 do livro-texto
40 30.jun.14

    • Analise sintática descendente (continuação)
    • Técnicas para A.P.'s determinísticos
    1. Lookahead

        Seção 3.7 do livro-texto
      42 02.jul.14
      • Analise sintática descendente (continuação)
      • Técnicas para A.P.'s determinísticos
      1. Lookahead
      2. Fatoracao a esquerda
      3. Remocao de recursao a esquerda
      • Exemplos
      		   Seção 3.7 do livro-texto
      44   07.jul.14
      • Analise sintática ascendente
      • Exemplos
      		   Seção 3.7 do livro-texto
       46 09.jul.14Revisão 
       48 14.jul.14 1A PROVA ESCRITA PARA 2VA
      		 Assunto: Capitulo 3 do livro-texto
       50 16.jul.14 Maquinas de Turing parte 1/2
      		Capitulo 4 do livro texto
      Notas de aula: aqui
       52 21.jul.14 Maquinas de Turing parte 2/2Capitulo 4 do livro texto
      Notas de aula: aqui
       54 23.jul.14 Indecidibilidade Notas de aula: aqui
       56 28.jul.14 Revisão 
       58 06.ago.14 2a PROVA ESCRITA PARA 2VA
      		 Capítulos 4 e 5 do livro texto
      Não caem as seções 4.4, 5.5, 5.6 e 5.7
       60 11.ago.14 3a VA
      		TUDO
       62 18.ago.14 PROVA FINAL
      		TUDO

























       

       

      • Avaliações

      NOTA 1V.A. = 4 Provas escritas + testes (90%) + trabalhos escolares (10%) + Bônus Extra e MEGA-Extra

      NOTA 2V.A. = Media aritmética de duas provas escritas

      NOTA 3V.A. = Prova escrita com todo o conteúdo (100%)

      NOTA FINAL = Prova escrita com todo o conteúdo (100%)

       

      A última avaliação será realizada no período sugerido para as VAs em Calendário Acadêmico.
                            bônus extras: possíveis exercícios do livro-texto e participações em aula.
                            penalidades: _toques de celulares (-3).
                                               _conversas paralelas (-2).
                                               _fontes adversas de informações (-5)

                                               _ informação de terceiros (Infração Disciplinar) - vide Regimento Geral da UFRPE, Cap. III, Seção IV, Art. 138, pg 113 a 118.
      Powered by Plone CMS, the Open Source Content Management System

      This site conforms to the following standards: