Curso: Engenharia Informática

Área Científica: Informática/Ciências da Computação

Uc Anual      

Semestral    

Trimestral  

Obrigatória   T

Opcional     

Outra         T

Objectivos

Levar os alunos a compreender alguns dos limites e das potencialidades da computação, enquanto tema central da sua Licenciatura; apresentar os modelos de computação sub-Turing mais importantes, enquanto abstracção de dispositivos reais ou idealizados, estabelecendo uma hierarquia entre eles; estudar a influência de elementos como o não-determinismo, a existência de memória e tipo de acesso à memória, na capacidade computacional desses modelos; Desenvolver a capacidade de abstracção e o raciocínio abstracto dos alunos, sensibilizando-os para os aspectos teóricos da computação e a sua relação com a prática.

Objecto da Aprendizagem (conteúdo programático)

1. Introdução (3h)
   1. Motivação
   2. Alfabetos e linguagens
   3. Representações finitas de linguagens
   4. Expressões regulares
2. Autómatos Finitos (9h)
   1. Autómatos finitos determinísticos
   2. Autómatos finitos não-determinísticos
   3. Autómatos finitos e expressões regulares
   4. Linguagens regulares e não regulares
   5. Minimização de estados
3. Linguagens livres de contexto (13h)
   1. Gramáticas livres de contexto
   2. Árvores de sintaxe
   3. Autómatos de pilha
   4. Autómatos de pilha e gramáticas livres de contexto
   5. Linguagens livres de contexto e não livres de contexto
   6. Determinismo e análise sintática (parsing)

Processo de Avaliação – Classificação

Exame: 100%;  Avaliação contínua por tutória electrónica : 0%

Resultados de Aprendizagem (RA)

Horas de contacto com o docente

Horas de trabalho independente

Horas de Avaliação

Total

Listagem de RAs  (4 a 6)

T

TP

PL

OT

Estudo

Trab.

Grupo

Trab.

Projecto

Compreender o conceito formal de linguagem, a matemática das sequências de símbolos, e a existência de linguagens que não admitem representação finita.

3

3

1

9

16

Compreender a noção de linguagem regular e reconhecer a existência de linguagens não regulares.

3

3

1,5

9

16,5

Reconhecer a equivalência entre expressões regulares, autómatos finitos determinísticos e não determinísticos, enquanto dispositivos geradores ou reconhecedores de linguagens regulares, e saber converter entre uns e outros.

6

6

3

18

33

Compreender a noção de linguagem sem contexto e reconhecer a existência de linguagens fora dessa classe.

4

4

2

12

22

Reconhecer a equivalência entre gramáticas sem contexto e autómatos de pilha enquanto dispositivos geradores ou reconhecedores de linguagens sem contexto, e saber converter entre uns e outros.

5

5

2,5

15

27,5

Reconhecer a existência de linguagens sem contexto não-determinísticas e saber construir analisadores sintáticos para linguagens sem contexto determinísticas simples.

4

4

2

12

22

TOTAL

25

25

12

75

3

140

TOTAL/Sem (em 5 semanas)

5

5

2,4

15