Métodos de Programação 3 -- HOME PAGE
Matemática e Ciências da Computação -- 3º ano ()
José Carlos Ramalho (0 + 1 + 0)
Resolução dos exercícios de consolidação, no quadro e no computador (usando projector MM), a nível das aulas teórico-práticas.
Realização, no computador, de trabalhos concretos de aplicação, em ambiente Linux, recorrendo à linguagem Haskell, ou C; os trabalhos serão desenvolvidos extra aulas.
É objectivo fundamental deste curso levar os alunos a:
Aprender, o conceito de Sistemas de Produção baseados em Padrões e a noção de Programação por Regras Condição-Reacção, recorrendo ao uso de Expressões Regulares
Recordar, ou Aprender, o conceito de Autómato Finito e a teoria associada, bem como a sua aplicação à simulação de Sistemas de Controlo e à especificação e reconhecimento de Linguagens Regulares;
Aprender o Conceito de Linguagem e de Gramática e o método de programação gramatical, sendo capaz de embeber linguagens de domínio específico (gramáticas especiais) numa linguagem de domínio geral (como, p.ex., o Haskell);
Aprofundar e interiorizar os conceitos de reutilização de programas e a sua especialização por cálculo parcial, dando especial relevo ao paradigma funcional
Exame, realizado na época de recurso, agora também no fim do semestre
A componente prática consistirá na resolução de dois problemas, envolvendo a análise de um enunciado concreto, o planeamento da resolução e a sua implementação em computador. Um dos enunciados versará a manipulação de Expressões Regulares e o outro será orientado ao trabalho com Autómatos.
O trabalho será realizado ao longo do semestre, extra-aulas e em grupo de 2 ou 3 alunos, sendo apresentado ao docente, para ser discutido em frente ao computador, acompanhado dum relatório sucinto, em datas a combinar com os alunos.
Cada Trabalho Prático será classificado de acordo com os seguintes escalões:
A nota final será determinada de acordo com a seguinte fórmula: NotaFinal = NotaTeorica * 0.60 + NotaPratica * 0.40
Exige-se 8 valores como nota mínima em cada uma das partes.
Para fazer o download (do ficheiro postscript ou literate haskell) do enunciado dos Trabalhos Práticos propostos, clique abaixo:
Enunciado (postscript) da 1º Folha de Problemas para 2002/2003
Ficheiro de Moradas para teste do problema 4 da 1º Folha de Problemas
Enunciado (postscript) da 2º Folha de Problemas para 2002/2003
Esboço do Relatório (literate haskell) para a 2º Folha de Problemas para 2002/2003
Notas Finais das 2 Chamadas da 1ª Época da LESI
Notas Finais das 2 Chamadas da 1ª Época da LMCC
I. Programação baseada em Sistemas de Produção:
I.1 Princípio geral da Programação baseada em Regras Condição-Acção
I.2 O papel dos Padrões no problema da definição de Condições; teste das condições e Concordância de Padrões
I.3 Sistemas de Produção: conceito e componentes (BF, BR e Motor); exemplos diversos
I.4 Sistemas de Produção: forward- e backward-chaining; comparação com sistemas de reescrita e de prova de teoremas
I.5 Sistemas de Produção: algoritmo base e variantes.
II. Uso de Expressões Regulares para definição e reconhecimento de Padrões:
II.1 Definição formal de Expressão Regular (ER) e seus axiomas
II.2 Exemplos de utilização de ERs
II.3 Derivação de Frases a partir de ERs
II.4 Reconhecimento de Frases; concordância com ERs
III. Uso de Autómatos Finitos para definição e reconhecimento de Padrões:
III.1 Programação baseada em Máquinas de Transição de Estado; noções básicas
III.2 Autómatos Não-Deterministas (AND): definições e reconhecimento
III.3 Autómatos Deterministas (AD): definições e reconhecimento
III.4 Conversão de ANDs em ADs; função de fecho de estados e regras de conversão
III.5 Minimização de estados de um AD
III.6 Conversão de ERs em ANDs
III.7 Autómatos Reactivos (ADR); sua aplicação à simulação de Sistemas de Controlo
III.8 O utilitário Lex
IV. Programação baseada em Gramáticas:
IV.1 Gramáticas Regulares (GR) e Gramáticas Independentes de Contexto (GIC)
IV.2 Gramática Concreta e Gramática Abstracta
IV.3 Derivação de Frases a partir de Gramáticas
IV.4 Reconhecimento de Frases (parsing); Método Recursivo-Descendente
V. Reutilização de programas:
V.1 Programação Generalizada via parametrização
V.2 Especialização de Programas: conceito e exemplos de Partial Evaluation
J.A. Saraiva, "Language Processing (with a Functional Flavour)", Notas Pedagógicas, DI/UM, 2000
J.A. Saraiva, "Especificação e Processamento de Linguagens", Notas Pedagógicas, DI/UM, 1995
L.S. Barbosa, "Elementos da Teoria dos Autómatos", Monografia DI-LSB-96:5:1, DI/UM, 1996
J.J. Almeida & J.B. Barros & P.R. Henriques, "O Ambiente de Desenvolvimento Unix", Notas Pedagógicas, DI/UM, 1990