Scribd Logo
Carregar

Bem-vindo(a) ao Scribd!

  • 264 visualizações

    Introducao A Teoria Da Computacao

    Enviado por

    demmaa
    Este documento descreve uma disciplina introdutória sobre Teoria da Computação oferecida na Universidade Federal Rural de Pernambuco. A disciplina aborda tópicos como autômatos finitos e não determinísticos, linguagens formais regulares e sensíveis ao contexto, e problemas de computabilidade como a função de parada. A carga horária total é de 60 horas ao longo de 4 horas semanais.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato DOC, PDF, TXT ou leia online no Scribd

    Introducao A Teoria Da Computacao

    Enviado por

    demmaa
    264 visualizações2 páginas
    Este documento descreve uma disciplina introdutória sobre Teoria da Computação oferecida na Universidade Federal Rural de Pernambuco. A disciplina aborda tópicos como autômatos finitos e não determinísticos, linguagens formais regulares e sensíveis ao contexto, e problemas de computabilidade como a função de parada. A carga horária total é de 60 horas ao longo de 4 horas semanais.

    Descrição original:

    Introducao a Teoria da Computacao

    Título original

    Introducao a Teoria Da Computacao

    Direitos autorais

    © © All Rights Reserved

    Formatos disponíveis

    DOC, PDF, TXT ou leia online no Scribd

    Você considera este documento útil?

    Este conteúdo é inapropriado?

    Este documento descreve uma disciplina introdutória sobre Teoria da Computação oferecida na Universidade Federal Rural de Pernambuco. A disciplina aborda tópicos como autômatos finitos e não determinísticos, linguagens formais regulares e sensíveis ao contexto, e problemas de computabilidade como a função de parada. A carga horária total é de 60 horas ao longo de 4 horas semanais.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato DOC, PDF, TXT ou leia online no Scribd
    Fazer download em doc, pdf ou txt
    264 visualizações2 páginas

    Introducao A Teoria Da Computacao

    Enviado por

    demmaa
    Este documento descreve uma disciplina introdutória sobre Teoria da Computação oferecida na Universidade Federal Rural de Pernambuco. A disciplina aborda tópicos como autômatos finitos e não determinísticos, linguagens formais regulares e sensíveis ao contexto, e problemas de computabilidade como a função de parada. A carga horária total é de 60 horas ao longo de 4 horas semanais.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato DOC, PDF, TXT ou leia online no Scribd
    Fazer download em doc, pdf ou txt
    de 2

    UNIVERSIDADE FEDERAL RURAL DE PERNAMBUCO

    Pró-Reitoria de Ensino de Graduação


    Coordenação do Curso de Bacharelado em Sistemas de Informação
    Site: http://www.bsi.ufrpe.br
    E-mail: [email protected]

    PROGRAMA DE DISCIPLINA
    IDENTIFICAÇÃO
    DISCIPLINA: Introdução a Teoria da Computação CÓDIGO: 06239

    DEPARTAMENTO: Estatística e Informática ÁREA: Sistemas Computacionais


    CARGA HORÁRIA TOTAL : 60
    NÚMERO DE CRÉDITOS: 04
    CARGA HORÁRIA SEMANAL: 4 TEÓRICAS: 4 PRÁTICAS: 0
    PRÉ-REQUISITOS: Matemática Discreta

    EMENTA
    Autômatos: Finitos, a Pilha e Máquina de Turing (linearmente limitada). Linguagens
    Formais: Regular, Livre e Sensível ao Contexto, Estrutura de Frases. Hierarquia de
    Chomsky. Aplicações em compiladores. Computabilidade: modelos computacionais
    (funções recursivas, linguagens de programação), funções não computáveis, problema
    da parada, decidibilidade.

    CONTEÚDOS
    UNIDADES E ASSUNTOS
    1. Introdução e Conceitos Básicos: Notas Históricas, Abordagem e Conceitos
    Básicos
    2. Autômatos
    2.1 Finitos (Determinísticos e Não-determinísticos)
    2.2 a Pilha
    2.3 Máquina de Turing
    2.4 Equivalência de Máquinas
    3. Linguagens Formais
    3.1 Regular
    3.2 Livre de Contexto
    3.3 Sensível ao Contexto
    3.4 Estrutura de Frases
    3.5 Gramáticas
    3.6 Hierarquia de Chomsky
    4. Computabilidade
    4.1 Modelos Computacionais
    4.2 Funções Recursivas
    4.3 Funções não-computáveis
    Continuação
    DISCIPLINA: Introdução a Teoria da Computação CÓDIGO: 06239

    UNIDADES E ASSUNTOS

    4.6 Problema da Parada


    4.7 Decidibilidade
    5. Conclusões
    5.1 Resumo dos Principais Conceitos
    5.2 Contribuições da Teoria da Computação

    BIBLIOGRAFIA
    BÁSICA
    1. LEWIS, Harry R; PAPADIMITRIOU, Christos H. Elementos de teoria da
    computação. 2. ed. Porto Alegre: Bookman, 2000. 339 p. ISBN8573075341.
    2. MENEZES, Paulo Blauth. Linguagens formais e autômatos. 5. ed. Porto
    Alegre, RS: Bookman, 2008. 215p. (Livros didáticos ;n.3)
    ISBN9788577802661.
    3. DIVERIO, Tiarajú A; MENEZES, Paulo Blauth. Teoria da computação:
    máquinas universais e computabilidade. 2. ed. Porto Alegre: Sagra Luzzatto,
    2008. 205 p. (Série livros didáticos. Instituto de informática da UFRG ;5)
    ISBN 9788577802678.

    COMPLEMENTAR
    4. VIEIRA, Newton José. Introdução aos fundamentos da computação:
    linguagem e máquinas. São Paulo: Thomson, 2006. xiii, 319p.
    5. SUDKAMP, Thomas A. Languages and machines: an introduction to the
    theory of computer science. 3rd ed. Boston, MA: Pearson Addison-Wesley,c
    2006. xvii, 654 p. ISBN 0321322215.
    6. HOPCROFT, John E.; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introdução
    à teoria de autômatos, linguagens e computação. Rio de Janeiro:Campus,
    c2003. 560 p. ISBN 8535210725.
    7. MIT Open Course: http://ocw.mit.edu/courses/electrical-engineering-and-
    computer-science/6-441-information-theory-spring-2010/index.htm
    8. Stanford Course: http://infolab.stanford.edu/ ullman/ialc.html

    Você também pode gostar