...collaborate on
SumáriosAulas

T (2005.02.21): Apresentação da Disciplina. Noção de refinamento.

TP (2005.02.22, 2005.02.24): Apresentação e marcação de turnos. Generalização das construções básicas das funções para as relações (do functor para o relator). A unidade nas relações. O produto de relações. Derivação de algumas das leis referidas como exercício de utilização do cálculo relacional.

T (2005.02.28): JOIN'05.

TP (2005.03.01): JOIN'05.

T (2005.03.07): Introdução ao refinamento de modelos de dados: relações de abstraçao e representação; a ordem de refinamento. Invariantes induzidos. Exemplos: algumas leis de reificação de conjuntos e correspondências.

TP (2005.03.03, 2005.03.08): Continuação da apresentação de relators: o coproduto de relações; o power relator. Derivação de algumas das leis referidas como exercício de utilização do cálculo relacional.

TP (2005.03.10, 2005.03.22): Catamorfismos relacionais: propriedades e exemplos.

T (2005.03.14): Estudo de algumas situações de refinamento de dados. Propriedades da relação de refinamento. Prototipagem: o legado Camila.

TP (2005.03.15): Assistir à apresentação sobre o "PURe Camila" por João Ferreira e Alexandra Mendes.

T (2005.03.21): Não houve aula (ausência do docente em reunião interna).

TP (2005.03.31, 2005.04.5): Especificação de propriedades como Catamorfismos Relacionais.

T (2005.04.04): Relacionadores e o refinamento estruturado. Leis de refinamento de conjuntos finitos, correspondências e representações por apontador. Introdução ao problema de desrecursivação de modelos de dados.

TP (2005.04.07, 2005.04.12): Utilização do Haskell na especificação do Software (comparação com VDM/Camila): abstração Set e Map; invariantes de tipo; pré e pós-condições nas operações; especificações não executáveis; características não funcionais (estado de objectos e do interpretador; operações IO; etc.). Apresentação dos projectos práticos da disciplina.

T (2005.04.11): Teorema de desrecursivação genérica: Função de abstracção e invariante concreto. Relações de pertença e acessibilidade estrutural. Cálculo da relação de acessibilidade para diversos exemplos.

TP (2005.04.14, 2005.04.19) Refinamento de Dados: caracterização abstracta; exemplos de refinamentos; exercícios sobre refinamento de dados e utilização da biblioteca CamilaPrelude? .

T (2005.04.18): Introdução ao refinamento algorítmico. Relação de satisfação de uma especificação (implícita) por uma função e sua generalização à satisfação de uma relação por outra. Enunciação e prova das propriedades básicas desta relação. Refinamento algoritmíco progressivo.

TP (2005.04.21, 2005.04.26) Refinamento de dados - exercício sobre normalização de dados para representação tabular.

T (2005.05.02): Continuação do sumário da aula anterior

TP (2005.04.28, 2005.05.03) Refinamento de dados: exercício sobre desrecursivação de dados.

T (2005.05.09): Noção de simulação. Resolução de equações de refinamento. Soluções funcionais e não funcionais.

TP (2005.05.05, 2005.05.17) Refinamento de algoritmos: Definição da relação "é implementado por". Demonstração de duas leis sobre a relação de implementação. Preenchimento dos inquéritos.

T (2005.05.16): Cálculo de simulações: análise de alguns casos de estudo.

TP (2005.05.19, 2005.05.24) Caso de estudo sobre refinamento de algoritmos: verificação da correcção do "insertion sort".

T (2005.05.23): Inter-combinação de ciclos e eliminação de recursão mútua. Teorema de Fokkinga e seus corolários. Exemplos de aplicação.

TP (2005.05.31, 2005.06.02) Recepção de trabalhos práticos.

T (2005.05.30): Conclusão da aula anterior. Introdução ao cálculo de soluções iterativas. Preenchimento dos inquéritos de avaliação e fecho da disciplina.

Métodos Formais de Programação II

2004-2005


Equipa Docente

Horários

Tipo Horário Sala
T 2as: 11-13 h DI A1
TP (Turno 1) 3as: 10-12 h DI 1.09
TP (Turno 2) 5as: 11-11 h DI 0.04

Horários de Atendimento

Docente Horário
Luís S. Barbosa a definir
Carlos Bacelar 2as 14-19

Nota: o contacto com os docentes através de email deve ser sempre feito a partir de contas institucionais da Universidade e com a indicação clara do nome da disciplina no subject.

Programa Resumido

  • Introdução ao cálculo de programas. Princípio da abstracção dos dados. Relações de abstracção e de representação. Inequações de refinamento.
  • Cálculo de refinamento formal de dados. Teorema de desrecursivação genérica. Relações de pertença estrutural e acessibilidade estrutural. Implementação de tipos indutivos polinomais em linguagens com gestão de memória dinâmica: Introdução de apontadores em linguagens tipo C/C++. Representação orientada a objectos.
  • Cálculo de refinamento algorítmico. A eficiência como principal motivação para o refinamento algorítmico. Fases do refinamento algorítmico: simulação, redução do não-determinismo, mudança de estrutura de dados virtual. Lei de refinamento funcional. Lei de refinamento relacional. Leis de fusão «vertical» e «horizontal». Lei de refinamento de simultâneo de dados e algoritmos. Cálculo de ciclos while como hilomorfismos.
  • Prototipagem rápida e integração com outras tecnologias. Introdução ao VDM++. Integração de protótipos reactivos em arquitecturas cliente-servidor. Emulação de serviços intermédios («middleware») e de serviços de dados («dataware»).

Critérios de Avaliação

  • Nota final
    • Componente Teórica (Exame): 70% (nota mínima de 8 valores)
    • Componente Prática: Facultativa, com um peso de 30%.
    • No caso não se realizar trabalho prático, o exame teórico conta integralmente para a nota final (100%), mas essa nota fica majorada a 16 valores.

Acetatos

  • Refinamento de modelos de dados (pdf)
  • Refinamento algoritmíco (pdf)

Aulas Práticas

Notas dos Exames

As notas da 1ª e 2ª chamadas estão disponíveis aqui (pdf).

A pauta da época de recurso está disponível aqui (pdf).

Projectos Práticos

  1. Reengenharia do interpretador PUReCamila
  2. Desenho de uma hiearquia de classes para os tipos do CamilaPrelude
  3. Camila/VDM frontend para Haskell
  4. Static analysis for VDM
  5. VDM.net

Ver descrição detalhada destes projectos na página PUReCamila.

Bibliografia

  • Algebra of Programming. R. Bird and O. de Moor. Series in Computer Science. Prentice-Hall International, 1997. C. A. R. Hoare, series editor.
  • Modelling Systems: Practical Tools and Techniques J. Fitzgerald and P.G. Larsen. Cambridge University Press, 1st edition, 1998, Cambridge University Press, 1999.
  • Systematic Software Development Using VDM. Cliff Jones,Prentice Hall (Hoare Series in Computer Science), 1986.
  • Recursion in Pointfree Style, J. N. Oliveira, (capítulo de livro em preparação), 2004.
  • Data representation and Refinement, J. N. Oliveira, (capítulo de livro em preparação), 2004.
  • Operation Refinement, J. N. Oliveira, (capítulo de livro em preparação), 2004.

r11 - 26 Feb 2007 - 00:31:23 - JoseBacelarAlmeida
This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback
Syndicate this site RSSATOM