Métodos de Programação III
Matemática e Ciências da Computação

Engenharia de Sistemas e Informática

2004/2005
Equipa Docente e Horário
Estrutura e Funcionamento
Objectivos
Avaliação
Programa
Fichas Teórico-Práticas
Software
Contribuições dos Alunos
Trabalhos Práticos
Sumários
Bibliografia

Esta página contém informação relativa à cadeira de Métodos de Programação III a decorrer no ano lectivo 2004-2005 . Métodos de Programação III é uma cadeira do 1º Semestre do 3º Ano das licenciaturas em Engenharia de Sistemas e Informática e em Matemática e Ciências da Computação. Referências para páginas de instâncias anteriores podem ser encontradas nos seguintes endereços:

Ano Lectivo 2003-2004: Página
Ano Lectivo 2002-2003: Página
Ano Lectivo 2000-2001: Página
Ano Lectivo 1999-2000: Página

Esta página está a ser gerada a partir de um documento XML, por uma ferramenta que utiliza os métodos de programação leccionados neste curso (eg, expressões regulares, autómatos finitos e gramáticas independentes do contexto). A partir da especificação XML é produzida esta página, bem como a sua representação em LaTeX. O formato LaTeX dá origem aos seguintes documentos em postscript e pdf: [ ps ] , [ pdf ]

Novidades e Avisos

(04-03-05) As notas finais estão disponíveis em: [ LMCC ] e [ LESI ]
(24-02-05)
  • As notas da época de recurso e dos trabalhos práticos estão disponíveis em: [ LMCC ] e [ LESI ]
  • Algumas resoluções dos trabalhos práticos estão disponíveis na secção Contribuições dos Alunos
(11-02-05)
  • As notas da 1ª e 2ª Chamadas estão disponíveis em [ LMCC ] e [ LESI ]
  • Os alunos que tem nota inferior a 8 valores terão de efectuar o exame da época de recurso.
  • Amanhã é possível ver o exame e tirar duvidas para o exame de recurso . Para isso deverão contactar o docente João Saraiva por telefone (ver número do telemovel na página pessoal) para marcar um encontro á porta do DI (que estará fechado da parte de tarde).
  • As notas práticas e as notas finais estarão disponíveis na próxima 2a feira
(10-02-05)
  • Devido à data tardia da 2ª Chamada, as notas finais (exames 1ª e 2ª Chamada e Trabalhos Práticos) serão disponbilizadas aqui amanhã (embora tardio achamos justo que ambas as chamadas sejam afixadas ao mesmo tempo) .
  • Exames da 1ª Chamada [ ps ] e 2ª Chamada [ ps ] .
(17-12-04)
  • Trabalho Prático nº2: Existe um erro no en únciado
    • A Referência Sar02 é o texto Especificação e Processamento de Linguagens ,
    • disponível na secção da bibliografia abaixo
    • obviamente, os grupos devem corrigir esse erro no relatório...
  • As fichas Teórico-Práticas nº10 e nº11 estão disponíveis (também na versão resolvida)
    • Esta matéria não será avaliada, nem sumariada
(10-12-04) O Trabalho Prático nº2 já está disponível
(04-12-04) Ficha-Teórico-Prática nº7 (Autómatos Reactivos em Haskell) Resolução (pdf produzido usando o lhs2TeX) Ficha7.pdf.
(03-12-04)
  • A Ficha-Teórico-Prática nº9 já está disponível
  • A Ferramenta Gram2C que permite definir gramáticas abstractas e catamorfismos em C está disponível na secção Software
(28-11-04) Trabalho Prático nº1: Trabalhos Recebidos
  • Os trabalhos recebidos até 28-11-04 são os que constam das seguintes listas de emails: lista1 , lista2
  • Os grupos cujo email não conste desta lista deverão contactar os docentes até à aula teórica do dia 2-11-04. Caso contrário será considerado que o trabalho não foi entregue.
  • Parabéns aos grupo da Mónica Santos pois foi o último grupo a submeter o trabalho dentro do prazo. Mais precisamente às 23:59 ! !
(26-11-04) A Ficha-Teórico-Prática nº8 já está disponível
(22-11-04) Trabalho Prático nº1:
  • Os extras referidos no enúnciado podem ser entregues com o 2º trabalho prático
  • Os grupos são obrigatoriamente de 3 alunos. Caso contrário a nota final terá uma penalização: a diferença entre o número de elementos do grupo e 3
(19-11-04)
  • A Ficha-Teórico-Prática nº7 já está disponível (ver secção respectiva)
  • Regras de Conversão de Expressões Regulares em Autómatos Finitos Não Deterministas: RegExp2Ndfa_rules.ps
  • Existe vária documentação na internet sobre conversão de Autómatos Finitos Deterministas em Expressões Regulares: basta fazer google...
(09-11-04) A Ficha-Teórico-Prática nº6 já está disponível (ver secção respectiva)
(09-11-04) O Trabalho Prático nº1 já está disponível
(04-11-04) Ficha Teórico-Prática nº 5: literate haskell ficha5.lhs.
(28-10-04) Ficha Teórico-Prática nº 4: literate haskell ficha4.lhs. e ps ficha4.ps (esta ficha usa uma figura que está disponível em ndfa.ps )
(22-10-04)
(18-10-04) Ficha Teórico-Prática nº 2: literate haskell ficha2.lhs. e pdf ficha2.pdf.
(11-10-04) Ficha Teórico-Prática nº 1: literate haskell ficha1.lhs. e pdf ficha1.pdf.
(24-09-04)
  • Na 2a. feira dia 27 de Setembro não há aula teórica
  • As aulas teórico-práticas começam na 1ª semana de Outubro
  • Na 5a. feira dia 30 de Setembro há aula teórica
(24-09-04) A página da disciplina está no "ar".

1- Equipa Docente e Horário

  • João Saraiva

    Teóricas: LESI/MCC T1 2ª Feira - 11:00-12:00 sala CP2-103
    T2 5ª Feira - 10:00-11:00 sala CP2-103
    Teórica-Prática: MCC TP1 4ª Feira - 11:00-13:00 sala DI 0.02
    MCC TP2 5ª Feira - 11:00-13:00 sala DI 0.02
    Dúvidas LESI/MCC 2ª Feira - 14:00-18:00
  • Jorge Gustavo Rocha

    Teórica-Prática: LESI TP1 2ª Feira - 14:00-16:00 sala DI-A2
    Teórica-Prática: LESI TP2 2ª Feira - 16:00-18:00 sala DI-A2
    LESI TP3 3ª Feira - 09:00-11:00 sala DI-A1
    LESI TP4 6ª Feira - 14:00-16:00 sala CP3-205
    Dúvidas LESI/MCC 3ª Feira - 11:00-13:00
2- Estrutura e Funcionamento

Exposição da matéria fundamental -- motivação, conceitos, definições, métodos e justificações -- a nível das aulas teóricas. Resolução de exercícios de consolidação, a nível das aulas teórico-práticas, no quadro e no computador. Realização, no computador, extra aulas de trabalhos concretos de aplicação, recorrendo à linguagem Haskell.
3- Objectivos

É objectivo deste curso levar os alunos a:
  • Aprofundar e interiorizar os conceitos fundamentais e os métodos de programação em larga escala e a reutilização de programas, dando especial relevo ao paradigma funcional.
  • 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.
  • Compreender os conceitos de cálculo parcial ou especialização de programas
  • Aprender o conceito de gramática e como descrever estruturas de linguagens através de gramáticas.
  • Compreender o conceito: embeber linguagens de dominio especifico (eg, gramáticas) numa linguagem de dominio geral (eg, Haskell).
  • Reforçar a aptidão dos alunos para desenvolver programas correctos e eficientes (quer no paradigma funcional quer em qualquer outro paradigma de programação).
4- Avaliação

A Avaliação tem uma componente teórica e uma componente prática, ambas obrigatórias.

De acordo com o regulamento actualmente em vigor na UM, a nota teórica será obtida através da realização de 1 prova individual escrita . Essa prova tem as instâncias a seguir indicadas (um aluno só poderá fazer melhoria na época de recurso):
  • Exame, realizado na 1ª chamada da época normal, no fim do 1º semestre
  • Exame, realizado na 2ª chamada da época normal, no fim do 1º semestre
  • Exame, realizado na época de recurso
A componente prática seré formada por 2 trabalhos para realização em grupo, sendo entregues acompanhados de um relatório sucinto e discutidos em frente ao computador: A nota prática será a média aritmética das classificações obtidas nos 2 trabalhos avaliados. A nota final será determinada de acordo com a seguinte fórmula:

NotaFinal = NotaTeorica * 0.50 + (NotaPratica - Delta / 2) * 0.50

sendo Delta = | NT - NP |

Exige-se 8 valores como nota mínima em cada parte.
5- Programa

  • Programação baseada em Transições de Estado:
    • Noções básicas
    • Autómatos Finitos
      • Autómatos não-deterministas
      • Autómatos deterministas
      • Cálculo Parcial aplicado a Autómatos Deterministas
      • Conversão de ANDs em ADs
      • Conversão de AFND am AFD através de cálculo parcial
      • Minimização de Estados de AFD
      • Autómatos reactivos
  • Programação baseada em Gramáticas:
    • Conceito e exemplos
    • Estrutura concreta e abstracta das linguagens formais
    • Desenvolvimento de Parsers baseados em Combinadores para Linguagens Formais.
6- Fichas Teórico-Práticas

  • Ficha Teórico-Prática nº 1: Expressões Regulares
  • Ficha Teórico-Prática nº 2: Expressões Regulares (continuação)
  • Ficha Teórico-Prática nº 3: Autómatos Finitos Deterministas
  • Ficha Teórico-Prática nº 4: Autómatos Finitos Não Deterministas
  • Ficha Teórico-Prática nº 5: Conversão de Autómatos Finitos Não Deterministas em Deterministas
  • Ficha Teórico-Prática nº 6: Conversão de Expressões Regulares em Autómatos Finitos Não Deterministas
    • literate haskell ficha6.tgz. (esta ficha usa várias figuras, daí o tgz)
  • Ficha Teórico-Prática nº 7: Autómatos Finitos Reactivos
  • Ficha Teórico-Prática nº 8: Cálculo Parcial de Autómatos Finitos
  • Ficha Teórico-Prática nº 9: Gramáticas Independentes do Contexto
  • Ficha Teórico-Prática nº 10: Combinadores de Parsing
  • Ficha Teórico-Prática nº 11: Combinadores de Parsing (continuação)
7- Software

  • Gramáticas em C: Gram2C.tgz
    • Este software usa o Bohem's Garbage Collector que é distribuído com o Gram2C. A versão do garbage collector que estava a ser distribuída (4.13) dava problemas em alguns sistemas operativos (segmentation fault durante a execução do programa). Nesse caso, recomenda-se a instalação de uma versão mais recente desse GC.
    • A versão que está disponível agora já é distribuída com uma versão mais recente do GC e deverá compilar e executar sem problemas.
  • A garbage collector for C and C + + : Bohem's Garbage Collector
  • Sistema HaLeX: HaLeX.tgz
8- Contribuições dos Alunos

  • Resolução dos trabalhos práticos propostos nesta disciplina por alguns grupos de trabalho:
    • Grupo constituído por: Bárbara Vieira (n. 38588), Hélder Teixeira (n. 39846) e Marco Coelho (n. 38618). Resolução: solução.
    • Grupo constituído por: Marcio (n. 24848), Miguel (n. 33195) e Luís (n. 22678). Resolução: solução TP1. e solução TP2.
    • Grupo constituído por: Daniela Cruz (n. 38612), Elisabete Ferreira (n. 38582) e Patrícia Oliveira (n. 38577). Resolução: solução.
    • Grupo constituído por: Hugo Pacheco (n. 38204), Rui Abreu (n. 38119) e João Falcão (n. 33171). Resolução: solução.
    • Grupo constituído por: Hugo Macedo (n. 39442) e Jose Correia (n. 38142). Resolução: solução.
    • Grupo constituído por: Ruben Fonseca (n. 38141) e Miguel Alves (n. 38221). Resolução: solução.
  • Função show de expressões regulares:
9- Trabalhos Práticos

Algumas resoluções destes trabalhos estão disponíveis na secção Contribuições dos Alunos
10- Sumários

Bibliografia

  • João Saraiva Language Processing (with a Functional Flavour) DI/UM 1ª Edicao 2000
  • L.S. Barbosa Elementos da Teoria dos Autómatos DI/UM [PS] 1996
  • João Saraiva Especificação e Processamento de Linguagens DI/UM 1ª Edicao [PS] [HTML] 1995
  • R. Floid and R. Beigel The Language of Machines: An Introduction to Computability and Formal Languages Computer Science Press 1994
  • S.P.Jones, et al Report on the Programming Language Haskell 98 [HTML] [PS] [PDF] 1999
  • R. Bird Introduction to Functional Programming using Haskell Prentice Hall 1998
  • S. Thompson Haskell - The Craft of Functional Programming Addison-Wesley 2ª Edicao 1999
  • N. Jones, C. Gomard and P. Sestoff Partial Evaluation and Automatic Program Generation Prentice Hall 1993
  • E. Horowitz and S. Sahni Fundamentos de Estruturas de Dados Editora Campus 1984
  • J. Carroll and D. Long Theory of Finite Automata Prentice Hall 1989
Pagina mantida por:

João Saraiva

jas@di.uminho.pt		 Page produced by a Tool generated by LRC from the XML document pagina_mpiii.xml

Last Change on Fri Mar 4 17:35:47 2005