Teoria da Computação

1.

Estudar os princípios básicos dos computadores e da computação, através de diversos modelos abstractos de

- Autómatos (modelos de hardware)

- Linguagens formais (modelos de linguagens de programação)

Constatar a relação entre os diversos modelos abstractos de computação

2.

Estudar os princípios básicos da complexidade algorítmica

- o que é um algoritmo

- como se analisa a sua complexidade

- o que é computável

- o que não é (nem será ?) computável

Uma viagem dos autómatos finitos (máquinas de estados finitos) ….

às …

Máquinas de Turing

Resumido

A. Introdução e conceitos básicos

B. Autómatos finitos

C. Expressões, linguagens e gramáticas regulares

D. Linguagens livres/independentes de contexto

E. Autómatos de pilha

F. Máquinas de Turing

G. Introdução à complexidade computacional

Detalhado

Cap. 1 - Introdução e definições básicas

Conceitos básicos

Linguagens

Gramáticas

Autómatos

Determinísticos (DFA)

Não Determinísticos (NFA)

Equivalência entre DFA e NFA

Autómatos finitos transdutores

Expressões regulares

Relação entre expressões regulares e linguagens regulares

Gramáticas regulares

Equivalência entre gramáticas regulares, linguagens regulares e DFA.

Cap. 4 - Propriedades das linguagens regulares

Propriedades de fecho

Lema da bombagem

Gramáticas livres de contexto

Parsing e ambiguidade nas gramáticas e linguagens

Cap. 6 - Simplificação de gramáticas livres de contexto e formas normais

Transformação de gramáticas

Forma Normal de Chomsky

Forma Normal de Greibach

Cap. 8 - Propriedades das linguagens livres de contexto

Lemas de bombagem

Propriedades de fecho

Autómatos de pilha não-determinísticos

Relação com linguagens livres de contexto

Autómatos de pilha determinísticos e linguagens livres de contexto determinísticas

Máquina de Turing padrão

Combinação de máquinas de Turing

Tese de Turing

Cap. 10 - Outras máquinas de Turing

Pequenas variações de máquina de Turing

Máquinas de Turing com várias fitas

Máquinas de Turing não-determinísticas

Máquina de Turing universal

Autómatos linearmente limitados (LBA)

Problemas irresolúveis pela máquina de Turing

Problemas indecidíveis para linguagens recursivamente enumeráveis

O problema da correspondência de Post

Problemas indecidíveis para linguagens livres de contexto

Cap. 13 - Outros modelos de computação

Funções recursivas

Sistemas de Post

Sistemas de rescrita

Cálculo-lambda

Máquinas de Turing e complexidade

Famílias de Linguagens e complexidade

Classes de complexidade P e NP

An Introduction to Formal Languages and Automata, 4th Ed.

Peter Linz

Jones and Bartelett Computer Science, 2006

Teoria da Computação - Computabilidade e Complexidade,
Francisco Coelho e João Pedro Neto
Escolar Editora, 2010.
ISBN: 978-972-592-281-1

Elements for the Theory of Computation, 2nd Ed.

Harry Lewis and Christos Papadimitriou

Prentice Hall, 1998.

Models of Computation and Formal Languages

R. Gregory Taylor

Oxford University Press, 1998

Introduction to Automata Theory, Languages and Computation, 2nd Ed.

John Hopcroft, Rajeev Motwani, Jeffrey Ullman

Addison Wesley, 2001.

A avaliação consiste no seguinte :

• 2 frequências: 10 + 10 valores

NotaFinal = Frequência 1 +  Frequência 2

em que,

• NotaFinal < 6      ==>  Reprovado e Não Admitido a Exame

• Frequência 1 < 4 ou Frequência 2 < 4   ==>  Reprovado e Admitido a Exame

Tipo	Data	Hora	Salas	Resolução
Frequência 1	22-11-2010	18h	6.4 - 6.5 - 6.6	Descarregar
Frequência 2	11-01-2011	18h	6.4 - 6.5 - 6.6	Descarregar
Exame 1
Exame 2

 

Outros apontamentos

Outras folhas práticas

Ferramentas usadas

Deus Ex-Machina (DEM) - Aplicação  +  Tutorial

Testes dos anos anteriores

Ano lectivo 2009/2010

Frequência 1

Frequência 2

Horas	Segunda	Sala	Terça	Sala	Quarta	Sala	Quinta	Sala	Sexta	Sala
8
9
10
11	LFC-PL3	6.25	LFC-PL1	6.25
12	LFC-PL3	6.25	LFC-PL1	6.25
13
14			LFC-TE	6.18
15			LFC-TE	6.18
16
17	LFC-PL2	6.25
18	LFC-PL2	6.25
19