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

Engenharia de Sistemas e Informática

2005/2006
Equipa Docente e Horário
Estrutura e Funcionamento
Objectivos
Avaliação
Programa
Fichas Teórico-Práticas
Software
Contribuições dos Alunos
Exames
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 2005-2006 . 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 2004-2005: Página
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

(03-02-06)
(03-02-06)
  • As notas da 1ª e 2ª chamadas estão disponíveis em 1ª e 2ª Chamadas .
  • Na 2ª feira (dia 6) de tarde os alunos poderão ver os testes.
(02-02-06) Devido a um pequeno atraso na correcção da 2ª chamada, as notas da 1ª e 2ª chamadas serão aqui disponibilizadas amanhã de manhã (6a feira).
(30-01-06)
  • As notas práticas finais estão disponíveis em Notas Práticas Finais
  • Os grupos que ainda aparecem com a nota de 18 valores suspensa ( * ) deverão enviar o trabalho devidamente documentado ao docente João Saraiva até 5a feira. Caso contrário, ficarão com essa nota.
  • As notas da 1ª e 2ª Chamadas serão aqui disponibilizadas 5a feira.
(05-01-06)
  • As notas do segundo trabalho prático estão disponíveis em notas_tp2.html
  • Os grupos que pretenderem fazer melhoria da nota deste trabalho deverão fazê-lo até à data da 2ª Chamada (24 de Janeiro). Terão para tal de combinar a apresentação com o Tiago Alves.
(04-01-06)
  • Um texto sobre cálculo parcial aplicado a gramáticas independentes do contexto LL(1) está disponível em calculoParcial_LL.pdf
(03-01-06)
  • Os exames do ano anterior estão disponíveis na página de MPIII desse ano lectivo (ver link acima).
  • Um texto sobre cálculo parcial aplicado a autómatos finitos está disponível em calculoParcial_FA.pdf
  • Amanhã será disponibilizado um texto sobre cálculo parcial e gramática LL(1) (matéria teórica da última semana)
(19-12-05)
  • Os segundo trabalho prático deverá ser submetido até às 24:00 no sistema de submissão de trabalhos.
  • A página para submissão dos trabalhos está disponível aqui Submissão dos Trabalhos Online
(16-12-05)
  • Uma nova versão dos combinadores de Pretty Printing de tabelas está já disponível. Incluí o pretty printing em HTML. Substituam a directoria Tables em UMinho_Haskell_Libs/PrettyPrint pela nova versão disponível Tables.tgz
  • Os critérios de avaliação do trabalho prático estão disponíveis em Criterios e na
  • Entrega do Trabalho prático:
    • A entrega será feita no sistema de submissão online até às 24:00 de segunda-feira, dia 19 . Este sistema estará disponível na segunda-feira.
    • As apresentações serão feitas nos dois dias seguintes, isto é terça e quata-feira. As marcações estarão disponíveis sexta-feira dia 16, a partir das 12:00 na recepção do DI.
(07-12-05) O módulo DfaUtils.hs da biblioteca HaleX tem um erro: o tipo das funções isint e isident é [ Char ] - > Bool (e não Char - > Bool). Por favor, corrijam ou substituam o ficheiro por este DfaUtils.hs
(05-12-05)
  • A Ficha-Teórico-Prática nº12 já está disponível
  • As notas do 1º Trabalho Prático já estão disponíveis (ver secção Trabalhos Práticos)
(29-11-05)
  • Uma vez que os exercícios de autómatos com reacções de IO e estado não foram resolvidos nas aulas TPs, e para ajudar na resolução do trabalho, a solução da ficha prática nº8 é disponibilizada aos alunos (ver secção Fichas Teórico Práticas).
  • No trabalho prático inclui-se vários ficheiro para os alunos completarem, nomeadamante o próprio enunciado, o ficheiro readme e ainda a Makefile. A ideia é criarem, re-utilizando as bibliotecas HaLeX, HaGLR e de Pretty Printing, uma ferramenta hall (com funcionamento similar ao halex). A directoria HaLL poderá ser usada, por exemplo, para aí produzir o seu binário.
(28-11-05) O Trabalho Prático nº2 já está disponível
(25-11-05) A Ficha-Teórico-Prática nº11 já está disponível
(21-11-05) Entrega do 1º Trabalho Prático:
  • A entrega será realizada na 4ª e 5ª feira, dias 23 e 24 de Novembro.
  • A folha para marcação da apresentação está disponível hoje e amanhã na recepção do DI , tal como definido na aula teróric de hoje.
  • Os alunos deverão trazer o relatório em papel e a versão electrónica do trabalho que submeteram
  • Todos os elementos do grupo têm de estar presentes na apresentação
(18-11-05)
  • A Ficha-Teórico-Prática nº10 já está disponível
  • O ficheiros fonte (i.e., LaTeX) das fichas nº 7 e 9 estão agora também disponíveis
(11-11-05)
  • A página para a submissão do 1º Trabalho Prático está disponível em entrega trabalho prático
  • A Ficha-Teórico-Prática nº9 já está disponível
(04-11-05) A Ficha-Teórico-Prática nº8 já está disponível
(28-10-05)
  • A Ficha-Teórico-Prática nº7 já está disponível
  • Existe um bug na versão do sistema HaLeX disponibilizada: a função de visualização de autómato finitos não deterministas estava desactualizada. A versão correcta está agora disponível em HaLeX_1.1.tgz (ou na página do sistema).
  • Congelamento de notas práticas ver secção sobre trabalhos práticos
(21-10-05) A Ficha-Teórico-Prática nº6 já está disponível
(18-10-05)
  • A Ficha-Teórico-Prática nº5 já está disponível
  • Esta ficha será apresentada/resolvida na aula teórica de 5a. feira (20-11-05)
  • O período de apoio laboratorial aos alunos é às 4a. feiras, lab 1.09, das 14:00 às 16:00
(14-10-05) A Ficha-Teórico-Prática nº4 já está disponível
(11-10-05)
  • O Trabalho Prático nº1 já está disponível
  • O Trabalho Prático será apresentado/discutido na aula teórica de 5a feira, 13-11-05
  • Uma nova versão do sistema HaLeX (usada/referida) no trabalho será disponibilizada esta 5a. feira. Não usar a versão disponibilizada actualmente
(07-10-05) A Ficha-Teórico-Prática nº3 já está disponível
(30-09-05) A Ficha-Teórico-Prática nº2 já está disponível
(23-09-05)
  • A Ficha-Teórico-Prática nº1 já está disponível
  • 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-102
    T2 5ª Feira - 10:00-11:00 sala CP2-104
    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
  • Pedro Rangel Henriques

    Teórica-Prática: LESI TP1 2ª Feira - 14:00-16:00 sala DI-0.02
    Teórica-Prática: LESI TP2 2ª Feira - 16:00-18:00 sala DI-0.02
    Dúvidas LESI/MCC 2ª Feira - 11:00-13:00
  • Tiago Alves

    Teórica-Prática: LESI TP1 3ª Feira - 9:00-11:00 sala DI-A1
    Apoio Laboratorial LESI/LMCC 4ª Feira - 14:00-16:00 Sala de atendimento do DI

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 (NT) 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 componentes
  • 2 trabalhos práticos ( P1 e P2 ) a realizar durante o semestre
  • Uma prova individual escrita ( PE ) sobre os trabalhos práticos com 15 minutos de duração. Esta prova escrita será realizada imediatamente antes (ou depois) da avaliaçao teórica da disciplina.
A nota prática ( NP ) será obtida de acordo com a seguinte fórmula:
NP = P1 * 0.4 + P2 * 0.4 + PE * 0.2
A nota final será determinada de acordo com a seguinte fórmula:

NF = ( NT + NP )/2
Exige-se 8 valores como nota mínima em cada uma das partes.

5- Programa

  • Linguagens Resulares
    • Noções básicas
    • Expressões Regulares
      • Expressões Regulares como uma Linguaguem de Domínio Específico
      • Expressões Regulares Embebidas em Haskell
    • Autómatos Finitos
      • Autómatos finitos deterministas (AFD)
      • Autómatos finitos não-deterministas (AFND)
      • Cálculo Parcial aplicado a Autómatos Deterministas
      • Conversão de ANFDs em AFDs
      • Conversão de AFND am AFD através de cálculo parcial
      • Minimização de Estados de AFD
      • Autómatos reactivos
        • Aplicação dos autómatos à simulação de Sistemas de Controlo
        • Aplicação dos autómatos ao reconhecimento de Linguagens Regulares
        • Autómatos Reactivos como AFDs Monádicos em Haskell
  • Linguagens Não Regulares
    • Conceitos e exemplos
    • Estrutura concreta e abstracta das linguagens formais
    • Gramáticas Independentes do Contexto
    • Introdução ao Conceito de Parsing
      • Gramáticas LL(1) e Parsers Top-Down
      • Funções First , Follow e LookAhead
      • Modelação de Gramáticas Independente de Contexto em Haskell
      • Modelação de Parsers Top-Down em Haskell
      • Cálculo Parcial aplicado a Parsers Top-Down
      • Combinadores de Parsing

6- Fichas Teórico-Práticas

As fichas a realizar em cada aula teórico-prática são disponibilizadas nesta secção. As fichas estarão disponíveis na sexta-feira da semana anterior à aula a que se destinam.
  • Ficha Teórico-Prática nº 1: Expressões Regulares
  • Ficha Teórico-Prática nº 2: Autómatos Finitos Deterministas
  • Ficha Teórico-Prática nº 3: Autómatos Finitos Não Deterministas
  • Ficha Teórico-Prática nº 4: Conversão de Autómatos Finitos Não Deterministas em Deterministas
  • Ficha Teórico-Prática nº 5: Conversaõ de Expressões Regulares em Autómatos Finitos Não Deterministas
  • Ficha Teórico-Prática nº 6: Cálculo Parcial de Autómatos Finitos
  • Ficha Teórico-Prática nº 7: Autómatos Finito Deterministas Reactivos
  • Ficha Teórico-Prática nº 8: Autómatos Finito Deterministas Reactivos em Haskell
  • Ficha Teórico-Prática nº 9: Gramáticas Independentes do Contexto
  • Ficha Teórico-Prática nº 10: Gramáticas Independentes do Contexto em Haskell
  • Ficha Teórico-Prática nº 11: Propriedades de Gramáticas Independentes do Contexto em Haskell
  • Ficha Teórico-Prática nº 12: Função de Aceitação LL(1) em Haskell

7- Software

O seguinte software utilizado/recomendado nesta disciplina está já disponível:
8- Contribuições dos Alunos


9- Exames

Prova individual escrita sobre os trabalhos práticos
10- Trabalhos Práticos

Algumas resoluções destes trabalhos estão disponíveis na secção Contribuições dos Alunos

Os alunos que fizeram a parte prática da disciplina no ano lectivo 2004-2005 poderão congelar a nota que obtiveram e estão dispensados de realizar os trabalhos práticos neste ano lectivo. Para tal deverão contactar o responsável da disciplina antes do dia 11 de Novembro (data de entrega do 1º trabalho). Só serão congeladas as notas dos alunos que constam da seguinte lista: Notas Congeladas.

11- Sumários


Bibliografia

  • John Hopcroft, Rajeev Motwani and Jeffrey Ullman Introduction to Automata Theory, Languages and Computation Addison-Wesley 2nd Edition Edicao [HTML] 2001
  • 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 [HTML] 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 Tue Mar 7 13:38:40 2006