Objetivos e resultados da aprendizagem

Teoria da Computação

 

Existem limites à capacidade de resolução de problemas por um computador, mesmo na hipótese “idealista” de ausência de restrições, quer sejam essas o tempo (de execução) ou o espaço (memória).

Esta unidade curricular tem como objetivos:

- perceber a capacidade de computação das máquinas, assim como os seus limites teóricos. Para tal, é necessário definir formalmente o que é e o que não é um programa, um algoritmo;

- perceber os fundamentos das linguagens de programação. Para tal, é necessário estudar as construções que determinam a capacidade de computação das linguagens, assim como o comportamento dos programas.

O aluno deverá ser capaz de:

- perceber e usar a capacidade de computação das máquinas, assim como os seus limites teóricos. 

- formalizar adequadamente e avaliar se determinados problemas tem solução computacional ou não.

- perceber e saber usar modelos, técnicas e algoritmos de computação simbólica introduzidos na resolução de problemas informáticos do dia-a-dia

 

Programa

Teoria da Computação

 

Resumido

A. Introdução

B. Modelos da Computação I: Autómatos de Estados Finitos

C. Teoria das Linguagens Formais

D. Modelos da Computação II: Autómatos com Pilha

E. Modelos da Computação III: Máquinas de Turing

F. A Não Computabilidade e a Indecidibilidade

G. Modelos de Computação Alternativos

H. Programação em Modelos da Computação (aulas pratico-laboratoriais)

Detalhado

A. Introdução

Capítulo 1. Introdução e conceitos básicos

B. Modelos da Computação I: Autómatos de Estados Finitos

Capítulo 2. Autómatos finitos

C. Teoria das Linguagens Formais

Capítulo 3. Expressões, linguagens e gramáticas regulares

Capítulo 4. Propriedades das linguagens regulares

Capítulo 5. Linguagens livres/independentes de contexto

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

Capítulo 8. Propriedades das linguagens livres de contexto

D. Modelos da Computação II: Autómatos com Pilha

Capítulo 7. Autómatos de pilha

E. Modelos da Computação III: Máquinas de Turing

Capítulo 9. Máquinas de Turing

Capítulo 10. Outras máquinas de Turing

Capítulo 11. Uma hierarquia de linguagens formais e autómatos

F. A Não Computabilidade e a Indecidibilidade

Capítulo 12. Limites da computação algorítmica

G. Modelos de Computação Alternativos

Capítulo 13. Outros modelos de computação

H. Programação em Modelos da Computação (aulas pratico-laboratoriais)

 

Bibliografia

Teoria da Computação

 

"An Introduction to Formal Languages and Automata", 4th Ed, 2006

Peter Linz

Jones and Bartelett Computer Science

 

"Teoria da Computação - Computabilidade e Complexidade", 2010

Francisco Coelho e João Pedro Neto

Escolar Editora

ISBN: 978-972-592-281-1

 

"Elements for the Theory of Computation", 2nd Ed, 1998

Harry Lewis and Christos Papadimitriou

Prentice Hall, 1998.

 

"Models of Computation and Formal Languages", 1998

R. Gregory Taylor

Oxford University Press

 

"Introduction to Automata Theory, Languages and Computation", 2nd Ed, 2001

John Hopcroft, Rajeev Motwani, Jeffrey Ullman

Addison Wesley

 

Critérios de avaliação

Teoria da Computação

 

A avaliação no período de Aprendizagem consiste no seguinte :

- 2 Testes escritos (Frequências): 14 valores (7 + 7)

- 2 Trabalhos práticos a realizar nas aulas prático-laboratoriais (PL): 6 valores (3 + 3)

Aprendizagem = Trabalhos práticos + Testes escritos (Frequências)

em que,

- Presença nas aulas inferior a 50%   ==>   Reprovado e Não Admitido a Exame

- Trabalhos práticos < 1,5 (em 6)   ==>   Reprovado e Não Admitido a Exame

- Aprendizagem < 5,5 (em 20)   ==>   Reprovado e Não Admitido a Exame

- Aprendizagem >= 9,5 (em 20)   ==>   Aprovado e Dispensado de Exame

- Outros casos   ==>   Reprovado e Admitido a Exame

 

Exame = Trabalhos práticos + Teste escrito

em que,

- Trabalhos práticos (realizados durante o período de Aprendizagem): 6 valores

- Teste escrito: 14 valores

 

Datas das avaliações

Teoria da Computação

 

Tipo

Data

Hora

Salas

Resolução

Frequência 1

3/abril

18h

Bloco 6

download

Frequência 2

30/maio

18h

6.5/6.6/6.17/6.18

download

Trabalho 1

27-29/Março

Aulas PL

 

download

Trabalho 2

22-24/Maio

Aulas PL

 

download

Exame Normal

 

 

 

download

 

 

 

 

download

Testes de anos anteriores (com resolução)

Frequência1_2009-2010

Frequência2_2009-2010

Exame1_2010-2011

Exame2_2010-2011

 

Classificações obtidas

Teoria da Computação

 

Ano letivo 2016/2017 (necessita de senha de acesso)

Presenças nas aulas

Trabalho Prático 1

Trabalho Prático 2

Frequência 1

Frequência 2  ==>  Os testes podem ser consultados no dia 21/junho, 4ª feira, das 14:30h às 18:00h, no gabinete 4.2

Aprendizagem (Trabalhos + Frequências + Presenças)

 

Exame Época Normal - Teste  ==>  Os testes podem ser consultados no dia 5/julho (11:30h às 13:00h) ou 6/julho (11h às 13h), no gabinete 4.2

Exame Época Normal - Total (Trabalhos práticos + Teste)

 

Exame Época Recurso - Teste  ==>  Os testes podem ser consultados no dia 19/julho (14:30h às 16:00h) ou 20/julho (11h às 12h), no gabinete 4.2

Exame Época Recurso - Total (Trabalhos práticos + Teste)

 

Exame Época Especial - Teste  ==>  Os testes podem ser consultados no dia 25/julho, 3ª feira, das 14:30h às 15:00h, no gabinete 4.2

Exame Época Especial - Total (Trabalhos práticos + Teste)

 

Apontamentos

Teoria da Computação

 

Capítulo 1 - Introdução (apontamentos) (slides)

Capítulo 2 - Autómatos de estados finitos (apontamentos) (slides).

                    Minimização/redução de autómatos finitos determinísticos (apontamentos).

Capítulo 3 - Expressões, linguagens e gramáticas regulares (apontamentos) (slides)

Capítulo 4 - Propriedades das linguagens regulares (apontamentos) (slides)

Capítulo 5 - Linguagens livres/independentes de contexto (apontamentos) (slides)

Capítulo 6 - Simplificação de gramáticas livres de contexto e formais normais (apontamentos) (slides)

Capítulo 7 - Autómatos de pilha (apontamentos) (slides)

Capítulo 8 - Propriedades das linguagens livres de contexto (apontamentos) (slides)

Capítulo 9 - Máquinas de Turing (apontamentos) (slides)

Capítulo 10 - Outras máquinas de Turing (apontamentos) (slides)

Capítulo 11. Uma hierarquia de linguagens formais e autómatos (slides)

Capítulo 12. Limites da computação algorítmica (apontamentos) (slides)

Capítulo 13. Outros modelos de computação (apontamentos) (slides)

 

Folhas práticas

Teoria da Computação

 

Folha prática 1 - Introdução e definições básicas

Folha prática 2 - Autómatos Finitos (Determinísticos e Não Determinísticos)

Folha prática 3 - Minimização/redução de Autómatos Finitos Determinísticos

Folha prática 4 - Expressões, Linguagens e Gramáticas Regulares

Folha prática 5 - Expressões e Gramáticas Regulares e Autómatos Finitos

Folha prática 6 - Linguagens e Gramáticas Livres de Contexto

Folha prática 7 - Autómatos de Pilha e Linguagens Livres de Contexto 

Folha prática 8 - Máquinas de Turing

Ficheiros

TheoryComputation.txt

Cadeias_01.txt

Cadeias_012.txt

Cadeias_TF.txt

Cadeias_ab.txt

Cadeias_anbm.txt

 

Folha8.c

Outros apontamentos

Método de Indução Matemática

Ferramentas usadas

JFLAP - Aplicação  +  Tutorial

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

 

Horário

Teoria da Computação

 

Horas

Segunda

Sala

Terça

Sala

Quarta

Sala

Quinta

Sala

Sexta

Sala

8

  

 

 

 

 

 

 

 

 

 

9

 

 

 

 

ATEND

G4.2

 

 

 

 

10

 

 

 

 

ATEND 

G4.2

 

 

 

 

11

 

 

ATEND

G4.2

PL4

6.14

 

 

 

 

12

 

 

ATEND 

G4.2

PL4

6.14

 

 

 

 

13

 

 

  

  

 

 

 

 

 

 

14

PL1

6.13

 

 

TE

6.3

 

 

 

 

15

PL1

6.13

 

 

TE

6.3

 

 

 

 

16

PL2

6.13

PL3

6.13

 

 

 

 

 

 

17

PL2

6.13

PL3

6.13

 

 

 

 

 

 

18